# G-MIXUP: GRAPH DATA AUGMENTATION FOR GRAPH CLASSIFICATION

**Anonymous authors**
Paper under double-blind review

ABSTRACT

This work develops mixup to graph data. Mixup has shown superiority in improving the generalization and robustness of neural networks by interpolating features
and labels of random two samples. Traditionally, Mixup can operate on regular, grid-like, and Euclidean data such as image or tabular data. However, it is
challenging to directly adopt Mixup to augment graph data because two graphs
typically: 1) have different numbers of nodes; 2) are not readily aligned; and
3) have unique topologies in non-Euclidean space. To this end, we propose GMixup to augment graphs for graph classification by interpolating the generator
(i.e., graphon) of different classes of graphs. Specifically, we first use graphs
within the same class to estimate a graphon. Then, instead of directly manipulating graphs, we interpolate graphons of different classes in the Euclidean space
to get mixed graphons, where the synthetic graphs are generated through sampling based on the mixed graphons. Extensive experiments show that G-Mixup
substantially improves the generalization and robustness of GNNs.

1 INTRODUCTION

Recently deep learning has been widely adopted to graph analysis. Graph Neural Networks
(GNNs) (Wu et al., 2020; Zhou et al., 2020b; Zhang et al., 2020; Xu et al., 2018) have made many
significant breakthroughs on graph classification. Meanwhile, data augmentation (e.g., DropEdge (Rong et al., 2020), Subgraph (You et al., 2020) ) has also been adopted to graph analysis by
generating synthetic graphs to create more training data for improving the generalization of graph
classification models. However, existing graph data augmentation strategies typically aim to augment graphs at a within-graph level by either modifying edges or nodes in individual graph, which
limits them to only generating new graphs based on one individual graph. The between-graph augmentation methods (i.e., augmenting graphs between graphs) are still under-explored.

In parallel with the development of graph neural networks, Mixup (Zhang et al., 2017) and its variants (e.g., Manifold Mixup (Verma et al., 2019)), as data augmentation methods, have been theoretically and empirically shown to improve the generalization and robustness of deep neural networks
in image recognition (Zhang et al., 2017; Verma et al., 2019; Zhang et al., 2021) and natural language processing (Guo et al., 2019; Guo, 2020). The basic idea of Mixup is to linearly interpolate
continuous values of random sample pairs to generate more synthetic training data. The formal
mathematical expression of Mixup is xnew = λxi + (1 − _λ)xj, ynew = λyi + (1 −_ _λ)yj, where_
(xi, yi) and (xj, yj) are two samples drawn at random from training data and the target y are onehot labels. With graph neural network and mixup in mind, the following question naturally arises,

**_Can we mix up graph data to improve the generalization and robustness of GNNs?_**

It remains an open and challenging problem to mix up the graph data due to the characteristics
of graphs and the requirements of applying Mixup. Typically, Mixup requires that original data instances are regular and well-aligned in Euclidean space, such as image data and table data. However,
graph data is distinctly different from image data due to the following characteristics: (i) graph data
_is irregular. The number of nodes in different graphs are typically different to others; (ii) graph_
_data is not well-aligned. The nodes in different graphs can not be aligned well directly; (iii) graph_
_topology between classes are divergent. The topologies of a pair of graphs from different classes are_
usually different while the topologies of those from the same class are usually similar. thus make it
challenging to directly adopt the Mixup strategy to graph data.


-----

1) graphon

**…** estimation

2) graphon 3) graph

_G = {G1, G2, · · ·, Gk} with label (1, 0)_ _WG_ mixup sampling **…**

1) graphon

**…** estimation _WI = 0.5 ⇤_ _WWGI + 0.5 ⇤_ _WH_ _I = {I1, I2, · · ·, Ik} with label (0.5, 0.5)_

_H = {H1, H2, · · ·, Hk} with label (0, 1)_ _WH_

Figure 1: An overview of G-Mixup. The task is binary graph classification. We have two classes of
graphs G and H with different topologies (G has two communities while H has eight communities).
and have different graphons. We mix up the graphons W and W to obtain a mixed graphon
_G_ _H_ _G_ _H_
_W_, and then sample new graphs from the mixed graphon. Intuitively, the synthetic graphs have two
_I_
major communities and each of which has four sub-communities, demonstrating that the generated
graphs preserve the structure of original graphs from both classes.

To tackle the aforementioned problems, we propose G-Mixup, a class-level graph data augmentation method, to mix up graph data based on graphons. The graphs within one class have the same
generator (i.e., graphon). We mix up the graphons of different classes and then generate synthetic
graphs. Informally, a graphon can be thought of as a probability matrix (e.g., the matrix WG and
_WH in Figure 1), where W_ (i, j) represents the probability of edge between node i and j. The realworld graphs can be regraded as generated from graphons. In this way, we can mix two classes of
graphs by mixing their generators. Since the graphons of different graphs is regular, well-aligned,
and is defined in Euclidean space, it is easy and natural to mix up the graphons and then generate the synthetic graphs therefrom. We also provide theoretical analysis of graphons mixup, which
guarantees that the generated graphs will preserve the key characteristics of both original classes.
Our proposed method is illustrated in Figure 1 with an example. Given two graph training sets
= _G1, G2,_ _, Gk_ and = _H1, H2,_ _, Hk_ with different labels and distinct topologies
_G_ _{_ _· · ·_ _}_ _H_ _{_ _· · ·_ _}_
(i.e., has two communities while has eight communities), we estimate graphons W and W
_G_ _H_ _G_ _H_
respectively from and . We then mix up the two graphons and obtain a mixed graphon W .
_G_ _H_ _I_
After that, we sample synthetic graphs from W as additional training graphs. The generated syn_I_
thetic graphs have two major communities and each of them have four sub-communities, which is a
mixture of the two graph sets. It thus shows that G-Mixup is capable of mixing up graphs.

In summary, our main contributions are three-fold. Firstly, we propose G-Mixup to augment the
training graphs for graph classification. Since directly mixing up graphs is intractable, G-Mixup
mixes the graphons of different classes of graphs to generate synthetic graphs. Secondly, we theoretically prove that the synthetic graph will be the mixture of the original graphs, where the key
topology (i.e., discriminative motif) of source graphs will be preserved. Thirdly, we demonstrate
the efficacy of the proposed G-Mixup on various graph neural network backbones and datasets. Extensive experimental results show the proposed G-Mixup substantially improves the performance of
graph neural networks in terms of enhancing their generalization and robustness.

2 PRELIMINARIES

In this section, we first go over the notations used in this paper, and then introduce graph related
concepts including graph homomorphism and graphons, which will be used for theoretical analysis
in this work. Finally, we briefly review the graph neural networks for graph classification.

2.1 NOTATIONS

Given a graph G, we use V (G) and E(G) to denote its nodes and edges, respectively. The number
of nodes is v(G) = |V (G)|, and the number of edges is e(G) = |E(G)|. We use G, H, I to denote
graphs and _,_ _,_ to denote graph set. y R[C] denotes the label of graph set, where C is
number of classes of graphs. A graph could contain some interesting and frequent patterns and G _H_ _I_ _G ∈_ _G_
subgraphs which are called motifs. The motifs in graph G is denoted as FG. The set of motifs
in graph set is denoted as . W denotes the graphon of graph set . W denotes the step
_G_ _FG_ _G_ _G_


-----

function. Unif [0,1] denotes the uniform distribution between 0 and 1. Bern(·) denotes the Bernoulli
distribution. G(n, W ) denotes the random graph with n nodes based on graphon W .

2.2 GRAPH HOMOMORPHISM AND GRAPHONS

