GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training

Introduction

Representative graph structural patterns are universal and transferable across networks.

Over the past two decades, the main focus of network science research has been on discovering and abstracting the universal structural properties underlying different networks. For example, Barabasi and Albert show that several types of networks, e.g., World Wide Web, social, and biological networks, have the scale-free property, i.e., all of their degree distributions follow a power law (Albert and Barabási, 2002). Leskovec et al. (2005) discover that a wide range of real graphs satisfy the densification and shrinking laws. Other common patterns across networks include small world (Watts and Strogatz, 1998), motif distribution (Milo et al., 2004), community organization (Newman, 2006), and core-periphery structure (Borgatti and Everett, 2000), validating our hypothesis at the conceptual level.

In the past few years, however, the paradigm of graph learning has been shifted from structural pattern discovery to graph representation learning (Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016; Dong et al., 2017; Kipf and Welling, 2017; Qiu et al., 2018a; Xu et al., 2019; Qiu et al., 2019), motivated by the recent advances in deep learning (Mikolov et al., 2013; Battaglia et al., 2018). Specifically, graph representation learning converts the vertices, edges, or subgraphs of a graph into low-dimensional embeddings such that vital structural information of the graph is preserved. The learned embeddings from the input graph can be then fed into standard machine learning models for downstream tasks on the same graph.

However, most representation learning work on graphs has thus far focused on learning representations for one single graph or a fixed set of graphs and very limited work can be transferred to out-of-domain data and tasks. Essentially, those representation learning models aim to learn network-specific structural patterns dedicated for each dataset. For example, the DeepWalk embedding model (Perozzi et al., 2014) learned on the Facebook social graph cannot be applied to other graphs. In view of (1) this limitation of graph representation learning and (2) the prior arts on common structural pattern discovery, a natural question arises here: can we universally learn transferable representative graph embeddings from networks?

The similar question has also been asked and pursued in natural language processing (Devlin et al., 2019), computer vision (He et al., 2020), and other domains. To date, the most powerful solution is to pre-train a representation learning model from a large dataset, commonly, under the self-supervised setting. The idea of pre-training is to use the pre-trained model as a good initialization for fine-tuning over (different) tasks on unseen datasets. For example, BERT (Devlin et al., 2019) designs language model pre-training tasks to learn a Transformer encoder (Vaswani et al., 2017) from a large corpus. The pre-trained Transformer encoder is then adapted to various NLP tasks (Wang et al., 2019a) by fine-tuning.

Presented work. Inspired by this and the existence of universal graph structural patterns, we study the potential of pre-training representation learning models, specifically, graph neural networks (GNNs), for graphs. Ideally, given a (diverse) set of input graphs, such as the Facebook social graph and the DBLP co-author graph, we aim to pre-train a GNN on them with a self-supervised task, and then fine-tune it on different graphs for different graph learning tasks, such as node classification on the US-Airport graph. The critical question for GNN pre-training here is: how to design the pre-training task such that the universal structural patterns in and across networks can be captured and further transferred?

In this work, we present the Graph Contrastive Coding (GCC) framework to learn structural representations across graphs. Conceptually, we leverage the idea of contrastive learning (Wu et al., 2018) to design the graph pre-training task as instance discrimination. Its basic idea is to sample instances from input graphs, treat each of them as a distinct class of its own, and learn to encode and discriminate between these instances. Specifically, there are three questions to answer for GCC such that it can learn the transferable structural patterns: (1) what are the instances? (2) what are the discrimination rules? and (3) how to encode the instances?

In GCC, we design the pre-training task as subgraph instance discrimination. Its goal is to distinguish vertices according to their local structures (Cf. Figure 1). For each vertex, we sample subgraphs from its multi-hop ego network as instances. GCC aims to distinguish between subgraphs sampled from a certain vertex and subgraphs sampled from other vertices. Finally, for each subgraph, we use a graph neural network (specifically, the GIN model (Xu et al., 2019)) as the graph encoder to map the underlying structural patterns to latent representations. As GCC does not assume vertices and subgraphs come from the same graph, the graph encoder is forced to capture universal patterns across different input graphs. Given the pre-trained GCC model, we apply it to unseen graphs for addressing downstream tasks.

To the best of our knowledge, very limited work exists in the field of structural graph representation pre-training to date. A very recent one is to design strategies for pre-training GNNs on labeled graphs with node attributes for specific domains (molecular graphs) (Hu et al., 2019b). Another recent work is InfoGraph (Sun et al., 2019), which focuses on learning domain-specific graph-level representations, especially for graph classification tasks. The third related work is by Hu et al. (2019a), who define several graph learning tasks, such as predicting centrality scores, to pre-train a GCN (Kipf and Welling, 2017) model on synthetic graphs.

We conduct extensive experiments to demonstrate the performance and transferability of GCC. We pre-train the GCC model on a collection of diverse types of graphs and apply the pre-trained model to three downstream graph learning tasks on ten new graph datasets. The results suggest that the GCC model achieves competitive or better results to the state-of-the-art task-specific graph representation learning models that are trained from scratch. For example, for node classification on the US-Airport network, GCC pre-trained on the Facebook, IMDB, and DBLP graphs outperforms GraphWave (Donnat et al., 2018), ProNE (Zhang et al., 2019a) and Struc2vec (Ribeiro et al., 2017) which are trained directly on the US-Airport graph, empirically demonstrating our hypothesis at the beginning.

