Contrastive Representation Learning Based on Multiple Node-centered Subgraphs

Inspired by the advances of contrastive learning in fields such as CV and NLP, some work has started to apply contrastive learning on graph data for graph representation learning. The objective of graph contrastive learning is to maximize the MI between similar instances in a graph (Wu et al., 2021), and its model design focuses on three modules: data augmentation, proxy tasks, and contrastive objectives. Among them, the most important modules is the proxy task, which describes the definition of similar instances (i.e. positive example) and dissimilar instances (i.e. negative example). DGI (Velickovic et al., 2019) extends the idea of DIM (Hjelm et al., 2018) to graph data to learn node representations by maximizing the MI between local node representation and global graph representation. GMI (Peng et al., 2020) takes nodes and their neighbors as objects of study and maximizes the MI between hidden representation of each node and the original features of its neighboring nodes. GIC (Mavromatis and Karypis, 2020) clusters the nodes in the graph by a differentiable version of K-means clustering, and then maximizes the MI between the node representation and its corresponding cluster summaries. SUBG-CON (Jiao et al., 2020) obtains the context subgraph of each node by subgraph sampling based data augmentation, and then maximizes the consistency between them. Despite the good results achieved, these works perform graph contrastive learning only on a single perspective for nodes.

Recently, multi-view representation learning has become a rapidly growing direction in machine learning and data mining areas (Li et al., 2018; Peng et al., 2022; Zhao and Chen, 2019; Zhao et al., 2020, 2021; Zhao, 2021). It has had a lot of success in areas such as computer vision. For instance, Contrastive Multiview Coding (CMC) (Tian et al., 2020) uses contrastive learning to maximize the mutual information between multiple views of a dataset to perform representation learning of images. MVGRL (Hassani and Khasahmadi, 2020) obtains multiple views of graph through data augmentation, and they find out that unlike visual representation learning, increasing the number of views of the entire graph to more than two by data augmentation does not improve performance. Unlike the multi-view graph contrastive learning summarized in MVGRL which focuses on node attributes at graph-level, our multiple node-centered subgraphs in this paper focus more on the differences in structure at node-level.

We can deal with a whole graph from different views (Hassani and Khasahmadi, 2020), and the same is true for any node in the graph. For a single node, there are many subgraphs centered on it (e.g., ego network (Zimmermann and Nagappan, 2008)). If these node-centered regional subgraphs have certain semantic information (e.g., ego network represents a specific individual and other persons who have a social relationship with him), then we can treat them as different perspectives of the central node.

The main role of the subgraph generator $\mathcal{T}$ is to sample these node-centered regional subgraphs from $\mathcal{G}$ and generate the corresponding negative samples from $\tilde{\mathcal{G}}$. Specifically, for a specific node $v_{i}$ and a prepared node-centered subgraph type $k$, the subgraph generator $\mathcal{T}$ first gets $idx$, a set which represents the index of chosen nodes for subgraph $\mathcal{G}_{i}^{k}$ to be obtained. Then, the node representation matrix $\textbf{H}_{i}^{k}\in\mathbb{R}^{N^{\prime}\times F^{\prime}}$ and adjacency matrix $\textbf{A}_{i}^{k}\in\mathbb{R}^{N^{\prime}\times N^{\prime}}$ of $\mathcal{G}_{i}^{k}$ are denoted respectively as

where $\cdot_{idx}$ is an indexing operation and $N^{\prime}$ is the length of $idx$.

In this way, we can obtain the $k$-th node-centered subgraph $\displaystyle\mathcal{G}_{i}^{k}=(\textbf{H}_{i}^{k},\textbf{A}_{i}^{k})\sim\mathcal{T}(\textbf{H},\textbf{A})$ for any specific node $v_{i}$. Likewise, the corresponding negative example can be obtained by $\displaystyle\tilde{\mathcal{G}}_{i}^{k}=(\tilde{\textbf{H}}_{i}^{k},\tilde{\textbf{A}}_{i}^{k})=(\tilde{\textbf{H}}_{idx,:},\tilde{\textbf{A}}_{idx,idx})$.

