G-Mixup: Graph Augmentation for Graph Classification
Authors: Xiaotian Han
Zhimeng Jiang
Ninghao Liu
Xia Hu
Venue: ICLR 2022 Submitted (2022)
Keywords: graph augmentation
mixup
graph classification
graphon

Abstract: This work develops \emph{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 $\mathcal{G}$-Mixup 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 new graphons.

Under review as a conference paper at ICLR 2022
G- 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 improv- ing the generalization and robustness of neural networks by interpolating features and labels of random two samples. Traditionally, Mixup can operate on regu- lar, grid-like, and Euclidean data such as image tabular data. However, it is challenging to directly adopt Mixup to augment graph data because two graphs typically: have different numbers of nodes; 2) are not readily aligned; and 3) have unique topologies in non-Euclidean space. To this end, we propose G- Mixup 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 graphon. Then, instead of directly manipu- lating graphs, we interpolate graphons of different classes in the Euclidean space to get mixed graphons, where the synthetic graphs are generated through sam- pling based on the mixed graphons. Extensive experiments show that G-Mixup substantially improves the generalization and robustness of GNNs.
INTRODUCTION
Recently deep learning has been widely adopted to graph analysis. Graph Neural Networks (GNNs) (Wu 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., DropE- dge (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 aug- ment 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- -raphh aug- mentation 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 vari- ants (e.g., Manifold Mixup (Verma al., 2019)), data augmentation methods, have been theoret- ically 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 lan- guage 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 Λx; + (1 A)x;; Nnew = xy, + (1 A)y,, where (x,, y;) and (x,, are two samples drawn at random from training data and the target y are one- hot 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 in- stances 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 divergent. The topologies of a pair of graphs from different classes usually different while the topologies of those from the same class are usually similar, thus make challenging directly adopt the Mixup strategy graph data.

---

Under review as a conference paper at ICLR 2022
Tarapben celmation
grgaphonn misup
graph
(G,. Ga....GG. with label (1,0)
We
sampling
grppho estimzionn
Wi 0.5 Wa + 0.5 Wa
I (Iul2.. .4) (0.5, 0.5)
(M1, May H.) (0,
W
Figure I: An overview of G-Mixup. The task is binary graph classification. We have two classes of graphs G and with different topologies (g has two communities while has eight communities). and H have different graphons. We mix up the graphons Wg and WN to obtain mixed graphon Wz, and then sample new graphs from the mixed graphon. Intuitively, the synthetic graphs have two major communities and each of which has four aub-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 augmenta- tion method, to mix up graph data based on graphons. The graphs within class have the same generator (i.e., graphon). We mix up the graphons of different classes and then generate synthetic graphs. Informally, graphon can be thought of probability matrix (e.g., the matrix Wa and Wi in Figure !), where W(i,) j) represents the probability of edge between node and j. The real- world graphs can be regraded as generated from graphons. In this way, we can mix 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 gener- ate 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 I with example. Given two graph training sets = (G1, G2. G and H = {Hi, H2, 1....... H&} with different labels and distinct topologies (i.e.. G has two communities while H has eight communities), respectively from G and H. We then mix up the two graphons and obtain a mixed graphon Wz- After that, sample synthetic graphs from Wz additional training graphs. The generated syn- thetic graphs have two major communities and each of them have four sub-communities, which is mixture of the two graph sets. It thus shows that G-Mixup is capable of mixing up graphs.
classes of
estimate graphons Wg and WN
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 the- oretically prove that the synthetic graph will be the mixture of the original graphs, where the key topology (i.c., 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. Ex- tensive 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, 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 (G) and E(G) to denote its nodes and edges, respectively. The number of nodes is v(G) IVG)), and the number of edges is e(G) [E)) We use G, H, to denote graphs and G, I to denote graph set. Yg E RC denotes the label of graph set g, where C is number of classes of graphs. A graph could contain some interesting and frequent patterns and subgraphs which are called motifs. The motifs in graph G is denoted as FG. The set of motifs in graph is denoted Fz. We denotes the graphon of graph set G. W denotes the step
2

---

Under review as a conference paper at ICLR 2022
function. Unifio, |o denotes the uniform distribution between 0 and 1. Bern(-) denotes the Bernoulli distribution. G(n, W) denotes the random graph with nodes based on graphon W.
2.2 GRAPH HOMOMORPHISM AND GRAPHONS
Graph Homomorphism. A graph homomorphism is an two graphs, i.e., mapping adjacent vertices in one graph to adjacent vertices in the other. Formally, a graph homomorphism o: F + G is a map from (F) to V(G). where if {u, o} E E(F), then {ō(u), <(v)} E EG)). 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 +, homo+., G) 2 E(G) if graph H is -, and hom A, G) is six times the number of triangles in G. There are in total [V()) mappings from H to G, but only some of them are homomorphisms. Thus, we define homomorphism density measure the relative frequency that the graph H appears in graph G:
mapping between
t(H, G) hom H, G)
[V
For example, G) = 1,
1, G) = 2
Graphon. A graphon (Airoldi al., 2013) is continuous, bounded and symmetric function W [0, 10. -> [0, 1] which may be thought of as the weight matrix of a graph with infinite number of nodes. Then, given two points u, U2 [0, 1), (i,, represents the probability that nodes i and 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 graphs can be easily extended a degree distribution function in graphons. which is characterized by its graphon marginal dw (a) = So W W(x, y)dy. Similarly, the concept of homomorphism density can be naturally extended from graphs to graphons. Given arbitrary graph motif F, its homomorphism density with respect to graphon W is defined by
f
(F (F.W))
II (JEE(F)
W(),) II dx..
(EV(F)
For example, the edge density of graphon W is t( W) = So.1P W(x, y) drdy, and the triangle density of graphon W is ((A, W) = So.ip W(x,, W) (z, 2) (v, dædydz.
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-ae approach for graph classification. Without loss of generalization, we present the formal expression of graph convolution network (GCN) (Kipf & Welling, 2016). The forward propagation at k-tth layer is described as the following:
(k) a,
(G) ((1) (hia-" :j JENO))
h (k) COMBINE(A) (n. (R-1) a.
(k)
(1)
where h (k) E Ra is the intermediate representation of node i the k-th layer, (ii) denotes the neighbors of node i. (-G(-) is an aggregation function to collect embedding representations from neighbors, and COMBINE(() combines neighbor representation and its representation (k 1) layer followed by nonlinear transformation. For graph classification, graph-level representation is obtained by summarizing all node-level representations in the graph by readout function:
bgg READOUT (fn.*) (k) : & F((G))
ý = soot
(2)
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), ,) he is the representation of graph G, and ÿ E IRC 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 analy- sis of graph generation via graphon interpolation from the graph homomorphism density perspective.
3

---

Under review as a conference paper at ICLR 2022
3.1 g GMIIXUP
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 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:
9 + Wg, H WR.
(3)
Graphon Mixup:
WI XWg + (1 - X)WR,
(4)
Graph Generation:
(11 12. ... 4 1id G(k, Wz), Yz = Aye + A)yR
(5)
Label Mixup:
(6)
where Wg, WH are graphons of the graph set G and H. The mixed graphon is denoted by Wz, and A E [0, 1] is the trade-off hyperparameter to control the contributions from different original graphs for interpolation. The set of synthetic graphs generated from Wz is I = 12, , The Ye E RC and yH RC are vectors containing ground-trui labels for graph G and H respectively. The label vector of a generated graph in is set as yı E RC, where C is the total classes of graphs.
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 G {G1, G2. G with label yG. and H. = {H1 H2. ... Hy}} with label Yи- Graphons Wg and Wx are estimated from graph set G and H. then we mix them up though linearly interpolating two graphons and their training labels and obtain Wz and yr. The synthetic graph set I is sampled based on Wz, which will be used as additional training graphs.
3.2 IMPLEMENTATION
In this section, we introduce the details of the implementation of estimating graphon from the ob- served graphs and generating synthetic graphs in the real-world scenario.
Graphon Estimation and Mixup. Estimating graphons from observed graphs is prerequisite for G-Mixup, however, it is intractable because graphon is an unknown function without closed- form solution in real-world graphs. Therefore, we use step function (Lovász, 2012; Xu et al., 2021) as an approximation of graphon. 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., de- gree) and then estimates the step function from all the aligned adjacency matrices. The step function estimation methods used includes sorting- sorting-and-sing and-smoothing (SAS) method (Chan & Airoldi, 2014), stochastic block approximation (SBA) (Airoldi et al., 2013), "largest gap" (LGG (Channarond et al., 2012), matrix completion (MC) (Keshavan et al., 2010), universal singular value threshold- ing (USVT) (Chatterjee et al., 2015). Formally, a step function W [0, 1J² + [0, 1] is define as WF(r, Σx WEK Lp xar (I, v), where P (Pi..., Px) denotes the partition of [o, 1] into K adjacent intervals of length 1/K, Wak [0. 11, and indicator function 1 (x, y) equals to if if. v/ E Pk x Pkr and otherwise it is O. Essentially, the step function can be seen as a matrix W = [[w E [0, x 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 G (G1, G2. .G) and H {Hi, H2, H&&) with dif- ferent labels, we estimate their step functions WG E RRxK and W E RR We let K be the average number of nodes in all graphs. For multi-class classification, we first estimate the step func- tion for each class of graphs and then randomly select two to perform mix-up. The resultant step function is Wz AWg g + (1 (1-X) Wn
WHE E R. Kxk which serves as the generator of synthetic graphs.
Becauus weak regularity lemma of graphon (Frieze & Kannan, 1999) indicates that an arbitrary graphon be approximated well by step function. Detailed discussion is in Appendix A.4.
4

---

Under review as a conference paper at ICLR 2022
Synthetic Graphs Generation. A graphon W provides distribution to generating arbitrarily sized graphs. Specifically, a k-node random graph Gkk, Wr) can be generated following the process: up) iid ~ Bern(W (u;, uz)), Vi, E [k].
U1...., Uk iid Uniffo.11. (G(k,
Since we only estimate the step function W to approximate the graph W. we set W(u,, új) = Wr[LI/u,], [1/u,]], and L-] 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 = [a,5] E {0, [0,1)** 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) oi 1}. A set of synthetic graphs can be generated by conducting the above process independently multiple times. For node features, we generate them of synthetie 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- tional complexity of the proposed G-Mixup. The major additional computation costs come from graphon estimation and graph gen- eration. For graphon estimation, suppose we have M graphs and each of them has N nodes and E edges, and estimate step function with K partitions to approximate a graphon, the complexity of used graphon estimation methods (Xu et al., 2021) is in Table 1. For graph generation, suppose we need to generate K graphs with N nodes, the computational complexity is (KKN) for node genera- tion and O
Table 1: Computational com- plexity of graphon estima- tion (Xu et al., 2021)
Mehhod
Complexity
MC
(NN)) O(N7)
USVT
LG
O N O(MKN log N)
SBA
SAS O(MN Iog N K log K3)
O(K K (KN22 for edge generation, so the overall complexity of graph generation is ((K
4 THEORETICAL JUSTIFICATION
In the following, we will theoretically prove that, the synthetic graphs generated by G-Mixup will be 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 (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 motifss Fg is the set of the discriminative motif of every graph the graph set 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 G has finite set of discriminative motifs Fg. The goal of graph classification is to filter out structural noise in graphs (Fox & Rajamanickam, 2019) and recognize the key typologies (discriminative motifs) to prediet the class label. For example, benzene (a compound in chemistry) is distinguished by the discriminative motif E3 (benzene ring).
4.1 WILL DISCRIMINATIVE MOTIFS PG AND Fx EXIST IN AW + (1- (0-=)) ?
We answer this question by exploring the difference in homomorphism density of discriminative motif' between the original graphon and mixed graphon. We propose the following theorem.
Theorem Given two sets of graphs G and H. the corresponding graphons are Wg and WH. and the corresponding discriminative motif set Fg and FR. For every discriminative motif F& E Fg and Fxt E Fu, the difference between the homomorphism density of Fg/Fu in the mixed graphon Wz = AWg + (1- W) n and that of the graphon WH/Wg is upper bounded by [b(Fg, Wz) t(FF, Wg)l < (1 >)e(FF))lWH Wgllo It(FH, Wz) - t(Fn. Wxd) I )e(Fx)llWx - Wyllm
(8)
where e(F) is the number of nodes in graph F and ||W Wg ll is the cut norm ?
Details about norm are in Appendic A.1
5

---

Under review as a conference paper at ICLR 2022
Proof Sketch. The proof follows the derivation of Counting Lemma for Graphons (Lemma 10.23 in Lovász (2012)), which relates the homomorphism density and the cut distance I|W - WWll of graphons. Specifically, we take the two graphons in this Lemma to deduce the bound of the difference of homomorphism densities of Wz and W W Detailed proof are in Appendix A.2.
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 X, the edge number e(fo)/ (e(())((F)))) and the cut norm I|W We -.. Since the e(Fo)/e norm || Wa [ are decided by the dataset can be regraded as a constant), the difference in homomorphism densities will be decided by A. On this basis, the corresponding label of the graphon is set to Λyg + (1 AjyH. Therefore, G-Mixup can preserve the different discriminative motif's of the two different graphons into one mixed graphon.
and the cut
4.2 WILL THE GENERATED GRAPHS FROM GRAPHON WI PRESERVE THE MIXTURE OF 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 Let W1 be the mixed graphon, n 2 1, 0 <E E < 1, and let F1 be the mixed discrimina- live motif, then the Wr-random graph G (n,, Wz) satisfies
E2n
P P( -ftcGG))--F/i...ee Wz) s) S 2exp
8v(FF)²
Theorem 2 states that for any nonzero specified margin E, 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(Fz, G) z 1(Fz. Wz) with high probability. In other words, it reads the synthetic graphs will preserve the discriminative motif of the mixed graphon with 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 randomly perturb the edges to improve the GNNs, inlcuding DropEdge (Rong et al., 2020), Graphon-based edge pertur- bation (Hu et al., 2021). DropEdge drops graph edges independently with specified probability, aiming to prevent over-smoothing and over-fitting issues in GNNs. Graphon-based edge perturba- tion (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 al., 2021) are spe- cial cases of G-Mixup while setting different hyperparameter X. i) G-Mixup will degenerate into Graphon-base
edge perturbation, while = 0 in Equation 4. The mathematical expression is Wz WH: {T, T2, T2,,.. T&) iid G(k, Wz), yz Yu- ii) G-Mixup will degenerate into DropEidge, while setting À = 0 and masking graphons with adjacency matrix A in Equation 4. The expression is iid G(k, Wz). = YH, where @ is element- wise multiplication. Wz A の WH: (1, .2.... ................................ J&]
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. Interpo- lating 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, G- Mixup 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.

---

Under review as a conference paper at ICLR 2022
5 EXPERIMENTS
We evaluate the performance of the proposed G-Mixup this section. First, we visualize graphons and graph generation results to investigate what G-Mixup actually do real-world datasets in Sec- tion 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, well 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 examine whether there different graphons for different classes of graphs, Observation 1: difffrrnt classes of graphs have different graphons in real-world dataset. shown Figure 2, the graphons of different class of graphs in one dataset are distinctly different. The graphons of IMDB- BODB-BINAERY in Figure 2 shows that the graphon of class has larger dense area, which indicates that the graphs this class have a more large communities than the graphs of class O. 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 solid foundation for generating the mixture of graphs by mixing up graphons.
Clack
Clacc
Chosk
Clack
Clacc
60
IMDR-BINARY
REDDIT-BINARY
INDE-MULTII
Figure 2: Estimated graphons IMDB-BINARE REDDIT-BINARY, and IMDB-MULTY Obvi- ously, 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 visualized in Figure 3(a)(b) and Figure (()), respectively. Figure demonstrates that mixed graphon 0.5 Wg g + 0.5 W'e is able generate graphs with high-degree node and dense subgraph, which can be regarded as the mixture of graphs with one high-degree node and two high-degree nodes. It validates that M-xixup prefer preserve the discriminative motifs from the original graphs.
origink graphts
graphe
graphin
yraple
grophun
generatel graqut
(i) graple genraiad Jmm 1y Ws 00 O.
()) gopps geseuted +1*W,
graphe geneaced
Figure 3: The visualization of generated synthetic graphs dataset REDDIT-BINARY. The first row the original graphs in the dataset while the second row 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 class have one high-degree node while graphs of class have two marked with
in (a) and (b) ). (c)/(d) shows graphs generated with the mixed graphon (1 Wo + * W, ) (0 * Wo + 1 * W1). which have one/two high-degree node/nodes (marked with in (c) and (d)) because the mixed graphon only contains Wo/W, The synthetic graphs generated from (0.5 * Wo + 0.5 * W1) the mixture graphs of class 0 and class 1, which appears high-degree node and dense subgraph marked with and in (e), respectively). The visualization shows that synthetic graphs are the mixture of the original graphs.
7

---

Under review as a conference paper at ICLR 2022
IMDB-BINARY
IUDL-MULTI
REDDIT-BINARY
REDDIT-MULTI-SK
(Cmmime trah
weRk. m
M000 Trale
6300
1.5
Beak J00
6.60
Cluss
0:20
Epuch
Epoch
Epach
Figure 4: The traininngvallidationness curves on IMDB- IMDE-BINARY, IMDB-MULTI, REDDIT-
BINARY and REDDIT-MULTI-5E with GCN 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.I. Experiments with more backbones (Diff-
Pool, MincutPool, GMT) and molecular property prediction are in Appendix C. and Appendix C.2.
Dataset
IMDB-B
IMDB-M REDDIT-B REDD-M5K REDD-MI2K
#graphs
1000
1500
2000
4999
11929
#classes
2
3
2
5
11
favg.nodes
19.77
13.00
429.63
508.52
391.41
#avg.edges
96.53
65.94
497.75
594.87
456.89
GCN
vanilla
1::55
48.79
78.82+1.33
4..07
46.90.10.3
w/ Dropedge
72.50+a31
49.08+1.89
81.25+8.15
51.35
47.08+0.5
w/ Dropping
72.00+400
48.58
79.25
49.35=1.8
47.93+4064
w/ Subgraph
68.5014476
49.58
74.33
1..70
47.49
w/ ManfoldMixup
72.83
49.50
75.75
49.82.2088
46.92:1105
w/ G-Mixup
72.87+3.5
51.30
89.81
51.51
48.06
GIN
vanilla
71.55
48.83
92.59
55. 10.1 =1002
50.23
w/ Dropedge
22.20
48.83
92.00
55.10=o.44
49.77=176
w/ Nodepnopping
72.16100.8
48.33 1:098
90.25 1:.98
53.26
49.95
w/ Subgraph
68.50
47,25 1:378
90.33
54.60
49.67
w/ ManfoldMixup
70.83+1.04
49.88
90.75+
54.95=0066
49.81 +0.0
w/ G-Mixup
71.94+3300
50.46+1.49
92.90+4.87
55,49
50.50+0.41
TopKPool vanilla
50.57 72.37
90.30
45.07
45.06
w/ Dropedge 71.75+2.18
48.75 18.75 #:2.4
88,96+1990
47.43
44.56+1141
w/ Nroepng
69.16++1.4
48.50
81.33
46.15 +2.28
44.49+115
w/ Subgraph 67.83
50.83
86.08
45.75
18.18
w/ ManfoldMixup
71.83
51.22
87.58
45.60
43.81
w/ G-Mixup
72.80
51.30
90.40
46.48
43.72.
5.3 CAN M-XIXUP IMPROVE THE PERFORMANCE AND GENERALIZATION OF GNNs?
To validate the effectiveness of our proposal, we experiment to compare the performance with vari- ous backbones of GNNs on various datasets, and summarize results in Table 2 as well as the training curves in Figure 4. Our main observations 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 effective- ness 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, proposal substantially is able 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 vrain/validtiionnesst
Observation 3: G-Mixup
significantly im-
8

---

Under review as a conference paper at ICLR 2022
eurves 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 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
more robust 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 different corruption ratio.
Table 4: Robustness to topology corruption with different corruption ratio.
Modab
Mebood
30%
Medel
Nithhod
30%
IMDB-B
nailk
72
55.21=0.755
Rasening olgo
vaiila
o7 07,9043333
6496-28877
(671
Despodac
72/01--244
Dnspecigs
24.0--226
Wi Munisstttteapp
in Statressitspp
Masg
72.66-3108
0A87-5441
$2.55
G-Mlicap
7L12+-747
0746+1300
0625--128
REDDIT
nuilk
13
75:68-2.75
68.12::81
46.50:20000
Adlingg odye vailla
7231
120002900
Dospodac
13.25+-1226
12:05-1422
46.30--1..00
46:50-000
Drspecias
7055-14477
71:6+113
1000-15)
Xi Manisaattteep
11.00:100
06:0020000
in Statreshitspp
23:12200
71.00220
11:11:1000
Misap
G-Micap
82211-111
6 RELATED WORKS
Graph Data Augmentation Graph neural networks (GNNs) also achieve the state-of-the-an per- formance on graph classification task (Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017: Xu et al., 2018; Zhang et al., 20. In parallel, graph data augmentation methods are also proposes to improve the performance of GNNs. There are three categories of graph data augmen- tation, 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 model- independent 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ász, 2012; Lovász & 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 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.
(SAS) method (Chan & Airoldi, 2014), stochastic
7 CONCLUSION
This work develops G-Mixup to augment graph data. Unlike image data, graph data 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 imput 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.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Edoardo M Airoldi, Thiago B Costa, and Stanley H Chan. Stochastic blockmodel approximation of graphon: Theory and consistent estimation. arXiv preprint urXiv:1311.17311 2013.
Marco Avella-Medina, Francesca Parise, Michael T Schaub, and Santiago Segarra. Centrality mea- sures for graphons: Accounting for uncertainty networks. IEEE Transactions on Network Science and Engineering, 7(1):520-531) 2018.
Jinheon Back, 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ászló Lovász, Vera T Sós, and Katalin Vesztergombi. Conver- gent sequences of dense graphs Subgraph frequencies, metric properties and testing, Advances in Mathematics, 219(6):10111183) 2008.
Stanley Chan and Edoardo Airoldi. A consistent histogram estimator for exchangeable graph mod- cls. In International Conference on Machine Learning, pp. 208-216, 2014.
Antoine Channarond, Jean-Jacques Daudin, Stéphane 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 1921:1991. 2019.
Alan Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175-22) 1999.
Hongyang Gao and Shuiwang Ji. Graph u-nets. arXiv preprint arXiv:1905.0511 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 classifi- cation: empirical study. arXiv preprint /905 00040, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances neural information processing systems, pp. 1024-1034, 2017.
Weihua Hu, Mathhis Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. In Ad- vances in Neural Information Processing Systems, volume 33, pp. 22112-22 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 Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from a few entries. IEEE transactions information theory, 2666))2980-9998. 2010.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. ICLR (Poster), 2015.
10

---

Under review as a conference paper at ICLR 2022
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 2016.
László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.
László Lovász and Balázs 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 leml, 2010.
Yu Rong. Wenbing Huang. Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. 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. 2020b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6448. 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 202/, 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 Leskovee, and Stefanie Jegelka. How powerful 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. Proceedings of the 32nd International Conference Neural Information Processing Systems, pp.
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 empiri- cal 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 Learning Representa- tions, 2021.
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Chirty-Seconal AAAI Conference on Artificial Intelligence, 2018.
11

---

Under review as a conference paper at ICLR 2022
Ziwei Zhang, Peng Cui, and Wenwu Zhu. Deep learning 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 aug- mentation for graph neural networks. In Proceedings of the AAAI Conference Artificial Intel- ligence, volume 35, pp. 11015-11023, 2021.
Yufei Zhao. Graph theory and additive combinatorics, 2019. URLhttps://yaaeeihaeee com/ gtac/.
Jiajun Zhou, Jie Shen, and Qi Xuan. Data augmentation for graph classification. In Proceedings of the 29th ACM International Conference 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 applica- tions. Al Open, 1:57-81, 2020b.
12

---

Under review as a conference paper at ICLR 2022
A PROOF OF THEOREM
In the appendix, we first present the preliminaries in Appendix A.I. And then we present complete proof for Theorem I and Theorem in Section A.3 and A.2, respectively,
A.1 PRELIMINARIES
Cut norm (Lovász, 2012; Zhao, 2019) is used to measure structural similarity of two graphons. The definition of cut norm as follow:
Definition The cut norm of grapon W is defined as
/ 9XT
|| sups.rc(o.1]
W(r, ((ddyy
(10)
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ász, 2012). It will be used to prove the Theorem
Lemma Let F be a simple graph and let W, W E W. Then
[MFF W) - (F,, W S e - W'
-
(11)
Proof of Lemma I. The proof follows Zhao (2019). For an arbitrary simple graph F, by the triangle inequality we have
|E(E, W) t(F, W'Il
II UEREEE
W (M,, 05)
II M.REE
W (wz, v5)
II de VEV
(12)
II W' (uj, 15) (W (us, 0z) W (uz, Uz))
II Am=++
W (ux, vk)
II VEV
du
Here, each absolute value term in the sum is bounded by the norm I| W' if we fix all other irrelavant variables (everything except and for the i-th term), altogether implying that
(FF W) t(F, W & e(F)] W'llo
(13)
Lemma (Corollary 10.4 in Lovász & Szegedy (2006)) Let W be a graphon, n 2 and let F. be simple graph, then the -random graph G G(n, W) satisfies
1,,0<<<1
22n
((I((F))) W) 8) S 2exp
(14)
8v(2F2
A.2 PROOF OF THEOREM I
We have the mixed graphon Wz XWg + (1- A)WH. Let W Wz. W Wg, and F Fg in Lemma 1, we have,
(FFe W2) - t(Fg, Wg) ((FF)) Wz Welln
[[Fg. AWg + (1 t(F, Wc) S c(Fg) (WW (1 - 2)W Wello (15)
< -Wali
Recall that the cut norm | Ia --s-uussss...
S Sxx W
13

---

Under review as a conference paper at ICLR 2022
obviously, suppose R, have
||a Ia = sup
aW
= sup S
a
W = =allWo
(16)
s,rg 0,1]
SxT
SxT
Based on Equation 15 and Equation 16, we have
IFFg, + ()WW) (Fss, Wo)l {c(Fg)]((1
Wo)llo
(17)
$ - F))(Fs) - Wollo
Similarly, W WI. V WH and F = Fx in Lemma 1, We can also easily obtain
[(FR. AWg + (1 x)Wx) (Fx, Wx)) z >e(F#)]lW== - Woll= Equation 17 and 18 produce the upper bound Theorem 8.
(18)
A.3 PROOF OF THEOREM 2
Let F and W be the discriminative motif Fg and the mixed graphon Wz in Lemma 2, we will have
(- E"N
P (I
- - Wz) > < 2exp
(<v((F))
(19)
which produces the result 9.
A.4 GRAPHONS ESTIMATION BY STEP FUNCTIONS
The proof follows Xu (2021). graphon can always be approximated by step function in the cut norm (Frieze & Kannan, 1999).
Let P (P1..., (k) be a partition of into K measurable sets. We define step function Wp Ω + [0, 1] as
Wz( Ex
- Wayr
(x,
(20)
where each way 10 and the indicator function 1 xP (x. is 1 if (x, Ps. Pvo otherwise it is O. The weak regularity lemma Lovász (2012) shown below guarantees that every graphon can be approximated well in the cut norm by step functions.
Theorem 3 (Weak Regularity Lemma (Lemma 9.9 in (Lovász, 2012))) For every graphon W and 2 there always exists a step function W with P| = steps such that
|W - Wlo <
W W
(21)
Vlog K
B EXPERIMENTS SETTING
B.1 EXPERIMENTAL SETTING
To ensure 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 opti- mizer(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 128. We split the dataset into train/val/test data by 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.
2.
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).
14

---

Under review as a conference paper at ICLR 2022
TopKPool (Gao & Ji, 2019). Three GNN layers and three TopK pooling are applied. A there- layer percetron are adopted to predict the labels. All the hidden units 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 normal- ization (loffe & 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, generate 20% graph for training graph. The graphons estimated based on the training graphs. We use different À E [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 coruptiion, corruption ratio 10%, 20%, 30%, 40%. The datasct for topology corruption is REDDIT-BINARE
randomly remove/add edges with different
B.3 VISUALIZATION OF GRAPHONS ON MORE REAL-WORLLD DATASET
G-Mixup explores five graphon estimation methods, including boann---nd-smmootine (SAS) method (Chan & Airoldi, 2014), stochastic block approximation (SBA) (Airoldi et al., 2013), "largest gap" (LG) (Chamnarond al., 2012), matrix completion (MC) (Keshavan 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
REDDIT-BINARY and IMDB-MULTI dataset. An obvious observation is that graphons of different classes graphs are different. This observation further validates the divergence graphon between different classes of graphs
MC
SAS
USVT
IMDI-M REDDIT-B IMD
Figure 5: The estimated graphon various dataset with different graphon estimation methods.
15

---

Under review as a conference paper at ICLR 2022
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 ((DifPPool, MineutPool, GMT)) in Appendix C.I, 2) molecular property prediction task with OGB datasets in Appendix C.2, 3) exper- iments the impact of the nodes number of generated graphs in Appendix C.3 and experiments on the performance of GCN with different layers in Appendix C.4.
C.I 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 presented in Tables and 6.
The details of backbones are listed as follows:
DiffPool (Ying al., 2018) 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 clustering function that can be quickly evaluated on out-of-sample graphs.
GMT (Back et al., 2020) is 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 shows that G-Mixup outperform all the baselines 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
DiftPool
vanilla
71.68
47.75
78. 38.40
31.61 $1.611550 25.5
Dropedge
69.1642.1
49.44=2.50
76.004550
34.4616.00
w/ NodeDro
70.25
46.83
76.68
33,10
w/ Subgraph
69.50
46.00
76.06
31.65
w/ Manuo
66.50
45.16
78.37+2.29
34.4626.00
w/ G-Mixup
73.25+33.9
50.70 22.9
78.87+227
38.42
MincutPool vanilla
73.25
49.04
84.95
49.32
Dropedge
69.164251
49.66
81.37+1.9 1..6
47.20
w/ Nooepng
73.50
49.91 #283
85. $5.68+204
46.82
Subgraph
70.25
48.18
42.51
49.22-2249
w/ ManfoldMixup
70.62+2.m
49.96_1.85
$5.1242200
47.20
w/ G-Mixup
73.93
50.29 2.30
85.87 1-1.37
50.12 #2.47
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
82.77
74.59
73.601387
50.73
w/ Dropedge
78.37
82,22++8.s
74.32
73.40
50.73
w/ ManfoldMixup
77.69
82.22+104s
74.41
73.70
49,93 +3.49
w/ G-Mixup
79.57 3.00
84.44
75.13
74.70
51.33 #3.22
16

---

9. This validates the effectiveness of Under review as a conference paper at ICLR 2022
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 molecule, where nodes atoms, and edges are chemical bonds. We adopte official reference graph neural network backbones (gen, gen-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 shows that G-Mixup gains 9 best performances among 12 reported AUCs.
Table 7: Performance comparisons of G-Mixup molecular property prediction task. The metric AUROC and its standard deviation. The best performance is in boldface.
Backbones
Mehtods
ogbg-molhiy
ogbg- gogg-mobbace
GCN
vanilla
76.24
68.05
80.36
w/ Dropedge
75,93
68.02
80.22.1..9
w/ ManifoldMixup
76.24
68.36=2.05
80,4612208
w/ G-Mixup
76.29 +0.00
68.45 -0.84
80.73+2206
GCN-virtual
vanilla
75.62:11.65
65.13
74.4913.04
Dropedge
74.64
66.46=161
69.75
w/ ManifoldMixup
74.04
65.51 +1774
73.10
w/ G-Mixup
76.56
67.20
73.55
GIN
vanilla
17.08
68.42
75,91 1.101
Dropedge
75.77
66.16
70.50
w/ ManifoldMixup
75.73
68. =2004
77.44
G-Mixup
77.14
69.28
77.79
GIN-virtual
vanilla
77.52:11.56
67.10=2.10
74.1914.90
w/ Dropedge
76.83+1.11
68.87
72.20
w/ ManifoldMixup
76.5 10.51+22.22
68.04 -8.0042287
74.17+138
w/ G-Mixup
77.09
=..02
73.53
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 better choice for hyperparameters K for -Mixpp, 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 -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 significant margin for REDDIT-BINARY dataset while the depth of GCNs
G-Mixup when graph neural network goes deeper.
Area Under Receiver Operating Characteristic
17

---

Under review as a conference paper at ICLR 2022
IMDB-BINARY
REDDIT-BINAN
95
90
72.5
Accuracy
70.0
67.5
65.0
Arg. KNela of Oiiginal Grapht
Ary. of
62.5
Unnginal Graphs
60.0
70
30 #Nodes of Generated Graphs
200
400
600
800
#Nodes of Generated Graphs
Figure 6: The impact of the node numbers of generated synthetic graphs 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 aceuracy with different number of nodes of generated graphs. Obviously, the accuracy reach the maximum values around the red line on both two datasets
IMDE-BINARY
REDDIT-BINARY
100
Dropedge +G-bbup
95
-Dropedge
80
G-mixup
Accuracy
Accuracy
50
3
3
6
#Layers GCN
#Layers of GCN
Figure 7: The performance 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.
18


Reviews:
[{"review_id": "KVvp0TQ2rp1", "reviewer": "Reviewer_s4VH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n1. The graph-level data augmentation methods have been mainly focusing on augmentation for unsupervised graph learning, and the graph data augmentation for supervised graph classification is rather underexplored. This topic is interesting and worth studying.\n2. I like idea of using mixup on graph generators instead of directly on graphs, which is simple yet reasonable.\n3. The authors provided good theoretical justification on their proposed method.\n\nCons:\n1. Missing related works: [1][2]\n2. The design of G-mixup seems to rely on the assumption of \"graph topology between classes are divergent\" (point 3 in the end of page 1), the theoratical justification (Thm 1) and observations in Fig 2 both support it. Moreover, other than being able to generate more data to improve the model's generalization, G-mixup also tries to help the model to learn such topological patterns. Therefore, I wonder how much does this information help on the node classification. For example, what if we concate $W_{\\mathcal{G}}$ with $\\mathbf{h}_G$ for all $G \\in \\mathcal{G}$ and directly use this new graph representation for node classification? Such ablative experiments would make this work more compelling.\n3. In Table 2, I noticed that G-mixup showed significant performance improvement on Reddit-B with GCN, while showing mostly marginal improvements under all other settings. The authors should give more explaination on that.\n4. I would recommend the authors to use the term \"graph data augmentation\" instead of \"graph augmentation\" to avoid potential confusion with a different problem in graph theory.\n\n[1] Data Augmentation for Graph Neural Networks, AAAI'21\\\n[2] Graph Contrastive Learning Automated, ICML'21", "summary_of_the_paper": "This work studied the research problem of graph data augmentation for supervised graph classification. The authors proposed G-mixup that performs mixup on graph data via graphon generators. Due to the irregular characteristics of graphs, instead of directly mixing up the data objects, G-mixup mix up the graph generators. ", "summary_of_the_review": "The proposed method is interesting, but the experiments can be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IHxJIcF3f6f", "reviewer": "Reviewer_RkbU", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper introduces a novel attempt of applying Mixup from vision and text to graph data. The idea of leveraging graphs being sampled from estimated graphons sounds interesting to me. On the other hand, I have the following concerns regarding the paper.\n\n1.\tThe proposed method bases on a strong assumption which deserves further justification. That is, each class has a graphon and this graphon can be accurately estimated. I would like to see some theoretical proof and/or analysis on that. Such assumption also raises the question whether such graphon estimation can be used for graphs with node and edge features; it would be useful if the authors could shed some lights on that. \n\n2.\tTheorem 2 suggests that in order to allow the synthetic graphs sampled from the mixed graphons to preserve the discriminative motifs, one needs sufficiently large sampled graphs. This assumption of g-Mixup makes me wonder that at the earlier stage of training, the synthetic graphs cannot preserve the discriminative motif of the graphon. I wonder how this guarantees the proposed g-Mixup would work. In other words, the synthetic graphs may be noise at all. Also, since the addition and deletion of graph edge in g-Mixup are based on the learned (imperfect) graphon, I think it may encounter the manifold intrusion issue when mixing graphs (Guo et al. at “mixup as locally linear out-of-manifold regularization”, AAAI2019). \n\n3.\tThe experiment section is quite weak in its current form. \n\n     a.\tA critical baseline is missed in the experiment. The proposed g-Mixup is closely related to the MixupGraph approach as proposed by Wang et al. (“Mixup for Node and Graph Classification”, WWW2021). Mixing the embeddings resulting from the READOUT function of GNNs is much easier to be implemented than the g-Mixup method proposed here, so it would be interesting to see the comparison between the two approaches. \n\n     b.\tIt would be useful to provide ablation studies to show how accurate are the graphons estimated for the datasets (namely Equation 3), and how such estimation impacts the performance of the g-Mixup.\n\n     c.\tThere is a parameter n, i.e., the number of nodes to be generate by the graphon. How this number impacts the performance of g-Mixup?\n\n     d.\tWhen estimating graphons from training data, K is used as the average number of nodes in all graphs. How the K was set in testing is not clear to me, and how different Ks impact the g-Mixup performance?\n\n     e.\tThe datasets used are without nature node features, I wonder how the proposed method would perform on graphs with node features. \n\n      f.\tFrom Table2. The accuracy improvement over vanilla baselines is minor, in particular for the powerful model GIN. This makes me wonder why one needs extra computation cost for g-Mixup?\n\n     g.\tAlso, for dropEdge, 4 layer GCN and 5 Layer GIN seem a bit too shallow to me. DropEdge typically performs well on deeper GNNs such as six to eight layers. \n\n     h.\tIn Table3, it would be useful to also compare with dropEdge and GraphMixup. \n\n\nOther comments:\n1.\tThe sentence at the end of page one: “thus prohibit us from directly adopting the Mixup strategy to graph data”. “Prohibit” here is a bit strong to me, although I think it is quite challenge to applying Mixup to graph input. \n2.\tLast paragraph in section 1. “Since directly mixing up graphs is intractable,”. It would be helpful to make it specific why and how the intractable occurs here?\n3.\tNotations are inconsistent. Such as N(v_{i}) vs. N(i); k and n refer to nodes and graphs in different places (see end of section4.2). \n4.\tTypos: first sentence of section 4.2 “propose the following the theorem.”; middle of second paragraph in section 4.3: “on a estimated…”.\n", "summary_of_the_paper": "The paper proposes to leverage graphon as a graph generator to adapt Mixup from vision and text to graph classification. It works as follows. A graphon, which aims to capture the existence probability of an edge between any two nodes in a graph, is first estimated for each class of the training graphs. Next, two random graphons are mixed with mixing ratio \\lambda, forming a mixed graphon. Finally, graphs are sampled from the mixed graphon as synthetic graphs for training.  The proposed method is evaluated using graph classification accuracy and robustness to graph corruption, showing improvement over baseline models. Applying Mixup to graph samples is an interesting and important research topic, but I think the paper in its current form is a bit immature.", "summary_of_the_review": "Some key assumptions of the proposed method are not well justified. Also, the experimental study is quite weak in its current form. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "GD7zElAVQT6", "reviewer": "Reviewer_vVum", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n* Clear contribution that generalizes the mixup [1] to the graph data. Although mixup has shown to be an effective data augmentation method in the image and text domain, it has not been applied to the graph domain due to the non-Euclidean characteristic of a graph. Therefore, the contribution of this work is clear since this work makes the mixup be applicable to the graph-structured data by introducing the concept of the graphon. \n* Well-written. Especially, it is easy to understand the concept of this paper through the figures and examples. The theoretical justification of the method clearly shows the G-mixup is effective to generate the mixup of two graphs of different classes on the theoretical side. In addition, the analysis in Section 5.2 empirically shows that the G-mixup can generate a well-mixed graph of different classes.\n\n## Weaknesses\nThe empirical results are not sufficient to show the effectiveness of G-mixup.\n* Baselines are not enough. I wonder that why the authors did not include the experiments against Manifold Mixup [2] although the authors refer to it in the discussion.\n* Besides, several other baselines [3,4,5] including simple augmentations should be compared against the G-mixup.\n* Experimental setting is too limited. Since the G-mixup mainly focuses on the improvement of graph neural networks on the graph classification task, it is important to show its effectiveness in various settings including dataset and base models. For instance, I recommend authors include the experiments on the classification task of a biomedical graph (e.g. molhiv dataset in Open Graph Benchmark [6]).\n* In terms of the base GNN model, I believe the experiments on the GNN with the recent pooling [7,8] method will also be helpful to show the effectiveness of G-mixup for the performance improvement on the classification task.\n\nOverall, the experiment part should be improved.\n\n\n\n### References\n[1] Zhang et al., mixup: Beyond Empirical Risk Minimization, ICLR 2018.\n\n[2] Wang et al., Mixup for Node and Graph Classification, WWW 2021.\n\n[3] Zhao et al., Data Augmentation for Graph Neural Networks, AAAI 2021.\n\n[4] You et al., Graph Contrastive Learning with Augmentations, NeurIPS 2020.\n\n[5] Zhou et al., Data Augmentation for Graph Classification, CIKM 2020.\n\n[6] Hu et al., Open Graph Benchmark: Datasets for Machine Learning on Graphs, NeurIPS 2020.\n\n[7] Bianchi et al., Spectral Clustering with Graph Neural Networks, ICML 2020.\n\n[8] Baek et al., Accurate Learning of Graph Representations with Graph Multiset Pooling, ICLR 2021.\n", "summary_of_the_paper": "This paper proposes the mixup method for graphs which is based on the concept of the graphon. Specifically, G-mixup first estimates the graphon for each class of graphs with the same label then interpolates the graphons of different classes of graphs. Finally, they generate the new graphs from the interpolated graphons to produce the mixed graph with a mixed label.\n\nThe authors theoretically show that G-mixup can preserve the different motifs of the two different graphs into one mixed graphon. In experiments, they empirically show that the G-mixup improve the generalization and the performance of existing GNNs on several graph classification task.\n", "summary_of_the_review": "This is an impressive paper but there is a lack of experiments.\nI am willing to upraise my score if the authors successfully address my concerns regarding experiments in the rebuttal.\n\n------------\nAfter rebuttal: In this version, the experimental results seem convincing. I raise my score from 5 to 8.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work tries to extend mixup to graph structured data, where graphs can differ in the number of nodes, and the space is not Euclidean.  This is achieved by G-Mixup, which interpolates the generator (graphon) of different classes of graphs through the latent Euclidean space.  Experimental results show some promise.

Several concerns have been raised by the reviewers, and although the rebuttal helped, some concerns remain.  For example, how to confirm that the graphon can be accurate estimated.  Several weakness in experiment is also raised, and a revision is needed before the paper can be published.
Decision: Reject