To summarize, our work makes the following four contributions:

We formalize the problem of graph neural network pre-training across multiple graphs and identify its design challenges.

We design the pre-training task as subgraph instance discrimination to capture the universal and transferable structural patterns from multiple input graphs.

We present the Graph Contrastive Coding (GCC) framework to learn structural graph representations, which leverages contrastive learning to guide the pre-training.

We conduct extensive experiments to demonstrate that for out-of-domain tasks, GCC can offer comparable or superior performance over dedicated graph-specific models.

Related Work

In this section, we review related work of vertex similarity, contrastive learning and graph pre-training.

Quantifying similarity of vertices in networks/graphs has been extensively studied in the past years. The goal of vertex similarity is to answer questions (Leicht et al., 2006) like “How similar are these two vertices?” or “Which other vertices are most similar to these vertices?” The definition of similarity can be different in different situations. We briefly review the following three types of vertex similarity.

Neighborhood similarity. The basic assumption of neighborhood similarity, a.k.a., proximity, is that vertices closely connected should be considered similar. Early neighborhood similarity measures include Jaccard similarity (counting common neighbors), RWR similarity (Pan et al., 2004) and SimRank (Jeh and Widom, 2002), etc. Most recently developed network embedding algorithms, such as LINE (Tang et al., 2015), DeepWalk (Perozzi et al., 2014), node2vec (Grover and Leskovec, 2016), also follow the neighborhood similarity assumption.

Structural similarity. Different from neighborhood similarity which measures similarity by connectivity, structural similarity doesn’t even assume vertices are connected. The basic assumption of structural similarity is that vertices with similar local structures should be considered similar. There are two lines of research about modeling structural similarity. The first line defines representative patterns based on domain knowledge. Examples include vertex degree, structural diversity (Ugander et al., 2012), structural hole (Burt, 2009), k-core (Alvarez-Hamelin et al., 2006), motif (Milo et al., 2002; Benson et al., 2016), etc. Consequently, models of this genre, such as Struc2vec (Ribeiro et al., 2017) and RolX (Henderson et al., 2012), usually involve explicit featurization. The second line of research leverages the spectral graph theory to model structural similarity. A recent example is GraphWave (Donnat et al., 2018). In this work, we focus on structural similarity. Unlike the above two genres, we adopt contrastive learning and graph neural networks to learn structural similarity from data.

Attribute similarity. Real world graph data always come with rich attributes, such as text in citation networks, demographic information in social networks, and chemical features in molecular graphs. Recent graph neural networks models, such as GCN (Kipf and Welling, 2017), GAT (Veličković et al., 2018), GraphSAGE (Hamilton et al., 2017; Ying et al., 2018) and MPNN (Gilmer et al., 2017), leverage additional attributes as side information or supervised signals to learn representations which are further used to measure vertex similarity.

2. Contrastive Learning

Contrastive learning is a natural choice to capture similarity from data. In natural language processing, Word2vec (Mikolov et al., 2013) model uses co-occurring words and negative sampling to learn word embeddings. In computer vision, a large collection of work (Hadsell et al., 2006; Wu et al., 2018; He et al., 2020; Tian et al., 2019) learns self-supervised image representation by minimizing the distance between two views of the same image. In this work, we adopt the InfoNCE loss from Oord et al. (2018) and instance discrimination task from Wu et al. (2018), as discussed in Section 3.

3. Graph Pre-Training

Skip-gram based model. Early attempts to pre-train graph representations are skip-gram based network embedding models inspired by Word2vec (Mikolov et al., 2013), such as LINE (Tang et al., 2015), DeepWalk (Perozzi et al., 2014), node2vec (Grover and Leskovec, 2016), and metapath2vec (Dong et al., 2017). Most of them follow the neighborhood similarity assumption, as discussed in section 2.1. The representations learned by the above methods are tied up with graphs used to train the models, and can not handle out-of-sample problems. Our Graph Contrastive Coding (GCC) differs from these methods in two aspects. First, GCC focuses on structural similarity, which is orthogonal to neighborhood similarity. Second, GCC can be transferred across graphs, even to graphs never seen during pre-training.

Pre-training graph neural networks. There are several recent efforts to bring ideas from language pre-training (Devlin et al., 2019) to pre-training graph neural networks (GNN). For example, Hu et al. (2019b) pre-train GNN on labeled graphs, especially molecular graphs, where each vertex (atom) has an atom type (such as C, N, O), and each edge (chemical bond) has a bond type (such as the single bond and double bond). The pre-training task is to recover atom types and chemical bond types in masked molecular graphs. Another related work is by Hu et al. (2019a), which defines several graph learning tasks to pre-train a GCN (Kipf and Welling, 2017). Our GCC framework differs from the above methods in two aspects. First, GCC is for general unlabeled graphs, especially social and information networks. Second, GCC does not involve explicit featurization and pre-defined graph learning tasks.

Graph Contrastive Coding (GCC)

In this section, we formalize the graph neural network (GNN) pre-training problem. To address it, we present the Graph Contrastive Coding (GCC) framework. Figure 2 presents the overview of GCC’s pre-training and fine-tuning stages.