To learn a more comprehensive representation, we carefully design five different node-centered subgraphs, as illustrated in Figure 3. The details of them are as follows:

Subgraph 1: Basic subgraph. The basic subgraph only contains the central node itself (i.e., $N^{\prime}=1$), that means for each node $v_{i}$:

Further, we can get the basic subgraph representation and its corresponding negative example by $\textbf{v}_{i}^{1}=\textbf{h}_{i}$ and $\textbf{u}_{i}^{1}=\tilde{\textbf{h}}_{i}$. For any specific node, basic subgraph is the purest “subgraph” as well as the main subgraph, which contains the most concentrated features of the node iteself.

Subgraph 2: Neighboring subgraph. The neighbors of the central node are often closely related to the node in structure, and study with them can better capture the structural features of node (Hamilton et al., 2017a). The neighboring subgraph contains all nodes with a distance less than or equal to $d$ from the central node $v_{i}$, denoted as

where $dis(\cdot,\cdot)$ is a function used to get the distance between two nodes. After obtaining the neighboring subgraph $\mathcal{G}_{i}^{2}$ by Eq. (1), a readout function $\displaystyle\mathcal{R}:\mathbb{R}^{N\times F^{\prime}}\to\mathbb{R}^{F^{\prime}}$ is used to obtain the neighboring subgraph representation and its corresponding negative example:

It is beneficial to learn a more comprehensive representation when we take a larger range of neighbors. But at the same time, the features of the central node will be weakened, which will cause the model to be more inclined to learn the representation of a region or even the whole graph. It follows that it’s important to choose the value of $d$. As shown in the Figure 5, the model reaches the best performance when $d=1$ for the neighboring subgraph.

Subgraph 3: Intimate subgraph. The intimate subgraph takes into account the similarity that actually exists between two nodes in the input graph $\mathcal{G}$. It contains the first $l$ nodes that are most similar to the central node. This is equivalent to identifying the nodes that are structurally close to the central node from another perspective, and thus learning the structural features of the nodes more comprehensively.

The similarity between nodes is usually measured by a similarity scores matrix $\textbf{S}\in\mathbb{R}^{N\times N}$, where $\textbf{S}(i,j)$ measures the similarity between nodes $v_{i}$ and $v_{j}$. Here we follow the personalized pagerank (PPR) algorithm (Jeh and Widom, 2003) as introduced in (Zhang et al., 2020). The similarity scores matrix S based on the PPR algorithm can be denoted as

where I is the identity matrix and $\bar{\textbf{A}}=\textbf{A}\textbf{D}^{-1}$ denotes the colum-normalized adjacency matrix. D is the diagonal matrix corresponding to A with $\textbf{D}(i,i)=\sum_{j}\textbf{A}(i,j)$ on its diagonal. $\alpha\in[0,1]$ is a parameter which is set as 0.15 in (Jiao et al., 2020). For a specific node $v_{i}$, the subgraph generator $\mathcal{T}$ chooses its top-$l$ similar nodes (i.e., $N^{\prime}=l$) to generate intimate subgraph with $\textbf{S}(i,:)$, which can be denoted as

where $top\_rank(\cdot)$ is a function that selects the top-$l$ values from a vector and return the corresponding indices. Same as Subgraph 2 subsection, we can obtain the intimate subgraph representation and its corresponding negative example with $\textbf{v}_{i}^{3}=\mathcal{R}(\textbf{H}_{i}^{3})$ and $\textbf{u}_{i}^{3}=\mathcal{R}(\tilde{\textbf{H}}_{i}^{3})$.

Subgraph 4: Communal subgraph. In graph clustering, nodes in a uniform cluster tend to have similarity in attributes. Therefore, we can select all nodes in the cluster to which the central node belongs to get the communal subgraph. These nodes with similar attributes to the central node can help the model better learn the attribute features of the central node.

