CuCo: Graph Representation with Curriculum Contrastive Learning

1 Introduction

Graph-structured data, such as social networks, proteinprotein interactions and financial networks, are ubiquitous in real-world scenes. Recently, it is well recognized that an adequate representation of graphs is vital to the learning performance of a statistical or machine learning model, and therefore, much work has been done on learning the lowdimensional [Cai et al., 2018]. To date, graph representation learning has achieved remarkable success in many domains such as social network analysis and recommendation system [Fouss et al., 2007].

Most of the current graph representation learning methods aim at learning node-level representation in a single graph.

∗Corresponding author

However, in practice, a variety of applications need to extract the representation of entire graphs such as predicting molecule properties in drug and material discovery [Gilmer et al., 2017], and forecasting protein function in biological networks [Jiang et al., 2017]. Therefore, graph-level representation learning has also attracted a large amount of attention in recent years. These methods design a message passing algorithm and aggregation procedure to get the node embedding, and then use pooling mechanisms [Ying et al., 2018] to obtain a representation of the entire graph in a supervised way.

Nevertheless, in many real applications, labeled data are very limited and expensive to obtain. For example, in the chemical domain, labels are typically produced with a costly density functional theory calculation. As a consequence, it is becoming increasingly important to learn the representations of entire graphs in an unsupervised or self-supervised fashion. Recently, motivated by profound success in natural language processing [Devlin et al., 2018] and computer vision [He et al., 2020], self-supervised contrastive leaning based graphlevel representation learning attracts considerable attention. To be specific, the basic idea of these methods is to enforce the embeddings of views augmented from the same instance (forming the positive pair) close to each other, while those from different instances (negatives) apart using a contrastive loss, leading to powerful and transferable representations.

When applying contrastive learning to graphs, two fundamental problems need to be carefully considered: one is how to augment positive pairs on graphs and the other is how to select and train negative samples effectively. These two factors both essentially determine the success of contrastive learning on graphs. Most of current works focus on the former issue and design different graph augmentation strategies, such as substructure augmentation [Veliˇckovi´c et al., 2018; Sun et al., 2019; Weihua et al., 2020a; You et al., 2020a]. However, little efforts have been made towards an effective negative sample selection and training strategies, while in fact treating negative samples effectively is rather crucial on the generalization performance of the contrastive learning [Robinson et al., 2020; Kalantidis et al., 2020]. This requirement is quite challenging because in contrastive leaning setting the label information is unknown, making it infeasible to adopt existing negative sampling strategies that use label information. At present, most of contrastive methods select negative samples randomly in the training process. Nevertheless, different negative samples play different roles and have different influence. Specifically, for a specific sample, the difficulties of its negative samples is different, and these negative samples play distinct roles in different training periods. For instance, harder negative samples play a major role in the later stage of training [Kalantidis et al., 2020]. Therefore, we need to consider the order of sampling negatives based on their difficulty in the training process, especially in the case of no label information, the problem becomes more challenging.

In this paper, we attempt to tackle the above challenging problem by proposing a Curriculum Contrastive learning framework for graph-level representation, called CuCo. In particular, we introduce four types of graph augmentations for constructing positive sample pairs firstly and use a scoring function to measure the difficulty of negative samples in the training dataset. According to the learning process of human beings, we should start with easy samples when learning a new model and then learn difficult samples gradually [Bengio et al., 2009], so we sort the negative samples from easy to hard. In addition, we design a pacing function to schedule how the negative samples are introduced to the training procedure. At last, we utilize a popular contrastive object function to optimize our model. In this way, compared with stateof-the-art self-supervised graph-level representation learning methods, our method not only achieves overall better performance, but also reduces training time.

We summarize the contributions as follows:

• We make the first attempt towards studying the impact of negative samples on learning graph-level representation, which is largely ignored by previous works but rather practical and important for a good self-supervised graphlevel representation learning.
• We propose a novel curriculum contrastive learning based graph representation learning model. Our model effectively combines curriculum learning and contrastive learning, which is able to automatically select and train negative samples in a human-learning manner.
• We conduct comprehensive experiments, which show that the proposed method improves downstream convergence speed and performance on fifteen datasets.

