Multi-view Contrastive Graph Clustering
Year: 2021

Abstract:
With the explosive growth of information technology, multi-view graph data have become increasingly prevalent and valuable. Most existing multi-view clustering techniques either focus on the scenario of multiple graphs or multi-view attributes. In this paper, we propose a generic framework to cluster multi-view attributed graph data. Specifcally, inspired by the success of contrastive learning, we propose multi-view contrastive graph clustering (MCGC) method to learn a consensus graph since the original graph could be noisy or incomplete and is not directly applicable. Our method composes of two key steps: we frst flter out the undesirable highfrequency noise while preserving the graph geometric features via graph fltering and obtain a smooth representation of nodes; we then learn a consensus graph regularized by graph contrastive loss. Results on several benchmark datasets show the superiority of our method with respect to state-of-the-art approaches. In particular, our simple approach outperforms existing deep learning-based methods.

heading: 1 Introduction
text: An attributed graph contains of node features and edges characterizing the pairwise relations between nodes. It is a natural and effcient representation for many real-world data [Liu et al., 2021]. For example, social network users have their own profles and the topological graph refects their social relationships. Different from most classical clustering methods like K-means and hierarchical clustering which only focus on Euclidean data, graph clustering divides unlabeled nodes of graph into clusters. Typical graph clustering methods frst learn a good representation of graph and then apply a classical clustering method upon the embeddings. For example, large-scale information network embedding (LINE) [Tang et al., 2015] is a popular graph representation learning method, which can preserve both local and global information and scale up easily to large-scale networks. To incorporate node features and graph structure information, graph autoencoder (GAE) [Kipf and Welling, 2016] employs a graph convolution network (GCN) encoder and achieves signifcant performance improvement. The real-life data are often collected from various sources or obtained from different extractors, thus are naturally represented by different features or views [Kang et al., 2021, 2020c]. Each view could be noisy and incomplete, but important factors, such as geometry and semantics, tend to be shared among all views. Therefore, features and graphs of different views are complementary, which implies that it’s paramount to integrate all features and graphs of diverse views to improve the performance of clustering task. Numerous graph-based multi-view clustering methods have been developed to capture the consensus information shared by different views in the literature. Graph-based multi-view clustering constructs a graph for each view and fuses them based on a weighting mechanism [Wang et al., 2019]. Multi-view spectral clustering network [Huang et al., 2019] learns a discriminative representation by using a deep metric learning network. These methods are developed for feature matrix and can not handle graph data. To directly process graph data, some representative methods have also been proposed.
∗Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Scalable multiplex network embedding (MNE) [Zhang et al., 2018] is a scalable multi-view network embedding model, which learns multiple relations by a unifed network embedding framework. Principled multilayer network embedding (PMNE) [Liu et al., 2017] proposes three strategies (“network aggregation”, “results aggregation”, and “layer co-analysis”) to project a multilayer network into a continuous vector space. Nevertheless, they fail to explore the feature information [Lin and Kang, 2021]. Recently, based on GCN, One2Multi graph autoencoder clustering (O2MA) framework [Fan et al., 2020] and multi-view attribute GCNs for clustering (MAGCN) [Cheng et al., 2020] achieve superior performance on graph clustering. O2MA introduces a graph autoencoder to learn node embeddings based on one informative graph and reconstruct multiple graphs. However, the shared feature representation of multiple graphs could be incomplete because O2MA only takes into account the informative view selected by modularity. MAGCN exploits the abundant information of all views and adopts a cross-view consensus learning by enforcing the representations of different views to be as similar as possible. Nevertheless, O2MA targets for multiple graphs while MAGCN mainly solves graph structured data of multi-view attributes. They are not directly applicable to multiple graphs data with multi-view attributes. Therefore, the research of multi-view graph clustering is at the initial stage and more dedicated efforts are pressingly needed. In this paper, we propose a generic framework of clustering on attributed graph data with multiview features and multiple topological graphs, denoted by Multi-view Contrastive Graph Clustering (MCGC). To be exact, MCGC learns a new consensus graph by exploring the holistic information among various attributes and graphs rather than utilizing the initial graph. The reason of introducing graph learning is that the initial graph is often noisy or incomplete, which leads to suboptimal solutions [Chen et al., 2020b, Kang et al., 2020b]. A contrastive loss is adopted as regularization to make the consensus graph clustering-friendly. Moreover, we implement on the smooth representation rather than raw data. The contributions of this work could be summarized as follows:
• To boost the quality of learned graph, we propose a novel contrastive loss at graph-level. It is capable of drawing similar nodes close and pushing those dissimilar ones apart.
• We propose a generic clustering framework to handle multilayer graphs with multi-view attributes, which contains graph fltering, graph learning, and graph contrastive components. The graph fltering is simple and effcient to obtain a smoothed representation; the graph learning is utilized to generate the consensus graph with an adaptive weighting mechanism for different views.
• Our method achieves state-of-the-art performance compared with shallow methods and deep methods on fve benchmark datasets.