**Graph Homomorphism. A graph homomorphism is an adjacency-preserving mapping between**
two graphs, i.e., mapping adjacent vertices in one graph to adjacent vertices in the other. Formally,
a graph homomorphism φ : F → _G is a map from V (F_ ) to V (G), where if {u, v} ∈ _E(F_ ), then
_{φ(u), φ(v)} ∈_ _E(G). For two graphs H and G, there could be multiple graph homomorphisms_
between them. Let hom(H, G) denotes the total number of graph homomorphisms from graph
_H to graph G. For example, hom(, G) = |V (G)| if graph H is_, hom( _, G) = 2|E(G)|_
if graph H is, and hom( _, G) is six times the number of triangles in G. There are in total_
_|V (G)|[|][V][ (][H][)][|]_ mappings from H to G, but only some of them are homomorphisms. Thus, we define
_homomorphism density to measure the relative frequency that the graph H appears in graph G:_

_t(H, G) = [hom(][H, G][)]_

_|V (G)|[|][V][ (][H][)][|][ .]_

For example, t(, G) = |V (G)|/n[1] = 1, t( _, G) = 2|E(G)|/n[2]._

**Graphon. A graphon (Airoldi et al., 2013) is a continuous, bounded and symmetric function W :**

[0, 1][2] _→_ [0, 1] which may be thought of as the weight matrix of a graph with infinite number of
nodes. Then, given two points ui, uj [0, 1], W (i, j) represents the probability that nodes i and j
be related with an edge. Various quantities of a graph can be calculated as a function of the graphon. ∈
For example, the degree of nodes in graphs can be easily extended to a degree distribution function
1
in graphons, which is characterized by its graphon marginal dW (x) = 0 _[W]_ [(][x, y][)][dy][. Similarly, the]
concept of homomorphism density can be naturally extended from graphs to graphons. Given an
arbitrary graph motif F, its homomorphism density with respect to graphonR _W is defined by_

_t(F, W_ ) = _W_ (xi, xj) _dxi._

[0,1][V][ (][F][ )]

Z _i,j_ _E(F )_ _i_ _V (F )_

_∈Y_ _∈Y_

For example, the edge density of graphon W is t( _, W_ ) = [0,1][2][ W] [(][x, y][)][ dxdy][, and the triangle]

density of graphon W is t( _, W_ ) = [0,1][3][ W] [(][x, y][)][W] [(][x, z][)][W]R [(][y, z][)][ dxdydz][.]
R


_t(F, W_ ) =



[0,1][V][ (][F][ )]


2.3 GRAPH CLASSIFICATION WITH GRAPH NEURAL NETWORKS

Given a set of graphs, graph classification aims to assign a class label for each graph G. Recently,
graph neural networks have become the state-of-the-art approach for graph classification. Without
loss of generalization, we present the formal expression of a graph convolution network (GCN) (Kipf
& Welling, 2016). The forward propagation at k-th layer is described as the following:

**a[(]i[k][)]** = AGG[(][k][)][ n]h[(]j[k][−][1)] : j (i) _,_ **h[(]i[k][)]** = COMBINE[(][k][)][ ]h[(]i[k][−][1)], a[(]i[k][)] _,_ (1)
_∈_ _N_

o 

where h[(]i[k][)] R[n][×][d][k] is the intermediate representation of node i at the k-th layer, (i) denotes the
_∈_ _N_
neighbors of node i. AGG(·) is an aggregation function to collect embedding representations from
neighbors, and COMBINE(·) combines neighbor representation and its representation at (k − 1)-th
layer followed by nonlinear transformation. For graph classification, a graph-level representation is
obtained by summarizing all node-level representations in the graph by a readout function:

**hG = READOUT** **h[(]i[k][)]** : i _E(G)_ _,_ **yˆ = softmax(hG),** (2)
_∈_
n o

where READOUT(·) is the readout function, which can be a simple function such as average or
sophisticated pooling function (Gao & Ji, 2019; Ying et al., 2018), hG is the representation of graph
_G, and ˆy ∈_ R[C] is the output estimating the probability that G belongs to each of the C classes.

3 METHODOLOGY

In this section, we first formally introduce the proposed G-Mixup, and then present theoretical analysis of graph generation via graphon interpolation from the graph homomorphism density perspective.


-----

3.1 _G -MIXUP_

Different from interpolation of image data in Euclidean space, adopting Mixup to graph data is
nontrivial since graphs are irregular, unaligned and non-Euclidean data. In this work, we show that
this challenge could be tackled via graphon theories. By intuition, graphon can be thought of as a
generator to generate graphs. The real-world graphs can be regraded as generated form a graphon,
which has same homomorphism density of arbitrary motif to that of graphon. With this in mind, we
propose G-Mixup, a class-level data augmentation via graphon interpolation. G-Mixup interpolates
different graph generator to obtain a new generator. Then, synthetic graphs are sampled based on
the mixed graphon for graph data augmentation. The graphs sampled from this generator partially
possess properties of all the original graphs. Formally, G-Mixup can be formulated as the following:
Graphon Estimation: _W_ _,_ _W_ _,_ (3)
_G →_ _G_ _H →_ _H_
Graphon Mixup: _W_ = λW + (1 _λ)W_ _,_ (4)
_I_ _G_ _−_ _H_

i.i.d
Graph Generation: _I1, I2,_ _, Ik_ G(k, W ), (5)
_{_ _· · ·_ _}_ _∼_ _I_
Label Mixup: **y** = λy + (1 _λ)y_ _,_ (6)
_I_ _G_ _−_ _H_

where W _, W_ are graphons of the graph set and . The mixed graphon is denoted by W, and
_G_ _H_ _G_ _H_ _I_
_λ ∈_ [0, 1] is the trade-off hyperparameter to control the contributions from different original graphs
for interpolation. The set of synthetic graphs generated from W is = _I1, I2,_ _, Ik_ . The
_I_ _I_ _{_ _· · ·_ _}_
**y** R[C] and y R[C] are vectors containing ground-truth labels for graph G and H respectively.
The label vector of a generated graph inG ∈ _H ∈_ is set as y R[C], where C is the total classes of graphs.
_I_ _I ∈_

As illustrated in Figure 1 and the above equations, the proposed G-Mixup includes three key steps:
**i) estimate the graphon for each class of graphs with the same label, ii) mix up the graphons of**
different classes of graphs, and iii) generate the synthetic graphs based on the mixed graphon.
Specifically, we have = _G1, G2,_ _, Gk_ with label yG, and = _H1, H2,_ _, Hk_ with
_G_ _{_ _· · ·_ _}_ _H_ _{_ _· · ·_ _}_
label y . Graphons W and W are estimated from graph set and, then we mix them up
_H_ _G_ _H_ _G_ _H_
though linearly interpolating two graphons and their training labels and obtain W and y . The
_I_ _I_
synthetic graph set is sampled based on W, which will be used as additional training graphs.
_I_ _I_

3.2 IMPLEMENTATION

In this section, we introduce the details of the implementation of estimating graphon from the observed graphs and generating synthetic graphs in the real-world scenario.

**Graphon Estimation and Mixup. Estimating graphons from observed graphs is a prerequisite**
for G-Mixup, however, it is intractable because graphon is an unknown function without closedform solution in real-world graphs. Therefore, we use step function (Lov´asz, 2012; Xu et al.,

2021) as an approximation of graphon. [1] The step function estimation methods are well-studied,
which first aligns the nodes of a series of graphs based on simple node measurements (e.g., degree) and then estimates the step function from all the aligned adjacency matrices. The step
function estimation methods used includes sorting-and-smoothing (SAS) method (Chan & Airoldi,
2014), stochastic block approximation (SBA) (Airoldi et al., 2013), “largest gap” (LG) (Channarond
et al., 2012), matrix completion (MC) (Keshavan et al., 2010), universal singular value thresholding (USVT) (Chatterjee et al.K, 2015). Formally, a step function W[P] : [0, 1][2] _7→_ [0, 1] is define as

**W[P]** (x, y) =

_k,k[′]=1_ _[w][kk][′]_ [1][P][k][×P][k][′][ (][x, y][)][, where][ P][ = (][P][1][, ..,][ P][K][)][ denotes the partition of][ [0][,][ 1]]