2 RelatedWork

Graph Neural Networks. In recent years, Graph Neural Networks (GNNs) [Kipf and Welling, 2016; Xu et al., 2018] have emerged as a promising approach for analyzing graphstructured data. They follow an iterative neighborhood aggregation (or message passing) scheme, where each node aggregates feature vectors of its neighbors to compute its new feature vector [Gilmer et al., 2017]. After k iterations of aggregation, a node is represented by its transformed feature vector, which captures the structural information within the node's k-hop neighborhood. The representation of an entire graph can then be obtained through pooling, for example, by meaning the representation vectors of all nodes in the graph. Unlike these methods which are mainly trained in a supervised fashion, our approach aims for unsupervised/self-supervised learning for GNNs.

Contrastive Learning. Contrastive learning is one of the state-of-the-art self-supervised representation learning algorithms that achieves great success for natural language processing [Devlin et al., 2018] and visual representation learning [He et al., 2020]. Contrastive learning force the embeddings of views generated from the same data instance to be closer to each other, while those from different instances apart. In this work, we adopt the noise-contrastive estimation from [Oord et al., 2018], as discussed in Section 3.

CurriculumLearning. Curriculum learning [Bengio et al., 2009] is a training strategy that trains a machine learning model from easier samples to harder samples, which imitates the meaningful learning order in human curricula. Previous empirical studies have shown that curriculum learning strategy can improve the generalization capacity and convergence speed of various models in a wide range of scenarios such as computer vision [Pentina et al., 2015] and natural language processing [Guo et al., 2018], etc. These methods are mainly developed for images or words but not for graph-structured data.

3 Our ProposedModel: CuCo

The main goal of this paper is to train a GNN encoder with a curriculum learning based negative sampling strategy. As shown in Figure 1, given a graph G, we employ the graph augmentation techniques to obtain the positive pairs ˆ Gi, ˆ Gj at first. Here we use every other graph except G in the training set as negative samples {Gk}Kk=1 , called memory bank. Then we utilize graph neural networks to learn their representations zi, zj , {zk}Kk=1 respectively. Thereafter we use a scoring function S(·) to measure the difficulty of negative samples and sort the negative samples from easy to hard. Next a pacing function g(·) is to schedule how the negative samples are introduced to the training procedure. Finally, the parameters of GNN are optimized with gradient descent using the contrastive learner.

Problem Definition. Given an undirected graph G = {V, E} where V = {vi}|V| i=1 denotes a set of |V| nodes and E = [eij] ∈ R|V|×|V| denotes the adjacency matrix, with the node feature matrix X ∈ R|V|×N where xn = X[n, :]T is the N-dimensional attribute vector of the node vn ∈ V, for self-supervised graph representation learning, a set of unlabeled graphs G = {G1, G2, · · · , GM} are given, and we aim to learn a d-dimensional vector zGi ∈ Rd for each graph Gi ∈ G under the guidance of the data itself.

3.1 Graph Augmentations

We know that, without any data augmentation, contrastive learning is not helpful and often worse compared with training from scratch. Data augmentation aims at creating novel and realistically rational data through applying certain transformation without affecting the semantics label. We focus on graph-level augmentations. Specifically, given a graph G ∈ {Gm : m ∈ M} in the dataset of M graphs, we formulate the augmented graph ˆ G satisfying: ˆ G ∼ T ( ˆ G|G), where T (·|G) is the augmentation distribution conditioned on the original graph, which is pre-defined, representing the human prior for data distribution. Usually, there are four basic data augmentation strategies to construct positive pairs of graphs [You et al., 2020a] : (1) node dropping that randomly discards certain portion of nodes along with their connections; (2) edge perturbation that perturbs the connectivities in G through randomly adding or dropping certain ratio of edges; (3) attribute masking that prompts models to recover masked node attributes using their context information, i.e., the remaining attributes; and (4) subgraph that samples a subgraph from G using random walk.

