Clustering-Induced Adaptive Structure Enhancing Network for Incomplete Multi-View Data

1 Introduction

Describing objects from different aspects constitutes multiview data. For instance, an image can be described by different features such as color, texture, surrounding texts or deep features. The content of a web page can be described by text, images, and videos, etc. Each view contains some specific information that other views do not have. Therefore, leveraging multiple views can obtain multi-view complementary information and generate more complete descriptions of data. Multi-view clustering aims to exploit diverse and complementary features of different views to improve clustering performance, and many methods have been developed in the past few years [Kang et al., 2020; Zhang et al., 2020b; Li et al., 2020; Kang et al., 2021].

∗Corresponding Author

In real-world applications, it is often the case that each view suffers from loss of information due to data collection equipment failures or environmental changes [Li et al., 2014; Zhang et al., 2020a]. For instance, different types of tests may be conducted for different medical applications, which leads to the loss of some views. However, conventional multiview clustering methods assume that all views are available for each sample so that they cannot well handle the incomplete multi-view data. It is more challenging and meaningful to endow the method with adaptive capability and high effectiveness for view-missing situations.

To discover clusters from incomplete multi-view data, a variety of incomplete multi-view clustering (IMC) methods have been developed [Peng et al., 2019; Yang et al., 2021; Huang et al., 2020]. Some methods adopt matrix factorization model to extract a consensus matrix from incomplete multi-view data. PVC [Li et al., 2014] establishes a latent subspace where the instances corresponding to the same sample in different views are close to each other. Several methods further extend PVC method. IMG [Zhao et al., 2016] adopts a graph Laplacian term to couple the incomplete multi-view samples. MIC [Shao et al., 2015] integrates weighted nonnegative matrix factorization and l2,1 regularization to handle the incomplete multi-view data. Moreover, some methods adopt multiple graph learning or multiple kernel learning for IMC [Wen et al., 2019; Zhou et al., 2019]. OPIMC [Hu and Chen, 2019b] directly obtains clustering results for large-scale multi-view data through a regularized matrix factorization model. PIC [Wang et al., 2019] adopts spectral perturbation theory and learns a consensus Laplacian matrix from incomplete multi-view data for clustering. MKKMIK [Liu et al., 2019] integrates kernel imputation and clustering into a unified learning procedure, where incomplete kernels can be adaptively imputed and combined for clustering.

In addition to the shallow models mentioned above, some deep learning based methods are proposed for IMC [Wang et al., 2018; Wen et al., 2020b]. AIMC [Xu et al., 2019] learns the consensus latent space and performs missing data inference simultaneously, where a generative adversarial network is used to infer missing data. CDIMC-net [Wen et al., 2020a] incorporates view-specific deep encoders and graph embedding into a framework to capture the local structure of each view, and a self-paced strategy is adopted to train the deep model. Deep learning based IMC methods can well handle the discrepancy and dependence among multiple views, so they achieve better clustering performance and wider application prospects than the shallow models.

Despite significant progress has been made in the field of incomplete multi-view clustering, there are still some issues that have not been well solved. First, it is difficult to obtain the complete data structure when some views are missing. Most of the existing IMC methods fail to complete the missing features to extract the intrinsic data structure. Second, both global and local structures are essential for IMC, yet most of the existing methods fail to simultaneously use them so that the data structure information cannot be comprehensively exploited. Third, the reliability and accuracy of views are different, so they should have different importance during the clustering process. However, the existing deep learning based IMC methods ignore this factor and their clustering performance are limited.

In order to solve the above issues, we propose a novel incomplete multi-view clustering method, i.e., Clusteringinduced Adaptive Structure Enhancing Network (CASEN). We develop an end-to-end trainable framework for joint multi-view structure enhancing and data clustering. CASEN is composed of a multi-view autoencoder module, an adaptive multi-view graph structure extraction module and a clustering-induced structure enhancing module. We introduce multi-view autoencoder to extract the global structure of multi-view data as well as infer the missing features of incomplete samples. Then, we leverage adaptive graph learning and graph convolution networks (GCNs) to extract and encode the local structure of data. Our method can accurately extract local structure of data by learning suitable graph representation that best serves the clustering task. To obtain robust and reliable clustering results, we adopt multiple kernel clustering to assign different weights to views and integrate both global and local structures. The clustering results are used to supervise the network training through the self-supervision strategy so that the learned data structures can be further enhanced. We conduct comprehensive experiments on several benchmark datasets to study the properties of the proposed method. Experimental results show that CASEN consistently outperforms the state-of-the-art IMC methods, which demonstrates the advantages of our method. The main contributions of this work are summarized as follows:

• We develop a novel deep learning framework to simultaneously reconstruct the missing views and learn data structure from the reconstructed complete multi-view data. Our method can explore and extract comprehensive data structure from incomplete multi-view data to reduce the impact of missing views on structure learning.
• We exploit both global and local structures to reveal the complex relationship and intrinsic distribution of multiview data. The global and local structure information can be effectively preserved and encoded into the latent representation of the network, which can yield better clustering performance.
• We introduce multiple kernel clustering to obtain more reliable clustering results, which is achieved by assigning different weights to views according to their importance. The multiple kernel clustering and structure learning can promote each other during network training, so the learned structures can be further enhanced.

2 Methodology

CASEN is an end-to-end multi-view clustering network which is composed of three modules as shown in Figure 1. Multi-view autoencoder module and adaptive multi-view graph structure extraction module learn the global and local structure, respectively. Clustering-induced structure enhancing module utilizes multiple kernel clustering to obtain clustering results and supervises the training of the network. We introduce the details of CASEN in the following parts.

2.1 ProblemDefinition

Incomplete multi-view data with V views and n samples can be denoted by a set of matrices {X(v) }Vv=1 , where X(v) = [x(v) 1 , x(v) 2 , ..., x(v) n ]T ∈ Rn∗mv , mv is the feature dimensions of the v-th view. If the i-th sample xi = {x(1) i , x(2) i , ..., x(V ) i } loses the features of the j-th view, then x(j) i is filled by zeros. Assume that each sample would not lose the features of all the views. Our objective is to cluster n unlabeled multi-view data samples into c categories.

2.2 Multi-ViewAutoencoder Module

Different views have different physical meanings and they are not directly comparable. Therefore, we introduce multi-view autoencoder to obtain the common latent representation of multi-view data. By training multi-view autoencoder to encode and decode data, the latent representation can well explore the global structure of multi-view data and fully preserve multi-view complementary information. Additionally, multi-view autoencoder can be used to infer missing views of incomplete samples by the reconstruction process, which enables the model to learn the complete graph representation of multi-view data.

Multi-view autoencoder consists of several view-specific encoders {f (v) }Vv=1 and corresponding decoders {g(v) }Vv=1 . To obtain the common representation of multi-view data, we make the encoders of each view {f (v) }Vv=1 share the same top hidden layer so that they have the same output. When the sample xi is input into encoders, hi is the output of the encoders which provides the common representation of xi. The decoders of each view take hi to reconstruct original data. The reconstruction process of decoders is ̂ x(v) i = g(v) (hi), ∀v = 1, ..., V . Noted that decoders can generate the features of all the views, thus the missing views of incomplete samples can be infered. The reconstructed data is denoted by ̂X(v) = [̂ x(v) 1 , ̂ x(v) 2 , ..., ̂ x(v) n ]T ∈ Rn∗mv . The loss function of multi-view autoencoder is defined as:

where P (v) ∈ Rn∗n is a diagonal matrix which records the view missing information. P (v) ii = 1 if the i-th sample is available in the v-th view, otherwise, P (v) ii = 0. By training the multi-view autoencoder to reconstruct data, the learned latent representation H = [h1, h2, ..., hn]T ∈ Rn∗kh can capture the global structure of multi-view data and provide effective representation for data clustering.

2.3 Adaptive Multi-ViewGraph Structure Extraction Module

Although the multi-view autoencoder module is able to capture the global structure of multi-view data, it ignores the local relationship of samples. In the adaptive multi-view graph structure extraction module, we introduce adaptive graph structure learning to learn graph representation of multi-view data, and leverage GCNs to further extract and explore the local structure information of multi-view data.

Given the reconstructed multi-view data { ̂X(v) }Vv=1 , we aim to learn a graph with affinity matrix S(v) ∈ Rn∗n for each view to represent the pairwise relationship between samples. Inspired by [Jiang et al., 2019], we implement adaptive graph learning via v single-layer neural networks, which are parameterized by the weight vector a(v) ∈ Rmv∗1 . Let S(v) ij represent the similarity between xi and xj for the v-th view which is learned by

