Learn Multi-task Anchor: Joint View Imputation and Label Generation for Incomplete Multi-view Clustering

1 Introduction

Multi-view data has attracted significant attention in many real-world applications such as medical diagnosis [Bai et al., 2024] and multimedia recommendation [Yu et al., 2023]. It captures diverse and complementary information about the same object from different sources. However, equipment malfunctions or selective information collection can result in missing partial views, leading to incomplete multi-view data. For example, in imaging examinations like X-ray, CT, and MRI, patients often undergo partial tests based on specific symptoms, resulting in incomplete medical histories. As one of the most effective tools to analyze incomplete multi-view data, incomplete multi-view clustering groups unlabeled samples into semantic clusters by exploring the correlations between samples and views [Wen et al., 2023a].

∗Corresponding author.

In recent years, numerous incomplete multi-view clustering methods have been proposed [Wu et al., 2024; Wan et al., 2024b; Lu et al., 2024; Wen et al., 2023b; Hu and Chen, 2018; Wang et al., 2021a]. Among these, anchor-based incomplete multi-view clustering explores and exploits the representational capacity of anchors to reveal underlying clustering structures, achieving great success. For instance, [Wang et al., 2022] utilized view-shared anchors to capture the consistent data distributions among views. [Liu et al., 2022] introduced view-specific anchors to integrate the complementary information among views. [Li et al., 2023a] employed the distribution of observed data to improve anchor learning. [Li et al., 2024] removed hyperparameters to enhance model applicability. However, these approaches still experience several limitations.

On one hand, most anchor-based incomplete multi-view clustering methods rely on constructing additional anchor graphs to capture relationships among samples. Spectral analysis and factorization techniques are then applied to these graphs to generate final clustering indicators [Wang et al., 2020b]. However, the introduction of additional variables or separate processes can lead to information loss and suboptimal performance [Liu et al., 2021b]. On the other hand, how missing views are handled significantly affects model performance. Some methods utilize only observed views [Wen et al., 2021a; Wang et al., 2021b; Wan et al., 2024b], ignoring the semantic information of the missing views. Some approaches fill in missing views using all available observed views [Wen et al., 2019; Wen et al., 2021b; Liu et al., 2021a], which can introduce redundant information and diminish the quality of the imputed views.

To address these issues, we propose a Joint View Imputation and Label Generation (JVILG) method that facilitates high-quality missing view imputation and direct label generation. First, we project the multi-view data from the original feature space into a latent embedding space, where data reconstruction is learned with the help of fine-grained anchors in respective views. These anchor representations in each view are explored with orthogonality constraints. For label generation, we construct a view-specific membership matrix that correlates the anchor matrix with cluster centroids, establishing explicit connections among fine-grained anchors, cluster centroids, and soft clustering labels. To further capture the diversity and complementary information among cluster indicators, we impose tensor Schatten p-norm regularization on the constructed label tensor. For missing view imputation, we assume that the missing views share latent subspace structures with fine-grained anchors. Therefore, missing views can be recovered using the linear combinations of anchors from the same subspace. The L1-norm is applied to coefficient matrices to preserve only the necessary intrinsic relationships. Additionally, we introduce adaptive weights to balance the contributions from each view. We devise an alternating optimization algorithm to solve the unified objective function. Our method directly outputs soft labels without post-processing. The main contributions are summarized as follows:

• We propose a novel mutli-task framework for missing view imputation and incomplete multi-view clustering. To our knowledge, this is the first approach that directly generates clustering labels from anchors and recover missing views.
• To facilitate direct label generation, we utilize a membership matrix to establish explicit connections among data observations, fine-grained anchors, and cluster partitioning within a reconstruction framework.
• To effectively imputemissing views, we use fine-grained anchors to linearly reconstruct the missing views, applying a sparse constraint on the coefficient matrix to avoid spurious connections.
• Comprehensive experimental results on six datasets demonstrate the advantages of our JVILG over both shallow and deep methods for incomplete multi-view clustering.

2 RelatedWork

2.1 Anchor-based Incomplete Multi-view Clustering