into K adjacent intervals of lengthX 1/K, wkk′ ∈ [0, 1], and indicator function 1Pk×Pk′ (x, y) equals
to 1 if (x, y) _k_ _k′ and otherwise it is 0. Essentially, the step function can be seen as a matrix_
**W = [wkk′** ] ∈P[0, ×P 1][K][×][K], where Wij is the probability of edge between node i and j. In practice,
_∈_
_we use the matrix-form step function as graphon to mix up and generation synthetic graphs._

_For binary classification, we have_ = _G1, G2,_ _, Gk_ and = _H1, H2,_ _, Hk_ with dif_G_ _{_ _· · ·_ _}_ _H_ _{_ _· · ·_ _}_
ferent labels, we estimate their step functions W R[K][×][K] and W R[K][×][K] We let K be the
average number of nodes in all graphs. For multi-class classificationG ∈, we first estimate the step func-H ∈
tion for each class of graphs and then randomly select two to perform mix-up. The resultant step
function is W = λW +(1 _λ)W_ R[K][×][K], which serves as the generator of synthetic graphs.
_I_ _G_ _−_ _H ∈_

1Because weak regularity lemma of graphon (Frieze & Kannan, 1999) indicates that an arbitrary graphon
can be approximated well by step function. Detailed discussion is in Appendix A.4.


-----

**Synthetic Graphs Generation. A graphon W provides a distribution to generating arbitrarily sized**
graphs. Specifically, a k-node random graph G(k, W ) can be generated following the process:
_I_

_u1, . . ., uk_ _∼iid_ Unif [0,1], (G(k, W )ij|u1, . . ., uk) _∼iid_ Bern(W (ui, uj)), ∀i, j ∈ [k]. (7)

Since we only estimate the step function W to approximate the graph W, we set W (ui, uj) =
**WI** [ 1/ui _,_ 1/uj ], and is the floor function. The first step samples K nodes independently
_⌊_ _⌋_ _⌊_ _⌋_ _⌊·⌋_
from a uniform distribution on [0, 1]. The second step generates an adjacency matrix A = [aij]
_∈_
_{0, 1}[K][×][K], whose element values follow the Bernoulli distributions determined by the step func-_
tion. A graph is thus obtained as G where V (G) = {1, ..., K} and E(G) = {(i, j) | aij = 1}.
A set of synthetic graphs can be generated by conducting the above process independently multiple
times. For node features, we generate them of synthetic graphs based the original two sets of graphs.
Specifically, we generate the node feature of each graphons. In the graphon estimation, we align the
node features with the process of the adjacency matrix. For each graphon we have a set of node
features, we can pooling the node features to obtain the graphon features. The the node features
would inherit form the graphon features.

**Computational Complexity Analysis. We now discuss computa-** Table 1: Computational comtional complexity of the proposed -Mixup. The major additional
_G_ plexity of graphon estimacomputation costs come from graphon estimation and graph gen
tion (Xu et al., 2021)

eration. For graphon estimation, suppose we have M graphs and

Method Complexity

each of them has N nodes and E edges, and estimate step function
withgraphon estimation methods ( K partitions to approximate a graphon, the complexity of usedXu et al., 2021) is in Table 1. For MCUSVTLG _O(OOMN((NN_ [3][3][2])))
_graph generation, suppose we need to generate K graphs with N_ SBA _O(MKN log N_ )
nodes, the computational complexity is O(KN ) for node genera- SAS _O(MN log N + K[2]_ log K[2])
tion and O(KN [2]) for edge generation, so the overall complexity of graph generation is O(KN [2]).

4 THEORETICAL JUSTIFICATION

In the following, we will theoretically prove that, the synthetic graphs generated by G-Mixup will
_be a mixture of original graphs. We first define the discriminative motif, and then we justify the_
graphon mixup operation (Equation 4) and graph generation operation (Equation 5) by analysing
the homomorphism density of discriminative motifs of the original graphs and the synthetic graphs.

**Definition 1 (Discriminative Motif) A discriminative motif FG of graph G is the subgraph, with**
_the minimal number of nodes and edges, that can decide the class the graph G. Discriminative_
_motifs_ _is the set of the discriminative motif of every graph in the graph set_ _._
_FG_ _G_

Intuitively, the discriminative motif is the key topology of a graph, by which the graph can be
distinguished. We assume that (i) every graph G has a discriminative motif FG, and (ii) a set
_of graphs_ _has a finite set of discriminative motifs_ _. The goal of graph classification is to_
_G_ _FG_
filter out structural noise in graphs (Fox & Rajamanickam, 2019) and recognize the key typologies
(discriminative motifs) to predict the class label. For example, benzene (a compound in chemistry)
is distinguished by the discriminative motif (benzene ring).

4.1 WILL DISCRIMINATIVE MOTIFS F AND F EXIST IN λW + (1 _λ)W_ ?
_G_ _H_ _G_ _−_ _H_

We answer this question by exploring the difference in homomorphism density of discriminative
motifs between the original graphon and mixed graphon. We propose the following theorem,

**Theorem 1 Given two sets of graphs** _and_ _, the corresponding graphons are W_ _and W_ _, and_
_G_ _H_ _G_ _H_
_the corresponding discriminative motif set_ _and_ _. For every discriminative motif F_
_and F_ _, the difference between the homomorphism density of FG_ _FH_ _F_ _/F_ _in the mixed graphonG ∈FG_
_W_ =H λW ∈F + (1H _λ)W_ _and that of the graphon W_ _/W_ _is upper bounded byG_ _H_
_I_ _G_ _−_ _H_ _H_ _G_
_|t(FG, WI) −_ _t(FG, WG)| ≤_ (1 − _λ)e(FG)||WH −_ _WG||□_ _,_ (8)
_|t(FH, WI) −_ _t(FH, WH)| ≤_ _λe(FH)||WH −_ _WG||□_

_where2Details about cut norm are in Appendic e(F_ ) is the number of nodes in graph A.1 _F and ||WH −_ _WG||□_ _is the cut norm_ [2].


-----

_Proof Sketch. The proof follows the derivation of Counting Lemma for Graphons (Lemma 10.23_
in Lov´asz (2012)), which relates the homomorphism density and the cut distance _W_ _W_
of graphons. Specifically, we take the two graphons in this Lemma to deduce the bound of the || _H −_ _G||_
difference of homomorphism densities of W and W _/W_ . Detailed proof are in Appendix A.2. ■
_I_ _G_ _H_

Theorem 1 suggests that the difference in the homomorphism densities of the mixed graphon and
original graphons is upper bounded. Note that difference depends on the hyperparameter λ, the
normhomomorphism densities will be decided byedge number ||WH − e(WFGG||)/□e(are decided by the dataset ( can be regraded as a constant), the difference inFH) and the cut norm λ ||. On this basis, the corresponding label of the graphonWH − _WG||□. Since the e(FG)/e(FH) and the cut_
is set to λy + (1 _λ)y_ . Therefore, **-Mixup can preserve the different discriminative motifs**
_G_ _−_ _H_ _G_
**of the two different graphons into one mixed graphon.**

4.2 WILL THE GENERATED GRAPHS FROM GRAPHON W PRESERVE THE MIXTURE OF
_I_
DISCRIMINATIVE MOTIFS?

Ideally, the generated graphs should inherit the homomorphism density of discriminative motifs
from the graphon. To verify this, we propose the following theorem.

**Theorem 2 Let WI be the mixed graphon, n ≥** 1, 0 < ε < 1, and let FI be the mixed discrimina_tive motif, then the W_ _-random graph G = G(n, W_ ) satisfies
_I_ _I_

_ε[2]n_
P ( _t(F_ _, G)_ _t(F_ _, W_ ) _> ε)_ 2exp _._ (9)
_|_ _I_ _−_ _I_ _I_ _|_ _≤_ _−_ 8v(FI )[2]
 

Theorem 2 states that for any nonzero specified margin ε, no matter how small, with a sufficiently
large samples of graph from mixed graphon, the homomorphism density of discriminative motif
in synthetic graphs will approximately equal to that in graphon t(F _, G)_ _t(F_ _, W_ ) with high
_I_ _≈_ _I_ _I_
probability. In other words, it reads the synthetic graphs will preserve the discriminative motif
of the mixed graphon with a very high probability if the sample number n is large enough. The
detailed proof is presented in Appendix A.3. Therefore, G-Mixup can preserve the different
**discriminative motifs of the two different graphs into one mixed graph.**

