What techniques have been proposed to pretrain graph neural networks?
6.3 Pretraining on Graphs
Inspired by the recent success of pretrained lan-
guage models, researchers are starting to explore
pretraining strategies for graph neural networks
(Hu et al., 2020b; Qiu et al., 2020; Hu et al., 2020a).
Famous strategies include graph autoregressive
modeling (Hu et al., 2020b), masked component
modeling (Hu et al., 2020a), graph context predic-
tion (Hu et al., 2020a) and constrastive pretraining
(Qiu et al., 2020; Velickovic et al., 2019; Sun et al.,
2020). These works conduct pretraining for graph
neural network utilizing network structure informa-
tion and do not consider the associated rich textual
signal. However, our work proposes to pretrain the
language model, adopting both textual information
and network structure information.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Graph neural networks (GNNs) have been demonstrated to be powerful in modeling graph-structured data. However, training GNNs usually requires abundant task-specific labeled data, which is often arduously expensive to obtain. One effective way to reduce the labeling effort is to pre-train an expressive GNN model on unlabeled data with self-supervision and then transfer the learned model to downstream tasks with only a few labels. In this paper, we present the GPT-GNN framework to initialize GNNs by generative pre-training. GPT-GNN introduces a self-supervised attributed graph generation task to pre-train a GNN so that it can capture the structural and semantic properties of the graph. We factorize the likelihood of the graph generation into two components: 1) Attribute Generation and 2) Edge Generation. By modeling both components, GPT-GNN captures the inherent dependency between node attributes and graph structure during the generative process. Comprehensive experiments on the billion-scale Open Academic Graph and Amazon recommendation data demonstrate that GPT-GNN significantly outperforms state-of-the-art GNN models without pre-training by up to 9.1% across various downstream tasks.
[{"first":"Ziniu","last":"Hu","middle":[]},{"first":"Yuxiao","last":"Dong","middle":[]},{"first":"Kuansan","last":"Wang","middle":[]},{"first":"Kai-Wei","last":"Chang","middle":[]},{"first":"Yizhou","last":"Sun","middle":[]}]
Deep Graph Infomax
We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised manner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. We demonstrate competitive performance on a variety of node classification benchmarks, which at times even exceeds the performance of supervised learning.
[{"first":"Petar","last":"Velivckovi'c","middle":[]},{"first":"William","last":"Fedus","middle":[]},{"first":"William","last":"Hamilton","middle":["L."]},{"first":"Pietro","last":"Lio","middle":[]},{"first":"Yoshua","last":"Bengio","middle":[]},{"first":"R","last":"Hjelm","middle":["Devon"]}]
Strategies for Pre-training Graph Neural Networks
Many applications of machine learning require a model to make accurate pre-dictions on test examples that are distributionally different from training ones, while task-specific labels are scarce during training. An effective approach to this challenge is to pre-train a model on related tasks where data is abundant, and then fine-tune it on a downstream task of interest. While pre-training has been effective in many language and vision domains, it remains an open question how to effectively use pre-training on graph datasets. In this paper, we develop a new strategy and self-supervised methods for pre-training Graph Neural Networks (GNNs). The key to the success of our strategy is to pre-train an expressive GNN at the level of individual nodes as well as entire graphs so that the GNN can learn useful local and global representations simultaneously. We systematically study pre-training on multiple graph classification datasets. We find that naive strategies, which pre-train GNNs at the level of either entire graphs or individual nodes, give limited improvement and can even lead to negative transfer on many downstream tasks. In contrast, our strategy avoids negative transfer and improves generalization significantly across downstream tasks, leading up to 9.4% absolute improvements in ROC-AUC over non-pre-trained models and achieving state-of-the-art performance for molecular property prediction and protein function prediction.
[{"first":"Weihua","last":"Hu","middle":[]},{"first":"Bowen","last":"Liu","middle":[]},{"first":"Joseph","last":"Gomes","middle":[]},{"first":"Marinka","last":"Zitnik","middle":[]},{"first":"Percy","last":"Liang","middle":[]},{"first":"Vijay","last":"Pande","middle":[]},{"first":"Jure","last":"Leskovec","middle":[]}]
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Graph representation learning has emerged as a powerful technique for addressing real-world problems. Various downstream graph learning tasks have benefited from its recent developments, such as node classification, similarity search, and graph classification. However, prior arts on graph representation learning focus on domain specific problems and train a dedicated model for each graph dataset, which is usually non-transferable to out-of-domain data. Inspired by the recent advances in pre-training from natural language processing and computer vision, we design Graph Contrastive Coding (GCC) -- a self-supervised graph neural network pre-training framework -- to capture the universal network topological properties across multiple networks. We design GCC's pre-training task as subgraph instance discrimination in and across networks and leverage contrastive learning to empower graph neural networks to learn the intrinsic and transferable structural representations. We conduct extensive experiments on three graph learning tasks and ten graph datasets. The results show that GCC pre-trained on a collection of diverse datasets can achieve competitive or better performance to its task-specific and trained-from-scratch counterparts. This suggests that the pre-training and fine-tuning paradigm presents great potential for graph representation learning.
[{"first":"Jiezhong","last":"Qiu","middle":[]},{"first":"Qibin","last":"Chen","middle":[]},{"first":"Yuxiao","last":"Dong","middle":[]},{"first":"Jing","last":"Zhang","middle":[]},{"first":"Hongxia","last":"Yang","middle":[]},{"first":"Ming","last":"Ding","middle":[]},{"first":"Kuansan","last":"Wang","middle":[]},{"first":"Jie","last":"Tang","middle":[]}]
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
This paper studies learning the representations of whole graphs in both unsupervised and semi-supervised scenarios. Graph-level representations are critical in a variety of real-world applications such as predicting the properties of molecules and community analysis in social networks. Traditional graph kernel based methods are simple, yet effective for obtaining ﬁxed-length representations for graphs but they suffer from poor generalization due to hand-crafted designs. There are also some recent methods based on language models (e.g. graph2vec) but they tend to only consider certain substructures (e.g. subtrees) as graph representatives. Inspired by recent progress of unsupervised representation learning, in this paper we proposed a novel method called InfoGraph for learning graph-level representations. We maximize the mutual information between the graph-level representation and the representations of substructures of different scales (e.g., nodes, edges, triangles). By doing so, the graph-level representations encode aspects of the data that are shared across different scales of substructures. Furthermore, we further propose InfoGraph*, an extension of InfoGraph for semi-supervised scenarios. InfoGraph* maximizes the mutual information between unsupervised graph representations learned by InfoGraph and the representations learned by existing supervised methods. As a result, the supervised encoder learns from unlabeled data while preserving the latent semantic space favored by the current supervised task. Experimental results on the tasks of graph classiﬁcation and molecular property prediction show that InfoGraph is superior to state-of-the-art baselines and InfoGraph* can achieve performance competitive with state-of-the-art semi-supervised models
[{"first":"Fan-Yun","last":"Sun","middle":[]},{"first":"Jordan","last":"Hoffmann","middle":[]},{"first":"Vikas","last":"Verma","middle":[]},{"first":"Jian","last":"Tang","middle":[]}]
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The breakthroughs in graph neural networks (GNNs) have revolutionized graph mining from structural feature engineering to representation learning [1,9,17]. Recent GNN developments have been demonstrated to benefit various graph applications and network tasks, such as semi-supervised node classification [17], recommendation systems [42], and knowledge graph inference [28].
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Commonly, GNNs take a graph with attributes as input and apply convolutional filters to generate node-level representations layer by layer. Often, a GNN model is trained with supervised information in an end-to-end manner for one task on the input graph. That said, for different tasks on the same graph, it is required to have enough and different sets of labeled data to train dedicated GNNs corresponding to each task. Usually, it is arduously expensive and sometimes infeasible to access sufficient labeled data for those tasks, particularly for large-scale graphs. Take, for example, the author disambiguation task in academic graphs [34], it has still faced the challenge of the lack of ground-truth to date.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Similar issues had also been experienced in natural language processing (NLP). Recent advances in NLP address them by training a model from a large unlabeled corpus and transferring the learned model to downstream tasks with only a few labels-the idea of pretraining. For example, the pre-trained BERT language model [4] is able to learn expressive contextualized word representations by reconstructing the input text-next sentence and masked language predictions, and thus it can significantly improve the performance of various downstream tasks. Additionally, similar observations have also been demonstrated in computer vision [2,13,35].
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Inspired by these developments, we propose to pre-train graph neural networks for graph mining. The goal of the pre-training is to empower GNNs to capture the structural and semantic properties of a input graph, so that it can easily generalize to any downstream tasks with a few fine-tuning steps on the graphs within the same domain. To achieve this goal, we propose to model the graph distribution by learning to reconstruct the input attributed graph.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
To pre-train GNNs based on graph reconstruction, one straightforward option could be to directly adopt the neural graph generation techniques [16,18,43]. However, they are not suitable for pre-training GNNs by design. First, most of them focus only on generating graph structure without attributes, which does not capture the underlying patterns between node attributes and graph structure-the core of convolutional aggregation in GNNs. Second, they are designed to handle small graphs to date, limiting their potential to pre-train on large-scale graphs. ? initialization with pre-trained parameters * Figure 1: The pre-training and fine-tuning flow of GPT-GNN: First, a GNN is pre-trained with the self-supervised learning task-attribute and structure generations. Second, the pretrained model and its parameters are then used to initialize models for downstream tasks on the input graph or graphs of the same domain.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Contributions. In this work, we design a self-supervised attributed graph generation task for GNN pre-training, with which both the structure and attributes of the graph are modeled. Based on this task, we present the GPT-GNN framework for generative pretraining of graph neural networks (Cf. Figure 1). The pre-trained GNN on the input graph can be then used as the initialization of models for different downstream tasks on the same type of graphs. Specifically, our contributions are illustrated below.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
First, we design an attributed graph generation task to model both node attributes and graph structure. We decompose the graph generation objective into two components: Attribute Generation and Edge Generation, whose joint optimization is equivalent to maximizing the probability likelihood of the whole attributed graph. In doing this, the pre-trained model can capture the inherent dependency between node attributes and graph structure.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Second, we propose an efficient framework GPT-GNN to conduct generative pre-training with the aforementioned task. GPT-GNN can calculate the attribute and edge generation losses of each node simultaneously, and thus only need to run the GNN once for the graph. Additionally, GPT-GNN can handle large-scale graphs with sub-graph sampling and mitigate the inaccurate loss brought by negative sampling with an adaptive embedding queue.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Finally, we pre-train GNNs on two large-scale graphs-the Open Academic Graph (OAG) of 179 million nodes & 2 billion edges and Amazon recommendation data of 113 million nodes. Extensive experiments show that the GPT-GNN pre-training framework can significantly benefit various downstream tasks. For example, by applying the pre-trained model on OAG, the node classification and link prediction performance is on average lifted by 9.1% over the state-of-the-art GNN models without pre-training. In addition, we show that GPT-GNN can consistently improve the performance of different base GNNs under various settings.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The goal of pre-training is to allow a model (usually neural networks) to initialize its parameters with pre-trained weights. In this way, the model can leverage the commonality between the pretraining and downstream tasks. Recently pre-training has shown superiority in boosting the performance of many downstream applications in computer vision and natural language processing. In the following, we first introduce the preliminaries about GNNs and then review pre-training approaches in graphs and other domains.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Recent years have witnessed the success of GNNs for modeling graph data [12,15,17,36]. A GNN can be regarded as using the input graph structure as the computation graph for message passing [9], during which the local neighborhood information is aggregated to get a more contextual representation. Formally, suppose H (l ) t is the node representation of node t at the (l)-th GNN layer, the update procedure from the (l-1)-th layer to the (l)-th layer is:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
where N (t) denotes all the source nodes of node t and E(s, t) denotes all the edges from node s to t.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
There are two basic operators for GNNs, which are Extract(·) and Aggregate(·). Among them, Extract(·) represents the neighbor information extractor. It uses the target node's representation H (l −1) t and the edge e between the two nodes as query, and extract useful information from source node H (l −1) s . Aggregate(·) serves as the aggregation function of the neighborhood information. The mean, sum, and max functions are often considered as the basic aggregation operators, while sophisticated pooling and normalization functions can also be designed. Under this framework, various GNN architectures have been proposed. For example, the graph convolutional network (GCN) proposed by Kipf et al. [17] averages the one-hop neighbor of each node in the graph, followed by a linear projection and then a non-linear activation. Hamilton et al. [12] propose GraphSAGE that generalizes GCN's aggregation operation from average to sum, max and a RNN unit.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Also, there are a bunch of works incorporating the attention mechanism into GNNs. In general, the attention-based models implement the Extract(·) operation by estimating the importance of each source node, based on which a weighted aggregation is applied. For example, Velickovi et al. [36] propose the graph attention network (GAT), which adopts an additive mechanism to calculate attention and uses the same weight for calculating messages. Recently, Hu et al. propose the heterogeneous graph transformer (HGT) [15] that leverages multi-head attentions for different relation types to get type-dependent attentions. The proposed pre-training framework GPT-GNN can apply to all of these GNN models.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Previous studies have proposed to utilize pre-training to learn node representations, which largely belong to two categories. The first category is usually termed as network/graph embedding, which directly parameterizes the node embedding vectors and optimizes them by preserving some similarity measures, such as the network proximity [33] or statistics derived from random walks [6,11,26]. However, the embeddings learned in this way cannot be used to initialize other models for fine-tuning over other tasks. In contrast, we consider a transfer learning setting, where the goal is to pre-train a generic GNN that can deal with different tasks.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
With the increasing focus on GNNs, researchers have explored the direction of pre-training GNNs on unannotated data. Kipf et al.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
propose Variational Graph Auto-Encoders [16] to reconstruct the graph structure. Hamilton et al. propose GraphSAGE [12], which can optimize via an unsupervised loss by using random walk based similarity metric. Velickovic et al. introduce Graph Infomax [37], which maximizes the mutual information between node representations obtained from GNNs and a pooled graph representation. Although these methods show enhancements over purely-supervised learning settings, the learning tasks can be achieved by forcing nearby nodes to have similar embeddings, ignoring the rich semantics and higher-order structure of the graph. Our work proposes to pre-train GNNs by the permutated generative objective, which is a harder graph task and thus can guide the model to learn more complex semantics and structure of the input graph.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
In addition, there are attempts to pre-train GNNs to extract graphlevel representations. Sun et al. present InfoGraph [29], which maximizes the mutual information between graph-level representations obtained from GNNs and the representations of sub-structures. Hu et al. [14] introduce different strategies to pre-train GNNs at both node and graph levels and show that combining them together can improve the performance on graph classification tasks. Our work is different with them as our goal is to pre-train GNNs over a single (large-scale) graph and conduct the node-level transfer.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Pre-training has been widely used in computer vision (CV) and natural language processing (NLP). In CV, early pre-training techniques [5,10,24] mostly follow the paradigm of first pre-training a model on large-scale supervised datasets (such as ImageNet [3]) and then fine-tuning the pre-trained model on downstream tasks [10] or directly extracting the representations as features [5]. Recently, some self-supervised tasks [2,13,35] have also been utilized to pre-train vision models. In NLP, Early works have been focused on learning (shallow) word embeddings [22,25] by leveraging the cooccurrence statistics on the text corpus. More recently, significant progresses have been made on contextualized word embeddings, such as BERT [4], XLNET [41] and GPT [27]. Take BERT as an example, it pre-trains a text encoder with two self-supervised tasks in order to better encode words and their contexts. These pre-training approaches have been shown to yield state-of-the-art performance in a wide range of NLP tasks and thus used as a fundamental component in many NLP systems.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
In this section, we formalize the attributed graph generation task and introduce the generative pre-training framework (GPT-GNN).
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The input to GNNs is usually an attributed graph G = (V, E, X), where V and E denote its node and edge sets, and X represents the node feature matrix. A GNN model learns to output node representations under the supervision of a specific downstream task, such as node classification. Sometimes there exist multiple tasks on a single graph, and most GNNs require sufficient dedicated labeled data for each task. However, it is often challenging to obtain sufficient annotations, in particular for large-scale graphs, hindering the training of a well-generalized GNN. Therefore it is desirable to have a pre-trained GNN model that can generalize with few labels. Conceptually, this model should 1) capture the intrinsic structure and attribute patterns underlying the graph and 2) thus benefit various downstream tasks on this graph.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
GNN Pre-Training. Formally, our goal of GNN pre-training concerns the learning of a general GNN model f θ purely based on single (large-scale) graph G = (V, E, X) without labeled data such that f θ is a good initialization for various (unseen) downstream tasks on the same graph or graphs of the same domain. To learn such a general GNN model without labeled data on the graph, a natural question arises here is: how to design an unsupervised learning task over the graph for pre-training the GNN model?
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Recent advances in self-supervised learning for NLP [4,41] and CV [2,13,35] have shown that unlabeled data itself contains rich semantic knowledge, and thus a model that can capture the data distribution is able to transfer onto various downstream tasks. Inspired by this, we propose GPT-GNN, which pre-trains a GNN by reconstructing/generating the input graph's structure and attributes.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Formally, given an input graph G = (V, E, X) and a GNN model f θ , we model the likelihood over this graph by this GNN as p(G; θ )representing how the nodes in G are attributed and connected. GPT-GNN aims to pre-train the GNN model by maximizing the graph likelihood, i.e., θ * = max θ p(G; θ ).
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Then, the first question becomes how to properly model p(G; θ ). Note that most existing graph generation methods [18,43] follow the auto-regressive manner to factorize the probability objective, i.e., the nodes in the graph come in an order, and the edges are generated by connecting each new arriving node to existing nodes. Similarly, we denote a permutation vector π to determine the node ordering, where i π denotes the node id of i-th position in permutation π . Consequently, the graph distribution p(G; θ ) is equivalent to the expected likelihood over all possible permutations, i.e.,
GPT-GNN: Generative Pre-Training of Graph Neural Networks
where X π ∈ R |V |×d denotes permutated node attributes and E is a set of edges, while E π i denotes all edges connected with node i π . For simplicity, we assume that observing any node ordering π has an equal probability and also omit the subscript π when illustrating the generative process for one permutation in the following sections. Given a permutated order, we can factorize the log likelihood autoregressively-generating one node per iteration-as:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
At each step i, we use all nodes that are generated before i, their attributes X <i , and the structure (edges) between these nodes E <i to generate a new node i, including both its attribute X i and its connections with existing nodes E i . Essentially, the objective in Eq. 2 describes the autoregressive generative process of an attributed graph. The question becomes: how to model the conditional probability p θ (X i , E i |X <i , E <i )? 
GPT-GNN: Generative Pre-Training of Graph Neural Networks
, one naive solution could be to simply assume that X i and E i are independent, that is,
GPT-GNN: Generative Pre-Training of Graph Neural Networks
With such decomposition, for each node, the dependency between its attributes and connections are completely neglected. However, the ignored dependency is the core property of attributed graphs and also the foundation of convolutional aggregation in GNNs. Therefore, such a naive decomposition cannot provide informative guidance for pre-training GNNs.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
To address this issue, we present the dependency-aware factorization mechanism for the attributed graph generation process. Specifically, when estimating a new node's attributes, we are given its structure information, and vice versa. During the process, a part of the edges has already been observed (or generated). Then the generation can be decomposed into two coupled parts:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
• given the observed edges, generate node attributes; • given the observed edges and generated node attributes, generate the remaining edges.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
In this way, the model can capture the dependency between the attributes and structure for each node. Formally, we define a variable o to denote the index vector of all the observed edges within E i . Thus, E i,o denotes the observed edges. Similarly, ¬o denotes the index of all the masked edges, which are to be generated. With this, we can rewrite the conditional probability as an expected likelihood over all observed edges:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
This factorization design is able to model the dependency between node i's attributes X i and its associated connections E i . The first term p θ (X i | E i,o , X <i , E <i ) denotes the generation of attributes for node i. Based on the observed edges E i,o , we gather the target node i's neighborhood information to generate its at-
GPT-GNN: Generative Pre-Training of Graph Neural Networks
denotes the generation of masked edges. Based on both the observed edges E i,o and the generated attributes X i , we generate the representation of the target node i and predict whether each edge within E i,¬o exists.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
A graph generation example. We intuitively show how the proposed factorization-based graph generation process works. Take, for example, an academic graph, if we would like to generate one paper node, whose title is considered as its attribute, while this paper node is connected to its authors, published venue, and cited papers. Based on some observed edges between this paper and some of its authors, our generation process first generates its title. Then, based on both the observed edges and generated title, we predict its remaining authors, published venue, and references. In this way, this process models the interaction between the paper's attribute (title) and structure (observed and remaining edges) to complete the generation task, bringing in informative signals for pre-training GNNs over the academic graph.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
So far, we factorize the attributed graph generation process into a node attribute generation step and an edge generation step. The question we need to answer here is: How to efficiently pre-train GNNs by optimizing both attribute and edge generation tasks?
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For the sake of efficiency, it is desired to compute the loss of attribute and edge generations by running the GNN only once for the input graph. In addition, we expect to conduct attribute generation and edge generation simultaneously. However, edge generation requires node attributes as input, which can be leaked to attribute generation. To avoid information leakage, we design to separate each node into two types:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
• Attribute Generation Nodes. We mask out the attributes of these nodes by replacing their attributes with a dummy token and learn a shared vector X init to represent it † . This is equivalent to the trick of using the [Mask] token in the masked language model [4]. • Edge Generation Nodes. For these nodes, we keep their attributes and put them as input to the GNN. † X ini t has the same dimension as X i and can be learned during pre-training.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We then input the modified graph to the GNN model and generate the output representations. We use h At t r and h Edдe to represent the output embeddings of Attribute Generation and Edge Generation Nodes, respectively. As the attributes of Attribute Generation Nodes are masked out, h At t r in general contains less information than h Edдe . Therefore, when conduct the GNN message passing, we only use Edge Generation Nodes' output h Edдe as outward messages. The representations of the two sets of nodes are then used to generate attributes and edges with different decoders. For Attribute Generation, we denote its decoder as Dec At t r (·), which takes h At t r as input and generates the masked attributes. The modeling choice depends on the type of attributes. For example, if the input attribute of a node is text, we can use the text generator model (e.g., LSTM) to generate it. If the input attribute is a standard vector, we can apply a multi-layer Perceptron to generate it. Also, we define a distance function as a metric between the generated attributes and the real ones, such as perplexity for text or L2-distance for vectors. Thus, we calculate the attribute generation loss via:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
By minimizing the distance between the generated and masked attributes, it is equivalent to maximize the likelihood to observe each node attribute, i.e., p θ (X i | E i,o , X <i , E <i ), and thus the pretrained model can capture the semantic of this graph.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For Edge Generation, we assume that the generation of each edge is independent with others, so that we can factorize the likelihood:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Next, after getting the Edge Generation node representation h Edдe , we model the likelihood that node i is connected with node j by Dec Edдe (h
GPT-GNN: Generative Pre-Training of Graph Neural Networks
where Dec Edдe is a pairwise score function. Finally, we adopt the negative contrastive estimation to calculate the likelihood for each linked node j + . We prepare all the unconnected nodes as S − i and calculate the contrastive loss via
GPT-GNN: Generative Pre-Training of Graph Neural Networks
By optimizing L Edдe , it is equivalent to maximizing the likelihood of generating all the edges, and thus the pre-trained model is able to capture the intrinsic structure of the graph. Figure 2 illustrates the attributed graph generation process. Specifically: (a) We determine the node permutation order π for the input graph. (b) We randomly select a portion of the target node's edges as observed edges E i,o and the remaining as masked edges E i,¬o (grey dashed lines with cross). We delete masked edges in the graph. (c) We separate each node into the Attribute Generation and Edge Generation nodes to avoid information leakage. (d) After the preprocessing, we use the modified adjacency matrix to calculate the representations of node 3,4 and 5, including both their Attribute and Edge Generation Nodes. Finally, as illustrated in (d)-(e), we train the GNN model via the attribute prediction and masked edge prediction task for each node in parallel. The overall pipeline of GPT-GNN is illustrated in Algo. 1 (See Appendix B for details).
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Require: Input Attributed Graph G, Graph Sampler Sampler (·). Ensure:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
1: Initialize the GNN model as f θ , the attribute generation decoder as Dec At t r , and the edge generation decoder as Dec Edдe . 2: Initialize the adaptive node embedding queue Q = {} and the attribute vector h init . 3: for each sampled graphĜ ∈ Sampler (G) do 4: For each node, sample the observed edge index o and masked edges ¬o, and delete masked edges E i,¬o accordingly. 5: Separate each node into the Attribute Generation and Edge Generation nodes. Replace the input to Attribute Generation node as h init . Apply GNN f θ to get two sets of node embeddings h At t r and h Edдe for each node in the graph. 6: for node i with attributes X i and masked edges E i,¬o do 7:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Calculate the attribute generation loss L At t r by Eq. 4 8: Prepare negative samples S − i for edge generation by concatenating unconnected nodes and adaptive queue Q.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Calculate the edge generation loss L Edдe by Eq. 6 10: end for 11: Optimize θ by minimizing L At t r and L Edдe . 12: Update Q by adding in h Edдe and popping out most outdated embeddings. 13: end for 14: return Pre-trained model parameters θ * for downstream tasks
GPT-GNN: Generative Pre-Training of Graph Neural Networks
In this section, we discuss how to apply GPT-GNN to pre-train for large-scale and heterogeneous graphs, which can be of practical use for modeling real-world complex systems [7,30], such as academic graphs, product graphs, IoT networks, and knowledge graphs.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Heterogeneous graphs. Many real-world graphs are heterogeneous, meaning that they contain different types of nodes and edges. For heterogeneous graphs, the proposed GPT-GNN framework can be straightforwardly applied to pre-train heterogeneous GNNs. The only difference is that each type of nodes and edges may have its own decoder, which is specified by the heterogeneous GNNs rather than the pre-training framework. All the other components remain exactly the same.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Large-scale graphs. To pre-train GNNs on graphs that are too large to fit into the hardware, we sample subgraphs for training. In particular, we propose to sample a dense subgraph from homogeneous and heterogeneous graphs by using the LADIES algorithm [45] and its heterogeneous version HGSampling [15], respectively. Both methods theoretically guarantee that the sampled nodes are highly interconnected with each other and maximally preserve the structural information.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
To estimate the contrastive loss in Eq. 6, it is required to go over all nodes of the input graph. However, we only have access to the sampled nodes in a subgraph for estimating this loss, making the (self-)supervision only focus on local signals. To alleviate this issue, we propose the Adaptive Queue, which stores node representations in previously-sampled subgraphs as negative samples. Each time we process a new subgraph, we progressively update this queue by adding the latest node representations and remove the oldest ones. As the model parameters will not be updated rigorously, the negative samples stored in the queue are consistent and accurate. The Adaptive Queue enables us to use much larger negative sample pools S − i . Moreover, the nodes across different sampled sub-graphs can bring in the global structural guidance for contrastive learning.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
To evaluate the performance of GPT-GNN, we conduct experiments on the Open Academic Graph (OAG) and Amazon Recommendation datasets. To evaluate the generalizability of GPT-GNN, we consider different transfer settings-time transfer and field transfer-which are of practical importance.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Datasets and Tasks. We conduct experiments on both heterogeneous and homogeneous graphs. For heterogeneous graphs, we use the Open Academic Graph and Amazon Review Recommendation data. For homogeneous graphs, we use the Reddit dataset [12] and the paper citation network extracted from OAG. All datasets are publicly available and the details can be found in Appendix A.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Open Academic Graph (OAG) [34,38,44] contains more than 178 million nodes and 2.236 billion edges. It is the largest publicly available heterogeneous academic dataset to date. Each paper is labeled with a set of research topics/fields (e.g., Physics and Medicine) and the publication date ranges from 1900 to 2019. We consider the prediction of Paper-Field, Paper-Venue, and Author Name Disambiguation (Author ND) as three downstream tasks [7,15]. The performance is evaluated by MRR-a widely adopted ranking metric [19].
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Amazon Review Recommendation Dataset (Amazon) [23] contains 82.8 million reviews, 20.9 million users, and 9.3 million products. The reviews are published from 1996 to 2018. Each review consists of a discrete rating score from 1 to 5 and a specific field, including book, fashion, etc. For downstream tasks, we predict the rating score as a five-class classification task within the Fashion, Beauty, and Luxury fields. We use micro F1-score as the evaluation metric.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The base GNN model. On the OAG and Amazon datasets, we use the state-of-the-art heterogeneous GNN-Heterogeneous Graph Transformer (HGT) [15]-as the base model for GPT-GNN. Furthermore, we also use other (heterogeneous) GNNs as the base model to test our generative pre-training framework.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Implementation details. For all base models, we set the hidden dimension as 400, the head number as 8, and the number of GNN layers as 3. All of them are implemented using the PyTorch Geometric (PyG) package [8].
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We optimize the model via the AdamW optimizer [21] with the Cosine Annealing Learning Rate Scheduler [20] with 500 epochs and select the one with the lowest validation loss as the pre-trained model. We set the adaptive queue size to be 256.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
During downstream evaluation, we fine-tune the model using the same optimization setting for 200 epochs as that in pre-training. We train the model on the downstream tasks for five times and report the mean and standard deviation of test performance.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Pre-training baselines. There exist several works that propose unsupervised objectives over graphs, which can potentially be used to pre-train GNNs. We thus compare the proposed GPT-GNN framework with these baselines:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
• GAE [16], which denotes graph auto-encoders, focuses on a traditional link prediction task. It randomly masks out a fixed proportion of the edges and asks the model to reconstruct these masked edges. • GraphSAGE (unsp.) [12] forces connected nodes to have similar output node embeddings. Its main difference with GAE lies in that it does not mask out the edges during pre-training. • Graph Infomax [37] tries to maximize the local node embeddings with global graph summary embeddings. Following its setting for a large-scale graph, for each sampled subgraph, we shuffle the graph to construct negative samples. In addition, we also evaluate the two pre-training tasks in GPT-GNN by using each one of them alone, that is, attribute generation-GPT-GNN (Attr)-and edge generation-GPT-GNN (Edge).
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The goal of pre-training is to transfer knowledge learned from numerous unlabeled nodes of a large graph to facilitate the downstream tasks with a few labels. Specifically, we first pre-train a GNN and use the pre-trained model weights to initialize models for downstream tasks. We then fine-tune the models with the downstream task specific decoder on the training (fine-tuning) set and evaluate the performance on the test set.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Broadly, there are two different setups. The first one is to pretrain and fine-tune on exactly the same graph. The second one is relatively more practical, which is to pre-train on one graph and fine-tune on unseen graphs of the same type as the pre-training one. Specifically, we consider the following three graph transfer settings between the pre-training and fine-tuning stages:
GPT-GNN: Generative Pre-Training of Graph Neural Networks
• Time Transfer, where we use data from different time spans for pre-training and fine-tuning. For both OAG and Amazon, we use data before 2014 for pre-training and data since 2014 for fine-tuning. • Field Transfer, where we use data from different fields for pre-training and evaluating. In OAG, we use papers in the field of computer science (CS) for downstream fine-tuning and use all papers in the remaining fields (e.g., Medicine) for pre-training. In Amazon, we pre-train on products in Arts, Crafts, and Sewing, and fine-tune on products in Fashion, Beauty, and Luxury. • Time + Field Transfer, where we use the graph of particular fields before 2014 to pre-train the model and use the data from other fields since 2014 for fine-tuning. Intuitively, this combined transfer setting is more challenging than the transfer of time or field alone. For example, we pre-train on the OAG graph except CS field before 2014 and fine-tune on the CS graph since 2014. During fine-tuning, for both datasets, we choose nodes from 2014 to 2016 for training, 2017 for validation, and since 2018 for testing. To meet the assumption that training data is usually scarce, we only provide 10% of the labels for training (fine-tuning) by default, while the ablation study over different data percentages is also conducted.  [15] as the base model. 10% of labeled data is used for fine-tuning.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
During pre-training, we randomly select a subset of the data as the validation set.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We summarize the performance of downstream tasks with different pre-training methods on OAG and Amazon in Table 1. As discussed above, we setup three different transfer settings between pre-training and fine-tuning stages: Field Transfer, Time Transfer, and Field + Time Combined Transfer, as organized in three different blocks in the Table. Overall, the proposed GPT-GNN framework significantly enhances the performance for all downstream tasks on both datasets. On average, GPT-GNN achieves relative performance gains of 13.3% and 5.7% over the base model without pre-training on OAG and Amazon, respectively. Moreover, it consistently outperforms other pre-training frameworks, such as Graph Infomax, across different downstream tasks for all three transfer settings on both datasets. Table 1, the performance gain lifted by pre-training under the field transfer is higher than that under the time transfer, and the time + field combined transfer is the most challenging setting as evident in the least performance gain brought by pre-training. Nonetheless, under the combined transfer, GPT-GNN still achieves 11.7% and 4.6% performance gains on both datasets, respectively. Altogether, the results suggest that the proposed generative pre-training strategy enables the GNN model to capture the generic structural and semantic knowledge of the input graph, which can be used to fine-tune on the unseen part of the graph data.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Ablation studies on pre-training tasks. We analyze the effectiveness of the two pre-training tasks in GPT-GNN-attribute generation and edge generation-by examining which of them is more beneficial for the pre-training framework and, by extension, downstream tasks. In Table 1, we report the performance of GPT-GNN by using attribute generation and edge generation alone, that is, GPT-GNN (Attr) and GPT-GNN (Edge). On OAG, the average performance gains by GPT-GNN (Attr) and GPT-GNN (Edge) are 7.4% and 10.3%, respectively, suggesting that Edge Generation is a more informative pre-training task than Attribute Generation in GPT-GNN. However, we have an opposite observation for Amazon, on which the performance improved by Attribute Generation is 5.2% in contrast to the 4.1% improvement lifted by Edge Generation. This suggests that the GPT-GNN framework benefits differently from attribute and edge generations on different datasets. However, combining the two pre-training tasks together produces the best performance on both cases.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We further compare the Edge Generation task against other edge-based pre-training methods-GAE and GraphSage (unsp.)-in Table 1. On OAG, the performance improvements brought by GPT-GNN's edge generation, GAE, and GraphSage over no pre-training are 10.3%, 7.4%, and 4.0%, respectively. On Amazon, the gains are  5.2%, 3.1%, and 1.3%, respectively. From the comparisons, we have the following observations. First, both GAE and GPT-GNN's edge generation offer better results than GraphSage on both datasets, demonstrating that masking on edges is an effective strategy for self-supervised graph representation learning. Without edge masking, the model simply retains a similar embedding for connected nodes, as the label we would like to predict (whether two nodes are linked) has already been encoded in the input graph structure. Such information leakage will downgrade the edge prediction task to a trivial problem. Second, the proposed Edge Generation task consistently outperforms GAE. The main advantage of GPT-GNN's edge generation comes from that it learns to generate missing edges autoregressively and thus can capture the dependencies between the masked edges, which are discarded by GAE. In summary, the results suggest that the proposed graph generation tasks can give informative self-supervision for GNN pre-training.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Ablation studies on the base GNN. We investigate whether the other GNN architectures can benefit from the proposed pretraining framework. Therefore, in addition to HGT [15], we try GCN [17], GAT [36], RGCN [28], and HAN [39] as the base model. Specifically, we pre-train them on OAG and then use the paper-field prediction task under the combined transfer setting with 10% of training data for fine-tuning and testing. Model-independent hyperparameters, such as the hidden dimension size and optimization, are set the same. The results are reported in in Table 2. We can observe that 1) HGT achieves the best performance among all non pre-trained GNN models; 2) GPT-GNN with HGT generates the most promising results for the concerned downstream task; and 3) more importantly, the proposed GPT-GNN pre-training framework can enhance the downstream performance for all the GNN architectures.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Ablation studies on the node separation and adaptive queue. Finally, we examine the effectiveness of the two design choices of GPT-GNN, i.e., node separation and adaptive queue. The node separation is designed for alleviating the information leakage problem for the Attribute Generation task. Without this component, the attributes would appear in the input and thus the pre-training method would only need to maintain the input features for output. In other words, it cannot learn any knowledge of the input graph that could be transferred to downstream tasks and thus affect the results negatively. From Table 1, we can see that the attribute generation based pre-training model suffers from the removal of the node separation component (w/o node separation), and in many cases, its performance is even worse than the ones without pre-training. This demonstrates the significance of this node separation design in avoiding attribute information leakage.   Table 3: Downstream performance on homogeneous graphs, including the paper citation network in OAG and Reddit.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The adaptive queue is designed for alleviating the gap between the sampled graphs and the full graph. Similarly, we conduct the ablation study by removing it from the Edge Generation based pre-training model and from Table 1, we witness the consistent performance drops for all tasks-GPT-GNN (Edge) vs. (w/o adaptive queue). This indicates that adding more negative samples by using the adaptive queue is indeed helpful to the pre-training framework.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Training data size. In Figure 3, we examine whether the proposed GPT-GNN method can generalize well with different training data size during fine-tuning, i.e., from 10% to 100%. First, we can observe that GPT-GNN and other pre-training frameworks consistently improve the downstream task performance with more labeled training data. Second, it is clear that GPT-GNN performs the best among all pre-training tasks/frameworks. Finally, we can see that with the pre-trained model, fine-tuning with only 10-20% of data (the two leftmost blue circles) generates comparative performance to the supervised learning with all 100% of training data (the rightmost purple diamond), demonstrating the superiority of GNN pre-training, especially when the label is scarce.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Results for homogeneous graphs. In addition to heterogeneous graphs, we also test whether the GPT-GNN pre-training framework can benefit downstream tasks on homogeneous graphs. Specifically, we pre-train and fine-tune on two homogeneous graphs: 1) the paper citation network extracted from the field of CS in OAG, on which the topic of each paper is predicted; 2) the Reddit network consisting of Reddit posts, on which the community of each post is inferred. As there is only one type of nodes and edges in homogeneous graphs, we require one single set of edge and attribute decoders for pre-training. HGT is used as the base pre-training model by ignoring its heterogeneous components. The fine-tuned results with 10% labeled data are presented in Table 3. We can observe that the downstream tasks on both homogeneous graphs can benefit from all pre-training frameworks, among which the proposed GPT-GNN offers the largest performance gains.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
In this work, we study the problem of graph neural network pretraining. We present GPT-GNN-a generative GNN pre-training framework. In GPT-GNN, we design the graph generation factorization to guide the base GNN model to autoregressively reconstruct both the attributes and structure of the input graph. Furthermore, we propose to separate the attribute and edge generation nodes to avoid information leakage. In addition, we introduce the adaptive node representation queue to mitigate the gap between the likelihoods over the sampled graph and the full graph. The pretrained GNNs with fine-tuning over few labeled data can achieve significant performance gains on various downstream tasks across different datasets. Also, GPT-GNN is robust to different transfer settings between pre-training and fine-tuning. Finally, we find that fine-tuning the generative pre-trained GNN model with 10-20% of labeled data offers comparative performance for downstream tasks to the supervised GNN model with 100% of training data.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We mainly use Open Academic Graph (OAG) and Amazon Review Recommendation Dataset (Amazon) for evaluation. Both are widely used heterogeneous graph [30][31][32]. Here we introduce their statistics, schema and how we prepare the attributes and tasks in detail.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Open Academic Graph (OAG) [34,38,44] consists of five types of nodes: 'Paper', 'Author', 'Field', 'Venue', and 'Institute', and 14 types of edges between these nodes. The schema and meta relations are illustrated in Figure 4(a). For example, the 'Field' nodes in the OAG are categorized into six levels from L 0 to L 5 , which are organized with a hierarchical tree (We use 'is_organized_in' to represent this hierarchy). Therefore, we differentiate the 'Paper-Field' edges in the corresponding field levels. Besides, we differentiate the different author orders (i.e., the first author, the last one, and others) and venue types (i.e., journal, conference, and preprint) as well. Finally, the 'Self' type corresponds to the self-loop connection, which is widely added in GNN architectures. Despite 'Self' and 'CoAuthor' edge relationships, which are symmetric, all other edge types X have a reverse edge type X −1 .
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For downstream tasks, we choose the following three tasks: the prediction of Paper-Field (L2), Paper-Venue, and Author Disambiguation. In the first two tasks, we give a model a paper and want it to predict the correct fields it belongs to or the venue it is published at. We model these three tasks as node classification problem, where we use GNNs to get the contextual node representation of the paper and use a softmax output layer to get its classification results. For author disambiguation, we pick all the authors with the same name, and the papers that link to one of these same-name authors. The task is to conduct link prediction between papers and candidate authors. After getting the paper and author node representations from GNNs, we use a Neural Tensor Network to get the probability of each author-paper pair to be linked.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For input attributes of heterogeneous graph, as we don't assume the attribute of each data type belongs to the same distribution, and we are free to use the most appropriate attributes to represent each type of node. For paper and author nodes, the node numbers are extremely large. Therefore, traditional node embedding algorithms are not suitable for extracting attributes for them. We, therefore, resort to the paper titles for extracting attributes. For each paper, we get its title text and use a pre-trained XLNet [40,41] to get the representation of each word in the title. We then average them weighted by each word's attention to get the title representation for each paper. The initial attribute of each author is simply an average of his/her published papers' embeddings. For field, venue and institute nodes, the node numbers are small and we use the metap-ath2vec model [6] to train their node embeddings by reflecting the heterogeneous network structures.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Amazon Review Recommendation Dataset (Amazon) [23] consists of three types of nodes, including reviews (ratings and text), users and products, and some other meta-types of the product, including color, size, style and quantity. The schema and meta relations are illustrated in Figure 4(b). Compared to a general user-item bipartite graph, this dataset have review in between, each is associated with text information and a rating from 1 to 5. The reviews are also associated with those product meta-type descriptions. For simplicity, we only consider these review-type link as 'categorize_in' type. Thus, there are totally three types of relations in this graph.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For downstream task, we choose the rating classification for each new review. Since the problem is a node-level multi-class classification, we use GNNs to get the contextual node representation of the review and use a softmax output layer to get 5-class prediction.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For input attributes of Amazon, we also use a pre-trained XLNet to get each review embedding, and the attributes for all the other nodes are simple an average of its associated review's embeddings.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
The overall pipeline of GPT-GNN is illustrated by Algorithm 1. Given an attributed graph G, we each time sample a subgraphĜ as training instance for generative pre-training. The first step is to determine the node permutation order π . To support parallel training, we want to conduct the forward pass for a single run and get the representation of the whole graph, so that we can simultaneously calculate the loss for each node, instead of processing each node recursively. Therefore, we remove all the edges from nodes with higher order to those with lower order according to π , which means each node can only receive information from nodes with lower order. In this way, they won't leak the information to the autoregressive generative objective, and thus we only need one single round to get node embeddings of the whole graph, which can directly be utilized to conduct generative pre-training.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Afterwards, we need to determine the edges to be masked out. For each node, we get all its outward edges, randomly select a set of edges to be masked out. This corresponds to line 4. Next, we conduct node separation and get contextualized node embeddings for the whole graph in line 5, which will be utilized to calculate generative loss. line 7-9. For both OAG and Amazon, the main nodes that contain meaningful attributes are paper and review nodes, which both have text feature as input. Thus, we only consider them for Attribute Generation, with a 2-layer LSTM as decoder. Note that in line 8, we prepare the negative samples by aggregating both the unconnected nodes within this sampled graph and the previously calculated embeddings stored in the adaptive queue Q. This can mitigate the gap between optimizing over sampled graph with over the whole graph. Finally, we optimize the model and update the adaptaive queue in line 11-12. Afterwards, we can use the pretrained model as initialization, to fine-tune on other downstream tasks.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We use a Tesla K80 to run both pre-training and downstream tasks. For graph sampling, we follow the HGSampling [15,45] to sample subgraph over large-scale heterogeneous graph. For each type of node, we sample 128 nodes per layer. We repeat sampling for 6 times for OAG and average sampled nodes in the sub-graph is 3561 nodes. We repeat for 8 times for Amazon, and average sampled nodes is 1478. For each batch, we sample 32 graphs to conduct generative pre-training. During GPU training, we conduct multiprocess sampling to prepare the pre-training data. Such CPU-GPU cooperation can help us save the sampling time.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
We here illustrate the convergence curves for pre-training and fine-tuning. For pre-training, as illustrated in Figure 6, we show the 
GPT-GNN: Generative Pre-Training of Graph Neural Networks
Groundtruth Paper Title person recognition system using automatic probabilistic classification person re-identification by probabilistic relative distance comparison a novel framework using spectrum sensing in wireless systems a secure collaborative spectrum sensing strategy in cyber physical systems a efficient evaluation of a distributed data storage service storage an empirical analysis of a large scale mobile cloud storage service parameter control in wireless sensor networks networks networks optimal parameter estimation under controlled communication over sensor networks a experimental system for for to the analysis of graphics an interactive computer graphics approach to surface representation Table 4: Generated paper title samples. The left column is generated by GPT-GNN, and the right column is the groundtruth.  shows that the generative pre-training task is hard enough and can thus can guide the model to really capture the intrinsic structure of the graph data. It took about 12 hours for GPT-GNN to converge. For downstream tasks, we show the convergence curve utilizing our GPT-GNN with no-pretrain, with different data percentage. As is illustrated in Figure 5, GPT-GNN can always get a more generalized model than no-pretrain, and is more robust to over-fitting since a good initialization from pre-training.
GPT-GNN: Generative Pre-Training of Graph Neural Networks
For OAG, since our attribute generation task is oriented on the paper title, we'd like to see how well our GPT-GNN can learn to generate the title. The results are shown in table 4. We can see that the model can capture the main meaning of each paper to be predicted, only by looking at partial neighborhoods (note that we use Attribute Generation Node for this task, which replace the input attribute as a share vector). For example, for the first sentence, our model successfully predict the key words for this paper, including 'person recognition', 'probabilistic', etc. This shows that the graph itself contains rich semantic information, and explains why a pretrained model can generalize well to downstream tasks.
Deep Graph Infomax
In this work, we propose an alternative objective for unsupervised graph learning that is based upon mutual information, rather than random walks. Recently, scalable estimation of mutual information was made both possible and practical through Mutual Information Neural Estimation (MINE, Belghazi et al., 2018), which relies on training a statistics network as a classifier of samples coming from the joint distribution of two random variables and their product of marginals. Following on MINE, Hjelm et al. (2018) introduced Deep InfoMax (DIM) for learning representations of highdimensional data. DIM trains an encoder model to maximize the mutual information between a high-level "global" representation and "local" parts of the input (such as patches of an image). This encourages the encoder to carry the type of information that is present in all locations (and thus are globally relevant), such as would be the case of a class label. DIM relies heavily on convolutional neural network structure in the context of image data, and to our knowledge, no work has applied mutual information maximization to graph-structured inputs. Here, we adapt ideas from DIM to the graph domain, which can be thought of as having a more general type of structure than the ones captured by convolutional neural networks. In the following sections, we introduce our method called Deep Graph Infomax (DGI). We demonstrate that the representation learned by DGI is consistently competitive on both transductive and inductive classification tasks, often outperforming both supervised and unsupervised strong baselines in our experiments.
Deep Graph Infomax
Contrastive methods. An important approach for unsupervised learning of representations is to train an encoder to be contrastive between representations that capture statistical dependencies of interest and those that do not. For example, a contrastive approach may employ a scoring function, training the encoder to increase the score on "real" input (a.k.a, positive examples) and decrease the score on "fake" input (a.k.a., negative samples). Contrastive methods are central to many popular word-embedding methods (Collobert & Weston, 2008;Mnih & Kavukcuoglu, 2013;Mikolov et al., 2013), but they are found in many unsupervised algorithms for learning representations of graphstructured input as well. There are many ways to score a representation, but in the graph literature the most common techniques use classification (Perozzi et al., 2014;Grover & Leskovec, 2016;Kipf & Welling, 2016b;Hamilton et al., 2017b), though other scoring functions are used (Duran & Niepert, 2017;Bojchevski & Günnemann, 2018). DGI is also contrastive in this respect, as our objective is based on classifying local-global pairs and negative-sampled counterparts.
Deep Graph Infomax
Sampling strategies. A key implementation detail to contrastive methods is how to draw positive and negative samples. The prior work above on unsupervised graph representation learning relies on a local contrastive loss (enforcing proximal nodes to have similar embeddings). Positive samples typically correspond to pairs of nodes that appear together within short random walks in the graph-from a language modelling perspective, effectively treating nodes as words and random walks as sentences. Recent work by Bojchevski & Günnemann (2018) uses node-anchored sampling as an alternative. The negative sampling for these methods is primarily based on sampling of random pairs, with recent work adapting this approach to use a curriculum-based negative sampling scheme (with progressively "closer" negative examples; Ying et al., 2018a) or introducing an adversary to select the negative examples (Bose et al., 2018).
Deep Graph Infomax
Predictive coding. Contrastive predictive coding (CPC, Oord et al., 2018) is another method for learning deep representations based on mutual information maximization. Like the models above, CPC is also contrastive, in this case using an estimate of the conditional density (in the form of noise contrastive estimation, Gutmann & Hyvärinen, 2010) as the scoring function. However, unlike our approach, CPC and the graph methods above are all predictive: the contrastive objective effectively trains a predictor between structurally-specified parts of the input (e.g., between neighboring node pairs or between a node and its neighborhood). Our approach differs in that we contrast global / local parts of a graph simultaneously, where the global variable is computed from all local variables.
Deep Graph Infomax
To the best of our knowledge, the sole prior works that instead focuses on contrasting "global" and "local" representations on graphs do so via (auto-)encoding objectives on the adjacency matrix (Wang et al., 2016) and incorporation of community-level constraints into node embeddings (Wang et al., 2017). Both methods rely on matrix factorization-style losses and are thus not scalable to larger graphs.
Deep Graph Infomax
In this section, we will present the Deep Graph Infomax method in a top-down fashion: starting with an abstract overview of our specific unsupervised learning setup, followed by an exposition of the objective function optimized by our method, and concluding by enumerating all the steps of our procedure in a single-graph setting.
Deep Graph Infomax
We assume a generic graph-based unsupervised machine learning setup: we are provided with a set of node features, X = { x 1 , x 2 , . . . , x N }, where N is the number of nodes in the graph and x i ∈ R F represents the features of node i. We are also provided with relational information between these nodes in the form of an adjacency matrix, A ∈ R N ×N . While A may consist of arbitrary real numbers (or even arbitrary edge features), in all our experiments we will assume the graphs to be unweighted, i.e. A ij = 1 if there exists an edge i → j in the graph and A ij = 0 otherwise.
Deep Graph Infomax
Our objective is to learn an encoder, E :
Deep Graph Infomax
for each node i. These representations may then be retrieved and used for downstream tasks, such as node classification.
Deep Graph Infomax
Here we will focus on graph convolutional encoders-a flexible class of node embedding architectures, which generate node representations by repeated aggregation over local node neighborhoods (Gilmer et al., 2017). A key consequence is that the produced node embeddings, h i , summarize a patch of the graph centered around node i rather than just the node itself. In what follows, we will often refer to h i as patch representations to emphasize this point.
Deep Graph Infomax
Our approach to learning the encoder relies on maximizing local mutual information-that is, we seek to obtain node (i.e., local) representations that capture the global information content of the entire graph, represented by a summary vector, s.
Deep Graph Infomax
In order to obtain the graph-level summary vectors, s, we leverage a readout function, R : R N ×F → R F , and use it to summarize the obtained patch representations into a graph-level representation; i.e., s = R(E(X, A)).
Deep Graph Infomax
As a proxy for maximizing the local mutual information, we employ a discriminator, D : R F × R F → R, such that D( h i , s) represents the probability scores assigned to this patch-summary pair (should be higher for patches contained within the summary).
Deep Graph Infomax
Negative samples for D are provided by pairing the summary s from (X, A) with patch representations h j of an alternative graph, ( X, A). In a multi-graph setting, such graphs may be obtained as other elements of a training set. However, for a single graph, an explicit (stochastic) corruption function, C : R N ×F × R N ×N → R M ×F × R M ×M is required to obtain a negative example from the original graph, i.e. ( X, A) = C(X, A). The choice of the negative sampling procedure will govern the specific kinds of structural information that is desirable to be captured as a byproduct of this maximization.
Deep Graph Infomax
For the objective, we follow the intuitions from Deep InfoMax (DIM, Hjelm et al., 2018) and use a noise-contrastive type objective with a standard binary cross-entropy (BCE) loss between the samples from the joint (positive examples) and the product of marginals (negative examples). Following their work, we use the following objective 1 :
Deep Graph Infomax
This approach effectively maximizes mutual information between h i and s, based on the Jensen-Shannon divergence 2 between the joint and the product of marginals.
Deep Graph Infomax
As all of the derived patch representations are driven to preserve mutual information with the global graph summary, this allows for discovering and preserving similarities on the patch-level-for example, distant nodes with similar structural roles (which are known to be a strong predictor for many node classification tasks; Donnat et al., 2018). Note that this is a "reversed" version of the argument given by : for node classification, our aim is for the patches to establish links to similar patches across the graph, rather than enforcing the summary to contain all of these similarities (however, both of these effects should in principle occur simultaneously).
Deep Graph Infomax
We now provide some intuition that connects the classification error of our discriminator to mutual information maximization on graph representations.
Deep Graph Infomax
be a set of node representations drawn from an empirical probability distribution of graphs, p(X), with finite number of elements, |X|, such that p(X (k) ) = p(X (k ) ) ∀k, k . Let R(·) be a deterministic readout function on graphs and s (k) = R(X (k) ) be the summary vector of the k-th graph, with marginal distribution p( s). The optimal classifier between the joint distribution p(X, s) and the product of marginals p(X)p( s), assuming class balance, has an error rate upper bounded by Err * = 1 2 |X| k=1 p( s (k) ) 2 . This upper bound is achieved if R is injective.
Deep Graph Infomax
Proof. Denote by Q (k) the set of all graphs in the input set that are mapped to s (k) by R, i.e. Q (k) = {X (j) | R(X (j) ) = s (k) }. As R(·) is deterministic, samples from the joint, (X (k) , s (k) ) are drawn from the product of marginals with probability p( s (k) )p(X (k) ), which decomposes into:
Deep Graph Infomax
For convenience, let ρ (k) = p(X (k) ) X ∈Q (k) p(X ) . As, by definition, X (k) ∈ Q (k) , it holds that ρ (k) ≤ 1. This probability ratio is maximized at 1 when Q (k) = {X (k) }, i.e. when R is injective for X (k) . The probability of drawing any sample of the joint from the product of marginals is then bounded above by |X| k=1 p( s (k) ) 2 . As the probability of drawing (X (k) , s (k) ) from the joint is ρ (k) p( s (k) ) ≥ ρ (k) p( s (k) ) 2 , we know that classifying these samples as coming from the joint has a lower error than classifying them as coming from the product of marginals. The error rate of such a classifier is then the probability of drawing a sample from the joint as a sample from product of marginals under the mixture probability, which we can bound by Err ≤ 1 2 |X| k=1 p( s (k) ) 2 , with the upper bound achieved, as above, when R(·) is injective for all elements of {X (k) }.
Deep Graph Infomax
It may be useful to note that 1 2|X| ≤ Err * ≤ 1 2 . The first result is obtained via a trivial application of Jensen's inequality, while the other extreme is reached only in the edge case of a constant readout function (when every example from the joint is also an example from the product of marginals, so no classifier performs better than chance). Corollary 1. From now on, assume that the readout function used, R, is injective. Assume the number of allowable states in the space of s, | s|, is greater than or equal to |X|. Then, for s , the optimal summary under the classification error of an optimal classifier between the joint and the product of marginals, it holds that | s | = |X|.
Deep Graph Infomax
Proof. By injectivity of R, we know that s = argmin s Err * . As the upper error bound, Err * , is a simple geometric sum, we know that this is minimized when p( s (k) ) is uniform. As R(·) is deterministic, this implies that each potential summary state would need to be used at least once. Combined with the condition | s| ≥ |X|, we conclude that the optimum has | s | = |X|.
Deep Graph Infomax
Proof. This follows from the fact that the mutual information is invariant under invertible transforms. As | s | = |X| and R is injective, it has an inverse function, R −1 . It follows then that, for any s, MI(X; s) ≤ H(X) = MI(X; X) = MI(X; R(X)) = MI(X; s ), where H is entropy.
Deep Graph Infomax
Theorem 1 shows that for finite input sets and suitable deterministic functions, minimizing the classification error in the discriminator can be used to maximize the mutual information between the input and output. However, as was shown in Hjelm et al. (2018), this objective alone is not enough to learn useful representations. As in their work, we discriminate between the global summary vector and local high-level representations.
Deep Graph Infomax
where n is the neighborhood function that returns the set of neighborhood indices of node i for graph X (k) , and E is a deterministic encoder function. Let us assume that
Deep Graph Infomax
Proof. Given our assumption of |X i | = | s|, there exists an inverse X i = R −1 ( s), and therefore h i = E(R −1 ( s)), i.e. there exists a deterministic function (E • R −1 ) mapping s to h i . The optimal classifier between the joint p( h i , s) and the product of marginals p( h i )p( s) then has (by Lemma 1) an error rate upper bound of
Deep Graph Infomax
i ) 2 . Therefore (as in Corollary 1), for the optimal h i , | h i | = |X i |, which by the same arguments as in Theorem 1 maximizes the mutual information between the neighborhood and high-level features, MI(X
Deep Graph Infomax
This motivates our use of a classifier between samples from the joint and the product of marginals, and using the binary cross-entropy (BCE) loss to optimize this classifier is well-understood in the context of neural network optimization.
Deep Graph Infomax
Assuming the single-graph setup (i.e., (X, A) provided as input), we will now summarize the steps of the Deep Graph Infomax procedure:
Deep Graph Infomax
1. Sample a negative example by using the corruption function: ( X, A) ∼ C(X, A).
Deep Graph Infomax
2. Obtain patch representations, h i for the input graph by passing it through the encoder:
Deep Graph Infomax
3. Obtain patch representations, h j for the negative example by passing it through the encoder:
Deep Graph Infomax
. Summarize the input graph by passing its patch representations through the readout function: s = R(H).
Deep Graph Infomax
5. Update parameters of E, R and D by applying gradient descent to maximize Equation 1.
Deep Graph Infomax
This algorithm is fully summarized by Figure 1. Figure 1: A high-level overview of Deep Graph Infomax. Refer to Section 3.4 for more details. 
Deep Graph Infomax
We have assessed the benefits of the representation learnt by the DGI encoder on a variety of node classification tasks (transductive as well as inductive), obtaining competitive results. In each case, DGI was used to learn patch representations in a fully unsupervised manner, followed by evaluating the node-level classification utility of these representations. This was performed by directly using these representations to train and test a simple linear (logistic regression) classifier.
Deep Graph Infomax
We follow the experimental setup described in Kipf & Welling (2016a) and Hamilton et al. (2017a) on the following benchmark tasks: (1) classifying research papers into topics on the Cora, Citeseer and Pubmed citation networks (Sen et al., 2008); (2) predicting the community structure of a social network modeled with Reddit posts; and (3) classifying protein roles within protein-protein interaction (PPI) networks (Zitnik & Leskovec, 2017), requiring generalisation to unseen networks.
Deep Graph Infomax
Further information on the datasets may be found in Table 1 and Appendix A.
Deep Graph Infomax
For each of three experimental settings (transductive learning, inductive learning on large graphs, and multiple graphs), we employed distinct encoders and corruption functions appropriate to that setting (described below).
Deep Graph Infomax
Transductive learning. For the transductive learning tasks (Cora, Citeseer and Pubmed), our encoder is a one-layer Graph Convolutional Network (GCN) model (Kipf & Welling, 2016a), with the following propagation rule:
Deep Graph Infomax
whereÂ = A + I N is the adjacency matrix with inserted self-loops andD is its corresponding degree matrix; i.e.D ii = jÂ ij . For the nonlinearity, σ, we have applied the parametric ReLU (PReLU) function (He et al., 2015), and Θ ∈ R F ×F is a learnable linear transformation applied to every node, with F = 512 features being computed (specially, F = 256 on Pubmed due to memory limitations).
Deep Graph Infomax
The corruption function used in this setting is designed to encourage the representations to properly encode structural similarities of different nodes in the graph; for this purpose, C preserves the original adjacency matrix ( A = A), whereas the corrupted features, X, are obtained by row-wise shuffling of X. That is, the corrupted graph consists of exactly the same nodes as the original graph, but they are located in different places in the graph, and will therefore receive different patch representations. We demonstrate DGI is stable to other choices of corruption functions in Appendix C, but we find those that preserve the graph structure result in the strongest features.
Deep Graph Infomax
Inductive learning on large graphs. For inductive learning, we may no longer use the GCN update rule in our encoder (as the learned filters rely on a fixed and known adjacency matrix); instead, we apply the mean-pooling propagation rule, as used by GraphSAGE-GCN (Hamilton et al., 2017a):
Deep Graph Infomax
with parameters defined as in Equation 3. Note that multiplying byD −1 actually performs a normalized sum (hence the mean-pooling). While Equation 4 explicitly specifies the adjacency and degree matrices, they are not needed: identical inductive behaviour may be observed by a constant attention mechanism across the node's neighbors, as used by the Const-GAT model (Veličković et al., 2018).
Deep Graph Infomax
For Reddit, our encoder is a three-layer mean-pooling model with skip connections (He et al., 2016):
Deep Graph Infomax
where is featurewise concatenation (i.e. the central node and its neighborhood are handled separately). We compute F = 512 features in each MP layer, with the PReLU activation for σ.
Deep Graph Infomax
Given the large scale of the dataset, it will not fit into GPU memory entirely. Therefore, we use the subsampling approach of Hamilton et al. (2017a), where a minibatch of nodes is first selected, and then a subgraph centered around each of them is obtained by sampling node neighborhoods with replacement. Specifically, we sample 10, 10 and 25 neighbors at the first, second and third level, respectively-thus, each subsampled patch has 1 + 10 + 100 + 2500 = 2611 nodes. Only the computations necessary for deriving the central node i's patch representation, h i , are performed. These representations are then used to derive the summary vector, s, for the minibatch (Figure 2). We used minibatches of 256 nodes throughout training.
Deep Graph Infomax
To define our corruption function in this setting, we use a similar approach as in the transductive tasks, but treat each subsampled patch as a separate graph to be corrupted (i.e., we row-wise shuffle the feature matrices within a subsampled patch). Note that this may very likely cause the central node's features to be swapped out for a sampled neighbor's features, further encouraging diversity in the negative samples. The patch representation obtained in the central node is then submitted to the discriminator.
Deep Graph Infomax
Inductive learning on multiple graphs. For the PPI dataset, inspired by previous successful supervised architectures (Veličković et al., 2018), our encoder is a three-layer mean-pooling model with dense skip connections (He et al., 2016;Huang et al., 2017):
Deep Graph Infomax
where W skip is a learnable projection matrix, and MP is as defined in Equation 4. We compute F = 512 features in each MP layer, using the PReLU activation for σ.
Deep Graph Infomax
In this multiple-graph setting, we opted to use randomly sampled training graphs as negative examples (i.e., our corruption function simply samples a different graph from the training set). We found this method to be the most stable, considering that over 40% of the nodes have all-zero features in this dataset. To further expand the pool of negative examples, we also apply dropout (Srivastava et al., 2014) to the input features of the sampled graph. We found it beneficial to standardize the learnt embeddings across the training set prior to providing them to the logistic regression model.
Deep Graph Infomax
Readout, discriminator, and additional training details. Across all three experimental settings, we employed identical readout functions and discriminator architectures.
Deep Graph Infomax
For the readout function, we use a simple averaging of all the nodes' features:
Deep Graph Infomax
where σ is the logistic sigmoid nonlinearity. While we have found this readout to perform the best across all our experiments, we assume that its power will diminish with the increase in graph size, and in those cases, more sophisticated readout architectures such as set2vec (Vinyals et al., 2015) or DiffPool (Ying et al., 2018b) are likely to be more appropriate.
Deep Graph Infomax
The discriminator scores summary-patch representation pairs by applying a simple bilinear scoring function (similar to the scoring used by Oord et al. (2018)):
Deep Graph Infomax
Here, W is a learnable scoring matrix and σ is the logistic sigmoid nonlinearity, used to convert scores into probabilities of ( h i , s) being a positive example.
Deep Graph Infomax
All models are initialized using Glorot initialization (Glorot & Bengio, 2010) and trained to maximize the mutual information provided in Equation 1 on the available nodes (all nodes for the transductive, and training nodes only in the inductive setup) using the Adam SGD optimizer (Kingma & Ba, 2014) with an initial learning rate of 0.001 (specially, 10 −5 on Reddit). On the transductive datasets, we use an early stopping strategy on the observed training loss, with a patience of 20 epochs 3 . On the inductive datasets we train for a fixed number of epochs (150 on Reddit, 20 on PPI).
Deep Graph Infomax
The results of our comparative evaluation experiments are summarized in Table 2.
Deep Graph Infomax
For the transductive tasks, we report the mean classification accuracy (with standard deviation) on the test nodes of our method after 50 runs of training (followed by logistic regression), and reuse the metrics already reported in Kipf & Welling (2016a) for the performance of DeepWalk and GCN, as well as Label Propagation (LP) (Zhu et al., 2003) and Planetoid (Yang et al., 2016)-a representative supervised random walk method. Specially, we provide results for training the logistic regression on raw input features, as well as DeepWalk with the input features concatenated.   0.958 ± 0.001 0.969 ± 0.002
Deep Graph Infomax
For the inductive tasks, we report the micro-averaged F 1 score on the (unseen) test nodes, averaged after 50 runs of training, and reuse the metrics already reported in Hamilton et al. (2017a) for the other techniques. Specifically, as our setup is unsupervised, we compare against the unsupervised GraphSAGE approaches. We also provide supervised results for two related architectures-FastGCN (Chen et al., 2018) and Avg. pooling .
Deep Graph Infomax
Our results demonstrate strong performance being achieved across all five datasets. We particularly note that the DGI approach is competitive with the results reported for the GCN model with the supervised loss, even exceeding its performance on the Cora and Citeseer datasets. We assume that these benefits stem from the fact that, indirectly, the DGI approach allows for every node to have access to structural properties of the entire graph, whereas the supervised GCN is limited to only two-layer neighborhoods (by the extreme sparsity of the training signal and the corresponding threat of overfitting). It should be noted that, while we are capable of outperforming equivalent supervised encoder architectures, our performance still does not surpass the current supervised transductive state of the art (which is held by methods such as GraphSGAN (Ding et al., 2018)). We further observe that the DGI method successfully outperformed all the competing unsupervised GraphSAGE approaches on the Reddit and PPI datasets-thus verifying the potential of methods based on local mutual information maximization in the inductive node classification domain. Our Reddit results are competitive with the supervised state of the art, whereas on PPI the gap is still large-we believe this can be attributed to the extreme sparsity of available node features (over 40% of the nodes having all-zero features), that our encoder heavily relies on.
Deep Graph Infomax
We note that a randomly initialized graph convolutional network may already extract highly useful features and represents a strong baseline-a well-known fact, considering its links to the Weisfeiler- Lehman graph isomorphism test (Weisfeiler & Lehman, 1968), that have already been highlighted and analyzed by Kipf & Welling (2016a) and Hamilton et al. (2017a). As such, we also provide, as Random-Init, the logistic regression performance on embeddings obtained from a randomly initialized encoder. Besides demonstrating that DGI is able to further improve on this strong baseline, it particularly reveals that, on the inductive datasets, previous random walk-based negative sampling methods may have been ineffective for learning appropriate features for the classification task.
Deep Graph Infomax
Lastly, it should be noted that deeper encoders correspond to more pronounced mixing between recovered patch representations, reducing the effective variability of our positive/negative examples' pool. We believe that this is the reason why shallower architectures performed better on some of the datasets. While we cannot say that these trends will hold in general, with the DGI loss function we generally found benefits from employing wider, rather than deeper models.
Deep Graph Infomax
We performed a diverse set of analyses on the embeddings learnt by the DGI algorithm in order to better understand the properties of DGI. We focus our analysis exclusively on the Cora dataset (as it has the smallest number of nodes, significantly aiding clarity).
Deep Graph Infomax
A standard set of "evolving" t-SNE plots (Maaten & Hinton, 2008) of the embeddings is given in Figure 3. As expected given the quantitative results, the learnt embeddings' 2D projections exhibit discernible clustering in the 2D projected space (especially compared to the raw features and Random-Init), which respects the seven topic classes of Cora. The projection obtains a Silhouette score (Rousseeuw, 1987) of 0.234, which compares favorably with the previous reported score of 0.158 for Embedding Propagation (Duran & Niepert, 2017).
Deep Graph Infomax
We ran further analyses, revealing insights into DGI's mechanism of learning, isolating biased embedding dimensions for pushing the negative example scores down and using the remainder to encode useful information about positive examples. We leverage these insights to retain competitive performance to the supervised GCN even after half the dimensions are removed from the patch representations provided by the encoder. These-and several other-qualitative and ablation studies can be found in Appendix B.
Deep Graph Infomax
We have presented Deep Graph Infomax (DGI), a new approach for learning unsupervised representations on graph-structured data. By leveraging local mutual information maximization across the graph's patch representations, obtained by powerful graph convolutional architectures, we are able to obtain node embeddings that are mindful of the global structural properties of the graph. This enables competitive performance across a variety of both transductive and inductive classification tasks, at times even outperforming relevant supervised architectures. 
Deep Graph Infomax
Transductive learning. We utilize three standard citation network benchmark datasets-Cora, Citeseer and Pubmed (Sen et al., 2008)-and closely follow the transductive experimental setup of Yang et al. (2016). In all of these datasets, nodes correspond to documents and edges to (undirected) citations. Node features correspond to elements of a bag-of-words representation of a document. Each node has a class label. We allow for only 20 nodes per class to be used for training-however, honouring the transductive setup, the unsupervised learning algorithm has access to all of the nodes' feature vectors. The predictive power of the learned representations is evaluated on 1000 test nodes.
Deep Graph Infomax
Inductive learning on large graphs. We use a large graph dataset (231,443 nodes and 11,606,919 edges) of Reddit posts created during September 2014 (derived and preprocessed as in Hamilton et al. (2017a)). The objective is to predict the posts' community ("subreddit"), based on the GloVe embeddings of their content and comments (Pennington et al., 2014), as well as metrics such as score or number of comments. Posts are linked together in the graph if the same user has commented on both. Reusing the inductive setup of Hamilton et al. (2017a), posts made in the first 20 days of the month are used for training, while the remaining posts are used for validation or testing and are invisible to the training algorithm. Inductive learning on multiple graphs. We make use of a protein-protein interaction (PPI) dataset that consists of graphs corresponding to different human tissues (Zitnik & Leskovec, 2017). The dataset contains 20 graphs for training, 2 for validation and 2 for testing. Critically, testing graphs remain completely unobserved during training. To construct the graphs, we used the preprocessed data provided by Hamilton et al. (2017a). Each node has 50 features that are composed of positional gene sets, motif gene sets and immunological signatures. There are 121 labels for each node set from gene ontology, collected from the Molecular Signatures Database (Subramanian et al., 2005), and a node can possess several labels simultaneously.
Deep Graph Infomax
Visualizing discriminator scores. After obtaining the t-SNE visualizations, we turned our attention to the discriminator-and visualized the scores it attached to various nodes, for both the positive and a (randomly sampled) negative example (Figure 4). From here we can make an interesting observation-within the "clusters" of the learnt embeddings on the positive Cora graph, only a handful of "hot" nodes are selected to receive high discriminator scores. This suggests that there may be a clear distinction between embedding dimensions used for discrimination and classification, which we more thoroughly investigate in the next paragraph. In addition, we may observe that, as expected, the model is unable to find any strong structure within a negative example. Lastly, a few negative examples achieve high discriminator scores-a phenomenon caused by the existence of low-degree nodes in Cora (making the probability of a node ending up in an identical context it had in the positive graph non-negligible).
Deep Graph Infomax
Impact and role of embedding dimensions. Guided by the previous result, we have visualized the embeddings for the top-scoring positive and negative examples ( Figure 5). The analysis revealed existence of distinct dimensions in which both the positive and negative examples are strongly biased. We hypothesize that, given the random shuffling, the average expected activation of a negative example is zero, and therefore strong biases are required to "push" the example down in the discriminator. The positive examples may then use the remaining dimensions to both counteract this bias and encode patch similarity. To substantiate this claim, we order the 512 dimensions based on how distinguishable the positive and negative examples are in them (using p-values obtained from a t-test as a proxy). We then remove these dimensions from the embedding, respecting this order-either starting from the most distinguishable (p ↑) or least distinguishable dimensions (p ↓)-monitoring how this affects both classification and discriminator performance ( Figure 6). The observed trends largely support our hypothesis: if we start by removing the biased dimensions first (p ↓), the classification performance holds up for much longer (allowing us to remove over half of the embedding dimensions while remaining competitive to the supervised GCN), and the positive examples mostly remain correctly discriminated until well over half the dimensions are removed.
Deep Graph Infomax
Here, we consider alternatives to our corruption function, C, used to produce negative graphs. We generally find that, for the node classification task, DGI is stable and robust to different strategies. However, for learning graph features towards other kinds of tasks, the design of appropriate corruption strategies remains an area of open research.
Deep Graph Infomax
Our corruption function described in Section 4.2 preserves the original adjacency matrix ( A = A) but corrupts the features, X, via row-wise shuffling of X. In this case, the negative graph is constrained to be isomorphic to the positive graph, which should not have to be mandatory. We can instead produce a negative graph by directly corrupting the adjacency matrix. Therefore, we first consider an alternative corruption function C which preserves the features ( X = X) but instead adds or removes edges from the adjacency matrix ( A = A). This is done by sampling, i.i.d., a switch parameter Σ ij , which determines whether to corrupt the adjacency matrix at position (i, j). Assuming a given corruption rate, ρ, we may define C as performing the following operations:
Deep Graph Infomax
where ⊕ is the XOR (exclusive OR) operation.
Deep Graph Infomax
This alternative strategy produces a negative graph with the same features, but different connectivity.
Deep Graph Infomax
Here, the corruption rate of ρ = 0 corresponds to an unchanged adjacency matrix (i.e. the positive and negative graphs are identical in this case). In this regime, learning is impossible for the discriminator, and the performance of DGI is in line with a randomly initialized DGI model. At higher rates of noise, however, DGI produces competitive embeddings.
Deep Graph Infomax
We also consider simultaneous feature shuffling ( X = X) and adjacency matrix perturbation ( A = A), both as described before. We find that DGI still learns useful features under this compound corruption strategy-as expected, given that feature shuffling is already equivalent to an (isomorphic) adjacency matrix perturbation.
Deep Graph Infomax
From both studies, we may observe that a certain lower bound on the positive graph perturbation rate is required to obtain competitive node embeddings for the classification task on Cora. Furthermore, the features learned for downstream node classification tasks are most powerful when the negative graph has similar levels of connectivity to the positive graph.
Deep Graph Infomax
The classification performance peaks when the graph is perturbed to a reasonably high level, but remains sparse; i.e. the mixing between the separate 1-step patches is not substantial, and therefore the pool of negative examples is still diverse enough. Classification performance is impacted only marginally at higher rates of corruption-corresponding to dense negative graphs, and thus a less rich negative example pool-but still considerably outperforming the unsupervised baselines we have considered. This could be seen as further motivation for relying solely on feature shuffling, without adjacency perturbations-given that feature shuffling is a trivial way to guarantee a diverse set of negative examples, without incurring significant computational costs per epoch. Corruption Rate, ρ
Deep Graph Infomax
Classification accuracy for (X, A) corruption X = X GCN Figure 8: DGI is stable and robust under a corruption function that modifies both the feature matrix (X = X) and the adjacency matrix ( A = A) on the Cora dataset. Corruption functions that preserve sparsity (ρ ≈ 1 N ) perform the best. However, DGI still performs well even with large disruptions (where edges are added or removed with probabilities approaching 1). N.B. log scale used for ρ.
Strategies for Pre-training Graph Neural Networks
Transfer learning refers to the setting where a model, initially trained on some tasks, is re-purposed on different but related tasks. Deep transfer learning has been immensely successful in computer vision Girshick et al., 2014;Zeiler & Fergus, 2014) and natural language processing (Devlin et al., 2019;Peters et al., 2018;Mikolov et al., 2013). Despite being an effective approach to transfer learning, few studies have generalized pre-training to graph data.
Strategies for Pre-training Graph Neural Networks
Pre-training has the potential to provide an attractive solution to the following two fundamental challenges with learning on graph datasets (Pan & Yang, 2009;Hendrycks et al., 2019): First, task-specific labeled data can be extremely scarce. This problem is exacerbated in important graph datasets from scientific domains, such as chemistry and biology, where data labeling (e.g., biological experiments in a wet laboratory) is resource-and time-intensive (Zitnik et al., 2018). Second, graph data from real-world applications often contain out-of-distribution samples, meaning that graphs in the training set are structurally very different from graphs in the test set. Out-of-distribution prediction is common in real-world graph datasets, for example, when one wants to predict chemical properties of a brand-new, just synthesized molecule, which is different from all molecules synthesized so far, and thereby different from all molecules in the training set.
Strategies for Pre-training Graph Neural Networks
However, pre-training on graph datasets remains a hard challenge. Several key studies (Xu et al., 2017;Ching et al., 2018; have shown that successful transfer learning is not only a In our systematic study, we show that pre-training GNNs does not always help. Naïve pre-training strategies can lead to negative transfer on many downstream tasks. Strikingly, a seemingly strong pre-training strategy (i.e., graph-level multi-task supervised pre-training using a state-of-the-art graph neural network architecture for graph-level prediction tasks) only gives marginal performance gains. Furthermore, this strategy even leads to negative transfer on many downstream tasks (2 out of 8 molecular datasets and 13 out of 40 protein prediction tasks).
Strategies for Pre-training Graph Neural Networks
We develop an effective strategy for pre-training GNNs. The key idea is to use easily accessible node-level information and encourage GNNs to capture domain-specific knowledge about nodes and edges, in addition to graph-level knowledge. This helps the GNN to learn useful representations at both global and local levels (Figure 1 (a.iii)), and is crucial to be able to generate graph-level representations (which are obtained by pooling node representations) that are robust and transferable to diverse downstream tasks (Figure 1). Our strategy is in contrast to naïve strategies that either leverage only at graph-level properties (Figure 1 (a.ii)) or node-level properties (Figure 1 (a.i)).
Strategies for Pre-training Graph Neural Networks
Empirically, our pre-training strategy used together with the most expressive GNN architecture, GIN (Xu et al., 2019), yields state-of-the-art results on benchmark datasets and avoids negative transfer across downstream tasks we tested. It significantly improves generalization performance across downstream tasks, yielding up to 9.4% higher average ROC-AUC than non-pre-trained GNNs, and up to 5.2% higher average ROC-AUC compared to GNNs with the extensive graph-level multitask supervised pre-training. Furthermore, we find that the most expressive architecture, GIN, benefits more from pre-training compared to those with less expressive power (e.g., GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017b) and GAT (Velickovic et al., 2018)), and that pre-training GNNs leads to orders-of-magnitude faster training and convergence in the fine-tuning stage.
Strategies for Pre-training Graph Neural Networks
We first formalize supervised learning of graphs and provide an overview of GNNs (Gilmer et al., 2017). Then, we briefly review methods for unsupervised graph representation learning.
Strategies for Pre-training Graph Neural Networks
Supervised learning of graphs. Let G = (V, E) denote a graph with node attributes X v for v ∈ V and edge attributes e uv for (u, v) ∈ E. Given a set of graphs {G 1 , . . . , G N } and their labels {y 1 , . . . , y N }, the task of graph supervised learning is to learn a representation vector h G that helps predict the label of an entire graph G, y G = g(h G ). For example, in molecular property prediction, G is a molecular graph, where nodes represent atoms and edges represent chemical bonds, and the label to be predicted can be toxicity or enzyme binding.
Strategies for Pre-training Graph Neural Networks
Graph Neural Networks (GNNs). GNNs use the graph connectivity as well as node and edge features to learn a representation vector (i.e., embedding) h v for every node v ∈ G and a vector h G for the entire graph G. Modern GNNs use a neighborhood aggregation approach, where representation of node v is iteratively updated by aggregating representations of v's neighboring nodes and edges (Gilmer et al., 2017). After k iterations of aggregation, v's representation captures the structural information within its k-hop network neighborhood. Formally, the k-th layer of a GNN is:
Strategies for Pre-training Graph Neural Networks
v is the representation of node v at the k-th iteration/layer, e uv is the feature vector of edge between u and v, and N (v) is a set neighbors of v. We initialize h
Strategies for Pre-training Graph Neural Networks
Graph representation learning. To obtain the entire graph's representation h G , the READOUT function pools node features from the final iteration K,
Strategies for Pre-training Graph Neural Networks
READOUT is a permutation-invariant function, such as averaging or a more sophisticated graph-level pooling function (Ying et al., 2018b;.
Strategies for Pre-training Graph Neural Networks
At the technical core of our pre-training strategy is the notion to pre-train a GNN both at the level of individual nodes as well as entire graphs. This notion encourages the GNN to capture domain-specific semantics at both levels, as illustrated in Figure 1 (a.iii). This is in contrast to straightforward but limited pre-training strategies that either only use pre-training to predict properties of entire graphs (Figure 1 (a.ii)) or only use pre-training to predict properties of individual nodes (Figure 1 (a.i)).
Strategies for Pre-training Graph Neural Networks
In the following, we first describe our node-level pre-training approach (Section 3.1) and then graph-level pre-training approach (Section 3.2). Finally, we describe the full pre-training strategy in Section 3.3.
Strategies for Pre-training Graph Neural Networks
For node-level pre-training of GNNs, our approach is to use easily-accessible unlabeled data to capture domain-specific knowledge/regularities in the graph. Here we propose two self-supervised methods, Context Prediction and Attribute Masking.
Strategies for Pre-training Graph Neural Networks
Context graph K-hop neighborhood Figure 2: Illustration of our node-level methods, Context Prediction and Attribute Masking for pretraining GNNs. (a) In Context Prediction, the subgraph is a K-hop neighborhood around a selected center node, where K is the number of GNN layers and is set to 2 in the figure. The context is defined as the surrounding graph structure that is between r 1 -and r 2 -hop from the center node, where we use r 1 = 1 and r 2 = 4 in the figure. (b) In Attribute Masking, the input node/edge attributes (e.g., atom type in the molecular graph) are randomly masked, and the GNN is asked to predict them.
Strategies for Pre-training Graph Neural Networks
In Context Prediction, we use subgraphs to predict their surrounding graph structures. Our goal is to pre-train a GNN so that it maps nodes appearing in similar structural contexts to nearby embeddings (Rubenstein & Goodenough, 1965;Mikolov et al., 2013).
Strategies for Pre-training Graph Neural Networks
Neighborhood and context graphs. For every node v, we define v's neighborhood and context graphs as follows. K-hop neighborhood of v contains all nodes and edges that are at most K-hops away from v in the graph. This is motivated by the fact that a K-layer GNN aggregates information across the K-th order neighborhood of v, and thus node embedding h
Strategies for Pre-training Graph Neural Networks
depends on nodes that are at most K-hops away from v. We define context graph of node v as graph structure that surrounds v's neighborhood. The context graph is described by two hyperparameters, r 1 and r 2 , and it represents a subgraph that is between r 1 -hops and r 2 -hops away from v (i.e., it is a ring of width r 2 − r 1 ). Examples of neighborhood and context graphs are shown in Figure 2 (a). We require r 1 < K so that some nodes are shared between the neighborhood and the context graph, and we refer to those nodes as context anchor nodes. These anchor nodes provide information about how the neighborhood and context graphs are connected with each other.
Strategies for Pre-training Graph Neural Networks
Encoding context into a fixed vector using an auxiliary GNN. Directly predicting the context graph is intractable due to the combinatorial nature of graphs. This is different from natural language processing, where words come from a fixed and finite vocabulary. To enable context prediction, we encode context graphs as fixed-length vectors. To this end, we use an auxiliary GNN, which we refer to as the context GNN. As depicted in Figure 2 (a), we first apply the context GNN (denoted as GNN in Figure 2 (a)) to obtain node embeddings in the context graph. We then average embeddings of context anchor nodes to obtain a fixed-length context embedding. For node v in graph G, we denote its corresponding context embedding as c G v . Learning via negative sampling. We then use negative sampling (Mikolov et al., 2013;Ying et al., 2018a) to jointly learn the main GNN and the context GNN. The main GNN encodes neighborhoods to obtain node embeddings. The context GNN encodes context graphs to obtain context embeddings. In particular, the learning objective of Context Prediction is a binary classification of whether a particular neighborhood and a particular context graph belong to the same node:
Strategies for Pre-training Graph Neural Networks
and v are the same nodes}, (3.1)
Strategies for Pre-training Graph Neural Networks
where σ(·) is the sigmoid function, and 1(·) is the indicator function. We either let v = v and G = G (i.e., a positive neighborhood-context pair), or we randomly sample v from a randomly chosen graph G (i.e., a negative neighborhood-context pair). We use a negative sampling ratio of 1 (one negative pair per one positive pair), and use the negative log likelihood as the loss function. After pre-training, the main GNN is retained as our pre-trained model
Strategies for Pre-training Graph Neural Networks
In Attribute Masking, we aim to capture domain knowledge by learning the regularities of the node/edge attributes distributed over graph structure.
Strategies for Pre-training Graph Neural Networks
Masking node and edges attributes. Attribute Masking pre-training works as follows: We mask node/edge attributes and then we let GNNs predict those attributes (Devlin et al., 2019) based on neighboring structure. Figure 2 (b) illustrates our proposed method when applied to a molecular graph. Specifically, We randomly mask input node/edge attributes, for example atom types in molecular graphs, by replacing them with special masked indicators. We then apply GNNs to obtain the corresponding node/edge embeddings (edge embeddings can be obtained as a sum of node embeddings of the edge's end nodes). Finally, a linear model is applied on top of embeddings to predict a masked node/edge attribute. Different from Devlin et al. (2019) that operates on sentences and applies message passing over the fully-connected graph of tokens, we operate on non-fullyconnected graphs and aim to capture the regularities of node/edge attributes distributed over different graph structures. Furthermore, we allow masking edge attributes, going beyond masking node attributes.
Strategies for Pre-training Graph Neural Networks
Our node and edge attribute masking method is especially beneficial for richly-annotated graphs from scientific domains. For example, (1) in molecular graphs, the node attributes correspond to atom types, and capturing how they are distributed over the graphs enables GNNs to learn simple chemistry rules such as valency, as well as potentially more complex chemistry phenomenon such as the electronic or steric properties of functional groups. Similarly, (2) in protein-protein interaction (PPI) graphs, the edge attributes correspond to different kinds of interactions between a pair of proteins. Capturing how these attributes distribute across the PPI graphs enables GNNs to learn how different interactions relate and correlate with each other.
Strategies for Pre-training Graph Neural Networks
We aim to pre-train GNNs to generate useful graph embeddings composed of the meaningful node embeddings obtained by methods in Section 3.1. Our goal is to ensure both node and graph embeddings are of high-quality so that graph embeddings are robust and transferable across downstream tasks, as illustrated in Figure 1 (a.iii). Additionally, there are two options for graph-level pre-training, as shown in Figure 1 (b): making predictions about domain-specific attributes of entire graphs (e.g., supervised labels), or making predictions about graph structure.
Strategies for Pre-training Graph Neural Networks
As the graph-level representation h G is directly used for fine-tuning on downstream prediction tasks, it is desirable to directly encode domain-specific information into h G .
Strategies for Pre-training Graph Neural Networks
We inject graph-level domain-specific knowledge into our pretrained embeddings by defining supervised graph-level prediction tasks. In particular, we consider a practical method to pre-train graph representations: graph-level multi-task supervised pre-training to jointly predict a diverse set of supervised labels of individual graphs. For example, in molecular property prediction, we can pre-train GNNs to predict essentially all the properties of molecules that have been experimentally measured so far. In protein function prediction, where the goal is predict whether a given protein has a given functionality, we can pre-train GNNs to predict the existence of diverse protein functions that have been validated so far. In our experiments in Section 5, we prepare a diverse set of supervised tasks (up to 5000 tasks) to simulate these practical scenarios. Further details of the supervised tasks and datasets are described in Section 5.1. To jointly predict many graph properties, where each property corresponds to a binary classification task, we apply linear classifiers on top of graph representations.
Strategies for Pre-training Graph Neural Networks
Importantly, naïvely performing the extensive multi-task graph-level pre-training alone can fail to give transferable graph-level representations, as empirically demonstrated in Section 5. This is because some supervised pre-training tasks might be unrelated to the downstream task of interest and can even hurt the downstream performance (negative transfer). One solution would be to select "truly-relevant" supervised pre-training tasks and pre-train GNNs only on those tasks. However, such a solution is extremely costly since selecting the relevant tasks requires significant domain expertise and pre-training needs to be performed separately for different downstream tasks.
Strategies for Pre-training Graph Neural Networks
To alleviate this issue, our key insight is that the multi-task supervised pre-training only provides graph-level supervision; thus, local node embeddings from which the graph-level embeddings are created may not be meaningful, as illustrated in Figure 1 (a.ii). Such non-useful node embeddings can exacerbate the problem of negative transfer because many different pre-training tasks can more easily interfere with each other in the node embedding space. Motivated by this, our pre-training strategy is to first regularize GNNs at the level of individual nodes via node-level pre-training methods described in Section 3.1, before performing graph-level pre-training. As we demonstrate empirically, the combined strategy produces much more transferable graph representations and robustly improves downstream performance without expert selection of supervised pre-training tasks.
Strategies for Pre-training Graph Neural Networks
A second approach is to define a graph-level predictive task where the goal would be to model the structural similarity of two graphs. Examples of such tasks include modeling the graph edit distance (Bai et al., 2019) or predicting graph structure similarity (Navarin et al., 2018). However, finding the ground truth graph distance values is a difficult problem, and in large datasets there is a quadratic number of graph pairs to consider. Therefore, while this type of pre-training is also very natural, it is beyond the scope of this paper and we leave its investigation for future work.
Strategies for Pre-training Graph Neural Networks
Altogether, our pre-training strategy is to first perform node-level self-supervised pre-training (Section 3.1) and then graph-level multi-task supervised pre-training (Section 3.2). When the GNN pre-training is finished, we fine-tune the pre-trained GNN model on downstream tasks. Specifically, we add linear classifiers on top of graph-level representations to predict downstream graph labels. The full model, i.e., the pre-trained GNN and downstream linear classifiers, is subsequently fine-tuned in an end-to-end manner. Time-complexity analysis is provided in Appendix F, where we show that our pre-training methods incur little computational overhead to forward computation in GNNs.
Strategies for Pre-training Graph Neural Networks
There is rich literature on unsupervised representation learning of individual nodes within graphs, which broadly falls into two categories. In the first category are methods that use local random walk-based objectives (Grover & Leskovec, 2016;Perozzi et al., 2014;Tang et al., 2015) and methods that reconstruct a graph's adjacency matrix, e.g., by predicting edge existence (Hamilton et al., 2017a;Kipf & Welling, 2016). In the second category are methods, such as Deep Graph Infomax (Veličković et al., 2019), that train a node encoder that maximizes mutual information between local node representations and a pooled global graph representation. All these methods encourage nearby nodes to have similar embeddings and were originally proposed and evaluated for node classification and link prediction. This, however, can be sub-optimal for graph-level prediction tasks, where capturing structural similarity of local neighborhoods is often more important than capturing the positional information of nodes within a graph (You et al., 2019;Rogers & Hahn, 2010;Yang et al., 2014). Our approach thus considers both the node-level as well as graph-level pretraining tasks and as we show in our experiments, it is essential to use both types of tasks in order for pretrained models to achieve good performance.
Strategies for Pre-training Graph Neural Networks
A number of recent works have also explored how node embeddings generalize across tasks (Jaeger et al., 2018;Zhou et al., 2018;Chakravarti, 2018;Narayanan et al., 2016). However, all of these methods use distinct node embeddings for different substructures and do not share any parameters. Thus, they are inherently transductive, cannot transfer between datasets, cannot be fine-tuned in an end-to-end manner, and cannot capture large and diverse neighborhoods/contexts due to data sparsity. Our approach addresses all these challenges by developing pre-training methods for GNNs that use shared parameters to encode the the graph-level as well as node-level dependencies and structures.
Strategies for Pre-training Graph Neural Networks
We consider two domains; molecular property prediction in chemistry and protein function prediction in biology. We release the new datasets at: http://snap.stanford.edu/gnn-pretrain.
Strategies for Pre-training Graph Neural Networks
Pre-training datasets. For the chemistry domain, we use 2 million unlabeled molecules sampled from the ZINC15 database (Sterling & Irwin, 2015) for node-level self-supervised pre-training. For graph-level multi-task supervised pre-training, we use a preprocessed ChEMBL dataset (Mayr et al., 2018;Gaulton et al., 2011), containing 456K molecules with 1310 kinds of diverse and extensive biochemical assays. For the biology domain, we use 395K unlabeled protein ego-networks derived from PPI networks of 50 species (e.g., humans, yeast, zebra fish) for node-level self-supervised pretraining. For graph-level multi-task supervised pre-training, we use 88K labeled protein ego-networks to jointly predict 5000 coarse-grained biological functions (e.g., cell apoptosis, cell proliferation).  (2019), consisting of 88K proteins from 8 different species, where the subgraphs centered at a protein of interest (i.e., ego-networks) are used to predict their biological functions. Our downstream task is to predict 40 fine-grained biological functions 1 that correspond to 40 binary classification tasks. In contrast to existing PPI datasets (Hamilton et al., 2017a), our dataset is larger and spans multiple species (i.e., not only humans), which makes it a suitable benchmark for evaluating out-of-distribution prediction. Additional details about datasets and features of molecule/PPI graphs are in Appendices C and D.
Strategies for Pre-training Graph Neural Networks
Dataset splitting. In many applications, conventional random split is overly optimistic and does not simulate the real-world use case, where test graphs can be structurally different from training graphs (Wu et al., 2018;Zitnik et al., 2019). To reflect the actual use case, we split the downstream data in the following ways to evaluate the models' out-of-distribution generalization. In the chemistry domain, we use scaffold split (Ramsundar et al., 2019), where we split molecules according to their scaffold (molecular substructure). In the biology domain, we use species split, where we predict functions of proteins from new species. Details are in Appendix E. Furthermore, to prevent data leakage, all test graphs used for performance evaluation are removed from the graph-level supervised pre-training datasets.
Strategies for Pre-training Graph Neural Networks
We thoroughly compare our pre-training strategy with two naïve baseline strategies: (i) extensive supervised multi-task pre-training on relevant graph-level tasks, and (ii) node-level self-supervised pre-training.
Strategies for Pre-training Graph Neural Networks
GNN architectures. We mainly study Graph Isomorphism Networks (GINs) (Xu et al., 2019), the most expressive and state-of-the-art GNN architecture for graph-level prediction tasks. We also experimented with other popular architectures that are less expressive: GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2019), and GraphSAGE (with mean neighborhood aggregation) (Hamilton et al., 2017b). We select the following hyper-parameters that performed well across all downstream tasks in the validation sets: 300 dimensional hidden units, 5 GNN layers (K = 5), and average pooling for the READOUT function. Additional details can be found in Appendix A.
Strategies for Pre-training Graph Neural Networks
Pre-training. For Context Prediction illustrated in Figure 2 (a), on molecular graphs, we define context graphs by setting inner radius r 1 = 4. On PPI networks whose diameters are often smaller than 5, we use r 1 = 1, which works well empirically despite the large overlap between the neighborhood and context subgraphs. For both molecular and PPI graphs, we let outer radius r 2 = r 1 + 3, and    Table 4 in Appendix H. Pre-training strategy for chemistry data: Context Prediction + Graph-level supervised pre-training; pre-training strategy for biology data: Attribute Masking + Graph-level supervised pre-training.
Strategies for Pre-training Graph Neural Networks
use a 3-layer GNN to encode the context structure. For Attribute Masking shown in Figure 2 (b), we randomly mask 15% of node (for molecular graphs) or edge attributes (for PPI networks) for prediction. As baselines for node-level self-supervised pre-training, we adopt the original Edge Prediction (denoted by EdgePred) (Hamilton et al., 2017a) and Deep Graph Infomax (denoted by Infomax) (Veličković et al., 2019) implementations. Further details are provided in Appendix G.
Strategies for Pre-training Graph Neural Networks
We report results for molecular property prediction and protein function prediction in Tables 2 and 1 and Figure 3. Our systematic study suggests the following trends:
Strategies for Pre-training Graph Neural Networks
Observation (1): Table 2 shows that the most expressive GNN architecture (GIN), when pre-trained, achieves the best performance across domains and datasets. Compared with gains of pre-training achieved by GIN architecture, gains of pre-training using less expressive GNNs (GCN, GraphSAGE, and GAT) are smaller and can sometimes even be negative (Table 2). This finding confirms previous observations (e.g., Erhan et al. (2010)) that using an expressive model is crucial to fully utilize pre-training, and that pre-training can even hurt performance when used on models with limited expressive power, such as GCN, GraphSAGE, and GAT.
Strategies for Pre-training Graph Neural Networks
Observation (2): As seen from the shaded cells of Table 1 and highlighted region in the middle panel of Figure 3, the strong baseline strategy that performs extensive graph-level multi-task supervised pre-training of GNNs gives surprisingly limited performance gain and yields negative transfer on many downstream tasks (2 out of 8 datasets in molecular prediction, and 13 out of 40 tasks in protein function prediction). Table 1 and the left panel of Figure 3, we see that another baseline strategy, which only performs node-level self-supervised pre-training, also gives limited performance improvement and is comparable to the graph-level multi-task supervised pre-training baseline.
Strategies for Pre-training Graph Neural Networks
Observation (4): From the lower half of Table 1 and the right panel of Figure 3, we see that our pre-training strategy of combining graph-level multi-task supervised and node-level self-supervised pre-training avoids negative transfer across downstream datasets and achieves best performance.
Strategies for Pre-training Graph Neural Networks
Observation (5): Furthermore, from Table 1 and the left panel of Figure 3, we see that our strategy gives significantly better predictive performance than the two baseline pre-training strategies as well as non-pre-trained models, achieving state-of-the-art performance.
Strategies for Pre-training Graph Neural Networks
Specifically, in the chemistry datasets, we see from Table 1 that our Context Prediction + Graph-level multi-task supervised pre-training strategy gives the most promising performance, leading to an increase in average ROC-AUC of 7.2% over non-pre-trained baseline and 4.2% over graph-level multi-task supervised pre-trained baseline. On the HIV dataset, where a number of recent works (Wu et al., 2018;Li et al., 2017;Ishiguro et al., 2019) have reported performance on the same scaffold split and using the same protocol, our best pre-trained model (ContextPred + Supervised) achieves state-ofthe-art performance. In particular, we achieved a ROC-AUC score of 79.9%, while best-performing graph models in Wu et al. (2018) Also, in the biology datasets, which we have built in this work, we see from the left panel of Figure 3 that our Attribute Masking + Graph-level multi-task supervised pre-training strategy achieves the best predictive performance compared to other baseline strategies across almost all 40 downstream prediction tasks (the right panel of Figure 3). On average, our strategy improves ROC-AUC by 9.4% over non-pre-trained baseline and 5.2% over graph-level multi-task supervised pre-trained baseline, again achieving state-of-the-art performance.
Strategies for Pre-training Graph Neural Networks
Observation (6): In the chemistry domain, we also report performance on classic benchmarks (MUTAG, PTC molecule datasets) in Appendix B. However, as mentioned in Section 5.1, the extremely small dataset sizes make these benchmarks unsuitable to compare different methods in a statistically reliable way.
Strategies for Pre-training Graph Neural Networks
Observation (7): Beyond predictive performance improvement, Figure 4 shows that our pre-trained models achieve orders-of-magnitude faster training and validation convergence than non-pre-trained models. For example, on the MUV dataset, it took 1 hour for the non-pre-trained GNN to get 74.9% validation ROC-AUC, while it took only 5 minutes for our pre-trained GNN to get 85.3% validation ROC-AUC. The same trend holds across the downstream datasets we used, as shown in Figure 5 in Appendix I. We emphasize that pre-training is a one-time-effort. Once the model is pre-trained, it can be used for any number of downstream tasks to improve performance with little training time.
Strategies for Pre-training Graph Neural Networks
As a final remark, in our preliminary experiments, we performed the Attribute Masking and Context Prediction simultaneously to pre-train GNNs. That approach did not improve performance in our experiments. We leave a thorough analysis of the approach for future work.
Strategies for Pre-training Graph Neural Networks
We developed a novel strategy for pre-training GNNs. Crucial to the success of our strategy is to consider both node-level and graph-level pre-training in combination with an expressive GNN. This ensures that node embeddings capture local neighborhood semantics that are pooled together to obtain meaningful graph-level representations, which, in turn, are used for downstream tasks. Experiments on multiple datasets, diverse downstream tasks and different GNN architectures show that the new pre-training strategy achieves consistently better out-of-distribution generalization than non-pre-trained models.
Strategies for Pre-training Graph Neural Networks
Our work makes an important step toward transfer learning on graphs and addresses the issue of negative transfer observed in prior studies. There are many interesting avenues for future work. For example, further increasing generalization by improving GNN architectures as well as pre-training and fine-tuning approaches, is a fruitful direction. Investigating what pre-trained models have learned would also be useful to aid scientific discovery (Tshitoyan et al., 2019). Finally, it would be interesting  to apply our methods to other domains, e.g., physics, material science, and structural biology, where many problems are defined over graphs representing interactions of e.g., atoms, particles, and amino acids. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views, policies, or endorsements, either expressed or implied, of DARPA, NIH, ARO, or the U.S. Government.
Strategies for Pre-training Graph Neural Networks
The Pande Group acknowledges the generous support of Dr. Anders G. Frøseth and Mr. Christian Sundt for our work on machine learning. The Pande Group is broadly supported by grants from the NIH (R01 GM062868 and U19 AI109662) as well as gift funds and contributions from Folding@home donors.
Strategies for Pre-training Graph Neural Networks
V.S.P is a consultant & SAB member of Schrodinger, LLC and Globavir, sits on the Board of Directors of Apeel Sciences, Asimov, BioAge Labs, Ciitizen, Devoted Health, Freenome, Insitro, Omada Health, PatientPing, and is a General Partner at Andreessen Horowitz.
Strategies for Pre-training Graph Neural Networks
Here we describe GNN architectures used in our molecular property and protein function prediction experiments. For both domains we use the GIN architecture (Xu et al., 2019) with some minor modifications to include edge features, as well as center node information in the protein ego-networks.
Strategies for Pre-training Graph Neural Networks
As our primary goal is to systematically compare our pre-training strategy to the strong baseline strategies, we fix all of these hyper-parameters in our experiments and focus on relative improvement directly caused by the difference in pre-training strategies.
Strategies for Pre-training Graph Neural Networks
Molecular property prediction. In molecular property prediction, the raw node features and edge features are both 2-dimensional categorical vectors (see Appendix C for details), denoted as (i v,1 , i v,2 ) and (j e,1 , j e,2 ) for node v and edge e, respectively. Note that we also introduce unique categories to indicate masked node/edges as well as self-loop edges. As input features to GNNs, we first embed the categorical vectors by    
Strategies for Pre-training Graph Neural Networks
where N (v) is a set of nodes adjacent to v, and e = (v, v) represents the self-loop edge. Note that for the final layer, i.e., k = K, we removed the ReLU from Eq. (A.1) so that h (k) v can take negative values. This is crucial for pre-training methods based on the dot product, e.g., Context Prediction and Edge Prediction, as otherwise, the dot product between two vectors would be always positive.
Strategies for Pre-training Graph Neural Networks
The graph-level representation h G is obtained by averaging the node embeddings at the final layer, i.e.,
Strategies for Pre-training Graph Neural Networks
The label prediction is made by a linear model on top of h G .
Strategies for Pre-training Graph Neural Networks
In our experiments, we set the embedding dimension d to 300. For MLPs in Eq. (A.1), we use the ReLU activation with 600 hidden units. We apply batch normalization (Ioffe & Szegedy, 2015) right before the ReLU in Eq. (A.1) and apply dropout (Srivastava et al., 2014) to h (k) v at all the layers except the input layer.
Strategies for Pre-training Graph Neural Networks
Protein function prediction. The GNN architecture used for protein function prediction is similar to the one used for molecular property prediction except for a few differences. First, the raw input node features are uniform (denoted as X here) and second, the raw input edge features are binary vectors (see Appendix D for the detail), which we denote as c e ∈ {0, 1} d0 . As input features to GNNs, we first embed the raw features by
Strategies for Pre-training Graph Neural Networks
e ∈ R d . At each layer, GNNs update node representations by  where CONCAT(·, ·) takes two vectors as input and concatenates them. Since the downstream task is ego-network classification, we use the embedding of the center node v center together with the embedding of the entire ego-network. More specifically, we obtain graph-level representation h G by
Strategies for Pre-training Graph Neural Networks
Other GNN architectures. For GCN, GraphSAGE, and GAT, we adopt the implementation in the Pytorch Geometric library (Fey & Lenssen, 2019), where we set the number of GAT attention heads to be 2. The dimensionality of node embeddings as well as the number of GNN layers are kept the same as GIN. These models do not originally handle edge features. We incorporate edge features into these models similarly to how we do it for the GIN; we add edge embeddings into node embeddings, and perform the GNN message-passing on the obtained node embeddings.
Strategies for Pre-training Graph Neural Networks
In Table 3 we report our experiments on the commonly-used classic graph classification benchmarks (Kersting et al., 2016). Among the datasets Xu et al. (2019) used, MUTAG, PTC, and NCI1 are molecule datasets for binary classification. Out of these three, we excluded the NCI1 dataset, because it misses edge information (i.e., bond type) and therefore, we cannot recover the original molecule information, which is necessary to construct our input representations described in Appendix C.
Strategies for Pre-training Graph Neural Networks
For fair comparison, we used exactly the same evaluation protocol as Xu et al. (2019), i.e., report 10-fold cross-validation accuracy. All the hyper-parameters in our experiments are kept the same in the main experiments except that we additionally tuned dropout rate from {0, 0.2, 0.5} and the batch size from {8, 64} at the fine-tuning stage.
Strategies for Pre-training Graph Neural Networks
While the pre-trained GNNs (especially those with Context Prediction) give competent performance, all the accuracies (including all the previous methods) are within a standard deviation with each other, making it hard to reliably compare different methods. As Xu et al. (2019) has pointed out, this is due to the extremely small dataset size; a validation set at each fold only contains around 19 to 35 molecules for MUTAG and PTC, respectively. Given these results, we argue that it is necessary to use larger datasets to make reliable comparison, so we mainly focus on MoleculeNet (Wu et al., 2018) in this work.  (Zitnik et al., 2019). The original PPI networks do not have node attributes, but contain edge attributes that correspond to the degree of confidence for 7 different types of protein-protein relationships. The edge weights range from 0, which indicates no evidence for the specific relationship, to 1000, which indicates the highest confidence. The weighted edges of the PPI networks are thresholded such that the distribution of edge types across the 50 PPI networks are uniform. Then, for every node in the PPI networks, subgraphs centered on each node were generated by: (1) performing a breadth first search to select the subgraph nodes, with a search depth limit of 2 and a maximum number of 10 neighbors randomly expanded per node, (2) including the selected subgraph nodes and all the edges between those nodes to form the resulting subgraph.
Strategies for Pre-training Graph Neural Networks
The entire dataset contains 394,925 protein subgraphs derived from 50 species. Out of these 50 species, 8 species (arabidopsis, celegans, ecoli, fly, human, mouse, yeast, zebrafish) have proteins with GO protein annotations. The dataset contains 88,000 protein subgraphs from these 8 species, of which 57,448 proteins have at least one positive coarse-grained GO protein annotation and 22,876 proteins have at least one positive fine-grained GO protein annotation. For the self-supervised pre-training dataset, we use all 394,925 protein subgraphs.
Strategies for Pre-training Graph Neural Networks
We define fine-grained protein functions as Gene Ontology (GO) annotations that are leaves in the GO hierarchy, and define coarse-grained protein functions as GO annotations that are the immediate parents of leaves (Ashburner et al., 2000;Consortium, 2018). For example, a fine-grained protein function is "Factor XII activation", while a coarse-grained function is "positive regulation of protein". The former is a specific type of the latter, and is much harder to derive experimentally. The GO hierarchy information is obtained using GOATOOLS (Klopfenstein et al., 2018). The supervised pre-training dataset and the downstream evaluation dataset are derived from the 8 labeled species, as described in Appendix E. The 40-th most common fine-grained protein label only has 121 positively annotated proteins, while the 40-th most common coarse-grained protein label has 9386 positively annotated proteins. This illustrates the extreme label scarcity of our downstream tasks.
Strategies for Pre-training Graph Neural Networks
For supervised pre-training, we combine the train, validation, and prior sets described previously, with the 5,000 most common coarse-grained protein function annotations as binary labels. For our downstream task, we predict the 40 most common fine-grained protein function annotations, to ensure that each protein function has at least 10 positive labels in our test set.
Strategies for Pre-training Graph Neural Networks
For molecular prediction tasks, following Ramsundar et al. (2019), we cluster molecules by scaffold (molecular graph substructure) (Bemis & Murcko, 1996), and recombine the clusters by placing the most common scaffolds in the training set, producing validation and test sets that contain structurally different molecules. Prior work has shown that this scaffold split provides a more realistic estimate of model performance in prospective evaluation compared to random split (Chen et al., 2012;Sheridan, 2013). The split for train/validation/test sets is 80%:10%:10%.
Strategies for Pre-training Graph Neural Networks
In the PPI network, species split simulates a scenario where we have only high-level coarse-grained knowledge on a subset of proteins (prior set) in a species of interest (human in our experiments), and want to predict fine-grained biological functions for the rest of the proteins in that species (test set).
Strategies for Pre-training Graph Neural Networks
For species split, we use 50% of the protein subgraphs from human as test set, and 50% as a prior set containing only coarse-grained protein annotations. The protein subgraphs from 7 other labelled species (arabidopsis, celegans, ecoli, fly, mouse, yeast, zebrafish) are used as train and validation sets, which are split 85% : 15%. The effective split ratio for the train/validation/prior/test sets is 69% : 12% : 9.5% : 9.5%.
Strategies for Pre-training Graph Neural Networks
Here we analyze the time complexity for processing graphs in Attribute Masking and Context Prediction. First, the time complexity for Attribute Masking is linear with respect to the number of edges/nodes as it only involves sampling nodes/edges to be masked. Second, the time complexity for Context Prediction is again linear with respect to the number of edges/nodes, because it involves sampling a center node per graph plus extracting K-hop neighborhood and context graph. Extracting the neighborhood/context graphs is performed by the breadth-first search, which takes at most linear time with respect to the number of edges in the graph. In summary, the time complexity for both of our pre-training methods are at most linear with respect to the number of edges, which is as efficient as message-passing computation in GNNs, and thus, is as efficient as the ordinary supervised learning using GNNs. Also, there is almost no memory overhead as we transform data (e.g., mask input node/edge features, sample the context graphs) on-the-fly.
Strategies for Pre-training Graph Neural Networks
Optimization. All models are trained with Adam optimizer (Kingma & Ba, 2015) with a learning rate of 0.001. We use Pytorch (Paszke et al., 2017) and Pytorch Geometric (Fey & Lenssen, 2019) for all of our implementation. We run all pre-training methods for 100 epochs. For self-supervised pre-training, we use a batch size of 256, while for supervised pre-training, we use a batch size of 32 with dropout rate of 20%.
Strategies for Pre-training Graph Neural Networks
Fine-tuning. After pre-training, we follow the procedure in Section 3.3 to fine-tune the models on the training sets of the downstream datasets. We use a batch size of 32 and dropout rate of 50%. Datasets with multiple prediction tasks are fit jointly. On the molecular property prediction datasets, we train models for 100 epochs, while on the protein function prediction dataset (with the 40 binary prediction tasks), we train models for 50 epochs.
Strategies for Pre-training Graph Neural Networks
Evaluation. We evaluate test performance on downstream tasks using ROC-AUC (Bradley, 1997) with the validation early stopping protocol, i.e., test ROC-AUC at the best validation epoch is reported. For datasets with multiple prediction tasks, we take the average ROC-AUC across all their tasks. The downstream experiments are run with 10 random seeds, and we report mean ROC-AUC and standard deviation.
Strategies for Pre-training Graph Neural Networks
Computation time for pre-training. The computation time for the two stages of our pre-training is reported below. Chemistry: Self-supervised pre-training takes about 24 hours, while supervised pre-training takes about 11 hours. Biology: Self-supervised pre-training takes about 3.8 hours, while supervised pre-training takes about 2.5 hours. Table 4 shows the detailed comparison of different GNN architectures on the chemistry datasets. We see that the most expressive GIN architectures benefit most from pre-training compared to the other less expressive models.
Strategies for Pre-training Graph Neural Networks
Training and validation curves. In Figure 5, we plot training and validation curves for all the datasets used in the molecular property prediction experiments.
Strategies for Pre-training Graph Neural Networks
Additional scatter plot comparisons of ROC-AUCs. In Figure 6, we compare our Context Prediction + graph-level supervised pre-training with a non-pre-trained model and a graph-level supervised pre-trained model. We see from the left plot that the combined strategy again completely avoids negative transfer across all the 40 downstream tasks. Furthermore, we see from the right plot that additionally adding our node-level Context Prediction pre-training almost always improves ROC-AUC scores of supervised pre-trained models across the 40 downstream tasks.   ContextPred + Graph-level supervised pre-training
Strategies for Pre-training Graph Neural Networks
No pre-training Graph-level supervised pre-training only Context Prediction helps avoiding negative transfer across tasks.
Strategies for Pre-training Graph Neural Networks
Context Prediction improves generalization over pure graph-level pretraining across tasks. Figure 6: Scatter plot comparisons of ROC-AUC scores of our Context Prediction + graph-level supervised pre-training strategy versus the two baseline strategies (non-pre-trained and graph-level supervised pre-trained) on the 40 individual downstream tasks of predicting different fine-grained protein function labels.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Hypothesis. Representative graph structural patterns are universal and transferable across networks.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [1]. Leskovec et al. [28] discover that a wide range of real graphs satisfy the densification and shrinking laws. Other common patterns across networks include small world [57], motif distribution [31], community organization [34], and core-periphery structure [6], validating our hypothesis at the conceptual level.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In the past few years, however, the paradigm of graph learning has been shifted from structural pattern discovery to graph representation learning [11, 14, 25, 39-41, 47, 59], motivated by the recent advances in deep learning [4,30]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 outof-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 [39] 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?
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
The similar question has also been asked and pursued in natural language processing [10], computer vision [17], and other domains. To date, the most powerful solution is to pre-train a representation learning model from a large dataset, commonly, under the selfsupervised 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 [10] designs language model pre-training tasks to learn a Transformer encoder [52] from a large corpus. The pre-trained Transformer encoder is then adapted to various NLP tasks [55] by fine-tuning.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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?
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [58] 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?
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [59]) 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 pretrained GCC model, we apply it to unseen graphs for addressing downstream tasks.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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) [19]. Another recent work is InfoGraph [46], which focuses on learning domain-specific graph-level representations, especially  Figure 1: An illustrative example of GCC. In this example, GCC aims to measure the structural similarity between a user from the Facebook social graph and a scholar from the DBLP co-authorship network.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
for graph classification tasks. The third related work is by Hu et al. [20], who define several graph learning tasks, such as predicting centrality scores, to pre-train a GCN [25] model on synthetic graphs.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [12], ProNE [64] and Struc2vec [43] which are trained directly on the US-Airport graph, empirically demonstrating our hypothesis at the beginning.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• We design the pre-training task as subgraph instance discrimination to capture the universal and transferable structural patterns from multiple input graphs.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• We present the Graph Contrastive Coding (GCC) framework to learn structural graph representations, which leverages contrastive learning to guide the pre-training.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• We conduct extensive experiments to demonstrate that for out-ofdomain tasks, GCC can offer comparable or superior performance over dedicated graph-specific models.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In this section, we review related work of vertex similarity, contrastive learning and graph pre-training.
GCC: Graph Contrastive Coding for Graph Neural Network 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 [26] 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [36] and SimRank [21], etc. Most recently developed network embedding algorithms, such as LINE [47], DeepWalk [39], node2vec [14], also follow the neighborhood similarity assumption.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [51], structural hole [7], k-core [2], motif [5,32], etc. Consequently, models of this genre, such as Struc2vec [43] and RolX [18], usually involve explicit featurization. The second line of research leverages the spectral graph theory to model structural similarity. A recent example is Graph-Wave [12]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [25], GAT [53], GraphSAGE [16,62] and MPNN [13], leverage additional attributes as side information or supervised signals to learn representations which are further used to measure vertex similarity.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Contrastive learning is a natural choice to capture similarity from data. In natural language processing, Word2vec [30] model uses cooccurring words and negative sampling to learn word embeddings. In computer vision, a large collection of work [15,17,49,58] 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. [35] and instance discrimination task from Wu et al. [58], as discussed in Section 3.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Skip-gram based model. Early attempts to pre-train graph representations are skip-gram based network embedding models inspired by Word2vec [30], such as LINE [47], DeepWalk [39], node2vec [14], and metapath2vec [11]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Pre-training graph neural networks. There are several recent efforts to bring ideas from language pre-training [10] to pre-training graph neural networks (GNN). For example, Hu et al. [19] pretrain 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. [20], which defines several graph learning tasks to pre-train a GCN [25]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In this section, we formalize the graph neural network (GNN) pretraining 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [28,32]. 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;
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• Second, transferability, it is compatible with vertices and graphs unseen during pre-training.
GCC: Graph Contrastive Coding for Graph Neural Network 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [14,[39][40][41]47] and recent attempts on pre-training graph neural networks with attributed graphs as input and applying them within a specific domain [19].
GCC: Graph Contrastive Coding for Graph Neural Network 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 [17,58] and NLP [9,30], we propose to use subgraph instance discrimination as our pre-training task and InfoNCE [35] 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 [17,58].
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
From a dictionary look-up perspective, given an encoded query q and a dictionary of K + 1 encoded keys {k 0 , · · · , k K }, contrastive learning looks up a single key (denoted by k + ) that q matches in the dictionary. In this work, we adopt InfoNCE such that:
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
where τ 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
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
To instantiate each component in GCC, we need to answer the following three questions: • Q1: How to define subgraph instances in graphs?
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• 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?
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
• Q3: What are the proper graph encoders f q and f k ?
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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:
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
where V denotes the set of vertices and E ⊆ V × V denotes the set of edges 2 . For a vertex v, its r -neighbors are defined as
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Q2: Define (dis)similar instances. In computer vision [17], 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 [27]. 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) [50], subgraph induction, and anonymization [22,29].
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
(1) 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In addition, at each step, with a positive probability the walk returns back to the starting vertex v.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
(2) Subgraph induction. The random walk with restart collects a subset of vertices surrounding v, denoted by S v . The sub-graph G v induced by 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).
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
(3) Anonymization. We anonymize the sampled graph G v by relabeling its vertices to be {1, 2, · · · , | S v |}, in arbitrary order 3 .
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 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 [56]. 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. [42] to use 0.8 as the restart probability. The proposed GCC framework is flexible to other graph sampling algorithms, such as neighborhood sampling [16] and forest fire [27].
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [4] 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) [59], 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: The generalized positional embedding is inspired by the Transformer model in NLP [52], 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Fact. The Laplacian of path graph has eigenvectors: u k (i) = cos (πki/n − πk/2n), for 1 ≤ k ≤ n, 1 ≤ i ≤ n. Here n is the number of vertices in the path graph, and u k (i) is the entry at i-th row and k-the column of U , i.e., U = u 1 · · · u n .
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [59] and the binary indicator of the ego vertex [42] as vertex features. After encoded by the graph encoder, the final d-dimensional output vectors are then normalized by their L2-Norm [17].
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 vectorsq and {k 0 , k 1 , 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) [17]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 θ q ) by backpropagation. The parameters of f k (denoted by θ k ) are not updated by gradient descent. He et al. [17] propose a momentum-based update rule for θ k . Formally, MoCo updates θ k by θ k ← mθ k + (1 − m)θ q , where m ∈ [0, 1) is a momentum hyper-parameter. The above momentum update rule gradually propagates the update in θ q to θ k , making θ 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In addition to E2E and MoCo, there are other contrastive learning mechanisms to maintain the dictionary, such as memory bank [58]. Recently, He et al. [17] 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 taskspecific outputs.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 pretrained 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: Graph Contrastive Coding for Graph Neural Network Pre-Training
GCC as a local algorithm. As a graph algorithm, GCC belongs to the local algorithm category [45,48], 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 largescale graph learning tasks and to be friendly to the distributed computing setting.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In this section, we evaluate GCC on three graph learning tasksnode classification, graph classification, and similarity search, which have been commonly used to benchmark graph learning algorithms [12,43,46,59,60]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [44] as well as two DBLP datasets from SNAP [61] and NetRep [44], respectively. As for social graphs, we collect Facebook and IMDB datasets from NetRep [44], as well as a LiveJournal dataset from SNAP [3]. Table 1 presents the detailed statistics of datasets for pre-training.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Pre-training settings. We train for 75,000 steps and use Adam [24] for optimization with learning rate of 0.005, β 1 = 0.9, β 2 = 0.999, ϵ = 1 × 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 [−1, 1]. 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 τ is set as 0.07, and we adopt GIN [59] with 5 layers and 64 hidden units each layer as our encoders. Detailed hyper-parameters can be found in Table 6 in the Appendix.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In this section, we apply GCC to three graph learning tasks including node classification, graph classification, and similarity search.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
As prerequisites, we discuss the two fine-tuning strategies of GCC as well as the baselines we compare with.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Fine-tuning. As we discussed in Section 3.3, we adopt two finetuning strategies for GCC. We select logistic regression or SVM from the scikit-learn [38] package as the linear classifier for the freezing strategy 4 . 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [60], Struc2vec [43], GraphWave [12], graph2vec [33] and InfoGraph [46]. 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 [66] and GIN [59]. GCC with the full fine-tuning setting belongs to this category.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
For a fair comparison, we fix the representation dimension of all models to be 64 except graph2vec and InfoGraph 5 . The details of baselines will be discussed later.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [43] and Hindex [63]. 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 [63]. The labels indicate whether the h-index of the author is above or below the median.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Experimental results. We compare GCC with ProNE [64], Graph-Wave [12], and Struc2vec [43]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Setup. We use five datasets from Yanardag and Vishwanathan [60]-COLLAB, IMDB-BINARY, IMDB-MULTI, REDDITBINARY and REDDIT-MULTI5K, which are widely benchmarked in recent graph classification models [19,46,66]. 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 4 In node classification tasks, we follow Struc2vec to use logistic regression. For graph classification tasks, we follow DGK [60] and GIN [59] to use SVM [8]. 5 We allow them to use their preferred dimension size in their papers: graph2vec uses 1024 and InfoGraph uses 512.   layer to predict the label of the graph. We compare GCC with several recent developed graph classification models, including Deep Graph Kernel (DGK) [60], graph2vec [33], InfoGraph [46], DGCNN [66] and GIN [59]. Among these baselines, DGK, graph2vec and InfoGraph belong to the first category, while DGCNN and GIN belong to the second category.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network 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 [59] to train GIN and report the detailed results in Table 7 in the Appendix.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
We can see that, in each dataset, the best performance of GIN is achieved by different hyper-parameters. And by varying hyperparameters, GIN's performance could be sensitive. However, GCC on all datasets shares the same pre-training/fine-tuning hyperparameters, showing its robustness on graph classification. 
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Setup. We adopt the co-author dataset from Zhang et al. [65], 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 [18], Panther++ [65] and GraphWave [12]. We also provide random guess results for reference.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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++ [65] and GraphWave [12] which are trained in place on co-author graphs, simply applying pre-trained GCC can be competitive.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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. 
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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 [59] 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 pretraining 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Contrastive loss mechanisms. The common belief is that MoCo has stronger expression power than E2E [17], 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 [17]. 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 [17], momentum m plays a subtle role in learning high-quality representations. Table 5 shows accuracy with different momentum values on US-Airport and COL-LAB datasets. For US-Airport, the best performance is reached by m = 0.999, which is the desired value in [17], 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 [17] when setting m = 0. GCC (MoCo) converges well, but the accuracy is much worse.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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, respectively 6 .  
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
In the future, we plan to benchmark more graph learning tasks on more diverse graph datasets, such as the protein-protein association networks.   and Python 3.6. Our code and datasets will be available.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
The detailed hyper-parameters are listed in Table 6. Training times of GCC variants are listed in Figure 6. 7 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. 7 The table shows the elapsed real time for pre-training, which might be affected by other programs running on the server. 
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
A.2.1 Node Classification.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
GraphWave [12]. 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/.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Struc2vec [43]. We download the authors' official source code and use default hyper-parameters provided by the authors: (1)  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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
Code: https://github.com/leoribeiro/struc2vec.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
ProNE [64]. We download the authors' official code and keep hyper-parameters as the same: (1) step = 10; (2) θ = 0.5; (3) µ = 0.2. The dimension size is set to 64. Code: https://github.com/THUDM/ProNE/.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
DGK [60], graph2vec [33], InfoGraph [46], DGCNN [66]. 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.
GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training
GIN [59]. We use the official code released by [59] and follow exactly the procedure described in their paper: the hyper-parameters tuned for each dataset are: (1) the number of hidden units ∈ {16, 32} for bioinformatics graphs and 64 for social graphs; (2) the batch size ∈ {32, 128}; (3) the dropout ratio ∈ {0, 0.5} after the dense layer; (4) the number of epochs, i.e., a single epoch with the best
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Graphs have proven to be an effective way to represent very diverse types of data including social networks [38], biological reaction networks [46], protein-protein interactions [29], the quantum mechanical properties of individual molecules [59,20], and many more. Graphs provide explicit information about the coupling between individual units in a larger part along with a well defined framework for assigning properties to the nodes and the edges connecting them. There has been a significant amount of previous work done studying many aspects of graphs including link prediction [13,57] and node prediction [2]. Due to its flexibility, graph-like data structures can capture rich information which is critical in many applications.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
At the lowest level, much work has been done on learning node representations-low-dimensional vector embeddings of individual nodes [47,53,16]. Another field that has attracted a large amount of attention recently is learning representations of entire graphs. Such a problem is critical in a variety of applications such as predicting the properties of molecular graphs in both drug discovery and material science [7,6]. There has been some recent progress based on neural message passing algorithms [15,59], which learn the representations of entire graphs in a supervised way. These methods have been shown achieving state-of-the-art results on a variety of different prediction tasks [25,59,15,6].
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
However, one of the most difficult obstacles for supervised learning on graphs is that it is often very costly or even impossible to collect annotated labels. For example, in the chemical domain labels are typically produced with a costly Density Functional Theory (DFT) calculation. One option is to use semi-supervised methods which combine a small handful of labels with a larger, unlabeled, dataset. In real-world applications, partially labeled datasets are common, making tools that are able to efficiently utilize the present labels particularly useful.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Coming up with methods that are able to learn unsupervised representations of an entire graph, as opposed to nodes, is an important step in working with unlabeled or partially labeled graphs [36,18,39]. For example, there exists work that explores pre-training techniques for graphs to improve generalization [18]. Another common approach to unsupervised representation learning on graphs is through graph kernels [48,21,43]. However, many of these methods do not provide explicit graph embeddings which many machine learning algorithms operate on. Furthermore, the handcrafted features of graph kernels lead to high dimensional, sparse or non-smooth representations and thus result in poor generalization performance, especially on large datasets [36].
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Unsupervised learning of latent representations is also an important problem in other domains, such as image generation [24,22] and natural language processing [32]. A recent work introduced Deep Infomax, a method that maximizes the mutual information content between the input data and the learned representation [17]. This method outperforms other methods on many unsupervised learning tasks. Motivated by Deep InfoMax [17], we aim to use mutual information maximization for unsupervised representation learning on the entire graph. Specifically, our objective is to maximize the mutual information between the representations of entire graphs and the representations of substructures of different granularity. We name our model InfoGraph.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We also propose a semi-supervised learning model which we name InfoGraph*. We employ a student-teacher framework similar to Mean-Teacher method [54]. We maximize the mutual information between intermediate representations of the two models so that the student model learns from the teacher model. The student model is trained on the labeled data using a supervised objective function while the teacher model is trained on unlabeled data with InfoGraph. Using InfoGraph*, we achieve performance competitive with state-of-the-art methods on molecular property prediction.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We summarize our contributions as follows:
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
• We propose InfoGraph, an unsupervised graph representation learning method based on Deep InfoMax (DIM) [17].
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
• We show that InfoGraph can be extended to semi-supervised prediction tasks on graphs.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
• We empirically show that InfoGraph surpasses state-of-the-art performance on graph classification tasks with unsupervised learning and obtains performance comparable with state-of-art methods on molecular property prediction tasks using semi-supervised learning.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Representation learning for graphs has mainly dealt with supervised learning tasks. Recently, however, researchers have proposed algorithms that learn graph-level representations in an unsupervised manner [36,1].
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Concurrently to this work, information maximizing graph neural networks (IGNN) was introduced which uses mutual information maximization between edge states and transform parameters to achieve state-of-the-art predictions on a variety of supervised molecule property prediction tasks [7]. In this work, our focus is on unsupervised and semi-supervised scenarios.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Graph Kernels. Constructing graph kernels is a common unsupervised task in learning graph representations. These kernels are typically evaluated on node classification tasks. In graph kernels, a graph G is decomposed into (possibly different) {G s } sub-structures. The graph kernel K(G 1 , G 2 ) is defined based on the frequency of each sub-structure appearing in G 1 and G 2 respectively. Namely, K(G 1 , G 2 ) = f Gs 1 , f Gs 2 , where f Gs is the vector containing frequencies of {G s } sub-structures, and , is an inner product in an appropriately normalized vector space. Much work has been devoted to deciding which sub-structures are more suitable than others, popular ones are graphlets [48,52], random walk and shortest path kernels [21,3], and the Weisfeiler-Lehman subtree kernel [51]. Furthermore, deep graph kernels [63], graph invariant kernels [43], optimal assignment graph kernels [28] and multiscale laplacian graph kernels [27] have been proposed with the goal to redefine kernel functions to appropriately capture sub-structural similarity at different levels. Another line of research in this area focuses on efficiently computing these kernels either through exploiting certain structural dependencies, or via approximations/randomization [11,9,37]. Instead of defining hand crafted similarity measures between substructures, InfoGraph adopts a more principled metric -mutual information.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Contrastive methods. An important approach for unsupervised representation learning is to train an encoder to be contrastive between representations that capture statistical dependencies of interest and those that do not. For example, a contrastive approach may employ a scoring function, training the encoder to increase the score on "real" input (a.k.a, positive examples) and decrease the score on "fake" input (a.k.a., negative samples).
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Contrastive methods are central many popular word-embedding methods [8,35,33]. Word2vec [32] is an unsupervised algorithm which obtains word representations by using the representations to predict context words (the words that surround it). Doc2vec [31] is an extension of the continuous Skip-gram model that predicts representations of words from that of a document containing them. Researchers extended many of these unsupervised language models to learn representations of graph-structured input [1,36]. For example, graph2vec [36] extends Doc2vec to arbitrary graphs. Intuitively, for graph2vec a graph and the rooted subgraphs in it correspond to a document and words in a paragraph vector, respectively. One of the technical contributions of the paper is using the Weisfeiler-Lehman relabelling algorithm [58,51] to enumerate all rooted subgraphs up to a specified depth. InfoGraph can be interpreted as an extension of graph2vec though there are many major differences such as instead of listing all rooted subgraphs explicitly, we make use of graph neural networks to obtain patch representations of subgraphs.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Deep Graph InfoMax (DGI) [55] also belongs to this category, which aims to train a node encoder that maximizes mutual information between node representations and the pooled global graph representation. Although we built upon a similar methodology, our aim is different than theirs as our goal is to obtain embeddings at the whole graph level for unsupervised and semi-supervised learning whereas DGI only evaluates node level embeddings. In order to differentiate our method with Deep Graph Infomax ( [55]), we term our model InfoGraph.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Semi-supervised Learning. A comprehensive overview of semi-supervised learning (SSL) methods is out of the scope of this paper. We refer readers to [67,5,42]. Here, we discuss 2 state-of-the-art methods applicable for regression tasks which solely involve adding an additional loss term to the training of a neural network, and otherwise leave the training and model unchanged from what would be used in the fully-supervised setting. Virtual Adversarial Training (VAT) [34], a method that approximates a tiny perturbation r adv to add to input data which most significantly affect the output of the prediction function. We did not include VAT in our experiments as small perturbation on molecular graphs can lead to drastically different results in real world scenarios. Mean Teacher [54] adds a loss term which encourages the distance between the original network's output and the teacher's output to be small. The teacher's predictions are made using an exponential moving average of parameters from previous training steps. Inspired by the "student-teacher" framework in Mean Teacher model, our semi-supervised model (InfoGraph*) deploys two separate encoders but instead of explicitly encouraging the output of the student model to be similar to the teacher model's output, we enable the student model to learn from the teacher model by maximizing mutual information between intermediate representations learned by two models.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Most recent work on graphs focus on supervised learning tasks or learning node representations. However, many graph analytic tasks such as graph classification, regression, and clustering require representing entire graphs as fixed-length feature vectors. Though graph-level representations can be obtained through the node-level representations implicitly, explicitly extracting the graph can be more straightforward and optimal for graph-oriented tasks.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Another scenario that is important, yet attracts comparatively less attention in the graph related literature is semisupervised learning. One of the biggest challenges in prediction tasks in biology [62,64] or molecular machine learning [10,15,19] is the extreme scarcity of labeled data. Therefore, semi-supervised learning, in which a large number of unlabeled samples are incorporated with a small number of labeled samples to enhance accuracy of models, will play a key role in these areas.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
In this section, we first formulate an unsupervised whole graph representation learning problem and a semi-supervised prediction task on graphs. Then, we present our method to learn graph-level representations. Afterwards we present our proposed model for the semi-supervised learning scenario. Figure 1: Illustration of InfoGraph. An input graph is encoded into a feature map by graph convolutions and jumping concatenation. The discriminator takes a (global representation, patch representation) pair as input and decides whether they are from the same graph. InfoGraph uses a batch-wise fashion to generate all possible positive and negative samples. For example, consider the toy example with 2 input graphs in the batch and 7 nodes (or patch representations) in total. For the global representation of the blue graph, there will be 7 input pairs to the discriminator and same for the red graph. Thus, the discriminator will take 14 (global representation, patch representation) pairs as input in this case.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Unsupervised Graph Representation Learning. Given a set of graphs G = {G 1 , G 2 , ...} and a positive integer δ (the expected embedding size), our goal is to learn a δ-dimensional distributed representation of every graph G i ∈ G.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We denote the number of nodes in G i as |G i |. We denote the matrix of representations of all graphs as Φ ∈ R |G|×δ .
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Semi-supervied Graph Prediction Tasks. Given a set of labeled graphs G L = {G 1 , · · · , G |G L | } with corresponding output {o 1 , · · · , o |G L | }, and a set of unlabeled samples G U = {G |G L |+1 , · · · , G |G L |+|G U | }, our goal is to learn a model that can make predictions for unseen graphs. Note that in most cases |G U | |G L |.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We focus on graph neural networks (GNNs)-a flexible class of embedding architectures which generate node representations by repeated aggregation over local node neighborhoods. The representations of nodes are learned by aggregating the features of their neighborhood nodes, so we refer to these as patch representations. GNNs utilize a READOUT function to summarize all the obtained patch representations into a fixed length graph-level representation.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Formally, the k-th layer of a GNN is
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
where h (k) v is the feature vector of node v at the k-th iteration/layer (or patch representation centered at node i), e uv is the feature vector of the edge between u and v, and N (v) are neighborhoods to node v. h (0) v is often initialized as node features. READOUT can be a simple permutation invariant function such as averaging or a more sophisticated graph-level pooling function [65,66].
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We seek to obtain graph representations by maximizing the mutual information between graph-level and patch-level representations. By doing so, the graph representations can learn to encode aspects of the data that are shared across all substructures. Assume that we are given a set of training samples G := {G j ∈ G} N j=1 with empirical probability distribution P on the input space. Let φ denote the set of parameters of a K-layer graph neural network. After the first k layers of the graph neural network, the input graph will be encoded into a set of patch representations {h
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Next, we summarize feature vectors at all depths of the graph neural network into a single feature vector that captures patch information at different scales centered at every node. Inspired by [61], we use concatenation. That is, Figure 2: Illustration of the semi-supervised version of InfoGraph (InfoGraph*). There are two separate encoders with the same architecture, one for the supervised task and the other trained using both labeled and unlabeled data with an unsupervised objective (eq. (4)). We encourage the mutual information of the two representations learned by the two encoders to be high by deploying a discriminator that takes a pair of representation as input and determines whether they are from the same input graph.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
where h i φ is the summarized patch representation centered at node i and H φ (G) is the global representation after applying READOUT. Note that here we slightly abuse the notation of h.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We define our mutual information (MI) estimator on global/local pairs, maximizing the estimated MI over the given
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
I φ,ψ is the mutual information estimator modeled by discriminator T ψ and parameterized by a neural network with parameters ψ. We use the Jensen-Shannon MI estimator (following the formulation of [41]),
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
where x is an input sample, x (negative sample) is an input sampled fromP = P, a distribution identical to the empirical probability distribution of the input space, and sp(z) = log(1 + e z ) is the softplus function. In practice, we generate negative samples using all possible combinations of global and local patch representations across all graph instances in a batch.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Since H φ (G) is encouraged to have high MI with patches that contain information at all scales, this favours encoding aspects of the data that are shared across patches and aspects that are shared across scales. The algorithm is illustrated in Fig. 1.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
It should be noted that our model is similar to Deep Graph Infomax (DGI) [55], a model proposed for learning unsupervised node embeddings. However, there are important design differences due to the different problems that we are focusing on. First, in DGI they use random sampling to obtain negative samples due to the fact that they are mainly focusing on learning node embeddings on a graph. However, contrastive methods require a large number of negative samples to be competitive [17], thus the use of batch-wise generation of negative samples is crucial as we are trying to learn graph embeddings given many graph instances.Second, the choice of graph convolution encoders is also crucial. We use GIN [60] while DGI uses GCN [26] as GIN provides a better inductive bias for graph level applications. Graph neural network designs should be considered carefully so that graph representations can be discriminative towards other graph instances. For example, we use sum over mean for READOUT and that can provide important information regarding the size of the graph.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Based on the previous unsupervised model, a straightforward way to do semi-supervised property prediction on graphs is to combine the purely supervised loss and the unsupervised objective function which acts as a regularization term. In doing so, the model is trained to predict properties for the labeled dataset while keeping a rich discriminative intermediate representation learned from both the labeled and the unlabeled dataset. That is, we try to minimize the following objective function:
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
where L supervised (y φ (G i ), o i ) is defined as the loss function of graph G i that measures the discrepancy between the classifier output y φ (G i ) and the true output o i . L unsupervised (h φ (G j ); H φ (G j ) is the unsupervised InfoGraph loss term as defined in eq. (4) that can be optimized using both labeled and unlabeled data. The hyper-parameter λ controls the relative weight between the purely supervised and the unsupervised loss. The intuition behind this is that the model will benefit from learning a good representation from the large amount of unlabeled data while learning to predict the corresponding supervised label.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
However, supervised tasks and unsupervised tasks may favor different information or a different semantic space. Simply combining the two loss functions using the same encoder may lead to "negative transfer" 1 [44,50]. Inspired by the "student-teacher" framework in many semi-supervised learning methods [30,54], we derive a simple way to alleviate this problem. For example, in the Mean Teacher model [54], the teacher model is an exponential moving average of student model's parameters from previous training steps and they encourage student model's output to be similar to teacher model's output. Similarly, we deploy two encoder models on labelled data and unlabelled data respectively. We believe that the supervised encoder (student) can benefit if it incorporates information learned from the unsupervised encoder (teacher) as it is trained on many more data points. However, encouraging the output of two encoders to be similar does not make sense as the two encoders are trained with different objectives. Therefore, instead of adding a loss term that encourages the output of the two networks to be similar, we add a loss term that encourages the representations learned by the two encoders to have high mutual information. Now, let ϕ denote the set of parameters of another K-layered graph neural network, identical to the one parameterized by φ, and let λ be a tunable hyper-parameter. The total loss function can be defined as follows:
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
In our semi-supervised experiments, we refer to the naive method using the objective function given in eq. (6) as InfoGraph. We refer to the method that uses two separate encoders and employ the objective function given in eq. (8) as InfoGraph*. InfoGraph* is fully summarized in Figure 2.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
We evaluate the effectiveness of the graph-level representation learned by InfoGraph on downstream graph classification tasks and on semi-supervised molecular property prediction tasks.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For graph classification, we conduct experiments on 6 well-known benchmark datasets: MUTAG, PTC, REDDIT-BINARY, REDDIT-MULTI-5K, IMDB-BINARY, and IMDB-MULTI ( [63]).
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For semi-supervised learning tasks, we use the publicly available QM9 dataset [49]. All molecules in the dataset consist of Hydrogen (H), Carbon (C), Oxygen (O), Nitrogen (N), and Flourine (F) atoms and contain up to 9 non Hydrogen atoms. In all, this results in about 134,000 drug-like organic molecules that span a wide range of chemical compositions and properties. A total of 12 interesting and fundamental chemical properties are pre-computed for each molecule.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For a more detailed description of these datasets and properties, see the supplementary material.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For graph classification, we used 6 state-of-the-art graph kernels for comparison: Random Walk (RW) [14], Shortest Path Kernel (SP) [3], Graphlet Kernel (GK) [52], Weisfeiler-Lehman Sub-tree Kernel (WL) [51], Deep Graph Kernels (DGK) [63], and Multi-Scale Laplacian Kernel (MLG) [27]. Aside from graph kernels, we also compare with 3 unsupervised graph-level representation learning methods: node2vec [16], sub2vec [1], and graph2vec [36]. Node2vec is a neural embedding framework that learns feature representations of individual nodes in graphs and eventually aggregates node embeddings to obtain graph embeddings.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For semi-supervised tasks, aside from comparing the results with the fully supervised results, we also compare our results with a state-of-the-art semi-supervised method: Mean-Teachers [54].
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For graph classification tasks, we adopt the same procedure of previous works [40,56,63,66] to make a fair comparison and used 10-fold cross validation accuracy to report the classification performance. Experiments are repeated 5 times. We report results from previous papers with the same experimental setup if available. If results are not previously reported, we implement them and conduct a hyper-parameter search according to the original paper. For node2vec [16], we took the result from [36] but we did not run it on all datasets as the implementation details are not clear in the paper. For Deep Graph Kernels, we report the best result out of Deep WL Kernels, Deep GK Kernels, and Deep RW Kernels. For sub2vec, we report the best result out of its two variants: sub2vec-N and sub2vec-S. For all methods, the embedding dimension is set to 512 and parameters of downstream classifiers are independently tuned using cross validation on training folds of data. The best average classification accuracy is reported for each method. The classification accuracies are computed using LIBSVM [4], and the C parameter was selected from {10 −3 , 10 −2 , . . . , 10 2 , 10 3 }.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
The QM9 dataset has 130462 molecules in it. We adopt similar experimental settings as traditional semi-supervised methods [54,30,34]. We randomly chose 5000 samples as labeled samples for training and another 10000 as validation samples, 10000 samples for testing, and use the rest as unlabeled training samples. Note that we use the exact same split when running the supervised model and the semi-supervised model. We use the validation set to do model selection and we report scores on the test set. All targets were normalized to have mean 0 and variance 1. We minimize the mean squared error between the model output and the target, although we evaluate mean absolute error.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For the unsupervised experiments, we use the Graph Isomorphism Network (GIN) [60]. For the semi-supervised experiments, we adopt a similar model configuration as in [15]. The number of set2set computations is set to 3. Models were trained using SGD with the Adam optimizer [23] with an initial learning rate 0.001. We train for 500 epochs with a batch size 20. As recommended in [42], we use the exact same underlying model architecture when comparing semi-supervised learning approaches as our goal is not to produce state-of-the-art results, but instead to provide a rigorous comparative analysis in a common framework. For the supervised case, the weight decay is chosen from {0, 10 −3 , 10 −4 }. For InfoGraph and InfoGraph*, λ is chosen from {10 −3 , 10 −4 , 10 −5 }.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
Hyper-parameters are chosen based on the validation error.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
The discriminator scores global-patch representation pairs by passing two representations to different non-linear transformations and then takes the dot product of the two transformed representations. Both non-linear transformations are parameterized by 3-layered feed-forward neural networks with jumping connections. Following each linear layer is a ReLU activation function. We use Pytorch [45] and the Pytorch Geometric [12] libraries for all our experiments.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
The results of evaluating unsupervised graph level representations using downstream graph classification tasks are presented in Table 1. We show results from six methods including three state-of-the-art graph kernel methods: WL [51], DGK [63], and MLG [27]. While these kernel methods perform well on individual datasets, none of them are competitive across all of the datasets. Additionally, MLG suffers from a long run time and take more than 24 hours to   run on the two larger benchmark datasets. We find that InfoGraph outperforms all of these baselines on 4 out of 6 of the datasets. In the other 2 datasets, InfoGraph still has very competitive performance.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
The results of the semi-supervised learning experiments on the molecular property prediction task are presented in Table  2. We observe that by simply combining the supervised objective with the unsupervised infomax objective (InfoGraph) obtains better performance compared to the purely supervised models on 7 out of 12 of the targets. However, in 1 out of 12 targets it does not obtain better performance and in 4 out of 12 targets, it results in poorer performance. This "negative transfer" effect may be caused by the fact that the supervised objective and the unsupervised objective favor different information or different latent semantic space. This effect is alleviated with InfoGraph*, our modified version of InfoGraph for semi-supervised learning. InfoGraph* improves over the supervised model in 11 out of 12 targets and gets a tie on 1 target. InfoGraph* obtains the best result on 7 targets while the Mean Teacher method obtains the best results on 6 targets (with one overlap). However, the Mean Teacher model yields worse performance on 2 targets when compared to the supervised result.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
In this paper, we propose InfoGraph to learn unsupervised graph-level representations and InfoGraph* for semisupervised learning. We conduct experiments on graph classification and molecular property prediction tasks to evaluate these two methods. Experimental results show that InfoGraph and InfoGraph* are both very competitive with state-of-the-art methods. There are many research works on semi-supervised learning on image data, but few of them focus on semi-supervised learning for graph structured data. In the future, we aim to explore semi-supervised frameworks designed specifically for graphs.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
MUTAG contains 188 mutagenic aromatic and heteroaromatic nitro compounds with 7 different discrete labels. PTC is a dataset of 344 different chemical compounds that have been tested for carcinogenicity in male and female rats. This dataset has 19 discrete labels. IMDB-BINARY and IMDB-MULTI are movie collaboration datasets. Each graph corresponds to an ego-network for each actor/actress, where nodes correspond to actors/actresses and an edge is drawn between two actors/actresses if they appear in the same movie. Each graph is derived from a pre-specified genre of movies, and the task is to classify the genre graph it is derived from. REDDIT-BINARY and REDDIT-MULTI5K are balanced datasets where each graph corresponds to an online discussion thread and nodes correspond to users. An edge was drawn between two nodes if at least one of them responded to another's comment. The task is to classify each graph to the community or subreddit that it belongs to.
I NFO G RAPH : U NSUPERVISED AND S EMI - SUPERVISED G RAPH -L EVEL R EPRESENTATION L EARNING VIA M UTUAL I NFORMATION M AXIMIZATION
For a description of the properties in the QM9 dataset see section 10.2 of [15].