Automated Data Augmentations for Graph Classification
Authors: Youzhi Luo
Michael Curtis McThrow
Wing Yee Au
Tao Komikado
Kanji Uchino
Koji Maruhashi
Shuiwang Ji
Venue: ICLR 2023 poster (2023)
Keywords: Data Augmentation
Graph Classification
Label-invariance

Abstract: Data augmentations are effective in improving the invariance of learning machines. We argue that the core challenge of data augmentations lies in designing data transformations that preserve labels. This is relatively straightforward for images, but much more challenging for graphs. In this work, we propose GraphAug, a novel automated data augmentation method aiming at computing label-invariant augmentations for graph classification. Instead of using uniform transformations as in existing studies, GraphAug uses an automated augmentation model to avoid compromising critical label-related information of the graph, thereby producing label-invariant augmentations at most times. To ensure label-invariance, we develop a training method based on reinforcement learning to maximize an estimated label-invariance probability. Experiments show that GraphAug outperforms previous graph augmentation methods on various graph classification tasks.

Published as a conference paper at ICLR 2023
AUTOMATED DATA AUGMENTATIONS FOR GRAPH CLASSIFICATION
Youzhi Luo'; Michael McThrow?, Wing Au², Tao Komikado', Kanji Uchino?, Koji Maruhashi', Shuiwang Ji 'Texas A&M University, TX, USA FFujitsu Research of America, INC., CA, USA
Fujjituu Research, Fujitsu Limited, Kanagawa, Japan {yzluo, sji amtamu. edu (mmethrow, WAu, komikado. tao, kanji, maruhashi koijeasfiii.iiiefffffttutuu..
ABSTRACT
Data augmentations are effective improving the invariance of learning ma- chines. We argue that the core challenge of data augmentations lies in designing data transformations that preserve labels. This is relatively straightforward for im- ages, but much more challenging for graphs. In this work, we propose GraphAug, a novel automated data augmentation method aiming at computing label-invariant augmentations for graph classification. Instead of using uniform transformations as in existing studies, GraphAug uses an automated augmentation model to avoid compromising critical label-related information of the graph, thereby producing label-invariant augmentations at most times. To ensure label-ine -ibblliivrriancee we de- velop training method based on reinforcement learning maximize an estimated label-invariance probability. Experiments show that GraphAug outperforms pre- vious graph augmentation methods on various graph classification tasks.
INTRODUCTION
Many real-world objects, such as molecules and social networks, can be naturally represented as graphs. Developing effective classification models for these graph-structured data has been highly desirable but challenging. Recently, advances deep learning have significantly accelerated the progress in this direction. Graph neural networks (GNNs) (Gilmer et al.) (017), class of deep neural network models specifically designed for graphs, have been widely applied to many graph representation learning and classification tasks, such molecular property prediction (Wang al.
20226
Liu et al. 2022 Wang et al. 2022a 2023
Yan et al. 2022).
However, just like deep models images, GNN models easily overfit and fail to achieve satis- factory performance on small datasets. To address this issue, data augmentations can be used to gen- erate more data samples. An important property of desirable data augmentations is label-invariance, which requires that label-related information should not be compromised during the augmentation process. This is relatively easy and straightforward achieve for images (Taylor & Nitschke 2018)), since commonly used image augmentations, such as flipping and rotation, can preserve almost all information of original images. However, ensuring label-invariance much harder for graphs be- cause even minor modification of graph may change its semantics and thus labels. Currently, most commonly used graph augmentations (You et al., (2020) are based on random modification of nodes and edges in the graph, but they do not explicitly consider the importance of label-invariane.
In this work, we propose GraphAug, a novel graph augmentation method that can produce label- invariant augmentations with an automated learning model. GraphAug uses a learnable model to automate augmentation category selection and graph transformations. optimizes the model to maximize estimated label-invariance probability through reinforcement learning. Experimen- tal results show that GraphAug outperforms prior graph augmentation methods on multiple graph classification tasks. The codes of GraphAug are available in DIG (Liu al. 202T) library.
Work was done while the author Fujitsu Research of America, INC.

---

Published as a conference paper at ICLR 2023
2 BACKGROUND AND RELATED WORK
2.1 GRAPH CLASSIFICATION WITH NEURAL NETWORKS
In this work, we study the problem of graph classification. Let G (V, EX) be an undirected graph, where V is the set of nodes and E' is the set of edges. The node feature matrix of the graph G is X E R xd where the i-th row of X denotes the d-dimensional feature vector for the i-th node in G. For graph classification task with k categories, the objective J:C. G + E (1,.... k) that can predict the categorical label of G.
learn classification model
Recently, GNNs (Kipf & Welling 2017
Veličković al. 2018 Xu et al. 2019 Gilmer al. 2017
Gao & Jil (2119) have shown great success in various graph classification problems. Most GNNs use the message passing mechanism to learn graph node embeddings. Formally, the message passing for any node E V at the E-th layer of GNN model can be described as
1 = UPDATE (h AGG (fm)p : EN()))))
(1)
where (v) denotes the set of all nodes connected to the node v in the graph G, h, is the embedding outputted from the é-th layer for v, m/, the message propagated from the node j the node at the &-th layer and is usually function of hş- and hn-!.. The aggregation function AGG(.) maps the single vector, and the function UPDATE(-) updates h to A using this aggregated message vector. Assuming that the GNN model has L layers, the graph representation he computed by a global pooling function READOUT over all node embeddings
messages from all neighboring nodes
as
h = READOUT ((h : v vEV)..
(2)
Afterwards, he is fed into multi-layer perceptron (MLP) model to compute the probability that G belongs to each of the categories f1,....k.
Despite the success of GNNs, major challenge in many graph classification problems is data scarcity. For example, GNNs have been extensively used to predict molecular properties from graph structures of molecules. However, the manual labeling of molecules usually requires expensive wet lab experiments, so the amount of labeled molecule data is usually not large enough for expressive GNNs to achieve satisfactory prediction accuracy. In this work, we address this data scarcity chal- lenge with data augmentations. We focus on designing advanced graph augmentation strategies to generate more data samples by performing transformations on data samples in the dataset.
2.2 DATA AUGMENTATIONS
Data augmentations have been demonstrated to be effective in improving the performance for image and text classification. For images, various image transformation or distortion techniques have been proposed to generate artificial image samples, such as flipping, cropping, color shifting (Krizhevsky) et al. 2012), scaling, rotation, and elastic distortion (Sato et al.] 2015) Simard et al., 2003). And for texts, useful augmentation techniques include synonym replacement, positional swaps (Ratner al.) 2017a), and back translation (Sennrich et al.) 2016). These data augmentation techniques have been widely used to reduce overfitting and improve robustness in training deep neural network models.
In addition to hand-crafted augmentations. automating the selection of augmentations with learnable neural network model has been recent emerging research area. |atner et al.) (2017b) selects and composes multiple image data augmentations using an LSTM (Hochreiter & Schmidhuber] 1997) model, and proposes to make the model avoid producing out-of-distribttion samples through adver- sarial training. Cubuk et al. (2019) proposes AutoAugment, which adopts reinforcement learning based method to search optimal augmentations maximizing the classification accuracy. To speed up training and reduce computational cost, a lot of methods have been proposed to improve AutoAug- ment through either faster searching mechanism (Ho et al. 2019 Lim al. 2019), or advanced
optimization methods (Hataya et al. 2020 Li ct al. 2020 Zhang ct al. 2020).
2.3 DATA AUGMENTATIONS FOR GRAPHS
While image augmentations have been extensively studied, doing augmentations for graphs is much more challenging. Images Fuclidean data formed by pixel values organized in matrices. Thus,
2

---

