Multi-Scale Contrastive Siamese Networks for Self-Supervised Graph Representation Learning

1 Introduction

trastive learning, have recently achieved promising results. Traditional unsupervised methods such as DeepWalk [Perozzi et al., 2014] and Node2Vec [Grover and Leskovec, 2016] are based on random walks and the skip-gram model, forcing neighboring nodes to have similar representations. However, random walk and other matrix reconstruction-based approaches [Kipf and Welling, 2017b; Hamilton et al., 2017] place a strong emphasis on the graph proximity and fail to consider other widely available relationships within or between subgraphs. Following the concept of mutual information (MI) [Oord et al., 2018] and other visual representation learning advances [Tian et al., 2020; He et al., 2020; Chen et al., 2020; Hjelm et al., 2019], a series of graph contrastive learning (GCL) methods have been proposed. For example, inspired by Deep InfoMax [Hjelm et al., 2019], DGI [Veliˇckovi´c et al., 2019] proposes to maximize the mutual information between the patch- and global-level representations. Based on this, MVGRL [Hassani and Khasahmadi, 2020] introduces the concept of graph multi-view contrastive learning by discriminating the patch-global representations over two augmented views that derived from the input graph. Other approaches, such as GMI [Peng et al., 2020] and GRACE [Zhu et al., 2020], extend the idea of MI maximization to contrast the representation of a node with its raw information (e.g., node features) or neighbors' representations in different views.

Over the past few years, graph representation learning, which aims to learn low-dimensional embeddings of nodes or graphs to preserve the underlying structural and attributive information, has become a pivotal part of mining graph-structured data. The learned embeddings can then be used in different downstream tasks, such as node and graph classification, by training specific decoders on top of the learned embeddings. Although graph neural networks (GNNs) [Defferrard et al., 2016; Kipf and Welling, 2017a; Veliˇckovi´c et al., 2018; Hamilton et al., 2017] have achieved significant progress in graph representation learning, most of them require a certain number of labeled nodes to train, which hinders them from being adopted in real-world applications where the labeling information is usually scarce and valuable.

To mitigate this gap, self-supervised graph representation learning approaches, especially those methods based on con- Although the aforementioned methods have achieved significant success, they suffer all or at least partially the following limitations. Firstly, existing MI-based methods, such DGI, GMI, and MVGRL, usually require an additional MI estimator to score positive (e.g., local-global representations) and negative pairs (e.g., representations from corrupted views), which is computationally expensive and also makes the model sensitive to the choice of discriminators [Tschannen et al., 2020]. Secondly, most of existing GCL methods heavily rely on a large number of negative samples to avoid collapsing to trivial solutions. In other words, negative nodes and graphs act as an indispensable regulator that needs to be deliberately selected in contrastive learning. To alleviate this problem, Grill et al. [2020] propose the Bootstrap Your Own Latent (BYOL) framework to perform unsupervised representation learning on images by leveraging the bootstrapping mechanism without using negative samples. Self-supervised representation learning methods utilizing Siamese networks [Chen and He, 2021; Shi et al., 2020] predominantly work in the visual domain but have not been extended to graphs yet.

∗Corresponding author

In this paper, to alleviate the drawbacks of existing GCL methods and take advantage of bootstrapping in Siamese networks, we propose a simple yet powerful framework to learn node-level representations, which we refer to as Multi-scalE contRastive sIamese neTwork (MERIT). Our method is designed to optimize two objectives, namely cross-network and cross-view contrastiveness. Firstly, considering that existing GCL methods heavily rely on negative samples to avoid representation collapse, we propose to use a momentum-driven Siamese architecture as our backbone to maximize the similarity between node representations in different views from the online and target network, respectively. The intuition behind is that the slowly-moving target network in our framework serves as a stable "mean teacher" to encode historical observations, which guides the online network to learn to explore richer and better representations without relying on extra negatives to avoid collapse [Grill et al., 2020]. However, merely optimizing this objective ignores the rich underlying graph topological information. To partially alleviate this problem, we inject additional negative samples to push disparate nodes away in different views across two networks, as shown in Figure 2(a). Secondly, different from the work in the visual domain where the similarity measurements are typically defined on the image level, we propose to further utilize node connectivity and introduce a multi-scale contrastive learning within and across views in the online network, i.e., Figure 2(b), to regularize the training of the aforementioned bootstrapping objective in our method. Experimental results on a variety of datasets demonstrate the superb performance of our design.

