Pairwise Half-graph Discrimination: A Simple Graph-level Self-supervised Strategy for Pre-training Graph Neural Networks

1 Introduction

Graph modeling has recently received broad interest because of the increasing number of non-Euclidean data that needs to be analyzed across various areas, including social networks, physics, and bioinformatics [Hamilton et al., 2017b]. The graph neural network (GNN) [Kipf and Welling, 2017; Velickovic et al., 2018; Hamilton et al., 2017a], a deep learning-based method, has been reported to be a powerful tool for graph representation learning. However, supervised training of GNN usually requires labor-intensive labeling and relies on domain expert knowledge. One way to alleviate the need for large labeled data is to pre-train a GNN on unlabeled data via self-supervised learning, and then transfer the learned model to downstream tasks. This transfer learning methodology has achieved great success in nature language process (NLP) and computer vision (CV) [Liu et al., 2020b]. But, there is less exploration [Hu et al., 2019; Hu et al., 2020; Rong et al., 2020; You et al., 2020] of pre-training schemes for GNNs compared to NLP and CV domains. Current pretraining schemes for GNN mainly focus on unsupervised representation learning [Sun et al., 2019], which learn graph embeddings on a dataset and the embeddings are fed into a classifier for the downstream task on this same dataset. The stateof-the-art method in unsupervised node and graph classification is contrastive learning. Contrastive learning techniques are used to train an encoder that builds discriminative representations by comparing positive and negative samples to maximize the mutual information [Liu et al., 2020b]. Most of them employ the batch-wise positive/negative samples generation for contrastive discrimination, which bring huge computation costs and unsuitability for pre-training on large-scale datasets, while large-scale dataset is essential for pre-training.

∗These two authors contributed equally.

†Corresponding Author.

The reason for less works on graph transfer learning might be that some graph datasets are limited in size and GNNs often have shallow architectures [You et al., 2020]. In fact, the graph datasets are recently getting larger (e.g. molecular graph data), and even for shallow GNNs, pre-training could provide a better initialized parameters than random initialization. Moreover, recent researches have proposed many theories and architectures about deep GNNs [Li et al., 2020; Liu et al., 2020a]. Nowadays, some works have proven the significance of GNN transfer learning. For example, Hu et.al. [Hu et al., 2019] and GROVER [Rong et al., 2020] have pre-trained the GNN model on large-scale molecular graph data and achieved impressive performance on multiple molecular properties prediction tasks by transferring the pre-trained model to downstream datasets. However, most of these strategies fell into node-level representation learning, which might not capture global information well and result in limited performance in downstream graph-level tasks. In general, self-supervised learning and pre-training are still insufficiently explored for GNNs.

In this paper, we propose a novel self-supervised strategy, named Pairwise Half-graph Discrimination (PHD), for pretraining GNNs at graph-level. The key idea of PHD is to learn to compare two half-graphs (each decomposed from a graph) and discriminate whether they come from the same source (binary classification). In particular, we employ a virtual node to integrate the information of two half-graphs based on the message passing of GNN. The representation of the virtual node, serving as the global representation of the given two half-graphs, learns to predict the true label of the classification task via maximum likelihood estimation. We conduct a systematic empirical study on the pre-training of various GNN models, to evaluate PHD on transfer learning and unsupervised representation learning. The results demonstrate that PHD is an effective pre-training strategy for graph data.

To summarize, our work presents the following key contributions:

• We propose a novel and simple self-supervised strategy named PHD which explicitly pre-trains a GNN at graphlevel.
• Extensive experiments indicate that PHD achieves superior or comparable results to the state-of-the-art methods on graph transfer learning and unsupervised representation learning.
• Our PHD can cooperates well with node-level strategies, and can generalize well to different GNN models.
• We provide a procedure to evaluate whether a selfsupervised strategy can empower GNN to learn graphlevel knowledge. By this way, we find PHD can capture intrinsic patterns underlying the graph structures.

2 RelatedWorks

Transfer Learning. Transfer learning refers to pre-training a model and re-purposing it on different tasks [Hu et al., 2019]. Although transfer learning is a common and effective approach for NLP and CV, it is rarely explored for GNNs, due to the diverse fields that graph-structured data sources are from [You et al., 2020]. Current transfer learning schemes on graph data are mainly inspired by language model, such as AttrMasking [Hu et al., 2019], ContextPred [Hu et al., 2019], GPT-GNN [Hu et al., 2020], and GROVER [Rong et al., 2020]. However, most of these strategies fell into node-level representation learning, which might can not capture global information well. Besides the language model inspired methods, some works began to use contrasive learning for transfer learning on graph data, including GraphCL [You et al., 2020] and MICRO-Graph [Zhang et al., 2020].