4.3 DISCUSSION

This section discusses the differences and relations between G-Mixup and other graph augmentation
strategies, such as DropEdge (Rong et al., 2020), and Manifold Mixup (Wang et al., 2021).

**Relation to Edge Perturbation Method . Edge perturbation methods is to randomly perturb the**
edges to improve the GNNs, inlcuding DropEdge (Rong et al., 2020), Graphon-based edge perturbation (Hu et al., 2021). DropEdge drops graph edges independently with a specified probability,
aiming to prevent over-smoothing and over-fitting issues in GNNs. Graphon-based edge perturbation (Rong et al., 2020) improves the Dropedge by dropping edge based on an estimated probability.
One of the limitations of such methods is that the edge permutation is based on the one individual
graph, the graphs will not mix up. Edge perturbation methods will not mix the two discriminative
motifs together and only randomly add remove some edges while the graphon will add some edges
based on the graphon. DropEdge and Graphon-based edge perturbation (Hu et al., 2021) are special cases of G-Mixup while setting different hyperparameter λ. i) G-Mixup will degenerate into
_Graphon-based edge perturbation, while λ = 0 in Equation 4. The mathematical expression is_
i.i.d
_W_ = W _,_ _I1, I2,_ _, Ik_ G(k, W ), y = y . ii) _-Mixup will degenerate into DropEdge,_
_I_ _H_ _{_ _· · ·_ _}_ _∼_ _I_ _I_ _H_ _G_
while setting λ = 0 and masking graphons with adjacency matrix A in Equation 4. The expression is
i.i.d
_W_ = A _W_ _,_ _I1, I2,_ _, Ik_ G(k, W ), y = y, where is element-wise multiplication.
_I_ _⊙_ _H_ _{_ _· · ·_ _}_ _∼_ _I_ _I_ _H_ _⊙_

**Relation to Manifold Mixup for Graph. The methods proposed by Wang et al. (2021) is to adopt**
Manifold Mixup to graph data, which mix up graphs representation in the embedding space. The
Manifold Mixup is to stabilize the model training by interpolating hidden representation. Interpolating hidden representation limits its applications by that 1) learning algorithms must have hidden
representation of graphs and 2) models must be modified to adapt Manifold Mixup. In contrast, GMixup is capable of generating synthetic graphs without modifying models. As a data augmentation
method, our proposal has broader applications, e.g., creating graphs for graph contrastive learning.


-----

5 EXPERIMENTS

We evaluate the performance of the proposed G-Mixup in this section. First, we visualize graphons
and graph generation results to investigate what G-Mixup actually do on real-world datasets in Section 5.1 and Section 5.2. Then, we evaluate the effectiveness of G-Mixup in graph classification
with various datasets and GNN backbones in Section 5.3, as well as how it improve the robustness
of GNNs against label corruption and adversarial examples in Section 5.4.


5.1 DOES DIFFERENT CLASSES OF REAL-WORLD GRAPHS HAVE DIFFERENT GRAPHONS?

We visualize the estimated graphon in Figure 2 to examine whether there are different graphons for
different classes of graphs. Observation 1: different classes of graphs have different graphons in
**real-world dataset. As shown in Figure 2, the graphons of different class of graphs in one dataset**
are distinctly different. The graphons of IMDB-BINAERY in Figure 2 shows that the graphon
of class 1 has larger dense area, which indicates that the graphs in this class have a more large
communities than the graphs of class 0. The graphons of REDDIT-BINARY in Figure 2 shows that
graphs of class 0 have one high-degree nodes while the graphs of class 1 have two. This observation
validates that real-world graphs of different classes have distinctly different graphons, which lays a
solid foundation for generating the mixture of graphs by mixing up graphons.


**Class 0** **Class 1** **Class 0** **Class 1** **Class 0** **Class 1** **Class 2**

**IMDB-BINARY** **REDDIT-BINARY** **IMDB-MULTI**


Figure 2: Estimated graphons on IMDB-BINARY, REDDIT-BINARY, and IMDB-MULTI. Obviously, graphons of different classes of graphs are quiet different. This observation validates the
divergence of graphons between different classes of graphs, which is the basis of the G-Mixup. The
graphons are estimated by LG. More estimated graphons via various methods are in Appendix B.3.

5.2 WHAT IS G-MIXUP DOING? A CASE STUDY


To investigate the outcome of G-Mixup in real-world scenarios, we visualize the generated synthetic
graphs in REDDIT-BINARY dataset in Figure 3. Observation 2: synthetic graphs are indeed the
**mixture of the original graphs. Original graphs and the generated synthetic graphs are visualized**
in Figure 3(a)(b) and Figure 3(c)(d)(e), respectively. Figure 3 demonstrates that mixed graphon
0.5 _W_ +0.5 _W_ is able to generate graphs with a high-degree node and a dense subgraph, which
_∗_ _G_ _∗_ _H_
can be regarded as the mixture of graphs with one high-degree node and two high-degree nodes. It
validates that G-Mixup prefer to preserve the discriminative motifs from the original graphs.

(a) graphs of class 0 and the graphon W0 (b) graphs of class 1 and the graphon W1

_W0_ _W1_

(c) graphs generated from 1 ⇤ _W0 + 0 ⇤_ _W1_ (d) graphs generated from 0 ⇤ _W0 + 1 ⇤_ _W1_ (e) graphs generated from 0.5 ⇤ _W0 + 0.5 ⇤_ _W1_


Figure 3: The visualization of generated synthetic graphs on dataset REDDIT-BINARY. The first
row is the original graphs in the dataset while the second row is the generated graphs through the
proposed G-Mixup. The graphs in (a) and (b) are the original graphs of class 0 and class 1. The
distinct difference of these two classes of graphs is that graphs of class 0 have one high-degree node
while graphs of class 1 have two ( marked with in (a) and (b) ). (c)/(d) shows graphs generated
with the mixed graphon (1 ∗ _W0 + 0 ∗_ _W1) / (0 ∗_ _W0 + 1 ∗_ _W1), which have one/two high-degree_
node/nodes (marked with in (c) and (d)) because the mixed graphon only contains W0/W1. The
synthetic graphs generated from (0.5 ∗ _W0 + 0.5 ∗_ _W1) is the mixture of graphs of class 0 and_
class 1, which appears as a high-degree node and a dense subgraph ( marked with and in (e),
respectively). The visualization shows that synthetic graphs are the mixture of the original graphs.


-----

Figure 4: The training/validation/test curves on IMDB-BINARY, IMDB-MULTI, REDDIT
**IMDB-BINARY** **IMDB-MULTI** **REDDIT-BINARY** **REDDIT-MULTI-5K**

**Cross-entropy Loss**

**Epoch** **Epoch** **Epoch** **Epoch**

BINARY and REDDIT-MULTI-5K with GCN as backbone. The curves are depicted on ten runs.

Table 2: Performance comparisons of G-Mixup with different graph neural networks on different
dataset. The metric is the classification accuracy and its standard deviation. The best performance is
in boldface. Experimental settings are in Appendix B.1. Experiments with more backbones (DiffPool, MincutPool, GMT) and molecular property prediction are in Appendix C.1 and Appendix C.2.

|Dataset IMD|B-B IMDB-M REDDIT-B REDD-M5k R|
|---|---|

|#graphs 10 #classes 2 #avg.nodes 19. #avg.edges 96.|00 1500 2000 4999 3 2 5 77 13.00 429.63 508.52 53 65.94 497.75 594.87|
|---|---|