Anchors have emerged as powerful tools in effectively revealing data distribution in multi-view clustering. Typically, the K-means method and random sampling are used to generate these anchors with clustering potential [Kang et al., 2020]. Recently, [Guo and Ye, 2019] selected common instances as anchors to bridge non-overlapping partial views, though this method only addresses two-view cases. To mitigate the occasionality and randomness associated with heuristic anchors, [Chen et al., 2023] proposed dynamic anchor learning to enhance clustering performance. To address the crossview anchor misalignment problem, [Li et al., 2023b] introduced a predefined anchor-level graph, transforming this issue into a cross-view cluster-level alignment problem. Additionally, [Zhao et al., 2023] integrated single-view local anchors with concatenated-view global anchors to explore diverse and consistent information among views. Other developments include view-independent anchors [Liu et al., 2022], view-shared anchors [Wang et al., 2022], and deep anchors [Cui et al., 2023], all aimed at improving performance. These methods have demonstrated significant success, highlighting the substantial potential of anchors. However, they depend on additional anchor graphs to generate final labels and fail to directly produce labels from anchors. Moreover, these methods utilize anchors solely to construct anchor graphs, ignoring the potential of anchors for imputing missing views.

2.2 Label Generation for Multi-viewClustering

To obtain labels for multi-view data, two primary approaches are commonly used. The first involves applying K-means on sample representations to derive final labels, though this method is sensitive to initialization. Some studies utilize matrix factorization to implement K-means. For example, [Cai et al., 2013] proposed parallelized multi-view K-means to directly output final labels, while [Hu and Chen, 2019] adapted this approach for incomplete multi-view data using an indicate matrix strategy. However, the fixed-dimensional centroid matrix may limit model performance due to its restricted representational capacity [Wan et al., 2023]. The second approach relies on spectral analysis, which constructs graphs to capture correlations among samples. [Tang et al., 2022] expanded multi-view spectral clustering to generate discrete labels, while [Wen et al., 2023a] learned a consensus graph for direct label acquisition using k-connected components. However, tuning parameter settings to ensure appropriate kconnected components remains challenging. Notably, none of these methods can directly learn labels from incomplete multi-view data using anchors, limiting their ability to reduce information loss.

3 ProposedMethod

This section elaborates our Joint View Imputation and Label Generation (JVILG) approach. We model the JVILG as a reconstruction problem that leverages subspace correlation to strengthen the relationships between missing views and anchors. We present our approach in two aspects and formulate a unified objective function for JVILG.

3.1 Anchor-based Tensorized Label Generation (ALG) for Incomplete Multi-view Data

Much redundancy in original data hinders the ability to depict the underlying data structure using all data samples [Chen et al., 2024]. Anchor-based incomplete multi-view clustering methods rely on anchor representations to enhance the model's discriminative ability [Guo and Ye, 2019]. However, existing methods fail to establish explicit connections among the input observations and underlying data structure. The introduction of mediating variables, such as anchor graphs, can lead to information loss and suboptimal outcomes [Chen et al., 2023; Wan et al., 2024a].

To address this issue, we develop a label generation module based on anchor representations. Given an incomplete multiview dataset {︁X(v) ∈ Rdv×n}︁mv=1 , where dv denotes the dimensionality of the v-th view, n is the total sample size, and m is the number of views, with missing views zero-imputed, the objective function can be formulated as follows:

where Pv ∈ Rl×dv represents projection matrix, and the uncorrelated constraint enhances the separability of the projected data points. Av ∈ Rl×b is anchor matrix of the vth view, on which an orthogonality constraint is imposed to achieve mutual independence among different anchor representations, enhancing their discriminative power. Wv ∈ Rb×k is a membership matrix that indicates the degree to which fine-grained anchors are related to the cluster centroids, with AvWv representing the centroids. Fv ∈ Rn×k is cluster indicator matrix. ψ is a nonnegative hyper-parameter that controls the trade-off.

However, Eq. (1) reconstructs different views independently, without considering their inter-view correlations. Inspired by the excellent performance of the tensor Schatten p-norm [Gao et al., 2020] in capturing inter-view complementary information and spatial structure, we apply it to a third-order tensor, where Fv as lateral slices. Thus Eq. (1) is rewritten as follows:

Each frontal slice of F represents the relationships between sample and cluster centroids across different views, Shatten p-norm in Eq. (2) ensures that indicators of different views exhibit across-view similarity.

3.2 Anchor-based Sparse Regularized Subspace Correlation (ASC) for View Imputation

To reduce the impact of missing views, JVILG employs dynamic data imputation. High-quality anchors not only disclose the underlying data structure but also aid in recovering missing views. Thus, we can infer the missing views using anchors by solving the following subspace correlation learning module.

