CSGCL: Community-Strength-Enhanced Graph Contrastive Learning

1 Introduction

Graph Representation Learning (GRL) is extensively used in knowledge graphs [Zhang et al., 2022], recommendation [He et al., 2020], e-commerce [Li et al., 2020], biological systems [Rao et al., 2022], etc. Unlike the label-dependent and noise-sensitive supervised GRL methods, Graph Contrastive Learning (GCL) [Becker and Hinton, 1992] extracts well-generalized representations between paired data views in a self-supervised manner. Many promising results from node-level GCL studies have been achieved [Veliˇckovi´c et al., 2019; Hassani and Khasahmadi, 2020; Zhu et al., 2021]. Despite their success, most of these studies hardly consider the community in GCL.

* Corresponding authors.

† Tsinghua University (www.ruizhang.info)

A community is a high-order structure of a graph, characterized by a denser connection among its members [Girvan and Newman, 2002]. This underlying structure is highly informative: for citation networks, communities indicate different academic fields; for co-purchase networks, communities indicate the common interests of a customer in multiple types of merchandise. Therefore, it is necessary to take into account communities in GCL. Recently, research like gCooL [Li et al., 2022] combines community detection with GCL. However, their work is built on an underlying hypothesis that different communities have the same influence on global semantics, which may lead to extra representation biases in GCL.

To tackle this issue, we hold that communities influence global semantics differently, which is vital for GCL. We define "community strength" to measure this influence of communities, and give a visualized example of community strength in Figure 1(a). Community strength, denoted as S, indicates how dense the connection of a community c is, and reflects the influence of c on the entire graph. A stricter definition can be found in Section 3.2. "Strong communities", with more densely connected edges, have a larger S (e.g. Sc1 and Sc3); "weak communities", more sparsely connected ones, have a smaller S (e.g. Sc2 and Sc4). As shown in Figure 1(b), the difference of community strength is one of the inherent features of real-world networks. Hence, community strength is of practical importance. We naturally ask: is there an effective way to leverage community strength information in GCL?

To answer this question, we propose a novel CommunityStrength-enhanced Graph Contrastive Learning (CSGCL) framework. It can capture and preserve community strength information throughout the learning process, from data augmentation to the training objective. Firstly, we put forward two novel graph augmentation approaches, Communal Attribute Voting (CAV) and Communal Edge Dropping (CED), which apply community strength respectively to every attribute and every edge to preserve the differences among communities. Secondly, we propose a dynamic "Team-up" contrastive scheme for CSGCL to progressively fine-tune the contrastive objective with community strength.

With the help of community strength, CSGCL can learn more discriminative representations, as in Figure 2. Without the consideration of community strength, every community is treated equally, which is not the case for real-world networks, so it leads to more representation biases. CSGCL takes into account community strength to handle these biases.

Our main contributions are as follows:

• We give a definition of community strength to evaluate the influence of a community. To the best of our knowledge, we are the first to manage to preserve community strength information in GCL.
• We propose two enhanced graph augmentation methods, CAV and CED, in which the perturbations of node attributes and edges are guided by community strength.
• A dynamic Team-up objective is devised, which directs the training process to preserve community strength.
• Extensive experiments on graph benchmark datasets show that CSGCL achieves state-of-the-art performance on up to three downstream tasks - node classification, node clustering, and link prediction.

2 RelatedWork

In this section, we give a brief review of traditional GRL methods, node-level GCL methods, and GCL with communities. Then, we compare CSGCL with these methods. For additional related work, see Appendix D.

2.1 Graph Representation Learning (GRL)

GRL extracts and compresses the semantic information and topological structure of a graph into low-dimensional representation vectors. Traditional methods [Perozzi et al., 2014; Grover and Leskovec, 2016] employ random walks to generate node sequences and embed them into the representation space using text encoding approaches. These methods only consider the co-occurrence of nodes. As improvements, CPNE [Wang et al., 2017] preserves community information by Non-negative Matrix Decomposition and, WGCN [Zhao et al., 2021] captures weighted structure features. An effective GRL paradigm is graph self-supervised learning [Kipf and Welling, 2016; Liu et al., 2022], which creates pretext tasks to leverage the information within data, helping the model to get rid of label dependency. However, they do not preserve community strength well in their representations.

