Incomplete Multi-view Clustering via Prototype-based Imputation

1 Introduction

Clustering is a fundamental tool in data analysis [Van Gansbeke et al., 2020; Li et al., 2021; Li et al., 2022], which aims at partitioning instances into different clusters without the help of data annotations. To handle multi-view data, many efforts have been devoted to developing multi-view clustering (MvC) methods [Tao et al., 2017; Hu et al., 2019; Huang et al., 2019; Yang et al., 2021a; Yang et al., 2021b]. Almost all of MvC works implicitly or explicitly take the data completeness assumption, i.e., all instances exist in all views. In practice, however, the assumption is always violated due to the complexity of data collection and transmission, leading to the incomplete problem in multi-view data. For example, when building medical history for patients, the multi-view healthcare data is susceptible to be incomplete due to disease concealment in the data collection or information loss during treatment transfer.

To achieve incomplete multi-view clustering (IMvC), a feasible solution is employing the observed cross-view samples to recover the missing counterparts and then performing clustering. As shown in Fig 1(a), one of the most straightforward paradigms is using observed samples to find cross-view neighbors which are further used to recover missing samples. Such a paradigm implicitly assumes that the views could be mapped into a common space wherein the neighbors of the missing sample could be accurately identified by its crossview counterpart. In practice, however, such an assumption is satisfied always at the cost of the view versatility since the view-specific information is often excluded to learn the common space. To compensate for view versatility, some studies propose capturing the view-specific information using a cross-view predictor [Lin et al., 2021] or generator [Wang et al., 2018]. Unfortunately, such a generative paradigm essentially learns an equivalent mapping for the whole dataset across views, which will lose the instance commonality, i.e., within-cluster compactness and between-cluster scatterness.

Different from the aforementioned sample-based imputation methods, we propose a prototype-based imputation paradigm as shown in Fig. 1(b). Unlike existing methods that restore the missing sample through learning a common representation for cross-view samples, we propose performing data recovery using the prototypes from the missing view and the sample-prototype relationship from the observed view. Thanks to our paradigm, the instance commonality and the view versatility can be preserved because the prototypes capture the cluster- and view-specific information. Furthermore, our invariance assumption on the sample-prototype relationship is milder than that on the cross-view representation taken in these works.

To implement the prototype-based imputation, ones have to overcome the following two technical challenges, i.e., i) incorporating prototypes and samples to enhance the instance commonality, and ii) learning view-specific prototypes to preserve view versatility. To this end, we propose an incomplete multi-view clustering method based on a novel dual-stream model consisting of a dual attention layer and a dual contrastive learning loss. To be specific, the dual attention layer aims to enhance the instance commonality by representing samples and prototypes with each other. More specifically, the sample representation is learned by aggregating the sample itself and the corresponding prototype, thus enhancing the commonality of with-cluster instances. In a dual manner, the prototype representation is learned through aggregating prototype itself and the current input samples, thus integrating the historical and current information. The dual contrastive learning loss is designed to preserve view versatility, which consists of the standard contrastive learning on samples and a new bounded contrastive loss on the prototypes. Thanks to the bounded contrastive loss, the prototypes will embrace the unique view-specific information, thus preserving the view versatility. The major contributions of this paper could be summarized as follows:

1. From the standpoint of data recovery for IMvC, we proposed a novel imputation method which restores the missing samples using the prototypes and the sampleprototype relationship. Such a prototype-based imputation paradigm could preserve instance commonality and view versatility that are favorites to IMvC.
2. From the standpoint of unsupervised multi-view representation learning, we propose a novel dual-stream model which learns sample representation using prototypes and prototype representation using the input samples. Thanks to the dual-stream model, our method could learn better representation for boosting IMvC performance.
3. Extensive experiments on five benchmarks demonstrate the superiority of our method in both incomplete multiview clustering and data recovery performance, compared with 11 baselines.

2 RelatedWork

In this section, we briefly review two related topics, namely, incomplete multi-view clustering and attention-based model.

2.1 Incomplete Multi-ViewClustering