It is particularly noteworthy that the other subgraphs are obtained independently of the node attributes (i.e., H), but the communal subgraph is attribute-related. Since H will change during training, a fixed $idx$ before the model training as other subgraphs may lead to undesirable results.

There are already many methods to perform graph clustering (Schaeffer, 2007). We tried three different clustering strategies based on $K$-means clustering (MacQueen, 1967) due to the stable and excellent performance of it.

• •

  Strategy 1: Precomputed K-means. Same as other subgraphs, the node-centered subgraphs are sampled before model training starts. Specifically, the traditional $K$-means clustering algorithm is used to cluster the nodes in the input graph $\mathcal{G}$. For any specific node $v_{i}$, take all the indices of nodes in its cluster as $idx$ and further compute $\textbf{v}_{i}^{4}$ and $\textbf{u}_{i}^{4}$.

• •

  Strategy 2: A differentiable version of K-means. To update the communal subgraph during training, we need an end-to-end clustering algorithm. Here we follow a differentiable version of K-means as introduced in (Wilder et al., 2019). For each node $v_{i}$, let $\mathbf{\mu}_{c}$ denote the center of cluster $c$ and $\hat{\mathbf{\gamma}}_{ic}$ (s.t., $\sum_{c}\hat{\mathbf{\gamma}}_{ic}=1,\forall i$) denotes the degree to which node $v_{i}$ is assigned to cluster $c$. Suppose that the number of clusters to be obtained is $C$, ClusterNet updates $\mathbf{\mu}_{c}$ via an iterative process by alternately setting.

  (7)

  $$\mathbf{\mu}_{c}=\frac{\sum_{i}\hat{\mathbf{\gamma}}_{ic}\textbf{h}_{i}}{\sum_{i}\hat{\mathbf{\gamma}}_{ic}}\ \ c=1,...,C,$$

  and

  (8)

  $$\hat{\mathbf{\gamma}}_{ic}=\frac{exp(-\beta\cdot sim(\textbf{h}_{i},\mathbf{\mu}_{c}))}{\sum_{c}exp(-\beta\cdot sim(\textbf{h}_{i},\mathbf{\mu}_{c}))}\ \ c=1,...,C,$$

  where $\beta$ is an inverse-temperature hyperparameter, the standard K-means assignment is recovered when $\beta\to\infty$. $sim(\cdot,\cdot)$ denotes a similarity function between two instances. Eventually, we can get the communal subgraph representation by

  (9)

  $$\textbf{v}_{i}^{4}=\sigma\left(\sum_{c=1}^{C}\hat{\mathbf{\gamma}}_{ic}\mathbf{\mu}_{c}\right),$$

  where $\sigma(\cdot)$ is the logistic sigmoid nonlinearity. Since this method does not get $idx$, we simply get negative example $\displaystyle\{\textbf{u}_{1}^{4},\textbf{u}_{2}^{4},...,\textbf{u}_{N}^{4}\}$ of all nodes by row-wise shuffling of $\displaystyle\{\textbf{v}_{1}^{4},\textbf{v}_{2}^{4},...,\textbf{v}_{N}^{4}\}$.

• •

  Strategy 3: An end-to-end version of K-means with an estimation network. In this way, we replace the iterative process in Strategy 2 with an estimation network, which utilizes a multi-layer neural network to directly predict the degree to which each node belongs to each cluster $\displaystyle\hat{\mathbf{\gamma}}\in\mathbb{R}^{N\times C}$, denoted as

  (10)

  $$\hat{\mathbf{\gamma}}=softmax(MLP(\textbf{H};\theta)),$$

  where $softmax(\cdot)$ is a softmax nonlinearity and $MLP(\cdot)$ is a multi-layer neural network with trainable parameters $\theta$. Then we get the communal subgraph representation by Eq. (8) and Eq. (9) as same as Strategy 2.

The comparison of the three strategies is shown in Figure 5. After weighing both accuracy and efficiency, we chose Strategy 2 to generate the communal subgraph.

