Year: 2021

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.

heading: 1 INTRODUCTION
text: 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.
WI
WH
WG
I = {I1, I2, · · · , Ik} with label (0.5, 0.5)
H = {H1, H2, · · · , Hk} with label (0, 1)
G = {G1, G2, · · · , Gk} with label (1, 0)
…
…
…
1) graphon estimation
3) graph sampling
WI = 0.5 ⇤ WG + 0.5 ⇤ WH
1) graphon estimation
2) graphon mixup
Figure 1: An overview of G-Mixup. The task is binary graph classification. We have two classes of graphs G andH with different topologies (G has two communities whileH has eight communities). G and H have different graphons. We mix up the graphons WG and WH to obtain a mixed graphon WI , and then sample new graphs from the mixed graphon. Intuitively, the synthetic graphs have two 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 G = {G1, G2, · · · , Gk} and H = {H1, H2, · · · , Hk} with different labels and distinct topologies (i.e., G has two communities while H has eight communities), we estimate graphons WG and WH respectively from G and H. We then mix up the two graphons and obtain a mixed graphon WI . After that, we sample synthetic graphs from WI as additional training graphs. The generated synthetic 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.

heading: 2 PRELIMINARIES
text: 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.

heading: 2.1 NOTATIONS
text: 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 G,H, I to denote graph set. yG ∈ 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 set G is denoted as FG . WG denotes the graphon of graph set G. W denotes the step
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 .

heading: 2.2 GRAPH HOMOMORPHISM AND GRAPHONS
text: 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)|/n1 = 1, t( , G) = 2|E(G)|/n2. 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 in graphons, which is characterized by its graphon marginal dW (x) = ∫ 1 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 graphon W is defined by
t(F,W ) = ∫ [0,1]V (F ) ∏ i,j∈E(F ) W (xi, xj) ∏ i∈V (F ) dxi.
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 (y, z) dxdydz.

heading: 2.3 GRAPH CLASSIFICATION WITH GRAPH NEURAL NETWORKS
text: 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 (k) i = AGG
(k) ({
h (k−1) j : j ∈ N (i)
}) , h
(k) i = COMBINE (k) ( h (k−1) i ,a (k) i ) , (1)
where h(k)i ∈ Rn×dk is the intermediate representation of node i at the k-th layer, N (i) denotes the 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 (k) i : i ∈ E(G) }) , ŷ = softmax(hG), (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), hG is the representation of graph G, and ŷ ∈ RC is the output estimating the probability that G belongs to each of the C classes.

heading: 3 METHODOLOGY
text: 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.

heading: 3.1 G -MIXUP
text: 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: G →WG ,H →WH, (3) Graphon Mixup: WI = λWG + (1− λ)WH, (4) Graph Generation: {I1, I2, · · · , Ik} i.i.d∼ G(k,WI), (5) Label Mixup: yI = λyG + (1− λ)yH, (6)
where WG ,WH are graphons of the graph set G and H. The mixed graphon is denoted by WI , and λ ∈ [0, 1] is the trade-off hyperparameter to control the contributions from different original graphs for interpolation. The set of synthetic graphs generated from WI is I = {I1, I2, · · · , Ik}. The yG ∈ RC and yH ∈ RC are vectors containing ground-truth labels for graph G and H respectively. The label vector of a generated graph in I is set as yI ∈ 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, · · · , Gk} with label yG, and H = {H1, H2, · · · , Hk} with label yH. Graphons WG and WH are estimated from graph set G and H, then we mix them up though linearly interpolating two graphons and their training labels and obtain WI and yI . The synthetic graph set I is sampled based on WI , which will be used as additional training graphs.