Published as a conference paper at ICLR 2023
many well studied matrix transformations naturally be used to design image augmentations, such as flipping, scaling, cropping or rotation. They are either strict information lossless transformation, or able to preserve significant information at most times, label-invariance is relatively straight- forward to be satisfied. Differently, graphs are non-Fuclidean data formed with nodes connected by edges in irregular manner. Even minor structural modification of graph destroy important information in it. Hence, it is very hard to design generic -iblr-nnvrriant transformations for graphs.
Currently, designing data augmentations for graph classification (Zhao et al. 2022 Ding al. 2022
Yu et al. 2022) is challenging problem. Some studies (Wang et al. 202 Han et al. 2022 Guo & Mao [022]] Park et al. 2022) propose interpolation- based mixup methods for graph augmentations, and Kong et al. (2022) propose to augment node features through adversarial learning. Nonetheless, most commonly used graph augmentation methods (Hamilton et al., 2017 Wang et al.) 2020 You et al. 2020; Zhou et al.] 2020a; Rong et al., 2020; /hhu et al., (021a) are based on the random modification of graph structures or features, such as randomly dropping nodes, perturbing edges, or masking node features. However, such random transformations are not necessarily label-invariant, because important label-related information may be randomly compromised (see Section 3.2 for detailed analysis and discussion). Hence, in practice, these augmentations do not always improve the performance of graph classification models.
3 THE PROPOSED GRAPHAUG METHOD
While existing graph augmentation methods do not consider the importance of label-invariance, we dive deep into this challenging problem and propose to solve it by automated data augmentations.
Note that though automated data augmentations have been applied to graph contrastive learning (You
jet al. 2021 Yin et al.) 2022, Suresh et al. 2021 Hassani Khasahmadi 2022] Xie et al., 2022) and node classification (Zhao et al. 2021 Sun et al. 2021), they have not been studied in supervised graph classification. In this work, we propose GraphAug, a novel automated data augmentation framework for graph classification. GraphAug automates augmentation category selection and graph transformations through a learnable augmentation model. To produce label-invariant augmentations, we optimize the model to maximize an estimated label-invariance probability with reinforcement learning. To our best knowledge, GraphAug is the first work successfully applying automated data augmentations to generate new graph data samples for supervised graph classification.
3.1 AUGMENTATION BY SEQUENTIAL TRANSFORMATIONS
Similar to the automated image augmentation method in Ratner et al. (001b)), we consider graph augmentations sequential transformation process. Given a graph Go sampled from the train- ing dataset, we map to the augmented graph GT with sequence of transformation functions a1, (22 ..., aT generated by automated data augmentation model g. Specifically, at the (-th step (1 < < T), let the graph obtained from the last step G,-1, we first use the augmentation model to generate a based on Gi-1, and map Gi-1 Ge with a, In summary, this sequential augmentation process can be described as
at = g(
G =
(GG-)),
1
(3)
In our method, d1 02 ..., ar are all selected from three categories graph transformations:
Node feature masking (MaskNF), which sets some values in node feature vectors to zero;
Node dropping (DropNode), which drops certain portion of nodes from the input graph;
Edge perturbation (PerturbEdge), which produces the new graph by removing existing edges
from the input graph and adding new edges to the input graph.
3.2 LABEL-INVARIANT AUGMENTATIONS
Most automated image augmentation methods focus on automating augmentation category selection. For instance, Ratner et al. (2017b) automate image augmentations by generating discrete sequence from an LSTM (Hochreiter & Schmidhuber] 1997) model, and each token in the sequence represents certain category of image transformation, such random flip and rotation. Following this setting.
3

---

Published as a conference paper at ICLR 2023
our graph augmentation model 9 also selects the augmentation category at each step. Specifically, g will generate a discrete token o representing the category of augmentation transformation at denoting whether MaskNF, DropNode, or PerturbEdge will be used at the t-th step.
We have experimented to only automate augmentation category selection and use the graph trans- formations that uniformly operated on each graph element, such each node, edge, node feature. For example, the uniform DropNode will randomly drop each node in the graph with the same probability. These transformations are commonly used in other studies (You et al. 2020 Zhu iet al. 2021a la Rong et al. 2020), and we call them as uniform transformations. However, we find that this automated composition of multiple uniform transformations does not improve classifica- tion performance (see Section 4.3 for details). We argue that it is because uniform transformations have equal chances to randomly modify each graph element, thus may accidentally damage signif- icant label-related information and change the label of the original data sample. For instance, in a molecular graph dataset, assuming that all molecular graphs containing a cycle are labeled as toxic because the cyclic structures exactly the cause of toxicity. If we are using DropNode transfor- mation, dropping any node belonging to the cycle will damage this cyclic structure, and map a toxic molecule to non-toxic one. By default, data augmentations only involve modifying data samples while labels are not changed, so data augmentations that are not tabel-invarian may finally produce many noisy data samples and greatly harm the training of the classification model.
We use the TRIANGLES dataset (Knyazev et al. 2019) as an example to study the effect of label- invariance. The task in this dataset is classifying graphs by the number of triangles (the cycles formed by only three nodes) contained in the graph. As shown in Figure 3 of Appendix [A] the uni- form DropNode transformation is not label-invariant because it produces data samples with wrong labels through dropping nodes belonging to triangles, and the classification accuracy is low when the classification model is trained on these data samples. However, if we intentionally avoid dropping nodes in triangles, training the classification model with this label-invariant data augmentation im- proves the classification accuracy. The significant performance gap between these two augmentation strategies clearly demonstrates the importance of label-invariance for graph augmentations.
Based on the above analysis and experimental results, we can conclude that uniform transforma- tions should be avoided in designing label-invariant graph augmentations. Instead, we generate transformations for each element in the graph by the augmentation model g in our method. Next, we introduce the detailed augmentation process in Section 3.3 and the training procedure in Section 3.4
3.3 AUGMENTATION PROCESS
Our augmentation model g composed of three parts. They are a GNN based encoder for extracting features from graphs, GRU (Cho et al.] 2014) model for generating augmentation categories, and four MLP models for computing probabilities. We use graph isomorphism network (GIN) (Xu et al. 2019) model as the encoder.
At the t-th augmentation step (1 < t S T), let the graph obtained from the last step be GG-1 = (V--1, 16-1,X,-1) we first add virtual node Uoirtual into Vi-1 and add edges connecting the virtual node with all the nodes in V--1- In other words, a new graph G/-1 = (V/ Ei x/-1) is created from G--1 such that Vi-, = V/-1 U (Fvartuatt }. E = E U ((Vertuull v) u V--1),
and X E [ is the concatenation of X,-1 and a trainable initial feature vector for the virtual node. We use the virtual node here to extract graph-level information because it can capture long range interactions in the graph more effectively than a pooling based readout layer (Gilmer) al. 2017). The GNN encoder performs multiple message passing operations on Gi-1 to obtain r- dimensional embeddings {ei_1 E R u E Vi-1 for nodes in V and the virtual node embedding evirtual E Rr. Afterwards, the probabilities of selecting each augmentation category is computed from et-1 cintual as q: GRU( efirtual), ) of MLPC (q:), where q: is the hidden state vector of the GRU model at the t-th step, and the MLP model MLP outputs the probability vector of E g denoting the probabilities of selecting Mask DropNode, or PerturbEdge the augmentation at the t-th step. The exact augmentation category e for the t-th step is then randomly sampled from the categorical distribution with the probabilities in p,"" Finally, described below, the computation of transformation probabilities for all graph elements and the process of producing the new graph G, from G vary depending Gt.
4

---

Published as a conference paper at ICLR 2023
Extract node embedddnngs
Select augmentation category
Perform transformation
vituaal node
sample for each node feature
node festures
Viriiel mode embedd ig
Vituaal node featire
node embeddingg
C MaskNE
masiked node
G
GRU
mach nodis
GMM iencssder
MLP
node amrbeddings
DropNode
uirizol 11-1
xemple for each odgo
vituual embodding
Mukkhe Dispicee Panuttdgg
nodo wrttestiigg
Ct
embeodingg
PerturbEage
Figure I: An illustration of the process of producing G, from G.-1 with the augmentation model.
If c₁ is MaskNF, then for any node feature of v is computed by the MLP model MLP taking the node embedding e--1 as input. Afterwards, a binary vector M E {0, is randomly sampled from the Bernoulli distribution parameterized with M If the k-th element of of is one, i.e., o [k] = 1, the k-th node feature of is set to zero. Such MaskNF transformation is performed for every node feature in X,-1-
Vi-1, the probabilities Pi.e I of masking each node
o is DropNode, then the probability pf, of dropping any node v Vi-1 from G,- is computed by the MLP model MLP taking the node embedding ei_ as input. Afterwards, a binary value of. E {0, is sampled from the Bernoulli distribution parameterized with př. and is dropped from V if of. Such DropNode transformation is performed for every node in V
If at is PerturbEdge, the transformations involve dropping some existing edges from E,- and adding some new edges into E We consider the set E, as the droppable edge set, and we create an addable edge set E,-1, by randomly sampling at most | addable edges from the set {u, v) u, V/-1, (u, v) & E,-1). For any (u, v) in E,-1, we compute the probability P. Pr,(w.)) of dropping it by the MLP model MLP taking [e + e_ 1] as input, where [.--1 denotes the concatenation operation. For any (u, v) in ET-1, we compute the probability Pf,(a.)) of adding an edge connecting u and v by MLP" taking [c"_, +e,_1,0) 0] as input. Afterwards, for every (u, v) Ei-1, randomly sample a binary value (((u,,) from the Bernouli distribution parameterized with (..(...) and drop (u, v) from E,_ (,(u,)) = 1. Similarly, we randomly sample ((u,,)) for every (u, v) E Ex-1 but we will add (u, v) into E if (.(,..)) =.
An illustration of the process of producing G, from G,-1 with our augmentation model is given in We also provide the detailed augmentation algorithm in Algorithm ① of Appendix
Figure [
3.4 LABEL- OPTIMIZATION WITH REINFOR LEARNING
As our objective is generating label-invariant augmentations at most times, the ideal augmentation model should assign low transformation prohabilities to graph elements corresponding to label- related information. For instance, when DropNode is used, if the dropping of some nodes will damage important graph substructures and cause label changing, the model g should assign very low dropping probabilities these nodes. However, we cannot directly make the model learn to produce label-invariant augmentations through supervised training because we do not have ground truth labels denoting which graph elements are important and should not be modified. To tackle this issue, we implicitly optimize the model with reinforcement learning based training method.
We formulate the sequential graph augmentations as a Markov Decision Process (MDP). This is intuitive and reasonable, because the Markov property is naturally satisfied, i.e., the output graph at any transformation step is only dependent on the input graph, not on previously performed transfor- mation. Specifically, at the i-th augmentation step, we define G.-1, the graph obtained from the last step, as the current state, and the process of augmenting G to G, is defined as state transition. The action is defined as the augmentation transformation a generated from the model 9, which includes the augmentation category a, and the exact transformations performed on all elements of G The probability p(ax) of taking action a, for different e is is described below.
5

---

Published as a conference paper at ICLR 2023
If C is MaskNF, then the transformation probability is the product of masking unmasking probabilities for features of all nodes in Ve-1, so p(at) is defined as
II II (P), of [4] (1-PMM11)) 1o (. -
p(a:) = p(c))=
(4)
If et is DropNode, then the transformation probability is the product of dropping or non-dropping probabílities for all nodes in Vi-1, so p(a,) is defined as
p(a:) = p(c))
II =EV2-1
oi (1 (1-Pi,) P(.e)
1-o0
(5)
If Ce is PerturbEdge, then the transformation probability is the product of perturbing or non- perturbing probabilities for all edges in Ei- and Ei-1, so p(at) defined as
Kiuwn (1- (1-Pr.(..)) I-dfeu.))
p(a:)= = p(c))=
II
(ph(o..))
(6)
(U.))R 1UE,
We use the predicted label-invariance probabilities from reward generation model as the feedback reward signal in the above reinforcement learning environment. We use graph matching network (Li al., 2019) as the backbone of the reward generation model (see Appendix [ for detailed in- troduction). When the sequential augmentation process starting from the graph Go ends, s takes (Go, Gr) as inputs and outputs sGo, GT), which denotes the probability that the label is invariant after mapping the graph Go to the graph Gr. We use the logarithm of the predicted label-invariance probability, i.e., Rr = log sGo, Gr), as the return of the sequential augmentation process. Then the augmentation model is optimized by the REINFORCE algorithm (Sutton et al. 2000), which updates the model by the policy gradient go computed go R. denotes the trainable parameters of
log p(o)). where
Prior to training the augmentation model g. we first train the reward generation model on manually sampled graph pairs from the training dataset. Specifically, a graph pair (G1, G2) is first sampled from the dataset and passed into the reward generation model to predict the probability that G1 and G2 have the same label. Afterwards, the model is optimized by minimizing the binary cross entropy loss. During the training of the augmentation model g. the reward generation model is only used to generate rewards, so its parameters are fixed. See Algorithm 2 and in Appendix B for the detailed training algorithm of reward generation model and augmentation model.
3.5 DISCUSSIONS AND RELATIONS WITH PRIOR METHODS
Advantages of our method. Our method explicitly estimates the transformation probability of each graph element by the automated augmentation model, thereby eliminating the negative effect of adopting uniform transformation probability. Also, the reinforcement learning based training method can effectively help the model detect critical label-related information the input graph, so the model can avoid damaging it and produce label-invariant augmentations with greater chances.
We will show these advantages through extensive empirical studies in Section [41 [.22 4.2 Besides, the use of sequential augmentation, i.e., multiple steps of augmentation, can naturally help produce more diverse augmentations and samples, and the downstream classification model can benefit from diverse training samples. We will demonstrate through ablation studies in Section
Relations with prior automated graph augmentations. Several automated graph augmentation methods (You et al. 2021 Yin al.] 2022] Suresh al., [02T]] Hassani & Khasahmadij (022) have been proposed to generate multiple graph views for contrastive learning based tre-training.
However, their augmentation models are optimized by contrastive learning objectives, which are not related to graph labels. Hence, their augmentation methods may still damage label-related infor- mation, and we experimentally show that they do not perform as well as GraphAug in supervised learning scenarios in Section 4.2 Though a recent study (Trivedi et al.) 2022) claims that label- invariance is also important in contrastive learning, to our best knowledge, no automated graph augmentations have been proposed preserve label-invariance in contrastive learning. Besides, notice that a very recent study (Yue et al. (202)) also proposes a aabel-invariant automated augmenta- tion method named GLA for semi-supervised graph classification. However, GLA is fundamentally