where σ is the activation function. Softmax operation on each row of S(v) can guarantee the learned graph satisfying the following property∑n

To ensure the graph can well capture the local structure of multi-view data, we adopt the following loss function to learn S(v) and the weight vectors {a(v) }Vv=1 ,

where λ is the tradeoff parameter to control the sparsity of learned graph S(v) . By adjusting the sparsity of S(v) , we can establish the neighborhood relationship and local structure of multi-view data adaptively.

Next, we introduce GCN to further extract the local structure of multi-view data and encode them into the latent representation. For the v-th view, Z (v) l is the representation learned by the l-th layer of GCN, which can be obtained by the following operation,

where l ∈ {1, ..., L}, D(v) is a diagonal matrix with diagonal element D(v) ii = ∑nj=1 S(v) ij , W (v) l-1 is the weight matrix of the convolution layer, σ is the activation function. We set the reconstructed multi-view feature as the initial node feature of GCN, i.e., Z (v) 0 = ̂X(v) . The last layer of GCN Z (v) L is denoted by Z (v) ∈ Rn∗kc for simplicity. GCN is able to encode both the local structure and node features. Therefore, the local structure of multi-view data can be effectively encoded into the learned representation {Z (v) }Vv=1 .

2.4 Clustering-Induced Structure Enhancing Module

Now, we present the clustering-induced structure enhancing module to achieve multi-view clustering. Considering the reliability of views are different, we adopt multiple kernel clustering (MKC) [Tzortzis and Likas, 2012] which assigns different weights to views so that more accurate clustering results can be obtained. Then, the clustering results are used to enhance the learned structures through a self-supervision strategy. Our method jointly implements multiple kernel clustering and structure enhancing so that they can promote each other and the clustering performance can be further improved.

In multiple kernel clustering, K(·, ·) is the kernel function. The kernel matrix for each view is constructed by K(v) = K(Z (v) ,Z (v) ), and another kernel is constructed to capture the global structure by K(V+1) = K(H,H). The unified kernel is defined by Ku = ∑V+1 v=1 β(v) rK(v) , where β = [β(1) , β(2) , ..., β (V ) ] is the weight parameter of kernels and r controls the sparsity of β. The objective of MKC is presented as follows,min

where Q ∈ Rn∗c is the embedding matrix to be learned. The detailed algorithm for solving (6) is shown in Algorithm 2. By performing k-means clustering on Q, we can obtain the clustering results qi ∈ {0, 1}c for each sample xi.

We adopt self-supervision strategy to utilize the clustering results to guide the network training. The output of multi-view autoencoder and GCNs are concatenated by R = [H||Z (1) ||Z (2) ||...||Z (V ) ], and then we put R into FC layers. The output of FC layers is denoted by {yi ∈ Rc }ni=1 . We use self-supervision strategy to train the whole network by integrating cross-entropy loss and center loss [Wen et al., 2016] as follows:

where yi is a normalization of yi via softmax. ri is the i-th row of R, which represents the concatenated representation of the i-th sample. φi takes the cluster index of qi, and ρφi is the cluster center which corresponds to the i-th sample. θ is the tradeoff parameter. The clustering result qi provides the pseudo labels for network training. Noted that the label index assigned to a cluster undergoes an unknown permutation during clustering. Hence, the class labels from two successive clusterings may be inconsistent. To address this issue, Hungarian algorithm [Munkres, 1957] is adopted to find an optimal assignment between the pseudo labels of successive iterations and then feed them into loss function (7).

2.5 Overall Loss Function

The overall loss function of CASEN is proposed by integrating multi-view autoencoder module, adaptive multi-view graph structure extraction module and clustering-induced structure enhancing module. By putting together the loss functions in (1), (4), and (7), the end-to-end trainable framework is formulated as follows,

where η1 and η2 are tradeoff parameters to control the importance of each component. By optimizing (8), our network is capable of jointly enhancing multi-view data structure and achieve effective clustering results.

Algorithm 1: The learning procedure of CASEN.

Input: Input data {X(v) }Vv=1, tradeoff parameters, network parameters, Tmax, T1, iter=1.