Subgraph 5: Full subgraph. To learn a comprehensive representation of a node, it is essential to observe it from a global perspective. The full subgraph contains all the nodes (i.e. $N^{\prime}=N$) in the input graph $\mathcal{G}$, e.g., for any specific node $v_{i}$,

Compared with the previous subgraphs, the full subgraph contains far more nodes than they do, which extremely weakens the specificity of the central node. At the same time, it is not conducive to learning a specialized node representation as all nodes have the same full subgraph. Based on these ideas, we propose full subgraph for specific node $v_{i}$ with self-weighted, denoted as

where $\eta\in[0,1]$ is a self-weighted factor.

So far, we have introduced five carefully designed node-centered subgraphs. It is noted that subgraphs other than Subgraph 4 can be precomputed before model training starts, which allows us to quickly obtain these subgraphs during training by performing only one calculation before training.

The key idea of self-supervised comparative learning is to define a proxy task to generate positive and negative samples. The encoder $\mathcal{F}$ that generates the node representation is trained by contrast between positive and negative samples.

To handle multiple subgraphs we obtained before, we take the “core view” (CV) and “full graph” (FG) paradigms as introduced in CMC (Tian et al., 2020), as shown in Figure 4.(a). Further, the contrastive lossess under core view and full graph cases are illustrated in Figure 4.(b). Specifically, in the core view case, we regard Subgraph 1 as the most critical node-centered subgraph. It and its corresponding negative sample constitute positive and negative pairs with Subgraph 2$\thicksim$5, respectively. As for the full graph case, any two between Subgraph 1$\thicksim$5 constitute positive pairs, and Subgraph 1$\thicksim$5 respectively form negative pairs with their corresponding negative examples.

After defining the proxy task, we follow the intuitions from DGI (Velickovic et al., 2019) and use a noise-contrastive type objective with a standard binary cross-entropy (BCE) loss between positive examples and negative examples. MNCSCL’s objective under core view case is

where $K$ is the number of selected node-centered subgraphs and $\mathcal{D}:\mathbb{R}^{F^{\prime}}\times\mathbb{R}^{F^{\prime}}\to\mathbb{R}$ is a discriminator which is used for estimating the MI by assigning higher scores to positive examples than negatives. When using the full graph case, the objective becomes

The Eq. (13) and Eq. (14) are used as the contrastive loss in the experiments respectively.

Baseline methods. In node classification task, the compared methods include direct use of row features, 1 traditional unsupervised algorithm (i.e., Deep Walk (Perozzi et al., 2014)), two supervised graph neural networks (i.e., GCN (Kipf and Welling, 2016a) and FastGCN (Chen et al., 2018)) and 5 state-of-the-art self-supervised methods(i.e., DGI, GMI, GIC, GRACE (Zhu et al., 2020) and MVGRL (Hassani and Khasahmadi, 2020)).

• •

  DGI is one of the classical methods of graph representation learning based on contrastive learning. It aims to maximize the MI between the local perspective and the global perspective of the input graph, as well as the corresponding corrupted graph.

• •

  GMI draws on the ideas of DGI, but rather than employing a corruption function, this approach focuses on maximizing the MI between the hidden representations of nodes and their original local structure.

• •

  GIC is also inspired by DGI, its objective is to maximize the MI between the node’s representation and the representation of the cluster to which it is assigned.

• •

  GRACE propose a novel framework for unsupervised graph representation learning by leveraging a contrastive objective at the node level. In order to enhance the contrast effect, they created two sets of negative pairs, one within the same view and the other across different views.

• •

  MVGRL performs self-supervised learning by contrasting structural views of graphs, where they contrast first-order neighbors of nodes as well as a graph diffusion, with good results.

In link prediction, we directly follow the effective link prediction methods used in GIC (i.e., Deep Walk, Spectral Clustering (SC) (Tang and Liu, 2011), VGAE (Kipf and Welling, 2016b), ARGVA (Pan et al., 2019), DGI and GIC).