2.2 Graph Contrastive Learning (GCL)

Shortly after the proposal of contrastive learning [Hjelm et al., 2019; Chen et al., 2020], it was introduced into the GRL field and became a new self-supervised hotspot. Most existing GCL methods [Zhu et al., 2020; Lee et al., 2022; Zhu et al., 2022; Wei et al., 2022] only focus on node-level relations. GraphCL [You et al., 2020] introduces augmentations of nodes or node pairs like DropEdge [Rong et al., 2020] and feature masking into GCL to increase the difference between two graph views. GCA [Zhu et al., 2021] further improves graph augmentation methods to adaptively capture the impact of different nodes. Outstanding as they are, they ignore the inherent community information in networks. Other works which consider the global information of graphs [Veliˇckovi´c et al., 2019; Hassani and Khasahmadi, 2020] also pay little attention to community semantics, which is discarded or undermined in node-level readout operations.

gCooL [Li et al., 2022] makes a good attempt to combine community information with GCL. It partitions communities on the representation graph and contrasts node-level and community-level representations across two different views, considering node pairs of the same community as positive samples. However, gCooL does not capture the difference between strong and weak communities. The differences between CSGCL and the aforementioned methods are that (1)

CSGCL is a contrastive method taking advantage of community strength information; (2) CSGCL preserves community strength from data augmentation to model optimization.

3 Community-Strength-enhanced Graph Contrastive Learning

In this section, we illustrate and formulate the details of CSGCL. The overall architecture of CSGCL is shown in Figure 3. Notations used below are summarized in Table 1. For an intuitive workflow of CSGCL, we summarize our approaches in pseudo-codes in Appendix A.

3.1 Graph Contrastive Learning

An undirected attributed graph G = (V, E) is composed of a vertex set V and an edge set E. In a graph dataset, a graph with n nodes and d attributes is given as a node attribute matrix X ∈ Rn×d and a symmetric adjacency matrix A ∈ {0, 1}n×n , denoted as G = (X, A). For nodes u, v ∈ V, A(u,v) = 1 iff edge (u, v) ∈ E, otherwise A(u,v) = 0.

Graph Contrastive Learning aims to maximize the agreement of pairwise graph embeddings [Hjelm et al., 2019]. In general, A GCL framework is comprised of a GNN encoder, a projection head, and a contrastive loss. At the beginning of training, GCL generates two graph views ( ˜ G1, ˜ G2) by random perturbation to the input graph. Such perturbation is usually from multiple data augmentations T (G), e.g. DropEdge [Rong et al., 2020] and feature masking [Zhu et al., 2020]. Then, two views are both fed into a shared GNN encoder (like a two-layer GCN [Kipf and Welling, 2017]) to obtain node representations (but only the encoder is retained for various downstream predictions). Let Z = f ( ˜ G; Θ) be the projected embedding of ˜ G, where f is the graph encoder followed by a nonlinear projection layer. The embeddings of a certain node i in different views (Z(1) i: ,Z(2) i: ) are seen as positive pairs, and all other pairs (embeddings of different nodes in the same or different views) are seen as negative pairs.

GCL usually employs noise contrastive estimation (NCE) as the optimization objective. The most commonly used one is InfoNCE [Oord et al., 2018], which enhances the discrimination of representations by pulling similar (positive) ones together and pushing dissimilar (negative) ones away. The similarity between node pairs is calculated as

where sim(zi, zj) = (z⊤i zj)/ (∥zi∥∥zj∥) , and τ is the temperature of the similarity. Then InfoNCE is formulated as

3.2 Community-strength-enhancedAugmentations

In this section, we introduce the community-strengthenhanced augmentations: Communal Attribute Voting and Communal Edge Dropping.

Community strength. To begin with, communities in the graph are highlighted by unsupervised community detection methods. CSGCL utilizes existing community detectors so that our study can refocus attention on the communities in graph representations. We give more details of community detection methods suitable for CSGCL in Appendix D.

Let C be the set of all communities in graph G. Then, we have the definition below:

Definition 1. (Community strength S) For every community c of an undirected attributed graph G = (V, E), let |E| and |Ec| be the number of edges of the entire graph and inside that community respectively. Then, the community strength Sc of community c is formulated as follows:

which is composed of two terms: the proportion of edges inside community c, and the inter-community connection between c and other communities.

Community strength is based on modularity [Newman and Girvan, 2004], a measure of graph partition quality, which compares every community with its randomly connected counterpart, and calculates the difference in their number of edges. However, community strength is a metric of the local topological structure, while modularity is a quality metric of the entire graph. S > 0 for every community, because Sc ≤ 0 means c does not have any community characteristics.

Communal Attribute Voting (CAV). Based on the definition above, we propose CAV, a graph augmentation method based on attribute masking, which adopts community voting for attribute removal: attributes which are more influential in strong communities are better preserved, whereas less influential attributes are more likely to be voted out.

As the voting begins, a community penalty wa is assigned to every single attribute of X. Intuitively, wa reflects the odds to be removed for every attribute candidate:

where H ∈ {0, 1}n×|C| is an indicator matrix with Hi,c = 1[vi∈c] indicating to which community the ith node belongs, and ˜na(x) = (xmax - x)/(xmax - xmean) is a onedimensional normalization operation. Each node will score and vote for its redundant attributes, and the least-voted-for attributes will win a greater opportunity to be preserved.

Then, inspired by [Zhu et al., 2021], we adaptively adjust the attribute perturbation distribution using wa. Specifically, the voting results are a group of attribute masks ma independently sampled from two Bernoulli distributions:

where p(1) a and p(2) a are two hyperparameters controlling the sampling ranges. In this way, community strength is well preserved in the perturbed attribute matrices:

where ◦ is the Hadamard product.

Communal Edge Dropping (CED). The edge is the fundamental structural unit of graphs. Evolved from DropEdge [Rong et al., 2020], CED preserves community structures from perturbations guided by community strength.

The rationale for CED is that (1) intra-community edges are more important than inter-community edges, and (2) edges in strong communities are more important than those in weak communities. If there is a scoring function w(e) to calculate the weight we of each edge e ∈ Ec in the community c, it must meet the following condition:

where estrong is an intra-strong-community edge, eweak is an intra-weak-community edge with Sstrong > Sweak, and einter is an inter-community edge.

To this end, let e = (ui, uj), we formulate CED as:

where ˜ne(x) = (x - xmin)/(xmean - xmin) is a onedimensional normalization operation.

Remark 1. Theorem 1 indicates that CED is an ideal graph augmentation on edges: (1) strong communities have larger edge weights and vice versa; (2) inter-community edges have the smallest weights, which are much more likely to be dropped. Such design aims to retain real-world community properties in the perturbed graphs as much as possible.

Then, similar to CAV, the edge weight vector we is used to adjust the edge perturbation distribution:

where p(1) e and p(2) e function like p(1) a and p(2) a . In this way, community strength is well preserved in the perturbed adjacency matrices:

Up to now, two augmented graphs ( ˜ G (1) , ˜ G (2) ) have been generated by CSGCL to get embeddings.

3.3 Team-up Contrastive Learning Scheme

After obtaining the embeddings of two augmented graph views Z(1) = f( ˜ G (1) ; Θ), Z(2) = f( ˜ G (2) ;Θ), we find it necessary to teach our encoder the differences among communities, guided by a community-strength-enhanced objective.

GRL with communities is analogous to real-world social group activities. On such occasions, people tend to team up with those with whom they are familiar. A group of strangers need to communicate with one another to seek common interests before they coalesce [Khambatti et al., 2002]. Going back to the GRL scenario: at the beginning of training, nodes are unfamiliar with each other and crave for interaction with anyone within reach. As the training goes on, sufficient information exchange between nodes makes them understand their partners better. Driven by common interests, they tend to gather into groups - at this moment, the guidance of communities is indispensable for model optimization.

Inspired by this, we propose the dynamic Team-up contrastive learning scheme to learn communities more effectively. We divide CSGCL's learning process into two phases:

Individual contrast. In the first phase, themodel optimizes InfoNCE to learn initial similarities between each node individuals. The form of InfoNCE is shown in (2).

Team-up contrast. In the second phase, every similarity term s of InfoNCE is fine-tuned by community strength:

where

and Hi: is the community membership for the ith node. The latter term in (13) refers to the strength of "teams" (communities) to which the ith and jth nodes belong, and γ is a coefficient of community strength.