|GCN vanilla 72.18 w/ Dropedge 72.50 w/ NodeDropping 72.00 w/ Subgraph 68.50 w/ ManfoldMixup 72.83 w/ G-Mixup 72.87|48.79 78.82 45.07 ±1.55 ±2.72 ±1.33 ±1.70 49.08 81.25 51.35 ±0.31 ±1.89 ±8.15 ±1.54 48.58 79.25 49.35 ±4.09 ±2.85 ±0.35 ±1.80 49.58 74.33 48.70 ±4.76 ±2.61 ±2.88 ±1.63 49.50 75.75 49.82 ±1.75 ±1.97 ±4.53 ±0.85 ±3.85 51.30 ±2.14 89.81 ±0.74 51.51 ±1.70|
|---|---|

|GIN vanilla 71.55 w/ Dropedge 72.20 w/ NodeDropping 72.16 w/ Subgraph 68.50 w/ ManfoldMixup 70.83 w/ -Mixup 71.94 G|48.83 92.59 55.19 ±3.53 ±2.75 ±0.86 ±1.02 48.83 92.00 55.10 ±1.82 ±3.02 ±1.13 ±0.44 48.33 90.25 53.26 ±0.28 ±0.98 ±0.98 ±4.99 47.25 90.33 54.60 ±0.86 ±3.78 ±0.87 ±3.15 49.88 90.75 54.95 ±1.04 ±1.34 ±1.78 ±0.86 ±3.00 50.46 ±1.49 92.90 ±0.87 55.49 ±0.53|
|---|---|

|TopKPool vanilla 72.37 w/ Dropedge 71.75 w/ NodeDropping 69.16 w/ Subgraph 67.83 w/ ManfoldMixup 71.83 w/ G-Mixup 72.80|50.57 90.30 45.07 ±5.01 ±1.62 ±1.47 ±1.70 ±2.18 48.75 ±2.94 88.96 ±1.90 47.43 ±1.82 48.50 81.33 46.15 ±1.04 ±2.50 ±4.48 ±2.28 50.83 86.08 45.75 ±4.01 ±2.38 ±2.12 ±2.47 51.22 87.58 45.60 ±3.03 ±1.17 ±3.16 ±2.35 ±3.33 51.30 ±2.14 90.40 ±0.89 46.48 ±1.70|
|---|---|


5.3 CAN G-MIXUP IMPROVE THE PERFORMANCE AND GENERALIZATION OF GNNS?

To validate the effectiveness of our proposal, we experiment to compare the performance with various backbones of GNNs on various datasets, and summarize results in Table 2 as well as the training
curves in Figure 4. Our main observations are: Observation 3: G-Mixup can significantly im**proves the performance of various graph neural networks on various datasets. From Table 2,**
our proposal gain 12 best performances among 15 reported accuracies, which substantially improve
the performance of GNNs. Overall, our proposal performs 2.84% better than vanilla model. Note
that G-Mixup and baseline models adopt the same architecture of GNNs (e.g., layers, activation
functions) and the same training hyperparameters (e.g., optimizer, learning rate). Considering both
model performance and experimental setting, the improvement adequately validates the effectiveness of our proposal. Observation 4: G-Mixup can significantly improve the generalization of
**various backbones of graph neural networks. From the loss curve on test data (green line) in**
Figure 4, the loss of test data of G-Mixup (dashed green lines) are consistently lower than the vanilla
model (solid green lines). Considering both the better performance and the better test loss curves,
our proposal substantially is able to improve the generalization of GNNs. Observation 5: G-Mixup
**largely stabilizes the model training. As shown in Table 2, G-Mixup achieves 11 lower standard**
deviation among total 15 reported numbers than vanilla model. Additionally, the train/validation/test


-----

curves of G-Mixup (dashed line) in Figure 4 are more stable than vanilla model (solid line). These
all indicate that our proposal G-Mixup is capable of stabilizing the training of graph neural networks.

5.4 CAN G -MIXUP VIRTUALLY IMPROVE THE ROBUSTNESS OF GNNS?

We investigate the two kinds of robustness of the proposed G-Mixup, including Label Corruption
_Robustness and Topology Corruption Robustness, and report the results in Table 3 and 4, respec-_
tively. More experimental settings are presented in Appendix B.2. Observation 6: G-Mixup im**proves the robustness of graph neural networks. Table 3 shows our proposal gains the better**
performance, indicating it is more robust to noisy label than vanilla baseline. Table 4 shows that
_G-Mixup is more robust when graph topology is corrupted since the accuracy is consistently better_
than baselines. This can be an advantage of G-Mixup when graph labels or topologies are noisy.

Table 3: Robustness to label corruption with Table 4: Robustness to topology corruption with
different corruption ratio. different corruption ratio.


Models Methods 10% 20% 30% 40%

IMDB-B vanilla 72.30±3.67 69.43±4.80 63.65±8.87 **55.21±8.75**

w/ Dropedge 72.00±2.44 69.52±3.25 64.12±3.44 48.50±0.00

w/ ManfoldMixup 71.87±3.56 69.03±4.85 65.62±9.89 48.50±0.00

w/ G-Mixup **72.56±3.08** **69.87±5.41** **65.50±8.90** 52.56±6.97

REDDIT-B vanilla **73.90±1.43** 75.68±2.75 68.12±0.81 46.50±0.00

w/ Dropedge 73.75±1.28 72.06±1.42 46.50±0.00 46.50±0.00

w/ ManfoldMixup 71.96±1.97 76.00±2.24 54.43±1.09 46.50±0.00

w/ G-Mixup 71.94±3.00 **76.34±1.49** **74.21±1.85** **53.50±0.00**


Models Methods 10% 20% 30% 40%

Removing edges vanilla 77.96±3.71 67.59±5.73 64.96±8.87 65.71±8.31

w/ Dropedge 74.40±2.26 65.12±3.51 65.93±2.32 57.87±4.14

w/ ManfoldMixup 75.62±1.59 65.81±3.84 59.81±9.45 57.31±3.15

w/ G-Mixup **81.46±3.08** **71.12±7.47** **67.46±8.90** **66.25±7.78**

Adding edges vanilla 76.12±5.73 74.37±6.48 72.31±2.69 72.00±2.92

w/ Dropedge 70.53±1.47 70.18±1.29 71.18±1.53 70.90±1.53

w/ ManfoldMixup 73.41±2.40 71.87±1.28 71.50±2.03 71.21±2.00

w/ G-Mixup **84.31±3.21** **82.21±4.31** **77.00±2.25** **75.56±3.05**


6 RELATED WORKS

**Graph Data Augmentation** Graph neural networks (GNNs) also achieve the state-of-the-art performance on graph classification task (Kipf & Welling, 2016; Veliˇckovi´c et al., 2017; Hamilton et al.,

2017; Xu et al., 2018; Zhang et al., 2018). In parallel, graph data augmentation methods are also
proposes to improve the performance of GNNs. There are three categories of graph data augmentation, including node perturbation (You et al., 2020), edge perturbation (Rong et al., 2020; You
et al., 2020), and subgraph sampling (You et al., 2020). We have discussed the detailed differences
to the mainstream graph augmentation method in Section 4.3. However, the common limitation of
the existing graph data augmentation methods is that these methods are based on one single graph
while G-Mixup is able to augment new graphs using multiple input graphs. Besides, there are modelindependent graph data augmentation methods (Zhou et al., 2020a; Zhao et al., 2021) and graph data
augmentation method for node classification, which is not applicable while our methods is genral
plug-in model-agnostic graph data augmentation methods for graph classification.

**Graphon Estimation.** Graphons and convergent graph sequences have been broadly studied in
mathematics (Lov´asz, 2012; Lov´asz & Szegedy, 2006; Borgs et al., 2008) and have been applied to to
network science (Avella-Medina et al., 2018; Vizuete et al., 2021) and graph neural networks (Ruiz
et al., 2020a;b). There are tow lines of works to estimate step functions, one is based on stochastic
block models, such as sorting-and-smoothing (SAS) method (Chan & Airoldi, 2014), stochastic
block approximation (SBA) (Airoldi et al., 2013), “largest gap” (LG) (Channarond et al., 2012);
another one is based on matrix decomposition, such as matrix completion (MC) (Keshavan et al.,
2010), universal singular value thresholding (USVT) (Chatterjee et al., 2015). We estimate the step
function using the above five methods (Xu et al., 2021) and the estimation are in Appendix B.3.

7 CONCLUSION

This work develops G-Mixup to augment graph data. Unlike image data, graph data is irregular,
unaligned and in non-Euclidean space, making it hard to be mixed up. However, the graphs within
one class have the same generator (i.e., graphon), which is regular, well-aligned and in Euclidean
space. Thus we turn to mix up the graphons of different classes then generate synthetic graphs.
_G-Mixup is a new graph data augmentation algorithm which mix up the input graph to interpolate_
the topologies of different classes of graphs. A variety of experiments have shown that graph neural
networks trained with G-Mixup achieve better performance and generalization in terms of model
accuracy and model loss, and improve the robustness to noisy labels and corrupted topologies.


-----

REFERENCES

Edoardo M Airoldi, Thiago B Costa, and Stanley H Chan. Stochastic blockmodel approximation of
a graphon: Theory and consistent estimation. arXiv preprint arXiv:1311.1731, 2013.

Marco Avella-Medina, Francesca Parise, Michael T Schaub, and Santiago Segarra. Centrality measures for graphons: Accounting for uncertainty in networks. IEEE Transactions on Network
_Science and Engineering, 7(1):520–537, 2018._

Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with
graph multiset pooling. In International Conference on Learning Representations, 2020.

Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural
networks for graph pooling. In International Conference on Machine Learning, pp. 874–883.
PMLR, 2020.

Christian Borgs, Jennifer T Chayes, L´aszl´o Lov´asz, Vera T S´os, and Katalin Vesztergombi. Convergent sequences of dense graphs i: Subgraph frequencies, metric properties and testing. Advances
_in Mathematics, 219(6):1801–1851, 2008._

Stanley Chan and Edoardo Airoldi. A consistent histogram estimator for exchangeable graph models. In International Conference on Machine Learning, pp. 208–216, 2014.

Antoine Channarond, Jean-Jacques Daudin, St´ephane Robin, et al. Classification and estimation
in the stochastic blockmodel based on the empirical degrees. Electronic Journal of Statistics, 6:
2574–2601, 2012.

Sourav Chatterjee et al. Matrix estimation by universal singular value thresholding. The Annals of
_Statistics, 43(1):177–214, 2015._

James Fox and Sivasankaran Rajamanickam. How robust are graph neural networks to structural
noise? arXiv preprint arXiv:1912.10206, 2019.

Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica,
19(2):175–220, 1999.

Hongyang Gao and Shuiwang Ji. Graph u-nets. arXiv preprint arXiv:1905.05178, 2019.

Hongyu Guo. Nonlinear mixup: Out-of-manifold data augmentation for text classification. In
_Proceedings of the AAAI Conference on Artificial Intelligence, 2020._

Hongyu Guo, Yongyi Mao, and Richong Zhang. Augmenting data with mixup for sentence classification: An empirical study. arXiv preprint arXiv:1905.08941, 2019.

Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
In Advances in neural information processing systems, pp. 1024–1034, 2017.

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 Ad_vances in Neural Information Processing Systems, volume 33, pp. 22118–22133, 2020._

Ziqing Hu, Yihao Fang, and Lizhen Lin. Training graph neural networks by graphon estimation,
2021.

Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by
reducing internal covariate shift. In International conference on machine learning, pp. 448–456.
PMLR, 2015.

Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few
entries. IEEE transactions on information theory, 56(6):2980–2998, 2010.

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster),
2015.


-----

Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.

L´aszl´o Lov´asz. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.

L´aszl´o Lov´asz and Bal´azs Szegedy. Limits of dense graph sequences. Journal of Combinatorial
_Theory, Series B, 96(6):933–957, 2006._

Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines.
In Icml, 2010.

Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph
convolutional networks on node classification. In ICLR 2020 : Eighth International Conference
_on Learning Representations, 2020._

Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability
of graph neural networks. Advances in Neural Information Processing Systems, 33, 2020a.

Luana Ruiz, Zhiyang Wang, and Alejandro Ribeiro. Graph and graphon neural network stability.
_arXiv preprint arXiv:2010.12529, 2020b._

Petar Veliˇckovi´c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua
Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.

Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David LopezPaz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states.
In International Conference on Machine Learning, pp. 6438–6447. PMLR, 2019.

Renato Vizuete, Federica Garin, and Paolo Frasca. The laplacian spectrum of large graphs sampled
from graphons. IEEE Transactions on Network Science and Engineering, 2021.

Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph
classification. In Proceedings of the Web Conference 2021, pp. 3663–3674, 2021.

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A
comprehensive survey on graph neural networks. IEEE transactions on neural networks and
_learning systems, 2020._

Hongteng Xu, Dixin Luo, Lawrence Carin, and Hongyuan Zha. Learning graphons via structured
gromov-wasserstein barycenters. In Proceedings of the AAAI Conference on Artificial Intelli_gence, pp. 10505–10513, 2021._

Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? In International Conference on Learning Representations, 2018.

Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec.
Hierarchical graph representation learning with differentiable pooling. In Proceedings of the 32nd
_International Conference on Neural Information Processing Systems, pp. 4805–4815, 2018._

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, 2020.

Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Representations, 2017.

Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou. How does mixup
help with robustness and generalization? In International Conference on Learning Representa_tions, 2021._

Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning
architecture for graph classification. In Thirty-Second AAAI Conference on Artificial Intelligence,
2018.


-----

Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning on graphs: A survey. IEEE Transactions
_on Knowledge and Data Engineering, 2020._

Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intel_ligence, volume 35, pp. 11015–11023, 2021._