---

Published as a conference paper at ICLR 2023
Table 1: The testing accuracy on the COLORS and TRIANGLES datasets with the GIN model. We
report the average accuracy and standard deviation over ten runs on fixed cainn/alidation/test splits.
No augmeatation
Uniform MaskNF
Uniform DropNode
Uniform PerturbEdge
Uniform Mixture
Dataset
GraphAug
COLORS TRIANGLES
0.507 0.578+0.001
0.547+0.012 0.473=0.006
0.684+0.014 0.303+0.010
0.560+00001
0.633 0.009
0,506++0.006
0.509=0.020
0.467=0.007
0.003
Temart mm
Paeratoon
Ianation
Danation
Figure 2: The changing curves of average rewards and label-invariance ratios on the validation set of the COLORS and TRIANGLES datasets as the augmentation model training proceeds. The results are averaged over ten runs, and the shadow shows the standard deviation.
different from GraphAug. For a graph data sample, GLA first obtains its graph-level representation by a GNN encoder. Then the augmentations are performed by perturbing the representation vector and label-invariant representations are selected by an auxiliary classification model. However, our GraphAug directly augments the graph data samples, and label-invariance is ensured by our pro- posed training method based on reinforcement learning. Hence, GraphAug can generate new data samples to enrich the existing training dataset while GLAA cannot achieve
Due to the space limitation, we will discuss computational cost, augmentation step number, pre- training reward generation models, limitations, and relation with more prior methods in Appendix D
4 EXPERIMENTS
In this section, we evaluate the proposed GraphAug method on two synthetic graph datasets and seven benchmark datasets. We show that in various graph classification tasks, GraphAug can consis- tently outperform previous graph augmentation methods. In addition, we conduct extensive ablation studies evaluate the contributions of some components in GraphAug.
4.1 EXPERIMENTS ON SYNTHETIC GRAPH DATASETS
Data. We first show that our method can indeed produce label-invariant augmentations and outper- form uniform transformations through experiments on two synthetic graph datasets COLOR ORRSS and TRIANGLES, which are synthesized by running the open sourced data synthesis code of Knyazev et al. (211)). The task of COLORS dataset is classifying graphs by the number of green nodes, and the color of a node is specified by its node feature. The task of TRIANGLES dataset classifying graphs by the number of triangles (three-node cycles). We use fixed train/validation/test splits for experiments on both datasets. See more information about these two datasets in Appendix E.T
Setup. We first train the reward generation model until it converges, then train the automated aug- mentation model. To check whether our augmentation model can learn to produce label-invariant augmentations, at different training iterations, we calculate the average rewards and the label- invariance ratio achieved after augmenting graphs in the validation set. Note that since we ex- plicitly know how to obtain the labels of graphs from data generation codes, we can calculate label- invariance ratio, i.e., the ratio of augmented graphs that preserve their labels. To compare GraphAug with other augmentation methods, different augmentations for ten times, and report the averaged testing classification accuracy. We compare our GraphAug method with not using any data augmentations, and four graph augmenta- tion baseline methods. Specifically, the augmentation methods using uniform MaskNF, DropNode, and PerturbEdge transformations, and a mixture of these three uniform transformations (Uniform Mixture), i.c., randomly picking one to augment graphs at each time, are used as basclines. To en-
train GIN (Xu et al.) 2019) based classification model with

---