Conceptually, given a collection of graphs from various domains, we aim to pre-train a GNN model to capture structural patterns across these graphs in a self-supervised manner. The model should be able to benefit downstream tasks on different datasets. The underlying assumption is that there exist common and transferable structural patterns, such as motifs, across different graphs, as evident in network science literature (Milo et al., 2002; Leskovec et al., 2005). One illustrative scenario is that we pre-train a GNN model on Facebook, IMDB, and DBLP graphs with self-supervision, and apply it on the US-Airport network for node classification, as shown in Figure 2.

Formally, the GNN pre-training problem is to learn a function $f$ that maps a vertex to a low-dimensional feature vector, such that $f$ has the following two properties:

First, structural similarity, it maps vertices with similar local network topologies close to each other in the vector space;

Second, transferability, it is compatible with vertices and graphs unseen during pre-training.

As such, the embedding function $f$ can be adopted in various graph learning tasks, such as social role prediction, node classification, and graph classification.

Note that the focus of this work is on structural representation learning without node attributes and node labels, making it different from the common problem setting in graph neural network research. In addition, the goal is to pre-train a structural representation model and apply it to unseen graphs, differing from traditional network embeddings (Perozzi et al., 2014; Tang et al., 2015; Grover and Leskovec, 2016; Qiu et al., 2019, 2018a) and recent attempts on pre-training graph neural networks with attributed graphs as input and applying them within a specific domain (Hu et al., 2019b).

2. GCC Pre-Training

Given a set of graphs, our goal is to pre-train a universal graph neural network encoder to capture the structural patterns behind these graphs. To achieve this, we need to design proper self-supervised tasks and learning objectives for graph structured data.

Inspired by the recent success of contrastive learning in CV (Wu et al., 2018; He et al., 2020) and NLP (Mikolov et al., 2013; Clark et al., 2019), we propose to use subgraph instance discrimination as our pre-training task and InfoNCE (Oord et al., 2018) as our learning objective. The pre-training task treats each subgraph instance as a distinct class of its own and learns to discriminate between these instances. The promise is that it can output representations that captures the similarities between these subgraph instances (Wu et al., 2018; He et al., 2020).

From a dictionary look-up perspective, given an encoded query $\bm{q}$ and a dictionary of $K+1$ encoded keys $\{\bm{k}_{0},\cdots,\bm{k}_{K}\}$, contrastive learning looks up a single key (denoted by $\bm{k}_{+}$) that $\bm{q}$ matches in the dictionary. In this work, we adopt InfoNCE such that:

where $\tau$ is the temperature hyper-parameter. $f_{q}$ and $f_{k}$ are two graph neural networks that encode the query instance $x^{q}$ and each key instance $x^{k}$ to $d$-dimensional representations, denoted by $\bm{q}=f_{q}(x^{q})$ and $\bm{k}=f_{k}(x^{k})$.

To instantiate each component in GCC, we need to answer the following three questions:

Q1: How to define subgraph instances in graphs?

Q2: How to define (dis) similar instance pairs in and across graphs, i.e., for a query $x^{q}$, which key $x^{k}$ is the matched one?

Q3: What are the proper graph encoders $f_{q}$ and $f_{k}$?

It is worth noting that in our problem setting, $x^{q}$ and $x^{k}$’s are not assumed to be from the same graph. Next we present the design strategies for the GCC pre-training framework by correspondingly answering the aforementioned questions.

Q1: Design (subgraph) instances in graphs. The success of contrastive learning framework largely relies on the definition of the data instance. It is straightforward for CV and NLP tasks to define an instance as an image or a sentence. However, such ideas cannot be directly extended to graph data, as instances in graphs are not clearly defined. Moreover, our pre-training focus is purely on structural representations without additional input features/attributes. This leaves the natural choice of a single vertex as an instance infeasible, as it is not applicable to discriminate between two vertices.

To address this issue, we instead propose to use subgraphs as contrastive instances by extending each single vertex to its local structure. Specifically, for a certain vertex $v$, we define an instance to be its $r$-ego network:

A $r$-ego network. Let $G=(V,E)$ be a graph, where $V$ denotes the set of vertices and $E\subseteq V\times V$ denotes the set of edgesIn this work, we consider undirected edges.. For a vertex $v$, its $r$-neighbors are defined as $S_{v}=\{u:d(u,v)\leq r\}$ where $d(u,v)$ is the shortest path distance between $u$ and $v$ in the graph $G$. The $r$-ego network of vertex $v$, denoted by $G_{v}$, is the sub-graph induced by $S_{v}$.

The left panel of Figure 3 shows two examples of 2-ego networks. GCC treats each $r$-ego network as a distinct class of its own and encourages the model to distinguish similar instances from dissimilar instances. Next, we introduce how to define (dis)similar instances.

Q2: Define (dis)similar instances. In computer vision (He et al., 2020), two random data augmentations (e.g., random crop, random resize, random color jitering, random flip, etc) of the same image are treated as a similar instance pair. In GCC, we consider two random data augmentations of the same $r$-ego network as a similar instance pair and define the data augmentation as graph sampling (Leskovec and Faloutsos, 2006). Graph sampling is a technique to derive representative subgraph samples from the original graph. Suppose we would like to augment vertex $v$’s $r$-ego network ($G_{v}$), the graph sampling for GCC follows the three steps—random walks with restart (RWR) (Tong et al., 2006), subgraph induction, and anonymization (Micali and Zhu, 2016; Jin et al., 2019).