The given graph G undergoes graph data augmentations to obtain two correlated views ˆ Gi, ˆ Gj, as a positive pair, where ˆ Gi, ˆ Gj ∼ T (·|G) independently. Furthermore, although any other graph in the training set can be regarded as a negative pair with G, most of contrastive methods simply select negative samples randomly. However, how to strategically select negative samples matters, we will discuss this in Sec. 3.4. For different domains of graph datasets, we adopt [You et al., 2020a] to strategically select data augmentations. Specifically, for chemical and biochemical molecules, we employ two augmentations strategies as: node dropping and subgraph; for social networks, we use all four data augmentation strategies.

3.2 Graph Encoder

After we obtain the positive augmented graph pairs, i.e., ˆ Gi and ˆ Gj, we need to learn their representations. Although our method allows various choices of the network architecture without any constraint, here we employ graph neural networks (GNNs) as the graph encoder. Next we take ˆ Gi as an example to introduce the GNN based learning process, and this procedure is the same as ˆ Gj. Given an undirected graph ˆ Gi = {Vi, Ei} with the node feature matrix X ∈ R|Vi|×N where xn = X[n, :]T is the N-dimensional attribute vector of the node vn ∈ Vi. Considering a L-layer GNN f (·), the propagation of the lth layer is represented as:

where h(l) n is the embedding of the node vn at the lth layer with h(0) n = xn, N(n) is a set of nodes adjacent to vn, and AGGREGATION(l) (·) and COMBINE(l) (·) are component functions of the GNN layer. After the L-layer propagation, the output embedding f( ˆ Gi) for ˆ Gi is summarized on layer embeddings through the READOUT function. Then a multilayer perceptron (MLP) is adopted for the graph-level downstream task (classification or regression):

3.3 Contrastive Learning withMemory

To enforce maximizing the consistency between positive pairs {zi, zj} compared with negative pairs, we adopt the noise-contrastive estimation loss [Oord et al., 2018]. Specifically, we define a "memory bank" Q which contains K negative sample embeddings {zk}Kk=1 for each positive pair {zi, zj}, then we employ a similarity metric function sim(·, ·) to calculate the similarity of positive pair {zi, zj} and the negative pair {zi, zk}. Based on this, the loss function is as follows:

where τ denotes the temperature parameter. Minimizing Eq.(3) implies that we enforce the positive pair score higher than the negative pairs in the memory bank.

To simplify the calculation, we use dot product as the similarity metric function. The log-likelihood function of Eq.(3) is defined over the probability distribution created by applying a softmax function for each zi. Let pˆ z be the matching probability for the zi and the other samples ˆ z ∈ Z = Q∪ {zj}, then the gradient of the loss with respect to the zi is given by

where

and pzj , pzk are the matching probability of the positive pair ˆ z = zj and negative pair ˆ z = zk respectively.

3.4 Curriculum Setting for Negative Sampling

Obviously, we need negative sampling from our memory bank. In the following, we will introduce a novel negative sampling method by adopting curriculum learning. The main idea is ordering negative samples during training based on their difficulty. Generally speaking, a curriculum is defined by specifying three ingredients [Hacohen and Weinshall, 2019]: the scoring function, the pacing function and the order.

The Scoring Function

Here, in our memory bank, we have K negative embeddings {zk} with different diffuculties. We then define a scoring function, which maps a negative embedding zk to a numerical score S(zk), to measure such difficulty. Usually, higher score corresponds to a more difficult negative embedding. We can set up the scoring function S(zk) as sim(zi, zk) ∈ R to return the measure of a negative embedding's difficulty, since the higher the scoring function value is, the loss for zi also becomes higher according to Eq. (3), meaning that zk is a more difficult negative embedding. Specially, we use two common score functions based on embedding's similarity:

• Cosine Similarity : It uses the cosine value of the angle between two vectors to measure the similarity.

• Dot Product Similarity : In contrast to the cosine similarity, the dot product is proportional to the vector length.

The Pacing Function

After we get the score S(zk) of every single negative embedding zk in the memory bank, we use pacing function to schedule how the negative samples are introduced to the training procedure. The pacing function g(t) specifies the size of the memory bank used at each step t. The memory bank at step t consists of the g(t) lowest scored samples. Negative sample batches are sampled uniformly from this set. We denote the full memory bank size by K and the total number of training steps by T. Here we consider four common function families: logarithmic, linear , quadratic, and root.

• Logarithmic :

• Polynomial :

where λ is a smoothing parameter which controls the pace in the training procedure. λ = 1/2, 1, 2 denote root, linear and quadratic pacing functions, respectively.

The Order

In order to narrow down the specific effects of using scoring function based on ascending difficulty level, we specify an order of either curriculum (ordering examples from the lowest score to the highest score), anti-curriculum (ordering examples from the highest score to the lowest), or random.

3.5 Early StopMechanism

In the later stage of training, with the increasing difficulty of negative samples, the proportion of false negative samples which have the same label with the zi will increase, and false negative samples will hurt the generalization performance of the model [Kalantidis et al., 2020]. To relieve this problem, we design an early stop mechanism. Specially, we define a hyperparameter patience of early stop p. When loss no longer decreases, p value begins to decreased. Once p becomes 0, the training will stop.

Algorithm 1 Training procedure of CuCo

Input: Training set D = {Gj}ND j=1 , the number of training iterations NT , difficulty scoring function S, pacing function g, a GNN model f , patience of early stop p, the augmentation distribution T

Output: The pre-trained GNN fθ

Initialize model parameters θ with an Xavier initialization.

end while

3.6 Model Optimization

The training procedure of CuCo is summarized in Algorithm 1. During the training, using the online-updated graph embeddings, we sort the negative embeddings by their difficulty according to score function S(·), and then sample the negative pairs according to pacing function g(·). In each iteration, the parameters of GNN are optimized with gradient descent using the objective LNCE. If the objective no longer decreases, the patience value p begins to reduce 1 every iteration. Once the patience value p becomes 0 or epoch t achieves the last iteration NT , the training will stop.

4 Experiments

In this section, in order to indicate that our self-supervised model, CuCo, can learn graph representation fast and well, we compare our model with state-of-the-art methods (SOTAs) in the settings of unsupervised and transfer learning on graph classification.

baselines on 6 out of 7 of the datasets. In the other dataset NCI1, CuCo still has very competitive performance.

We also investigate the benefits of convergence speed. We compare CuCo with GraphCL for fairness, since our method and GraphCL employ the same graph augmentations and GNN architecture. Due to our early stop mechanism and ordered learning, as shown in Figure 2, our method leads to faster training: our negative sampling only needs 13 to 14 epochs to reach the better performance than GraphCL in 20 epochs, which reduces time cost by about 40%.

Alternative Pacing Functions

In our empirical setup, we investigate all four pacing functions on five datasets, and the results are shown in Table 3. We find that the linear pacing function has a slight advantage on most datasets and the other pacing functions have comparable performance. For the logarithmic and root which are concave functions, the memory bank we used will contain more diffculty negative samples in a fewer iteration, resulting in the effect of curriculum learning is similar to random sampling. For the quadratic which is a convex function, the number of hard negative samples will rise rapidly in the later stage of training. It leads to a rapid increase in the number of false negative samples, which will be harmful for the model. Therefore, we think that increasing the difficulty of introducing negative samples at a uniform rate have a positive effect on improving the generalization performance.

The Number of Negative Samples

We employ three datasets to study the effect of negative sample size on generalization performance, and the results are shown in Figure 3. We can find that too small or too large number of negative samples are not good in our negative sampling scheme. It is retional that few negative samples cannot provide enough information for contrastive learning, while too many negative samples will inevitably contain more false

4.1 Unsupervised Representation Learning

We evaluate our method in the unsupervised representation learning following [Sun et al., 2019], where CuCo is used to learn graph representations in a fully unsupervised manner, followed by evaluating the graph-level classification utility of these representations. This is performed by directly using these representations to train and test a SVM classifier.

Experiments Setting

We evaluate model performance on seven classical graph classification benchmarks shown in Table 1. Aside from SOTA graph kernel methods that Weisfeiler-Lehman subtree kernel (WL) [Shervashidze et al., 2011] and deep graph kernel (DGK) [Yanardag and Vishwanathan, 2015], we also compare with four state-of-the-art unsupervised graph-level representation learning methods as sub2vec [Adhikari et al., 2018], graph2vec [Narayanan et al., 2017], InfoGraph [Sun et al., 2019] and GraphCL[You et al., 2020a]. For our proposed model, we adopt a three-layer Graph Isomorphism Network (GIN) with 32-dimensional hidden units and a sum pooling readout function for performance comparisons. We use 10fold 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 hyperparameter search according to the original paper.

Performance Analysis

The results of evaluating unsupervised graph level representations using downstream graph classification tasks are presented in Table 2. While two kernel methods perform well on individual datasets, none of them are competitive across all of the datasets. We find that CuCo outperforms all of these negative samples in the later stage of the curriculum, which will hurt the generalization.

The Value of Ordered Learning

Equipped with the ingredients described in the previous sections, we investigate the relative benefits of curriculum negative sampling. To understand whether anti-curriculum, or random learning provides any benefit over ordinary training, we replicate this procedure with three random seeds and five standard benchmark datasets. For each experiment in this sweep, we select the best configuration and stopping time and record the corresponding test accuracy. The results of these runs are shown in Figure 4. Compared with random negative sampling, the curriculum negative sampling has an average improvement of the accuracy by about 2% for five benchmarks. In addition, the anti-curriculum negative sampling is not helpful for the model.

4.2 Transfer Learning

We perform transfer learning on molecular property prediction in chemistry and protein function prediction in biology following [Weihua et al., 2020a], which pre-trains and finetunes the model in different datasets to evaluate the transferability of the pre-training scheme. We fine-tune the pretrained GNN model with a small portion of labels on downstream tasks.

Experiments Setting

We adopt the same train-test and model selection procedure as in [Xu et al., 2018], where we perform 10-fold cross- validation and select the epoch with the best cross-validation performance averaged over the 10 folds. The evaluation metric is ROC-AUC score. For fine-tuning on a downstream task, a linear classifier is appended on the top of pre-trained GNN. All reported results are averaged over five independent runs under the same configuration. In our transfer learning experiments, we evaluate model performance on eight Open Graph Benchmark (OGB) [Weihua et al., 2020b] molecule property prediction datasets. Traditional unsupervised methods have no ability to transfer knowledge to other domain datasets. So we consider six baselines, including non-pretrain (direct supervised learning) and five state-of-the-art GNN self-supervised learning (SSL) methods including EdgePred [Hamilton et al., 2017], InfoGraph [Sun et al., 2019], AttrMasking [Weihua et al., 2020a], ContextPred [Weihua et al., 2020a] and GraphPartition [You et al., 2020b].

Transferability of CuCo

Table 4 reports the performance of proposed CuCo method compared with other works in transfer learning setting. Among all self-supervised learning strategies, our method outperforms all baselines on average performance and achieves the highest results on on six of eight datasets. We gain a 5% performance enhancement against non-pretrain baseline, which well indicates the effectiveness of our proposed CuCo on transfer learning.

5 Conclusion

In this paper, we study the impact of negative samples on learning graph-level representations, and propose a novel curriculum contrastive learning framework for self-supervised graph-level representation called CuCo. We look into different ways of associating difficulty to negative samples using scoring functions and a variety of schedules known as pacing functions for introducing negative samples to the selfsupervised training procedure. We conduct comprehensive experiments, which show that the proposed method improves downstream convergence speed and performance on fifteen datasets.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (No.U20B2045, 61772082, 61702296, 62002029), "The Fundamental Research Funds for the Central Universities 2021RC28".