Published as a conference paper at ICLR 2023
Table 2: The performance on seven benchmark datasets with the GIN model. We report the average ROC-AUC and standard deviation over ten runs for the ogbg-molhiv dataset, and the average ac- curacy and standard deviations over three 10-fold rross-validation runs for the other datasets. Note that for JOAOv2, AD-GCL, and AutoGCL, we evaluate the augmentation methods of them under the supervised learning setting, so the numbers here are different from those in their papers.
Method
PROTEINS
IMDB BINARY
COLLAB
MUTAG
NC1109
NCI1
ogby molhiv
augmentttiio
0.704=0.004
0.731=0.004
0.806+0.003
0.827=0.013
0.794+0.003
0.804+0.003
0.756=0.014
Unilorm MaskNI
0.702-0.008
0.720=0.006
0.815=0.002
0.788=0.012
0.77740.006
0.794:0.002
0.741=0.010
Uniform Drop
0.707=0.004
0.728=0.006
0.815=0.004
0.787=0.003
0.777=0.002
0.787=0.003
0.717=00011
Uniform PerturhFdge
0.668-0.006
0.728=0.007
0.816+00.003
0,764+0.008
0.555+00.01
0,545+000066
0.755=0.013
Uniform Mixture
0.707=0.004
0.730=0.009
0.815=0.003
0.779=0.014
0.776#0.006
0.783=0.003
0.746=0.010
DrupEdge
0.707__0.002
0..03
0.812100.03
0.779.0.005
0.762.10.077
0.78010.002
0.762_0.010
M-Mixup
0.706=0.003
0.736=0.004
0.811=0.0055
0.798=0.015
0.788:200005
0.803:20.003
0.753=0.013
G-Mixup
0.715=0.006
0.748=0.004
0.811=0.009
0,805=0.020
0.654=0.043
0,686=0.037
0.771=0.005
FLAG
0.709=0.007
0.747=0.008
0.803=0.006
0.835=0.0115
0.80410.002
0.80110.002
0.765=0.011
JOA0v2
0.700 0.003
0.707-0.0006
0.688-00.03
0.775+00.01
0.675+-0.003
0.670+-0.006
0.744-0.014
AD-GCL
0.699_0.008
0.712-10.008
0.670.0..088
0.837100.000
0,634110.003
0.60110.004
0.762-10.013
AutoGCL
0.684=0.008
0.707=0.007
0.745=0.002
0.783=0.022
0.705=0.003
0.737:20.022
0.704=0.016
GraphAug
0..72 0.004
0.762 0.004
0.009
0.853:0.008
0.811:0.002
0.816
0.774-0.001
sure fair comparison, we use the same hyper-parameter setting in training classification models for all methods. See hyper-parameters and more experimental details in Appendix E.1
The changing curves of average rewards and label-invariance ratios are visualized in Fig- 2 These curves show that as the training proceeds, our model can gradually learn to obtain higher rewards and produce augmentations leading to higher -ibar-iivariance ratio. In other words, they demonstrate that our augmentation model can indeed learn to produce label- invaaiiat augmentations after training. The testing accuracy of all methods on two datasets are presented in Table From the results, we can clearly find using some uniform transformations that do not satisfy label-invariance, such as uniform MaskNF on the COLORS dataset, achieve much worse performance than not us- ing augmentations. However, using augmentations produced by the trained GraphAug models can consistently achieve the best performance, which demonstrates the significance of label-invarian augmentations to improving the performance of graph classification models. We further study the training stability and generalization ability of GraphAug models, conduct an exploration experiment about training GraphAug models with adversarial learning, compare with some manually designed label-invariant augmentations, and compare label-invariance ratios with baseline methods on the COLORS and TRIANGLES datasets. See Appendix F.1
Results.
F3 and for details.
4.2 EXPERIMENTS ON GRAPH BENCHMARK DATASETS
Data. We further demonstrate the advantages of our GraphAug method over previous graph aug- mentation methods on six widely used datasets from the TUDatasets benchmark (Morris et al.] 2020), including MUTAG, NCI109, NCII, PROTEINS, MMDB-BINAR conduct experiments on the ogbg-molhiv dataset, which is a large molecular graph dataset from the OGB benchmark (Hu et al. 2020). See more information about datasets in Appendix F.2
and COLLAB. We also
Setup. We evaluate the performance by testing accuracy for the six datasets of the TUDatasets benchmark, and use testing ROC-AUC for the molhim dataset. We use two classification mod- els. including GIN (Xu et al. 2019) and GCN (Kipf & Welling 2017). We use the 10-fold cross- validation scheme with vrann/valiation/nest splitting ratios of 80%/10%/10% on the datasets from the TU-Datasets benchmark, and report the averaged testing accuracy over three different runs. For the oobg-molhiv dataset, we use the official train/validationnesst splits and report the averaged testing ROC-AUC over ten runs. In addition to the baselines in Section 4.1 we also compare with previ- ous graph augmentation methods, including DropEdge (Rong et al. 2020). M-Mixup (Wang al., 2021], G-Mixup (Han et al. (022), and FLAG (Kong et 2022). Besides, we compare with three automated augmentations proposed for graph self-supervised learning, including JOAOv2 (You) et al. 2021), AD-GCL (Suresh et al. 2021), and AutoGCL (Yin et al. (022). Note that we take their trained augmentation modules as the data augmenter, and evaluate the performance of supervised classification models trained on the samples produced by these data augmenters. For fair compar- ison, we use the same
setting in training classification models for GraphAug and baseline methods. See hyper-parameters and more experimental details in Appendix H.2
8

---

Published as a conference paper at ICLR 2023
Table 3: Results of ablation studies about learnable and sequential augmentation. We report the
erage accuracy and standard deviation over three 10-fold cross-validation runs with the GIN model.
Method
PROTEINS
MIDB-BINARY
NCI1
GraphAug w/o learnable graph transformation
0.696=10.006
0.724+00003
0.760=
GraphAug w/o learnable category selection
0.702:10.004
0.746:10.009
0.79610.000
GraphAug w/o sequential augmentation GraphAug
0.712:#0.002
0.753++0.003
0.809=0.004
0.722:10.004
0.762-10.004
0.81610.001
Results. The performance of different methods on all seven datasets with the GIN model is sum- marized in Table 2 and see Table in Appendix [44 for the results of the GCN model. According to the results, our GraphAug method can achieve the best performance among all graph augmenta- tion methods over seven datasets. Similar to the results in Table I for molecule datasets including MUTAG, NC1109, NCII, and ogbg-molhiv, using some uniform transformations based augmenta- tion methods dramatically degrades the classification accuracy. On the other hand, our GraphAug method consistently outperforms baseline methods, such as mixup methods and existing automated data augmentations in graph self-supervised learning. The success graph benchmark datasets once again validates the effectiveness of our proposed GraphAug method.
4.3 ABLATION STUDIES
In addition demonstrating the effectiveness of GraphAug, we conduct a series of ablation experi- ments and use empirical results to answer (1) why we make augmentation automated and learnable, (2) why we use sequential, multi-step augmentation, (3) why we adopt combination of three differ- ent transformations (MaskNF, DropNode. PerturbEdge) instead of using only one, and (4) why we use virtual nodes. We present the ablation studies (1) and (2) in this section and leave (3) and (4) in Appendix F.5) For all ablation studies, we train GIN based classification models on the PROTEINS, IMDB-BINARY, and NCI1 datasets, and use the same evaluation pipeline as Section 4.2
Ablation on learnable graph transformation and category selection. We first show that making the model learn to generate graph transformations for each graph element and select augmenta- tion category are both important. We compare with variant of GraphAug that does not learn graph transformations but simply adopts uniform transformations, and another variant that randomly select the category of graph transformation, instead of explicitly predicting it. The classification accuracy on three datasets of these two variants are presented in the first two rows of Table 3 Results show that the performance of two variants is worse, and particularly removing learnable graph transfor- mation will significantly degrade the performance. It is demonstrated that learning to generate graph transformations and select augmentation category are both key success factors of GraphAug.
Ablation on sequential augmentation. We next show the advantage of sequential augmentation over one-step augmentation. We compare with the variant of GraphAug that performs only one step of augmentation, i.e.. with the augmentation step number T=1, and present its performance in the third row of T It clear that using one step of augmentation will result in worse performance over all datasets. We think this demonstrates that the downstream classification model will benefit from the diverse training samples generated from sequential and multi-step augmentation.
CONCLUSIONS AND FUTURE WORK
We propose GraphAug, the first automated data augmentation framework for graph classification. GraphAug considers graph augmentations as sequential transformation process. To eliminate the negative effect of uniform transformations, GraphAug uses an automated augmentation model to generate transformations for each element in the graph. In addition, GraphAug adopts a reinforce- ment learning based training procedure, which helps the augmentation model learn to avoid damag- ing label-related information and produce aabel-invariant augmentations. Through extensive empiric studies, we demonstrate that GraphAug can achieve better performance than many existing graph augmentation methods on various graph classification tasks. In the future, would like to explore simplifying the current training procedure of GraphAug and applying GraphAug to other graph representation learning problems, such the node classification problem.

---

Published as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
We have provided the detailed algorithm pseudocodes in Appendix and experimental setting de- tails in Appendix E for reproducing the results. The source codes of our method are included in DIG (Liu et al. 202 library.
REFERENCES
Alessandro Bicciato and Andrea Torsello. GAMS: Graph augmentation with module swapping. In Proceedings of the 11th International Conference on Pattern Recognition Applications and Methods (ICPRAM 2022), pp. 249-255, 2022.
Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- decoder for statistical machine translation. In Proceedings of the 2014 conference pirical methods in natural language processing (EMNLP), pp. 1724-1734, Doha, Qatar, Oc- tober 2014, Association for Computational Linguisties. doi: 10.3115/+1/D14-11199 URL
https: www. awlweb.............. org/ axzg/anthology. DD109//DD-119999
Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le. AutoAugment: Learning augmentation strategies from data. In Proceedings of the IEEE/CVP Conference on Computer Vision and Puttern Recognition, pp. 113-123, 2019.
Kaize Ding, Zhe Xu, Hanghang Tong, and Huan Liu. Data augmentation for deep graph learning: A survey, SIGKDD Explor. Newsl., 24(2)x61-77, dec 2022. ISSN 1931-0145. doi: 10.1145/ 3575637.3575646. httts:ts:://dot O4 357534373575455
Hongyang Gao and Shuiwang Ji. Graph U-Nets. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 2083-2092. PMLR, 09-15 Jun 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1263-1272, International Convention Centre, Sydney, Australia, 2017.
Hongyu Guo and Yongyi Mao. Intrusion-frer free graph mixup. arXiv preprint 1 2021.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, pp. 1025-1035, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-Mixup: Graph data augmentation for graph classification. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 8230-8248. PMLR, 17-23 Jul 2022. URL http:: httpp:::/proceedingggg
mlr. www.mmmr.....m.mmmmmmmmm hatps//vv2hhhaaaa2 html
Kaveh Hassani and Amir Hosein Khasahmadi. Learning graph augmentations to learn graph repre- sentations. arXiv preprint arXiv:2201.098300 2022.
Ryuichiro Hataya, Jan Zdenek, Kazuki Yoshizoe, and Hideki Nakayama. Faster Augmeng::nt: Learning augmentation strategies using backpropagation. In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), Computer Vision ECCV 2020, pp. 1-16, Cham, 2020. Springer International Publishing. ISBN 978-3-030-58595-2.
Daniel Ho, Eric Liang, Chen, Ion Stoica, and Pieter Abbeel. Population based augmentation: Efficient learning of augmentation policy schedules. In International Conference on Machine Learning, pp. 2731-2741. PMLR, 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
10

---

Published as a conference paper at ICLR 2023
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 22118-22133. Curran As- sociates, Inc., 2020. URL httptttts///ppoeeeiiiiiii neureiinnnsseeeugeeeee neurips..... wwtpp/pppee/22///11a22. F=60d411a5c5572222 http://222227777722222228888
pdf
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceddings of the 3rd international conference on learning representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, 2017.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. Advances in Neural Information Processing Systems, 32:4202-4212, 2019.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. FLAG: Adversarial data augmentation for graph neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), 2022.
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Yonggang Li, Guosheng Hu, Yongtao Wang, Timothy Hospedales, Neil M. Robertson, and Yongxin Yang. Differentiable automatic data augmentation. Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm (eds.), Computer Vision ECCV 2020, pp. 580-595, Cham, 2020.
Springer International Publishing. ISBN 978-3-030-58542-6.
Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. Graph matching net- works for learning the similarity of graph structured objects. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3835-3845. PMLR, 09-15 Jun 2019.
Sungbin Lim, Ildoo Kim, Taesup Kim, Chiheon Kim, and Sungwoong Kim. Fast AutoAug- ment. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gar- nett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL httth:::////.....t. htttpp:://prooceedingg neuri http://ceeaaaaaa..errrrroo..ppp/ Papeeea000--pppppppp.. pdf
Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou. Learning fair graph represen- tations via automated data augmentations. In The Eleventh International Conference on Learning Representations, 2023. URL http::
wttp::/eeeeeeeeeeeeeeeeeemeee [a_____WPPP_ 1s 9w
Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, Keqiang Yan, Haoran Liu, Cong Fu, Bora M Oztekin, Xuan Zhang, and Shuiwang Ji. DIG: A turnkey library for diving into graph deep learning research. Journal of Machine Learning Research, 22(240):1-9, 2021. URL http::////// //tr///mrr... org/ www.:r/rggppppe.ppeeem pa2ers/222/
21-0343.hrr
Yi Liu, Limei Wang, Meng Liu, Yuchao Lin, Xuan Zhang, Bora Oztekin, and Shuiwang Ji. Spherical message passing for 3D molecular graphs. In International Conference on Learning Representa- tions, 2022. URL
net met/forun: id=givsRXss0 VsRXsOt 9r
Koji Maruhashi, Masaru Todoriki, Takuya Ohwa, Keisuke Goto, Yu Hasegawa, Hiroya Inakoshi, and Hirokazu Anai. Learning multi-way relations via tensor decomposition with neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. graph ea maannngg... 1c
11

---

Published as a conference paper at ICLR 2023
Joonhyung Park, Hajin Shim, and Eunho Yang. Graph Transplant: Node mixup with local structure preservation. Proceedings of the AAAI Conference on Artificial Intel- ligence, 2022.
graph
Alex Ratner, Henry Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Chris Ré. Data augmentation with Snorkel. https: www. snorkel. aarg/blog/tandee 2017a. Accessed:2022-011 2022-01-24
Alexander J. Ratner, Henry R. Ehrenberg, Zeshan Hussain, Jared Dunnmon, and Christopher Ré. Learning to compose domain-specific transformations for data augmentation. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, pp. 3239 3249, Red Hook, NY, USA, 2017b. Curran Associates Inc. ISBN 97815 108669099
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep graph convolutional networks node classification. In International Conference on Learning Repre- sentations, 2020. URL
Ikuro Sato, Hiroki Nishimura, and Kensuke Yokoi. APAC: Augmented pattern classification with
neural networks. arXiv preprint arXiv:/505.032299 2015.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Improving neural machine translation mod- els with monolingual data. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 86-96, Berlin, Germany, Au- gust 2016. Association for Computational Linguistics. doi: 10. 10.18653/v1/P16-10099 URL https: htt///acaanii https://aclaatthllooo
htgg/P161. 1009
P.Y. Simard, D. Steinkraus, and J.C. Platt. Best practices for convolutional neural networks applied to visual document analysis. In Seventh International Conference on Document Analysis and Recognition, 2003. Proceedings., pp. 958 963, 2003. doi: 10. 109/CCDAR.20...II..... 1227800.
Junwei Sun, Bai Wang, and Bin Wu. Automated graph representation learning for node classifica- tion. In 2021 International Joint Conference on Neural Networks (IJCNN) pp. 1-7, 2021. doi: N0.1109/DCNN52387.22011111
Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial graph augmentation im- prove graph contrastive learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https: //openreview. wonenrrwiiew.nnt//oounaaaa
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour. Policy gradient methods for reinforcement learning with function approximation. In Advances in neural informa- fion processing systems, pp. 1057-1063, 2000.
Luke Taylor and Geoff Nitschke. Improving deep learning with generie data augmentation. In 2018
JEEE Symposium Series on Computational Intelligence (SSCI), pp. 1542-1547. IRFE, 2018.
Puja Trivedi, Ekdeep Singh Lubana, Yujun Yan. Yaoqing Yang. and Danai Koutra. Augmentations in graph contrastive learning: Current methodological flaws & towards better practices. In Proceed- ings of the ACM Web Conference 2022, WWW '22, pp. 1538-1549 New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450390965.
doi: 10. 00.114573485447:3552200
URL https::///// / /tttps::/doi.ooe http:///oooooo11..1111 1ttp://11.111/3448313
3512200
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL TRllitttps://pperreettt
net. www.moormmmmmm//mm/ d=r kCZ.
Limei Wang, Yi Liu, Yuchao Lin, Haoran Liu, and Shuiwang Ji. ComENet: Towards complete and efficient message passing for 3d molecular graphs. In Alice H. Oh, Alekh Agarwal, Danielle Bel- grave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022a. net. http:://ppeeevvveeeee www.wewweeeettreeeeeeeeeee forum? waerrmmmmmmCCaa. d=mC..MgeWSFF
Limei Wang, Haoran Liu, Liu, Jerry Kurtin, and Shuiwang Ji. Hierarchical protein representations via complete 3d graph networks. International Conference on Learning Representations, 2023.
URL /ttttsts:///........ pttttp:://openrevieee www.eeeewwweeeoomm///eoooooo
12

---

Published as a conference paper at ICLR 2023
Yiwei Wang, Wei Wang, Yuxuan Liang. Yujun Cai, and Bryan Hooi. GraphCrop: Subgraph cropping for graph classification. arXiv preprint arXiv:2009.10564 2020.
Yiwei Wang, Wei Wang. Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, WWW '21, pp. 3663-3674, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 978 178033333.. doi: 10. htttps///beb..rrr//..111////333 1tt...144/44223339999399999 3449796
1145/3442381 .3449796. URL https://tccciiio.. wwtp://....rroo.. 114.0/.114/3331
Zhengyang Wang. Meng Liu, Youzhi Luo, Zhao Xu, Yaochen Xie, Limei Wang, Lei Cai, Qi Qi, Zhuoning Yuan, Tianbao Yang, and Shuiwang Ji. Advanced graph and sequence neural net- works for molecular property prediction and drug discovery. Bioinformaties, 3809):257--2586 02 2022b. ISSN 1367-4803 doi: 11109//iiinfoommcii///aalllllll URLpttts:://ao...
10.1093/bioinformaacc /bt.cc1ttacaa22
Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. Self-supervised learning of graph neural networks: A unified review. IEEE Transactions on Pattern Analysis and Machine Intelligence, pp. 1-1, 2022. doi: 10.1 10.1009/PAM.2222.3775555
Keyulu Xu, Weihua Hu. Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference Learning Representations, 2019. URL https:
//openreview. serpenreviee.ee//frrrroe dddorrmmmmdryyyaai Am5km
Keqiang Yan, Yi Liu, Yuchao Lin, and Shuiwang Ji. Periodic graph transformers for crys- tal material property prediction. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL net htte:/oormmiddddee httpss//eepereevii Iort
Yihang Yin, Qingzhong Wang, Siyu Huang, Haoyi Xiong, and Xiang Zhang. AutoGCL: Automated graph contrastive learning via learnable view generators. Proceedings of the AAAI Conference on Artificial Intelligence, 36(8):8892 8900, Jun. 2022. doi: 10.1609/anai. v36i8. www....261..77777. 20871.
URL
https:://jjs.ce aaa.i....aaa...a................ org/ index http://////aattttlll/////////e/a http://.....aaaaaoo.....oo./a/tr
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33:5812-5823, 2020.
Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning tomated. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Con- ference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp- 12121-12132. PMLR, 18-24 Jul 2021.
Shuo Yu, Huafei Huang, Minh N. Dao, and Feng Xia. Graph augmentation learning. In Companion Proceedings of the Web Conference 2022, WWW '22 pp. 1063-1072, New York, NY, USA, 2022. Association for Computing Machinery, ISBN 9781450391 306. doi: 00.145/3487533.3524771..
URL https::/do...... http:///ooooog///.//// 1145/11875/355333 3524718
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. XGNN: Towards Model-Level Explanations
of Graph Neural Networks, pp. 430-438. Association for Computing Machinery, New York, NY, USA, 2020. ISBN 9781 9781450379984. http:t/:::///
34C3085
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 12241-12252. PMLR, 18-24 Jul 2021.
Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi-supervised graph classification. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL net net/ Eorum? iid _g_yy__BHp__ee
Xinyu Zhang, Qiang Wang, Jian Zhang, and Zhao Zhong. Adversarial AutoAugment. In Interna- tional Conference on Learning Representations, 2020. URL htthttts///ppaeevieee..tt
forum? dirrum?kd-Ryy
13

