# Graph Data Augmentation for Graph Machine Learning: A Survey

Tong Zhao1111Contact Author Gang Liu1 Stephan Günnemann2&Meng Jiang1
1University of Notre Dame, USA
2Technical University of Munich, Germany
{tzhao2, gliu7<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Data augmentation has recently seen increased interest in graph machine
learning given its ability of creating extra training data and improving model
generalization. Despite this recent upsurge, this area is still relatively
underexplored, due to the challenges brought by complex, non-Euclidean
structure of graph data, which limits the direct analogizing of traditional
augmentation operations on other types of data. In this paper, we present a
comprehensive and systematic survey of graph data augmentation that summarizes
the literature in a structured manner. We first categorize graph data
augmentation operations based on the components of graph data they modify or
create. Next, we introduce recent advances in graph data augmentation,
separating by their learning objectives and methodologies. We conclude by
outlining currently unsolved challenges as well as directions for future
research. Overall, this paper aims to clarify the landscape of existing
literature in graph data augmentation and motivate additional work in this
area. We provide a GitHub repository222https://github.com/zhao-tong/graph-
data-augmentation-papers with a reading list that will be continuously
updated.

##  1 Introduction

Data driven inference has received a significant boost in generalization
capability and performance improvement in recent years from data augmentation
(DA) techniques. The DA techniques increase the amount of training data by
creating plausible variations of existing data without additional ground-truth
labels, and have seen widespread adoption in fields such as computer vision
(CV) Cubuk et al. (2019) and natural language processing (NLP) Feng et al.
(2021). These techniques allow inference engines to learn to generalize across
those variations and attend to signal over noise.

In recent years, with the rapid development of graph machine learning (GML)
methods such as graph neural networks (GNNs) Kipf and Welling (2016); Hamilton
et al. (2017), there has been increased interest and demand for data
augmentation techniques on graph data Zhao et al. (2021b). Due to the
irregular and non-Euclidean structure of graph data, graph data augmentation
(GDA) techniques could hardly be directly analogized from the DA techniques
used in CV and NLP. Moreover, GML faces unique challenges such as feature data
incompleteness, structural data sparsity brought by power-law distributions,
lack of labelled data due to costly annotations, and over-smoothing caused by
message passing in GNNs. To address these challenges, there has been a growing
number of works on GDA. GML researchers design graph-specific augmentation
techniques for these unique challenges on graphs. On graph-level tasks, GDA
techniques aim at generating extra data for training with known labels from
the input training data to improve generalization. On node-level tasks, GDA
techniques have enhanced GML models from a variety of perspectives. For
example, Rong et al. (2019) randomly removes edges during training to
alleviate the over-smoothing problem. Zhao et al. (2021b) enhanced graph
structure to promote graph homophily. Kong et al. (2020) modified or added
node attributes via adversarial training.

This paper aims to sensitize the GML community towards this growing area of
work, when data augmentation has already drawn much attention in CV and NLP.
As interest and work on this topic continue to increase, this is an opportune
time for a paper of our kind to (i) give a bird’s eye view of existing GDA
techniques, and (ii) identify key challenges to effectively motivate and
orient interest in this area. To the best of our knowledge, this is the first
comprehensive survey on the topic of graph data augmentation. We hope this
survey can serve as a guide for researchers and practitioners who are new to
or interested in studying this topic.

This paper is structured as follows. Section 2 gives background on GNNs and
data augmentation. It categorizes GDA techniques based on their modified
components of graph data. Section 3 describes GDA techniques for
(semi-)supervised GML – which we separate by the task levels: node-level tasks
(Section 3.1), graph-level tasks (Section 3.2), and edge-level tasks (Section
3.3). Section 4 introduces GDA techniques that are used with self-supervised
learning objectives, i.e., contrastive learning (Section 4.1) and consistency
learning (Section 4.2). Within these subsections, we introduce the GDA
techniques grouping by their methodologies. Finally, Section 5 discusses
challenges and future directions for GDA.

##  2 Background

###  2.1 Graph Neural Networks

Graph neural networks (GNNs) enjoy widespread use in modern graph-based
machine learning due to their flexibility to incorporate node features, custom
aggregations, and inductive operation, unlike earlier works which were based
on embedding lookups Perozzi et al. (2014); Grover and Leskovec (2016).
Following the initial idea of convolution based on spectral graph theory Bruna
et al. (2013), many spectral GNNs have since been developed and improved by
Defferrard et al. (2016); Kipf and Welling (2016); Levie et al. (2018);
Klicpera et al. (2018); Ma et al. (2021). As spectral GNNs generally operate
(expensively) on the full adjacency, spatial-based methods which perform graph
convolution with neighborhood aggregation became prominent Hamilton et al.
(2017); Veličković et al. (2017); Xu et al. (2018), owing to their scalability
and flexibility Ying et al. (2018).

###  2.2 Data Augmentation

Data augmentation (DA) encompasses techniques of increasing/generating
training data without directly collecting or labeling more data. Most DA
techniques either add slightly modified copies of existing data or generate
synthetic based on existing data. The augmented data act as a regularizer and
reduce overfitting when training data-driven models Shorten and Khoshgoftaar
(2019). DA techniques has been commonly used in CV and NLP Feng et al. (2021),
where augmentation operations such as cropping, flipping, and backtranslation
are commonly used in machine learning model training. In graph machine
learning, in contrast to regular data such as grids (e.g., images) and
sequences (e.g., sentences), the graph structure is encoded by node
connectivity, which is non-Euclidean and irregular. Most structured
augmentation operations used frequently in CV and NLP cannot be easily
analogized to graph data. Therefore, how to generate effective augmented data
examples on graph data is less obvious.

###  2.3 Graph Data Augmentation

Similar to DA techniques for CV and NLP, GDA creates data objects via
modification or generation. However, as graphs are connected data, unlike
images or texts, the data objects in graph machine learning are often
non-i.i.d. Hence, for node-level and edge-level tasks, GDA techniques modify
the entire dataset (graph) instead of some data objects (nodes or edges).
Based on the graph data components that are modified or created, we define
four categories of GDA operations as follows.

#### Node Augmentations

are the GDA operations that create or remove nodes from the graph. For
example, Mixup-based methods Wang et al. (2021b) created new nodes by
combining two existing nodes. Feng et al. (2020) proposed the DropNode
operation that removed nodes by masking of the features of selected nodes.

#### Edge Augmentations

are the GDA operations that modify the graph connectivity via adding/removing
edges. The modifications can be either deterministic (e.g., GDC Klicpera et
al. (2019) and GAug-M Zhao et al. (2021b) both modified the graph structure
and used the modifed graph for training/inferencing) or stochastic (e.g., Rong
et al. (2019) proposed to randomly drop edges during each training epoch).

#### Feature Augmentations

are the GDA operations that modify or create raw node features. For example,
You et al. (2020) used Attribute Masking that randomly masked off node
features; FLAG Kong et al. (2020) augmented node features with gradient-based
adversarial perturbations.

#### Subgraph Augmentation

refers to the GDA operations that operate at the graph level, such as cropping
out subgraphs or creating new graphs. As the subgraph augmentation operations
usually affect multiple nodes in the subgraph, they are mostly used for graph
level tasks. For example, JOAO You et al. (2021) used subgraph cropping;
ifMixup Guo and Mao (2021) created new graphs by mixing up two graphs.

##  3 Graph Data Augmentation Techniques for Supervised Learning

Table 1: A summary of graph data augmentation techniques for graph machine
learning. Task levels: V: node-level; G: graph-level; E: edge-level. Augmented
data categories: V: node; E: edge; X: feature; G: subgraph.
†Although GRAND and NodeAug are semi-supervised methods, they used GDA
operations with only self-supervised learning objectives (i.e, consistency
loss). Therefore, we categorize their GDA techniques as designed for self-
supervised learning objectives.

Task Level Augmented Data Augmentation Methodology V G E V E X G GDA for
Supervised Objective DropEdge Rong et al. (2019) ✓ ✓ Edge dropping
NeuralSparse Zheng et al. (2020) ✓ ✓ TADropEdge Gao et al. (2021) ✓ ✓ FairDrop
Spinelli et al. (2021) ✓ ✓ GDC Klicpera et al. (2019) ✓ ✓ Graph diffusion MV-
GCN Yuan et al. (2021) ✓ ✓ AdaEdge Chen et al. (2020) ✓ ✓ Structure prediction
Pro-GNN Jin et al. (2020) ✓ ✓ GAug-M Zhao et al. (2021b) ✓ ✓ GAug-O Zhao et
al. (2021b) ✓ ✓ Eland Zhao et al. (2021c) ✓ ✓ MH-Aug Park et al. (2021) ✓ ✓
FLAG Kong et al. (2020) ✓ ✓ ✓ ✓ Feature generation LA-GNN Liu et al. (2021) ✓
✓ SR+DR Song et al. (2021) ✓ ✓ AutoGRL Sun et al. (2021a) ✓ ✓ ✓ ✓ AutoML
GraphMix Verma et al. (2019) ✓ ✓ Mixup Graph Mixup Wang et al. (2021b) ✓ ✓ ✓ ✓
ifMixup Guo and Mao (2021) ✓ ✓ Graph Transparent Park et al. (2022) ✓ ✓
GraphCrop Wang et al. (2020a) ✓ ✓ Subgraph cropping MoCL Sun et al. (2021b) ✓
✓ Substructure substitution M-Evolve Zhou et al. (2020) ✓ ✓ Motif-similarity
mapping CFLP Zhao et al. (2021a) ✓ ✓ Counterfactual augmentation MeTA Wang et
al. (2021a) ✓ Edge perturbation GDA for Self-supervised Objective DGI
Velickovic et al. (2019) ✓ ✓ Corruption GraphCL You et al. (2020) ✓ ✓ ✓ ✓ ✓
GRACE Zhu et al. (2020) ✓ ✓ ✓ SUBG-CON Jiao et al. (2020) ✓ ✓ InfoGCL Xu et
al. (2021) ✓ ✓ ✓ ✓ BGRL Thakoor et al. (2022) ✓ ✓ ✓ GRAND† Feng et al. (2020)
✓ ✓ ✓ MVGRL Hassani and Khasahmadi (2020) ✓ ✓ Graph diffusion MV-CGC Yuan et
al. (2021) ✓ ✓ JOAO You et al. (2021) ✓ ✓ ✓ ✓ ✓ Automated augmentation GCA Zhu
et al. (2021) ✓ ✓ ✓ LG2AR Hassani and Khasahmadi (2022) ✓ ✓ ✓ ✓ ✓ FairAug Kose
and Shen (2022) ✓ ✓ ✓ ✓ AD-GCL Suresh et al. (2021) ✓ ✓ NodeAug† Wang et al.
(2020b) ✓ ✓ ✓ Biased perturbation

In this section, we discuss GDA techniques that are used for supervised graph
learning. We categorize the GDA techniques by their task levels (node, graph,
or edge).

###  3.1 Node-level Tasks

#### Edge Dropping

Edge dropping methods stochastically remove a certain amount of edges from the
graph data during each training epoch. Rong et al. (2019) first proposed
DropEdge which randomly dropped a fixed fraction of edges in each epoch, in a
way similar to Dropout. By showing the GNN model different part of the graph
in each training epoch, DropEdge significantly improved the model’s
generalization and alleviates the over-smoothing problems of GNNs, especially
for deeper GNNs. Although DropEdge efficiently augmented the edges, it is
often criticized for also removing task-relevant signals and corrupting
informative graph structures.

Following DropEdge, Zheng et al. (2020) proposed NeuralSparse that utilized a
MLP-based graph sparsification model that learned to remove only the
potentially task-irrelevant edges. The graph sparsification model is
supervised and trained jointly with GNN on the node classification loss.
PTDNet Luo et al. (2021) further applied the nuclear norm regularization loss
to impose the low-rank constraint on the modified graph by the graph
sparsification model. Gao et al. (2021) proposed TADropEdge that leveraged the
graph spectrum to generate edge weights that represent the edges’ criticality
for the graph connectivity. TADropEdge dropped the edges using the edges
weights as the probabilities.

Other than node classification, Spinelli et al. (2021) proposed FairDrop for
the task of fair graph representation learning, which biasedly dropped edges
with a sensitive attribute homophily mask to protect against unfairness.

#### Graph Diffusion

Klicpera et al. (2019) first proposed generalized graph diffusion that modeled
a “future” state of the graph where the signals were more spread out. By
utilizing commonly used graph diffusion such as personalized PageRank (PPR) or
heat kernal along with graph sparsification, GDC Klicpera et al. (2019)
generates a diffused version of the observed graph. The generated graph is
then used for both training and inferencing. While message passing-based GNNs
are only capable of aggregating one hop information in each layer, GDC allows
GNNs to learn from multi-hop information without specifically re-designing the
model.

To further utilize the information given by different graph diffusions, MV-GCN
Yuan et al. (2021) generates two complementary views with PPR and heat kernal
and learns from both created views and the original graph. MV-GCN uses a
consistency regularization loss to reduce the distribution distance of the
representations learned from the three views.

#### Structure Prediction

Prediction-based GDA techniques update the graph structure to enhance task-
relevant information in the graph. For example, Zhao et al. (2021b) showed the
correlation between graph structural homophily and node classification
performance. Then they proposed GAug-M and GAug-O to update the graph
structure by neural link predictors. Similar to GDC Klicpera et al. (2019),
GAug-M deterministically modifies the graph structure and use the updated
graph for training and inferencing. To allow inductive learning on graphs,
GAug-O samples graph structure from learned probabilities in each training
epoch. Chen et al. (2020) also proposed AdaEdge that iteratively add/remove
edges according to the node classification prediction. In each iteration,
AdaEdge adds edges between nodes that are predicted to be in the same class
with high confidence, and vice versa. Pro-GNN Jin et al. (2020) updates the
graph structure with constrains on the low-rank property and feature
smoothness.

MH-Aug Park et al. (2021) creates an “explicit” target distribution, with
controlled strength and diversity, to sample augmented graphs. As sampling
from the complex target distribution is infeasible, MH-Aug adopts the
Metropolis-Hastings algorithm to obtain the augmented samples.

Zhao et al. (2021c) proposed Eland for the task of anomaly detection on time-
stamped user-item bipartite graphs. Eland first transforms the user-item graph
into users’ action sequences and adopts seq2seq model for future action
prediction. The predicted user actions are added back into the graph to
generate the augmented graph data. As the augmented graph contains richer user
behavior information, Eland enhances the anomaly detection performance and
detects anomalies at an early stage.

#### Feature Augmentation

For (semi-)supervised graph learning, feature augmentation methods usually try
to improve the node feature quality by learning additional task-relevant
features. FLAG Kong et al. (2020) utilizes adversarial training to iteratively
augment the node features with gradient-based adversarial perturbations. Being
a free training approach, FLAG improves the performances of GNNs on the tasks
of node classification, link prediction, and graph classification. LA-GNN Liu
et al. (2021) enhances the locality of node representations by generating
additional node features based on the conditional distribution of local
neighborhoods. The generated feature is directly used together with the raw
node features. Similarly, SR+DR Song et al. (2021) generates topology features
with DeepWalk Perozzi et al. (2014), and uses a dual GNN model with topology
regularization to jointly train with both raw and topology features.

#### Mixup

Mixup Zhang et al. (2018) merges two images to generate a new images with a
weighted label. Given the dependent and non-Euclidean structure of graph, the
direct analog of Mixup on graph data is not obvious. Verma et al. (2019)
proposed GraphMix that augmented the training of a GNNs with a Fully-Connected
Network. As GraphMix is more of a regularization method than the analog of
Mixup on graphs, Wang et al. (2021b) proposed Graph Mixup, which analogized
Mixup with a two-branch graph convolution module. Given a pair of nodes, Graph
Mixup mixes the raw features of them, feeds the them into the two-branch GNN
layer, and mixes their hidden representations of each layer. Mixing up the
nodes on features and hidden states avoids re-assembling the local
neighborhoods of the two nodes.

#### AutoML

With the rapid development of AutoML, automated graph learning method were
proposed to automate the design of GNN architecture as well as the choice of
GDA operations. Sun et al. (2021a) proposed AutoGRL for the task of node
classification. Though training process, AutoGRL learns the best combination
of GDA operations, GNN architecture, and hyperparameters. The searching space
of AutoGRL includes four GDA operations implemented by random masking and
GAug-M Zhao et al. (2021b): drop features, drop nodes, add edges, and remove
edges.

###  3.2 Graph-level Tasks

For graph-level tasks, where data objects are independent graphs, certain
augmentation operations in CV and NLP can be transferred to graph data. For
example, similar to image cropping, GraphCrop Wang et al. (2020a) crops a
contiguous subgraph from each of the given graph object. GraphCrop adopts a
graph diffusion-based node-centric strategy to maintain the topology
characteristics of original graphs.

M-Evolve Zhou et al. (2020) utilizes motifs to augment the graph data.
M-Evolve first finds and selects the target motif in the graph, then adds or
removes edges within the selected motifs based on a sampling weight calculated
with Resource Allocation index. Similarly, MoCL Sun et al. (2021b) utilizes
biomedical domain knowledge to augment the molecular graphs on the
substructures such as functional groups. MoCL selects a substructure from each
molecular graph and replaces it with another substructure.

#### Mixup

Several Mixup methods were also proposed for graph classification. For
example, the aforementioned Graph Mixup Wang et al. (2021b) also works for
graph classification. Graph Mixup mixes the latent representations of the pair
of graphs. On the other hand, ifMixup Guo and Mao (2021) directly applies
Mixup on the graph data instead of the latent space. As the pair of graphs are
irregular and the nodes from two graphs are not aligned, ifMixup arbitrarily
assigns indices to the nodes in each graph and matches the nodes according to
the indices. Following ifMixup, Graph Transparent Park et al. (2022) also
mixes graph in data space. Unlike ifMixup that randomly matches nodes during
mixing, Graph Transparent uses substructures as mixing units to preserve the
local structural information. Graph Transparent employs the node saliency
information to select one meaningful substructure from each graph, where the
saliency information is defines as the $l_{2}$ norm of the gradient of the
classification loss.

###  3.3 Edge-level Tasks

We note that very few GDA techniques were proposed for edge level tasks such
as link prediction. Zhao et al. (2021a) proposed a counterfactual data
augmentation method CFLP. CFLP asks the counterfactual question of “would the
link still exist if the graph structure became different from observation?” To
answer the question, Zhao et al. (2021a) proposed counterfactual links that
approximates the unobserved outcome in the question. CFLP trains the link
prediction model with both the given training data and the generated
counterfactual links (as augmented data).

Wang et al. (2021a) proposed MeTA for link prediction on temporal graphs. MeTA
contains a multi-level module that processes the augmented graphs of different
magnitudes on separate levels. MeTA adopted three augmentation operations for
the temporal graphs: perturb time that modifies the time-stamp on edges,
remove edge that is similar to DropEdge Rong et al. (2019), and add edges that
repeats existing edges with a different time-stamp. During training and
prediction, MeTA performs message passing across levels to provide adaptively
augmented input graphs.

##  4 Graph Data Augmentation Techniques for Self-supervised Learning
Objectives

In this section, we cover the GDA techniques that are used for self-supervised
learning objectives, i.e., contrastive learning and consistency learning.
Self-supervised objectives learn representations that are robust to noise and
perturbations by maximizing the (dis)agreements of learned representations.
Therefore, unlike the above presented GDA techniques that aim to enhance the
task-relevant information in the data, most of the GDA techniques for self-
supervised learning are stochastic augmentations that aims to corrupt the
given graph data. Moreover, most self-supervised graph representation learning
methods tend to use a combination of several simple GDA operations.

###  4.1 Contrastive Learning

In the past few years, with the rapid development of contrastive learning,
several graph contrastive learning methods You et al. (2021) have been
proposed. Contrastive learning aims to maximize the distance between
representations of different objects and minimize the distance between
representations learned from different views of the same object. Data
augmentation is commonly used for generating the different views for
contrastive learning.

#### Corruption

To efficiently generate different augmented data for graph contrastive
learning, the most commonly used GDA operations are the corruption-based ones.
For example, DGI Velickovic et al. (2019) adopts feature corruption where it
conducts a row-wise shuffling on the raw node feature matrix $\mathbf{X}$. The
feature corruption by DGI can also be viewed as randomly swapping the nodes in
the graph.

GraphCL You et al. (2020) and InfoGCL Xu et al. (2021) adopt four GDA
operations: node dropping that randomly removes nodes along with its edges,
edge perturbation that randomly adds or drops edges, attribute masking that
randomly masks off certain node attributes, and subgraph sampling that samples
a connected subgraph. Similar to the subgraph sampling operation used in
GraphCL, SUBG-CON Jiao et al. (2020) utilizes a subgraph sampler to sample the
augmented subgraph. GRACE Zhu et al. (2020) and BGRL Thakoor et al. (2022) use
only the basic random edge dropping and attribute masking for creating
different views of the graph.

#### Graph diffusion

As an efficient GDA operation that can naturally creates a “future view” of
the given graph, graph diffusion is used in graph contrastive learning. MVGRL
Hassani and Khasahmadi (2020) adopts the diffusion graph proposed by GDC
Klicpera et al. (2019) as the second view. Interestingly, Hassani and
Khasahmadi (2020) showed that using three views (original graph, diffusion
graphs by PPR and heat kernal) would not result with better performance than
using two views (original graph and one diffusion graph), and concluded
“increasing the number of views does not improve the performance.” However,
Yuan et al. (2021) later proposed MV-CGC that adopted a similar contrastive
learning framework with three views: original graph, diffusion graph, and
their proposed feature similarity view. Empirically, the node representations
learned by MV-CGC outperformed those learned by MVGRL on node classification.

#### Automated GDA

As aforementioned, most contrastive learning methods adopt a combination of
several simple augmentation operations. The selection among the operations and
their magnitudes significantly increases the number of hyperparameters.
Therefore, automated solutions that can learn the augmentation strategies are
developed.

JOAO You et al. (2021) models the selection of GDA for GraphCL You et al.
(2020) as a bilevel optimization problem, where the outer level learns the
augmentation strategy and the inner level learns graph representations with
the given augmentations. AD-GCL Suresh et al. (2021) utilizes an adversarial
graph augmentation strategy to avoid redundant information brought by random
augmentation. LG2AR Hassani and Khasahmadi (2022) learns a probabilistic
policy that contains a set of distributions over different augmentation
operations, and samples augmentation strategy from the policy in each training
epoch. GCA Zhu et al. (2021) designs adaptive augmentations based on the node
centrality measures. Unlike the above-mentioned that finds the best
augmentation strategy for the dataset, the adaptive augmentation of GCA gives
different augmentation to nodes according to their importance. Similarly,
FairAug Kose and Shen (2022) utilizes adaptive augmentation for fair graph
representation learning.

###  4.2 Consistency Learning

Similar to contrastive learning, consistency learning learns representation
from different views of data and maximizes their agreement. However, unlike
contrastive learning that compares between data objects, the consistency loss
compares the distributions of a batch of representations via metrics like KL-
divergence. Therefore, the consistency loss is rarely used itself, but often
used along with supervised losses in the semi-supervised learning. For
example, NodeAug Wang et al. (2020b) uses three local structure-based
augmentation operations: replace attributes, remove edges, and add edges.
NodeAug minimizes the KL-divergence between the node representations learned
from the original graph and augmented graph. GRAND Feng et al. (2020) creates
multiple different augmented graphs with node dropping and feature masking.
The consistency loss then minimizes the distances of the representations
learned from the augmented graphs.

##  5 Challenges and Directions

###  5.1 Automation and Domain Adaptation

As GDA is a relatively new topic, many GDA techniques (as shown in Table 1)
have been proposed and used independently. However, an ideal GDA solution
would have to select and tune many data augmentation techniques prior to
deployment. This challenge has been observed in CV. For example, over ten
independent augmentation operations exist for image data Cubuk et al. (2019),
each with its own magnitude parameter. CV researchers then developed automated
augmentation solutions to adaptively customize augmentation strategies for
each (batch of) object. Although several automated augmentation solutions
exist for graph contrastive learning, automated augmentation methods for
(semi-)supervised graph learning are still needed. Moreover, the automated
augmentation solutions should be transferable. That is, domain adaptation is a
desired characteristic for automated GDA techniques. When the automated
augmentation method trained on one dataset could only be used on that dataset,
the method would just automate the hyperparameter training process and lose
the generalizability You et al. (2021). Therefore, for an ideal automated GDA
method, it should be able to be trained on one dataset and used for many,
ideally cross domain. Automated GDA methods that can be transferable across
domains are still missing.

###  5.2 Scalability for Large-Scale Graphs

Many GDA techniques used global structural information during the augmentation
process as those were hard to learn by message passing GNNs. However, learning
global information often requires the method to learn from the entire graph,
which can cause the scalability issue. The scalability issue is especially
severe for node-level tasks where the graph size can be very large. While the
complex GDA techniques bring significant performance improvements, the
scalability of the methods are still worthy of attention. For example, in
order to enable end-to-end training, GAug-O Zhao et al. (2021b) required back-
propagating on the entire adjacency matrix, resulting the extra need of memory
on GPU cards. To improve the performance of DropEdge Rong et al. (2019),
TADropEdge Gao et al. (2021) required the pre-calculation of a score for each
edge in the graph prior to the training of GNNs. Therefore, to be applicable
in real life applications, efficiency is also a necessity for GDA techniques.
As mentioned in the previous subsection, an automated solution that combines
the fast and simple augmentation operations may be solution. Nonetheless, how
to design an efficient automated GDA framework is still an open question.

###  5.3 Generalization and Regularization

On certain types of graph data such as molecule graphs, most commonly used GDA
operations would change the underlying semantic of the graph. For example,
dropping a carbon atom from the phenyl ring of aspirin breaks the aromatic
system and results in a alkene chain Lee et al. (2021), which is an entirely
different chemical compound. Therefore, domain-based regularization should be
used in such situation. So far, only Sun et al. (2021b) proposed MoCL that
considers the semantic information brought by local substructures when
augmenting the molecule graphs, leaving the domain-specific regularization for
GDA rather under-explored. Moreover, as a generalization improving technique,
GDA should be naturally good for out-of-distribution (OOD) data. GDA
techniques for OOD graph learning are still missing.

###  5.4 Theoretical Foundation

GDA is a powerful technology to improve the performance of data-driven
inference on graphs without the need of extra labeling effort or complex
models. GDA is also known for improving the generalization of graph learning
and alleviating the over-smoothing problem of GNNs. Yet, there is little
rigorous understanding of how and why GDA achieves those, especially for
(semi-)supervised learning. Although several works Zhao et al. (2021b); Chen
et al. (2020) have analyzed the relation between graph homophily and
classification performance or the over-smoothing problem, we are facing lack
of a rigorous proof or theoretical bounds on those relations.

Recently, several works provided theoretical insights of data augmentation in
CV. For example, Wu et al. (2020) theoretically analyzed the generalization
effect of data augmentation on images. They interpreted the effect of data
augmentation from bias and variance, where data augmentation adds new
information to model while also serving as a regularization. Due to the
irregular characteristics of graph data, these theoretical analysis cannot be
directly used for GDA. Other than the perspective of generalization, several
recent works have studied the certified robustness of GNNs Zügner and
Günnemann (2020). Improved robustness bounds would be a desired property of
GDA techniques. Recent studies Topping et al. (2022) on the topology
bottleneck and over-squashing of GNNs provide theoretical guides for edge-
based GDA techniques. Counterfactual augmentation methods on graphs such as
CFLP Zhao et al. (2021a) can also bring insights for analyzing GDA from the
perspective of causality.

##  6 Conclusions

In this paper, we presented a comprehensive and structured survey of data
augmentation techniques for graph machine learning. We categorized existing
GDA techniques, introduced recent GDA approaches based on their methodologies,
and outlined current challenges as well as directions for future research. We
showed that there was much room for further exploration on GDA. In conclusion,
we hope this paper serves as a guide for GML researchers and practitioners to
study and use GDA techniques, and inspire additional interest and work on this
topic.

## References

  * Bruna et al. (2013) Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral networks and locally connected networks on graphs.  In arXiv:1312.6203, 2013.
  * Chen et al. (2020) Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun.  Measuring and relieving the over-smoothing problem for graph neural networks from the topological view.  In AAAI, pages 3438–3445, 2020.
  * Cubuk et al. (2019) Ekin D Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V Le.  Autoaugment: learning augmentation strategies from data.  In CVPR, 2019.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  In NeurIPS, pages 3844–3852, 2016.
  * Feng et al. (2020) Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang.  Graph random neural networks for semi-supervised learning on graphs.  In NeurIPS, volume 33, pages 22092–22103, 2020.
  * Feng et al. (2021) Steven Y Feng, Varun Gangal, Jason Wei, Sarath Chandar, Soroush Vosoughi, Teruko Mitamura, and Eduard Hovy.  A survey of data augmentation approaches for nlp.  In arXiv:2105.03075, 2021.
  * Gao et al. (2021) Zhan Gao, Subhrajit Bhattacharya, Leiming Zhang, Rick S Blum, Alejandro Ribeiro, and Brian M Sadler.  Training robust graph neural networks with topology adaptive edge dropping.  In arXiv:2106.02892, 2021.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In KDD, pages 855–864, 2016.
  * Guo and Mao (2021) Hongyu Guo and Yongyi Mao.  ifmixup: Towards intrusion-free graph mixup for graph classification.  In arXiv:2110.09344, 2021.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In NeurIPS, pages 1024–1034, 2017.
  * Hassani and Khasahmadi (2020) Kaveh Hassani and Amir Hosein Khasahmadi.  Contrastive multi-view representation learning on graphs.  In ICML, 2020.
  * Hassani and Khasahmadi (2022) Kaveh Hassani and Amir Hosein Khasahmadi.  Learning graph augmentations to learn graph representations.  In arXiv:2201.09830, 2022.
  * Jiao et al. (2020) Yizhu Jiao, Yun Xiong, Jiawei Zhang, Yao Zhang, Tianqi Zhang, and Yangyong Zhu.  Sub-graph contrast for scalable self-supervised graph representation learning.  In ICDM, pages 222–231. IEEE, 2020.
  * Jin et al. (2020) Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang.  Graph structure learning for robust graph neural networks.  In KDD, 2020.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In arXiv:1609.02907, 2016.
  * Klicpera et al. (2018) Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  In arXiv:1810.05997, 2018.
  * Klicpera et al. (2019) Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann.  Diffusion improves graph learning.  In NeurIPS, volume 32, 2019.
  * Kong et al. (2020) 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 arXiv:2010.09891, 2020.
  * Kose and Shen (2022) O Deniz Kose and Yanning Shen.  Fair node representation learning via adaptive data augmentation.  In arXiv:2201.08549, 2022.
  * Lee et al. (2021) Namkyeong Lee, Junseok Lee, and Chanyoung Park.  Augmentation-free self-supervised learning on graphs.  In AAAI, 2021.
  * Levie et al. (2018) Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein.  Cayleynets: Graph convolutional neural networks with complex rational spectral filters.  IEEE Transactions on Signal Processing, 2018.
  * Liu et al. (2021) Songtao Liu, Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu.  Local augmentation for graph neural networks.  In arXiv:2109.03856, 2021.
  * Luo et al. (2021) Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang.  Learning to drop: Robust graph neural network via topological denoising.  In WSDM, 2021.
  * Ma et al. (2021) Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah.  A unified view on graph neural networks as graph signal denoising.  In CIKM, 2021.
  * Park et al. (2021) Hyeonjin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung-Woo Ha, and Hyunwoo J Kim.  Metropolis-hastings data augmentation for graph neural networks.  In NeurIPS, volume 34, 2021.
  * Park et al. (2022) Joonhyung Park, Hajin Shim, and Eunho Yang.  Graph transplant: Node saliency-guided graph mixup with local structure preservation.  In AAAI, 2022.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In KDD, pages 701–710, 2014.
  * Rong et al. (2019) Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang.  Dropedge: Towards deep graph convolutional networks on node classification.  In arXiv:1907.10903, 2019.
  * Shorten and Khoshgoftaar (2019) Connor Shorten and Taghi Khoshgoftaar.  A survey on image data augmentation for deep learning.  Journal of big data, 2019.
  * Song et al. (2021) Rui Song, Fausto Giunchiglia, Ke Zhao, and Hao Xu.  Topological regularization for graph neural networks augmentation.  In arXiv:2104.02478, 2021.
  * Spinelli et al. (2021) Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini.  Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning.  IEEE TAI, 2021.
  * Sun et al. (2021a) Junwei Sun, Bai Wang, and Bin Wu.  Automated graph representation learning for node classification.  In IJCNN, 2021.
  * Sun et al. (2021b) Mengying Sun, Jing Xing, Huijun Wang, Bin Chen, and Jiayu Zhou.  Mocl: data-driven molecular fingerprint via knowledge-aware contrastive learning from molecular graph.  In KDD, pages 3585–3594, 2021.
  * Suresh et al. (2021) Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville.  Adversarial graph augmentation to improve graph contrastive learning.  In NeurIPS, 2021.
  * Thakoor et al. (2022) Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko.  Large-scale representation learning on graphs via bootstrapping.  In ICLR, 2022.
  * Topping et al. (2022) Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein.  Understanding over-squashing and bottlenecks on graphs via curvature.  In ICLR, 2022.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  In arXiv:1710.10903, 2017.
  * Velickovic et al. (2019) Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  In ICLR, 2019.
  * Verma et al. (2019) Vikas Verma, Meng Qu, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang.  Graphmix: Improved training of gnns for semi-supervised learning.  In arXiv:1909.11715, 2019.
  * Wang et al. (2020a) Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi.  Graphcrop: Subgraph cropping for graph classification.  In arXiv:2009.10564, 2020.
  * Wang et al. (2020b) Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi.  Nodeaug: Semi-supervised node classification with data augmentation.  In KDD, pages 207–217, 2020.
  * Wang et al. (2021a) Yiwei Wang, Yujun Cai, Yuxuan Liang, Henghui Ding, Changhu Wang, Siddharth Bhatia, and Bryan Hooi.  Adaptive data augmentation on temporal graphs.  In NeurIPS, volume 34, 2021.
  * Wang et al. (2021b) Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi.  Mixup for node and graph classification.  In The WebConf, 2021.
  * Wu et al. (2020) Sen Wu, Hongyang Zhang, Gregory Valiant, and Christopher Ré.  On the generalization effects of linear transformations in data augmentation.  In ICML, pages 10410–10420, 2020.
  * Xu et al. (2018) Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka.  Representation learning on graphs with jumping knowledge networks.  In arXiv:1806.03536, 2018.
  * Xu et al. (2021) Dongkuan Xu, Wei Cheng, Dongsheng Luo, Haifeng Chen, and Xiang Zhang.  Infogcl: Information aware graph contrastive learning.  In NeurIPS, 2021.
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In KDD, 2018.
  * You et al. (2020) Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  In NeurIPS, 2020.
  * You et al. (2021) Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang.  Graph contrastive learning automated.  In ICML, pages 12121–12132, 2021.
  * Yuan et al. (2021) Jinliang Yuan, Hualei Yu, Meng Cao, Ming Xu, Junyuan Xie, and Chongjun Wang.  Semi-supervised and self-supervised classification with multi-view graph neural networks.  In CIKM, 2021.
  * Zhang et al. (2018) Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In ICLR, 2018.
  * Zhao et al. (2021a) Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang.  Counterfactual graph learning for link prediction.  In arXiv:2106.02172, 2021.
  * Zhao et al. (2021b) Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah.  Data augmentation for graph neural networks.  In AAAI, 2021.
  * Zhao et al. (2021c) Tong Zhao, Bo Ni, Wenhao Yu, Zhichun Guo, Neil Shah, and Meng Jiang.  Action sequence augmentation for early graph-based anomaly detection.  In CIKM, pages 2668–2678, 2021.
  * Zheng et al. (2020) Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang.  Robust graph representation learning via neural sparsification.  In ICML, pages 11458–11468, 2020.
  * Zhou et al. (2020) Jiajun Zhou, Jie Shen, and Qi Xuan.  Data augmentation for graph classification.  In CIKM, 2020.
  * Zhu et al. (2020) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Deep graph contrastive representation learning.  In arXiv:2006.04131, 2020.
  * Zhu et al. (2021) Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang.  Graph contrastive learning with adaptive augmentation.  In The WebConf, 2021.
  * Zügner and Günnemann (2020) Daniel Zügner and Stephan Günnemann.  Certifiable robustness of graph convolutional networks under structure perturbations.  In KDD, 2020.