Anchor-based Multi-view Subspace Clustering with Hierarchical Feature Descent

The decision variables for the objective function are $\{\mathbf{W}^{(v)}_{i}\}_{i=1}^{\delta},\mathbf{A}$, $\mathbf{Z}$ and $\boldsymbol{\alpha}$. As a result, we introduce a four-step iterative optimization method to approximate the optimal target mentioned in Eq. (6). In this approach, we keep three variables fixed while optimizing the remaining ones. The specific procedure is derived from the following detailed steps.

Where $\boldsymbol{\Omega}$ denotes the hierarchical dimensional projection series $\mathbf{W}^{(v)}_{1}\mathbf{W}^{(v)}_{2}\cdots\mathbf{W}^{(v)}_{o-1}$. The multiplication term $\hat{\mathbf{A}}_{o}\mathbf{Z}$ refers to the anchor-based subspace reconstruction of $i$-th layer’s representation, and $\hat{\mathbf{A}}_{o}$ denotes the generalized anchors. Through deduction of matrix Frobenius norm and let $\mathbf{M}^{(v)}=\boldsymbol{\Omega}^{\top}\mathbf{X}^{(v)}\mathbf{Z}^{\top}\mathbf{A}^{\top}$, Eq. (3.2.1) can be reformulated as:

Denote the SVD of matrix $\mathbf{M}^{(v)}$ as $\mathbf{U}_{\mathbf{M}}\mathbf{D}_{\mathbf{M}}\mathbf{V}_{\mathbf{M}}^{\top}$ and the optimal solution of Eq. (9) is demonstrated as ${\mathbf{W}^{(v)}_{o}}^{\star}$. In this case, $\mathbf{D}_{\mathbf{M}}$ is a nonnegative diagonal matrix with each entry representing the singular value of $\mathbf{M}^{(v)}$, both $\mathbf{U}_{\mathbf{M}}$ and $\mathbf{V}_{\mathbf{M}}$ are unitary matrix with orthogonal entries. According to deduction in [23], a closed-form resolution can be found by calculating ${\mathbf{W}^{(v)}_{o}}^{\star}=\mathbf{U}_{\mathbf{M}}sign(\mathbf{D}_{\mathbf{M}})\mathbf{V}_{\mathbf{M}}^{\top}$, where $sign(\cdot)$ is a function imposed on matrix with each element, which returns $1$ if the element is larger than $0$. And it is obvious that in our case, $sign(\mathbf{D}_{\mathbf{M}})$ is an identity matrix. Accordingly, the optimal solution can be calculated as:

By following the updating expression in Eq. (10), our algorithm updates $\mathbf{W}^{(v)}_{i},~{}i=1,2,\cdots,\delta$ in succession.

Likewise, the deduction for the optimization of the anchor selection variable $\mathbf{A}$ is similar to Eq. (9), which can be equally written as:

where $\Phi=\sum_{v=1}^{p}\alpha_{v}^{2}{\mathbf{W}^{(v)}_{\delta}}^{\top}{\mathbf{W}^{(v)}_{\delta-1}}^{\top}\cdots{\mathbf{W}^{(v)}_{1}}^{\top}\mathbf{X}^{(v)}\mathbf{Z}^{\top}$ and $\Phi\in\mathbb{R}^{k\times m}$.

Corresponding to the updating rule in [23], it is straightforward to obtain the optimal solution for $\mathbf{A}$ as in Eq. (9). The multiplication of the left and right singular matrices of $\Phi$ costs $\mathcal{O}(km^{2})$.

According to the definition of Frobenius norm, we can easily derive Eq. (13) as follows:

where $\mathbf{P}=\mathbf{W}^{(v)}_{1}\mathbf{W}^{(v)}_{2}\cdots\mathbf{W}^{(v)}_{\delta}\mathbf{A}$. As the optimisation of the columns in $\mathbf{Z}$ is identical with each other, the optimisation task can be separated into $n$ sub-tasks by the identical form as:

for $j=1,2,\cdots,n$, where the parameter for quadratic term is $\mathbf{Q}=2\sum_{v=1}^{p}{\alpha_{v}^{2}}\mathbf{I}$ and the first order polynomial term ${\boldsymbol{q}^{\top}}=-2\sum_{v=1}^{p}{\alpha_{v}^{2}}{\mathbf{X}^{(v)}_{:,j}}^{\top}\mathbf{P}$. These are several QP(quadratic programming) problems with domain constraints. As each column of $\mathbf{Z}$ is an $m$ dimensional vector, and there are $n$ sub-problems identical to each other, the overall time cost of optimising $\mathbf{Z}$ is $\mathcal{O}(nm^{3})$.

Denote the Frobenius norm of the alignment term $(\mathbf{X}^{(v)}-\mathbf{W}^{(v)}_{1}\mathbf{W}^{(v)}_{2}\cdots\mathbf{W}^{(v)}_{\delta}\mathbf{A}\mathbf{Z})$ as $f^{(v)}$, and the vector $\mathbf{F}=[f^{(1)},f^{(2)},\cdots,f^{(m)}]^{\top}$ refers to the concatenation. By Cauchy-Schwarz inequality, the optimal value of $\boldsymbol{\alpha}$ can be directly acquired by

In our four-step iterative convex optimization process, each updating formula has a closed-form solution and for each iteration, the objective value of the optimization target monotonically decreases while keeping the rest of the decision variables fixed. At the same time, both $\{\mathbf{W}^{(v)}_{i}\}_{i=1}^{\delta}$ and $\mathbf{A}$ are orthogonal matrices, while both $\boldsymbol{\alpha}$ and $\mathbf{Z}$ satisfies $1$-sum non-negative constraints, which provides the lower bound of the optimization target. Consequently, the convex objective monotonically decreases with a lower bound, thus guaranteeing the overall convergence of the proposed method MVSC-HFD.

The optimization procedure demonstrated in Algorithm 1 has decomposed the model into four sub-problems with a closed-form solution. For simplicity and practicality, the hierarchical dimensional reduction processes are conducted identically for different views. Subsequently, their layers’ dimensions $\{l_{i}\}_{i=1}^{\delta}$ are the same. In specific, the optimization of $\mathbf{W}^{(v)}_{o}$ in Eq. (10) involves the calculation of $\mathbf{M}^{(v)}$ and its SVD complexity, which is $\mathcal{O}((\sum_{i=0}^{\delta-2}l_{i}l_{i+1})l_{\delta}+nd_{v}l_{\delta}+2md_{v}l_{\delta})$ and $\mathcal{O}(l_{o-1}k^{2})$, respectively. The multiplication applied to acquire $\mathbf{W}^{(v)}_{o}$ is $\mathcal{O}(l_{o-1}k^{2})$. In all, suppose the dimension $l_{\delta}$ of the last layer is the same as the cluster number $k$ and $\sum_{i=1}^{p}d_{v}=q$, it needs $\mathcal{O}((ql_{1}+p\sum_{i=0}^{\delta-2}l_{i}l_{i+1})k+nqk+2mqk)$ to update $\{\mathbf{W}^{(v)}_{i}\}_{i=1}^{\delta}$ for all views. The optimization of $\mathbf{A}$ requires $\mathcal{O}(k(d_{v}+m)n)$ time cost to gather the multiplicator and $\mathcal{O}(km^{2})$ to decompose it. In sum, the overall complexity of our algorithm is $\mathcal{O}(n)$, which is scalable for large-scale datasets.

For in-depth experimental analysis, we conduct a series of tests over 10 real-world datasets, varying in multiple domains. The datasets used in our experiments are WebKB ¹¹1http://lig-membres.imag.fr/grimal/data.html, BDGP ²²2https://www.fruitfly.org/, MSRCV1 [38], Caltech7-2view ³³3http://www.vision.caltech.edu/Image_Datasets/Caltech101/, NUS-WIDE-10 ⁴⁴4https://lms.comp.nus.edu.sg/wp-content/uploads/2019/research/nuswide/NUS-WIDE.html, Caltech101-7 ³, Caltech101-20 ³, NUS-WIDE ⁴, SUNRGBD ⁵⁵5https://rgbd.cs.princeton.edu/, YoutubeFace ⁶⁶6https://www.cs.tau.ac.il/ wolf/ytfaces/. These datasets vary in broad ranges of application background. In specific, WebKB is a dataset that includes web pages from computer science departments of various universities and they are categorized into 5 categories (Student, Faculty, Department, Course, Project). The SUNRGBD dataset contains 10335 real RGB-D images of room scenes. The MSRCV1 dataset from Microsoft Research in Cambridge contains 7 classes of images with coarse pixel-wise labeling. In Table 2, we summarize the detailed information of these benchmark datasets.

We use the initialization specified in Algorithm 1. In practice, we simply adopt the number of clusters $k$ as the value of the dimension of embedding space and the value of anchor count. For each view, the hierarchical feature descent rate is different according to their original dimensions. However, it is rather practicable as it performs well by directly slicing the dimension to equal sections: $l_{o}-l_{o-1}=l_{o+1}-l_{o},\forall o\in[1,\delta]$. The best depths among $[1,2,\cdots,5]$ of the datasets WebKB, BDGP, MSRCV1, Caltech7-2view, NUS-WIDE-10, Caltech101-7, Caltech101-20, NUS-WIDE ⁴, SUNRGBD, YoutubeFace are 5, 5, 5, 5, 4, 4, 5, 5, 2, respectively.

To be specific, the experiments are conducted in MATLAB environment on PC with Intel(R) Core(TM) i7-6800K 3.40GHz CPU and 128GB RAM.

We list the information of our compared algorithms as in detail as possible by first giving brief introduction to their distinct mechanism, and analyze the hyper-parameters of each method.

• 1.

  Multi-view k-means clustering on big data (RMKM) [5]. This method uses $\ell_{2,1}$ norm to minimize the non-negative matrix factorization form of the cluster indicator matrix in terms of reconstruction of the original data matrix. Its inherent property is similar to the $k$-means clustering method and the $1$-of-$K$ coding scheme provides one-step clustering results.

• 2.

  Large-scale multi-view subspace clustering in linear time (LM-
  VSC) [16]. Under the framework of subspace clustering, this paper intends for clustering of large-scale datasets by using initially selected anchor points to build reconstruction.

• 3.

  Parameter-free auto-weighted multiple graph learning: a fram-ework for multi-view clustering and semi-supervised classification (AMGL) [22]. A fusion of different graph representations where the weights of each graph of view are automatically learned and assumed to be the optimal combination.

• 4.

  Binary Multi-view Clustering (BMVC) [49]. In order to reduce computational complexity and spacial cost, this work proposes to integrate binary representation of all views and consensus binary clustering into a uniform framework by both minimizing these two parts of loss at the same time.

• 5.

  Flexible Multi-View Representation Learning for Subspace Clustering (FMR) [17]. After performing clustering on each different view, the best clustering result is flexibly encoded via adopting complementary information of provided views, thus avoiding the partial outcome in the reconstruction stage.

• 6.

  Multi-view Subspace Clustering (MVSC) [12]. MVSC proposes to learn subspace representation of different views simultaneously while regularising the separate affinity matrices to a common one to improve clustering consistency among different views.

• 7.

  Multi-view clustering: A scalable and parameter-free bipartite graph fusion method (SFMC) [18]. Based on Ky Fan’s Theorem [10], SFMC explores the relationship between Laplacian matrix and graph connectivity, thus proposing a scalable and parameter-free method to interactively fuse the view-specific graphs into a consensus graph with adaptable anchor strategy.

• 8.

  Fast parameter-free multi-view subspace clustering with consensus anchor guidance (FPMVS-CAG) [33]. FPMVS-CAG integrates anchor guidance and bipartite graph construction within an optimization framework and learns collaboratively, promoting clustering quality. The algorithm offers linear time complexity, is hyper-parameter-free, and automatically learns an optimal anchor subspace graph.

• 9.

  Efficient Multi-view K-means Clustering with Multiple Anchor Graphs (EMKMC) [46]. EMKMC integrates anchor graph-based and $k$-means-based approaches, constructing anchor graphs for each view and utilizing an improved $k$-means strategy for integration. This enables high efficiency, particularly for large-scale high-dimensional multi-view data, while maintaining or surpassing clustering effectiveness compared to other methods.

As shown in Table.3, most of algorithm have more than one hyper-parameters. It is encouraged to use learnable parameters which can adaptively collaborate with the optimization of other decision variables to boost the performance whereas spare the acquisition of prior knowledge. In our method, the learnable vector of parameters $\boldsymbol{\alpha}=[\alpha_{1},\alpha_{2},\cdots,\alpha_{p}]^{\top}$ represents the weights adherent to different views, and they are optimized in each iteration. However, for the compared algorithm EMKMC, each view has a hyper-parameter, so the number of parameters is equal to the number of views, which we denote by $p$. As a result, the searching space for best parameter is $\epsilon^{p}$ where $\epsilon$ denotes the size of the candidate set of the hyper-parameter. These unlearnable parameters dramatically increases computation time of EMKMC.

The running time of compared algorithms on benchmark datasets are shown in Figure 4. Due to the excessive time consumed by some of the algorithms, we use the logarithms of the time as the vertical axis of the coordinate.

It is worth noticing that for large-scale datasets, namely NUS-WIDE, SUNRGBD and YoutubeFace, some algorithms(FMR, MVSC, SFMC, RMKM) encounter the ’Out-of-Memory’ problem. As a result, the time bars of these methods are omitted in the comparison graph. We observe that the time cost of EMKMC is comparable to ours, but the total runtime cost is still high owing to the aforementioned search space for the best hyper-parameters.

As described in the previous sections, our proposed algorithm possesses a theoretical guarantee, ensuring its convergence to a local minimum. Furthermore, to provide empirical evidence of its convergence, we conduct experiments on benchmark datasets. Figure 5 illustrates the evolution of the objective value throughout the experimental process. Notably, the experimental results reveal a consistent and monotonically decreasing trend in the objective values of our algorithm at each iteration. Furthermore, we observe that the algorithm achieves rapid convergence, typically within fewer than 10 iterations. These findings undeniably validate the convergence property of our proposed algorithm.

To demonstrate the impact of varying selections for the number of hierarchical dimension projection matrix, we present the performance variation across distinct layers of $\mathbf{W}^{(v)}_{i}$ with respect to each dataset, as depicted in Figure 6.