Output: The trained network and clustering results {qi}ni=1.

• 1 Pre-train the multi-view autoencoder and initialize all the parameters of the network.
• 2 PerformMKC to get initial clustering results.
• 3 while iter ≤ Tmax do
• 4 Given the clustering results, update the network T1 epoches by optimizing the overall loss function (8). 5 Perform MKC to update clustering results by Algorithm 2. 6 iter ← iter + 1. 7 end

Algorithm 2: The learning procedure of MKC.

Input: {K(v) }V+1 v=1 , r, c. Output: Clustering results {qi}ni=1. 1 Initialize β(v) = 1/(V +1). 2 while not converged do 3 Update Ku = ∑V+1 v=1 β(v)rK(v) . 4 Update Q by c largest eigenvectors of Ku. 5 Update d(v) = Tr(K(v) (I -QQT )), v ∈ {1, ..., V +1}. 6 Update β(v)=1/∑V+1 v′=1 ( d(v) d(v′) ) 1 r-1 , v ∈ {1, ..., V + 1}. 7 end

• 8 Obtain clustering results {qi}ni=1 by performing k-means on Q.

2.6 Implementation

Pre-training the network. Before training the whole network, we pre-train multi-view autoencoder by using loss function (1). All features of the missing views are filled with zero. Stochastic gradient descent (SGD) is adopted to pretrain the multi-view autoencoders.

MKC model learning. For multiple kernel clustering, linear kernel is adopted as the kernel function for its simplicity and effectiveness. An iterative algorithm that alternates between updating the embedding matrix Q and updating the kernel weights β is adopted. The updating rules for Q and β can be derived by Lagrange multiplier method. The detailed learning process of MKC is shown in Algorithm 2.

Training the whole network. After pre-training the network, we use the overall loss function (8) to train the whole network. Specifically, given the clustering result, we update the other parameters in the network for T1 epoches. Then, we perform multiple kernel clustering to update the clustering result. The two steps are performed alternately until the network is well trained. The initial clustering result is achieved by performing MKC on H, which is obtained from the pre-trained multi-view autoencoder. We present the detailed training procedure of CASEN in Algorithm 1.

3 Experiments

3.1 Experimental Settings

Datasets. We adopt four well-known multi-view learning datasets to demonstrate the effectiveness of the proposed method. 1) BBC: It consists of 685 documents from BBC news website which corresponds to stories about five topical areas. Each sample is described by four views [Greene and Cunningham, 2006]. 2) Caltech20: It is a subset of Caltech101 dataset, which consists of 2386 images of 20 classes. To obtain multiple views, we manually extract six kinds of visual features as in [Cai et al., 2013]. 3) Wikipedia: It contains 2866 multimedia documents which are collected from Wikipedia [Rasiwasia et al., 2010]. Each document contains two views i.e., the image view and the text view. 4) MNIST: It is composed of 10000 samples of ten digits. Pixel feature and edge feature are adopted as two views [LeCun et al., 1998]. To construct the incomplete multi-view data, for data with more than two views, we randomly remove p% instances from each view while guarantee that each sample at least have one view. Wikipedia and MNIST datasets have only two views, we randomly choose 1 - p% samples and keep their views complete, and the remaining samples are treated as single view samples. Half of the single view samples have the first view and the others have the second view.

Baseline methods. The compared methods include several representative IMC methods. BestSV: We reports the best clustering results achieved by performing k-means on each view. MIC [Shao et al., 2015]: It learns the latent feature matrices for all the views and generates a consensus matrix so that the difference between each view is minimized. OMVC [Shao et al., 2016]: It learns the latent feature matrices for all the views by pushing them towards a consensus. IMG [Zhao et al., 2016]: It imposes the orthogonal constraint on the basis matrix of each view to handle the outof-sample problem. DAIMC [Hu and Chen, 2019a]: It is based on weighted semi-nonnegative matrix factorization to obtain cluster results. UEAF [Wen et al., 2019]: A localitypreserved reconstruction term is introduced to infer the missing views so that all views can be aligned. OPIMC [Hu and Chen, 2019b]: It adopts regularized and weighted matrix factorization to obtain clustering results. PIC [Wang et al., 2019]: It learns a consensus Laplacian matrix from incomplete multi-view data for clustering. We adopt two widely used evaluation metrics: Clustering accuracy (ACC) and normalized mutual information (NMI) to validate the clustering performance.