Unsupervised Learning. Traditional graph unsupervised learning methods are mainly based on graph kernels. Compared to graph kernel, contrastive learning methods can learn explicit embedding, and achieve better performance, which are the current state-of-the-art in unsupervised node and graph classification tasks. Generally, current contrastive graph learning employs a node-node contrast [Veliˇckovi´c et al., 2019] or node-graph contrast [Sun et al., 2019; Hassani and Khasahmadi, 2020] to maximize the mutual information.

3 Methodology

3.1 PHDOverview

In order to train a model that captures the global graph information, we pre-train the model with a binarized Pairwise Half-graph Discrimination (PHD) task that can be easily established from any graph database. Simply, PHD task is designed to discriminate whether two half-graphs come from the same source. As shown in Figure 1, the graph is firstly decomposed into two half-graphs, one of these two halfgraphs has a 0.5 possibility to be replaced by a half-graph disconnected from another graph which constitutes the negative sample, otherwise the positive sample. Actually, we can regard PHD as a jigsaw puzzle. We assume that two halfgraphs decomposed from the same source can be combined into a valid graph, while two half-graphs from the different source can not. By making the model to combine two subgraph and distinguish whether they can form a valid graph by piecing together, the model can learn the global topological structure in this training process of comparing and combining.

To collect the information from the half-graph pair and learn the graph-level features, a virtual node, called collection node, is added to connect with all other nodes by virtual edges. The embedding hc of collection node is learned by GNN. Formally, during each message-passing iteration k in a GNN, the vertex update function Uk updates each node's hidden states hi, based on the messages from representations of neighboring nodes and edges.

where Ni represents the neighbors of node i, Mk is the messsage passing function, eij denotes the edge between the node i and node j. And mki denotes the message node i receives during iteration k.

The message passing runs for K iterations and sequentially updates each node's representation. The final embedding hKc of collection node is fed into a simple linear discriminator to make a binary prediction,

where σ represents the sigmoid activation function, NN is a single-layer perceptron network. We employed the crossentropy loss function for simple computation to optimize the parameters of the network as follows:

where m is the number of samples. After pre-trained, the collection node embedding can be regarded as a graph-level representation for the graph and used for downstream tasks. In addition, graph representation can also be obtained by averaging the nodes' embeddings or other global graph pooling methods.

In the following sections, we describe the important components of PHD in detail.

3.2 Graph Decomposition and Negative Sampling

We decompose the graph into two half-graphs to generate the half-graph pairs, served as the positive sample, and replace one of the half-graphs to produce the negative sample. As the example shown in Figure 2, given a graph G = (V,E) where V represents nodes and E represents edges. A sampled node v3 is employed as the border node to separate G into two half-graphs Gs,1 and Gs,2, where Gs,1 contains nodes {v0, v1, v2} and Gs,2 contains nodes {v3, v4, · · · , v7}. The edges in these two half-graphs correspond to the top-left submatrix and bottom-right sub-matrix of the adjacency matrix respectively. In order to produce half-graphs with balanced and various size, the border node index is randomly sampled in the range of 1/3 to 2/3 of the total number of nodes.

For negative sampling, we randomly sample another graph in the dataset and separate it into two half-graphs using the above method, and Gs,2 is replaced with one of these two half-graphs to generate a negative sample. How negative samples are generated can have a large impact on the quality of the learned embeddings. It may drive the model to identify whether the two graphs are homologous or estimate whether the two graphs can be combined into a valid graph. In this way, the model can learn the valuable graph-level features of graphs from the nodes and edges which is essential for the downstream tasks.

3.3 Virtual Collection Node

The half-graph pair obtained via the above approach are two independent graphs without any connection. We concatenate these two half-graphs into a single whole graph, and introduce a virtual collection node to derive the global graph-level representation by aggregating every node information. The collection node is linked with all the other nodes by virtual directed edges, pointing from the other nodes to the collection node. During the message passing process of GNN, the collection node learns its representation from all the other nodes but does not affect the feature update procedure of them. Consequently, the collection node's feature can grasp the global representation of the half-graphs pair and be fed into a feedforward neural network for the final prediction.

3.4 Input Representation

As shown in Figure 3, the input representation consists of two parts: feature embedding and segment embedding. A graph is generally described by a set of nodes features and edges features. Besides the feature embedding, we add a learned segmentation embedding to every node and every edge indicating which half-graph it belongs to. Specifically, we label each node and edge of Gs,1 as 0, each node and edge of Gs,2 as 1, collection node and edges connected to collection node as 2. Then these segment labels are fed into the embedding layer that yields segment embedding. The final input representation is constructed by summing the segment embedding and feature embedding. In this way, the model could distinguish the nodes and edges from different segments, thus enables simultaneous input of two graphs.

