Consensus-Guided Incomplete Multi-view Clustering via Cross-view Affinities Learning

1 Introduction

In the wake of the ongoing progression of information technology, the same object can be observed from multiple sources and engender multi-view data [Wang, 2021], [Fang et al., 2023], [Wang et al., 2023]. The consistent and complementary information embedded within such data is customarily harnessed to tackle the multi-view clustering (MVC) [Su et al., 2024], [Tan et al., 2024], [Long et al., 2024a] task. However, in practical applications, it is often intractable to ensure the completeness of multi-view data [Wu et al., 2024].

∗Corresponding Author.

Figure 1: Comparison between traditional strategy and our strategy. (a) The traditional strategy focuses on pairwise interaction between the current view and others. (b) Our strategy fully considers the collaborative effects among multiple views and leverages consensus representation to regulate the learning of high-order consistency.

As a result, incomplete multi-view clustering (IMC) [Wang et al., 2024a], [Long et al., 2024b], [Yao et al., 2025] has attracted considerable attention for its ability to partition missing data into their corresponding classes.

Owing to the remarkable success of multi-view subspace clustering (MVSC) as described in [Cao et al., 2015], [Kang et al., 2020], [Huang et al., 2022], most IMC approaches [Li et al., 2022], [Gu et al., 2024] follow a pipeline similar to MVSC with a two-step strategy: constructing a unified affinity graph followed by applying spectral clustering, in which the construction of the affinity graph plays a pivotal role in the IMC process.

According to the way of affinity graph construction, existing IMC methods can be categorized into subspace clustering-based methods [Liang et al., 2024], [Liu et al., 2024a] and graph learning-based methods [Wang et al., 2024b], [Chen et al., 2025]. For instance, in [Wen et al., 2020], missing view inference and the semantic consistency constraint were incorporated into MVSC to learn complete pairwise consistency between views. [Zhao et al., 2023] applies the between-view consistency constraint to establish a joint graph completion framework and achieve pairwise consistency learning. The mentioned IMC methods prioritize the recovery of missing instances to enhance the accuracy of affinity graphs, a principle that our method also follows. While these methods have achieved outstanding performance in the IMC task, they often rely on simple dual-view interaction to explore pairwise consistency, as depicted in Figure 1(a). This reliance may restrict the comprehensive exploration of holistic characteristics and clustering structure information across multiple views. Meanwhile, the pairwise consistency calculation between views tends to diverge from the true data clustering distribution affected by various noises.

To surmount the above weakness, this paper puts forward a novel cross-view affinities learning (CAL) framework for IMC, which learns a unified structural graph through the high-order interaction between content and structural information across multiple views, under the guidance of a consensus representation. Specifically, two padding matrices are introduced to extract comprehensive content information for each view and capture sample-wise affinities. Following this, CAL applies the structured sparsity constraint on acquired affinity representations to filter out erroneous connections between clusters arising from reconstruction errors and inherent noise. Furthermore, CAL decomposes view-specific affinity representations into a consensus representation and diverse representations with linear relationships. Unlike prior methods that rely on dual-view interaction, CAL stacks the consensus representation together with affinity representations into a tensor, making full use of the collaborative effects across multiple views to excavate and learn a structural graph with high-order semantic consistency. Eventually, to preserve the distinctiveness of each view, the view-specific representations and the learned structural graph jointly contribute to the computation to yield a unified structural graph. In summary, the flowchart of CAL is illustrated in Figure 2, and its main contributions can be encapsulated as follows:

• We propose a novel cross-view affinity learning method, which stacks the consensus representation and the affinity representations into a high-order tensor. It can efficiently learn a unified structural graph by considering collaborative effects across multiple views.
• By recovering missing instances and applying a structured sparse constraint to the representation tensor, CAL
• enhances the learning of comprehensive and precise content and structural information in each view, which facilitates the acquisition of a unified structural graph.
• To substantiate the superiority of high-order interaction over dual-view interaction, extensive experiments were conducted on seven benchmark datasets, and the comparison results demonstrated that our approach can achieve state-of-the-art performances in most cases.

2 The ProposedMethod

In this section, we will delve into the details of the proposed CAL. As shown in Figure. 2, CAL aims to learn a unified structural graph based on the complete content information and clean structural information within each view via highorder interaction across multiple views.