heading: 3.2 IMPLEMENTATION
text: 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 (Lovász, 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., 2015). Formally, a step function WP : [0, 1]2 7→ [0, 1] is define as WP (x, y) = ∑K k,k′=1
wkk′1Pk×Pk′ (x, y), where P = (P1, ..,PK) denotes the partition of [0, 1] into K adjacent intervals of length 1/K, wkk′ ∈ [0, 1], and indicator function 1Pk×Pk′ (x, y) equals to 1 if (x, y) ∈ Pk×Pk′ and otherwise it is 0. Essentially, the step function can be seen as a matrix W = [wkk′ ] ∈ [0, 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 G = {G1, G2, · · · , Gk} and H = {H1, H2, · · · , Hk} with different labels, we estimate their step functions WG ∈ RK×K and WH ∈ RK×K We let K be the average number of nodes in all graphs. For multi-class classification, we first estimate the step function for each class of graphs and then randomly select two to perform mix-up. The resultant step function is WI = λWG+(1−λ)WH ∈ RK×K , which serves as the generator of synthetic graphs.
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,WI) can be generated following the process:
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 [b1/uic, b1/ujc], and b·c 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 function. 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 computational complexity of the proposed G-Mixup. The major additional computation costs come from graphon estimation and graph generation. For graphon estimation, suppose we have M graphs and each of them has N nodes and E edges, and estimate step function withK 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 O(KN) for node genera-
tion and O(KN2) for edge generation, so the overall complexity of graph generation is O(KN2).

heading: 4 THEORETICAL JUSTIFICATION
text: 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 FG is the set of the discriminative motif of every graph in 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 a 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 predict the class label. For example, benzene (a compound in chemistry) is distinguished by the discriminative motif (benzene ring).
4.1 WILL DISCRIMINATIVE MOTIFS FG AND FH EXIST IN λWG + (1− λ)WH ?
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 G and H, the corresponding graphons are WG and WH, and the corresponding discriminative motif set FG and FH. For every discriminative motif FG ∈ FG and FH ∈ FH, the difference between the homomorphism density of FG /FH in the mixed graphon WI = λWG + (1− λ)WH and that of the graphon WH/WG is upper bounded by
|t(FG ,WI)− t(FG ,WG)| ≤ (1− λ)e(FG)||WH −WG || , |t(FH,WI)− t(FH,WH)| ≤ λe(FH)||WH −WG ||
(8)
where e(F ) is the number of nodes in graph F and ||WH −WG || is the cut norm 2. 2Details about cut norm are in Appendic A.1
Proof Sketch. The proof follows the derivation of Counting Lemma for Graphons (Lemma 10.23 in Lovász (2012)), which relates the homomorphism density and the cut distance ||WH − WG || of graphons. Specifically, we take the two graphons in this Lemma to deduce the bound of the difference of homomorphism densities of WI and WG/WH. 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 λ, the edge number e(FG)/e(FH) and the cut norm ||WH −WG || . Since the e(FG)/e(FH) and the cut norm ||WH −WG || are decided by the dataset ( can be regraded as a constant), the difference in homomorphism densities will be decided by λ. On this basis, the corresponding label of the graphon is set to λyG + (1−λ)yH. Therefore, G-Mixup can preserve the different discriminative motifs of the two different graphons into one mixed graphon.

heading: 4.2 WILL THE GENERATED GRAPHS FROM GRAPHON WI PRESERVE THE MIXTURE OF DISCRIMINATIVE MOTIFS?
text: 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 discriminative motif, then the WI-random graph G = G(n,WI) satisfies
P (|t(FI ,G)− t(FI ,WI)| > ε) ≤ 2exp ( − ε 2n
8v(FI)2
) . (9)
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(FI ,G) ≈ t(FI ,WI) with high 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.

heading: 4.3 DISCUSSION
text: 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 WI = WH, {I1, I2, · · · , Ik} i.i.d∼ G(k,WI),yI = yH. ii) G-Mixup will degenerate into DropEdge, while setting λ = 0 and masking graphons with adjacency matrix A in Equation 4. The expression is WI = A WH, {I1, I2, · · · , Ik} i.i.d∼ G(k,WI),yI = yH, where is element-wise multiplication. 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.

heading: 5 EXPERIMENTS
text: 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.

heading: 5.1 DOES DIFFERENT CLASSES OF REAL-WORLD GRAPHS HAVE DIFFERENT GRAPHONS?
text: 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.
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∗WG+0.5∗WH is able to generate graphs with a high-degree node and a dense subgraph, which 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.
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.
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 improves 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.