[Yufei Zhao. Graph theory and additive combinatorics, 2019. URL https://yufeizhao.com/](https://yufeizhao.com/gtac/)
[gtac/.](https://yufeizhao.com/gtac/)

Jiajun Zhou, Jie Shen, and Qi Xuan. Data augmentation for graph classification. In Proceedings of
_the 29th ACM International Conference on Information & Knowledge Management, pp. 2341–_
2344, 2020a.

Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang,
Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57–81, 2020b.


-----

A PROOF OF THEOREM

In the appendix, we first present the preliminaries in Appendix A.1. And then we present complete
proof for Theorem 1 and Theorem 2 in Section A.3 and A.2, respectively.

A.1 PRELIMINARIES

Cut norm (Lov´asz, 2012; Zhao, 2019) is used to measure structural similarity of two graphons. The
definition of cut norm is as follow:

**Definition 2 The cut norm of grapon W is defined as**


_W_ (x, y)dxdy _,_ (10)
_S×T_


_∥W_ _∥□_ = supS,T ⊂[0,1]


where the supremum is taken over all measurable subsets S and T .

The following lemma follows the derivation of counting lemma for graphons, are known in the
paper (Lov´asz, 2012). It will be used to prove the Theorem 1.

**Lemma 1 Let F be a simple graph and let W, W** _[′]_ _∈W. Then_

_|t(F, W_ ) − _t(F, W_ _[′])| ≤_ e(F )||W − _W_ _[′]||□_ (11)

_Proof of Lemma 1. The proof follows Zhao (2019). For an arbitrary simple graph F_, by the triangle
inequality we have


_|t(F, W_ ) − _t(F, W_ _[′])|_

= _W (ui, vi)_ _W_ (ui, vi) _dv_

_−_ _[′]_

Z _uiYvi∈E_ _uiYvi∈E_ ! Yv∈V

_|E|_ _i−1_ _|E|_

_W_ (uj, vj) (W (ui, vi) _W_ (ui, vi)) _W (uk, vk)_ _dv_

_≤_ _[′]_ _−_ _[′]_ 

Xi=1 Z []jY=1 _k=Yi+1_ _v∈V_

  [Y]


(12)


Here, each absolute value term in the sum is bounded by the cut norm ∥W − _W_ _[′]∥□_ if we fix all
other irrelavant variables (everything except ui and vi for the i-th term), altogether implying that

_| t(F, W_ ) − _t(F, W_ _[′])| ≤_ e(F )||W − _W_ _[′]||□_ (13)

■

**Lemma 2 (Corollary 10.4 in Lov´asz & Szegedy (2006)) Let W be a graphon, n ≥** 1, 0 < ε < 1,
_and let F be a simple graph, then the W_ _-random graph G = G(n, W_ ) satisfies


_ε[2]n_
P ( _t(F, G)_ _t(F, W_ ) _> ε)_ 2exp
_|_ _−_ _|_ _≤_ _−_ 8v(F )[2]


A.2 PROOF OF THEOREM 1


(14)


We have the mixed graphon WI = λWG + (1 − _λ)WH. Let W = WI, W_ _[′]_ = WG, and F = FG in
Lemma 1, we have,


_|t(FG, WI) −_ _t(FG, WG)| ≤_ e(FG)||WI − _WG||□_
_|t(FG, λWG + (1 −_ _λ)WH) −_ _t(F, WG)| ≤_ e(FG)||λWG + (1 − _λ)WH −_ _WG||□_
_≤_ e(FG)||(1 − _λ)(WH −_ _WG)||□_


(15)


Recall that the cut norm ∥W _∥□_ = supS,T ⊆[0,1]


_S_ _T_ _[W]_
_×_


-----

obviously, suppose α ∈ R, we have

_∥αW_ _∥□_ = _S,Tsup ⊆[0,1]_


_W_ [=][ α][∥][W] _[∥][□]_ (16)
_S×T_


_αW_ [=] sup
_S×T_ _S,T ⊆[0,1]_


Based on Equation 15 and Equation 16, we have


_|t(FG, λWG + (1 −_ _λ)WH) −_ _t(FG, WG)| ≤_ e(FG)||(1 − _λ)(WH −_ _WG)||□_ (17)
_≤_ (1 − _λ)e(FG)||WH −_ _WG||□_

Similarly, let W = WI, W _[′]_ = WH and F = FH in Lemma 1, We can also easily obtain

_|t(FH, λWG + (1 −_ _λ)WH) −_ _t(FH, WH)| ≤_ _λe(FH)||WH −_ _WG||□_ (18)
Equation 17 and 18 produce the upper bound in Theorem 8. ■

A.3 PROOF OF THEOREM 2

Let F and W be the discriminative motif FG and the mixed graphon W in Lemma 2, we will have
_I_


_ε[2]n_
P ( _t(F_ _, G)_ _t(F_ _, W_ ) _> ε)_ 2exp
_|_ _I_ _−_ _I_ _I_ _|_ _≤_ _−_ 8v(F )[2]
 _I_

which produces the result in 9.

A.4 GRAPHONS ESTIMATION BY STEP FUNCTIONS


(19)


The proof follows Xu et al. (2021). A graphon can always be approximated by a step function in the
cut norm (Frieze & Kannan, 1999).

Let = ( 1, .., _K) be a partition of Ω_ into K measurable sets. We define a step function W :
_P_ _P_ _P_ _P_
Ω[2] _7→_ [0, 1] as

_K_
_W_ (x, y) = (20)
_P_ _k,k[′]=1_ _[w][kk][′]_ [1][P][k][×P][k][′][ (][x, y][)][,]
X

where eachotherwise it is 0. The weak regularity lemma wkk′ ∈ [0, 1] and the indicator function Lov´asz 1 (2012Pk×P) shown below guarantees that everyk′ (x, y) is 1 if (x, y) ∈Pk × Pk′,
graphon can be approximated well in the cut norm by step functions.

**Theorem 3 (Weak Regularity Lemma (Lemma 9.9 in (Lov´asz, 2012)) ) For every graphon W**
_and K ≥_ 1, there always exists a step function W with |P| = K steps such that

2
_∥W −_ **W∥□** _≤_ _√log K_ _W_ _∥L2_ _._ (21)
_∥_

B EXPERIMENTS SETTING

B.1 EXPERIMENTAL SETTING

To ensure a fair comparison, we use the same hyperparater for modeling training and the same
architecture for vanilla model and other baselines. For model training, we use the Adam optimizer(Kingma & Ba, 2015). The initial learning rate is 0.01 and will drop the learning rate by half
every 100 epochs. The batch size is set to 128. We split the dataset into train/val/test data by 7 : 1 : 2.
The best epoch are determined by the best validation accuracy. Note that best test epoch is selected
on a validation set. We also report the test accuracy on ten runs.

For architecture of graph neural networks, the details are listed as follows,

-  GCN (Kipf & Welling, 2016). Four GNN layers and global mean pooling are applied. All the
hidden units is set to 64. The activation is ReLU (Nair & Hinton, 2010).


-----

-  TopKPool (Gao & Ji, 2019). Three GNN layers and three TopK pooling are applied. A therelayer percetron are adopted to predict the labels. All the hidden units is set to 64. The activation
is ReLU (Nair & Hinton, 2010).

-  GIN (Xu et al., 2018). We apply five GNN layers and all MLPs have two layers. Batch normalization (Ioffe & Szegedy, 2015) is applied on every hidden layer. All hidden units are set to 64.
The activation is ReLU (Nair & Hinton, 2010).

For hyperparemeter in G-Mixup, we generate 20% more graph for training graph. The graphons are
estimated based on the training graphs. We use different λ ∈ [0.1, 0.2] to mix up the graphon and
generate synthetic with different strength of mixing up.

B.2 EXPERIMENTAL SETTING OF ROBUSTNESS

The graph neural network adopted in this experiment is GCN, the architecture of which is as
above. For label corruption, we randomly corrupt the graph labels with different corruption ratio
10%, 20%, 30%, 40%. For topology corruption, we we randomly remove/add edges with different
corruption ratio 10%, 20%, 30%, 40%. The dataset for topology corruption is REDDIT-BINARY.

B.3 VISUALIZATION OF GRAPHONS ON MORE REAL-WORLD DATASET

_G-Mixup explores five graphon estimation methods, including sorting-and-smoothing (SAS)_
method (Chan & Airoldi, 2014), stochastic block approximation (SBA) (Airoldi et al., 2013),
“largest gap” (LG) (Channarond et al., 2012), matrix completion (MC) (Keshavan et al., 2010) and
the universal singular value thresholding (USVT) (Chatterjee et al., 2015). We present the estimated
graphon by LG in Figure 2. Here we present more visualization of graphons on IMDB-BINARY,
REDDIT-BINARY and IMDB-MULTI dataset. An obvious observation is that graphons of different
classes of graphs are different. This observation further validates the divergence of graphon between
different classes of graphs.

**LG** **MC** **SAS** **SBA** **USVT**

**IMDB-B**
**REDDIT-B**
**IMDB-M**


Figure 5: The estimated graphon on various dataset with different graphon estimation methods.


-----

C ADDITIONAL EXPERIMENTS FOR REBUTTAL

In this appendix, we conduct additional experiments to further investigate the proposed method. The
additional experiments include 1) more graph neural networks ((DiffPool, MincutPool, GMT)) in
Appendix C.1, 2) molecular property prediction task with OGB datasets in Appendix C.2, 3) experiments on the impact of the nodes number of generated graphs in Appendix C.3 and 4) experiments
on the performance of GCN with different layers in Appendix C.4.

C.1 EXPERIMENT ON MORE GRAPH NEURAL NETWORKS (DIFFPOOL, MINCUTPOOL,
GMT)

To further validate the effectiveness of G-Mixup on more graph neural networks, we experiment
with DiffPool (Ying et al., 2018), MincutPool (Bianchi et al., 2020) and GMT (Baek et al., 2020).
For GMT, we use their released code and the recommended hyperparameters for their used datasets
(D&D, MUTAG, PROTEINS, IMDB-B, IMDB-M) in their paper. To reproduce its results, we use
their official code and the above datasets. The results are presented in Tables 5 and 6.

The details of backbones are listed as follows:

-  DiffPool (Ying et al., 2018) is a differentiable graph pooling methods that can be adapted to
various GNN architectures, which maps nodes to clusters based on their learned embeddings.

-  MincutPool (Bianchi et al., 2020) is a differentiable pooling baselines. It learns a clustering
function that can be quickly evaluated on out-of-sample graphs.