Random walk with restart. We start a random walk on $G$ from the ego vertex $v$. The walk iteratively travels to its neighborhood with the probability proportional to the edge weight. In addition, at each step, with a positive probability the walk returns back to the starting vertex $v$.

Subgraph induction. The random walk with restart collects a subset of vertices surrounding $v$, denoted by $\widetilde{S}_{v}$. The sub-graph $\widetilde{G}_{v}$ induced by $\widetilde{S}_{v}$ is then regarded as an augmented version of the $r$-ego network $G_{v}$. This step is also known as the Induced Subgraph Random Walk Sampling (ISRW).

Anonymization. We anonymize the sampled graph $\widetilde{G}_{v}$ by re-labeling its vertices to be $\{1,2,\cdots,|\widetilde{S}_{v}|\}$, in arbitrary orderVertex order doesn’t matter because most of graph neural networks are invariant to permutations of their inputs (Battaglia et al., 2018)..

We repeat the aforementioned procedure twice to create two data augmentations, which form a similar instance pair $(x^{q}$, $x^{k_{+}})$. If two subgraphs are augmented from different $r$-ego networks, we treat them as a dissimilar instance pair ($x^{q}$, $x^{k}$) with $k\neq k_{+}$. It is worth noting that all the above graph operations—random walk with restart, subgraph induction, and anonymization—are available in the DGL package (Wang et al., 2019b).

Discussion on graph sampling. In random walk with restart sampling, the restart probability controls the radius of ego-network (i.e., $r$) which GCC conducts data augmentation on. In this work, we follow Qiu et al. (2018b) to use 0.8 as the restart probability. The proposed GCC framework is flexible to other graph sampling algorithms, such as neighborhood sampling (Hamilton et al., 2017) and forest fire (Leskovec and Faloutsos, 2006).

Discussion on anonymization. Now we discuss the intuition behind the anonymization step in the above procedure. This step is designed to keep the underlying structural patterns and hide the exact vertex indices. This design avoids learning a trivial solution to subgraph instance discrimination, i.e., simply checking whether vertex indices of two subgraphs match. Moreover, it facilitates the transfer of the learned model across different graphs as such a model is not associated with a particular vertex set.

Q3: Define graph encoders. Given two sampled subgraphs $x^{q}$ and $x^{k}$, GCC encodes them via two graph neural network encoders $f_{q}$ and $f_{k}$, respectively. Technically, any graph neural networks (Battaglia et al., 2018) can be used here as the encoder, and the GCC model is not sensitive to different choices. In practice, we adopt the Graph Isomorphism Network (GIN) (Xu et al., 2019), a state-of-the-art graph neural network model, as our graph encoder. Recall that we focus on structural representation pre-training while most GNN models require vertex features/attributes as input. To bridge the gap, we propose to leverage the graph structure of each sampled subgraph to initialize vertex features. Specifically, we define the generalized positional embedding as follows:

Generalized positional embedding. For each subgraph, its generalized positional embedding is defined to be the top eigenvectors of its normalized graph Laplacian. Formally, suppose one subgraph has adjacency matrix $\bm{A}$ and degree matrix $\bm{D}$, we conduct eigen-decomposition on its normalized graph Laplacian s.t. $\bm{I}-\bm{D}^{-1/2}\bm{A}\bm{D}^{-1/2}=\bm{U}\bm{\Lambda}\bm{U}^{\top}$, where the top eigenvectors in $\bm{U}$ (Von Luxburg, 2007) are defined as generalized positional embedding.

The generalized positional embedding is inspired by the Transformer model in NLP (Vaswani et al., 2017), where the sine and cosine functions of different frequencies are used to define the positional embeddings in word sequences. Such a definition is deeply connected with graph Laplacian as follows.

The Laplacian of path graph has eigenvectors: $\bm{u}_{k}(i)=\cos{(\pi ki/n-\pi k/2n)}$, for $1\leq k\leq n,1\leq i\leq n$. Here $n$ is the number of vertices in the path graph, and $\bm{u}_{k}(i)$ is the entry at $i$-th row and $k$-the column of $\bm{U}$, i.e., $\bm{U}=\begin{bmatrix}\bm{u}_{1}&\cdots&\bm{u}_{n}\end{bmatrix}$.

The above fact shows that the positional embedding in sequence models can be viewed as Laplacian eigenvectors of path graphs. This inspires us to generalize the positional embedding from path graphs to arbitrary graphs. The reason for using the normalized graph Laplacian rather than the unnormalized version is that path graph is a regular graph (i.e., with constant degrees) while real-world graphs are often irregular and have skewed degree distributions. In addition to the generalized positional embedding, we also add the one-hot encoding of vertex degrees (Xu et al., 2019) and the binary indicator of the ego vertex (Qiu et al., 2018b) as vertex features. After encoded by the graph encoder, the final $d$-dimensional output vectors are then normalized by their L2-Norm (He et al., 2020).

