Graph Adversarial Self-Supervised Learning
Year: 2022

Abstract:
This paper studies a long-standing problem of learning the representations of a whole graph without human supervision. The recent self-supervised learning methods train models to be invariant to the transformations (views) of the inputs. However, designing these views requires the experience of human experts. Inspired by adversarial training, we propose an adversarial self-supervised learning (GASSL) framework for learning unsupervised representations of graph data without any handcrafted views. GASSL automatically generates challenging views by adding perturbations to the input and are adversarially trained with respect to the encoder. Our method optimizes the min-max problem and utilizes a gradient accumulation strategy to accelerate the training process. Experimental on ten graph classification datasets show that the proposed approach is superior to state-of-the-art self-supervised learning baselines, which are competitive with supervised models.

heading: 1 Introduction
text: Learning effective representations of graph-structured data plays an essential role in a variety of real-world applications, including social, biological, molecules, and financial networks [1]. Recently, graph neural networks (GNNs) have emerged as powerful architectures for learning and analyzing graph representations [2, 3, 4, 5, 6]. GNNs typically learn graph representations in a supervised or semi-supervised setting. In practice, obtaining a large number of labels is often difficult or even impossible, especially in specific areas that are very costly, such as in biochemistry. The labeled graphs may be limited, while unlabeled graphs are easy to collect. Self-supervised learning utilizing unlabeled data has made significant progress in computer vision [7, 8, 9, 10, 11, 12, 13] and shows great potential in exploring unlabeled data to enhance graph deep learning [14, 15, 16, 17, 18, 19, 20].
Despite their success, existing self-supervised learning methods rely heavily on handcrafted view, where the view here refers to human-defined data transformations to preserve the invariance of their intrinsic properties. In recent years, researchers have designed views of graphs from various levels, including nodes dropping, edge perturbation, attribute masking, subgraph [15], and graph diffusion
∗Corresponding authors.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
[14]. However, the handcrafted views require expert knowledge and trial and error but also do not yield consistent performance gains across multiple tasks [15]. Therefore, how to automatically search for augmentations for graph data remains an open problem.
GNNs are vulnerable to adversarial attacks, as are deep neural networks. Adversarial attacks usually exploit the gradient information to generate imperceptibly small perturbations that alter the model’s output. Adding these adversarial samples to the training set, i.e., adversarial training, can improve the neural network to generalize to out-of-distribution samples [21, 22, 23]. Adversarial training usually leads to a trade-off between robustness and generalization. There has been much research on adversarial training for security purposes [24], in particular, it is still unclear how to combine adversarial training in self-supervised learning of GNNs to improve the classification accuracy.
In this paper, we are motivated to address the drawbacks mentioned above and propose a selfsupervised learning framework to train a graph neural network without any class labels. We refer to this novel adversarial self-supervised learning approach as Graph Adversarial Self-Supervised Learning (GASSL). GASSL directly maximizes the similarity of a graph and its perturbed adversarial graph, relying on neither negative pairs nor handcrafted augmented views. In the training phase, we use the gradient accumulation strategy [25, 21] to accelerate the model training. We verify the effectiveness of GASSL on 10 datasets for the graph classification task including the TU datasets [26] and the Open Graph Benchmark (OGB) [27]. We conduct extensive experiments across graph datasets by applying classical GNN models (GCN [4] and GIN[5]) as encoders. Our approach automatically generates challenging views to yield performance gains on multiple tasks compared to handcrafted views. The results show that our method outperforms state-of-the-art graph self-supervised learning and is close to the performance of the supervised GNNs.
Our contribution could be summarized as: (1) We propose a self-supervised learning method GASSL for graph representation learning without human supervision. (2) We use adversarial training to automatically generate challenging views for self-supervised learning in place of handcrafted views, which yield performance gains on multiple datasets. (3) We show that GASSL consistently outperforms state-of-the-art self-supervised models with a significant margin in graph classification tasks. When compared to supervised baselines, GASSL performs on par with or superior to the strong baselines.

heading: 2 Related work
text: Graph neural network (GNN) GNN is built on graph structures to learn representation vector Hv for each node v ∈ V , which are formalized as the following function:
H(k+1)v = COMBINE (k) ( H(k)v ,AGGREGATE (k) ({ H(k)u ,∀u ∈ N (v) })) , (1)
where H(k)v is the embedding of node v at the k-th layer, N (v) denotes a neighbor set of node v, and H(0)v = Xv. COMBINE and AGGREGATE are functions parameterized by neural networks. After K rounds of message passing, we obtain the final-layer node representations. To obtain the representation of the entire graph hG ∈ Rd, we need the permutation-invariant READOUT function as follows: hG = READOUT ({Hv | v ∈ V}) . Various GNNs have been proposed [4, 28, 5] with various pooling [29, 30, 31], achieving state-of-the-art performance in graph tasks.
Adversarial robustness For adversarial training, more attention is paid to improving model robustness and less on improving generalization performance. For image classification tasks, combining a contrast learning framework with perturbation of the input samples is effective. CLAE [32] employs the Fast Gradient Sign Method (FSGM), and RoCL [33] adopts the Projected Gradient Descent (PGD) method to improve the generalization performance of the model. Concurrent to our work, Tamkin et al. [34] proposed a model-agnostic network (ViewMaker) that perturbs the input by adding an `p constraint to produce useful views and has successful applications on image, speech, and time-series data. Kong et al. [24] proposed to perturb the features of the input nodes of GNN for better generalization performance and utilized a gradient accumulation strategy to accelerate adversarial training in a supervised learning setting. Out of positive view, Hu et al. [35] proposed to directly learn a set of negative adversaries playing against the self-trained representation.
Graph self-supervised learning Self-supervised learning has recently made new advances in graph representation learning, in which contrast learning [36, 17, 15, 14, 37, 38, 39, 40, 41] has
achieved the state-of-the-art performance. Infograph [17] maximizes 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 shared across different scales of substructures. GraphCL [15] designed four types of graph augmentations to incorporate various priors, including node dropping, edge perturbation, attribute masking, and subgraph. MVGRL [14] utilized graph diffusion for graph augmentation and found no performance gain for more than two views or multi-scales of encoding. GCC [16] performs a random walk with a restart for each node to sample subgraph as augmentation. GRACE [40] adopt two augmentations, including removing edges and node feature masking. For a thorough review, we refer the reader to the recent survey [42]. However, one limitation shared by all these successful approaches is the handcrafted view, which is the primary goal of our GASSL – how to learn a view automatically without resorting to handcrafting or expert domain knowledge.

heading: 3 Methodology
text: We now show how to learn the representation of a graph without handcrafted views with domain expert knowledge. Before that, we will briefly introduce adversarial training in supervised learning.
A graph can be represented as G = (V, E), where V is the set of |V| = n nodes, the adjacency matrix A ∈ {0, 1}n×n, along with the c dimensional node attribute X ∈ Rn×c. Our goal is to learn from multiple graphs in a dataset and predict the property of a single graph G. The learned d dimensional distributed representation hG ∈ Rd is applied for downstream tasks (e.g. graph classification task).
Adversarial robustness We start with the definition of adversarial attacks under supervised settings. Given a dataset D = (X,Y ), let x ∈ X and y ∈ Y denote a training sample and the corresponding label, respectively. Given a supervised learning model fθ : X → Y with parameters θ. Traditional adversarial attacks maximize the loss within a certain radius from the sample as follows:
xi+1 = ΠB(x, ) ( xi + αsign ( ∇xiLCE ( θ, xi, y ))) (2)
where B(x, ) is the `∞ norm-ball around x with radius , and Π is the projection function for norm-ball, α is the step size, i is the attack iterations, sign(·) returns the sign of the vector, LCE is the cross-entropy loss for supervised training. The straightforward way to defend against adversarial attacks is to minimize the loss of adversarial samples. Authors [43] proposed to seek to find optimal parameters θ∗ to minimize the maximum risk for any δ within a norm ball as follows:
min θ
E(x,y)∼D [
max δ∈B(x, )
LCE(θ, x+ δ, y) ]
(3)
where δ is the perturbation of the adversarial example. The conventional adversarial attacks [43, 44] require to have a class label y ∈ Y , which is not applicable to unlabeled data.

heading: 3.1 Self-supervised learning on graphs
text: Self-supervised learning typically design pretext tasks to bring different views of the same instance (positive view) closer and push views of different samples (negative view) farther apart. The simple and performant BYOL [9] does not need to maintain negative views explicitly and depends only on positive views. Inspired by BYOL, we propose GASSL framework (Figure 3.1) to learn graph representation. GASSL comprises the two networks: the teacher and student networks. The two networks shared the same architecture with different parameters. In detail, the teacher network is defined by a set of weights θ, while the student network using a different set of weights ξ, which are an exponential moving average of parameters θ. Given a target decay rate β ∈ [0, 1], after each training step, we perform the following update, ξ ← βξ + (1 − β)θ. Note that the predictor qθ is only applied to the teacher network to avoid collapse, leading to an asymmetric architecture.
Encoders. In order to learn the graph representation z, we used GNN (defined in (2)) following with a two-layer multi-layer perceptron (MLP) as an encoder f(·). Our framework allows various choices of the network architecture without any constraints. We opt for simplicity and adopt the commonly used GCN [4] and GIN [5].
Similarity loss Our method relies on the positive view of the input graph. The traditional way to produce positive view need to be designed manually, such as node dropping, edge perturbation, subgraph. We will introduce to learn a challenging positive view automatically in the next subsection. Here suppose we have obtained the positive view, denoted as G′. We feed G′ and G to the teacher network and the student network, and obtained the output representations qθ(z′θ) and zξ , respectively. We then `2-normalized both qθ(z′θ) and zξ to q̄θ(z ′ θ) = qθ(z ′ θ)/||qθ(z′θ)||2 and z̄ξ = zξ/||zξ||2. We define the mean squared error as follows,
Lθ,ξ = ‖q̄θ(z′θ)− z̄ξ‖22 = 2− 2 · 〈qθ(z′θ), zξ〉
‖qθ(z′θ)‖2 · ‖zξ‖2 (4)
We symmetrize the loss Lθ,ξ by separately feeding G and G′ to student network and teacher network to compute L̂θ,ξ. At each training step, we optimize the loss as follows,
LGASSLθ,ξ = Lθ,ξ + L̂θ,ξ. (5)

heading: 3.2 Graph adversarial self-supervised learning
text: To apply adversarial training to self-supervised learning, we optimize the self-supervised loss LGASSL (Eq 5) to replace the supervised learning cross-entropy loss (Eq 3), allowing adversarial training to produce views without labels.
For self-supervised learning, the generated perturbations should be challenging and faithful [34]. The generated views should be complex and robust enough for the encoder to produce a useful representation. We generate perturbations by adversarial training to increase the loss between two networks. The perturbation should not make the encoder task impossible. We accomplish this by constraint the radius of perturbation. We can add perturbations directly to the input node features or the output of the hidden layer of the GNN encoder.
Algorithm 1 Graph Adversarial Self-Supervised Learning (GASSL) Input: Graph G = (V, E); input feature matrixX; learning rate τ ; ascent steps T ; ascent step size α; perturbation bound , decay rate β, LGASSL(·) as objective function. Initialize θ for epoch = 1 to dNep/T e do δ0 ← U(− , ) g0 ← 0 for t = 1 to T do gt ← gt−1 + 1T∇θL
GASSL(G;H(1) + δt−1) #Accumulate gradient of parameters θ gδ ← ∇δLGASSL(G;H(1) + δt−1) #Update the perturbation δ via gradient ascend δt ← δt−1 + αgδ/‖gδ‖F
end for θ ← θ − τgT ξ ← βξ + (1− β)θ
end for
Perturbation on initial node features It is common practice to add noise to the node features X, which we denote the perturbed features as Xadv = X + δ. The adversarial learning objective following the min-max formulation,
min θ
EG∼G [
max ‖δ‖F≤
LGASSL(G;X + δ) ]
(6)
Perturbation on hidden layers For GNNs, the features of nodes are aggregated by the neighborhoods. Perturbation on the hidden layer output to affect the nodes with their neighborhoods would produce a more challenging view. We denote the output of first hidden layer as H(1), the perturbed output is H(1) + δ. We optimize the following min-max formulation,
min θ
EG∼G [
max ‖δ‖F≤
LGASSL(G;H(1) + δ) ]
(7)
The problem (6) and problem (7) are similar, we analyze problem 7 in the following. For problem (7), the outer ‘min’ of the is non-convex and the inner ‘max’ is non-concave. This saddle-point problem could be reliably solved with stochastic gradient descent (SGD) for outer minimization and projected gradient descent (PGD) for inner maximization [43]. In this work, we take unbounded adversarial attacks instead. The parameter δ is updated after each step,
δt+1 = δt + αg(δt)/‖g(δt)‖F , (8)
where g(δt) = ∇δLGASSL(G;H(1) + δt) is the gradient of the loss with respect to δ.

heading: 3.3 Acceleration training with gradient accumulation
text: The computation of δ is inefficient since T -step updating takes T forward-backward passes, and the SGD takes only one pass through the neural network. We then leverage the ‘free’ strategy [25, 21] for efficient adversarial training. The core idea of ‘free’ strategy is to accumulate gradients of∇θLGASSL in each iteration of inner loop and update the model parameter θ with the accumulated gradients. During the training procedure, suppose we run inner loop T times, each time computing gradient for δt and θt−1. By taking a decent step along the averaged gradients atH(1) + δ0, . . . ,H(1) + δT−1, we approximately optimize the following objective:
min θ
EG∼G
[ 1
T T−1∑ t=0 max ‖δt‖F≤ LGASSL ( G;H(1) + δt )] (9)
The overall procedure is shown in Algorithm 1.

heading: 4 Experiment

heading: 4.1 Datasets
text: We selected 10 widely used graph classification datasets from TU datasets [26] and Open Graph Benchmark (OGB) [27]. For TU datasets, we select three bioinformatics datasets (MUTAG [45], PTC-MR [46, 45], NCI1 [47]) and three social network datasets (COLLAB [48], IMDB-BINARY [48], IMDB-MULTI [48]). Notably, since the nodes have no features for the social network datasets, we use the one-hot encodings of node degrees as features. We use classification accuracy as an evaluation metric. For OGB datasets, we selected four of the molecular datasets, including HIV, Tox21, ToxCast, and BBBP. We use the ROC-AUC for an evaluation metric. Statistics are reported in Table 1, and more details are described in the Appendix.

heading: 4.2 Baselines
text: We select three families of baselines, including graph kernel methods, supervised GNN, unsupervised (self-supervised) methods. The graph kernel methods including shortest path kernel (SP) [49], Graphlet kernel (GK) [50], Weisfeiler-Lehman sub-tree kernel (WL) [51], deep graph kernels (DGK) [48], and multi-scale Laplacian kernel (MLG) [52] reported in [17]. The supervised GNN-based models including GraphSAGE [3], GCN[4], GAT [28], GIN-0 and GIN- reported in [5]. In addition, GNN incorporates newly developed pooling methods to further improve performance on graph classification tasks, and we have selected StructPool [29], MinCutPool [30], and Grpah Multiset Transformer (GMT) [31]. The unsupervised methods including random walk [53], node2vec [54], sub2vec [55], and graph2vec [56]. The state-of-the-art self-supervised graph representation learning including InfoGraph [17], MVGRL [14], GraphCL [15], and GCC [16].

heading: 4.3 Evaluation protocol
text: For all experiments on the TU dataset, we follow [17, 31] and report the mean 10-fold cross-validation accuracy with standard deviation after 5 runs followed by a linear SVM. The linear classifier is trained using cross-validation on training folds of data, and the best mean classification accuracy is reported. For OGB datasets, we evaluate the performance with their original feature extraction and following the original training/validation/test dataset splits [27]. We train a linear classifier on the top of a frozen encoder on existing self-supervised learning models [7].
We train the model using Adam optimizer with an initial learning rate of 10−4, and we choose the number of GCN and GIN layers ∈ {2, 3, 4, 5}, number of epochs ∈ {20, 40, 100, 200}, batch size ∈ {32, 64, 128, 256, 512, 1024}, and the SVM parameter C ∈ {10−3, 10−2, . . . , 102, 103}. The step size α is set to 8× 10−3, the perturbation bound is set to 8× 10−3, the embedding dimension is set to 128 (expect HIV set to 512). We also use early stopping with the patience of 20, where we stop training if there is no further improvement on the validation loss during 20 epochs. We conduct all the experiments on an Nvidia TITAN Xp.

heading: 4.4 The role of adversarial views
text: Architecture vs. views To illustrate that views generated by adversarial training contribute to graph representation learning, we compare with GraphCL [15] that uses handcrafted views. Our proposed GASSL approach differs from the GraphCL in both the self-supervised learning approach and the view generation. Therefore, we construct a new baseline by combining the BYOL architecture with GraphCL’s view, named GraphCL-BYOL. We follow the setting of GraphCL and use GIN as the encoder for all comparison methods. From the Table 2, we observe that replacing the backbone of GraphCL from SimCLR to BYOL yields a consistent performance improvement. We choose the
best result as a baseline and compare it with our approach. Our GASSL obtained a boost ranging from 0.1% ∼ 4.7% using adversarial training. It is worth mentioning that compared to GraphCL, our approach improves 6.7% on COLLAB, which backbone contributes 2.0% and view contributes 4.7%. The improvement in classification performance indicates the effectiveness of adversarial training.
Effect of step size α and perturbation bound Step size α and perturbation bound are critical factors of adversarial training. We evaluate the effect of α and on the classification accuracy of the BBBP dataset. We separately vary α and in the range {0.00025, 0.0005, . . . , 64, 128}, while fix the other as 0.008. From Figure 2, the algorithm achieves the best classification performance when α ≤ 0.008. As the step size increases, the classification performance gradually decreases. Observing the perturbation bound , we find that the algorithm performance changes similarly. As mentioned in Section 3.2, the perturbations should be challenging and faithful. An overly large step size α or perturbation bound leads to perturbed samples that deviate too much from the input graph, and the encoder can hardly learn a useful representation. In the following experiments, we set α = = 0.008.

heading: 4.5 Comparison with state-of-the-art

heading: 4.5.1 Results on TU datasets
text: The results shown in Table 3 suggest that GASSL achieves state-of-the-art results with respect to unsupervised models. For example, on MUTAG it achieves 90.9% accuracy, a 1.9% relative improvement over the previous state-of-the-art. For kernel methods, our approach achieves better performance on all datasets. When compared to supervised baselines individually, our model outperforms GraphSAGE in all datasets and outperforms GCN in 4 out of 6 datasets, e.g., a 4.3% relative improvement on GCN for the MUTAG dataset.
Our approach outperforms the state-of-the-art contrastive learning approaches. For example, compared to MVGRL, GASSL has a relative improvement of 2.55% on average across all datasets. GASSL outperforms GraphCL and GCC with a relative improvement of 4.08% and 5.31%, respectively.

heading: SP ([49]) 85.2 ± 2.4 58.2 ± 2.4 55.6 ± 0.2 38.0 ± 0.3 – –

heading: 4.5.2 Results on OGB datasets
text: We evaluate our method GASSL on 4 OGB datasets. From Table 4, we observed that perturbing at the first hidden layer (GASSL-H) yields a slight performance gain compared to perturbing at the input node features (GASSL-X). Our method outperforms GCN and GIN on all datasets, demonstrating our method’s potential to outperform supervised learning on larger datasets. Compared with the stronger baselines like structurePool and MinCutPool, which exploit the graph structure information. For StructPool, GASSL has a 3% and 3.5% gain for the HIV and BBBP datasets, respectively. GASSL outperforms MinCutPool by 3.2% and 4.5% for the HIV and BBBP datasets, respectively. The performance is similar on the Tox21 and ToxCast datasets. Our GASSL performs inferior to GMT on Tox21 and ToxCast and superior to GMT on HIV and BBBP. The above results show that our GASSL method can learn a good representation of the graph and outperforms even the state-of-the-art supervised learning methods.

heading: 4.6 Ablation studies
text: Effect of batch size We analyze the sensitivity of the algorithm to the batch size on four OGB datasets. We selected batch size from {32, 64, 128, 256, 512, 1024}. From the Table 5, we observe
that GASSL performs stably under different batch sizes. The performance gradually decreases as the batch size increases. In particular, GASSL performs well for a batch size of 128. The benefit is that GASSL can be trained with fewer resources. Moreover, the perturbation on the first hidden layer output consistently leads to better test accuracy than perturbation on the input node features.
Effect of the number of GNN layers We evaluate the effect of the number of layers on the classification accuracy using ROC-AUC performance on the OGB dataset, using GCN as the encoder, and selecting the number of layers from {2, 3, 4, 5} respectively. From Table 6, we can observe that the performance of GASSL gradually decreases as the number of layers increases, while the best performance is obtained when using a 2-layer encoder.
Effect of embedding dimension We test the effect of encoding dimensions on classification accuracy on the OGB datasets. We choose the best encoding dimension among {128, 256, 512, 1024}. From Table 6 we observe that for HIV, the test accuracy increases as the encoding dimension increases. We set it to 512 for HIV and 128 for the rest, considering the computational efficiency.
Effect of ascent steps We explored the impact of ascent steps T on the performance of graph classification accuracy. We train the model in the same setting and vary T ∈ {1, 2, 3}. From Table 7, we observed that our method achieves a stable performance on test accuracy. When T = 3, for the IMDB-M dataset, there is an improvement in test accuracy along with a speedup of nearly 1.5 times. The results for other datasets are similar and are detailed in the Appendix.

heading: 5 Conclusion and Future work
text: In this paper, we explore a novel problem of how to learn graph representations without human supervision. We propose an adversarial self-supervised learning framework (GASSL) that automatically generates views using adversarial training. Our approach adversarially generates challenging views to train a self-supervised model. We obtain performance gain by generating views through adversarial training compared to handcrafted views. We use a gradient accumulation training method to improve the training efficiency. We conduct extensive experiments on ten datasets. The results show that our method outperforms state-of-the-art graph self-supervised learning and is close to the performance of the supervised GNNs.
For potential negative societal impact, the graph representations can be extended to many fields, such as financial networks, molecular biology. The use of transformations generated by adversarial perturbations does not certainly produce meaningful views. Expert knowledge is also required for domain-specific applications. The limitation of our approach falls in that it exploits the uniformly norm-bounded perturbation and ignores the distribution of the data. Besides, taking full advantage of the existing expert knowledge is the potential to improve performance.
In the future, we will explore the following directions: (1) Explore how to effectively combine adversarial training with existing handcrafted views to enhance performance further. (2) Theoretically analyze the use of adversarial training to improve the performance of downstream tasks. (3) Explore non-uniform norm-bounded perturbations on the graph to generate adversarial samples.
Acknowledgments and Disclosure of Funding
This work was partially supported by the National Natural Science Foundation of China (No. 91948303-1, No. 61803375, No. 12002380, No. 62106278, No. 62101575, No. 61906210, No. 91648204) and the National University of Defense Technology Foundation (No. ZK20-09, No. ZK20-52). We would like to thank the anonymous reviewers for their valuable suggestions.

Review summaries:
This paper presents a self-supervised learning method GASSL for graph representation learning. The authors have designed 2 key points:  a) Utilizing BYOL framework to learn graph representation; b) Using adversarial training to automatically generate challenging views for self-supervised learning. The idea seems to be simple but effective. Sufficient experimental analyses are conducted.

The paper investigates the unsupervised representation of graph data and proposes an adversarial self-supervised learning (GASSL) framework. The paper adopts the self-supervised framework in reference [12] for graph embedding representation, and apply adversarial learning to improve the robustness of the model, following the framework in [26]. A number of experimental results are given to validate the performance of the proposed model. The contribution of the paper is incremental.