Deep Multi-view Subspace Clustering with Anchor Graph

1 Introduction

Subspace clustering has been studied extensively over the years, which assumes that the data points are drawn from lowdimensional subspaces, and could be expressed as a linear combination of other data points. Especially, sparse subspace clustering (SSC) [Elhamifar and Vidal, 2013] has shown the ability to find a sparse representation corresponding to the points from the same subspace. After obtaining the representation of the subspace, the spectral clustering is then applied to obtain the final clustering results. On the other hand, low-rank subspace segmentation was proposed in [Liu et al., 2012] to find a low-rank subspace representation. Despite some state-of-the-art performances have been achieved, most existing methods only focus on single-view clustering tasks.

∗ Corresponding author.

In many real-world applications, with the exponential growth of data, the description of data has gradually evolved from a single source to multiple sources. For example, a video consists of text, images, and audio. A piece of text can be translated into various languages, and scenes can also be described from different perspectives. These different views often contain complementary information to each other. Making full use of the complementary and consistent information among multiple views could potentially improve the clustering performance.

Considering the diversity of information that comes with multi-view data, the research of multi-view subspace clustering (MVSC) has attracted increasing attention recently. MVSC aims to seek a unified subspace from learning the fusion representation of multi-view data, and then separates data in the corresponding subspace. In the literature, many MVSC methods have been proposed [Zhang et al., 2015; Luo et al., 2018; Li et al., 2019; Wang et al., 2019; Zheng et al., 2020; Liu et al., 2021; Si et al., 2022]. However, one major weakness of existing approaches is their high time and space complexities, which are often quadratic or cubic in the number of samples n. Recently, a number of anchor-based multiview subspace clustering methods [Chen and Cai, 2011; Sun et al., 2021; Kang et al., 2020; Wang et al., 2022; Liu et al., 2022] have been developed, which can achieve promising performance with a large reduction in storage and computational time. Generally, the anchor graphs are equally weighted and fused into the consensus graph, and then spectral clustering is performed to obtain the clustering result.

On the other hand, inspired by deep neural networks (DNNs), many deep multi-view subspace clustering (DMVSC) methods have been proposed [Peng et al., 2020; Wang et al., 2020; Kheirandishfard et al., 2020; Sun et al., 2019; Zhu et al., 2019; Ji et al., 2017]. However, most DMVSC methods only consider the feature learning ability in networks, their performance is still limited because this learning process is typically independent of the clustering task.

To address the above issues, this paper proposes deep multi-view subspace clustering with anchor graph (DMCAG). DMCAG firstly utilizes deep autoencoders to learn low-dimensional embedded features by optimizing the reconstruction loss for each view independently. For each view, a set of points are chosen by performing k-means on the learned features to construct anchor graphs. Then, we utilize anchor graphs and embedded features as input to get the subspace representation respectively. Once the desired subspace representation is obtained, the clustering result can be calculated by applying the standard spectral clustering algorithm. Unlike the most existing DMVSC methods, the proposed method does not output the clustering result from spectral clustering directly. Instead, we obtain a unified target distribution from this clustering result primarily, which is more robust than that generated by k-means [Xie et al., 2016; Xu et al., 2022], especially for clusters that do not form convex regions or that are not clearly separated. In a selfsupervised manner, the Kullback-Leibler (KL) divergence between the unified target distribution and each view's cluster assignments is optimized. We iteratively refine embedding with pseudo-labels derived from the spectral clustering, which in turn help to obtain complementary information and a more accurate target distribution. Besides, to ensure the consistency among different views and avoid affecting the quality of reconstruction, we adopt contrastive learning on the labels instead of latent features. The main contributions of this paper are summarized as follows:

• We propose a novel deep self-supervised model for MVSC. A unified target distribution is generated via spectral clustering which is more robust and can accurately guide the feature learning process. The target distribution and learned features are updated iteratively.
• To boost the model efficiency, we use anchor graph to construct the graph matrix, avoiding constructing a n × n graph. This strategy can significantly reduce time complexity by sampling anchor points.
• We utilize contrastive learning on pseudo-labels to alleviate the conflict between the consistency objective and the reconstruction objective, thus consistent soft cluster assignments can be obtained among multiple views.
• Extensive experiments on real-world data sets validate the effectiveness and efficiency of the proposed model.

2 RelatedWork

2.1 Deep EmbeddedMulti-ViewClustering

In recent years, the application of deep learning technology in multi-view clustering has been a hot topic. Deep embedded clustering (DEC) [Xie et al., 2016] utilizes the autoencoder to extract the low-dimensional latent representation from raw features and then optimizes the student's t-distribution and target distribution of the feature representation to achieve clustering. In contrast, traditional multi-view clustering algorithms mostly use linear and shallow embedding to learn the latent structure of multi-view data.

However, these methods cannot utilize the nonlinear property of data availably, which is crucial to reveal a complex clustering structure [Ren et al., 2022]. Deep embedded multiview clustering with collaborative training (DEMVC) [Xu et al., 2021a] is a novel framework for multi-view clustering, in which a shared scheme of the auxiliary distribution is used to improve the performance of the clustering. By assuming that clustering structures with high discriminability play a significant role in clustering, self-supervised discriminative feature learning for multi-view clustering (SDMVC) [Xu et al., 2022] leverages the global discriminative information contained in all views' embedded features. During the process, the global information will guide the feature learning process of each view. The autoencoder is usually utilized to capture the most important features present in the data. A suitable autoencoder can obtain more robust representations. Deep embedding clustering based on contractive autoencoder (DECCA) [Diallo et al., 2021] simultaneously disentangles the problem of learned representation by preserving important information from the initial data while pushing the original samples and their augmentations together. With the introduction of the contractive autoencoders, the learned features are better than normal autoencoders. The available information provided by latent graph is often ignored, deep embedded multi-view clustering via jointly learning latent representations and graphs (DMVCJ) [Huang et al., 2022] utilizes the graphs from latent features to promote the performance of deep MVC models. By learning the latent graphs and feature representations jointly, the available information implied in latent graph can improve the clustering performance. The self-supervised manner is widely used in deep clustering, which is valuable to migrate it to other clustering algorithms.

2.2 Multi-View Subspace Clustering

Although many methods exist in subspace clustering, such as low-rank representation subspace clustering (LRR) [Liu et al., 2012], sparse subspace clustering (SSC) [Elhamifar and Vidal, 2013], most of the multi-view subspace clustering methods adopt self-representation to obtain the subspace representation. Low-rank tensor constrained multi-view subspace clustering (LMSC) [Zhang et al., 2017] learns the latent representation based on multi-view features, and generates a common subspace representation rather than that of individual view. Flexible multi-view representation learning for subspace clustering (FMR) [Li et al., 2019] avoids using partial information for data reconstruction and makes the latent representation well adapted to subspace clustering.

Most of existing MVSC methods are challenging to apply in large-scale data sets. Fortunately, inspired by the idea of anchor graph which can help reduce both storage and computational time, a lot of anchor-based MVSC methods have been proposed. Large-scale multi-view subspace clustering (LMVSC) [Kang et al., 2020] can be solved in linear time, which selects a small number of instances to construct anchor graphs for each view, and then integrates all anchor graphs from each views. It thus can perform spectral clustering on a small graph. Efficient one-pass multi-view subspace clustering with consensus anchor (CGMSC) [Liu et al., 2022] unifies fused graph construction and anchor learning into a unified and flexible framework so that they seamlessly contribute mutually and boost performance. Fast multi-view anchor correspondence clustering (FMVACC) [Wang et al., 2022] finds that the selected anchor sets in multi-view data are not aligned, which may lead to inaccurate graph fusion and degrade the clustering performance, so an anchor alignment module is proposed to solve the anchor-unaligned problem (AUP).

With the development of deep neural networks, a number of deep multi-view subspace clustering methods have been proposed. Deep subspace clustering with ℓ1-norm (DSCL1) [Peng et al., 2020] learns nonlinear mapping functions for data to map the original features into another space, and then the affinity matrix is calculated in the new space. Deep multi-view subspace clustering with unified and discriminative learning (DMSC-UDL) [Wang et al., 2020] integrates local and global structure learning simultaneously, which can make full use of all the information of the original multi-view data. Different from the above-mentioned deep multi-view clustering methods, we combine representation learning and spectral clustering into a unified optimization framework, the clustering results can be sufficiently exploited to guide the representation learning for each view.

3 Methodology

Problem Statement. Given multi-view data X = {X v ∈ R dv×n } V v=1 with V views, dv is the dimension of the v-th view, and n is the instance number. The target of MVSC is to divide the given instances into k clusters.

3.1 Motivation

Subspace clustering aims to find out an underlying subspace which expresses each point as a linear combination of other points. The final clustering assignment is obtained by performing spectral clustering on the learned subspace. Basically, it can be mathematically formulated as:

where S v ∈ R n×n is the learned subspace of v-th view, 1 ∈ R n×1 is a vector where all its elements are equal to one, and γ is a trade-off coefficient that controls the sparsity of S v . The constraints on S v ensure that S v is non-negative and � j S i j = 1. When the adjacency graphs are obtained, spectral clustering can be performed on S v to get the clustering result. Existing MVSC methods aim at learning concrete subspace effectively and mining global information of all views to improve the

clustering assignment quality, but still meet some challenges: (1) Most MVSC methods require at least O(n 2 k) time com-

plexity to calculate the clustering result on raw features, which requires more storage and time and is also difficult to deal with large-scale datasets. Additionally, some DMVSC methods such as [Ji et al., 2017; Li et al., 2021] focus on learning subspace by nonlinearly embedding the data. Since the connection between the learned subspace and clustering is weak, the learned features may not be optimal for the clustering task.

(2) From existing self-supervised MVC methods, we can observe that most of them heavily depend on the quality of latent representations to supervise the learning process. [Xu et al., 2022] fuses the embedded features of all views and utilizes k-means [MacQueen, 1967] to obtain the global target distribution. However, k-means does not perform well on some data structure such as non-convex structure compared with spectral clustering [Ng et al., 2001] which is more robust to different distributions. Hence, their obtained pseudo-labels may not reflect clear clustering structure to guide the latent feature learning process.

(3) Some views of an instance might have wrong clustering assignment, leading to the clustering inconsistency. Some deep-learning based MVC methods achieve the consistency by directly learning common information on latent features [Cheng et al., 2021], which may reduce the complementarity of each view's information due to the conflict between learning exact latent representations and achieving consistency.

To address the above-mentioned issues, we propose a novel DMCAG framework as shown in Fig. 1. We use the anchor method to construct the graph matrix on latent features of each view which requires less time and storage. After that, we obtain global pseudo-labels by performing spectral clustering on the integrated anchor graph. Since spectral clustering is more robust to the data distribution, our self-supervised process can learn higher discriminative information from each view. Then, we adopt contrastive learning on pseudo-labels of latent features to maintain the view-private information and achieve the clustering consistency among all views.

3.2 Learning Anchor Graph via Autoencoders

As for much redundancy in the raw data, we utilize the deep autoencoder to extract the latent representations of all views. Through the encoder f v θ v and decoder g v ϕ v , where θ v and ϕ v are learnable parameters, X v is encoded as Z v ∈ R l×n (l is the same for all views) via f v θ v and Z v is decoded as ˆX v via g v ϕ v . The reconstruction loss is defined as:

Inspired by [Kang et al., 2020], we adopt the anchor graph to replace the full adjacency matrix S , which is formulated as:

where A v ∈ R l×m (m is the anchor number) is a set of clustering centroids through k-means on the embedded features Z v , and C v ∈ R n×m is the anchor graph matrix reflecting relationship between Z v and A v . The problem above can be solved by convex quadratic programming. We refer the readers to [Wolfe, 1959] for more details about quadratic programming.

3.3 Spectral Self-Supervised Learning

As stated in [Ng et al., 2001], for clusters that are not clearly separated or do not form convex regions, the spectral method can also reliably find clustering assignment. Hence, we use spectral clustering to obtain more robust global target distribution to guide the self-training. Spectral clustering [Ng et al., 2001] can be mathematically described as finding Q ∈ R n×k by maximizing:

Following Theorem 1 introduced by [Chen and Cai, 2011; Kang et al., 2020], we present an approach to approximate the singular vectors of S in latent space.

Theorem 1. [Chen and Cai, 2011; Kang et al., 2020] Given a similarity matrix S , which can be decomposed as (C T )C. Define singular value decomposition (SVD) of C as U∧V T , then we have

And the optimal solution Q ∗ is equal to U.

Proof. From Eq. (5), one can observe that the optimal H ∗ = C T Q. Substituting H ∗ = C T Q into Eq. (5), the following equivalences hold

Furthermore, one can obtain

Therefore, we could use left singular vectors of C to approximate the eigenvectors of S . □

According to Theorem 1, we calculate eigenvectors {U v } V v=1 of {C v } V v=1 to approximate the eigenvectors of full similarity matrix. To fully exploit the complementary information across all views, we concatenate all eigenvectors U = {U 1 , U 2 , . . . ,U V } ∈ R n×(Vk) to generate the global feature via the spectral method. After obtaining the global feature U, we apply k-means to calculate the cluster centroids {µj} k j=1 :

Similiar to DEC [Xie et al., 2016], which is a popular singleview deep clustering method utilizing Student's t-distribution [Van der Maaten and Hinton, 2008], the soft clustering assignment ti j between global feature U and each cluster centroid µj could be computed as:

To increase the discriminability of the global soft assignments, the target distribution P is formulated as:

We obtain soft clustering assignment (pseudo-label) Q v = � q v 1 , q v 2 , . . . , q v N � of each view, where q v i j can be considered as the probability of the i-th instance belonging to the j-th cluster in the v-th view. It is defined as:

where µ v j denotes the j-th cluster centroid of the v-th view.

Overall, we use Kullback-Leibler divergence between the unified target distribution P and view-private soft assignment distribution Q v to guide autoencoders to optimize latent features containing higher discriminative information, which can be formulated as:

As the target distribution obtained from spectral clustering is adaptive to different data distributions, we can get more explicit cluster structures to guide the self-training process compared with k-means clustering. To extract embedded features that reflect correct information of raw features and learn an accurate assignment for clustering, we jointly optimize the reconstruction of autoencoders and self-supervised learning. The total loss function Ls is defined as:

3.4 Label Consistency Learning

To guarantee the same soft assignment distribution of all views represent the same cluster, we need to achieve the consistency of pseudo-labels. We adopt contrastive learning to the soft assignment obtained from Eq. (9). For the m-th view, Q m (:, j) have (Vk - 1) pairs, where the (V - 1) pairs {Q m (:, j), Q n (:, j)}m�n are positive and the rest V(k - 1) pairs are negative. Thereby the contrastive loss can be defined as:

where d(·, ·) represents the cosine distance to meausure the similiarty between two labels, τ is the temperature parameter. Moreover, to avoid the samples being assigned into a single cluster, we use the cross entropy as a regularization term. Generally, the label consistency learning is formulated as:

Algorithm 1 Deep Multi-View Subspace Clustering with Anchor Graph (DMCAG)

Input: multi-view dataset X, cluster number k.

Initialization: Get {θ v , ϕ v , µ v , A v } V v=1 by pretraining autoencoders and k-means. Initialize {C v } V v=1 via quadratic programming.

Update {θ v , ϕ v Q v } V v=1 by performing self-supervised learning via Eq. (11).

Performing contrastive learning on {Q v } V v=1 via Eq. (13). Obtain {C v } V

Output: Cluster assignment y via Eq. (6).

v=1 via Eq. (3).

where s m j = 1 N � N i=1 q m i j . After finetuning the labels via contrastive learning, the similarities of positive pairs are enhanced and thereby the obtained latent features have clearer clustering structure. At last, the clustering prediction y is obtained through the target distribution P calculated by performing k-means on U.

3.5 Optimization

The detailed optimization procedure is summarized in Algorithm 1. We adopt the Adam method to train the autoencoders. At the beginning, autoencoders are initialized by Eq. (2). After that, we solve Eq. (3) via convex quadratic programming to obtain U and calculate the global target distribution P. Then, the spectral self-supervised learning is adopted to learn more representive embeddings. After performing the self-supervised learning, the contrastive learning is conducted to achieve the clustering consistency. At last, we run k-means on U to obtain the final clustering result y:

4 Experiments

4.1 Experimental Settings

Datasets. As shown in Table 1, our experiments are carried out on six datasets. Specifically, MNIST-USPS [Peng et al., 2019] collects from two handwritten digital image datasets, which are treated as two views. Multi-COIL-10 [Xu et al., 2021b] collects 720 grayscale object images with size of 32 × 32 from 10 clusters, where the different views represent various poses of objects. BDGP [Cai et al., 2012] UCI-digits 1 is a collection of 2000 samples with 3 views, which has 10 categories. Fashion-MV [Xiao et al., 2017] contains images from 10 categories, where we treat three different styles of one object as three views. Handwritten Numerals (HW) 2 contains 2000 samples from 10 categories corresponding to numerals 0-9. Each sample has six visual views.

1 https://archive.ics.uci.edu/ml/datasets/Multiple%2BFeatures

ComparisonMethods. Comparsionmethods include 3 traditional single-view clustering methods, i.e., k-means [MacQueen, 1967], SC (Spectral clustering [Ng et al., 2001]), and DEC (Deep embedded clustering [Xie et al., 2016]), and 6 state-of-art MVC methods, i.e., CSMSC (Consistent and specific multi-view subspace clustering[Luo et al., 2018]), FMR (Flexible multi-view representation learning for subspace clustering), SAMVC (Self-paced and auto-weighted multiview clustering [Ren et al., 2020]), LMVSC (Large-scale multi-view subspace clustering in linear time [Kang et al., 2020]), CGMSC (Multi-view subspace clustering with adaptive locally consistent graph regularization [Liu et al., 2021]), and FMVACC (Fast multi-view anchor-correspondence clustering [Wang et al., 2022]).

EvaluationMetrics. We evaluate the effectiveness of clustering by three commonly used metrics, i.e., clustering accuracy (ACC), normalized mutual information (NMI), and adjusted rand index (ARI). A higher value of each evaluation metric indicates a better clustering performance.

2 https://archive.ics.uci.edu/ml/datasets.php

Implementation. The convolutional (Conv) and fully connected (Fc) neural networks are applied according to different types of data. For the image datasets, i.e., MNIST-USPS and Multi-COIL-10, we use the convolutional autoencoder (CAE) for each view to learn embedded features. The encoder is Input-Conv 32 4 -Conv 64 4 -Conv 64 4 -Fc10. Since all views of BDGP, UCI-digits, Fashion-MV, and HW are vector data, we utilize fully connected autoencoder. For each view, the encoder is Input-Fc500-Fc500-Fc2000-Fc10. All the decoders are symmetric with the corresponding encoders. Following [Kang et al., 2020], we select anchor numbers in the range [10, 100]. We select γ from {0.1, 1, 10}. Temperature parameter τ is set to 1 and α is set to 0.001 for all experiments. All experiments are performed on Windows PC with Intel (R) Core (TM) i5-12600K CPU@3.69 GHz, 32.0 GB RAM, and GeForce RTX 3070ti GPU (8 GB caches). For fair comparison, all baselines are tuned to the best performance according to the corresponding papers.

clustering result.

Parameter SensitivityAnalysis. Asmain hyperparameters of the proposed method are anchor number and sparsity coefficient, we test the general clustering performance with different settings to show the stability of DMCAG. From Fig. 2 we can observe that our method in a certain range of parameters is insensitive to the clustering results. In addition, we can find that too many anchors will reduce clustering performance as the anchors' information may not be representative. A too large or too small γ also reduces the final clustering performence, of which the reason is that the inappropriate sparsity constraint could lead to extra errors.

Visualization of Clustering Results. We visualize the clustering results on four datasets via t-SNE [Van der Maaten and Hinton, 2008], which reduces the dimension of the extracted feature vectors to 2D. As shown in Fig. 3, where different colors denote the labels of different nodes, we can find that the final clustering structures are clearly visible, especially for Multi-COIL-10 and MNIST-USPS, which further demonstrates the effectiveness of our DMCAG method.

5 Conclusion

In this paper, we propose a novel DMCAG framework for deep multi-view subspace clustering. By introducing the latent anchor graph and spectral self-supervised learning, we can effectively perform spectral clustering to obtain more robust global target distribution and significantly improve the latent features structure for clustering. In addition, we adopt the contrastive learning on the soft assignment of each view to achieve the consistency among all views.

4.2 Results and Analysis

Comparison with Baselines. The comparison of DMCAG and baseline methods is shown in Table 2, where the best result is bolded in each row and the second-best result is underlined. Due to the high complexity, the result of FMR is not obtained on Fasion-MV dataset after running 24 hours. From Table 2, we can observe that the proposed method achieves the best performance among all baseline models on six datasets, illustrating the validity of our method. Especially for Multi-COIL-10 and Fasion-MV, our method makes greater improvement than existing methods. The main reason is that we conduct clearer self-supervised learning with latent anchor graphs and achieve clustering consistency via contrastive learning on pseudo-labels. Besides, many subspace clustering methods do not perform well on BDGP dataset due to the high dimension of one view's feature, however, our method outperforms due to the ability of extracting features from high-dimension data.

Ablation Studies. To verify the effectiveness of the proposed method, we further conduct a set of ablation studies on the loss components from Eqs. (10) and (13). Lr is the reconstruction loss of autoencoders. Ls aims to mine global information and supervise the learning process with global target distribution. LQ is optimized to achieve the consistency among all views. In the Table 3, (A) is optimized without self-supervised learning and contrastive learning, (B) is optimized without contrastive learning, and (C) is optimized without self-supervised process. As shown in Table 3, we can find that (B) and (C) perform better than (A). (D) (our proposed model with all loss components) performs the best, illustrating that each loss component is important for the final

Acknowledgments

This work was supported in part by Sichuan Science and Technology Program (Nos. 2022YFS0047 and 2022YFS0055), Medico-Engineering Cooperation Funds from the University of Electronic Science and Technology of China (No. ZYGX2021YGLH022), National Science Foundation (No. MRI 2215789), and Lehigh's grants (Nos. S00010293 and 001250).