• •

  Spectral Clustering is initially introduced to solve the node partitioning problem in graph analysis. It has demonstrated satisfactory performance across diverse domains, such as graphs, text, images, and microarray data. Its effectiveness has been widely acknowledged in these areas.

• •

  VGAE is an unsupervised learning framework designed for graph-structured data, utilizing the variational auto-encoder (VAE) methodology. In VGAE, a GNN-based encoder is employed to generate node embeddings, while a straightforward decoder is used to reconstruct the adjacency matrix.

• •

  ARGVA is a graph embedding framework specifically designed for graph data, incorporating adversarial learning techniques. Similar to VGAE, ARGVA adopts a similar structure, but it learns the underlying data distribution through an adversarial approach.

Evaluation metrics. For the node classification task, we classify the test set by a logistic regression classifier, and then evaluate the performance using classification accuracy for transductive datasets (i.e., Cora, Citeseer and Pubmed) and micro-averaged F1 score for inductive datasets (i.e., Reddit and PPI). Suppose that TP, FN, FP and TN represent the number of true positives, false negatives, false positives, and true negatives, respectively. Then classification accuracy can be calculated by $accuracy=(TP+TN)/(TP+FP+TN+FN)$. Also micro-averaged F1 score can be calculated by $F1-Score=2*precision*recall/(precision+recall)$, where $precision=TP/(TP+FP)$ and $recall=TP/(TP+FN)$. For the link prediction task, we use the AUC score (the area under ROC curve) and the AP score (the area under Precision-Recall curve) for evaluation. The closer the AUC score and the AP score approaches 1, the better the performance of the algorithm is.

Training strategy. We implement MNCSCL using PyTorch (Ketkar and Moolayil, 2021) on 4 NVIDIA GeForce RTX 3090 GPUs and use Adam optimizer (Kingma and Ba, 2014) with an initial learning rate of 0.001 (specially, 0.0001 for Reddit) during training. We follow settings in DGI that using an early stopping strategy with a patience of 20 epochs for transductive datasets and a fixed number of epochs (150 on Reddit, 20 on PPI) for inductive datasets. For large graphs, we adopt the sampling strategy used by GraphSAGE (Hamilton et al., 2017a).

Encoder design. For transductive datasets, we adopt a one-layer Graph Convolutional Network (GCN) as our encoder, with the following propagation rule:

where $\hat{\textbf{A}}=\textbf{A}+\textbf{I}_{N}$ is the adjacency matrix with self-loops and $\hat{\textbf{D}}(i,i)=\sum_{j}\hat{\textbf{A}}(i,j)$ is its corresponding degree matrix. $\sigma(\cdot)$ is the PReLU nonlinearity (He et al., 2015) and W is a learnable parameter matrix with $F^{\prime}=512$ (specially, $F^{\prime}=256$ on Pubmed). As for inductive datasets, we adopt a one-layer GCN with skip connections (Zhang and Meng, 2019) as our encoder, with the following propagation rule:

where $\textbf{W}_{skip}$ is a learnable parameter matrix with $F^{\prime}=512$ for skip connections.

Corruption function. For transductive datasets,we transform adjacency matrix A to a diffusion matrix U. Specifically, we compute diffusion using fast approximation and sparsification methods (Gasteiger et al., 2019) with heat kernel (Kondor and Lafferty, 2002):

where D is a diagonal degree matrix as in Section 3.1 and $t$ is diffusion time (Gasteiger et al., 2019). For Reddit dataset, we implement the corruption function $\mathcal{C}$ by keeping the adjacency matrix A unchanged (i.e. $\tilde{\textbf{A}}=\textbf{A}$) and perturbing the feature matrix X by row-wise shuffling. And for PPI dataset, we simply samples a different graph from the training set due to it’s a multiple-graph dataset.

Readout function. We use identical readout function $\mathcal{R}$ for all datasets, which performs a simple average of all node features for a given subgraph with $N^{\prime}$ nodes:

where $\sigma(\cdot)$ is the logistic sigmoid nonlinearity.

Discriminator. We use a simple bilinear scoring function as discriminator $\mathcal{D}$:

where $\textbf{W}_{d}$ is a learnable scoring matrix and $\sigma(\cdot)$ is the logistic sigmoid nonlinearity.

Details of node-centered subgraphs. We conduct experiments with all five node-centered subgraphs on two different contrastive losses (named MNCSCL-FG under full graph case and MNCSCL-CV under core view case, respectively). More specifically, we choose $d=1$ for the neighboring subgraph and Strategy 2 for the communal subgraph. For hyperparameters, we set the size of intimate subgraph $l$ as 20 (specially, 10 on citeseer). The number of clusters $C$ and inverse-temperature hyperparameter $\beta$ for communal subgraph is set to 128 and 10 respectively. To build a proper full subgraph, we also set the self-weighted factor as 0.01.

Node classification. Experiments show that MNCSCL achieves the best performance on all five datasets compared to other competing self-supervised methods, as shown in Table 3. We believe this robust performance is due to our comparison of multiple node-centered subgraphs, resulting in learning a more comprehensive node representation. Although MNCSCL-FG and MNCSCL-CV both have shown excellent performance, MNCSCL-FG performs better on PPI dataset and MNCSCL-CV performs better on other datasets. We think this is due to the very sparse available features on the PPI (over 40% of the nodes have all-zero features). It is more effective to use more perspectives for comparison on such sparse graph datasets. For other datasets, the contrastive loss under core view case is enough for MNCSCL to learn comprehensive information about the nodes, too much comparison will instead lead to overfitting and waste of resources. Compared to supervised methods, MNCSCL also outperforms the two compared methods on all datasets. This shows that our method is also very competitive compared to traditional supervision methods.

Link prediction. To test the generalization capability of MNCSCL, we intend to further investigate the performance of MNCSCL in link prediction task, as shown in Table 4. We find that MNCSCL outperforms all competing methods on both the Cora and Citeseer datasets, suggesting that a multiple node-centered subgraphs based comparison can help the model learn node representations with good generalizability. The excellent performance on different downstream tasks further proves the feasibility of our method.

Node-centered subgraph combination. To investigate how the number of node-centered subgraphs affects the performance of MNCSCL, we permuted and combined five previously mentioned node-centered subgraphs under the core view case and observed the classification accuracy of different subgraph combinations on Cora, Citeseer and Pubmed datasets with same hyperparameter setting, as shown in Table 5. Obviously, as the number of node-centered subgraphs increases, the classification accuracy continues to increase, and the best results are achieved when all five subgraphs are used. This indicates that multiple node-centered subgraphs contrastive learning can indeed learn better node representation. We also notice that the classification accuracy improvement is more obvious with the increase in the number of node-centered subgraphs.

Range of neighbors and clustering strategy. We investigate the value of $d$ in the neighboring subgraph and the selection of different clustering strategies in the communal subgraph, and the results are shown in Fig 5. Here we use all five node-centered subgraphs with the contrastive loss under core view case. It can be seen that the optimal choice in all three datasets is $d=1$ neighbors and Strategy 2. Our analyses are as follows.

• •

  For the neighboring subgraph, the classification accuracy tends to decrease as the vale of $d$ increases. We believe that too many neighboring nodes will lead to cause overfitting of the model and performance degradation. This viewpoint can also be verified from the pubmed dataset, where it is not obvious whether the classification accuracy is better or worse when setting $d=1$ and $d=2$. Because the attributes of pubmed are relatively sparse, sometimes its neighboring subgraph needs to contain more neighbors to get better results.

• •

  In the choice of clustering strategy, Strategy 1 is significantly less effective than the other two end-to-end strategies. Strategy 2 and Strategy 3 show comparable performance, but considering that Strategy 3 involves an estimation network, which means more resource consumption, we finally choose Strategy 2 as the clustering strategy for the communal subgraph.