---

Published as a conference paper at ICLR 2023
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. Proceedings of the AAAI Conference on Artificial In- relligence, 35(12)111015-1102, 11023, May 2021. doi: 10. hwwp:6/0/aaii.3555......
URL https:
T/ojs.aaat org www.rrgnndeeeee http:/ineexxpppe http://ideeeeepppeaeeeaae
Tong Zhao, Gang Liu, Stephan Günneman, and Meng Jiang. Graph data augmentation for graph machine learning: A survey, arXiv preprint 2.X::22002.0887,, 2022.
Jiajun Zhou, Jie Shen, and Qi Xuan. Data Augmentation for Graph Classification, pp. 2341-2344. Association for Computing Machinery, New York, NY, USA, 2020a. ISBN 9781450368599.
URL httpt::t/o/oiiii.. http::::///ooooo////////// 10. 1145/3344533111111 3412086
Jiajun Zhou, Jie Shen, Shanqing Yu, Guanrong Chen, and Qi Xuan. M-Evolve: cauctural-mapping based data augmentation for graph classification. IEEE Transactions Network Science and Engineering, 8(1):190-200, 2020b.
Yanqiao Zhu, Yichen Xu, Qiang Liu, and Shu Wu. An empirical study of graph contrastive learning. In Thirty-ffth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021a.
net htte:/ooommmddduubbbbb YnHKO
Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Graph contrastive learning with adaptive augmentation. In Proceedings of the Web Conference 2021, www '21, pp. 2069-2080, New York, NY, USA, 2021b. Association for Computing Machinery. ISBN doi: 10.1145/3442381. 249949990 URL
9781450383127.
3442381 3442381.344988 3449802
14

---