heading: 2 Related Work

heading: 2.1 Multi-view Clustering
text: Large quantities of multi-view clustering methods have been proposed in the last decades. Multi-view low-rank sparse subspace clustering [Brbić and Kopriva, 2018] obtains a joint subspace representation across all views by learning an affnity matrix constrained by sparsity and low-rank constraint. Cross-view matching clustering (COMIC) [Peng et al., 2019] enforces the graphs to be as similar as possible instead of the representation in the latent space. Robust multi-view spectral clustering (RMSC) [Xia et al., 2014] uses a shared low-rank transition probability matrix derived from each single view as input to the standard Markov chain method for clustering. These methods are designed for feature matrix and try to learn a graph from data. To directly cluster multiple graphs, self-weighted multi-view clustering (SwMC) [Nie et al., 2017] method learns a shared graph from multiple graphs by using a novel weighting strategy. Above methods are suitable for graph or feature data only, and can not simultaneously explore attributes and graph structure. As previously discussed, O2MA [Fan et al., 2020] and MAGCN [Cheng et al., 2020] can handle attributed graph, but they are not direct applicable to generic multi-view graph data.

heading: 2.2 Contrastive Clustering
text: Due to its impressive performance in many tasks, contrastive learning has become the most hot topic in unsupervised learning. Its motivation is to maximize the similarity of positive pairs and
H> − H>S 2 2min + α kSkF , FS
distance of negative pairs [Hadsell et al., 2006]. Generally, the positive pair are composed of data augmentations of the same instance while those of different instances are regarded as negatives. Several loss functions have been proposed, such as the triplet loss [Chopra et al., 2005], the noise contrastive estimation (NCE) loss [Gutmann and Hyvärinen, 2010], the normalized temperature-scaled cross entropy loss (NT-Xent) [Chen et al., 2020a]. Deep robust clustering turns maximizing mutual information into minimizing contrastive loss and achieves signifcant improvement after applying contrastive learning to decrease intra-class variance [Zhong et al., 2020]. Contrastive clustering develops a dual contrastive learning framework, which conducts contrastive learning at instance-level as well as cluster-level [Li et al., 2021]. As a result, it produces a representation that facilitates the downstream clustering task. Unfortunately, theses method can only handle single-view data. Recently, by combining reconstruction, cross-view contrastive learning, and cross-view dual prediction, incomplete multi-view clustering via contrastive prediction (COMPLETER) [Lin et al., 2021a] performs data recovery and consistency learning of incomplete multi-view data simultaneously. It also obtains promising performance on complete multi-view data. However, it can not deal with graph data. On the other hand, contrastive multi-view representation learning on graphs (MVGRL) [Hassani and Khasahmadi, 2020] method is proposed, which performs representation learning by contrasting two diffusion matrices transformed from the adjacency matrix. It reports better performance than variational GAE (VGAE) [Kipf and Welling, 2016], marginalized GAE (MGAE) [Wang et al., 2017], adversarially regularized GAE (ARGA) and VGAE (ARVGA) [Pan et al., 2018], and GALA [Park et al., 2019]. Different from MVGRL, our contrastive regularizer is directly applied on learned graph.