IMvC is a long-standing task in the multi-view learning community, which has attracted numerous studies. Based on the way to utilize the cross-view information, classic IMvC methods could be divided into three categories, including matrix factorization based [Li et al., 2014; Zhao et al., 2016; Shao et al., 2015; Hu and Chen, 2019], kernel learning based [Bach and Jordan, 2002; Liu et al., 2020], and similarity relation based [Wang et al., 2019; Liu et al., 2019]. To handle more complex and large-scale data, several deep IMvC methods have been developed recently. Based on the paradigm of recovering the missing data, deep IMvC methods could be divided into three categories, including i) neighborhood-based methods [Tang and Liu, 2022; Yang et al., 2022b], which impute the missing data with the help of cross-view nearest neighbors, ii) predictor-based methods [Lin et al., 2021; Lin et al., 2022], which learn a direct mapping from observed views to missing views for data recovery, and iii) GAN-based methods [Wang et al., 2018; Jiang et al., 2019; Zhang et al., 2020], which recover the missing data through adversarial generation.

Among the above works, deep IMvC methods are most similar to this study. However, this study is remarkably different from existing works in the following aspects. First, the existing works impute data based on the observed counterparts which might discard either instance commonality or view versatility. In contrast, the proposed prototype-based imputation paradigm performs recovery using the prototypes in the missing view and the sample-prototype relationship in the observed view, thus taking the best of both worlds. Second, to the best of our knowledge, this could be the first attention-based model in the IMvC community, showing its great potential in unsupervised data recovery and IMvC.

2.2 Attention-BasedModel

The attention-based model learns better representation by focusing on regions with relevant information, which has achieved great success in various tasks such as image classification [Yu et al., 2018], person re-identification [Yang et al., 2022a], object detection [Woo et al., 2018], neural machine translation [Vaswani et al., 2017], and sentence summarization [Rush et al., 2015]. Recently, some works have explored the attention mechanism in multi-view learning. For example, [Qu et al., 2017] promotes using attention to collaborate different views for multi-view representation learning. [Zhou and Shao, 2018] proposes a viewpoint-aware attention model for vehicle re-identification. [Luo et al., 2020] implements attention-enhanced matching confidence volume in multi-view stereo. [Yan et al., 2022] introduces lateral connections by cross-view attention, and fuses multi-view information for video recognition.

The major differences between this work and previous attention-based models lie in two aspects. First, different from most existing works that focus on single-stream and instance-wise attention, the proposed dual-streammodel employs a novel dual attention layer to incorporate samples and learnable prototypes with each other. Second, unlike most existing works that solely use attention for general multiview feature fusion, the proposed dual attention layer is IMvC-oriented, which simultaneously facilitates clusteringfavorable feature extraction and data recovery.

3 Method

In this section, we propose a dual-stream model dubbed ProImp to achieve incomplete multi-view clustering. As illustrated in Fig. 2, ProImp is composed of a dual attention layer to model the relationship between samples and prototypes, as well as a dual contrastive learning loss to learn attention and view-specific prototypes. For data recovery, ProImp adopts the prototype-based imputation paradigm to preserve instance commonality and view versatility. In the following, we first introduce our dual attention layer in Sec. 3.1, then elaborate on the dual contrastive learning loss in Sec. 3.2, and finally present the prototype-based imputation paradigm in Sec. 3.3.

3.1 Dual Attention Layer

Without loss of generality, we take bi-view data as an example for clarity. Let X = {X1,2 , X1 , X2} be an incomplete multiview dataset, where X1 ,X2 ,X1,2 refer to three subsets of instances that have data observed in the first, the second, and both views. We denote the set of N complete instances as X1,2 = {X1 ,X2 }, where Xv = {xv1 , xv2 , . . . , xvN } denotes the samples in the v-th view.

As illustrated in Fig. 2, the dual attention is computed between samples Xv and a set of learnable prototypes C v = {cv1 , cv2 , . . . , cvK }, where K corresponds to the target cluster number. Mathematically, the attention Av is computed through

where W v I andW v P are two linear layers for samples and prototypes in v-th view respectively, and d is the dimension of features.

The attention Av is then used to incorporate samples and prototypes in a dual manner. For sample representation, the corresponding prototype is aggregated to each sample, namely,

where Z v = {zv 1 , zv 2 , . . . , z vN } is the new representation of samples, andW ′vP is another linear layer for prototypes. Such behavior intrinsically pulls each sample to its corresponding cluster center, thus enhancing the instance commonality favored in clustering.