A running example. We illustrate a running example of GCC pre-training in Figure 3. For simplicity, we set the dictionary size to be 3. GCC first randomly augments two subgraphs $x^{q}$ and $x^{k_{0}}$ from a 2-ego network on the left panel of Figure 3. Meanwhile, another two subgraphs, $x^{k_{1}}$ and $x^{k_{2}}$, are generated from a noise distribution — in this example, they are randomly augmented from another 2-ego network on the left panel of Figure 3. Then the two graph encoders, $f_{q}$ and $f_{k}$, map the query and the three keys to low-dimensional vectors — $\bm{q}$ and $\{\bm{k}_{0},\bm{k}_{1},\bm{k}_{2}\}$. Finally, the contrastive loss in Eq. 1 encourages the model to recognize $(x^{q},x^{k_{0}})$ as a similar instance pair and distinguish them from dissimilar instances, i.e., $\{x^{k_{1}},x^{k_{2}}\}$.

Learning. In contrastive learning, it is required to maintain the $K$-size dictionary and encoders. Ideally, in Eq. 1, the dictionary should cover as many instances as possible, making $K$ extremely large. However, due to the computational constraints, we usually design and adopt economical strategies to effectively build and maintain the dictionary, such as end-to-end (E2E) and momentum contrast (MoCo) (He et al., 2020). We discuss the two strategies as follows.

E2E samples mini-batches of instances and considers samples in the same mini-batch as the dictionary. The objective in Eq. 1 is then optimized with respect to parameters of both $f_{q}$ and $f_{k}$, both of which can accept gradient updates by backpropagation consistently. The main drawback of E2E is that the dictionary size is constrained by the batch size.

MoCo is designed to increase the dictionary size without additional backpropagation costs. Concretely, MoCo maintains a queue of samples from preceding mini-batches. During optimization, MoCo only updates the parameters of $f_{q}$ (denoted by $\theta_{q}$) by backpropagation. The parameters of $f_{k}$ (denoted by $\theta_{k}$) are not updated by gradient descent. He et al. (2020) propose a momentum-based update rule for $\theta_{k}$. Formally, MoCo updates $\theta_{k}$ by $\theta_{k}\leftarrow m\theta_{k}+(1-m)\theta_{q}$, where $m\in[0,1)$ is a momentum hyper-parameter. The above momentum update rule gradually propagates the update in $\theta_{q}$ to $\theta_{k}$, making $\theta_{k}$ evolve smoothly and consistently. In summary, MoCo achieves a larger dictionary size at the expense of dictionary consistency, i.e., the key representations in the dictionary are encoded by a smoothly-varying key encoder.

In addition to E2E and MoCo, there are other contrastive learning mechanisms to maintain the dictionary, such as memory bank (Wu et al., 2018). Recently, He et al. (2020) show that MoCo is a more effective option than memory bank in computer vision tasks. Therefore, we mainly focus on E2E and MoCo for GCC.

3. GCC Fine-Tuning

Downstream tasks. Downstream tasks in graph learning generally fall into two categories—graph-level and node-level, where the target is to predict labels of graphs or nodes, respectively. For graph-level tasks, the input graph itself can be encoded by GCC to achieve the representation. For node-level tasks, the node representation can be defined by encoding its $r$-ego networks (or subgraphs augmented from its $r$-ego network). In either case, the encoded representations are then fed into downstream tasks to predict task-specific outputs.

Freezing vs. full fine-tuning. GCC offers two fine-tuning strategies for downstream tasks—the freezing mode and full fine-tuning mode. In the freezing mode, we freeze the parameters of the pre-trained graph encoder $f_{q}$ and treat it as a static feature extractor, then the classifiers catering for specific downstream tasks are trained on top of the extracted features. In the full fine-tuning mode, the graph encoder $f_{q}$ initialized with pre-trained parameters is trained end-to-end together with the classifier on a downstream task. More implementation details about fine-tuning are available in Section 4.2.

GCC as a local algorithm. As a graph algorithm, GCC belongs to the local algorithm category (Spielman and Teng, 2013; Teng et al., 2016), in which the algorithms only involve local explorations of the input (large-scale) network, since GCC explores local structures by random walk based graph sampling methods. Such a property enables GCC to scale to large-scale graph learning tasks and to be friendly to the distributed computing setting.

Experiments

In this section, we evaluate GCC on three graph learning tasks—node classification, graph classification, and similarity search, which have been commonly used to benchmark graph learning algorithms (Yanardag and Vishwanathan, 2015; Ribeiro et al., 2017; Donnat et al., 2018; Xu et al., 2019; Sun et al., 2019). We first introduce the self-supervised pre-training settings in Section 4.1, and then report GCC fine-tuning results on those three graph learning tasks in Section 4.2.

Datasets. Our self-supervised pre-training is performed on six graph datasets, which can be categorized into two groups—academic graphs and social graphs. As for academic graphs, we collect the Academia dataset from NetRep (Ritchie et al., 2016) as well as two DBLP datasets from SNAP (Yang and Leskovec, 2015) and NetRep (Ritchie et al., 2016), respectively. As for social graphs, we collect Facebook and IMDB datasets from NetRep (Ritchie et al., 2016), as well as a LiveJournal dataset from SNAP (Backstrom et al., 2006). Table 1 presents the detailed statistics of datasets for pre-training.

