High-Confident Local Structure Guided Consensus Graph Learning For Incomplete Multi-view Clustering

1 Introduction

Multi-view clustering (MVC) aims to categorize data points into their respective classes by comprehensively taking into account multiple feature representations, where each of these feature representations can be seen as a unique view [Sun et al., 2024]. For instance, a webpage typically includes three types of representations, i.e., text, imagery, and hyperlinks. Besides this, the test results for a patient often contain different indicators, such as CT, blood routine, and electrocardiogram [Fu et al., 2024] [Lyu et al., 2024]. Given the prevalent occurrence of incomplete data, with missing views or instances, in practical applications such as recommendation systems, disease diagnosis, and multimedia analysis, the research of incomplete multi-view clustering (IMC) holds significant importance [Chen et al., 2024] [Chao et al., 2024]. Besides this, Khan et al. [Khan et al., 2024] designed a weighted concept factorization approach.

∗ indicates the co-corresponding authors

Some common issues may emerge in the IMC tasks due to the absence of views [Wang et al., 2022] [Wen et al., 2021]: 1) The lack of views can complicate the integration of the remaining views, potentially reducing the accuracy and effectiveness of the clustering algorithm. 2) The problem of data imbalance caused by missing views makes the traditional multi-view clustering technique ineffective. Various researchers have undertaken considerable efforts to address these challenging IMC problems. For example, Cai et al. [Cai et al., 2024] incorporates a completion term designed to fill in the missing samples in unbalanced incomplete multi-view clustering, which utilizes the inherent information contained within the absent views. Chao et al. [Chao et al., 2024] introduces a multi-view consistency relation transfer combined with a graph convolutional network to address the missing values problem. This approach incorporates instance-level attention fusion and high-confidence guiding strategies to harness the complementary information available. Although existing IMC methods have achieved some positive performances, we notice that these approaches primarily focuses on pairwise-based geometric structures, which are easily affected by the weak feature expression or noisy [Gu et al., 2024] [Wang et al., 2023]. In particular, some samples located at the edge of two clusters are inaccurate in local structure learning due to their weak feature expression or noise effects. Therefore, accurate local structure learning is very important for calculating the affinity relationships between different samples [Yao et al., 2024] [Zhong et al., 2024].

Block diagonal structure (BDS) construction refers to the process of arranging a matrix into a block diagonal matrix form, where the matrix is partitioned into a series of smaller square submatrices along its main diagonal, and all elements outside these blocks are zero [Lu et al., 2018]. The learning BDS means that samples of different categories are strictly differentiated, which makes intra-class samples show relatively high correlation [Zhuo et al., 2024]. Consequently, the BDR is crucial in the incomplete multi-view learning, as it facilitates the model to accurately depict the internal connections of the available instances for each view [Liu et al., 2023b]. This is essential in IMC tasks, since it can provide precise comprehensive and available information from different views for the derivation of complete structure.

Motivated by this observation, we propose a simple but efficient method, called high-confident local structure guided consensus graph learning for incomplete multi-view clustering (HLSCG IMC). Specifically, this method can adaptively learn a strict block diagonal structure from the available samples using a block diagonal representation regularizer. Different from the existing methods using a simple pairwise affinity graph for structure construction, we consider the influence of instances located at the edge of two clusters on the construction of graph for each view. By harnessing the proposed highconfident strict block diagonal structures, the approach seeks to directly guide the learning of the robust consensus graph. As depicted in Fig.1, we first learn a high-confident local structure with a BDS regularizer for the available instances from each view. Afterwards, we reconstruct the complete graphs of all incomplete views by fully exploring the withinview and between-view information available in each view with the guiding of the learned high-confident local structure. Finally, unliking the existing consensus representation learning methods, we directly learn a confident affinity graph across all views for final clustering. Specifically, To ensure that the latent representation and graphs of all views achieve global optima, we integrate the high-confident local structure learning and the consensus graph completion into a unified joint optimization framework. The primary contributions of this paper are summarized as follows:

1. Different from the other existing methods, we propose a high-confident local structure learning strategy, which considers the attribution of instances with weak feature representation located at the edge of two clusters.

(2) A HLSCG IMC method is proposed, which can adaptively recover the complete graph for each view by exploiting the hidden information of missing instances and available in-

• stances to directly enhance the learning of consensus graph across all views.

(3) The proposed method can be flexibly applied to any types of IMC tasks. In addition, the experimental results proved the superiority of the proposed method in comparison with the other related methods.

2 Notations and Preliminaries

Given a matrix A ∈ Rm×n , we define its lF -norm and l1-norm as ∥ A ∥2F = ∑mi=1 ∑nj=1 a2i,j and ∥ A ∥1= ∑mi=1 ∑nj=1 |ai,j|, respectively, where ai,j presents the element on the (i, j)-th location. Additionally, The nuclear norm of matrix A is calculated as ∥ A ∥∗= ∑i γi, where γi indicates the ith singular value of A. The detailed notations of the used variables are presented in Table1.

BDS: The block diagonal structure highlights the independence of the submatrices, enabling efficient storage and manipulation of the matrix, particularly in scenarios where the submatrices represent distinct or separable components of the original matrix. By leveraging the sparsity and structural independence of the block diagonal matrix in (1), computations such as matrix multiplication, inversion, and eigenvalue analysis can be greatly simplified and accelerated. Here, we introduce two definitions abou BDR as follows [Lu et al., 2018]:

Definition 1: Let X = [X1,X2, ...,XC] ∈ Rd×n denote n training samples from C classes, where each column is a sample vector. Suppose that all the samples are rearranged based on the class labels, and each class of training samples are stacked together to form a sub-matrix Xi ∈ Rd×ni , which denotes ni samples from the i-th class.

Definition 2: Given the data matrix X = [X1, X2, ..., Xk] drawn from a union of k subspaces {Si}ki=1 , we say that Z obeys the Block Diagonal Property if Z is k-block diagonal, where the nonzero entries Zi correspond to only Xi.

Please note that the notions of the k-block diagonal matrix and the block diagonal property share certain connections as well as distinctions. The block diagonal property is tailored specifically for the context of subspace clustering problems, whereas the concept of a k-block diagonal matrix is more general and not confined to this particular application. A matrix that satisfies the block diagonal property is necessarily k-block diagonal, but the converse is not true. Additionally, the block diagonal property stipulates that each block must have a one-to-one correspondence with each data subject.

3 The ProposedMethod

3.1 LearningModel

Various clustering methods based on graph learning have demonstrated that acquiring a high-quality graph, which unveils the underlying relationships within the data, is advantageous for achieving superior clustering performance [Liu et al., 2023a][Zhou et al., 2019]. Particularly, graph learning plays a pivotal role in multi-view clustering by enabling the extraction of intricate relationships and correlations between different views of the data. A block diagonal structure refers to a matrix that is partitioned into diagonal blocks, where each block is itself a square matrix, and all off-diagonal blocks are zero matrices. Furthermore, the block diagonal constraint can act as a regularizer, preventing the model from overly relying on any single view and encouraging it to discover shared and discriminative features across all views [Jiang et al., 2025].

Given the multi-view dataset X = {X(v) }Vv=1 ∈ Rdv×n , where v is the vth view, V presents the total number of views, and dv denotes the dimensionality of the features from the vth view. Here, under the independent subspaces assumption, the self-representation matrix Z (v) for each view should be block diagonal as follows:

where ||Z|| k is the block diagonal matrix structure induced regularizer. For the affinity matrix Z (v) on the vth view, its kblock diagonal regularizer ||Z (v) || k is formulated as follows:

where λi(LZ(v)) is the eigenvalues of LZ(v) and i ∈ [1 n].

Problem and Motivation: Formula (2) necessitates that all perspectives of X are entirely comprehensive, a requirement that is impractical for IMVC tasks due to the varying sizes of graphs derived from incomplete perspectives. To tackle these challenges, some research endeavors concentrate on reconstructing the absent elements within the incomplete graphs linked to the missing perspectives [Lin et al., 2021]. However, these endeavors typically entail significant computational expenses. Furthermore, achieving perfectly reconstructed graphs from incomplete multi-view data is unfeasible, which could potentially degrade clustering performance. Consequently, the optimal approach is to maximize the utilization of the information contained within the accessible instances from each view. By adopting the prior index information of the missing instances, we perform the following extension of Z (v) :

where G(v) indicates the prior index information of the missing instances and ¯ S(v) is the complete graph of the v-th view. Importantly, it can transform the incomplete graph with size nv × nv of each view to a full size affinity graph with size n × n, such that the pairwise similarity relationships of instances between ¯ S and Z (v) can be alligned. In addition, ||·||1 can better simulate noise and learning bias. Here, the highconfident local structure ˜ Z (v) is defined as follows:

where qi,j indicates the distance between x(v) i and x(v) j calculated using the Gaussian kernel, and Ψ(x(v) j ) presents the k block of instance x(v) j on the v-th view. Otherwise, G(v) is computed as follows:

In particular, when dealing with incomplete multi-view data, the missing instances also result in the absence of certain pairwise correlations. Aiming to comprehensively exploit the complementary affinity information from different, we further impose a high quality consensus graph to align the structures of all views. Thus, we propose the final efficient but simple objective function of HLSCG IMC as follows:

where αv denotes an adaptive learned weight, which is applied to jointly balance the importance of all views. Specifically, F ∈ Rn×c is the consensus representation, c is the manual selected dimension which is generally chosen as the cluster number. Besides this, LS presents the Laplacian matrix of the complete structure S ∈ Rn×n , which can be achieved by LS = DDT - (S+ST ) 2 . In addition, W (v) can be calculated as follows:

where W (v) is the affinity relationship matrix between the missing instances and the existing instances.

3.2 Optimization

In this section, we use the alternating direction method of multipliers (ADMMs) to solve the optimization problem (7), which can be simply transformed into the following equivalent problem:

where C (v) 1 and C (v) 2 are the imposed argumented variables, and ¯ Z (v) = G(v) T ˜ Z (v)G(v) .

Solution of Z(v) : With the other variables fixed, Z v can be solved by optimizing the following formular:

Then, Z (v) can be calculated by setting the derivative of (10) with respect to Z (v) as 0:

Solution of B(v) : With the other variables fixed, B(v) can be solved by optimizing the following formular:

Then, (18) can be simplified as follows:

where L(v) 3 = Z (v) + C (v) 2 /µ. Particularly, ω(v) = U (v)U (v) T , where U (v) consists of k eigenvectors associated with the k smallest eigenvalues of Diag(B(v)1) -B(v) . Then, (19) can be rewritten as follows:

This problem has a closed form solution given as follows:

where A(v) = L(v) 3 + µ β (diag(W (v) )1T -W (v) ). Afterwards, B(v) can be updated as B(v) = ( ˆ A(v) + ˆ A(v) T )/2, where ˆ A(v) = A(v) - Diag(diag(A(v) )).

Solution of E(v) : With the other variables fixed, E(v) can be solved by optimizing the following formular:

where L(v) 4 = X(v) -X(v)Z (v) + C(v) 1µ . Here, E(v) has the closed solution as follows:

where ω denotes the shrinkage operator.

Solution of S: With the other variables fixed, S can be solved by optimizing the following formular:

By defining Hi,j =∥ Fi,: - Fj,: ∥22 , we can rewrite (18) as the following n independent sub-optimization problems with respect to each column of S:

According to the Lagrangian algorithm, we can obtain the following closed form solution:

where Ti,j = ∑Vv=1 αrvW (v) i,j 2 ¯ Zi,j- λ4 Ei,j ∑Vv=1 αrvW (v) i,j 2 . Here, (b)+ guarantees the non-negative value of b. Then, we can update δj = 1-∑ni=1,i̸=j Ti,j n-1 .

Solution of α: With the other variables fixed, α can be solved by optimizing the following formular:

By imposing the Lagrange multiplier sigma, we can rewrite the optimization problem (21) as follows:

Then, we can update α by setting the derivative of (22) with respect to αv as 0 as follows:

Solution of F: With the other variables fixed, F can be solved by optimizing the following formular:

Algorithm 1 Solution of HLSCG IMC

Input: Incomplete multi-view data {X(v) ∈ Rdv×nv }Vv=1 , prior index matrix G(v) , and parameters λ, β, and γ.

Initialization: Initialize Z (v) via the k-nearest neighbor graph of each view; Initialize F with the eigenvalue decomposition on the Laplacian graph of each transformed complete view; C (v) 1 = 0, C (v) 2 = 0; C (v) 3 = 0; µ = 0.1. Output: Z (v) , F.

• 1: while iteration < R do
• 2: Update Z (v) using (11)
• 3: Update B(v) using (15)
• 4: Update E(v) using (17)
• 5: Update S using (20)
• 6: Update α using (23)
• 7: Update F using (24)
• 8: Update C (v) 1 and C (v) 2 using (25) and (26), respectively.
• 9: end while

Here, F can be gained as F = [e1, e2, ..., ec] ∈ Rn×c , where e1 ≤ e2 ≤ ... ≤ ec are the c eigenvectors corresponding to the c minimum eigenvalues.

Solution of C(v) 1 and C(v) 2 : With the other variables fixed, C (v) 1 and C (v) 2 can be solved by optimizing the following formulars:

We present the detailed solutions for each variable of (9) in Algorithm 1.

3.3 Computation Complexity Analysis

In this sub-section, we make computation complexity analysis on the optimization steps of the proposed objective function. Firstly, for the step of Z (v) , the most computational costs is the inverse operation calculated as n3 . Afterwards, ror the optimization approach of S and B(v) , it is observable that the updating formula for the pertinent variable merely involves element-wise multiplication and division operations on matrices and vectors. Afterwards, the computational complexity of E(v) can be ignored since it only contains the basic matrix operations. For the solution of F, an efficient eigenvalue decomposition algorithm with the package 'eigs' serves as an excellent option, necessitating only O(cn2 ) operations to obtain the optimal F . Finally, for the step of α, its updating formula similarly encompasses solely element-wise division operations for vectors. Consequently, the total computational cost of the proposed objective function is O(τ(cn2 + n3 )), where tau denotes the number of interations.

4 Experiments and Analysis

4.1 Database Description

BBCSport 1 : BBCSport constitutes a document database comprising 737 news articles pertaining to five sports: athletics, cricket, football, rugby, and tennis, sourced from the BBC Sport website between 2004 and 2005. For the purpose of evaluating various algorithms grounded in Integrated Multiview Clustering (IMC), a subset from the BBC sport multiview datasets, encompassing four distinct views, was utilized. This specific subset contains 116 samples, where each of the four views possesses a feature dimensionality of 1991, 2063, 2113, and 2158, respectively. The Columbia Object Image Library 2 (COIL-20) comprises a total of 1,440 images spread across 20 different classes. To create the multi-view dataset, we extracted three feature types from each image: deep features using the VGG-F model [Zhao et al., 2019], Local Binary Patterns (LBP) features [Oliva and Torralba, 2001], and vectored pixel features. Meanwhile, the Caltech101 database encompasses 101 object categories, with each class having between 40 to 800 images [Fei-Fei et al., 2004]. For the comparison experiments conducted in this paper, a subset known as Caltech-7 was chosen, which includes 1474 images from 7 classes. Specifically, the selected multi-view dataset for Caltech-7 consists of two views: GIST and LBP features [Li et al., 2015]. Referring to [Zhao et al., 2016], a subset of the BUAA-visnir face database 3 was chosen to evaluate the proposed method, which comprises two views, i.e., 90 visual images and 90 near-infrared images, all belonging to the first 10 classes.

1 https://github.com/GPMVCDummy/GPMVC/tree/master/ partialMV/PVC/recreateResults/data

2 http://www.cs.columbia.edu/CAVE/software/softlib/coil20.php

Incomplete multi-view data construction: In this paper, the incomplete multi-view dataset was created by randomly removing 10%, 30%, and 50% instances in each view. Then, every algorithm method was carried out on each dataset 10 times, and the average value was reported as the final result. The evaluation metrics used were clustering accuracy (ACC), normalized mutual information (NMI), and purity [Wen et al.,

3 https://github.com/hdzhao/IMG/tree/master/data.

2020]. All experiments conducted in this study were run on MATLAB R2020a, utilizing a hardware setup with 16.0 GB of RAM and a 3.40 GHz CPU.

4.2 Experimental Results and Analysis

In the comparative experiments, the proposed method was evaluated alongside a range of state-of-the-art IMC methods., i.e., BSV [Zhao et al., 2016], Concat [Zhao et al., 2016], GPMVC [Rai et al., 2016], MIC [Shao et al., 2015], DAIMC [Hu and Chen, 2019], OMVC [Shao et al., 2016], MVL IV [Xu et al., 2015], AWIMVC [Deng et al., 2020], UEAF [Wen et al., 2019], and AGC IMVC [Wen et al., 2020]. Table 2 reports the experimental results on the BBCSport, COLI-20, Caltech-7, and BUAA databases, respectively. From Table 2, it can be observed that:

1. The proposed method can always obtainsthe best clustering performances on different incomplete multi-view databases. It shows that graph-based methods have clear advantages compared to the other related methods.
2. Because the proposed method is capable of uncovering higher-order correlations among various views, it outperforms the other methods in terms of performance.
3. The proposed method can be flexibly adopted to various types of IMC tasks.

4.3 Parameter Sensitivity Analysis

Three parameters, namely λ, β, and γ, are required to be adjusted for the proposed objective function. To identify the optimal parameter combination for each database, a series of experiments were conducted on the BUAA dataset. Figure 2 illustrates the sensitivity of the proposed method on different combinations of parameters on the BUAA dataset. Notably, our method exhibits minimal sensitivity to λ within the range of [10-3 , 1]. Furthermore, it is evident that the highest clustering accuracy for the BUAA database is achieved with β and γ in the range of [10-5 , 1] and [10-5 , 1], respectively.

4.4 Ablation Experiments

To demonstrate the effectiveness of the block diagonal structure embedding term, we implemented a variation that utilized a traditional K-NN to construct the affinity graph. This variation was evaluated on the COIL-20 and Caltech-101 databases, each with a 30% missing rate of views. Figure 3 depicts the experimental results of the proposed method incorporating different activation components. It can be obviously observed from Figure 3 that the proposed strategy consistently achieve the highest clustering accuracies.

4.5 Visualization

In this subsection, we applied the widely used Gram matrix visualization algorithm to the BBCSport dataset, which has a 10% missing rate in each view. This algorithm utilizes a color scale to depict the magnitude of the values within the matrix, with darker shades representing higher values and brighter shades indicating lower values. As illustrated in Figure 4, it is evident that our proposed method effectively recovers the ground-truth diagonal block structure, where each diagonal block corresponds to a distinct cluster.

5 Conclusions

In this paper, a novel and efficient IMC framework, called HLSCG IMC, for incomplete multi-view clustering is proposed. Unliking the other related works, it considers the attribution of instances with weak feature representation located at the edge of two clusters. Afterwards, a high-confident local structure is learned for each view to guide the intrinsic and complete structure construction. The experimental results demonstrate that the proposed method can effectively recover the missing affinity relationships and notably enhance the performance of IMVC. In the future, HLSCG IMC will be adopted to more application scenarios.

Acknowledgments

This work was partially supported by the Guangdong Basic and Applied Basic Research Foundation (Grant no. 2024A1515011647, and 2024A1515030213), and the Shenzhen Fundamental Research Program (Grant no. Ref.JCYJJCYJ20240813154703005).