Multi-level Graph Contrastive Prototypical Clustering

1 Introduction

As one of the most fundamental tasks in graph analysis, clustering divides nodes into different groups in absence of label annotations [Wang et al., 2022b; Li et al., 2020]. Recently, unsupervised graph representation learning based on GNNs [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Hamilton et al., 2017] has provoked tremendous interest and shown promising capability for graph clustering [Park et al., 2019; Zhu et al., 2021]. In the existing literature, their approaches can be roughly divided into two categories, i.e., generative and contrastive graph clustering.

Generative methods prevalently resort to reconstruction objectives, which generate self-supervised information for representation learning. Following the auto-encoder paradigm, GAE [Kipf and Welling, 2016] first leverages to reconstruct the adjacency matrix. Inspired by adversarial mechanism, ARGA [Pan et al., 2018] derives to refine the latent representations by discriminating real or fake samples. After that, DAEGC [Wang et al., 2019] utilizes Kullback-Leibler divergence to simultaneously learn representations and find a better cluster-friendly space. Furthermore, DFCN [Tu et al., 2021] considers multi-level features in a fusion manner. On the contrary, contrastive methods currently maximize agreements across views from an information theory perspective. DGI [Velickovic et al., 2019] maximizes the mutual information (MI) between node representations and the global summary. MVGRL [Hassani and Khasahmadi, 2020] augments and contrasts with PageRank algorithm [Gasteiger et al., 2018]. Inspired by Barlow Twins [Zbontar et al., 2021], AGC-DRR [Gong et al., 2022] reduces redundant information with an edge weight learner most recently.

∗Corresponding author.

Despite empirical successes have witnessed advances of deep clustering, there exist following drawbacks to be addressed. (1) Many generative or contrastive methods [Kipf and Welling, 2016; Gong et al., 2022] leverage shallow GNNs to avoid the over-smoothing and over-squashing phenomena [Keriven, 2022; Topping et al., 2022]. However, semantic information as global knowledge is seldomly investigated, which thus theoretically is inclined to semantic-agnostic for graph clustering. Specifically, informative inner-class nodes in graphs generally scatter beyond one-hop neighbors, which benefits the downstream tasks. Generative methods based on reconstruction objectives excessively emphasize local neighbors by direct connections, which presumably even deteriorates the clustering performance. Contrastive methods also perceive limited global semantic information with shallow encoders and their objectives [Chen et al., 2020] purely conjecture the rest of nodes are negatives, which simply pushes all the other nodes away, causing the sampling bias problem in Figure 1. (2) Some deep clustering approaches, such as SDCN [Bo et al., 2020] and DFCN [Tu et al., 2021] simultaneously consider multiple objectives in a fusion manner to explore multi-level information. Nevertheless, they impose objectives constraints within the same latent space regardless of whether representations have different granularities or not. This thus induces the conflict and presumably hinders optimization, leading serve performance degradation with laborious hyper-parameter searching and balancing.

In this paper, we introduce a novel Multi-Level Graph Contrastive Prototypical Clustering (MLG-CPC) to tackle aforementioned issues. Our goals include (1) optimizing representations of different granularities at multiple levels and (2) capturing semantic structures to explore the global information. To be specific, we first leverage encoders to distill feature representations from raw data, and then generate highlevel semantic prototypes and clusters in sequence via projection heads as well as predictors on low-level yet fundamental feature representations. Concurrently, for representations of different granularities, we propose distinct optimization objectives within their respective spaces. Specifically, to facilitate the representation learning within high-level space, we constrain feature representations within feature-level space to be augmentation-invariant and non-degenerate. Then the distilled representations are transformed and mapped into prototypical-level space via projection heads. After that, prototypes are generated via cluster assignments for semantic exploitation by formulating a new Prototype Discrimination (ProDisc) loss function, which gathers and disperses prototypes between inter- and inner-views. Furthermore, we render output units of our cluster predictors to be identical with the amount of classes, generating the cluster assignments within cluster-level space. And the consistency of obtained cluster assignments across views can be constrained by NTXent [Chen et al., 2020]. Overall, the features, prototypes, and clusters are individually optimized within their respective spaces, benefiting from each other and generating more promising representations for clustering. Our contributions are as follows:

• We propose a multi-level graph contrastive clustering method (MLG-CPC), which can simultaneously percieve representations of different granularities and conduct clustering in an end-to-end manner.
• To explore and exploit semantic knowledge, a Prototype Discrimination (ProDisc) objective function is derived on prototypes via cluster assignments.
• MLG-CPC optimizes different level of representations within individual spaces, avoiding laborious hyperparameter searching to balance multiple objectives.
• Extensive experiments on four benchmarks demonstrate that the proposed MLG-CPC outperforms state-of-theart graph clustering approaches.

2 RelatedWork

2.1 Deep Graph Clustering

Different from traditional graph clustering approaches such as probabilistic and matrix decomposition, deep graph clustering based on GNNs has received tremendous interest and advances by virtue of deep learning. Inspired by variation Bayes inference, GAE [Kipf and Welling, 2016] as the earliest deep clustering method leverages reconstruction objectives to reserve the graph structure. Following that, ARGA [Pan et al., 2018] proposes to discriminate true or false samples from latent space with adversarial training. DAEGC [Wang et al., 2019] simultaneously learns representations and finds a cluster-friendly space inspired by DEC [Xie et al., 2016]. DFCN [Tu et al., 2021] and SDCN [Bo et al., 2020] both leverage more information from different views combined with DEC [Wang et al., 2019], enhancing the quality of representations in a fusion manner. GALA [Park et al., 2019] utilizes graph Laplacian sharpening to design a symmetric framework, further boosting the clustering performance. DGI [Velickovic et al., 2019] adapts the idea of InfoMax into the graph domain, which maximizes the agreement between nodes and the global summary. MVGRL [Hassani and Khasahmadi, 2020] proposes to augment graphs with PageRank algorithm [Gasteiger et al., 2018] and maximizes the MI across views based on multi-view learning. Most recently, AGC-DRR [Gong et al., 2022] proposes an adversarial edge leaner, which reduces redundant information across views benefitted from Barlow Twins [Zbontar et al., 2021]. Albeit above approaches ameliorate graph clustering from various perspectives, methods such as DFCN and SDCN optimize different objectives and then fuse within the same space. Nevertheless, representations of different granularities may conflict with each other, thus requiring laborious parameters searching and balancing. Meanwhile, most approaches do not take global semantic structures into consideration, which is harmful for graph clustering.

2.2 Semantic Structures in Contrastive Learning

Prototypes can model the class semantic information, which are widely applied to few-shot learning [Snell et al., 2017]. Different from limited yet available labels in few-shot learning, there is no annotations in unsupervised scenarios. PCL [Li et al., 2021] proposes prototypical contrastive learning for images with Expectation-Maximization algorithms, which performs node-prototype interaction to improve the quality of image representations. However, this is theoretically non-trivial for graphs due to their assumptions, where images follow the independently and identically distributed (IID) hypothesis [Yuan et al., 2018; Liu et al., 2022; Wang et al., 2022a] while nodes in graphs manifest strong intrinsic dependences by edges. Similarly, SwAV [Caron et al., 2020] simultaneously learns representations and cluster assignments by extending the idea of deepCluster [Caron et al., 2018], while they still omit multi-level information. For graphs semantic exploitation, GraphLog [Xu et al., 2021] generates hierarchical prototypes and performs instance-prototype alignment. PGCL [Lin et al., 2022] extends the SwAV for graph domain, improving the representations of molecules.

Nonetheless, these approaches are devised for graph-level and are task-agnostic. Our MLG-CPC is for end-to-end clustering and posses different motivations with distinct objectives. Moreover, these methods adopt cosine similarities to compute the cluster probabilities whereas our method can directly obtain the class assignments by virtue of end-to-end architecture and cluster space, which may shed light upon multi-view graph clustering for further investigations.

3 Methodology

Given a graph, we initially augment this original graph with graph augmentations to produce two different views. Then the augmented graphs are first transformed into H via message passing encoders fθ, which are then projected by the projection head gθ to generate Z and construct prototypes M. Finally, we leverage cluster predictors kθ to learn assignments P and statistic matrix Q. Three distinct losses are formulated and optimized at different levels on H, M, P, and Q with respective feature-, prototypical-, and cluster-level spaces. The framework of our MLG-CPC is illustrated in Figure 2.

3.1 Notations and ProblemDefinitions

Let an attributed graph G = {V,A,X}, where nodes set V = {v1, v2, . . . , vN} associated with edges. The structure of G can be defined by an adjacency matrix A ∈ RN×N . Nodes with features can be denoted as X ∈ RN×D . I ∈ RD×D is the identity matrix. And lower case of the matrix denotes vectors. The goal of graph clustering is to separate the nodes into different clusters without requiring any annotations. The concrete notations are encapsulated in Table 1.

3.2 Message Passing and Graph Augmentations

Encoders Based on Message Passing. Following the message passing neural network (MPNN) [Gilmer et al., 2017], we update the node by transporting messages of it and its neighbors, which can be defined as:

where N(v) denotes the neighbors representations of node v. MESSAGEk is the message function at layer k, which should be permutation invariant. hkN(v) ∈ R1×d denotes messages of neighbors gathered by node v. UPDATES operator updates the node. Wk ∈ RD×d is the transformation matrix at layer k. hkv is the updated node v at layer k and h0v = xv . For simplicity, we set the MESSAGEk and UPDATES to be mean operation. Then the encoder can be represented as:

By this means, we locally generate feature representations H into feature-level space from raw data X and A. For global semantic exploration, we will detail it in section 3.3.

Graph Augmentations. Following the multi-view contrastive learning paradigm, we resort to contrasting across views and adopt two widely used graph augmentations techniques, edge dropping and feature masking, which augment graphs from perspectives of structures and features. Specifically, for edge dropping, we randomly drop a portion of edges in graphs by a mask matrix R ∈ {0, 1}N×N , whose elements are produced via Bernoulli distribution with probability ri for generating view i ∈ {A, B}, which can be defined as:

where ◦ is Hadamard product. For feature masking, we define an indicator m ∈ {0, 1}d×1 with probability mi for assigning 0 to features, and then mask a portion of the node features for generating view i ∈ {A, B}, which can be computed as:

Note that different from previous approaches [Xia et al., 2022], which set distinct value for two views, we set identical values for two views to draw them from the same distribution.

3.3 Multi-Level Graph Clustering

Feature Orthogonality with Invariance. Given the representations H of a graph, we formulate the feature distillation problem within feature-level space inspired by W-MSE [Ermolov et al., 2021], which is represented as:

where dist denotes the mean squared error, i.e., the L2 distance, and cov is the covariance measurement between variables across views. Different fromW-MSE whitens the embedding for implicitly satisfying the condition, we tackle this problem by via Lagrangian multiplier, so Lfl is computed as:

where the first term renders representations across views to be invariant to augmentations, capturing the permutation invariant information. The second term encourages different features in the same view to be orthogonal, minimizing correlation of features within views. λ is a parameter to balance the objective and conditions.

Prototypical-level Contrast. SimCLR [Chen et al., 2020] adopts instance discrimination strategy, which is semanticagnostic. We explore and regard prototypes as globally semantic structures and propose to conduct discrimination on prototypical-level. Specifically, we adopt Multi-Layer Perceptions (MLPs) as projection heads gθ within prototypicallevel space. The prototypes constructed by cluster assignments generated by cluster predictors, formally, we calculate prototypes for each cluster as follows:

where z ∈ R1×d is the output by projection heads based on h, and p(k | z) is the cluster assignment generated by predictors, which will be detailed in section 3.3.3. Cluster assignments indicate the node belong to certain cluster k. Then we define our ProDisc loss for one pair as:

where θ (, ) /τ is the cosine similarity with temperature parameter. Φ sums total negative sample pairs from inter or intra perspectives and K is the number of classes. Thus, the denominator can disperse negative prototypes pairs from different views and the same views:

Then we calculate the loss for all pairs symmetrically, so the overall ProDisc loss of prototypical-level is:

the prototype discrimination interacts globally from the semantic perspective, alleviating sampling bias to some extent. Moreover, similar to contrastive algorithms, this loss is theoretically coherent with [Wang and Isola, 2020], where the positive prototype pair encourages the alignment and negative prototype pairs guarantee the uniformity.

Cluster Space Consistency. Consequently, we formulate our cluster predictors kθ via MLPs followed by softmax activation. The units of predictor are equal to the amount of classes K. By this way, our model can predict nodes cluster assignments Pi ∈ RN×K of two views based on Zi . To constrain the consistency of two cluster distributions, we adopt the idea of cross-entropy and leverage a more flexible variant of it [Chen et al., 2020], which is defined as:

we calculate the loss for all pairs symmetrically, so the assignments consistency loss is:

In addition, we regard column pi of P as the cluster statistics vectors qi, and further constrain the consistency between them for stability, which is denoted as:

Algorithm 1 The training procedure of MLG-CPC

Input: Graph G = {V,A,X}; The number of clusters K; Maximum iterations T; Edge dropping rates ri and feather masking rates mi; Hyper-parameter λ.

Output:The clustering results.

• 1: for i = 1 to T do
• 2: Obtain GB via Eq.(4) and Eq.(5) augmentations.
• 3: Calculate feature HA and HB via Eq.(3).
• 4: Calculate representations µA and µB via Eq.(8).
• 5: Calculate assignments pA and pB by predictor.
• 6: Calculate statistics qA and qB by transposition.
• 7: Calculate Lfl, Lpl, and Lcl, respectively.
• 8: Update MLG-CPC via minimizing Eq.(18).
• 9: end for
• 10: Calculate clustering results via the clustering assignments P1 and P2.
• 11: return The clustering results.

and we calculate the loss for all pairs symmetrically, so the statistic consistency loss is:

here, the overall cluster-level consistency loss is:

3.4 Objective Function

We separately formulate different levels of representations within their own space, avoiding the objectives conflict issue. We do not need specific hyper-parameter tuning to balance the different objectives [Liu et al., 2023], thus keeping importance of each objective identical. The total objective function of our MLG-CPC is denoted as:

Feature representations are distilled by feature orthogonality in feature-level space, and then contribute to generating accurate prototypes within prototypical-level space. Consequently, representations refined by prototype discrimination are further optimized via cluster-level consistency. Lastly, we average cluster assignments from two views as labels output by our MLG-CPC for evaluation testing. The procedure of MLG-CPC is illustrated in Algorithm 1.

4 Experiments

In following sections, we first introduce experimental setups. Second, we conduct extensive experiments of graph clustering and verify the effectiveness of different sub-modules. After that, we investigate the influence of different graph augmentation strategies. Finally, the learned representations and similarity matrices are visualized for display intuitively.

4.1 Datasets

We adopt four commonly used graph datasets [Shchur et al., 2018] in our experiments including CITE, ACM, DBLP, and AMAP. Each dataset contains an adjacency matrix and a feature matrix. Concrete descriptions of these datasets are illustrated in Table 2.

4.2 Experiment Setup

ImplementationDetails. We implement ourMLG-CPCon PyTorch platform and Deep Graph Library (DGL) 1 with the NVIDIA GeForce RTX 3090. Our encoders and prototype projection heads are shared graph convolutional networks (GCNs) and MLPs, respectively. Also, we leverage one-layer MLP followed by softmax to construct cluster predictors.

Parameters Settings. For all datasets, we set the learning rate at 1e-3, τ at 0.2, and λ at 5e-4. We use grid-search to find the optimal graph augmentation parameters, i.e., edge dropping and feature masking rates ranging from 0 to 1. We will analyse these two parameters in the following section. The training procedure of MLG-CPC is optimized until reaching max epochs. We set max epochs at 40, 200, 400, 1000 for CITE, AMAP, ACM, and DBLP, respectively. We report the average mean scores and standard deviation of 10 times running. For other baselines, we follow and directly compare the results reported in AGC-DRR [Gong et al., 2022].

Evaluation Metrics. In our graph clustering experiments, the Accuracy (ACC), Normalized Mutual Information (NMI), adjusted rand index (ARI), and F1-score (F1) [Tu et al., 2021; Bo et al., 2020] are presented for evaluation.

4.3 Clustering Results

Comparison Methods. To demonstrate the validity of our MLG-CPC, we compare with 12 clustering methods. Kmeans [Hartigan and Wong, 1979] as one of the most classic algorithm can cluster data into different groups. AE [Yang et al., 2017] follows the auto-encoder paradigm to perform clustering. DEC [Xie et al., 2016] and IDEC [Guo et al., 2017] further enhance the AE with co-clustering mechanism, GAE/VGAE [Kipf and Welling, 2016] and DAEGC [Wang et al., 2019] extends the idea of AE to the graph domain. ARGA [Pan et al., 2018] combines adversarial networks with GAE. SDCN [Bo et al., 2020] and DFCN [Tu et al., 2021] integrate the representations of AE and GAE in a fusion manner. MVGRL [Hassani and Khasahmadi, 2020] adopts the MI maximization and Pagerank to improve the quality of representations. AGC-DRR [Gong et al., 2022] devises a edge learner for more robust clustering.

We present the graph clustering results in Table 3. Compared with the first three methods, our MLG-CPC consistently outperforms them by a large margin. These methods do not utilize the graph topological information though they are effective for tackling non-graph data such as images and tabular samples. Compared with generative graph clustering algorithms such as GAE [Kipf and Welling, 2016], ARGA [Pan et al., 2018], DAEGC [Wang et al., 2019], which pursue reconstruction for optimization. From the table, we can see MLG-CPC outperforms DAEGC [Wang et al., 2019], a stateof-the-art generative graph clustering algorithm, by 6.26%, 20.08%, 4.77%, 3.21% on ACM, DBLP, CITE, and AMAP datasets in terms of ACC evaluation, respectively. Meanwhile, compared with contrastive and fusion-fashion graph clustering methods such as MVGRL [Hassani and Khasahmadi, 2020], AGC-DRR [Gong et al., 2022], and DFCN [Tu et al., 2021], our method perceives multi-level optimization, and different granularities of representations facilitate each other to some degree. Moreover, MLG-CPC takes global semantic structures into consideration and optimizes different objectives with distinct spaces, whereas these methods still omits the semantic knowledge and might be risk of objectives optimization conflict issues. Overall, aforementioned clustering performance observations have demonstrated the effectiveness of our MLG-CPC for graph clustering.

1 https://www.dgl.ai/

4.4 Ablation Study

In this section, we analyse different components of MLGCPC and results are presented in Table 4. As we can observe, the MLG-CPC w/o feature-level leads to severe degradation. Taking results on AMAP for example, our MLG-CPC exceeds the MLG-CPC w/o feature-level loss by 5.65%, 4.75%, 11.46%, 4.42% performance increment in terms of ACC, NMI, ARI and F1, which demonstrates the low-level yet fundamental feature representations are crucial for the high-level spaces. The MLG-CPC w/o prototypical-level loss also is inferior to the MLG-CPC, showing that the global prototypical information can benefit the model training. Besides, since the cluster loss plays essential role in our end-to-end framework, when we remove this sub-module, our MLG-CPC sharply degrades a lot, specifically, by 11.89%, 10.72%, 17.46%, 8.22% performance decrement with respect to ACC, NMI, ARI and F1, due to poor labels generated for clustering.

4.5 Parameters Analysis

Graph augmentations play vital roles in multi-view graph learning. To this end, we investigate the influence of different augmentation strategies for our MLG-CPC framework in

0.8

0.8

Figure 3: Graph augmentations with different edge dropping and feature masking rates on the DBLP dataset.

Figure 3, i.e., the edge dropping rate (E) and feature masking rate (F) with different probabilities, ranging from 0 to 1. Since NMI, ARI, and F1-score have similar trends with ACC from our experiments, we only present the ACC value correspond to DBLP dataset due to the space limitations, and results of ACC, NMI, ARI and F1 values on all four datasets can be found in supplementary files.

We can see our MLG-CPC is stable for most parameters settings, though there exists several severe performance degradation, we conjecture this due to two main causes. On the one hand, when structural and feature corruptions are larger than a relatively large value such as 0.8, the augmented (distorted) graphs have been overwhelmed in the entire framework, and thus encoders and sub-modules cannot be trained steadily without enough graph information, capturing limited and useless representations. On the other hand, we observe that the poor capability happens when augmentations are slightly weak. For instance, when edge dropping rates are 0.1, performances degrade sharply on datasets. The reason behind this is that augmented graphs across views in these cases change slightly. Since multi-view contrastive learning needs proper and informative views to perform discrimination, this cannot provide sufficient information for multiview learning. Overall, with moderate views, MLG-CPC can yield competitive performances, which demonstrates more elegant graph augmentations are significant for multi-view contrastive graph learning.

4.6 Visualization

In this section, we provide visualization results of our MLGCPC. To be specific, we utilize t-SNE [Van der Maaten and Hinton, 2008] to visualize embedding of our MLG-CPC at different stages intuitively in Figure 4. At the initial stage, raw features are non-discriminative for clustering. During the model training phase, embedding gradually becomes more discriminative because objectives of MLG-CPC are optimized as epoch increases. At last, we can see the learned embedding is more promising, which has smaller intra-class distances as well as larger inter-class distances compared with raw features for the clustering task.

We also plot similarity matrices of embedding on the ACM dataset in Figure 5. Compared with the matrix without feature orthogonality on the left, the embedding of MLG-CPC on the right is more approximate to the diagonal matrix. Thanks to this feature orthogonality, different dimensions are encouraged to capture distinct information, and thus the overlap information of different feature dimensions is minimized. This discriminative information will serve for the prototypical- and cluster-level space in the overall model, further enhancing the underlying performances of other sub-modules.

5 Conclusion

We introduce a novel graph contrastive framework for end-toend clustering. Specifically, our MLG-CPC distills the features by orthogonality and generates assignments via cluster predictors. Currently, assignments are leveraged to generate prototypes, which then can perform prototype discrimination for semantic exploitation globally. Moreover, by virtue of different-level representation spaces, MLG-CPC concentrates on their objectives individually and jointly optimizes without laborious parameters balancing. Extensive experimental results on four datasets demonstrate the superiority of MLG-CPC. We will investigate the validity of MLG-CPC for graphs with heterophily in our future work.

Acknowledgments

This work was supported by the National Natural Science Foundation of China under Grant U21B2041, 61825603, National Key R&D Program of China 2020YFB2103902.