4 Experiments on Transfer Learning

We performed experiments on transfer learning on molecular property prediction following [Hu et al., 2019; You et al., 2020], which pre-trains GNNs on a large-scale molecular graph data and finetunes the model in different datasets to evaluate the transferability of the pre-training scheme.

4.1 Datasets

For pre-training, our PHD is performed on 2 million unlabeled molecules sampled from the ZINC15 [Sterling and Irwin, 2015] database. After pre-training, we fine-tuned the model on 8 downstream task datasets including MUV, HIV, BACE, BBBP, Tox21, ToxCast, SIDER, and ClinTox. All the molecules in these datasets are described by a set of node and bond features obtained by RDKit as same as Hu et al. [Hu et al., 2019].

4.2 Experimental Setup

We evaluate the effectiveness of PHD from three perspective on large-scale graph data: 1) Whether PHD can pretrain better GNNs that generalize well on graph classification tasks; 2)Whether our graph-level strategy-PHD can cooperate well with node-level strategies; 3)Whether PHD can generalize well to different GNNs.

For perspective 1), we systematically compared PHD with some strong baselines including Infomax [Veliˇckovi´c et al., 2019], EdgePred [Hamilton et al., 2017b], AttrMasking [Hu et al., 2019], ContextPred [Hu et al., 2019], and GraphCL [You et al., 2020]. For perspective 2), we combined PHD with the node-level strategies-AttrMasking and ContextPred to test whether the performances are improved. For perspective 3), we chose four popular GNN architectures including GIN [Xu et al., 2018], GCN [Kipf and Welling, 2017], GAT [Velickovic et al., 2018] and GraphSAGE [Hamilton et al., 2017a] to evaluate PHD.

4.3 Experiment Configuration

We adopt same experimental setting as Hu et al. [Hu et al., 2019]. The different GNN architectures including GIN, GCN, GAT, and GraphSAGE were adapted from the implementation in Hu et al. [Hu et al., 2019]. All the GNN architectures have 5 GNN message passing layers with 300 embedding dimension. We run all pre-training methods for 100 epochs with a learning rate of 0.001 and a batch size of 256 on 2 million molecules from ZINC15. After pre-training, we add a linear classifier to fine-tune on 8 datasets above. We split these datasets via scaffold split [Hu et al., 2019] with the ratio of 8:1:1 (train:validation:test). We train models for 100 epochs with a learning rate of 0.001 and the dropout rate of 50%. The validation sets were used for model selection and the ROC-AUC scores on test sets are reported. We report the mean ROC-AUC and standard deviation of experiments with 10 random seeds. We report results from previous papers with the same experimental setup if available.

4.4 Experimental Results

Whether PHD Can Pre-train Better GNN?

The upper half of Table 1 shows that our PHD strategy gives better predictive performance than the previous strategies in terms of the average ROC-AUC score on eight datasets. For example, on Toxcast, we observe 3.4% relative improvement over previous state-of-the-art. These results indicate that leveraging global structural information plays a more essential role in self-supervised graph learning. In particular, the edges between the collection node and other nodes in our PHD strategy can be unidirectional or bidirectional. We conduct the ablation study of the edges direction. Table 1 shows that unidirectional edges outperform bidirectional edges (biPHD) in terms of average ROC-AUC. What is more, the bidirectional edges need more computation than unidirectional edges, so we employed the unidirectional message passing for collection node in all our experiments.

Aside from above methods, we also compare with the other four recent proposed strategies as InfoGraph [Sun et al., 2019], GPT-GNN [Hu et al., 2020], GROVER [Rong et al., 2020], and MICRO-Graph [Zhang et al., 2020]. Because InfoGraph has a huge computation cost that unsuited to pretrain on large-scale dataset, we pre-trained on a small-scale dataset following the same experimental setting as MICROGraph. Specifically, we pre-trained DeeperGCN [Li et al., 2020] on the HIV dataset which contains 40K molecules. Then we fine-tuned the pre-trained model on downstream tasks. The best 10-fold cross validation ROC-AUC scores averaged over 10 folds are reported in Table 2. Table 2 shows that PHD outperform previous best schemes on 6 of 7 datasets by a large margin (about 5.5% average improvement).

Whether PHD Can Cooperate Well with Node-level Strategies?

In general, to pre-train well on graph data, we need to pretrain a model at both graph and node-level to encode more information[Hu et al., 2019]. Lower half of table 1 summarizes the results of combing our PHD with node-level strategies. It shows that the combinations significantly outperform the strategies of only PHD or node-level strategy. Furthermore, the PHD combining with AttrMasking gives a better predictive performance than that with ContextPred, achieving state-of-the-art performance. These results reveal that combining PHD with node-level strategy has the potential of pre-training a GNN model well on graph data, especially on molecular representation learning.

Whether PHD Can Generalize Well to Different GNNs?

We conducted experiments with other popular GNN architectures: GCN, GAT, and GraphSAGE. Table 3 shows that PHD pre-training yields superior performance than random initialization over different GNN architectures on most datasets, and the performance could be further enhanced when cooperated with node-level strategy. Thus, PHD is architecture-free that could empower different GNN architectures to learn an expressive graph representation. It provides a favorable initialization for model and improves the performance of downstream tasks. Although our PHD strategy acts universally well to enhance many GNN-based models, different GNN architectures have different gains after pre-trained. Our experiments indicate that GraphSAGE and GIN achieve larger improvement than GCN and GAT. It remains an open challenge in research to explore the relationship between the pretraining strategies and the GNN architectures.

5 Experiments on Unsupervised Learning

Besides transfer learning, we then evaluated PHD in the unsupervised representation learning, where unsupervised methods gengerate graph embeddings that are fed into a linear SVM classifier. We conduct experiments on five small-scale benchmark datasets: MUTAG, PTC-MR, REDDIT-BINARY, IMDB-BINARY, and IMDB-MULTI, to compare PHD with previous state-of-the-art approaches including graph kernel methods-GLK [Shervashidze et al., 2009], WL [Shervashidze et al., 2011], DGK [Yanardag, 2015], and some other unsupervised graph learning methods-sub2vec [Adhikari et al., 2018], graph2vec [Narayanan et al., 2017], InfoGraph [Sun et al., 2019], GraphCL [You et al., 2020], and Contrastive Multi-View (CMV) [Hassani and Khasahmadi, 2020].

We adopt the same procedure of previous works [Sun et al., 2019; You et al., 2020; Hassani and Khasahmadi, 2020] to make a fair comparison, and used 10-fold cross validation accuracy to report the classification performance. Specifically, we first pre-trained GIN model implemented by InfoGraph. The embedding dimension is set to 512. The graph representation learned by the GIN model was fed into a linear SVM to obtain the final prediction. The C parameter of SVM was selected from {10-3 , 10-2 , · · · , 102 , 103 }.

Table 4 shows that PHD still achieves state-of-the-art performance on MUTAG and PTC-MR and comparable performance on the rest datasets. The great improvement on MUTAG and PTC-MR indicates that PHD is good at handling the small attributed graphs.

6 Explainable Representation Visualization

To intuitively prove our PHD is a graph-level strategy, we visualized the representation extracted by the pre-trained models. The primary problem to be solved is to define what can represent global knowledge in a graph. Fortunately, the scaffold concept in chemistry is proposed to represent the core structures of a molecule, which reveals the graph-level intrinsic patterns to some extent [Bemis and Murcko, 1996]. Here, we employed UMAP [McInnes et al., 2018] for molecular graph representation visualization coloring with the corresponding scaffold. Specifically, we chose 9 most common scaffolds from ZINC dataset, and randomly sampled 1000

molecules from each selected scaffold. Finally, we have 9000 molecules labeled with nine different scaffolds. The molecular representations are obtained by averaging the node embeddings extracted by the last layer of a GIN model, we compared the UMAP visualization of representation results including (a) no pre-trained, (b) PHD, (c) AttrMasking and (d) combining AttrMasking with PHD.

From Figure 4, we observe that the no pre-trained GNN model (a) shows no obvious cluster and the molecules overlap in a mess without meaningful patterns. In contrast, the GNN model pre-trained with our PHD strategy (b) exhibits a discernible clustering. Moreover, although the model pre-trained with node-level AttrMasking (c) scatters the molecules with slight cluster, it still presents notable overlap. Alternatively, with a beneficial combination of PHD and node-level strategy, the representations extracted from the pre-trained model (d) exhibit a more favorable and distinctive clustering corresponding to the nine scaffolds. These results indicate that our PHD strategy prompts the pre-training model to better capture data's globally inherent characteristics, which provides high-quality representations for the downstream graph-level tasks.

7 Conclusions

In this work, we present a self-supervised strategy named Pairwise Half-graph Discrimination (PHD), an effective and simple strategy that explicitly pre-trains the expressive GNN at graph level. Extensive experiments on multiple downstream benchmarks show that the PHD achieves superior performance than state-of-the-art self-supervised strategies on transfer learning and unsupervised representation learning. Moreover, we observe that the pre-trained GNN model with PHD strategy can capture the global graph-level knowledge like the molecular scaffold. In the future, we plan to use PHD for pre-training more expressive GNN models on larger datasets and evaluate it on more downstream tasks.