Our contribution is summarized as follow:

• We propose a novel framework to learn node representation by taking advantage of bootstrapping in Siamese network and multi-scale graph contrastive learning. To the best of our knowledge, we are the first to use the Siamese networks on node representation learning.
• We propose two types of contrastive objectives for self-supervised node representation learning based on Siamese networks. They regularize each other and are capable of providing a more effective graph encoder.
• We conduct extensive experiments on various real-world datasets and validate the effectiveness of the proposed method over state-of-the-art methods in self-supervised graph representation learning.

2 RelatedWork

Siamese network is a neural architecture that contains two or more identical structures (e.g., online and target encoder in Figure 1) to make multi-class prediction or entity comparison [Bromley et al., 1993]. Traditionally, it has been used on supervised tasks such as signature verification [Bromley et al., 1993] and face matching [Taigman et al., 2014]. Recently, Grill et al. [2020] employed this architecture on selfsupervised visual representation learning and achieved significant improvements over existing arts without using negative samples. To fully understand the underlying mechanism of BYOL, SimSiam [Chen and He, 2021] and RAFT [Shi et al., 2020] verify that the extra predictor in the online network and the stop-gradient mechanism in the target network are keys to prevent the collapse without the help of negative samples.

Unsupervised graph representation learning approaches are traditional based on random walks [Perozzi et al., 2014; Grover and Leskovec, 2016] and adjacency matrix reconstruction [Kipf and Welling, 2017b]. These methods heavily rely on node proximity but are less scalable and error-prone without extracting other widely available self-supervision signals in graphs. Recently, unsupervised GNN-based methods, such as GraphSAGE [Hamilton et al., 2017], have achieved considerable progress but still limited in performance. Contrastive methods, on the other hand, alleviate the aforementioned problems and achieve state-of-the-art performance. For example, DGI [Veliˇckovi´c et al., 2019] and InfoGraph [Sun et al., 2019] employ the idea of Deep InfoMax [Hjelm et al., 2019] and consider both patch and global information during the discrimination. MVGRL [Hassani and Khasahmadi, 2020] introduces augmented views to graph contrastive learning and optimizes the DGI-like objectives. GMI [Peng et al., 2020] proposes considering both graph proximity and feature space similarity by maximizing the mutual information between the representation and feature space with learnable weights. Other approaches, such as CG3 [Wan et al., 2021] and GRACE [Zhu et al., 2020], further extend the idea of graph MI maximization and conduct the discrimination on different scales.

3 ProposedMethod

Problem definition. Given a graph G = (X,A), where X ∈ RN×D denotes the node feature matrix, and A ∈ RN×N indicates the adjacency matrix where each entry Aij is the linkage relation between nodes i and j. In this paper, we aim to learn a graph encoder gθ : RN×D × RN×N → RN×D′ such that D′ ≪ D, without relying on the labeling information. The resulted representations H = gθ(X,A) = {h1, h2..., hN} can then be directly used in downstream tasks, such as node classification.

Overall framework. We propose a novel algorithm, namely MERIT, to learn node representations by taking advantage of both bootstrapping and multi-scale graph contrastive learning. As illustrated in Figure 1, our model mainly consists of three components: Graph augmentations, cross-network contrastive learning, and cross-view contrastive learning. To train our model, we first generate two augmented graph views, denoted as ˜ G1 and ˜ G2. After this, by processing these two views via the online network and the target network, we construct different graph contrastive paths on multiple scales in the latent space, as shown on the rightmost part in Figure 1. In the following sections, we illustrate the aforementioned crucial components.

3.1 Graph Augmentations

Augmentation is a key component in self-supervised visual representation learning. However, image augmentations such as cropping and rotating cannot be directly applied to graphs due to the huge disparity of these two modalities. Therefore, to facilitate contrastive learning on graphs, we propose four augmentation methods, as shown below, to augment the graph topological and attributive information.

Graph Diffusion (GD). We transform a graph via diffusion to generate a congruent view. The effectiveness of this method may be attributed to the extra global information provided by the diffused view. This process is fomulated as:

where θ is a parameter to control the distribution of local and global signals, T ∈ RN×N is the transition matrix to transfer the adjacency matrix [Klicpera et al., 2019]. In this paper, we adopt the Personalized PageRank (PPR) kernel to power the graph diffusion. Formally, given the adjacency matrix A, the identity matrix I, and the degree matrix D, Equation 1 can be reformulated as:

where α is a tunable parameter for the random walk teleport probability [Hassani and Khasahmadi, 2020].

Edge Modification (EM). Instead of merely dropping edges in the adjacency matrix, we also add the same number of dropped edges [You et al., 2020]. In such a way, we can maintain the original graph's property, while complicate the augmented view with the additional edges. Specifically, given the adjacency matrix A and the modification ratio P, we randomly drop P/2 portion of existing edges in the original graph and then randomly add the same portion of new edges to the graph. Both our edge dropping and adding process follow an i.i.d. uniform distribution.

Subsampling (SS). Similar to the image cropping, we randomly select a node index in the adjacency matrix as the splitting point, and then use it to crop the original graph to create a fixed-sized subgraph as the augmented graph view. An advantage of SS is enabling the batch processing to handle large graphs whose size may exceed the capability of the GPU memory.

Node FeatureMasking (NFM). Different from [You et al., 2020], given the feature matrix X and an augmentation ratio P , we randomly select P fraction of node feature dimensions in X and then mask them with zeros.

In this paper, we apply SS, EM, and NFM to the first view, and use SS + GD + NFM for the second congruent view. By doing so, our model can encode both the local and global information through the contrastive learning.

3.2 Cross-Network Contrastive Learning

In MERIT, we introduce a Siamese architecture, which consists of two identical encoders (i.e., gθ, pθ, gζ, and pζ) with an extra predictor qθ on top of the online encoder, as shown in Figure 1. We first take node representations from one view in the online network as the anchor, then we maximize the cosine similarity to the corresponding representations from another view in the target network to form the basic bootstrapping contrastiveness.

This contrastive learning process is illustrated in Figure 2(a), where H1 = qθ(Z 1 ) and ˆ Z 2 denotes the representation of ˜ G1 and ˜ G2 from two different networks. Specifically, we use Z 1 = pθ (gθ( ˜ X1, ˜ A1)) and ˆ Z 2 = pζ (gζ( ˜ X2, ˜ A2)) to denote the output node embeddings of our online and target encoder for the view 1 and 2. The red dash line between two v1 nodes represents a positive pair (h1v1 , ˆ z2 v1 )+ constructed based on v1. The intuition behind is to pull closer the representations of the same node from different views across

0#

!"

!!

!#

!$

21$

!"

!!

Positive pair Negative pairs

(a) Cross-network contrastive-

ness.

Figure 2: Cross-network contrastive learning is based on pairs from two different representations in the online and target network. Differently, cross-view contrastiveness discriminates the pair representations from two views in the same (i.e., online) network.

two networks to distill the knowledge from historical observations, as well as stabilizing the online encoder training. To facilitate this, our target network does not directly receive the gradient during the training. Instead, we update its parameters by leveraging the momentum updating mechanism:

where m, ζ, and θ are momentum, target network parameters, and online network parameters, respectively.

To further explore the rich contrastive relations between node representations within H1 and ˆ Z2, we construct extra negative samples to regularize the basic bootstrapping loss, which are the blue dash lines between the red anchor node and blue nodes in Figure 2(a), i.e., (h1v1 , ˆ z2 vj )-, where we aim to push away from each other. Thus, the aforementioned processes can be formulated with the following loss functions:

In above formulas, L1cn and L2cn are two symmetric losses, which represent the multi-scale cross-network contrastiveness on different views. Besides, h1vi ∈ H1 , h2vi ∈ H2 , ˆ z1 vi ∈ ˆ Z 1 , ˆ z2 vi ∈ ˆ Z 2 , and sim(·) denotes the cosine similarity. Finally, by combining above two losses, we have our final cross-network contrastive objective function defined below:

3.3 Cross-ViewContrastive Learning

Apart from the contrastive relations across two networks, the ties between two views within the online network have not been considered yet, which acts as a strong regularization to enhance the learning ability of our method. We do not have to include such contrastive relations within the target network because it will not directly receive the gradient, and our end goal is to train gθ within the online encoder. Figure 2(b) illustrates our cross-view contrastiveness design, which consists