heading: 5.4 CAN G -MIXUP VIRTUALLY IMPROVE THE ROBUSTNESS OF GNNS?
text: 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, respectively. More experimental settings are presented in Appendix B.2. Observation 6: G-Mixup improves 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 4: Robustness to topology corruption with different corruption ratio.
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

heading: 6 RELATED WORKS
text: Graph Data Augmentation Graph neural networks (GNNs) also achieve the state-of-the-art performance on graph classification task (Kipf & Welling, 2016; Veličković 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 (Lovász, 2012; Lová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 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.

heading: 7 CONCLUSION
text: 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.

heading: A PROOF OF THEOREM
text: 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.

heading: A.1 PRELIMINARIES
text: Cut norm (Lovász, 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‖ = supS,T⊂[0,1] ∣∣∣∫
S×T W (x, y)dxdy ∣∣∣, (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 (Lovász, 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 ′)|
= ∣∣∣∣∣ ∫ ( ∏
uivi∈E W (ui, vi)− ∏ uivi∈E W ′ (ui, vi) ) ∏ v∈V dv ∣∣∣∣∣ ≤ |E|∑ i=1 ∣∣∣∣∣∣ ∫ i−1∏ j=1 W ′ (uj , vj) (W (ui, vi)−W ′ (ui, vi)) |E|∏ k=i+1 W (uk, vk)  ∏ v∈V dv ∣∣∣∣∣∣ (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 Lovász & 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
P (|t(F,G)− t(F,W )| > ε) ≤ 2exp ( − ε 2n
8v(F )2
) (14)

heading: A.2 PROOF OF THEOREM 1
text: 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‖ = sup S,T⊆[0,1] ∣∣∣∣∫ S×T αW ∣∣∣∣ = sup S,T⊆[0,1] ∣∣∣∣α ∫ S×T W ∣∣∣∣ = α‖W‖ (16) Based on Equation 15 and Equation 16, we have
|t(FG , λWG + (1− λ)WH)− t(FG ,WG)| ≤ e(FG)||(1− λ)(WH −WG)|| ≤ (1− λ)e(FG)||WH −WG ||
(17)
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.

heading: A.3 PROOF OF THEOREM 2
text: Let F and W be the discriminative motif FG and the mixed graphon WI in Lemma 2, we will have P (|t(FI ,G)− t(FI ,WI)| > ε) ≤ 2exp ( − ε 2n
8v(FI)2
) (19)
which produces the result in 9.

heading: A.4 GRAPHONS ESTIMATION BY STEP FUNCTIONS
text: 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 P = (P1, ..,PK) be a partition of Ω into K measurable sets. We define a step function WP : Ω2 7→ [0, 1] as
WP(x, y) = ∑K
k,k′=1 wkk′1Pk×Pk′ (x, y), (20)
where each wkk′ ∈ [0, 1] and the indicator function 1Pk×Pk′ (x, y) is 1 if (x, y) ∈ Pk × Pk′ , otherwise it is 0. The weak regularity lemma Lová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 (Lovász, 2012)) ) For every graphon W and K ≥ 1, there always exists a step function W with |P| = K steps such that
‖W −W‖ ≤ 2√
logK ‖W‖L2 . (21)

heading: B EXPERIMENTS SETTING

heading: B.1 EXPERIMENTAL SETTING
text: 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.

heading: B.2 EXPERIMENTAL SETTING OF ROBUSTNESS
text: 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.

heading: C ADDITIONAL EXPERIMENTS FOR REBUTTAL
text: 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.

heading: C.1 EXPERIMENT ON MORE GRAPH NEURAL NETWORKS (DIFFPOOL, MINCUTPOOL,
text: 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.

heading: C.2 EXPERIMENT ON MOLECULAR PROPERTY PREDICTION
text: 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.

heading: C.3 WHAT IS THE IMPACT OF NUMBER OF NODES OF GENERATED GRAPHS?
text: 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.

heading: C.4 HOW G -MIXUP PERFORM WHEN GRAPH NEURAL NETWORK GOES DEEPER?
text: 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 IMDBBINARY 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

Review summaries:
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. 

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.  The 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. 

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.