-  GMT (Baek et al., 2020) is a multi-head attention based global pooling layer to generate graph
representation, which captures the interaction between nodes according to their structure.

Our main observations are: Observation 7: G-Mixup improves the performance of DiffPool and
**MincutPool on various datasets. From Table 5, our proposal gains 7 best performances among**
8 reported accuracies, which substantially improve the performance of DiffPool and MincutPool.
**Observation 8: G-Mixup can significantly improve the performance of GMT. Table 6 shows**
that G-Mixup outperform all the baselines on all datasets. Overall, G-Mixup outperform vanilla,
Dropedge, ManifoldMixup by 1.44%, 1.28%, 2.01%, respectively. This indicates the superiority of
_G-Mixup for graph classification task._

Table 5: Performance comparisons of G-Mixup with DiffPool and MincutPool on different datasets.
The metric is classification accuracy and its standard deviation. The best performance is in boldface.

Backbone Method IMDB-B IMDB-M REDDIT-B REDDIT-M5k

DiffPool vanilla 71.68±3.40 47.75±2.34 78.40±4.38 31.61±5.95
w/ Dropedge 69.16±2.51 49.44±2.50 76.00±5.50 34.46±6.80
w/ NodeDropping 70.25±3.01 46.83±1.34 76.68±2.57 33.10±5.53
w/ Subgraph 69.50±2.16 46.00±4.43 76.06±2.81 31.65±4.43
w/ ManfoldMixup 66.50±4.04 45.16±4.63 78.37±2.29 34.46±6.80
w/ -Mixup **73.25±3.89** **50.70±2.79** **78.87±2.27** **38.42±6.51**
_G_

MincutPool vanilla 73.25±3.27 49.04±3.57 84.95±3.25 49.32±2.67
w/ Dropedge 69.16±2.51 49.66±1.73 81.37±1.59 47.20±1.10
w/ NodeDropping 73.50±3.89 49.91±2.83 85.68±2.04 46.82±4.60
w/ Subgraph 70.25±1.84 48.18±1.10 84.91±2.50 49.22±2.49
w/ ManfoldMixup 70.62±2.09 49.96±1.86 85.12±2.29 47.20±1.10
w/ -Mixup **73.93±2.84** **50.29±2.30** **85.87±1.37** **50.12±2.47**
_G_

Table 6: Performance comparisons of G-Mixup with GMT on different dataset. The metric is the
classification accuracy and its standard deviation. The best performance is in boldface.

Backbone Method D&D MUTAG PROTEINS IMDB-B IMDB-M

GMT vanilla 78.29±5.77 82.77±6.30 74.59±5.29 73.60±3.87 50.73±3.03
w/ Dropedge 78.37±4.17 82.22±8.88 74.32±5.42 73.40±3.85 50.73±3.09
w/ ManfoldMixup 77.69±3.81 82.22±10.48 74.41±3.97 73.70±3.79 49.93±3.49
w/ -Mixup **79.57±3.69** **84.44±8.88** **75.13±5.06** **74.70±3.76** **51.33±3.52**
_G_


-----

C.2 EXPERIMENT ON MOLECULAR PROPERTY PREDICTION

We experiment on molecular property prediction task (Hu et al., 2020), including ogbg-molhiv,
ogbg-molbace, ogbg-molbbbp. In these dataset, each graph represents a molecule, where nodes are
atoms, and edges are chemical bonds. We adopte official reference graph neural network backbones
(gcn, gcn-vitual, gin, gin-vitual) as our backbones, and we generate the edge attributes randomly
for synthetic graphs. The results are presented in Table 7. Observation 9: G-Mixup can improve
**the performance of GNNs on molecular property prediction task with the experimental setting**
**for a fair comparison. Table 7 shows that G-Mixup gains 9 best performances among 12 reported**
AUCs.

Table 7: Performance comparisons of G-Mixup on molecular property prediction task. The metric
is AUROC [3] and its standard deviation. The best performance is in boldface.

**Backbones** **Mehtods** **ogbg-molhiv** **ogbg-molbbbp** **ogbg-molbace**

GCN vanilla 76.24±0.98 68.05±1.52 80.36±1.56
w/ Dropedge 75.93±0.76 68.02±0.95 80.22±1.59
w/ ManifoldMixup 76.24±1.40 68.36±2.05 80.46±2.05
w/ G-Mixup **76.29±0.80** **68.45±0.84** **80.73±2.06**

GCN-virtual vanilla 75.62±1.65 65.13±1.11 **74.49±3.04**
w/ Dropedge 74.64±1.32 66.46±1.61 69.75±3.47
w/ ManifoldMixup 74.04±2.06 65.51±1.74 73.10±4.97
w/ G-Mixup **76.56±0.80** **67.20±1.30** 73.55±4.79

GIN vanilla 77.08±1.96 68.42±2.31 75.91±1.01
w/ Dropedge 75.77±1.75 66.16±2.96 70.50±6.24
w/ ManifoldMixup 75.73±1.25 68.15±2.04 77.44±4.13
w/ G-Mixup **77.14±0.45** **69.28±1.24** **77.79±3.34**

GIN-virtual vanilla **77.52±1.56** 67.10±2.10 **74.19±4.99**
w/ Dropedge 76.83±1.11 68.87±1.17 72.20±3.37
w/ ManifoldMixup 76.51±2.22 68.04±2.87 74.17±1.38
w/ G-Mixup 77.09±1.07 **70.02±1.68** 73.53±3.98

C.3 WHAT IS THE IMPACT OF NUMBER OF NODES OF GENERATED GRAPHS?

We investigate the impact of number of nodes of generated synthetic graphs by G -Mixup and report
the results in Figure 6. Specifically, G -Mixup generates synthetic graphs with different the numbers
(hyperparameters K) of nodes and use them to train graph neural networks. From Figure 6, we can
see that average number of nodes in the original graphs is a better choice for hyperparameters K for
_G -Mixup, which is accords with intuition._

C.4 HOW G -MIXUP PERFORM WHEN GRAPH NEURAL NETWORK GOES DEEPER?

We investigate the performance of G-Mixup when the GCN goes deeper and report the results in
Figure 7. We experimented with different numbers (2−9) of layers to investigate the performance of
_G -Mixup. Observation 10: G-Mixup improves the performance of graph neural networks with_
**different layers. The left figure in Figure 7 shows G -Mixup gains better performance for IMDB-**
BINARY dataset while the depth of GCNs is 2 − 6. The performance with deeper GCN (7 − 9) are
comparable to baselines, however, the accuracy of deeper GCN is much lower than shallow ones.
The right figure in Figure 7 shows G -Mixup gains better performance by a significant margin for
REDDIT-BINARY dataset while the depth of GCNs is 2 − 9. This validates the effectiveness of
_G-Mixup when graph neural network goes deeper._

3Area Under Receiver Operating Characteristic


-----

|Col1|Col2|Col3|Col4|Col5|Col6|
|---|---|---|---|---|---|
|||||||
|||||||
|||||||
|||||||
|||||||
||||Avg.|#Nodes of||
||||Origi|nal Graphs||
|||||||

|Avg. #Nodes of Original Graphs|Col2|Col3|Col4|Col5|
|---|---|---|---|---|
||||||
||||||
||||||
||||A|vg. #Nodes of|
||||O|riginal Graphs|


**IMDB-BINARY** **REDDIT-BINARY**

**Avg. #Nodes of** **Avg. #Nodes of**
**Original Graphs** **Original Graphs**


Figure 6: The impact of the node numbers of generated synthetic graphs on IMDB-BINARY and
REDDIT-BINARY datasets. The red vertical line indicates the average number of all the original
graphs. The blue line represents that classification accuracy with different number of nodes of
generated graphs. Obviously, the accuracy reach the maximum values around the red line on both
two datasets

**IMDB-BINARY** **REDDIT-BINARY**


Figure 7: The performance of G-mixup using GCNs with different depth on IMDB-BINARY and
REDDIT-BINARY. This figure show that G-Mixup consistently improve GCN when it goes deeper.


-----