!#

!$

of two discrimination schemes from two perspectives, namely the intra- and inter-view contrastiveness. Similar to but different from GRACE [Zhu et al., 2020], we apply such contrastive learning on the top of differently-augmented views, where we consider not only the local structural and attributive augmentations (e.g., edge modification and feature masking) but also the global topological information injected via the graph diffusion.

We start from the inter-view contrastiveness, which pulls closer the representations of the same nodes in two augmented views while pushing other nodes away, as depicted by the red and blue dash lines in Figure 2(b). In this case, we define our positive and negative pairs as (h1v1 , h2v1 )+ and (h1v1 , h2vj )-. Similar to the objective functions used in the previous section, the inter-view contrastive loss Linter for view 1 can be formulated as:

We can obtain L2inter (vi) in similar way for view 2. On the other hand, as the red and green dash lines shown in Figure 2(b), the intra-view contrastiveness regards all nodes except the anchor node (i.e., v1) as negatives within a particular view, denoted as (h1v1 , h1vj )-. Thus, the intra-view contrastive loss Lintra for view 1 can be constructed below, which shares the same positive pairs with our inter-view contrastive losses:

where Φ denotes the accumulated similarity of negative pairs in the intra-view contrastive learning. Similarly, we can calculate L2intra (vi) for view 2.

By combining the inter- and intra-view contrastiveness of both views, we have our cross-view contrastive objective function Lcv formulated below:

where L1cv (vi) and L2cv (vi) are two symmetric losses that represent the multi-scale cross-view contrasitveness on the two views:

3.4 Model Training

To train our model end-to-end and learn node representations for downstream tasks, we jointly leverage both the cross-view and cross-network contrastive loss. Specifically, the overall objective function is defined as:

where we aim to minimize L during the optimization, and β is a balance factor. During the inference, we aggregate the representations generated by the online graph encoder gθ, taking both the graph adjacency and diffusion matrices as inputs: ˜H = H1 + H2 ∈ RN×D′ , for downstream tasks.

4 Experiment

To evaluate the effectiveness of MERIT on self-supervised node representation learning, we conduct extensive experiments on five widely used benchmark datasets, including Cora, CiteSeer, PubMed, Amazon Photo [Shchur et al., 2018], and Coauthor CS [Shchur et al., 2018]. The dataset statistics are summarized in Table 1.

4.1 Experimental Settings

For simplicity, we adopt a 1-layer GCN [Kipf and Welling, 2017a] as our backbone graph encoders (i.e., gθ and gζ). For model tuning, we perform the grid search on primary hyperparameters over certain ranges. The latent dimension of graph encoders, projectors, and the predictor is fixed to 512. We tune momentum m and augmentation ratio P between 0 and 1. To balance the effect of two contrastive schemes, we tune β within {0.2, 0.4, 0.6, 0.8}.

To evaluate the trained graph encoder, we adopt a linear evaluation protocol by training a separate logistic regression classifier on top of the learned node representations. For Cora, Citeseer and PubMed, we follow the same data splits as in [Yang et al., 2016]. For Amazon Photo and Coauthor CS, we include 30 randomly-selected nodes per class to construct the training and validation set, while using the remaining nodes as the testing set. We repeat the experiments in Table 2 and 3 ten times and report the average accuracy with the standard deviation.

4.2 Classification Results

We choose node classification as our downstream task and compare MERIT with five supervised methods and four stateof-the-arts graph contrastive learning models. For supervised baselines, we select LP [Zhu et al., 2003], ChebConv [Defferrard et al., 2016], GCN [Kipf and Welling, 2017a], GAT [Veliˇckovi´c et al., 2018], and SGC [Wu et al., 2019]. DGI [Veliˇckovi´c et al., 2019], MVGRL [Hassani and Khasahmadi, 2020], GMI [Peng et al., 2020], and GRACE [Zhu et al., 2020] are chosen as the self-supervised competitors. We report the overall classification results in Table 2 and highlight the best performance in bold.

We can observe from the table that MERIT achieves the best classification accuracy on all five datasets, surpassing not only the self-supervised but also supervised methods (except a draw with GMI on PubMed). This result can be attributed to two key components in our framework: (1). Different from the compared GCL methods, we introduce a more expressive Siamese architecture to help the graph encoder distill the knowledge from historical representations and alleviate the reliance on negative samples. (2). To further realise the potential of our model, we introduce multiple contrastive routes within and across different views and networks, which not only provide a stronger regularization to our bootstrapping objective but also enrich the self-supervision signals during the optimization.