Suppose {X(v) }mv=1 denote incomplete multi-view data with m views and can be divided into an existing instance set X(v) E ∈ Rdv×N (v) E andmissing instance setX(v) M ∈ Rdv×N (v) M , i.e., X(v) = [X(v) E ,X(v) M ], where the feature dimension is denoted by dv, and N represents the total number of instances, which is equivalent to the sum of N (v) E and N (v) M .

Sample-wise Affinities Learning: In order to exploit the complete semantic information of each view to enhance the expressive ability of affinity representations, CAL introduces two padding matrices F(v) E ∈ RN (v) E ×N and F(v) M ∈ RN (v) M ×N that map existing and missing instances to respective positions in the complete feature matrix to reconstruct incomplete views, such that the v-th feature matrix can be rewritten as:

where F(v) E is constructed by iteratively substituting the columns of the zero matrix O(v) E ∈ RN (v) E ×N , which correspond to the indices of existing data in view v with the columns of the identity matrix I(v) E ∈ RN (v) E ×N (v) E . Similarly, F(v) M is constructed by substituting the columns of the zero matrix O(v) M ∈ RN (v) M ×N corresponding to the indices of missing data in view v with the columns of the identity matrix I(v) M ∈ RN (v) M ×N (v) M .

Then, adhering to the principle that each data point is amenable to linear representation by others, we carry out view reconstruction involving missing instances and formulate the objective function for sample-wise affinities learning as

where Z(v) ∈ RN×N and B(v) 1 ∈ Rd(v)×N are an affinity representation and error matrix for v-th view, respectively. In the above ways, CAL can effectively impute the missing data to mitigate the deviation caused by data imperfections. Building upon this, CAL further captures the richer content information for each view and explores the sample-wise affinities.

Intrinsic Representation learning: We regard the harmful information, induced by reconstruction error, outliers, and inherent noise concealed within views, as biased error. The affinity structure in Z(v) is vulnerable to being compromised by such biased error, giving rise to erroneous inter-cluster connections. Directly utilizing these damaged affinity representations to learn consistency between views could lead to a divergence from the realistic clustering distribution of the data. To this end, we stack {Z(v) }mv=1 into a tensor Z and subsequently separate the biased error by decomposing Z as follows:

where the intrinsic tensor L encodes the real relationships among all samples, including available and absent instances in each view. The biased tensor S is utilized to describe the harmful information and the ℓ2,1-norm is employed to capture the biased error among views as

where Φ is an operator used to construct a third-order tensor by aggregating all affinity representations. Moreover, the purified view-specific affinity representations {L(v) }mv=1 are decomposed into linearly related consensus representation Lc and diverse representation B(v) 2 .

Multiple View Interaction Learning: Upon the successful acquisition of comprehensive content information and clean structural information, we prefer to conduct high-order interaction among multiple views under the guidance of consensus representation rather than dual-view interaction. The dual-view interaction typically concentrates solely on the associations between two views at a time and there are significant limitations in mining the holistic characteristics of multiview data. In contrast, high-order interaction can fully leverage the collaborative effects of multiple views and effectively break through the information barriers formed by dual-view interaction. Based on the above description, we can arrive at the overall objective function of our method CAL as follows:

where λ1 and λ2 are the trade-off parameters of the corresponding terms in the model. The tensor T ∈ RN×(m+1)×N is a rotated tensor stacked with the affinity representations L(v) and the consensus representation Lc. Within this tensor, the consensus representation acts as a coefficient of consistency and is enforced by the weighted tensor Schatten pnorm constraint, it effectively promotes the exploration and reinforcement of consistent information across all views and we can acquire a consistent structural graph Lc. After learning the optimal Lc and L(v) , the unified structural graph R considering consistency and specificity can be calculated by

and then the final clustering result is gained by performing spectral clustering on R.

3 Optimization

3.1 Optimization Algorithm

By introducing an auxiliary tensor variable A, the augmented Lagrangian function of problem (5) can be formulated as:

where φ = {{X(v) M ,Z(v) ,B(v) ,L(v) }mv=1 ,Lc, S,A} represents the set of variables to be optimized, ρ > 0 is a penalty parameter, Y, C1 and C(v) 2 are Lagrange multipliers. We will iteratively optimize each variable with the following details.

(1) X(v) M Step: Fixing other variables and considering the constraint X(v) = X(v) E F(v) E +X(v) M F(v) M , we can derive the optimal solution by setting the partial derivatives of the minimization problem to zero:

(2) Z(v) Step: When all the other variables are fixed, Z(v) can be obtained by solving the following sub-problem:

By setting the partial derivative ∂L (Z(v) )/∂Z(v) = 0, we can obtain that:

Then, the optional Z(v) is obtained by solving

The optional solution is [Nie et al., 2016]:

with η = 1 n-1 - 1 n-1 N∑ j=1,j̸=i ˜Z(v) i,j .

(3) B(v) -Step: The solution for B(v) can be divided into the following two parts for solving:

where E(v) 1 =X(v) -X(v)Z(v) andE(v) 2 = L(v) -Lc+ C(v) 2ρ , Eq. (13) is a sparsity constraint optimization problem and has the following two closed-form solutions [Wen et al., 2019]:

where ϑ represents the shrinkage operator.

1. L(v) -Step: Similar to X(v) M , we can obtain the updating rule of Lv by taking the derivative of corresponding minimization problem and setting it to zero as:

1. S-Step: Removing the unrelated variables, S can be obtained by optimizing the following problem:

Algorithm 1 CAL Algorithm

Input: Incomplete multi-view data {X(v)

Parameter: λ1, λ2, ρ, η and ρmax;

E }mv=1 , padding matrix {F(v) E }mv=1 and {F(v) M }mv=1 , clustering number k;

Initialize: Let Z(v) , B(v) , L(v) , Lc, A(v) , Ac, C(v) 2 , S, Y and C1 to be all zero;

• 1: while not converged do
• 2: Update the variablesX(v) M , Z(v) , B(v) and L(v) of each view by Eqs. (8, 12, 14, 15).
• 3: Update the variables S, A, Lc and Lagrange multipliers by Eqs. (16, 17, 18, 19).
• 4: end while
• 5: Derive R by Eq. 6 and perform spectral clustering on it.

Output: L(v) , Lc;

where K = Z - L + C1 ρ . It can be resolved with the aid of lemma 4.1 in [Liu et al., 2013].

(6) A-Step: Fixing other variables, the objective function of auxiliary variable A is formulated as:

It can be resolved using Theorem 4 in [Gao et al., 2020].

1. L(v) c -Step: Similar to the process of solving for L(v) , the optional solution of Lc is given by

(8) Lagrange multipliers-Step: The updating rules of all Lagrangian multipliers are listed below.

where ρ = min (ρη, ρmax). In summary, the whole optimization procedure is presented in Algorithm 1.

3.2 Computational Complexity Analysis

In detail, the complexity of matrix inverse operation for variables {X(v) M }mv=1 and {Z(v) }mv=1 in each iteration is denoted as O( m∑ (N - N (v) E )3 ) and O(mN 3 ) respectively.

For updating rotated tensor A ∈ RN×(m+1)×N , the major computational costs lie in calculating the 3D FFT and the 3D inverse FFT, each of which has a complexity of O(2N 2 (m+1) log(N)). Besides, the N SVDs operation of N × (m + 1) matrices in the Fourier domain takes O(N 2 (m+1)2 ). Considering the other steps involve only fundamental matrix operations, we disregard their computational costs. Thus, the total computational complexity of Algorithm 1 is about O(t( m∑ v=1 (N - N (v) E )3 + mN 3 + 2N 2 (m + 1) log(N) + N 2 (m + 1)2 )).

4 Experiment

4.1 Experimental Settings

Datasets: We evaluate our method on seven popular multiview datasets, including BBCSport, MSRC, ORL, BBC, Caltech101-7, Flower and Handwritten datasets. Table 2 lists the general statistics.

Compared methods: We compare CAL with the following ten state-of-the-art methods: EE-E-IMVC [Liu et al., 2021], GIMC FLSD [Wen et al., 2021a], IMVTSC-MVI [Wen et al., 2021b], PSIMVC-PC [Li et al., 2024], SAGF IMC [Liang et al., 2023], TCIMC [Xia et al., 2022], LSIMVC [Liu et al., 2023], PIMVC [Deng et al., 2023], HCLS CGL [Wen et al., 2023], SCSL [Liu et al., 2024b], among which IMVTSCMVI and TCIMC are also tensor-based methods.

Incomplete data construction: For each dataset, we arbitrarily remove 10%, 30%, 50%, and 70% samples from each view to construct incomplete multi-view data, while ensuring that each sample exists in at least one view.