heading: 3.1 Notation
text: Defne the multi-view graph data as G = {V, E1, ..., EV , X1, ..., XV }, where V represents the sets of N nodes, eij ∈ Ev denotes the relationship between node i and node j in the v-th view,
v vXv = {x1 , ..., x }> is the feature matrix. Adjacency matrices {Aev}V characterize the initial N v=1 graph structure. {Dv}V represent the degree matrices in various views. The normalized adjacency
3 Methodology
1 v=1 matrix Av = (Dv )− 2 (Aev + I)(Dv )− 1 2 and the corresponding graph laplacian Lv = I − Av .

heading: 3.2 Graph Filtering
text: A feature matrix X ∈ RN×d of N nodes can be treated as d N -dimensional graph signals. A natural signal should be smooth on nearby nodes in term of the underlying graph. The smoothed signals H can be achieved by solving the following optimization problem [Zhu et al., 2021, Lin et al., 2021b]�
min kH − Xk2 F + s Tr H>LH , H
(1)
where s > 0 is a balance parameter and L is the laplacian matrix associated with X . H can be obtained by taking the derivative of Eq. (1) w.r.t. H and setting it to zero, which yields
H = (I + sL)−1X. (2) To get rid of matrix inversion, we approximate H by its frst-order Taylor series expansion, i.e., H = (I − sL)X . Generally, m-th order graph fltering can be written as
H = (I − sL)mX, (3) where m is a non-negative integer. Graph fltering can flter out undesirable high-frequency noise while preserving the graph geometric features.