Likewise, for prototype representation, features of current samples would be aggregated into prototypes, namely,

where U v = {uv1 , uv2 , . . . , uvK } is the new representation of prototypes, andW ′vI is another linear layer for samples. Such behavior enables prototypes to integrate the historical and current cluster information.

Notably, an encoder network is adopted to extract the features of samples in each view before feeding them to the dual attention layer. Here we omit it in mathematical notations for simplicity.

3.2 Dual Contrastive Learning

As discussed above, the dual attention layer outputs prototype-incorporated samples and sample-incorporated prototypes in each view. To optimize the entire model and learnable view-specific prototypes, we conduct dual contrastive learning on samples and prototypes, respectively.

Sample-Wise Contrastive Learning

To mine instance consistency between cross-view samples, we adopt the following contrastive loss that maximizes the similarities between cross-view samples of the same instance, while minimizing those between samples of different instances, namely,

where s (·, ·) denotes the cosine similarity, τI = 0.5 is the temperature parameter, and L2,1 i is defined similarly as L1,2 i .

Prototype-Wise Contrastive Learning

As discussed, our prototype-based imputation paradigm requires prototypes to capture view versatility. In other words, prototypes from different views should not collapse into an identical representation. To this end, instead of simply maximizing the similarities between cross-view prototypes of the same cluster, we propose to optimize their similarities to a bound. Meanwhile, to achieve a more distinct clustering, we minimize the similarities between prototypes of different clusters, which leads to the following bounded contrastive loss,

where α denotes the similarity bound and τP = 2.0 is the temperature parameter.

Attention Regularization

Recall that the dual attention Av defined in Eq. 1 is an N×K matrix, where Avij intrinsically corresponds to the probability of the i-th sample belonging to the j-th cluster. To achieve more distinct clustering, we expect each sample to be confidently assigned to a certain cluster. Meanwhile, we should prevent the trivial solution where most samples are assigned to the same cluster. For these purposes, we propose the following attention regularization term, namely,

where Av·j = ∑Ni=1 Avij and β is the weight parameter to balance the sharpness and uniformity of attention.

Combining the dual contrastive learning loss and the attention regularization term, we arrive at the overall objective function of the proposed ProImp, namely,

3.3 Prototype-Based Imputation

To recover the missing samples in the incomplete data {X1 ,X2 }, we design the following prototype-based imputation strategy as illustrated in Fig. 2(c). Specifically, given data X1 observed in view 1, the missing data in view 2 is recovered with attention A1 and prototypes C 2 through

where A1 is the dual attention computed in view 1 according to Eq. 1, and ˆ Z 2 is the recovered data in view 2. The idea behind such an attention inheritance is that the instance semantics are expected to be consistent across different views. By incorporating cluster- and view-specific information from prototypes, both instance commonality and view versatility could be preserved in the recovered data. In addition, samples from the observed view are skip-connected to the recovered data to introduce instance consistency.

Likewise, the missing data ˆ Z 1 in view 1 is similarly recovered given data X2 observed in view 2. Let Z1 and Z2 denote the observed views in the incomplete data, the representation Z = {{Z 1 ,Z 2 }, {Z1 , ˆ Z 2 }, { ˆ Z 1 , Z2 }} of both the observed and recovered data is concatenated and fed into the k-means algorithm to achieve clustering. Notably, though the attention itself intrinsically corresponds to the cluster assignment, it only utilizes data from a single view. Therefore, a simple concatenation operation is applied to gather multi-view information.

4 Experiment

In this section, we evaluate the proposed ProImp method on five widely-used multi-view datasets compared with 11 baselines. First, we present the experimental setting and implementation details in Sec. 4.1. Then, we compare our ProImp with state-of-the-art methods in Sec. 4.2. After that, we conduct the parameter analyses and ablation studies in Sec. 4.3. Finally, we present visualization results in Sec. 4.4.

4.1 Experimental Settings

Five multi-view datasets are used in our experiments, including Scene15 [Fei-Fei and Perona, 2005], Reuters [Amini et al., 2009], NoisyMNIST [Wang et al., 2015], CUB [Zhang et al., 2019a], and MNIST-USPS [Peng et al., 2019]. We randomly remove one view for m instances to simulate incomplete multi-view data with a missing rate of m/n, where n corresponds to the total number of instances.