where Ev ∈ Rl×nv represents missing view matrix, and Zv is coefficient matrix that captures subspace correlations. L1norm regularization term ensures that Zv is sparse, maintaining only the essential connections. The missing view can be recovered using a linear combination of a small number of anchor points from the same subspace. β is a nonnegative hyper-parameter that controls the trade-off. Unlike existing models that uses the whole observed data to recover missing views, Eq. (3) alleviates the impact of potential noisy observations.

3.3 Unified Objective Function

Considering the objectives of label generation and missing view imputation simultaneously, we minimize the following objective function:

where Ψ = {av,Pv,Av,Wv,Fv,Ev,Zv}. β is a trade-off hyper-parameter. a2v is an adaptive weight for the v-th view. Gv ∈ {0, 1}nv×n is a prior matrix defined as follows, which indicates the missing information of the v-th view:

where h(v) ∈ Rnv contains the indices of the nv missing instances of the v-th view, corresponding to their original positions. Based on this, PvXv +EvGv represents a complete view, with all views aligned.

3.4 Optimization

Eq. (4) is a non-convex optimization problem, and it is difficult to directly solve these variables. Inspired by Alternating Direction Method of Multipliers (ADMM) [Boyd et al., 2011], we devise an alternating optimization algorithm to address this objective function. By introducing an auxiliary variable J and setting F = J , the objective function in Eq. (4) can be expressed in the following separable form:

where Y represents the Lagrange multiplier and ρ denotes the penalty factor. The solution to Eq. (6) can be obtained by solving the following eight sub-optimization problems.

Update Av: With {Pv, Ev,Wv, Fv,Zv} fixed, for each Av, we need to minimize the following objective function:

(7)

The optimal solution of Eq. (7) is U[I, 0]VT , where U and V are the left and right singular vectors obtained from the Singular Value Decomposition (SVD) of (PvXv + EvGv)FvWT v +βEvZTv .

UpdateWv: With {Pv, Ev, Av, Fv,Zv} fixed, for eachWv, we need to minimize the following objective function:

By removing the normalization constraint, the partial derivation of Eq. (8) with respect toWv is

ThenWv can be obtained by

Eq. (10) is an euclidean projection problem on the simplex space [Wang et al., 2020a].

Update Fv: With {Pv,Ev,Av,Wv,Zv,J} fixed, for each Fv, we need to minimize the following objective function:

The optimal solution of Eq. (11) is

where Bv = a2vWT v Wv + ρ2 I. Update J : With {Pv,Ev,Av,Wv,Zv,Fv} fixed, for J , we need to minimize the following objective function:

which has a closed-form solution as Lemma 1 [Gao et al., 2020].

LEMMA 1. Let T ∈ Rn1×n2×n3 has a tensor-Singular Value Decomposition T = U ∗ Σ ∗ V ⊤, then the optimal solution for

is H = Γτ(T ) = U ∗ ifft (︁Pτ(Σ))︁ ∗ V ⊤, where Pτ(Σ) is an f-diagonal third-order tensor in Fourier domain, whose diagonal elements can be found by using the GST algorithm introduced in [Gao et al., 2020]. ifft(·) is the inverse discrete Fourier transform along the third dimension.

Update Ev: With {Pv,Av,Wv,Zv, Fv} fixed, for each Ev, we need to minimize the following objective function:

The partial derivation of Eq. (15) with respect to Ev is

Update Zv: With {Ev,Av} fixed, for each Zv, we need to minimize the following objective function:

The optimal solution can be obtained using the well-known soft-threshold operator [Yang and Zhang, 2011].

Algorithm 1 JVILG

Input: V -view incomplete dataset {Xv }mv=1 , the number of clusters k, and the number of anchors b.

Output: Clustering labels of data points.

• 1: Initialize: Ev =Av =Wv = Pv = 0, Fv = [I, 0],
• 2: Initialize Y = 0, av = 1m , ρ = 10-5 , µ = 2
• 3: while not converge do
• 4: Update Av by Eq. (7);
• 5: UpdateWv by Eq. (10);
• 6: Update Fv by Eq. (12);
• 7: Update J by solving Eq. (13);
• 8: Update Ev by solving Eq. (16);
• 9: Update Zv by solving Eq. (17);
• 10: Update Pv by solving Eq. (18);
• 11: Update av by Eq. (20);
• 12: Update Y and ρ: Y = Y + ρ(F - J), ρ = min(µρ, 1012 );
• 13: end while
• 14: Calculate the clustering results by using
• F = ∑︁Vv=1 a2v Fv/ ∑︁Vv=1 a2v .
• 15: return Clustering results (The label for the corresponding sample is given by the index of the largest element in each column of F).