The final loss is a piecewise function combining the two phases above, with a dynamic change of the fine-tuned similarity ˜ s in (13):

in which γ(t) is a monotonically non-decreasing function that varies with training time t (in the units of 100 epochs). We simply consider a hard Sigmoid-shaped form for γ(t):

where t0 is the demarcation point of two phases. Thus we can unify two phases and formulate the final loss as (12)(14)(15): during the individual contrast (t ≤ t0, γ = 0), free communications are allowed between node individuals; during the Team-up contrast (t0 < t < t0 + γmax) when the nodelevel relationships are well-learned, γ rises gradually to direct the model to notice community strength; when teaming-up is complete (t ≥ t0 + γmax), we set γ ≡ γmax to prevent deviation from the contrastive objective.

4 Experiments

In this section, we describe our experiments that were conducted to evaluate our model and answer the questions below:

• Does GCL really benefit from our proposed methods? (Section 4.2).
• Is the boost to performance really given by community strength? (Section 4.3).
• How does the Team-up strength coefficient influence the performance on a certain graph? (Section 4.4).

Detailed experiment configurations can be found in Appendix C. Additional experiment results using different community detectors and metrics (micro- & macro-F1 and average precision) can be found in Appendix E.

4.1 Experiment Setup

Datasets. We use four benchmark graphs in different fields, including one directed graph: Wiki-CS; and three undirected graphs: Amazon-Computers (Computers), Amazon-Photo (Photo), and Coauthor-CS. We convert Wiki-CS to an undirected graph only during the community detection process by adding reverse edges. There is no other difference between Wiki-CS and undirected graphs for model training.

Baselines. We divide all baseline models into the following three categories:

• Traditional unsupervised models: Logistic regression (LogReg) & K-means [MacQueen, 1967] with raw features, DeepWalk [Perozzi et al., 2014] w/ or w/o the use of node attributes, node2vec [Grover and Leskovec, 2016], and CPNE [Wang et al., 2017];
• Supervised graph neural network models: GCN [Kipf and Welling, 2017] and GAT [Veliˇckovi´c et al., 2018];
• Renowned and up-to-date self-supervised GRL models: GAE & VGAE [Kipf and Welling, 2016], DGI [Veliˇckovi´c et al., 2019], MVGRL [Hassani and Khasahmadi, 2020], GRACE [Zhu et al., 2020], GCA [Zhu et al., 2021], AFGRL [Lee et al., 2022], and gCooL [Li et al., 2022].

For GCA and gCooL which have multiple model configurations, we select the best one for each dataset, marked as "- best" in the statistics.

Evaluation protocol. For node classification, we follow the evaluation protocol of [Zhu et al., 2021] which trains and tests an ℓ2-regularized logistic regression classifier with 10 random data splits (20 fixed splits for Wiki-CS). For node clustering, a K-means model [MacQueen, 1967] with fixed initial clusters is fit. For link prediction, the cosine similarity between every two nodes is calculated to evaluate the existence of a link. Each experiment is repeated 10 times to report the average performance along with the standard deviation.

Metrics. We use accuracy for node classification, normalized mutual information (NMI) [Ana and Jain, 2003] for node clustering, and area under the curve (AUC) [Zhou et al., 2009] for link prediction.

Implementation details. We choose Leiden [Traag et al., 2019] as the community detector for CSGCL, before which we pretested the community detection methods detailed in Appendix E.1. To ensure fairness, A simple two-layer GCN is employed to CSGCL as well as all other contrastive baselines. We use the Adam optimizer to optimize the model. Detailed environment configurations can be found in Appendix C.2.

4.2 Overall Performance

In this section, we discuss the overall performance of CSGCL. CSGCL is adapted to three downstream tasks: node classification and node clustering on all datasets (Table 2 and 3), and link prediction on three undirected datasets (Table 4). Some statistics are borrowed from either their original papers or [Zhu et al., 2021; Li et al., 2022]. Data components used by each method during training are shown in the "Training data" column of Table 2, including node attributes X, the adjacency matrix A, and labels Y. The representation level of each unsupervised method is listed in the "Level" column, including node-level and community-level. Bolded results in Tables 2-5 below represent the best results for each column.