The proposed ProImp is implemented in PyTorch 1.11.0 and all the experiments are conducted on an NVIDIA 3090 GPU on Ubuntu 20.04 OS. The model is trained for 150 epochs using the Adam optimizer with an initial learning rate of 1e-3, with a batch size of 1,024 on all datasets. The similarity bound α in Eq. 6 and the weight parameter in Eq. 7 are set to 0.75 and 0.02, respectively. In practice, we first warm up the model with the sample-wise contrastive loss in Eq. 5 and the regularization term in Eq. 7 for 50 epochs. After that, we align the prototypes in different views with the Hungarian algorithm and train the model with the overall loss in Eq. 8 till the end.

Three widely-used metrics including Accuracy (ACC), Normalized Mutual Information (NMI), and Adjusted Rand Index (ARI) are used for evaluation. A higher value of these metrics indicates a better clustering performance.

4.2 Comparisons with State of the Arts

We compare ProImp with 11 state-of-the-art multi-view clustering baselines, including DCCA [Andrew et al., 2013], DCCAE [Wang et al., 2015], BMVC [Zhang et al., 2018], AE2 -Nets [Zhang et al., 2019b], PMVC [Li et al., 2014], UEAF [Wen et al., 2019], DAIMC [Hu and Chen, 2019], EERIMVC [Liu et al., 2020], COMPLETER [Lin et al., 2021], SURE [Yang et al., 2022b], and DSIMVC [Tang and Liu, 2022].

We first evaluate ProImp and baselines under the Incomplete (with the missing rate of 50%) and Complete (with the missing rate of 0%) scenarios. Table 1 shows the average clustering performance under five random experiments. As can be seen, our ProImp significantly outperforms the state-of-the-art methods on all datasets. In particular, ProImp achieves a relatively 22% (28.53% v.s. 23.32%) and 39% (32.77% v.s. 23.56%) ARI improvement under the Incomplete and Complete scenarios on the Reuters dataset, compared with the second best method SURE. The superior performance demonstrates the effectiveness of the proposed dual-streammodel, including the dual attention layer and dual contrastive learning objective.

We further explore the robustness of ProImp by increasing the missing rate from 0% to 90% with a gap of 10% on the Scene-15 dataset. Considering that the number of complete instances would be greatly reduced under large missing rates, we adjust the batch size to 128 and set the learning rate as 3e-4 in this experiment. As shown in Fig. 3, our ProImp substantially outperforms baselines under all missing rates. In addition, the performance of ProImp drops less as the miss rate increases. For example, in terms of ACC, ProImp outperforms SURE by 2.23% (43.18% v.s. 40.95%) under the complete scenario, and the performance gap increases to 4.26% (39.17% v.s. 34.91%) under 90% missing rate. Such a result demonstrates the superiority of our attention imputation strategy for data recovery, as it could preserve both the view versatility and instance commonality information.

In this section, to better understand the effectiveness of each component in ProImp, we conduct a series of parameter analyses and ablation studies. In brief, we first investigate the influence of the similarity bound α in the prototype stream loss and the balance weight β in the attention regularization term. Then we perform ablation studies on each loss term. Finally, we test variant data recovery strategies.

Influence of Hyper-Parameters α and β

There are two hyper-parameters in the proposed ProImp, namely, the similarity bound α in the prototype stream loss and the balance weight β in the attention regularization term. To investigate how they influence the performance of ProImp, we change α in the range of {0, 0.25, 0.5, 0.75, 1} and β in the range of {0.001, 0.02, 0.1, 0.5, 2}. As shown in Fig. 4a, ProImp achieves the best performance when α = 0.75. According to the cross-view prototype similarity shown in Fig. 4b, positive prototype pairs get closer as α increases. An over-small cross-view prototype similarity would harm view consistency, and an over-large value would sacrifice the view versatility, both leading to inferior performance. As for the other parameter β, we find that ProImp achieves promising results under a reasonable range (i.e., from 0.001 to 0.1). However, when the balance weight is too large, the attention between each instance and prototype tends to be equal. Such a collapsed attention would cause a significant performance drop.

Effectiveness of Each Loss Term