Implementation Details: For the comparative methods, we have sought their optimal hyper-parameters following the recommendations in the original papers. For our CAL, we select

λ1 and λ2 within the range of [10-5 , 103 ] and evaluate our method using three popular metrics: accuracy (ACC), normalized mutual information (NMI), and purity.

4.2 Experimental Results and Analysis

All experimental results on seven datasets w.r.t. three metrics are illustrated in table 1 and table 3, where the best results are in red and the second-best are highlighted in blue. From the experimental results, we can reach the following observations: (1) Our method almost achieves the best performance on all datasets and exhibits significant improvements in cases of high missing rates. For instance, on BBCSport dataset with a missing rate of 70%, our algorithm achieves advancement of 18.45%-53.02%, 17.64%-71.74%, and 8.45%-

51.29% in terms of three respective metrics. (2) Compared with the second-best performing method (IMVTSC-MVI) on most datasets, our method shows a substantial enhancement in the NMI metric under equal or lower ACC, which not only illustrates the superiority of high-order interaction across multiple views over dual-view interaction but also validates that consensus guidance can boost the ability to learn consistency. (3) We employ heatmaps and t-SNE to visualize the unified structural graph R and show in Figure 3, that the structural graph exhibits a distinct block diagonal structure and compact clusters, indicating that our method more effectively explores the data clustering structure. (4) From the perspective of interaction mechanisms, CAL establishes consensus-aware interactions based on existing tensor rank constraints compared with other methods, which can optimize the interaction process through consensus structure and achieve dynamic fusion between specific and consensus representation. Additionally, CAL can retain complete and accurate data clustering relationships through the dual affinity constraint mechanism composed of sample-wise affinities learning and intrinsic representation learning.

Parameter sensitivity analysis: In this subsection, we analyze the impact of model parameters λ1 and λ2 on clustering performance. Figure 4(a) and (c) illustrates the variation in ACC for different combinations of λ1 and λ2 on BBCSport and ORL datasets with a 30% missing rate. It can be observed that satisfactory performance is achieved when λ1 varies within the range [10-2 , 103 ]. The clustering results for BBCSport and ORL datasets are insensitive to relatively large and small values of λ2, respectively. Furthermore, we also investigate the influence of power parameter p in Figure 4(b) and (d). Generally, CAL obtains ideal clustering results when p is selected from [0.8, 0.9].

Convergence analysis: This paper develops an alternative optimization algorithm for solving the proposed CAL model. By iteratively optimizing each sub-problem and obtaining a closed-form solution, we ensure that the algorithm is bounded below. Additionally, convergence curves on Flower and Caltech101-7 datasets with a 30% missing rate are plotted in Figure 5, depicting the evolution of algorithm loss and ACC throughout iterations. It is evident that the algorithm loss declines promptly and has a lower bound of 0.

Ablation study: We conduct the ablation study to validate the effectiveness of each submodel and record the results on BBCSport and ORL datasets ith different missing rates. In specific, based on Eq. (5), we establish the below two degenerate methods: CAL without structured sparsity constraint (CAL-I) and high-order interaction without consensus guidance (CAL-II). From the results in table 4, it is evident that the clustering results of both variants are inferior to the original method. Moreover, in most cases, the performance degradation of CAL-II from the missing rate of 0.1 to 0.7 across the three metrics is greater than that of CAL-I. Large fluctuations in the performance of CAL-II underscores the substantial role of consensus representation in advancing consistency learning among multiple views in high-order interaction.

5 Conclusion

In this paper, we propose a cross-view affinity learning method named CAL for incomplete multi-view clustering, which effectively avoids the limitations posed by dual-view interaction on information fusion. CAL integrates comprehensive content information and pure structural information to acquire a unified structural graph for clustering under the guidance of consensus representation through the high-order interaction across multiple views. Moreover, an effective optimization algorithm for the CAL has been developed and extensive experiments have been carried out to validate its superiority over state-of-the-art methods.

Acknowledgments

This work was supported by the National Natural Science Foundation of China under Grant U21A20470, Grant 62172136 and Grant 72188101, by National Key Research and Development Program of China Grant 2024YFB4710800, by the Institute of Advanced Medicine and Frontier Technology under Grant 2023 IHM01080, Liaoning Provincial Natural Science Foundation Grant 2024MS-012, Dalian Science and Technology Talent Innovation Support Plan, Grant 2024RY010.