--- title: "EMGC²F: Efficient Multi-view Graph Clustering with Comprehensive Fusion" authors: - "Danyang Wu" - "Jitao Lu" - "Feiping Nie" - "Rong Wang" - "Yuan Yuan" doi: "10.24963/ijcai.2022/495" url: "https://ijcai.org/proceedings/2022/495" pdf: "https://ijcai.org/proceedings/2022/0495.pdf" venue: "Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence" year: 2022 pages: "3566-3572" track: "Main Track" keywords: - "Machine Learning: Clustering" - "Machine Learning: Multi-view learning" - "Machine Learning: Unsupervised Learning" --- # EMGC²F: Efficient Multi-view Graph Clustering with Comprehensive Fusion Danyang Wu, Jitao Lu, Feiping Nie, Rong Wang, Yuan Yuan *Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence*, pages 3566-3572. DOI: [10.24963/ijcai.2022/495](https://doi.org/10.24963/ijcai.2022/495) ## Abstract This paper proposes an Efficient Multi-view Graph Clustering with Comprehensive Fusion (EMGC²F) model and a corresponding efficient optimization algorithm to address multi-view graph clustering tasks effectively and efficiently. Compared to existing works, our proposals have the following highlights: 1) EMGC²F directly finds a consistent cluster indicator matrix with a Super Nodes Similarity Minimization module from multiple views, which avoids time-consuming spectral decomposition in previous works. 2) EMGC²F comprehensively mines information from multiple views. More formally, it captures the consistency of multiple views via a Cross-view Nearest Neighbors Voting (CN²V) mechanism, meanwhile capturing the importance of multiple views via an adaptive weighted-learning mechanism. 3) EMGC²F is a parameter-free model and the time complexity of the proposed algorithm is far less than existing works, demonstrating the practicability. Empirical results on several benchmark datasets demonstrate that our proposals outperform SOTA competitors both in effectiveness and efficiency. ## Full text ## 1 Introduction Multi-view clustering is a fundamental task in machine learning that aims to seek for a consistent clustering decision via fusing the information of multiple views [Chao et al., 2021; Xu et al., 2013]. As an important branch of multi-view clustering, multi-view graph clustering (MGC) focuses on seeking for clustering decision from linkages of multiple graphs, and has become more popular in recent years. Existing multi-view graph clustering models can be briefly categorized into three types based on the learning scheme. The first type of models (two-stage) aim to learn a consistent spectral embedding from multi-view similarity matrices or spectral embeddings [Belkin and Niyogi, 2003], then the clustering results can be obtained via K-means or other clustering procedure based on the learned spectral embedding. ∗ Equal contribution † Corresponding author To be specific, the learning schemes mainly include kernel approximation [Kumar et al., 2011; Dong et al., 2021; Wu et al., 2021b], manifold approximation [Wu et al., 2020; Dong et al., 2014] and graph reconstruction [Nie et al., 2016; Nie et al., 2017a]. The second type of models (one-stage) aim to learn a block-diagonal similarity matrix from multiview similarity matrices, in which the learned block-diagonal similarity matrix directly indicates the clustering result. Existing learning schemes of this type mainly include Frobenius norm minimization [Nie et al., 2017b; Li et al., 2020; Huang et al., 2021] and inner product minimization [Zhan et al., 2018]. The third type of models (one-stage) aim to learn the consistent clustering (soft) indicator matrix from multi-view spectral embeddings, and the learning schemes include factorization approximation [Hu et al., 2020; Liu et al., 2021], adaptive Procrustes [Nie et al., 2018], etc. However, the three types of existing models cannot avoid spectral decomposition operator that needs O(n3 ) (n is the number of samples) time complexity for accurate calculations, which is too time-consuming in practice. In this paper, we consider breaking out the traditional spectral-based form and handling multi-view graph clustering comprehensively to enhance both its effectiveness and efficiency as illustrated in Figure 1. To be specific, we propose an Efficient Multi-view Graph Clustering with Comprehensive Fusion (EMGC2F) model to directly optimize cluster indicator via integrating information from multiple views. EMGC2F first adopts a super-nodes similarity minimization strategy to establish a novel cluster indicator learning paradigm without spectral decomposition. Afterwards, EMGC2F considers two multi-view fusion mechanisms as follows. 1) To capture the consistency among multiple views, EMGC2F considers confirming the credible nearest neighbors relationship for each node via voting from multiple views, and constrain each pair of nodes to the same cluster if they are credible nearest neighbors. 2) To capture the importance of different views, an adaptive-weighted learning strategy is introduced. Besides, a vital transformation is proposed to transform EMGC2F into a two-stage scaled form, i.e., graph coarsening and clustering on coarsened graph, which provides the possibility to perform multi-view graph clustering efficiently. To handle the calculation and optimization problem of the two-stage EMGC2F form, an efficient alternative algorithm with O(|E| + m2 )(|E| < n2 ,m < n) time complexity is proposed, where |E| is the number of edges and m is the number of nodes of the coarsened graph. More importantly, EMGC2F is a parameter-free model, and the succinct parameter-free form guarantees the availability in practice. We conduct extensive experiments on several multi-view benchmark datasets, and the experimental results demonstrate that EMGC2F outperforms SOTA competitors on MGC tasks in terms of both effectiveness and efficiency. In a word, it is worthwhile summarizing the main highlights of this paper as the following two sides: Figure 1: EMGC2F and three different types of existing multi-view graph clustering models. Left: two-stage models that learn a consistent spectral embedding from multiple views and obtain clustering results via K-means. Middle: one-stage models that learn a block-diagonal similarity matrix from multi-view similarity matrices and obtain clustering result from its connectivity. Right: one-stage models that learn consistent clustering (soft) indicator matrix from multi-view spectral embeddings, and our proposed EMGC2F that directly learns clustering labels from input multi-view graphs. ![Image](https://ijcai.org/proceedings/2022/fulltext/495/image_000000_9750ffb61e69d75de15262fbe43b2e372eae7093a9d6d2cf64765ae93e7a51f2.png) - Effectiveness: The proposed EMGC2F model is a novel and systematic model to handle MGC tasks. 1) The designed super-nodes similarity minimization strategy contains rich theoretical meaning with several fields. 2) The designed Cross-view Nearest Neighbors Voting (CN2V) and adaptive-weighted learning mechanism comprehensively mine the multi-view information. In experiments, EMGC2F outperforms SOTA competitors on MGC tasks. - Efficiency: The objective problem of EMGC2F can be equivalently transformed into a two-stage scaled form which can be efficiently solved within O(|E| + m2 )(|E| < n2 ,m < n) via the proposed alternative algorithm. Its time complexity is far less than previous works based on O(n3 ) spectral decomposition. In experiments, the efficiency of EMGC2F with proposed algorithm is ahead of current competitors on MGC tasks. Notations. For a matrix X ∈ Rn×d , xi,j denotes the ⟨i, j⟩- th element, xi ∈ Rn and xi ∈ R1×d denote the i-th column and i-th row respectively; For a vector x ∈ Rn , xi denotes the i-th element, ∥x∥1 = ∑ni=1 |xi| and ∥x∥0 denotes the number of non-zero elements in x. For a set Q, |Q| denotes its cardinality; Suppose Qk ⊂ Q is a subset of Q, we denote ¯Qk as the complement of Qk in Q. Besides, in multi-view graph clustering, we denote the undirected weighted graph of s-th view byW(s) = (V,E(s) ,W(s) ), where V is the set of nodes, E(s) is the set of edges, W(s) ∈ Rn×n is the similarity matrix; D(s) ∈ Rn×n (diagonal) is the degree matrix of W(s) , where d(s) i,i = ∑nj=1 w(s) i,j ; L(s) = D(s) -W(s) is the Laplacian matrix of W(s) . Moreover, δ(c, n) ∈ Rn denotes the vector whose c-th element is 1 and the rest elements are 0. For a scalar x ∈ Z and x ∈ [1, n], we utilize the notation x ∈ Z[1,n] for convenience. For scalars x and y, x ∝ y means that x is positive correlational to y. ## 2 EMGC2F: Efficient Multi-viewGraph Clustering with Comprehensive Fusion In this section, we propose an Efficient Multi-view Graph Clustering with Comprehensive Fusion (EMGC2F) model to seek for a consistent clustering decision from multi-view graphs {W(1) , . . . ,W(s)}, where 1 W(s) = (V,E(s) ,W(s) ), s ∈ Z[1,v] is the graph of s-th view. For convenience, we introduce EMGC2F model with the following three folds and summarize the workflow in Figure 2. ## 2.1 Super-Node SimilarityMinimizationModule We first consider a single view form and start describing with set operator. Suppose Q is the set of all samples, Qk is the set of the samples within k-th cluster, and ¯Qk is the complement of Qk in Q. Considering the definition of graph clustering, an obvious observation can be obtained that the similarity between sets (Qk, ¯Qk) should be as small as possible. Inspired of data hierarchical clustering [Reddy and Vinzamuri, 2013], on s-th view, we consider (Qk, ¯Qk) as two super nodes, and then establish the similarity between (Qk, ¯Qk) as the average pairwise similarities (average-link) as follows: 1 In this paper, we also allowW to be an asymmetric translation matrix such as W(s) rw = D-1W(s) , thus we consider w(s) i,j and w(s) j,i separately in this paper. Figure 2: Workflow of the proposed EMGC2F model. A CN2V module is adopted to construct credible nearest neighbors via voting of multiple views, from which a 1NN graph is constructed and nodes in the same connected components are constrained to be in the same cluster. Each cluster is regarded as a super node, and we minimize similarities among different super nodes to obtain good clusters. ![Image](https://ijcai.org/proceedings/2022/fulltext/495/image_000001_1210c14373aee7107f3548733af62e459ab161550aad2475c19fc308209bbbdc.png) Then considering all clusters, the clustering model for s-th view can be written as For better illustration, we introduce an indicator matrix Y ∈ {0, 1}n×c,Y1 = 1 to replace the set operator {Qk}ck=1 , and rewrite problem (2) as follows: Afterwards, we consider the multi-view formulation of problem (3). To present the importance of each view, we consider learning an adaptive weight α(s) for s-th view and problem (3) can be improved as where ∑vs=1 1 α(s) = 1 is a scale constraint to guarantee that the solution (α(s) )∗ and y∗ k satisfy the following criterion: In Eq. (5), since the weight (α(s) )∗ is negative correlational to the loss of y∗ k , (α(s) )∗ can be seen as importance of s-th view. Furthermore, we consider mining the consistent information among multiple views in the following part. ## 2.2 Cross-viewNearest Neighbors VotingModule This part aims to find the credible consistency information among multiple views. To this goal, we first define a coefficient matrix E(s) ∈ Rn×n to describe the nearest neighbors relationship in s-th view as follows where e(s) i,j is the (i, j)-th element of E(s) and i = ϖ(s) j means that node i is the nearest neighbor of node j inW(s) . Since the nearest neighbor information for each pair of nodes may be inconsistent among different views, we define B ∈ Rn×n to describe cross-view nearest neighbors via voting as: where bi,j = 1 means that i and j are cross-view nearest neighbors if they are nearest neighbors (e(s) i,j = 1) in more than half of the views. Afterwards, we hope to generate some credible pairwise labels (whether node i and j belong to same cluster) from B. Formally, we construct a graph B associated with adjacency matrix B and find the connected components via Tarjan's algorithm [Tarjan, 1972], then we generate a pairwise label matrix T as follows: T provides consistent pairwise label information via summarizing consistent cross-view nearest neighbors information. Furthermore, we add a 2 pairwise label constraint for Y via T and improve problem (4) as follows: where the constraint YYT ◦ T = T guarantees that ti,j = 1 ⇒ yi = yj . In summary, problem (9) mines the importance among different views via weights {α(s) }vs=1 and mine the consistent information among multiple views via constraint YYT ◦ T = T, which preforms a comprehensive fusion among multi-view graphs. 2 In fact, the cross-view information in T can be also utilized as regularization to emphasize on the nearest neighbors relationship, such as maximizing sum of yT k Tyk. In this paper, we consider the simplest form that utilizing this information as constraint and the empirical results demonstrate its effectiveness. ## 3 Optimization Problem (9) is hard to solve due to the highly non-convex constraints. In this section, we propose an effective and efficient algorithm to deal with it. At first, we handle the constraint YYT ◦T = T with some equivalent transformations. To this goal, we need to reuse the set operator in Eq. (1). Suppose T has m diagonal blocks, i.e., graph B has m connected components, we define Pr as the set of samples within r-th component. Recall that Qk is the set of samples within k-th cluster of W(s) , its obvious that Qk is composed of several different Pr according to problem (9), i.e., Qk = ⋃r∈Ik Pr where Ik as the corresponding indices. Based on the above definitions, we have Then for s-th view, we construct a graph Z (s) of m nodes associated with a similarity matrix Z(s) where z(s) r,d = ∑i∈Pr ∑j∈Pd (w(s) i,j + w(s) j,i ) and define a vector σ ∈ Rm where σr = |Pr|. Substituting them into Eq. (10) results in Similar to transformation from problem (2) to (3), we introduce a new indicator matrix H ∈ {0, 1}m×c, H1 = 1 and rewrite problem (9) as follows from the perspective of coarsened multi-view graphs {Z(1) , . . . , Z (v) }: where ˜L(s) is Laplacian matrix of Z(s) . Then we solve problem (12) w.r.t. variables {α(s) }v and H alternatively. 1) {α(s) }v-subproblem. For better illustration, we denote ∆(s) = ∑ck=1 ∥˜L(s) hk∥1 2hTk σ(n-hTk σ) . Then when H is fixed, problem (12) w.r.t. {α(s) }v can be expressed as According to Cauchy-Schwarz inequality [Garling, 2005] and the constraint ∑vs=1 1 α(s) = 1, we have ∑vs=1 α(s)∆(s) = (∑vs=1 α(s)∆(s) ) (∑vs=1 1 α(s) ) (i) ⩾ (∑vs=1 √∆(s))2 where the equality in (i) holds when √α(s)∆(s) = r√ 1 α(s) with constant r. Combing with ∑vs=1 1 α(s) = 1, we have Then α(s) can be calculated as 2) H-subproblem. When {α(s) }vs=1 is fixed, problem (12) w.r.t. H can be written as For convenience, we denote ̂Z = ∑vs=1 α(s) (Z(s) +(Z(s) )T ), then we have ∑vs=1 α(s) ∥˜L(s)hk∥1 = ∑vs=1 α(s)hTk (Z(s) + (Z(s) )T )hk = hTk ̂Zhk, then problem (16) can be written as Considering that the constraint H1 = 1 is row-independent, coordinate descend algorithm [Wright, 2015] can be utilized directly to handle problem (17). To be specific, suppose current solution is H. When we seek for the solution ¯hr ∈ R1×c to update r-th row hr , it can be chosen from c alternatives, including {h[1] , h[2] , . . . , h[c] }, where h[i] = δ(i, c), ∀i ∈ Z[1,c]. For better illustration, we let h[0] ∈ R1×c be a zero vector, and H[i] , ∀i ∈ Z[0,c] be a matrix whose r-th row is h[i] and the others are same as H. Based on these definitions, ¯hr can be calculated as ¯hr = δ(t, c) where However, calculating Eq. (18) is time-consuming due to several redundant calculations. To accelerate it, we define and propose the following equivalent transformations: where the equality (ii) holds since Ji,k = J0,k, ∀i ̸= k. Then Eq. (18) can be improved as ## Algorithm 1 The Algorithm for Problem (9) ``` Input: {W(1) , . . . ,W(s) } Output: {α(s) }vs=1 ,Y 1: Calculate Z ∈ Rm×m and σ ∈ Rm in Eq. (10). 2: Initialize H. 3: while not converge do 4: ∀s ∈ Z[1,v], update α(s) via Eq. (15). 5: Calculate ̂Z = ∑vs=1 α(s) (Z(s) + (Z(s) )T ). 6: ∀i ∈ Z[1,c], calculate hTi ̂Zhi and hTi σ. 7: while not converge do 8: for r = 1 to n do 9: Find the index of 1 in hr and save as j. 10: ∀i ∈ Z[0,c], calculate H[i] . 11: Calculate t via Eqs. (20) to (22) and ¯hr = δ(t, c) 12: Update hr as ¯hr . ∀i ∈ Z[1,c], update hTi ̂Zhi and hTi σ via Eqs. (23) and (24). 13: end for 14: end while 15: end while 16: Calculate Y via Eq. (25). ``` Obviously, calculating Ji,i -J0,i is dominated by repeatedly calculating (h[i] i )T ̂Zh[i] i and (h[i] i )T σ for different i, which is expensive yet redundant. For further acceleration, we propose to calculate them based on hTi ̂Zhi, hTi σ and H obtained from the last iteration. Concretely, we denote the index of 1 element in hr as j and discuss the strategies for the following two cases: t can be efficiently calculated by substituting Eqs. (21) and (22) into Eq. (20) and we obtain the optimal ¯h. Afterwards, we need to calculate ¯hTi ̂Z¯hi and ¯hTi σ for use when updating hr+1 . Concretely, we denote the index of 1 element in ¯h as p, and then discuss the calculations of ¯hTi ̂Z¯hi and ¯hTi σ as the following two cases. When i = p, it is easy to observe that ¯hi = h[i] i , then When i ̸= p, it is obvious to obtain that ¯hi = h[0] i , then Notice and all terms on the right hand side have been calculated, so no additional calculation is needed in this step. Table 1: Dataset descriptions. The numbers in parentheses indicate the dimension of corresponding features. | Datasets | COIL20 | DIGIT10 | MSRC | ORL | |-----------------------------|---------------------------|------------------------|--------------------------|--------------------------------------| | Samples Clusters | 1440 20 | 10000 10 | 210 7 | 400 40 | | View-2 View-3 View-4 View-5 | LBP(3304) GABOR(6750) - - | - - | CM(24) HOG(576) LBP(256) | GIST(512) LBP(59) HOG(864) CENT(254) | | View-1 | INTE(1024) | ISO(30) LDA(9) NPE(30) | | | | | | | GIST(512) | | | | | | CENT(254) | - | Updating {α(s) }vs=1 and H alternatively until convergence, we can obtain the optimal H. So far, the optimization of problem (12) is completed, and the whole optimization procedure is summarized into Algorithm 1. Afterwards, the indicator matrix Y of problem (9) can be inferred as Convergence analysis. Algorithm1 optimizes {α(s) }v and H alternatively, and the corresponding sub-problems have been solved. Thus, we can conclude that the objective value of problem (12) will decrease until Algorithm 1 converges. Time complexity. The time complexity of the proposal can be divided into two parts. 1) The time complexity of Eqs. (6) to (8): O(|E|). 2) The time complexity of Algorithm 1: Lines 1-2 cost O(|E|); In the outer-loop, Lines 4-6 cost O(m2 v) (v ≪ m in most cases). In the inner-loop, Line 11 costs O(m) to calculate hTi ̂zi (considering the sparsity of hi), so the total time complexity of Algorithm 1 is O(m2 vt) where t is the number of total iterations. In summary, the time complexity of the whole proposal is O(|E| +m2 vt). ## 4 Experiment To evaluate the performance of our proposals, we employ 4 popular benchmark datasets including COIL20 [Nene et al., ], DIGIT10 [Wu et al., 2021a], MSRC [Lee and Grauman, 2009], ORL [Samaria and Harter, 1994] and they are summarized into Table 1. 10 SOTA multi-view clustering competitors are employed, including AMGL [Nie et al., 2016], SwMC [Nie et al., 2017b], MLAN [Nie et al., 2017a], MVGL [Zhan et al., 2018], AWP [Nie et al., 2018], MEA [Wu et al., 2020], SFMC [Li et al., 2020], NESE [Hu et al., 2020], CDMGC [Huang et al., 2021], OP-LFMVC [Liu et al., 2021]. All the experiments are implemented in MATLAB R2020b on a desktop with Intel i7-7700k @ 4.2GHz CPU and 32GB RAM. Following [Nie et al., 2017b], we construct KNN graph and set the number of nearest neighbors as 10. For AMGL and MEA that need K-means as post-processing, we run K-means 100 times and record results with minimum objective value. For OP-LFMVC, we utilize the multi-view spectral embeddings as input pre-processed matrix. Effectiveness evaluations. We evaluate the effectiveness of EMGC2F with 4 popular clustering metrics, including ACC, NMI, F1-Score and ARI. The clustering results are recorded in Table 2, from which we observe that the proposed EMGC2F outperforms all SOTA competitors on all four datasets. Specifically, EMGC2F exceeds the best competitor by 0.0400(ACC), 0.0171(NMI), 0.0554(F1), 0.0569(ARI) on ORL dataset, and 0.0493(ACC), 0.0246(NMI), 0.0697(F1), 0.0741(ARI) on COIL20 dataset. Furthermore, the CN2V module seeks for a part of (the number is adaptive) credible pairwise pre-labels, so the precision (the proportion of correct pairwise labels in predicted pairwise labels) is vital. We summarize the pairwise precision on 4 datasets into Figure 3, from which we observe that the precision of pairwise labels is 1 on MSRC, ORL, COIL20 datasets and 0.9581 on DIGIT10 dataset. Meanwhile, 998 nodes on COIL20 dataset and over 20% nodes on DIGIT10, ORL datasets are successfully reduced. These promising results indicate that CN2V is extremely effective at extracting consistent information from multiple views and thus beneficial for subsequent procedures. Table 2: Clustering results on 4 real-world datasets. Best results are in bold. | Method | Metric | AMGL | SwMC | MLAN | MVGL | AWP | MEA | SFMC | NESE | CDMGC | OP-LFMVC | EMGC2F | |----------|----------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------|-----------------------------| | COIL20 | ACC NMI F1 ARI | 0.8340 0.9125 0.7756 0.7621 | 0.8542 0.9429 0.8410 0.8318 | 0.8424 0.9250 0.8135 0.8025 | 0.7854 0.9130 0.7867 0.7739 | 0.7299 0.8975 0.7597 0.7449 | 0.8549 0.9240 0.8324 0.8233 | 0.8069 0.9197 0.8197 0.8098 | 0.7278 0.8617 0.7070 0.6902 | 0.8757 0.9450 0.8547 0.8462 | 0.7069 0.8647 0.7135 0.6947 | 0.9250 0.9696 0.9244 0.9203 | | DIGIT10 | ACC NMI F1 ARI | 0.8683 0.7712 0.7664 0.7403 | 0.6148 0.6094 0.5444 0.4739 | 0.5913 0.6181 0.5395 0.4736 | 0.8458 0.7639 0.7443 0.7149 | 0.6502 0.6497 0.5725 0.5198 | 0.7067 0.6833 0.6064 0.5558 | 0.7803 0.7190 0.6821 0.6416 | 0.8711 0.7743 0.7713 0.7457 | 0.8440 0.7620 0.7472 0.7183 | 0.6851 0.6628 0.6001 0.5511 | 0.8793 0.7836 0.7845 0.7605 | | MSRC | ACC NMI F1 ARI | 0.8571 0.7623 0.7494 0.7081 | 0.7619 0.7355 0.7138 0.6619 | 0.6952 0.6565 0.6089 0.5332 | 0.8714 0.7731 0.7560 0.7152 | 0.8952 0.7921 0.8050 0.7734 | 0.8714 0.7951 0.7730 0.7354 | 0.8238 0.7539 0.7398 0.6937 | 0.7667 0.7170 0.6944 0.6433 | 0.8286 0.7642 0.7407 0.6952 | 0.8952 0.7921 0.8050 0.7734 | 0.9143 0.8329 0.8364 0.8099 | | ORL | ACC NMI F1 ARI | 0.8325 0.9273 0.7846 0.7791 | 0.8200 0.9258 0.7416 0.7347 | 0.7600 0.8716 0.6550 0.6460 | 0.8250 0.9351 0.7993 0.7942 | 0.8000 0.9142 0.7691 0.7632 | 0.7625 0.9079 0.7130 0.7053 | 0.7875 0.9039 0.6883 0.6796 | 0.8075 0.9114 0.7512 0.7449 | 0.8250 0.9320 0.7815 0.7758 | 0.7850 0.9145 0.7576 0.7513 | 0.8725 0.9522 0.8547 0.8511 | Figure 3: The precision of cross-view nearest neighbors being in the same ground truth cluster and the reduced ratio (n-m)/n of CN2V. ![Image](https://ijcai.org/proceedings/2022/fulltext/495/image_000002_e77003c190ff560bc7b282b2e04742cb5df42b60d28227312ceaa24d33f80d70.png) Efficiency evaluations. In this part, we aim to evaluate the efficiency of the optimization (Algorithm 1) of EMGC2F model. For each model, we run it for 5 times and report the averaged execution time in Table 3. From the results, we can observe that the optimization efficiency of EMGC2F is far ahead of other models, which matches the theoretical analysis that the O(|E|+m2 vt) complexity of EMGC2F optimization is much more efficient than O(n3 ) of current works that depend on spectral decomposition in pro-processing or (and) learning procedure. The convergence curves on 2 benchmark datasets are plotted into Figure 4, from which we observe that Algorithm 1 can converge rapidly. Table 3: Mean execution time (s) of 5 runs. > 1000 s are omitted. | Algorithm | COIL20 | DIGIT10 | MSRC | ORL | |-------------|----------|-----------|--------|---------| | AMGL | 1.2397 | 515.5103 | 0.2326 | 0.4684 | | SwMC | 323.7284 | - | 5.9962 | 11.8308 | | MLAN | 8.4658 | - | 0.1022 | 0.2913 | | MVGL | 91.3807 | - | 0.7722 | 2.9360 | | AWP | 0.5025 | 169.6220 | 0.0169 | 0.0713 | | MEA | 9.3117 | - | 0.3328 | 1.0009 | | SFMC | 7.1074 | - | 0.7504 | 2.0840 | | NESE | 3.9386 | 183.4303 | 0.1025 | 0.4033 | | CDMGC | 10.8803 | - | 0.5603 | 1.2253 | | OP-LFMVC | 0.9626 | 228.9462 | 0.1272 | 0.4398 | | EMGC2F | 0.0136 | 0.4829 | 0.0121 | 0.0090 | Figure 4: The convergent curves on 2 real datasets. ![Image](https://ijcai.org/proceedings/2022/fulltext/495/image_000003_b7a62e1d47d945e4782de84639c5fc05ccf0d12abb93cac435cde1894764eea9.png) ## 5 Conclusion This paper proposes an EMGC2F model for MGC, which learns consistent clustering labels from multiple views directly and avoids time-consuming spectral decomposition in current works. Through our model, the importance and credible consistent information is captured comprehensively. An efficient discrete algorithm of O(|E| +m2 vt) time complexity is provided. Empirical results demonstrate the effectiveness and efficiency of our proposal. Besides, EMGC2F exploit credible consistent information as a constraint directly, which is the simplest way. In the future, how to use the information more flexibly and deeply may require more concern. ## Acknowledgments This work was supported in part by the National Key Research and Development Program of China under Grant 2018AAA0101902, in part by the Natural Science Basic Research Program of Shaanxi (Program No. 2021JM-071), in part by the National Natural Science Foundation of China under Grant 62176212, Grant 61936014 and Grant 61772427, and in part by the Fundamental Research Funds for the Central Universities under Grant G2019KY0501. ## References 1. [Belkin and Niyogi, 2003] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality re- duction and data representation. Neural Comput., 15(6):1373-1396, 2003. 2. [Chao et al., 2021] Guoqing Chao, Shiliang Sun, and Jinbo Bi. A survey on multi-view clustering. IEEE Trans. on Artif. Intell., 2021. 3. [Dong et al., 2014] Xiaowen Dong, Pascal Frossard, Pierre Vandergheynst, and Nikolai Nefedov. Clustering on multi- layer graphs via subspace analysis on grassmann mani- folds. IEEE Trans. Signal Process., 62(4):905-918, 2014. 4. [Dong et al., 2021] Xia Dong, Danyang Wu, Feiping Nie, Rong Wang, and Xuelong Li. Dependence-guided multi- view clustering. In ICASSP, pages 3650-3654. IEEE, 2021. 5. [Garling, 2005] D. J. H. Garling. The cauchy-schwarz master class: An introduction to the art of mathemati- cal inequalities by j. michael steele. Am. Math. Mon., 112(6):575-579, 2005. 6. [Hu et al., 2020] Zhanxuan Hu, Feiping Nie, Rong Wang, and Xuelong Li. Multi-view spectral clustering via inte- grating nonnegative embedding and spectral embedding. Inf. Fusion, 55:251-259, 2020. 7. [Huang et al., 2021] Shudong Huang, Ivor Tsang, Zenglin Xu, and Jian Cheng Lv. Measuring diversity in graph learning: A unified framework for structured multi-view clustering. IEEE Trans. Knowl. Data Eng., 2021. 8. [Kumar et al., 2011] Abhishek Kumar, Piyush Rai, and Hal Daumé III. Co-regularized multi-view spectral clus- tering. In NIPS, pages 1413-1421, 2011. 9. [Lee and Grauman, 2009] Yong Jae Lee and Kristen Grau- man. Foreground focus: Unsupervised learning from par- tially matching images. Int. J. Comput. Vis., 85(2):143- 166, 2009. 10. [Li et al., 2020] Xuelong Li, Han Zhang, Rong Wang, and Feiping Nie. Multi-view clustering: A scalable and parameter-free bipartite graph fusion method. IEEE Trans. Pattern Anal. Mach. Intell., 2020. 11. [Liu et al., 2021] Xinwang Liu, Li Liu, Qing Liao, Siwei Wang, Yi Zhang, Wenxuan Tu, Chang Tang, Jiyuan Liu, and En Zhu. One pass late fusion multi-view clustering. In ICML, volume 139 of Proceedings of Machine Learn- ing Research, pages 6850-6859. PMLR, 2021. 12. Nene et al., ] Sameer A Nene, Shree K Nayar, and Hiroshi Murase. Columbia object image library (coil-20). 13. [Nie et al., 2016] Feiping Nie, Jing Li, and Xuelong Li. Parameter-free auto-weighted multiple graph learning: A framework for multiview clustering and semi-supervised classification. In IJCAI, pages 1881-1887. IJCAI/AAAI Press, 2016. 14. [Nie et al., 2017a] Feiping Nie, Guohao Cai, and Xuelong Li. Multi-view clustering and semi-supervised classifica- tion with adaptive neighbours. In AAAI, pages 2408-2414. AAAI Press, 2017. 15. [Nie et al., 2017b] Feiping Nie, Jing Li, and Xuelong Li. Self-weighted multiview clustering with multiple graphs. In IJCAI, pages 2564-2570. ijcai.org, 2017. 16. [Nie et al., 2018] Feiping Nie, Lai Tian, and Xuelong Li. Multiview clustering via adaptively weighted procrustes. In KDD, pages 2022-2030. ACM, 2018. 17. [Reddy and Vinzamuri, 2013] Chandan K. Reddy and Bhanukiran Vinzamuri. A survey of partitional and hierarchical clustering algorithms. In Data Clustering: Algorithms and Applications, pages 87-110. CRC Press, 2013. 18. [Samaria and Harter, 1994] Ferdinand Samaria and Andy Harter. Parameterisation of a stochastic model for human face identification. In WACV, pages 138-142. IEEE, 1994. 19. [Tarjan, 1972] Robert Endre Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972. 20. [Wright, 2015] Stephen J. Wright. Coordinate descent algo- rithms. Math. Program., 151(1):3-34, 2015. 21. [Wu et al., 2020] Danyang Wu, Feiping Nie, Rong Wang, and Xuelong Li. Multi-view clustering via mixed embed- ding approximation. In ICASSP, pages 3977-3981. IEEE, 2020. 22. [Wu et al., 2021a] Danyang Wu, Zhanxuan Hu, Feiping Nie, Rong Wang, Hui Yang, and Xuelong Li. Multi-view clustering with interactive mechanism. Neurocomputing, 449:378-388, 2021. 23. [Wu et al., 2021b] Danyang Wu, Feiping Nie, Xia Dong, Rong Wang, and Xuelong Li. Parameter-free consensus embedding learning for multiview graph-based clustering. IEEE Trans. Neural Netw. Learn. Syst., 2021. 24. [Xu et al., 2013] Chang Xu, Dacheng Tao, and Chao Xu. A survey on multi-view learning. CoRR, abs/1304.5634, 2013. 25. [Zhan et al., 2018] Kun Zhan, Changqing Zhang, Junpeng Guan, and Junsheng Wang. Graph learning for multi- view clustering. IEEE Trans. Cybern., 48(10):2887-2895, 2018.