Published as a conference paper at ICLR 2023
A VISUALIZATION OF DIFFERENT AUGMENTATION METHODS
(a) illustration data sam- ple from the TRIANGLES dataset. Red nodes represent the nodes be- longing triangles. The label of this data sample since there are four triangles. Training without any augmentations on the TRIAN- GLES dataset achieves the average lesting accuracy of 0.506 + 0.006.
(b) The data sample generated by augmenting the data sample in (a) with the uniform DropNode transformation. Note that two nodes originally belonging angles are removed, and the label is changed to 1. Training with the uniform DropNode transformation achieves the average testing accu- racy 0.473 + 0.006.
(c) The data sample generated hy augmenting the data sample in (a) with the label-invariant DropN- ode transformation (the DropNode with GT method in Appendix [F33) which intentionally avoids drop- ping nodes in triangles. Training with this label-invariant augmen- tation achieves the average testing accuracy 0.522 + 0.007.
Figure 3: Comparison of different augmentation methods on the TRIANGLES dataset. We use
GIN (Xu et al. 2019) based classification model to evaluate different augmentation methods, and report the average accuracy and standard deviation over ten runs on fixed train/validation/tes split. In (a), we show a graph data sample with 4 triangles. In (b) and (c), we the data samples generated by augmenting the data sample (a) with two different augmentation methods. We can clearly find that using the uniform DropNode transformation degrades the classification performance but using the
augmentation improves the performance.
15

---

Published as a conference paper at ICLR 2023
B AUGMENTATION AND TRAINING ALGORITHMS
Algorithm 1: Augmentation Algorithm of GraphAug
1: Input: Graph Go (Vo. Ea, Xo); total number of augmentation steps T; the augmentation model composed of GNN-encoder, GRU, and four MLP models MLP MLP MLPP. MLP"
2: Initialize the hidden state qo of the GRU model to zero vector
3: for = 1 to T do
4: Obtain - by adding a virtual node to G
5: e {e;_1:00 Vi-1} GNN-encoder (111)
6: qe = GRU( 1 (urr
7:
pf MLP (7:)
8:
Sample a from the categorical distribution of 9
9:
if ot is MaskNF then
10: for V E V do
11:
M Pi.e = MLP"MeT_)
12:
Sample og2 from the Bernoulli distribution parameterized with Piçv
13:
for 1 do
14:
Set the k-tth node feature of to zero if of [k] 1
15: else if ct is DropNode then
for v E V do
17:
pr.0 MLPP (c
Sample of, from the Bernoulli distribution parameterized with pL,
19:
Drop the node from Vi-1 o, =
20:
else if c, is PerturbEdge then
21:
Obtain the addable edge set E,- by randomly sampling at most |E--1 addable edges
from {(u, v) u, E Vi-1, (u, & Ex-1}
22:
for (u, v) E Ei-1 do Pi,(u,o) = MLP (
23:
Sample ((.(u.w) from the Bernoulli distribution parameterized with p ((,(w)))
25:
Drop (u, v) from E,-1 if of, ((u,)) =1
26:
for (u, v) E E,-1 do
27:
Pi,(u,o) = MI.PP ((ei-1+ +),,,
28:
Sample (f.(u.v) from the Bernoulli distribution parameterized with pf,(u,))
29:
Add (u, v) into Ez-1 if o..(u..) =
Set G2 as the outputted graph from the t-th augmentation step
31:
Output GT
Algorithm 2: Training Algorithm of the reward generation model of GraphAug
1: Input: Graph dataset D; batch size B; learning rate a; the reward generation model with the parameter yp
2: repeat
3: Sample batch of B data samples from D
4: -=0
5: for G do
6:
Randomly sample graph G+ with the same label as G' from & and a graph G with different label G
7:
L= L log (G, G+) log(1 s(G, GT) 8: Update the parameter yp of & as & = & - aV L/B
9: until the training converges
10: Output the trained reward generation model s
16

---

Published as a conference paper at ICLR 2023
Algorithm 3: Training Algorithm of the augmentation model of GraphAug
Input: Graph dataset D; batch size B; learning rate a; total number of augmentation steps T; the augmentation model with the parameter 0 composed of GNN-encoder, GRU, and four MLP models MLP MMLPM MLPD, MLP"; the trained reward generation model s
2: repeat
3: Sample batch G of B data samples from D
4: Go
0
5:
for G E do
6:
Set Go (Vo: Po. Xo) as G
7:
Initialize the hidden state qo of the GRU model to zero vector tort= to do
8:
9:
Obtain G²-1 by adding virtual node Gt-1 virtual et-1 {ci-1 U V2-1) GNN-encoder( (1,
9i ,, e
12:
P MLP (4:)
13:
Sample с, from the categorical distribution of pf, set logp(as) log (cx)
14:
e is MaskNF then
for E V do
p/, MLP (ei-1)
17:
Sample MM from the Bernoulli distribution parameterized with pE, for k 1 to d do
18:
19:
p(,)(a,) = log p(a,) + of [k] log pi [k] + (1 o [k)] log(1 - Pt, [k])
20:
Set the k-th node feature of u to zero if M [k] = else e DropNode then
22:
for E 1 do
23:
p.. = MLP (MPP(ce_1))
24:
Sample of. from the Bernoulli distribution parameterized with pf,
p(a,() = p(a)(a;) + of log P.. (1 o..)) log(1 -,,)) Drop the node e from V if of =1
26:
else if c; PerturbEdge then
28:
Obtain the addable edge set E,-1 by randomly sampling at most | addable edges from {(u, v) u, V Vi-1, (u, (u,v) & E--1
29:
for (u, v) E Ei-1 do
30:
Pi,(u,v) = MLP (le 1.)
31:
Sample of,(u.v) from the Bernoulli distribution parameterized with pf (u, p(a,) p(ar) (o.())) logp(,(w.)) + (1 (f log((1 P Pr.(u..))
32:
33:
Drop (u, v) from E:- if of (((,,)) =1
34:
for (u, v) E Ec-1 do
35:
Pi((u.v) MLP (lei-1+ + 0))
36:
Sample of,(u.n) from the Bernoulli distribution parameterized with pfP (u.()))) log ((g)( log p(g,) + + (u,,)) loggf, + (1 - (,,))) log(1 - pl.(,.)))
37:
log(1
38:
Add (u, v) into E,-1 if of (,,vv) =1
39:
Set G, as the outputted graph from the t-th augmentation step Go -g + log (Go, Gr) Σt= logp(at)
40:
Update the parameter
g as 0 + aga/B. B.
42:
until the training converges
Output the trained augmentation model g
17

---

Published as a conference paper at ICLR 2023
C DETAILS OF REWARD GENERATION MODEL
We use the graph matching network (Li et al. 2019) as the reward generation model & to predict the probability sGo, GT) that Go and Gr have the same label (here Go is graph sampled from the dataset, i.c., the starting graph of the sequential augmentation process, and Gr is the graph produced from steps of augmentation by the augmentation model). The graph matching network takes both Go = (Vo, Eg, Xo) and GT = (Vr. Er. .x) as input, performs multiple message operations on them with a shared GNN model separately. The computational process of the message passing for any node in Go at the E-th layer of the model is
h UPDATE (h.-1.
, AGG (fmj.. : E ((())) . )
which is the same as the message passing of vanilla GNNs in Equation ①1) other than involving propagating the message 1 from the graph Gr to the node in Go. The message yu is extracted by an attention based module
exp (sim (hG-1,A;-)) 1)
Σ iEVr
who - -f-1).. VE Vo, (8)
Wiv Σuev, exp (sim (N--1 1)-
where -im(:,) computes the similarity between two vectors by dot-product. The message passing for any node in Gr is similarly computed as Equation (7). and this also involves propagating mes-
sage from Go to nodes in Gr with the attention module in Equation (8). Afterwards, the graph-level representations ha. and ha, of Go and Gr are separately obtained from their node embeddings as
in Equation (2). We pass lhc. - -hrhl I. the element-wise absolute deviation of lGo and ha, an
MLP model to compute s (Go: GT).
18

---

Published as a conference paper at ICLR 2023
D MORE DISCUSSIONS
Discussions about computational cost. Considering a graph with V nodes and [ edges, the time complexity of performing our defined DropNode or MaskNF transformation on it is ((VV), and the ) for the PerturbEdge transformation since both edge dropping or addition operated on at most [E] edges. Hence, the time complexity of augmenting the graph for 7 steps is V + E)). This time cost is affordable for most real-world applications. We test the average time used to augment a graph on each benchmark dataset used in our experiments with our trained augmentation model, see Table I0 for time results. We can find that for most dataset, method only takes a very small amount of time (< 0.05 s) to augment a graph in average. Besides, during the training of the augmentation model, the computation of rewards by the reward generation model involves attention module (see Equation (9)). which causes an extra computational cost of (((V)"). In practice, this does not have much effect on small graphs, but may lead to large computation and memory cost on large graphs.
time complexity is O(EE))
Discussions about augmentation step number. For the number of augmentation steps T, do not let the model to learn or decide T itself but make T a fixed hyper-parameter to avoid the model being stucked in the naive solution of not doing augmentation at all (i.e.. learn T 0). This strategy is also adopted by previous image augmentation method (c.g. AutoAugment (Cubuk et al. 2019 larger T encourages the model to produce more diverse augmentations but makes harder to keep label-invariance. We experimentally find that if T 2 8, it is hard to obtain sufficiently high reward for the model. Hence, we tune T' in [1, 8) for each dataset to achieve the best trade-off between producing diverse augmentations and keeping label-invariance.
Discussions about pre-training reward generation model. In our method, before training the augmentation model, we first pre-train the reward generation model and make it fixed while training the augmentation model. Such a training pipeline has both advantages and disad vantages. The ad- vantages of using the fixed/pre- trained reward generation model are two-fold. (1) First, pre-training the reward generation model enables it to accurately predict whether two input graphs have the same labels not, so that the generated reward signals can provide accurate feedback for the augmen- tation model. (2) Second, using the fixed reward generation model can stabilize the training of the augmentation model in practice. As we shown in Appendix [22] if the reward generation model is not fixed and jointly trained with the augmentation model, the training becomes unstable and mod- els consistently diverge. The disadvantage of pre- pre-training the reward generation model is that this training pipeline is time-consuming. because we have to train two models every time to obtain the finally usable graph augmenter.
Limitations of our method. There are some limitations in our method. (1) First, our method adopts a complicated two-step training pipeline which first trains the reward generation model and then trains the augmentation model. We have tried simplifying it to one-step training through adversarial training as in Ratner et al. (0176). However, we found it to be very unstable and the augmenta- tion model consistently diverges (see Appendix F22 for exploration experiment about adversarial training on the COLORS and TRIANGLES dataset). We leave the problem of simplifying the train- ing to the future. (2) Second, our augmentation method will take extra computational cost in both training the augmentation model and providing augmented samples for the downstream graph clas- sification training. The time and resource cost of training models can be large on the large datasets. For instance, on the ogbg-molhiv dataset, we find it takes the total time of around 10 hours to train the reward generation model and augmentation model before we obtain a finally usable graph aug- menter. Given that the performance improvement is not significant on the ogbg-molhiv dataset, such a large time cost is not worthwhile investment. Our GraphAug mainly targets on improving the graph classification performance by generating more training data samples for the tasks with small datasets, particularly for those that need huge cost to manually collect and label new data samples. But for the classification task with sufficient training data, the benefits of using GraphAug are limited and not worth the large time and resource cost to train GraphAug models.
Relations with automated image augmentations. GraphAug are somehow similar to some auto- mated image augmentations (Cubuk et al., 2019; Zhang et al. (020) in that they both use sequential augmentation and reinforeement learning based training. However, they are actually fundamen- tally different. Label-invariance is not a problem in automated image augmentations because the used image transformations ensure lahel-invariance. On the other hand, discussed in Section 3.2
19

---

Published as a conference paper at ICLR 2023
it is non-trivial to make graph transformations ensure label-invariance. In GraphAug, the learn- able graph transformation model and the reinforcement learning based training are used to produce label-invariant augmentations, which are actually the main contribution of GraphAug. Another fundamental difference between GraphAug and automated image augmentations lies in the reward design. Many automated image augmentation methods, such Automugment (Cubuk al.] 2019), train& a child network model on the training data and use the achieved classification accuracy on the validation data as the reward. Instead, our GraphAug uses the label-invariance probability predicted by the reward generation model as the reward signal to train the augmentation model. We argue that such reward design has several advantages over using the classification accuracy as the reward. (1) First, maximizing the label-invariance probability can directly encourage the augmentation model to produce label-invariant augmentations. However, the classification accuracy is not directly related to label-invariance, so using it as the reward feedback does not necessarily make the augmentation model learn to ensure label-invariance. (2) Second, predicting the label-invariance probability only needs one simple model inference process that is computationally cheap, while obtaining the clas- sification accuracy is computationally expensive because needs to train a model from scratch. (3) Most importantly,
reward generation scheme facilitates the learning of the augmentation model by providing the reward feedback for every individual graph. Even in the same dataset, the label-related structures or patterns in different graphs may vary lot, hence, good augmentation strategies for different graphs can be different. However, the classification accuracy evaluates the classification performance when using the produced graph augmentations to train models on the overall dataset, which does not provide any feedback about whether the produced augmentation on every individual graph sample is good or not. Differently, the lahel-invariance probability is com- puted for every individual graph sample, thereby enabling the model to capture good augmentation strategies for every individual graph. Considering these advantages, we do not use the classification accuracy but take the label-invariance probability predicted by the reward generation model as the reward. Overall, GraphAug cannot be considered as a simple extension of automated image augmentations to graphs.
Relation with prior graph augmentation methods. In addition to GLA Yue et al. 2022). we also notice Graphair (Ling et al. 2023), another recently proposed automated graph augmentation method. However, Graphair aims to produce fairness-aware graphs for fair graph representation learning, while our method is proposed for graph classification. Additionally, graph mixup methods
(Wang et al.) 2021 Han et al. 2022 Guo & Mao 2021 Park et al. (202)) synthesize a new graph or graph representation from two input graphs. Because the new data sample is assigned with the combination of labels of two input graphs, mixup operations are supposed to detect and mix the label-related information of two graphs (Guo & Mao 202I). However, our method is simpler and more intuitive because it only needs to detect and preserve the label-related information of one in- put graph. In addition, another method FLAG (Kong et al.) 2022) can only augment node features, while our method can produce augmentations in node features, nodes and edges. Besides, similar to the motivation of our GraphAug, some other studies have also found that preserving important structures or node features is significant in designing effective graph augmentations. A pioneering method in this direction is GCA (Zhu et al., 20216), which proposes to identify important edges and node features in the graph by node centralities. GCA augments the graph by random edge dropping and node feature masking, but assigns lower perturbation probabilities to the identified important edges and node features. Also, other studies (Wang al. 2020 Bicciato & Torsello 2022 Zhou let al.] (2020)) assume that some motif or subgraph structures in the graph is significant, and propose to augment graphs by manually designed transformations to avoid removing them. Overall, these augmentations are based on some rules or assumptions about how to preserve important structures of the input graph. Differently, our GraphAug method does not aim to define a fixed graph aug- mentation strategy for every graph. Instead, it seeks to make the augmentation model find good augmentation strategies automatically with reinforcement learning based training.
Relations with graph explainability. Our method is related to graph explainability in that the predicted transformation probabilities from our augmentation model g is similar to explainability scores of some graph explainability methods (Maruhashi et al., 2018 Yuan et al.] 2020 (021). Hence, we hope that our augmentation method can bring inspiration to researchers in the graph explainability area.
20

---

Published as a conference paper at ICLR 2023
Table 4: Statistics of graph benchmark datasets.
Datasets
graphs
Average # nodes
Average # edges
# classes
PROTEINS
1113
39.06
72.82
IMDB-BINARS
1000
19.77
96.53
COLLAB
5000
74.49
2457.78
MUTAG
188
17.93
19.79
NCI109
4127
29.68
32.13
NCII
4110
29.87
32.30
ogbg-molhiv
41,127
25.5
27.5
Table 5: Some hyper-paramette for the reward generation model and its training.
Datasets
layers
batch size
# training epochs
PROTEINS
6
32
420
IMDB-BINARY
6
32
320
COLLAB
5
8
120
MUTAG
32
230
NC1109
5
32
200
NCII
32
200
ogbg-molhiv
5
32
200
E MORE DETAILS ABOUT EXPERIMENTAL SETTING
E.1 EXPERIMENTS ON SYNTHETIC GRAPH DATASETS
Data information. We synthesize the COLORS and TRIANGLES dataset by running the open sourced data synthesis code of Knyazev et al. (2019). For the COLORS dataset, we synthesize 8000 graphs for training, 1000 graphs for validation. and 1000 graphs for testing. For the TRIANGLES dataset, we synthesize 30000 graphs for training, 5000 graphs validation, and 5000 graphs for testing. The labels of all data samples in both datasets belong to {1...., 10).
Details the model and training. The Adam optimizer (Kingma Ba, 2015) is used the training of all models. For both datasets, we use reward generation model with 5 layers and the hidden size 256, and the graph level embedding is obtained by sum pooling. It is trained for epoch the COLORS dataset and 200 epochs the TRIANGLES dataset. The batch size is 32 and the learning rate is 0.0001. For the augmentation model, we use GIN model with 3 layers and the hidden size of 64 for GNN encoder, MLP model with 2 layers, the hidden size of 64, and ReLU the non- non-linear activation function for MLP and an MLP model with 2 layers, the hidden size of 128, and ReLU the non-linear activation function for MLP MLP", and MLP" The augmentation model is trained for epochs with the batch size of 32 and the learning rate of 0.0001 on both datasets. To stabilize the training of the augmentation model, manually control the augmentation model to only modify 5% of graph elements at each augmentation step during the training. On the COLORS dataset, we the hidden size is 128, and the readout layer is max pooling. On the TRIANGLES dataset, we use classification model where the number of layers is the hidden size is 64, and the readout layer is sum pooling. On both datasets, we set the training batch size as 32 and the learning rate as 0.001 when training classification models, and all classification models are trained for 100 epochs.
classification model where the number of layers is 3,
E.2 EXPERIMENTS ON GRAPH BENCHMARK DATASETS
Data information. We use six datasets from the TUDatasets benchmark (Moris al. 2020), in- cluding three molecule datasets MUTAG, NC1109, NCII, one bioinformatics dataset PROTEINS, and two social network datasets IMDB-BINARY and COLLAB. We also use the ogbg-molhiv
21

---

Published as a conference paper at ICLR 2023
Table 6: Some hyper-parameters for the augmentation model and its training.
Datasets
augmentation steps
batch size
training epochs
PROTEINS
32
30
IMDB-BINARY
8
32
30
COLLAB
8
32
10
MUTAG
16
200
NC1109
2
32
20
NCII
32
20
ogbg-molhiv
2
128
10
Table 7: Some hyper-parameters for the classification model and its training.
Datasets
# layers
hidden size
batch size
PROTEINS
128
32
IMDB-BINARY
128
32
COLLAB
64
32
MUTAG
128
16
NCI109
128
32
NCII
128
32
ogbg-molhin
300
32
dataset from the OGB benchmark (Hu al. 2020). See Table 4 for the detailed statistics of all benchmark datasets used in our experiments.
Details of model and training. The Adam optimizer (Kingma Ba 2015) used for training of all models. For all six datasets, set the hidden size 256 and the readout layer as sum pooling for the reward generation model, and the reward generation model trained using 0.0001 as the learning rate. See other hyper-parameteed about the reward generation model and its training in Table The hyper-parameter parametrrssssssss synthetic graph datasets and the learning rate is 0.0001 during its training, but we size, the training epochs and the number of augmentation steps T on each dataset. See Table 6 for the optimal values of them each dataset. The strategy of modifying only 5% of graph elements is also used during the training of augmentation models. Besides, for classification models, we set the readout layer as mean pooling, and the number of layers, the hidden size, and the training batch size. See Table / for these hyper-parameters. All classification models are trained for 100 epochs with the learning rate of 0.001.
the augmentation model is the same as those in experiments of
the batch
22

---

Published as a conference paper at ICLR 2023
COL.C8 COLO85
TRUMIGLOS
ANGLES
Tracing
230
150
380
Caser
150
Figure 4: The changing curves of training and validation loss on the COLORS and TRIANGLES datasets when training the reward generation model of GraphAug with Algorithm The results are averaged over ten runs, and the shadow shows the standard deviation.
COLORS
COLORS
TUANGLES
TRUANGLSS
100110
Valrodtan
Strntoo
Haraton
Barator
Reratin
Figure 5: The changing curves of training and validation rewards on the COLORS and TRIANGLES datasets when training the augmentation model of GraphAug with Algorithm 3 The results are averaged over ten runs, and the shadow shows the standard deviation.
Training Reward of Augmentation Model
Training Loss of Reward Generation Model
-0.
1.4
Training Reward
1.2
1.0
Training
0.0
0.6
0.4
0
200
400
600
800
1000
200
400
600
600
1000
lteration
Iteration
Figure 6: The changing curves of training rewards of augmentation model and training loss of reward generation model when training two models together with adversarial learning on the COLORS dataset. The results are averaged over ten runs, and the shadow shows the standard deviation.
F MORE EXPERIMENTAL RESULTS
F.I STUDY TRAINING STABILITY AND GENERALIZATION
Taking the COLORS and TRIANGLES datasets as examples, we show the learning curves of reward generation models and augmentation models in Figure 4 and Figure 5 respectively. The learning curves on the training set show that the training is generally very stable for both reward generation models and augmentation models since no sharp oscillation happens. Comparing the learning curves on the training and validation set, we can find that on the COLORS dataset, the curves converge to around the same loss and rewards on the training and validation set when the training converges. Hence, reward generation model and the augmentation model both have very good generalization abilities. Differently, on more complicated TRIANGLES dataset, slight overfitting exists for both models but the overall generalization ability is still acceptable. Actually, to eliminatee the negative effect of overfitting, we always take the reward generation model with lowest validation loss and the augmentation model with highest validation reward in experiments. In word, our studies about training stability and generalization show that both the reward generation model and augmentation model can be trained stably and have acceptable generalization ability.
23

---

Published as a conference paper at ICLR 2023
Table 8: The testing accuracy on the COLORS and TRIANGLES datasets with the GIN model. We report the average accuracy and standard deviation over ten runs on fixed train/validation/lest splits.
No augmentation
MaskNF with GT
DropNode with GT
PerturbEdge with GT
Dataset
GraphAug
COLORS
0.578:10.012
0.627+0.013 n/a
0.627-00017 0.522=0.007
n/a 0.524
0.633:10.009
TRIANGLES
0.506:10.006
0.003
F.2 ADVERSARIAL TRAINING EXPERIMENT
One possible one-stage training alternative of GraphAug is the adversarial training strategy in Ratner et al. (2017b). Specifically, the augmentation model is trained jointly with the reward generation model. We construct the positive graph pair (G, G+) sampled from the dataset in which G and G+ have the same label, and use the augmentation model to augment the graph G' to G- and form the negative graph pair (G,G-) The reward generation model is then trained to minimize the loss function L = log sGG - log (1 s(G, G))), but the augmentation model is trained to maximize the reward log sG, G received from the reward generation model. In this adversarial training method, the reward generation model can actually be considered as the discriminator model. We conduct an exploration experiment of it on the COLORS and TRIANGLES datasets, but we find that this strategy cannot work well on both datasets. On the TRIANGLES dataset, gradient explosion consistently happens during the training but we have not yet figure out how to fix it. On the COLORS dataset, we show the learning curves of two models in Figure 6 Note that different from the learning curves of GraphAug in Figure 2 the augmentation model diverges and fails to learn to obtain more rewards as the training proceeds. In other words, the augmentation model struggles to learn to generate new graphs that can deceive the reward generation model. Given these existing problems in adversarial learning, we adopts the two-stage training pipeline GraphAug and leaves the problem of simplifying the training to the future.
F.3 COMPARISON WITH MANUALLY DESIGNED LABEL- AUGMENTATIONS
An interesting question is how does our GraphAug compare with the manually designed label- invariant augmentation methods (assuming we can design them from some domain knowledge)? We try answering this question by empirical studies on COLORS and TRIANGLES datasets. Since we explicitly know how the labels of graphs are obtained from their data generation codes, we can design some label-invariant augmentation strategies. We compare Graph/ug with three designed label-invariant augmentation methods, which are based on MaskNI, DropNode, and PerturbEdge transformations intentionally avoiding damaging label-related information. Specifically, for the COLORS dataset, compare with MaskNF that uniformly masks the node features other than the color feature, and DropNode that uniformly drops the nodes other than green nodes. In other words, they are exactly using the ground truth labels indicating which graph elements are label-related in- formation, so we call them as MaskNF with GT and DropNode with GT. Note that no PerturbEdge with GT is defined on the COLORS dataset because the modification of edges naturally ensures -abel-invariance. Similarly, for the TRIANGLES dataset, we compare with DropNode with GT and PerturbEdge with GT which intentionally avoid damaging any nodes or edges in triangles.
The performance of no augmentation baseline, three manually designed augmentation methods, and our GraphAug method is summarized in Table 8 It is not surprising that all augmentation meth- ods can outperform no augmentation bascline since they all can produce label-invariant training samples. Interestingly, GraphAug is competitive method compared with these manually designed label-invariant methods. GraphAug outperforms manually designed augmentations on the COLORS dataset but fails to do it on the TRIANGLES dataset. We find that is because GraphAug model se- lects M with higher chances than DropNode and PerturbEdge, but graph classification models benefits more from diverse topology structures produced by DropNode and PerturbEdge transforma- tions. Note that although our GraphAug may not show significant advantages over manually designed invariant augmentations on these two synthetic datasets, in most scenarios, de- signing such label-invariant augmentations is impossible because we do not know which graph
24

---

Published as a conference paper at ICLR 2023
Table 9: The performance on seven benchmark datasets with the GCN model. We report the aver- age ROC-AUC and standard deviation over ten runs for the ogbg-molhiv dataset, and the average accuracy and standard deviations over three 10-fold cross-validation runs for the other datasets.
Mathod
PROTEINS
IMDB BINARY
COLLAB
MUTAG
NC1109
NC11
oghg-molhiv
augmentation
0.711=00003
0.73420.010
0.797=0.002
0.80340.016
0.742:20.044
0.7314:.0002
0.761=00010
Uniform MaskNF
0.716:10.001
0.723:0.006
0.802=0.002
0.76510.017
0.73410.005
0.729:0.004
0.745:100011
Uniform DropNode
0.714+0.005
0.703++0.001
0.798=0.002
0.709
0.727=0.003
0.722++0000
0.723++0.012
Uniform PetturEEdge
0.69440.003
0.732-0.0100
0.795=0.003
0.7441:0.004
0.634=0.006
0.638::0011
0.746:10013
Uniform Mixture
0.714100003
0.734100.099
0.797=0.004
0.754:10.015
0.731=0.002
0.722::0002
0.743:10.011
DropEdge
0.710=20.006
0.735=0.013
0.797=0.004
0,762++0.00
0.724=0.004
0,723+00003
0.757=00012
M-Mixup
0.71440.004
0.728=0.0077
0.794=0.003
0.783+0.007
0.739=0.005
0.741+00002
0.753=0.014
G-Mixup
0.72411.0006
0.749=000010
0.800=0.027
0.799110.044
0.509=0.005
0.50610.000
0.763:10.008
FLAG
0.723+0.003
0.743=0.008
0.797=0.002
0.819:0.0044
0.746=0.003
0.73410.004
0.768:10.010
JOAOv2
0.722:10.003
0.687:10.010
0.681
0.736:10.007
0.691=0.007
0.6724:.004
0.722:100099
AD-GCL
0.691400.11
0.697+-0011
0.612-0.004
0.665++0.001
0.634+0.003
0.641+00004
0.752+00013
AutoGCL
0.668:20.008
0.719:00002
0.745=0.002
0,769-00022
0.707=00002
0.71440.005
0.701=10014
GraphAug
0.736:10.007
0.76411.008
0.808=0.001
0.832:10.005
0.760=0.003
0.748:
0.774:10.010
Table 10: Average augmentation time per graph with the trained augmentation model.
Method
PROTEINS IMDB-BINARY COLLAB MUTAG NC1109 NCII
ogbg-molhiv
JOAOv2
0.0323s
0.0854s
0.2846s
0.0397s
0.0208s
0.0223s
0.0299s
AD-GCL
0.0127s
0,0418s
0.1478s
0.0169s
0.0092s
0.0083s
0.0115s
AutoGCL
0.0218s
0.0643s
0.2398s
0.0256s
0.0162s
0.0168s
0.0221s
GraphAug
0.0073s
0.0339s
0.1097s
0.0136s
0.0075s
0.0078s
0.0106s
elements are label-related. However, our GraphAug can still work in these scenarios because it can automatically learn to produce label-invariant augmentations.
F.4 MORE EXPERIMENTAL RESULTS ON GRAPH BENCHMARK DATASETS
The performance of different augmentation methods on all seven datasets with the GCN model is presented in Table 9 Besides, to quantify and compare the computational cost of our method and some automated graph augmentation baseline methods on each dataset, we test the average time they use to augment each graph and summarize the average augmentation time results in Table 10) For most dataset, our method only takes very small amount of time (<. 0.05s) to augment graph in average, which is an acceptable time cost for most real-world applications. In addition, from Table TO we can clearly find that among all automated graph augmentation methods, our GraphAug takes the least average runtime to augment graphs. For the other baseline methods in Table 2 because they do not need the computation with neural networks in augmentations, their runtime is unsurprisingly lower (< 0.001s per graph). However, the classification performance of them consistently worse than GraphAug- Overall, GraphAug achieves the best classification performance, and its time cost is the lowest among all automated graph augmentations.
F.5 MORE ABLATION STUDIES
Ablation on combining three diffeerent transformations. In our method, we use combination of three different graph transformations, including MaskNF, DropNode, and PerturbEdge. Our GraphAug model are designed to automatically select one of them at each augmentation step. Here we explore how the performance will change if only one category of graph transformation is used. Specifically, we compare with three variants of GraphAug that only uses learnable MaskNI, DropN- ode, and PerturbEdge, whose performance are listed in the first three rows of Table IT We can find that sometimes using certain category of learnable augmentation gives very good results, e.g., learnable DropNode on the NCII dataset. However, not all categories can achieve it, and actually the optimal category varies among datasets because graph structure distributions modalities are very
25

---

Published as a conference paper at ICLR 2023
Table 11: Results of ablation studies ahout combining three different transformations. We report the average accuracy and standard deviation over three 10-fold cross-validation runs with the GIN model.
Method
PROTEINS
IMDB-BINARY
NCI1
GraphAug with only learnable MaskNF transformation
0.712:10.001
0.751110.00
0.80910.002
Graph Aug with only learnable DropNode transformation
0.716++00003
0.752++0.005
0.814+0.0002
Arg with only learnable PerturbEdge transformation GraphAug
0.702:+0.009
0.754+10.005
0.780=+00001
0.722:10.004
0.762:10.004
0.816:10.001
Table 12: Results of ablation studies about using virtual nodes. We report the average accuracy and standard deviation over three 10-fold cross-validation runs with the GIN model.
Method
PROTEINS
IMDB-BINARY
NCI1
GraphAug with sum pooling
0.711
0.750=#0.008
0.788=0.004
GraphAug with mean pooling
0.711=0.004
0.752:#0.004
0.801=0.005
GraphAug with max pooling GraphAug with virtual nodes
0.713-+0.002
0.737++0.005
0.795++0.005
0.722-+0.004
0.762+00.004
0.816 0.001
Table 13: The label-invariance ratios the sets of COLORS and TRIANGLES datasets.
Uniform MaskNF
Uniform DropNode
Uniform PerturbEdge
Uniform Mixture
Dataset
GraphAug
COLORS
0.3547
0.3560 0.6674
1.0000 0.1957
0.5645
0.9994
TRIANGLES
1.0000
0.6181
1.0000
different in different datasets. Nonetheless, GraphAug consistently achieve good performance without manually searching the optimal category on different datasets. Hence, combining different transformations makes it easier for the GraphAug model adapt to different graph datasets than using only one category of transformation.
Ablation on using virtual nodes. In our method, virtual nodes are used to capture graph-level representation and predict augmentation categories due to two advantages. (1) First, in the message passing process of GNNs, virtual nodes can help propagate messages among far-away nodes in the graph. (2) Second, virtual nodes can learn to more effectively capture graph-level representations through aggregating more information from important nodes or structures in the graph (similar to the attention mechanism). In fact, many prior studies (Gilmer et al., 2017; Hu al. 2020) have demonstrated the advantages of using virtual nodes in graph representation learning. To justify the advantages of using virtual nodes in GraphAug, ways to predict the augmentation category in an ablation experiment. Specifically, we evaluate the performance of GraphAug model variants in which virtual nodes not used, but the augmentation category is predicted from the graph-level representations obtained by sum pooling, mean pooling, or max pooling. The results of them are summarized in the first three rows of Table I2 From the results, we can find that using virtual nodes achieves the best performance, hence it is the best option.
compare the performance of taking different
F.6 EVALUATION OF LABEL-INVARIANCE PROPERTY
We evaluate the label-invariance ratios of our GraphAug method and the baseline methods used in Table [ on the test sets of two synthetic datasets. The results are summarized in Table [3 Since the label is defined as the number of nodes with green colors (indicated by node features) in the COLORS dataset, Uniform DropNode and Uniform PerturbEdge will destroy label-related informa- tion and achieve very low -abel-invariance ratio. Similarly, the label is defined as the number of 3-cycles in the TRIANGLES dataset, Uniform DropNode and Uniform PerturbEdge also achieve
26

---

Published as a conference paper at ICLR 2023
very low label-invariance ratio. However, our GraphAug achieve very high label-invariance ratio of close to 1.0 on both datasets. Besides, combining with the classification performance in Table [I] we can find that only the augmentations with high label-invariance ratios can outperform no augmentation baseline. This phenomenon demonstrates that label-invariance is significant to achieve effective graph augmentations.
27


Reviews:
[{"review_id": "wErQWwVBlj", "reviewer": "Reviewer_jQkA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed a reinforcement learning based approach for automatically predicting graph augmentations for a graph neural network (GNN) classification problem. The authors argue that label invariance (data augmentations that do not affect labels) is an important, unsolved problem for GNN, and propose a technique to maximize this property. Previous automatic graph augmentation methods did not consider labels, while the proposed method does. Experimental results demonstrate a marked improvement in classification accuracy on several benchmark datasets.\n", "summary_of_the_review": "Overall, the paper should be a strong contribution to the conference. However, evaluation of the key component of the paper (label invariance) is missing. If the authors are able to address this concern, I will increase my rating.\n\nEDIT: after reading through author rebuttals and other reviews, my concerns have been addressed and I increased my rating.", "strength_and_weaknesses": "The paper highlights and addresses an important problem in graph classification: how to perturb data without affecting label information. To address this problem, a reinforcement learning approach is proposed and extensive experiments demonstrate the utility of the technique. The paper is very well-written and easy to understand. Summary of related work is also extensive.\n\nThe key weakness is the lack of evaluation of the label invariance property. It’s not clear how often does the reinforcement learning method generate graphs that retain the same labels. Since this property is key to the motivation of the paper, I would like to see an analysis of how it is maintained.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mQHN8CGotv", "reviewer": "Reviewer_iXAY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper worked on data augmentation for graph classification, and proposed an automated method that learns label-invariant augmentations. \n\nIt formulates the graph augmentation problem as a sequential decision-making task (Markov Decision Process), where at each time step one augmentation method is picked given the current graph and transformed graph (as well as the reward). The model is optimized using policy gradient (i.e., REINFORCE) algorithm and the reward is generated using the graph matching network to predict the probability that the current graph and the transformed graph have the same label (so as to ensure label-invariant property). Experiments on both synthetic datasets and real-world benchmarks verify the effectiveness of the proposed method.", "summary_of_the_review": "Based on my previous comments, I recommend acceptance. ", "strength_and_weaknesses": "S1. This paper is overall well-written and easy to follow. \n\nS2. Extensive experiments on multiple datasets with SOTA baselines validates the effectiveness of the proposed method.\n\nS3. The proposed label-invariant augmentations seems very interesting.\n\nW1. I appreciate the complexity analysis in the appendix. It would be nice to also have runtime comparison with baselines to further validate the efficiency of the proposed method.\n\nW2. In Table 2, sometimes the mixture augmentation would underperform some of the single augmentations. I wonder if the authors have conducted sufficient hyperparameter search for it.\n\nW3. On the larger datasets such as the OGB one, the performance improvements over simple augmentations are not very big. In that case, I wonder if adding the much more complex RL framework would worth the trade-off on time and resource.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "JIk60GZCOZt", "reviewer": "Reviewer_2d1h", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes GraphAug, a new automated graph augmentation method. The method selects augmentation operation and ratio, considering the label-invariance of the operation. The experimental results show that the proposed method improves accuracy on various graph classification tasks, compared to the baseline methods.\n", "summary_of_the_review": "In summary, the paper studied a significant aspect of automated graph augmentation tasks, and the proposed method is based on intuitive and solid ideas. Although the idea of label-invariant augmentation exists in prior works, the design and the implementation of the model can be appreciated. Also, empirical results support its flexibility and superiority.\n\np.s.\nReference of GCA:\nYanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. 2021. Graph Contrastive Learning with Adaptive Augmentation. In Proceedings of the Web Conference 2021 (WWW '21), April 19–23, 2021, Ljubljana, Slovenia. ACM, New York, NY, USA 12 Pages.\nhttps://dl.acm.org/doi/fullHtml/10.1145/3442381.3449802", "strength_and_weaknesses": "[Strength]\n1. This paper studies a practical problem.\n2. The main idea of the method is simple and intuitive.\n3. The method achieves superior performance on various datasets for different classification tasks.\n4. The overall presentation is good.\n[Weakness]\n1.   There are some missing prior works. For example, GCA [Zhu and Xu et al. WWW’21] proposed an adaptive graph augmentation for graph contrastive learning. Although it does not use “label-invariance” explicitly, it aims to keep important structures and attributes unchanged.\n2.   The justifications for the reward generation network do not seem sufficient. The proposed method uses the reward generation network to generate the reward. However, in prior RL-based augmentation methods, the accuracy of the child network is given as the reward. So I think there should be justifications for the design decision of the network.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster