EMGC²F: Efficient Multi-view Graph Clustering with Comprehensive Fusion

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:

• 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.

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.

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.

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.

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.