By comparing the best performances of selected supervised and self-supervised baselines, we observe that contrastive learning-based models have achieved similar or even better classification accuracy in more than one datasets, which demonstrates the effectiveness of mining rich multi-scale contrastive relations in graphs. However, there still exist performance gaps between state-of-the-art graph contrastive learning and supervised methods in Cora and Coauthor CS.

4.3 Parameter Sensitivity Study

Balance factor β andmomentumm. We study two important hyper-parameters, the balance factor β in our final objective function (i.e., Equation 11) and the momentum term m in Equation 3. In Figure 3, for a fixed momentum value, we observe that a β value between 0.4 and 0.6 typically produces the best accuracies, which confirms our conjecture that the two proposed contrastive losses can regularize each other and achieve better results than only optimizing one of them (i.e., β = 0 or β = 1), where we give a detailed analyze in our ablation study. On the other hand, for a certain β value, we find that m = 1 usually gives a poor performance, comparing with other values between 0 and 0.999 as recommended in BYOL [Grill et al., 2020] and SimSiam [Chen and He, 2021]. We conjecture that making the parameters stale in the target network may hinder the process of knowledge distillation and thus disturb the model optimization. Another interesting finding here is that our model even performs better when m = 0. Our hypothesis is that the real effective components in bootstrapping are the predictor and stop gradient in our framework, which we leave to research in further work.

Effect of augmentation. Apart from m and β, augmentation plays a critical role in contrastive learning. Comparing the red and blue lines in Figure 4(a), we observe that jointly considering the structure and attributive augmentations gives the best performance. When applying the edge modification only, we surprisingly find that a higher modification ratio

gives a better performance. We conjecture that this is caused

by the nature of contrastive learning, which requires a more Modification Ratio challenging pretext task to achieve competitive performance. When considering multi-scale augmentations, e.g., combining edge and node feature modification, overly increasing the modification ratio may distort the underlying topological and attributive information, thus leading to significant performance degrade. The effectiveness of graph diffusion can be observed in Figure 4(b), where α = 0.05 gives the best performance in our experiments. When removing this module (i.e., α = 0), the performance decreases dramatically, which confirms our hypothesis that injecting global information further boosts the expressive ability of our model.

(a) Study on structural and attributive graph augmentations. (b) Effect of graph diffusion on performance.

Table 3: Ablation study on CiteSeer and Amazon Photo

4.4 Ablation Study

To validate the effectiveness of the two contrastive components, we conduct experiments on Citesser and Amazon Photo for two MERIT variants, each of which has one of the key components removed. The result is presented in Table 3. Here we use MERIT w/o cross-network and MERIT w/o cross-view to denote the ablated model with cross-network loss Lcn or cross-view loss Lcv being masked.

From Table 3, we can find that our model performance would degrade without one of the key components on the two datasets, which demonstrates the effectiveness of our two contrastive schemes. Specifically, our proposed model can boost MERIT w/o cross-view with 0.4% and 0.3% improvement, and MERIT w/o cross-network with 0.2% and 0.4% improvement for CiteSeer and Amazon Photo, respectively. This improvement can be attributed to our comprehensive multi-scale contrastive learning scheme, which takes the advantage of both single- and multiple-network contrastiveness.

Visualisation. To show the superiority of our model, we visualize the node embeddings of CiteSeer calculated by GCN, DGI, and MERIT via the t-SNE algorithm, in which node colors denote different classes. In Figure 5, MERIT's 2D projection presents a clearer separation, which indicates that our approach benefits the graph encoder to extract more expressive node representations for downstream tasks.

5 Conclusion

In this paper, we present a novel approach towards selfsupervised graph representation learning. By leveraging the backbone Siamese GNNs, we design a cross-network contrastiveness to distill the knowledge from historical representations to guide and stabilize the training of online graph encoder. To further enrich the self-supervision signals, we introduce another cross-view contrastive objective on multiple scales to regularize the bootstrapping scheme in the crossnetwork contrastiveness. Experimental results demonstrate the superiority and the effectiveness of our method.