Pre-training settings. We train for 75,000 steps and use Adam (Kingma and Ba, 2015) for optimization with learning rate of 0.005, $\beta_{1}=0.9,\beta_{2}=0.999,\epsilon=1\times 10^{-8}$, weight decay of 1e-4, learning rate warmup over the first $7,500$ steps, and linear decay of the learning rate after $7,500$ steps. Gradient norm clipping is applied with range $$. For MoCo, we use mini-batch size of$32$, dictionary size of$16,384$, and momentum$m$of$0.999$. For E2E, we use mini-batch size of$1,024$. For both MoCo and E2E, the temperature$\tau$is set as$0.07$, and we adopt GIN (Xu et al., 2019) with 5 layers and 64 hidden units each layer as our encoders. Detailed hyper-parameters can be found in Table 6 in the Appendix.

2. Downstream Task Evaluation

In this section, we apply GCC to three graph learning tasks including node classification, graph classification, and similarity search. As prerequisites, we discuss the two fine-tuning strategies of GCC as well as the baselines we compare with.

Fine-tuning. As we discussed in Section 3.3, we adopt two fine-tuning strategies for GCC. We select logistic regression or SVM from the scikit-learn (Pedregosa et al., 2011) package as the linear classifier for the freezing strategy In node classification tasks, we follow Struc2vec to use logistic regression. For graph classification tasks, we follow DGK (Yanardag and Vishwanathan, 2015) and GIN (Xu et al., 2019) to use SVM (Chang and Lin, 2011).. As for the full fine-tuning strategy, we use the Adam optimizer with learning rate 0.005, learning rate warmup over the first 3 epochs, and linear learning rate decay after 3 epochs.

Baselines. Baselines can be categorized into two categories. In the first category, the baseline models learn vertex/graph representations from unlabeled graph data and then feed them into logistic regression or SVM. Examples include DGK (Yanardag and Vishwanathan, 2015), Struc2vec (Ribeiro et al., 2017), GraphWave (Donnat et al., 2018), graph2vec(Narayanan et al., 2017) and InfoGraph (Sun et al., 2019). GCC with the freezing setting belongs to this category. In the second category, the models are optimized in an end-to-end supervised manner. Examples include DGCNN (Zhang et al., 2018) and GIN (Xu et al., 2019). GCC with the full fine-tuning setting belongs to this category.

For a fair comparison, we fix the representation dimension of all models to be 64 except graph2vec and InfoGraphWe allow them to use their preferred dimension size in their papers: graph2vec uses 1024 and InfoGraph uses 512.. The details of baselines will be discussed later.

Setup. The node classification task is to predict unknown node labels in a partially labeled network. To evaluate GCC, we sample a subgraph centered at each vertex and apply GCC on it. Then the obtained representation is fed into an output layer to predict the node label. As for datasets, we adopt US-Airport (Ribeiro et al., 2017) and H-index (Zhang et al., 2019b). US-Airport consists of the airline activity data among 1,190 airports. The 4 classes indicate different activity levels of the airports. H-index is a co-authorship graph extracted from OAG (Zhang et al., 2019b). The labels indicate whether the h-index of the author is above or below the median.

Experimental results. We compare GCC with ProNE (Zhang et al., 2019a), GraphWave (Donnat et al., 2018), and Struc2vec (Ribeiro et al., 2017). Table 2 represents the results. It is worth noting that, under the freezing setting, the graph encoder in GCC is not trained on either US-Airport or H-Index dataset, which other baselines use as training data. This places GCC at a disadvantage. However, GCC (MoCo, freeze) performs competitively to Struc2vec in US-Airport, and achieves the best performance in H-index where Struc2vec cannot finish in one day. Moreover, GCC can be further boosted by fully fine-tuning on the target US-Airport or H-Index domain.

2.2. Graph Classification

Setup. We use five datasets from Yanardag and Vishwanathan (2015)—COLLAB, IMDB-BINARY, IMDB-MULTI, REDDITBINARY and REDDIT-MULTI5K, which are widely benchmarked in recent graph classification models (Hu et al., 2019b; Sun et al., 2019; Zhang et al., 2018). Each dataset is a set of graphs where each graph is associated with a label. To evaluate GCC on this task, we use raw input graphs as the input of GCC. Then the encoded graph-level representation is fed into a classification layer to predict the label of the graph. We compare GCC with several recent developed graph classification models, including Deep Graph Kernel (DGK) (Yanardag and Vishwanathan, 2015), graph2vec (Narayanan et al., 2017), InfoGraph (Sun et al., 2019), DGCNN (Zhang et al., 2018) and GIN (Xu et al., 2019). Among these baselines, DGK, graph2vec and InfoGraph belong to the first category, while DGCNN and GIN belong to the second category.

Experimental results. Table 3 shows the comparison. In the first category, GCC (MoCo, freeze) performs competitively to InfoGraph in IMDB-B and IMDB-M, while achieves the best performance in other datasets. Again, we want to emphasize that DGK, graph2vec and InfoGraph all need to be pre-trained on target domain graphs, but GCC only relies on the graphs listed in Table 1 for pre-training. In the second category, we compare GCC with DGCNN and GIN. GCC achieves better performance than DGCNN and comparable performance to GIN. GIN is a recently proposed SOTA model for graph classification. We follow the instructions in the paper (Xu et al., 2019) to train GIN and report the detailed results in Table 7 in the Appendix. We can see that, in each dataset, the best performance of GIN is achieved by different hyper-parameters. And by varying hyper-parameters, GIN’s performance could be sensitive. However, GCC on all datasets shares the same pre-training/fine-tuning hyper-parameters, showing its robustness on graph classification.