We can see that CSGCL is superior to not only the traditional baselines but also the latest GCL models in all three downstream tasks. This is most noticeable in node clustering, where the NMI score of CSGCL is 1.7% higher on average than the next-best methods; for link prediction, CSGCL has a 7.5% increase of AUC on Coauthor-CS compared with other contrastive methods. CSGCL is also observed to be competitive against fully supervised models, especially on link prediction. Such achievements reveal the great generality of graph representations of CSGCL: community strength is beneficial to multiple downstream tasks on graphs.

Note that gCooL - another GCL method with communities - also achieves great performance on these tasks, which backs up the benefit of community semantics for GCL. However, gCooL does not capture the differences among communities. We conduct the one-tailed Wilcoxon signed-rank test [Wilcoxon, 1992] to further back up our improvement: taking node classification as an example, we have p = 9.77e4 < 0.05 on all datasets, indicating the acceptance of alternative hypothesis that CSGCL has significant improvements over the best model of gCooL.

Furthermore, we visualize the graph representations of CSGCL as well as baselines by t-SNE [Van der Maaten and Hinton, 2008], a dimension reduction and visualization method. As shown in Figure 4, CSGCL learns the most discriminative graph representations among the competitive methods.

4.3 Ablation Studies

In this section, we describe the ablation studies on the key modules of CSGCL. "-CAV" and "-CED" refers to uniform attribute masking and edge dropping respectively, where the perturbation probabilities are set to the same for all attributes and edges. "-T" refers to the InfoNCE objective instead of Team-up. "-S" refers to the disregard of community strength, where every community shares the average strength S.

Table 5 verifies the effectiveness of CSGCL. The classification accuracy over all 4 datasets increases with either CAV or CED, and gains over 1% improvement on average with both. CSGCL with Team-up objective reaches the best classification performance, bringing significant improvements over CSGCL-T on three datasets with the results p = 1.37e-2, 2.78e-1, 3.71e-2, and 1.37e-2 of Wilcoxon signed-rank test in order. More importantly, the accuracy degrades without variations of community strength S. This verifies that the difference among community strength cannot be ignored.

We also show that CSGCL has well preserved community semantics by carrying out community detection on the representations. Results are shown in Figure 5. The green curves (w/ CAV and CED) perform better than the red curves (w/ uniform attribute masking and edge dropping) after a period of training time, especially on Photo and CoauthorCS; CSGCL, the blue curves using the Team-up objective, performs the best among its counterparts, with the performance gaps widening in the Team-up phase, especially on Computers and Photo. This shows that our communitystrength-enhancement has better preserved community semantics throughout the learning process, which results in more accurate graph representations.

4.4 Parameter Analysis

In this section, we describe the parameter analysis on the upper bound of the strength coefficient, γmax, which controls the overall influence of communities on a certain graph. All experiments below use the same training epochs and configurations. γmax is set as 0, 1, 2, 5, 10, and 20. We take Coauthor-CS and Wiki-CS as examples.

As the results in Figure 6, the accuracy of node classification is relatively stable when γmax changes in a certain range. So holistically, CSGCL is robust to the variation of γmax, but it is recommended to use the most appropriate one for each dataset to achieve better performance. The classification accuracy will decrease if γmax is too small (e.g. < 1 for Coauthor-CS), undermining the benefit of communities; however, it will also decrease if γmax is too large (e.g. > 5 for Coauthor-CS), derailing the model training.

5 Conclusion

In this paper, we present CSGCL, a novel contrastive framework enhanced by community strength throughout the learning process. Firstly, we manage to preserve differences among communities by the enhanced augmentations on attributes and edges, CAV and CED. Secondly, we put forward the dynamic Team-up contrastive scheme which regards GCL as a social group activity, guiding the optimization with community strength in a progressive manner. CSGCL achieves state-of-the-art performance on three downstream tasks: node classification, node clustering, and link prediction, indicating the effectiveness and generality of community-strengthenhanced representations.

Acknowledgments

This work is supported by National Natural Science Foundation of China under grants U1936108, U1836204, 62206102, and Science and Technology Support Program of Hubei Province under grant 2022BAA046.

Contribution Statement

The paper is co-first authored by Han Chen and Ziwen Zhao.