Parameter settings. The autoencoders f (v) and g(v) are stacked by four layers and the dimensions are with [0.8mv, 0.8mv, 1200, 50] and [50, 0.8mv, 0.8mv,mv], respectively. We adopt two convolution layers in GCN and the dimensions are [0.8mv, 50]. The FC layers in LC are designed with four layers [l, d1, d2, d3], l is the dimension of the input layer, d1 and d2 are the dimensions of hidden layers, d3 is the dimension of output layer. We set d1 = n, d2 = 0.8n, d3 = c. The other parameters are set as η1 = 0.1, η2 = 0.01, λ = 0.5, θ = 0.1, r = 2. Rectified Linear Unit (ReLU) is adopted as the activation function of our network. We run all the methods 10 times and report the average performance. CASEN is implemented in PyTorch and executed on an Ubuntu 18.04 machine with Nvidia GeForce RTX 2080 Ti GPU.

3.2 Performance Comparison

All the methods are conducted on four benchmark datasets with different missing rates p ∈ {10%, 30%, 50%, 70%} and the results are shown in Table 1. The experimental results illustrate that our method CASEN consistently achieves better performance than the baseline methods on each dataset. Specifically, for missing rate p = 0.3, compared to the second best method, CASEN improves ACC by 2.37%, 6.39%, 2.77%, 8.08% on BBC, Caltech20, Wikipedia and MNIST datasets, respectively, which demonstrates the effectiveness of CASEN. We would like to highlight several aspects of the experimental results: 1) Multi-view clustering methods generally obtain better performance than BSV, which indicates that different views can complement each other and leveraging multi-view complementary information is beneficial to improve clustering performance. 2) MIC, OMVC and DAIMC are based on matrix factorization. However, their clustering performance are limited because the local structure information is ignored and the learned latent representation cannot well capture data correlations. 3) UEAF and PIC leverage local structure for multi-view clustering, while they neglect to use global structures so they cannot obtain effective clustering results. 4) The proposed method CASEN performs better than the other methods by utilizing both local and global structure to capture comprehensive data correlations. Moreover, multi-view clustering and network training are jointly conducted so that the two tasks can promote each other to achieve better clustering performance.

3.3 Component and Parameter Analysis

We study the effectiveness of each module of CASEN on Caltech20 and Wikipedia datasets. Three baseline methods are introduced: 1) CASEN-AE: Remove adaptive multi-view graph structure extraction module from CASEN, where only global structure is leveraged in the model. 2) CASEN-GCN: Remove multi-view autoencoder module from CASEN, where only local structure is used. 3) CASEN-KM: Perform k-means clustering on R to obtain clustering results instead of using multiple kernel clustering. From Figure 2 we can observe that by jointly exploiting global and local structure and conducting multi-view clustering through MKC, CASEN outperforms the other three degradation models, which verifies the effectiveness of each module.

The sensitivity analysis experiments are conducted on Caltech20 and Wikipedia datasets for p = 0.3 in Figure 3, where the two important parameters η1 and η2 in (8) are studied. We search η1 and η2 in [10-4 , 101 ] and present how the clustering performance changes. It can be observed that the performance of our method is relatively stable with the two parameters. Promising performance can be obtained in a wide range for η1 ∈ [10-3 , 10-1 ] and η2 ∈ [10-3 , 100 ].

4 Conclusion

We propose an end-to-end trainable network CASEN for joint adaptive structure enhancing and incomplete multi-view clustering. Unlike the existing incomplete multi-view clustering methods that only use the incomplete multi-view structure information, CASEN further improves clustering performance by completing the missing features and integrating both global and local structures of multi-view data. Multiple kernel clustering is introduced to obtain reliable and accurate clustering results, and the clustering results in turn are used to guide network training through a self-supervision strategy. Extensive experiments conducted on several benchmark datasets demonstrate the effectiveness and reasonableness of CASEN and its advantages over the other methods.

Acknowledgments

This work was supported by National Key R&D Program of China (2018YFB1402600), and by the National Natural Science Foundation of China (61802028, 61772083, 61877006, 62002027), and sponsored by CCF-Baidu Open Fund, and by Beijing Nova Program (No. Z201100006820074).