2.3. Top-k𝑘k Similarity Search

Setup. We adopt the co-author dataset from Zhang et al. (2015), which are the conference co-author graphs of KDD, ICDM, SIGIR, CIKM, SIGMOD, and ICDE. The problem of top-$k$ similarity search is defined as follows. Given two graphs $G_{1}$ and $G_{2}$, for example KDD and ICDM co-author graphs, we want to find the most similar vertex $v$ from $G_{1}$ for each vertex $u$ in $G_{2}$. In this dataset, the ground truth is defined to be authors publish in both conferences. Note that similarity search is an unsupervised task, so we evaluate GCC without fine-tuning. Especially, we first extract two subgraphs centered at $u$ and $v$ by random walk with restart graph sampling. After encoding them by GCC, we measure the similarity score between $u$ and $v$ to be the inner product of their representations. Finally, by sorting the above scores, we use HITS@10 (top-10 accuracy) to measure the performance of different methods. We compare GCC with RolX (Henderson et al., 2012), Panther++ (Zhang et al., 2015) and GraphWave (Donnat et al., 2018). We also provide random guess results for reference.

Experimental results. Table 4 presents the performance of different methods on top-$k$ similarity search task in three co-author networks. We can see that, compared with Panther++ (Zhang et al., 2015) and GraphWave (Donnat et al., 2018) which are trained in place on co-author graphs, simply applying pre-trained GCC can be competitive.

Overall, we show that a graph neural network encoder pre-trained on several popular graph datasets can be directly adapted to new graph datasets and unseen graph learning tasks. More importantly, compared with models trained from scratch, the reused model achieves competitive and sometimes better performance. This demonstrates the transferability of graph structural patterns and the effectiveness of our GCC framework in capturing these patterns.

3. Ablation Studies

Effect of pre-training. It is still not clear if GCC’s good performance is due to pre-training or the expression power of its GIN (Xu et al., 2019) encoder. To answer this question, we fully fine-tune GCC with its GIN encoder randomly initialized, which is equivalent to train a GIN encoder from scratch. We name this model GCC (rand), as shown in Table 2 and Table 3. In all datasets except IMDB-B, GCC (MoCo) outperforms its randomly initialized counterpart, showing that pre-training always provides a better start point for fine-tuning than random initialization. For IMDB-B, we attribute it to the domain shift between pre-training data and down-stream tasks.

Contrastive loss mechanisms. The common belief is that MoCo has stronger expression power than E2E (He et al., 2020), and a larger dictionary size $K$ always helps. We also observe such trends, as shown in Figure 4. However, the effect of a large dictionary size is not as significant as reported in computer vision tasks (He et al., 2020). For example, MoCo ($K=16384$) merely outperforms MoCo ($K=1024$) by small margins in terms of accuracy — 1.0 absolute gain in US-Airport and 0.8 absolute gain in COLLAB. However, training MoCo is much more economical than training E2E. E2E ($K=1024$) takes 5 days and 16 hours, while MoCo ($K=16384$) only needs 9 hours. Detailed training time can be found in Table 6 in the Appendix.

Momentum. As mentioned in MoCo (He et al., 2020), momentum $m$ plays a subtle role in learning high-quality representations. Table 5 shows accuracy with different momentum values on US-Airport and COLLAB datasets. For US-Airport, the best performance is reached by $m=0.999$, which is the desired value in (He et al., 2020), showing that building a consistent dictionary is important for MoCo. However, in COLLAB, it seems that a larger momentum value brings better performance. Moreover, we do not observe the “training loss oscillation” reported in (He et al., 2020) when setting $m=0$. GCC (MoCo) converges well, but the accuracy is much worse.

Pre-training datasets. We ablate the number of datasets used for pre-training. To avoid enumerating a combinatorial space, we pre-train with first several datasets in Table 1, and report the 10-fold validation accuracy scores on US-Airport and COLLAB, respectively. For example, when using one dataset for pre-training, we select Academia; when using two, we choose Academia and DBLP (SNAP); and so on. We present ordinary least squares (OLS) estimates of the relationship between the number of datasets and the model performance. As shown in Figure 5, we can observe a trend towards higher accuracy when using more datasets for pre-training. On average, adding one more dataset leads to 0.43 and 0.81 accuracy (%) gain on US-Airport and COLLAB, respectivelyThe effect on US-Airport is positive, but statistically insignificant ($p\text{-value}=0.231$), while the effect on COLLAB is positive and significant ($p\text{-value}\ll 0.001$)..

Conclusion

In this work, we study the pre-training of graph neural networks with the goal of characterizing and transferring structural representations in social and information networks. We present Graph Contrastive Coding (GCC), which is a graph-based contrastive learning framework to pre-train graph neural networks from multiple graph datasets. The pre-trained graph neural network achieves competitive performance to its supervised trained-from-scratch counterparts in three graph learning tasks on ten graph datasets. In the future, we plan to benchmark more graph learning tasks on more diverse graph datasets, such as the protein-protein association networks.

Acknowledgements. The work is supported by the National Key R&D Program of China (2018YFB1402600), NSFC for Distinguished Young Scholar (61825602), and NSFC (61836013).