Update Pv: With {Ev, Av,Wv, Fv} fixed, for each Pv, we need to minimize the following objective function:

The optimal solution of Eq. (18) is Up[I, 0]VT p , where Up and Vp are the left and right singular vectors obtained from the Singular Value Decomposition of (AvWvFTv - EvGv)XTv .

Update av: With {Pv,Ev,Av,Wv,Fv} fixed, for each av, we need to minimize the following objective function:

where r2 v = ⃦⃦PvXv +EvGv -AvWvFTv ⃦⃦2F + ∥Zv∥1 + β ∥Ev -AvZv∥2F . Based on Cauchy-Schwarz inequality, Eq. (19) has a close-form solution as follows:

In summary, we outline the entire optimization procedure for solving Eq. (6) in Algorithm 1.

3.5 Convergence and Complexity

Convergence Analysis: Our problem is bounded due to the summation of norms with positive penalty parameters. Furthermore, the optimization procedure in Algorithm 1 consists of eight sub-problems, each of which can reach exact minimum points. This implies that each sub-problem exhibits a monotonic decrease. Therefore, our algorithm can at least find a locally optimal solution according to the convergence theorem in [Rudin and others, 1964].

Complexity Analysis: Our algorithm mainly focuses on solving Av, Wv, Fv, J , Ev, Zv, Pv, and av. The computational complexity in updating these variables iteratively are O(mlb2 ), O(mkb), O(nl ∑︁mv=1 dv), O(2mnklog(mk)+ m2kn), O(nl ∑︁mv=1 dv), O(bl ∑︁mv=1 nv), O(nl ∑︁mv=1 dv), and O(1). Due to b ≪ n, dv ≪ n, and m, k, l are small constants, the main computational complexity of solving Eq. (6) is O(max(nl ∑︁mv=1 dv,m2kn)). This indicates that our approach can scale well with data size.

4 Experiments

Datasets: We evaluate the performance of our method on six extensively used multi-view datasets. ProteinFold [Wan et al., 2024b], Caltech101-7 [Fei-Fei et al., 2006], BDGP [Wang et al., 2022], CCV [Jiang et al., 2011], Animal [Lampert et al., 2009], and NUSWIDEOBJ [Chua et al., 2009]. The sample sizes range from 694 to 30000, and the number of views ranges from 3 to 12. The details of these datasets are shown in Table 1. We follow previous works [Wang et al., 2022; Liu et al., 2022] to construct incomplete multi-view datasets. We set a missing rate r ∈ {10% : 10% : 90%} and randomly select r samples as incomplete data by dropping partial views. The remaining 1 - r samples are kept complete.

Compared Methods: We compare our approach against two baseline methods and nine state-of-the-art methods: BSV (k-means on the best view), Concate (k-means on concated views), DAIMC [Hu and Chen, 2018], sFSR-IMVC [Long et al., 2023], FIMVC-VIA [Liu et al., 2022], IMVCCBG [Wang et al., 2022], SMVC-SA [Wen et al., 2023b], PSIMVC-PG [Li et al., 2024], FCMVC-IV [Wan et al., 2024b], DIVIDE [Lu et al., 2024], CPSPAN [Jin et al., 2023]. For the baseline methods BSV and Concate, we use the average feature values of the existing instances in current view to impute the missing instances. For the other compared methods, the hyper-parameters are set to the recommended values in their original papers. Shallow models are performed on a computer with a 3.5GHz AMD Ryzen 9 3950X CPU and 64GB RAM, MATLAB2022b (64-bit).

To evaluate the performance, three commonly used clustering metrics: accuracy (ACC), normalized mutual information (NMI), and Purity are used. The higher the values of these metrics, the better the clustering performance.

4.1 Performance Comparison

The clustering results (Each experiment is repeated 10 times.) on four datasets with 10%, 50%, and 90% missing ratios are reported in Table 2. We can draw the following observations:

1. Our JVILG achieves the best performance across the three metrics in most cases, demonstrating its superiority in incomplete multi-view clustering tasks. e.g., on the CCV dataset with a 10% missing ratio, our approach outperforms the second-best method, DIVIDE (a deep model) by about 13.73% on the ACC metric.
2. In most cases, an intuitive observation is that the model performance gradually decreases as the view missing ratios increase. The missing view imputation capability of our JVILG model can alleviate the effects of information loss, and help the model maintain the excellent performance. For example, On the BDGP, CCV, and Animal datasets, the ACC values increase by 11.48%, 7.68%, and 4.81%, respectively, as the missing ratio increases from 10% to 50%. Moreover, as the missing ratio reaches 90%, the model performance is still encouraging.
3. Compared to deep models like DIVIDE and CPSPAN, JVILG demonstrates better performance, highlighting the potential of anchors in capturing data distribution.

To further verify the effectiveness of our model, we vary the missing ratios from 10% to 90% with an interval 10% on the ProteinFold and Caltech101-7 datasets. The result curves are shown in Figure 1. We can observe that our method significantly outperforms other compared methods, and its performance remains stable even as the missing ratio increases.

We employed the t-SNE technique [Van der Maaten and Hinton, 2008] to plot the learned cluster representations of our model and the suboptimal sFSR-IMVC model on the BDGP dataset, as shown in Figure 2. Our model demonstrates more clearer cluster discriminability.

4.2 View Imputation Validation

To validate the missing view imputation capability of our JVILG model, we presented the incomplete data, filled data, projected filled data, and learned soft labels on View #1 of the BDGP dataset with a 50% missing ratio, as shown in Figure 3. Solid circles represent the observed data, while pentagrams denote the filled data. Comparing Figure 3 (a) and (b), the zero imputation results are clustered together, while the imputation values learned by our model are distinctly separated into their respective clusters. Figure 3 (b) and (c) show that the imputation values are effectively integrated into the corresponding clusters through projection learning. This indicates the improved cluster structures in the learned latent representations. Finally, Figure 3 (d) illustrates that the soft labels for the filled data accurately recover the underlying data distribution. These recovered data reside on the same subspace manifold structures as the observed data, demonstrating the effectiveness of our JVILG model.

4.3 Parameter Study

Our method involves four parameters to be set appropriately, i.e., parameter β, ψ, tensor low rank coefficient p, and the number of anchors b. As shown in Figure 4, we tune β in the range of 10[-5:1:4] , and vary ψ within {0.1, 1, 10, 50, 100}. Our JVILG achieves satisfactory performance in a wide scope of β and ψ. Fine tuning is still necessary for different datasets due to their diverse properties. Figure 5 demonstrates the effects of parameters p and b, which are varied as p ∈ {0.1 : 0.1 : 1} and b ∈ {k : k : 6k}. Notably, parameter p does impact the model performance, and a small number of anchors can achieve effective and stable results.

4.4 Convergence Study

We optimize the objective function iteratively by introducing an auxiliary variable J . Convergence of our algorithm is determined by checking the difference between F and J . As shown in Figure 6, the difference decreases significantly as the iterations approach 20, ultimately nearing zero. Additionally, clustering metrics such as ACC, NMI, and Purity improve gradually and stabilize as the algorithm converges. This indicates the strong clustering performance of our approach.

5 Conclusion

This paper concerned missing view imputation and direct label generation for incomplete multi-view data. Our JVILG model learned versatile anchors to achieve these tasks simultaneously. These anchors can relax the correlations between missing views and semantic clusters, allowing for the imputation of missing view representations and label generation in different feature spaces. For label generation, we introduced membership matrices to learn semantic cluster centroids from fine-grained anchors, fromwhich soft labels are generated to effectively partition the data. Moreover, the tensor Schatten p-norm was imposed on the constructed label tensor to capture complementary information among views. For missing view imputation, we applied subspace correlation to recover missing data from anchors, leveraging their diverse representations. An alternating optimization algorithm was proposed to solve the unified objective function. Extensive experiments demonstrated the effectiveness of our method.

Acknowledgments

This work was funded by the Science and Technology Development Fund, Macau SAR (File no. 0049/2022/A1, 0050/2024/AGJ), by the University of Macau Development Foundation (File no. MYRG-GRG2024-00181-FSTUMDF).