heading: 3.3 Graph Learning
text: Since real-world graph is often noisy or incomplete, which will degrade the downstream task performance if it is directly applied. Thus we learn an optimized graph S from the smoothed representation H . This can be realized based on the self-expression property of data, i.e., each data point can be represented by a linear combination of other data samples [Lv et al., 2021, Ma et al., 2020]. And the combination coeffcients represent the relationships among data points. The objective function on single-view data can be mathematically formulated as
(4)
⎪ P⎪ V n exp (t−1)S⎨ λv −1 + ij , j v, K(t− 1) if in Ni (t) r = v=1 2 (t−1) ⎪ V P ⎩⎪ n exp S λv ij , otherwise . K(t−1)
v=1
V NX X X2 exp (Sij )min λv ⎝ Hv> − Hv>S + α − log ⎠ . F PNS exp (Sip)v=1 i=1 j∈Nv p= ii
⎛ ⎞ V N VX X X X2 exp (Sij ) γmin λv ⎝ Hv> − Hv>S + α − log ⎠ + (λv) . F PNS,λv exp (Sip)v=1 i=1 j∈Nv p= i v=1i
NX X exp (Sij )J = − log PN , exp (Sip)i=1 j∈Nv p= ii
V VX X2 γmin λv Hv> − Hv>S + αkSk2 + (λv) , FFS,λv v=1 v=1
where S ∈ RN×N is the graph matrix and α > 0 is the trade-off parameter. The frst term is the reconstruction loss and the second term serves as a regularizer to avoid trivial solution. Many other regularizers could also be applied, such as the nuclear norm, sparse ` 1 norm [Kang et al., 2020a]. To tackle multi-view data, we can compute a smooth representation Hv for each view and extend Eq. (4) by introducing a weighting factor to distinguish the contributions of different views
(5)
where λv is the weight of v-th view and γ is a smooth parameter. Eq. (5) learns a consensus graph S shared by all views. To learn a more discriminative S, we introduce a novel regularizer in this work.

heading: 3.4 Graph Contrastive Regularizer
text: Generally, contrastive learning is performed at instance-level and positive/negative pairs are constructed by data augmentation. Most graph contrastive learning methods conduct random corruption on nodes and edges to learn a good node representation. Different from them, each node and its k-nearest neighbors (kNN) are regarded as positive pairs in this paper. Then, we perform contrastive learning at graph-level by applying a contrastive regularizer on the graph matrix S instead of node features. It can be expressed as
(6) 6
where Nv represents the k-nearest neighbors of node i in v-th view. The introduction of Eq. (6) is toi draw neighbors close and push non-neighbors apart, so as to boost the quality of graph. Eventually, our proposed multi-view contrastive graph clustering (MCGC) model can be formulated as
(7) 6
Different from existing multi-view clustering methods, MCGC explores the holistic information from both multi-view attributes and multiple structural graphs. Furthermore, it constructs a consensus graph from the smooth signal rather than the raw data.

heading: 3.5 Optimization
text: There are two groups of variables in Eq. (7) and it’s diffcult to solve them directly. To optimize them, we adopt an alternating optimization strategy, in which we update one variable and fx all others at each time. Fix λv , Update S Because λv is fxed, our objective function can be expressed as⎛ ⎞
(8) 6
S can be elemently solved by gradient descent and its derivative at epoch t can be denoted as (t) (t)r + αr . 1 2 (9) The frst term is V X h i
λv Hv Hv> Hv Hv>S(t−1)r(t) = 2 − + . 1 ij
(10)
ij v=1
Defne N (t−1) K(t−1) = p=i exp Sip and let n be the total number of neighbors (i.e., the neighbors from each graph are all incorporated). Consequently, the second term becomes⎧
P
(11)
6
1 γ−1−Mv
λv = . γ
Then we adopt Adam optimization strategy [Kingma and Ba, 2015] to update S. To increase the speed of convergence, we initialize S with S∗ , where S∗ is the solution of Eq. (5). Fix S, Update λv 2 For each view v, we defne Mv = Hv> − Hv>S + αJ . Then, the loss function is simplifed as
F V VX X λvMv
γ min + (λv) . λv
v=1 v
(12)
By setting its derivation to zero, we get
(13)
We alternatively update S and λv until convergence. The complete procedures are outlined in Algorithm 1.
Algorithm 1 MCGC Require: adjacency matrix Ae1 ,...,AeV , feature X1 ,...,XV , the order of graph fltering m, parameter
α, s and γ, the number of clusters c. Ensure: c clusters.
1: λv = 1; 2: Av = (Dv)− 1 2 (Aev + I)(Dv)− 12 ; 3: Lv = I − Av; 4: Graph fltering by Eq. (4) for each view; 5: while convergence condition does not meet do 6: Update S in Eq. (9) via Adam; 7: for each view do 8: Update λv in Eq. (13); 9: end for
10: end while (|S|+|S|>)11: C = ;2 12: Clustering on C.

heading: 4 Experiments

heading: 4.1 Datasets and Metrics
text: We evaluate MCGC on fve benchmark datasets, ACM, DBLP, IMDB [Fan et al., 2020], Amazon photos and Amazon computers [Shchur et al., 2018]. The statistical information is shown in Table 1. ACM: It is a paper network from the ACM dataset. Node attribute features are the elements of a bag-of-words representing of each paper’s keywords. The two graphs are constructed by two types of relationships: "Co-Author" means that two papers are written by the same author and "Co-Subject" suggests that they focus on the same fled. DBLP: It is an author network from the DBLP dataset. Node attribute features are the elements of a bag-of-words representing of each author’s keywords. Three graphs are derived from the relationships: "Co-Author", "Co-Conference", and "Co-Term", which indicate that two authors have worked together on papers, published papers at the same conference, and published papers with the same terms. IMDB: It is a movie network from the IMDB dataset. Node attribute features correspond to elements of a bag-of-words representing of each movie. The relationships of being acted by the same actor (Co-actor) and directed by the same director (Co-director) are exploited to construct two graphs. Amazon photos and Amazon computers: They are segments of the Amazon co-purchase network dataset, in which nodes represent goods and features of each good are bag-of-words of product reviews, the edges means that two goods are purchased together. To have multi-view attributes, the second feature matrix is constructed via cartesian product by following [Cheng et al., 2020]. We adopt four popular clustering metrics: Accuracy (ACC), normalized Mutual Information (NMI), Adjusted Rand Index (ARI), F1 score.

heading: 4.2 Experiment Setup
text: We compare MCGC with multi-view methods as well as single-view methods. LINE [Tang et al., 2015] and GAE [Kipf and Welling, 2016] have been chosen as representatives of single-view methods, and we report the best one among the results from all views. Compared multi-view clustering methods include: PMNE [Liu et al., 2017], RMSC [Xia et al., 2014], SwMC [Nie et al., 2017]. PMNE and SwMC only use structural information while RMSC only exploits attribute features. PMNE uses three strategies to project a multilayer network into a continuous vector space, so we select the best result. MCGC is also compared with other methods that not only explore attribute features but also structural information, i.e., O2MA and O2MAC [Fan et al., 2020], MAGCN [Cheng et al., 2020]. In addition, MCGC is compared with COMPLETER [Lin et al., 2021a] and MVGRL [Hassani and Khasahmadi, 2020] that conduct contrastive learning to learn a common representation shared across features of different views and multiple graphs respectively. For an unbiased comparison, we copy part of the results from [Fan et al., 2020]. Since the neighbors of each node on different views could be different, we also examine another strategy: only use the shared neighbors in the contrastive lossTVterm, Ni = Niv . And our method with this approach is marked as MCGC*. During experiments, v=1 k = 10 is used to select neighbors and γ is fxed as −4 since we fnd that it has little infuence to the result. According to parameter analysis, we set m = 2, s = 0.5, and tune α. All experiments are conducted on the same machine with the Intel(R) Core(TM) i7-8700 3.20GHz CPU, two GeForce GTX 1080 Ti GPUs and 64GB RAM. The implementation of MCGC is public available 1.

heading: 4.3 Results
text: All results are shown in Table 2 and Table 3. Compared with single-view method GAE, MCGC improves ACC by more than 9%, 4%, 19% on ACM, DBLP, IMDB, respectively. Though using deep neural networks, GAE can not explore the complementarity of views. Compared with PMNE, the ACC, NMI, ARI, F1 are boosted by 16%, 20%, 20%, 12% on average. With respect to LINE, RMSC, SwMC, the improvement is more signifcant. This can be attributed to the exploration of both feature and structure information in MCGC. Although O2MA, O2MAC, and MAGCN capture attributes and structure information, MCGC still outperforms them considerably. Specifcally, MCGC improves O2MAC on average by almost 6%, 9%, 11% on ACC, NMI, F1, respectively. With respect to MAGCN, the improvement is more than 20% for all metrics. Compared with contrastive learningbased approaches, our improvement is also impressive. In particular, compared with COMPLETER, the improvement is more than 30% on Amazon datasets, which illustrates that MCGC benefts from the graph structure information. MCGC also enhances the performance of MVGRL by 20%. By comparing the results of MCGC and MCGC*, we can see that the strategy of choosing neighbors does have impact on performance.
1https://github.com/Panern/MCGC

heading: 5 Ablation Study

heading: 5.1 The Effect of Contrastive Loss
text: By employing the contrastive regularizer, our method pulls neighbors into the same cluster, which decreases intra-cluster variance. To see its effect, we replace J with a Frobenius term, i.e. Eq. (5). As can be seen from Table 4, the performance falls precipitously without contrastive loss on all datasets. MCGC achieves ACC improvements by 16%, 8%, 5%, 12% on DBLP, ACM, IMDB, Amazon datasets, respectively. For other metrics, the contrastive regularizer also enhances the performance signifcantly. Above facts validate that MCGC benefts from the graph contrastive loss.

heading: 5.2 The Effect of Multi-View Learning
text: To demonstrate the effect of multi-view learning, we evaluate the performance of the following single-view model
NX X2 exp(Sij ) min H> − H>S + α − log . (14)
F NS X i=1 j∈Ni exp(Sip)
p6=i
Taking ACM and Amazon photos as examples, we report the clustering performance of various scenarios in Table 5. We can observe that the best performance is always achieved when all views are incorporated. In addition, we also see that the performance varies a lot for different views. This justifes the necessity of λv in Eq. (7). Therefore, it is benefcial to explore the complementarity of multi-view information.

heading: 5.3 The Effect of Graph Filtering
text: To understand the contribution of graph fltering, we conduct another group of experiments. Without graph fltering, our objective function becomes ⎛ ⎞
V N VX X X X2 exp (Sij ) γ min λv ⎝ Xv> − Xv>S + α − log ⎠ + (λv ) . (15)
F PNS,λν exp (Sip)v=1 i=1 j∈Nv p=6 i v=1i We denote this model as MCGC-. The results of MCGC- are shown in Table 6. With respect to MCGC, ACC on ACM, DBLP, IMDB drops by 0.8%, 1.3%, 0.8%, respectively. This indicates that graph fltering makes a positive impact on our model. For other metrics, MCGC also outperforms MCGC- in most cases.

heading: 6 Parameter Analysis
text: Firstly, two parameters m and s are applied in graph fltering. Taking ACM as an example, we show their infuence on performance by setting m = [1, 2, 3, 4, 5], s = [0.01, 0.1, 0.3, 0.5, 1, 3, 5, 10] in Fig. 1. It can be seen that MCGC achieves a reasonable performance for a small m and s.
Therefore, we set m = 2 and s = 0.5 in all experiments. Afterwards, we tune the trade-off parameter α = [10−3 , 0.1, 1, 10, 102 , 103]. As shown in Fig. 2, our method is not sensitive to α, which enhances the practicality in real-world applications. In addition, we plot the objective variation of Eq. (7) in Fig. 3. As observed from this fgure, our method converges quickly.

heading: 7 Conclusion
text: Multi-view graph clustering is till at a nascent stage with many challenges remained unsolved. In this paper, we propose a novel method (MCGC) to learn a consensus graph by exploiting not only attribute content but also graph structure information. Particularly, graph fltering is introduced to
flter out noisy components and a contrastive regularizer is employed to further enhance the quality of learned graph. Experimental results on multi-view attributed graph datasets have shown the superior performance of our method. This study demonstrates that it is possible for shallow model to beat deep learning methods facing the systematic use of complex deep neural networks. Graph learning is crucial to more and more tasks and applications. Just like other methods that learn from data, brings the risk of learning biases and perpetuating them in the form of decisions. Thus our method should be deployed with careful consideration of any potential underlying biases in the data. One potential limitation of our approach is that it could take a lot of memory if the data contain too many nodes. This is because the size of learned graph is N × N . Research on large scale network is left for future work.
Acknowledgments and Disclosure of Funding
This paper was in part supported by the Natural Science Foundation of China (Nos.61806045, U19A2059).

Review summaries:
This paper proposes a multi-view clustering method. They first use graph filter to generate a new node representation for input, and then do self-expression in a linear combination of various views. Afterwards, they propose a graph contrastive regularizer, which mimics the contrastive learning given the nearest neighbors as positive samples and any others as negative ones. Experiments compared with recent works and ablation studies are presented.

This paper considers the multiview graph clustering problem where the goal is to find a cluster given multiple networks. The paper integrates the self-expression strategy and contrastive learning mechanism into a unified framework to perform graph learning. Besides, graph filtering is designed to recover a clean data in advance. An optimization algorithm is developed to solve the objective function. The paper compares the effectiveness of their method with other deep methods and demonstrates that the proposed method is competitive and promising.