References

Appendix A Appendix

The experiments are conducted on Linux servers equipped with an Intel(R) Xeon(R) CPU E5-2680 v4 @ 2.40GHz, 256GB RAM and 8 NVIDIA 2080Ti GPUs.

A.1.2. Software Configuration

All models are implemented in PyTorch (Paszke et al., 2019) version 1.3.1, DGL (Wang et al., 2019b) version 0.4.1 with CUDA version 10.1, scikit-learn version 0.20.3 and Python 3.6. Our code and datasets will be available.

A.1.3. Pre-training

The detailed hyper-parameters are listed in Table 6. Training times of GCC variants are listed in Figure 6.The table shows the elapsed real time for pre-training, which might be affected by other programs running on the server. The training time of GCC (E2E) grows sharply with the dictionary size $K$ while GCC (MoCo) roughly remains the same, which indicates that MoCo is more economical and easy to scale with larger dictionary size.

A.2. Baselines

GraphWave (Donnat et al., 2018). We download the authors’ official source code and keep all the training settings as the same. The implementation requires a networkx graph and time points as input. We convert our dataset to the networkx format, and use automatic selection of the range of scales provided by the authors. We set the output embedding dimension to 64.

Code: https://github.com/snap-stanford/graphwave/.

Struc2vec (Ribeiro et al., 2017). We download the authors’ official source code and use default hyper-parameters provided by the authors: (1) walk length = 80; (2) number of walks = 10; (3) window size = 10; (4) number of iterations = 5.

The only modifications we do are: (1) number of dimensions = 64; (2) number of workers = 48 to speed up training.

We find the method hard to scale on the H-index datasets although we set the number of workers to 48, compared to 4 by default. We keep the code running for 24 hours on the H-index datasets and it failed to finish. We observed that the sampling strategy in Struc2vec takes up most of the time, as illustrated in the original paper.

Code: https://github.com/leoribeiro/struc2vec.

ProNE (Zhang et al., 2019a). We download the authors’ official code and keep hyper-parameters as the same: (1) step = 10; (2) $\theta$ = 0.5; (3) $\mu$ = 0.2. The dimension size is set to 64.

A.2.2. Graph Classification

DGK (Yanardag and Vishwanathan, 2015), graph2vec (Narayanan et al., 2017), InfoGraph (Sun et al., 2019), DGCNN (Zhang et al., 2018). We adopt the reported results in these papers. Our experimental setting is exactly the same except for the dimension size. Note that graph2vec uses 1024 and InfoGraph uses 512 as the dimension size. Following GIN, we use 64.

GIN (Xu et al., 2019). We use the official code released by (Xu et al., 2019) and follow exactly the procedure described in their paper: the hyper-parameters tuned for each dataset are: (1) the number of hidden units $\in\{16,32\}$ for bioinformatics graphs and $64$ for social graphs; (2) the batch size $\in\{32,128\}$; (3) the dropout ratio $\in\{0,0.5\}$ after the dense layer; (4) the number of epochs, i.e., a single epoch with the best cross-validation accuracy averaged over the 10 folds was selected. We report the obtained results in Table 7.

Code: https://github.com/weihua916/powerful-gnns.

A.2.3. Top-k𝑘k Similarity Search

Random, RolX (Henderson et al., 2012), Panther++ (Zhang et al., 2015). We obtain the experimental results for these baselines from Zhang et al. (2015).

Code: https://github.com/yuikns/panther/.

GraphWave (Donnat et al., 2018). Embeddings computed by the GraphWave method also have the ability to generalize across graphs. The authors evaluated on synthetic graphs in their paper which are not publicly available. To compare with GraphWave on the co-author datasets, we compute GraphWave embeddings given two graphs $G_{1}\text{ and }G_{2}$ and follow the same procedure mentioned in section 4.2.2 to compute the HITS@10 (top-10 accuracy) score.

Code: https://github.com/snap-stanford/graphwave/.

A.3. Datasets

US-Airport https://github.com/leoribeiro/struc2vec/tree/master/graph. We obtain the US-Airport dataset directly from Ribeiro et al. (2017).

H-index https://www.openacademic.ai/oag/. We create the H-index dataset, a co-authorship graph extracted from OAG (Zhang et al., 2019b). Since the original OAG co-authorship graph has millions of nodes, it is too large as a node classification benchmark. Therefore, we implemented the following procedure to extract smaller subgraphs from OAG:

Select an initial vertex set $V_{s}$ in OAG;

Run breadth first search (BFS) from $V_{s}$ until $N$ nodes are visited;

Return the sub-graph induced by the visited $N$ nodes.

We set $N=5,000$, and randomly select 20 nodes from top 200 nodes with largest degree as he initial vertex set in step (1).

A.3.2. Graph Classification Datasets

We download COLLAB, IMDB-BINARY, IMDB-MULTI, REDDIT-BINARY and REDDIT-MULTI5K from Benchmark Data Sets for Graph Kernels (Kersting et al., 2016).

A.3.3. Top-k𝑘k Similarity Search Datasets

We obtain the paired conference co-author datasets, including KDD-ICDM, SIGIR-CIKM, SIGMOD-ICDE, from the Zhang et al. (2015) and make them publicly available with the permission of the original authors.