To explore the effectiveness of the proposed sample-wise contrastive loss, prototype-wise contrastive loss, and attention regularization, we conduct the ablation experiments on the three losses in Eq. 8. According to the results shown in Table 2, the regularization term LR itself is not sufficient to learn appropriate attention. Both LS and LP could guide attention optimization, leading to better clustering performance. The best performance is achieved when all three losses are adopted, as both the instance commonality and view versatility are achieved.

4.3 Parameter Analyses and Ablation Studies

Variants of Data Recovery Strategy

Recall that to preserve instance commonality and view versatility, we recover the missing view by the sample-prototype attention inherited from the observed view and prototypes from the missing view, namely, ˆ Z 2 = X1 +W ′2P C 2 (A1 )T via Eq. 9. Here, to prove the superiority of our paradigm, we further investigate three other variants of recovery strategies on the Scene-15 dataset. Specifically,

• Prototypes from observed views: recovering by using the prototypes and sample-prototype attention from the observed view, i.e., ˆ Z 2 = X1 +W ′1P C 1 (A1 )T ;
• Prototypes frommissing views only: recovering by only using prototypes from the missing view, i.e., ˆ Z 2 = 2W ′2P C 2 (A1 )T ;
• Samples from observed views only: recovering by only using the observed cross-view counterparts, i.e., ˆ Z 2 = 2X1 ;

Notably, as both sample and prototype features are L2 normalized, we scale the features of the last two variants to keep the length consistent. From the results in Table 3, one could have the following conclusions. First, replacing the missing view prototypes with those in the observed view would lose the view versatility, thus remarkably degrading the performance. Second, solely using prototypes or crossview counterparts suffers from losing either cross-view consistency or instance commonality, resulting in sub-optimal results. In comparison, our default paradigm takes the best of both worlds, leading to the best performance.

2

4.4 Visualizations

In this section, we present two visualization results on the NoisyMNIST dataset with a missing rate of 0.5 to provide an intuitive understanding of the training process and data recovery performance of ProImp.

Features Learned by ProImp Across the Training Process

We conduct t-SNE visualization on features learned by ProImp at three different training epochs in Fig. 5. As can be seen, data forms four clusters at the initialization, which corresponds to the observed and recovered data from two views. After 50 epochs, data tends to form semantic clusters. However, as the prototypes are not yet matched across views, the recovered data is not semantically aligned with the observed data. At the end of the training, the gap between observed and recovered within-cluster samples is significantly narrowed, indicating a good instance commonality. Meanwhile, samples from different views are still not collapsed together, indicating that the view versatility is well preserved.

Data Recovery Performance

As discussed, a major advantage of our prototype-based imputation strategy is that it could preserve both instance commonality and view versatility in the recovered data. To prove its superiority, we visualize the observed and recovered data learned by our ProImp and the best competitor SURE in Fig. 6. From the results, one could see that i) data recovered by our ProImp forms more compact clusters, thanks to the dual-stream model which enhances the commonality between within-cluster instances, and ii) data recovered by our ProImp shows a more distinct pattern with observed data, which demonstrates that the view versatility is preserved from the view-specific prototypes.

To provide a quantitative evaluation of instance commonality, we compute the silhouette score on the data recovered by different paradigms. A larger value indicates better withincluster compactness and between-cluster scatter. The results in Table 4 show that our prototype-based imputation strategy significantly enhances the instance commonality, surpassing existing generative and neighborhood-based paradigms.

5 Conclusion

To implement the proposed prototype-based imputation paradigm, we propose a dual-stream model by designing a dual attention layer and a dual contrastive learning loss. Thanks to the proposed model, the instance commonality and view versatility could be preserved into representation, thus boosting the IMvC performance. Extensive experiment results demonstrate the superiority of our model in both clustering and data recovery performance. In the future, we plan to extend ProImp to handle the datasets that consist of three and more views.

Acknowledgments

This work was supported by NSFC under Grant U21B2040, 62176171, U19A2078, and Sichuan Science and Technology Planning Project (Grant No. 2022YFS0128).

Contribution Statement

† Equal Contribution. ∗ Corresponding Author. Xi Peng conceived the study. Haobin Li and Yunfan Li designed the ProImp and are of equal contribution. Mouxing Yang ran the baseline methods. Peng Hu and Dezhong Peng analyzed the results. All authors participated in the writing of the manuscript.