Intrusion-Free Graph Mixup
Authors: Hongyu Guo
Yongyi Mao
Venue: ICLR 2022 Submitted (2022)
Keywords: graph augmentation
Mixup
graph classification
graph neural networks

Abstract:  We present a simple and yet effective interpolation-based regularization technique to improve the generalization of Graph Neural Networks (GNNs). We leverage the recent advances in Mixup  regularizer for vision and text, where random sample pairs and their labels are interpolated to create synthetic samples for training. Unlike images or natural sentences,  which embrace a grid or linear sequence format, graphs have arbitrary structure and topology, which play a vital role on the semantic information of a graph. Consequently, even simply deleting or adding one edge from a graph can dramatically change its semantic meanings. This makes interpolating graph inputs very challenging because mixing random graph pairs may naturally create graphs with identical structure but with different labels, causing the manifold intrusion issue. To cope with this obstacle, we propose the first input mixing schema for Mixup on graph. We theoretically prove that our mixing strategy can recover the source graphs from the mixed graph, and guarantees that the mixed graphs are manifold intrusion free. We also empirically show that our  method can effectively regularize the graph classification learning, resulting in superior predictive accuracy over popular graph augmentation baselines. 

Under review as a conference paper at ICLR 2022
INTRUSION-FREB GRAPH MIXUP
Anonymous authors Paper under double-blind review
ABSTRACT
We present a simple and yet effective interpolation-basel regularization technique to improve the generalization of Graph Neural Networks (GNNs). We leverage the recent advances in Mixup regularizer for vision and text, where random sample pairs and their labels are interpolated to create synthetic samples for training. Unlike images or natural sentences, which embrace a grid or linear sequence format, graphs have arbitrary structure and topology, which play vital role on the semantic information of graph. Consequently, even simply deleting or adding one edge from a graph can dramatically change its semantic meanings. This makes interpolating graph inputs very challenging because mixing random graph pairs may naturally create graphs with identical structure but with different labels, causing the manifold intrusion issue. To cope with this obstacle, we propose the first input mixing schema for Mixup on graph. We theoretically prove that our mixing strategy
recover the source graphs from the mixed graph, and guarantees that the mixed graphs are manifold intrusion free. We also empirically show that our method can effectively regularize the graph classification learning, resulting superior predictive accuracy over popular graph augmentation baselines.
INTRODUCTION
Graph Neural Networks (GNNs) (Kipf & Welling, 2017
Veličković al. 2018 Xu et al. 2019)
have recently shown its profound successes in many cha applications, including predicting molecule properties for drug and material discovery (Gilmer al.
2017; Wu et al. 2018). forecasting
protein functions for biological networks (Alvarez & Yan 2012 2 Jiang et al.] 2017 7). and estimating circuit functionality in modern circuit design (Zhang et al. 2019). Nevertheless, like other successfully deployed deep networks such as those for image classification (Krizhevsky et al. 2012). speech recognition (Graves al., 2013) and machine translation (Sutskever et al.) 20144) Bahdanau al.. 2014). GNNs are also suffering from the data-hungry issue due to their high modeling freedom. Consequently, researchers have been actively seeking effective regularization techniques for GNNs, aiming to power their learning but to avoid over-smoothing (Li et al., 2018 Wu et al.) 2019) and over-fitting (Goodrellow et al. 2016 Zhang et al. 202T) for better model generalization. To this end, data augmentation schemes for regularizing GNNs mostly involve edge and node manipulation (e.g.. deletion and addition) on a single graph (Rong et al. 2020) Zhou et al. 2020 You et al.) 2020).
In this paper, we look into very success- ful pairwise data augmentation technique for image recognition (Zhang et al. 2018|
Intusoon
deltte noda.
Verma et al., 2018 Guo et al., (201a]] Kim
al.] 2020) and natural text classifica-
drop node: class
gaphi dlet
tion (Guo et al. 2019b Guo 2020 Jin-
delett delerttnnee edje
dal et 2020). called Mixup. Mixup
was originally introduced by Zhang et al. (2018a) as an interpolation-bant izer for image classification. It regularizes the learning of deep classification models by training with synthetic samples, which are created by linearly interpolating a pair of randomly selected training samples well as their modeling targets. Neverthe- less, unlike images natural sentences,
regular-
Crop edge: das
orginal gruph: class
Figure Manifold intrusion caused by deleting node or an edge (gray dot lines) from the left graph. The two synthetic graphs (middle) have the same structures as the two original graphs on the right but with different labels.
which embrace a grid linear sequence format, graph

---

Under review as a conference paper at ICLR 2022
data have arbitrary structure and topology, which play critical role on the semanties of graph, and consequently even simply removing or adding one edge can dramatically change the semantic meaning of a graph. As a result, mixing graph pair is challenging and may naturally cause the manifold intrusion issue in Mixup as identified by Guo et al. (019a).
Manifold intrusion results from conflicts between the synthetic labels of the mixed-up samples between the synthetic labels and the labels of the original training data. For example, consider the graph on the left of Figurel [ and its application of the popular graph perturbation action of node and edge deletion (gray lines in the figure). In this case, the resulting two graphs in the middle will have the same structure as the two on the right from the original training set, but with different labels (indicated by the color bars under the graphs). Note: an illustration of manifold intrusion when mixing two graphs is presented in A.5 As discussed in (Guo et al., (019a), when such intrusions occur, regularization using these synthetic graphs will contradict with the original training data. This essentially induces a form of under-fitting, resulting in the degradation of the model performance.
To address the aforementioned challenge, we propose the first input mixing schema for Mixup on graph learning, coined ifMixup (intrusion-free Mixup). As illustrated in Figure 2 ifMixup first samples a random graph pair (top subfigure) from the training data. For given mixing ratio À sampled from a Beta distribution, ifMixup then creates a synthetic graph (bottom subfigure), for each sample pair. ifMixup treats graph pair as two sets of ordered nodes in the same size (middle subfigure, where the unfilled node depicts an added dummy node). As result, it can linearly interpolate the node features and the edges of the input pair. The newly generated graphs, which have a much larger number of graphs with changing local neighborhood properties than the original training dataset, are then used for training to regularize the GNNs learning. Theoretically, we prove that our mixing strategy can recover the source graphs from the mixed graph, and such invertibility property guarantees that the mixed graphs are intrusion free. That is, method eliminates the possibility for the graphs resulting from mixing to coincide with any other graph in the training set or with mixed graph from any other graph pairs. Experimentally, we show, using eight benchmarking tasks from different domains, that our strategy effectively regularizes the graph classification to improve its predictive performance, outperforming popular graph augmentation approaches and existing pair-wise graph mixing methods[]
Graph A: (Vi, (a.Jaa
Graph B: (Va, Va)
A
G=Ara + (1 A)ve
Æ=λez + (1 2)eg
9= + (1 A)ys
mixed graph: (8,6,)
The proposed mixing schema. Top subfigure depicts the source graph pair, and the bottom is the resulting mixed graph for train- ing with mixing ratio E [0, 1].
Figure 2:
Our key contributions are as follows: 1) To the best of our knowledge, we are the first to propose an input Mixup for graph classification. 2) We prove that our Mixup schema is free of manifold intrusion, which can significantly degrade Mixup-like model's predictive accuracy. 3) We obtain the SOTA performance among popular graph perturbation baselines.
2 RELATED WORK
GNNs have been shown to be very effective for graph classification in a variety of domains (Kipf & Welling, 2017 Ying et al. 2018 Veličković et al.) 2018 Klicpera et al. 2019 Xu et al. 2019
Bianchi et al. 2020). One of the key challenges of these successes is to leverage strong regularization techniques such data augmentation to regularize those GNNs models with high modeling freedom. Nonetheless, data augmentation is still a less touched area in graph data due to the arbitrary structure and topology. Most of the graph augmentation strategies are for node classification tasks, and heavily focus on perturbing nodes and edges in one given graph (Hamilton et al. 22017; Zhang et al. 2018b Rong et al. 2020 Chen et al.) 2020 Zhou et al.) 2020 Qiu et al. 2020 You et 2020 Wang et al.; Fu et al.) 2020; Wang et al. 2020; Song et al. 2021 Zhao et 2021). For example, DropEdge Rong et al. (2020) randomly removes set of edges of given graph. GAUG (Zhao)
et al. 202 learns to perturb graph edges for node classification. DropNode, representing node
'Our PoToc code will he released upon the acceptance of the paper.
2

---

Under review as a conference paper at ICLR 2022
sampling based methods (Hamilton et al. 2017: Chen al. 2018 Huang al. 2018), samples set of nodes from a given graph. Unlike these approaches, our proposed strategy leverages a pair of graphs, instead of one graph, to augment the learning of graph level classification.
Despite its great success in augmenting data for image recognition and text processing (Zhagg et al. 2018a: Verma et al. 2018 Guo et al. (2019a Guo 2020 Jindal al., 2020 Kim et al. 2020p. Mixup has been less explored for graph learning. To the best of our knowledge, there are two methods that apply Mixup GNNs. GraphMix (Verma al. 2019) leverages the idea of mixing on the embedding layer, with an additional fully-connected network to share parameters with the GNNs, for graph node classification in semi-supert -upeiiieee learning. MixupGraph (Wang al. 202T) also leverages a simple way to avoid dealing with the arbitrary structure in the input space for mixing a graph pair, through mixing the graph representation resulting from passing the graph through the GNNs. Our paper here introduces the first input mixing method for Mixup to augment training data for graph classification. Furthermore, our method guarantees that the mixed graphs are manifold intrusion free for Mixup.
INTRUSION-FREE GRAPH MIXING
3.1 GRAPH CLASSIFICATION AND MIXUP INTERPOLATION
Graph Classification In the graph classification problem we consider, the input is a graph labelled with node features, or "node-featured graph". Specifically, assume that the graph has nodes, each identified with an integer ID in [n] := {1. 2, ................................ .n.. The set of edges E' of the graph is a collection of unordered pairs (f,j)'s of node-IDs, as the current paper considers only undirected graphs (although there is no difficulty to extend the setting to directed graphs). Associated with node i, there is a feature vector v(i) of dimension d. We will use denote the collection of all feature vectors and one may simply regards v as a matrix of dimension n x d. Thus, each input node featured graph G is essentially specified via the pair (v, E). The output y is class label in finite set y := (1.2..... C}. which will be expressed as a (one-hot) probability vector over the label set V. The classification problem is to find mapping that predicts the label y for a node-featured graph G. The training data G of this learning task is collection of such (G, y) pairs.
Modern GNNs use the graph structure and node features to learn distributed vector to represent graph. The learning follows the "message passing" mechanism for neighborhood aggregation. It iteratively updates the embedding of node h2 by aggregating representations/emeeddin neighbors. The entire graph representation hG is then obtained through READOUT function, which aggregates embeddings from all nodes of the graph. Formally, representation h of node i at the k-th layer of a GNN is defined as:
of its
h AGGREGATE( k ..1....--111 Piiee(N ((),,
(1)
where W denotes the trainable weights at layer k. (i) denotes the set of all nodes adjacent to i and AGGREGATE is an aggregation function implemented by the specific GNN model (popular ones include Max, Mean, Summation pooling operations), and hς is typically initialized as the input node feature v(i) The graph representation lGg aggregates node representations he using the READOUT graph pooling function:
hg (b [n]).
(2)
This graph representation is then mapped to label y using standard classification network (for example, a softmax layer).
interpolation- regularizer for image classification. It regularizes the learning of deep classification models by training with synthetic samples, which are created by linearly interpolating a pair of randomly selected training samples as well as their modeling targets. In detail, let (x.,, V.)) and (IB, YB) be two training instances, in which A and nn refer to the input images and ÿa and yn refer to their corresponding labels. For a randomly chosen such training pair, Mixup generates a synthetic sample as follows.
Mixup Interpolation Mixup introduced by Zhang al. 2018a)
ã = Az + (1 A)æB = Ay + (1 AjyB,
(3)
(4)
where À is a scalar mixing ratio, sampled from a Beta(a, 8) distribution with (3. Such synthetic instances (ū. 7)'s are then used for training.
a and
3

---

Under review as a conference paper at ICLR 2022
Motivated by the effectiveness of Mixup in regularizing image classification models, we naturally motivated to design a similar "Mixup" scheme for graph data, in particular, the node-featured graphs, as are the interest of this paper. When this is possible, we may use the synthetic instances (G, y)'s to learn the modele parameter 0 by minimizing the loss L:
min (.w.G.G.Aa......nnnnnnnnaaaaaaaa
[(G,,)
(5)
To mix (GA, yA) and (GB, yB). is straight-forward apply Equation (4 to obtain the mixed label y. The key question of investigation is how to mix GA and Gy to obtain G.
It is worth noting that, unlike images or natural sentences which embrace a rigid structure of spatial coordinates or time axis, the underlying "coordinate system" of graph data may have different and arbitrary topology across different instances. Consequently even simply deleting adding one edge can invalid the semantic meaning of a graph. One simple way to avoid dealing with the arbitrary structure in the input space for mixing graph pair is to mix their fixed-size graph representation that results from the READOUT function as depicted in Equation 2 namely mixing the two graphs by G = XhG, + (1 A)kG as proposed by Wang et al. 2021). We here propose to directly mix the graph inputs with arbitrary sizes for Mixup. Our mixing strategy can recover the source graphs from the mixed graph, and such invertibility guarantees that the mixed graphs are free of manifold intrusion (Guo et al. 2019a), which can cause severe underfitting for Mixup learning.
3.2 INVERTIBLE GRAPH MIXING SCHEMA
Now we propose a simple approach, ifMixup, for generating mixed node-featured graph G from a pair of such graphs G'A and GB. In the nutshell, ifMixup simply adopts different representation for each node-featured graph.
Specifically, given node featured graph G = (v, E), we represent E as a binary matrix with rows and n columns, in which e(i, j) if (i.j) E E, and e(i. = 0 otherwise. Thus intead of expressing G as (u, E) we express it as (u, The mixing of GA (UA, eA) with G3 (ug, eB) to obtain G (i, 2), can simply done as follow,
غ λa + (1 - AJeB
(6)
8 = AU + (1 AjUB-
In order for the above mixing rule to be well defined, we need the two graphs to have the same number of nodes. For this purpose we define n max(nA,, where n' and ng are the number of nodes in instances A and B respectively. If A or G3 has less than nodes, we simply introduce dummy node the graph and make them disconnected from the existing nodes. The feature vectors for the dummy nodes are set to the all-zero vector.
This mixing process is illustrated in Figure 2 where the top subfigure is the source graph pair, and the middle depicts the added dummy node (i.e., the node with unfilled circle). The bottom is the resulting mixed graph, where a mixed color indicates that the resulting node or edge is mixed by existing nodes edges from both source graphs, and the blue color denotes node that is mixed with a dummy node or an edge that is mixed with a zero- weighte edge.
It is worth noting that the resulting mixed graphs, through Equations 6 and contain edges with weights between [0, 1]. As a result, during training, this will require the GNN networks be able to take the edge weights into account for message passing. Below we will discuss how the two popular GNN networks, namely GCN (Kipf & Welling (017) and GIN (Xu et al. 2019), cope with the weighted edges in graphs, namely how they implement Equation] 1 to generate node representations.
GCN handles edge weights naturally by enabling adjacency matrix to have values between zero and one (Kipf & Welling, 2017), instead of either zero or one, representing edge weights:
e(i,g) n
h Wk.
Σ
(8)
vd,d.
(EN())()
4

---

Under review as a conference paper at ICLR 2022
where d, 1 EjeNts (ii,)): W stands for the trainable weights layer k; denotes the non-linearity transformation, i.c. the ReLu function.
To enable GIN to handle soft edge weight, we replace the sum operation of the isomorphism operator in GIN with weighted sum calculation. That is, the GIN updates node representations as:
h
MLP
-
(1+ h h + Σ e(i.j) - )
JEN(()
where ex is learnable parameter.
3.3 INVERTIBILITY AND INTRUSION-FREENSSS
We now show that such a simple mixing scheme in fact makes the original two node-featured graphs GA and G3 recoverable from the mixed graph G under a mild assumption and hence avoids manifold intrusion.
To see this, we first show that the graph topology and node features the two original instances can both be recovered from the mixed instance.
Lemma (Edge Invertibility) Let be constructed using Equation with À + 0.5. Consider equation
se + +
with unknowns s, e and e', where s is scalar and e and e' are binary (i.e. {0, 1--vauued n x n matrices. There are exactly two solutions this equation:
==
= d' = CB, or
8-1-1, c= cB = C
Note: the proof of this lemma in Section A.I
By this lemma, we see that if the mixing coefficient À a 0.5, from the mixed edge representation ē we can always recover ε and én (and hence EA and EB) and their corresponding weights used for mixing. Note that if À is drawn from continuous distribution over (0, 1), the probability it takes value 0.5 is zero. That is, the connectivity of original two graphs can be perfectly recovered from the mixed edge representation e.
Lemma 2 (Node Feature Invertibility) Suppose that the node feature vectors for all instances in the task take values from a finite set V C Rdd and that V is linearty independent. Let it be cosntructed using Equation 7 Let V V U (0), where 0 denotes the zero vector in RR Consider equation
T -= =u su + (1 s)y'
in which n matricess and of are unknowns with rows taking value in V For any fixed E (0, 1), there is exactly one solution of (v, v'), for this equation.
Note: the proof of this lemma is in Section A.2
The node feature invertibility in this lemma requires that the node feature vectors are linear inde- pendent. Note that if the feature dimension dl is larger than the size [V] of V and for each vector in V. its elements are drawn at random, then the linear independence property of V is satisfied with high probability. Thus, we have the modeling freedom in designing the dimension d of the feature vectors (for example, in designing the embedding dimension), choosing large d will make the linear independence condition of V satisfied. There are however cases which feature vectors are given and d < V.. In this case, we establish the following result which requires much weaker condition.
To that end, suppose that the span SPAN(V) of V is an m dimensioonn space and m < d. Let B be an x d matrix whose rows form a basis of SPAN(V). Any node feature matrix v can then be expressed as
v v= T=
for some matrix T with size x m. In this case, may identify node-featee featured graph (TB,e). Let T denote the collection of all T' matrices for all instances in the training set. That is,
(T' (TB,e) e) E &G
5

---

Under review as a conference paper at ICLR 2022
Lemma 3 (Node Feature Invertibility) Let e be constructed using Equation 7 and suppose that T is linearly independent. Consider equation
T +
which n x d matrices v and e' are unknowns where TB and v' T'B for some T and T in T. For any fixed E (0, 1}, there is exactly one solution of (v, v') for this equation.
Note: the proof of this lemma is in Section A.3
Note that since each 7 has size n x m, usually large number, it is much easier for the linear independence condition of T to get satisfied in practice.
Theorem (Intrusion- (natrusion-Freenss)) Freeness) Suppose that X + 1/2 and that either the condition for Lemma 2 is satisfied or the condition for Lemma is satisfied. Then for any mixed node-featured graph G = (ū. ē) constructed using Equations 6 andd the two original node-feature graph GA and G can be uniquely recovered.
Proof: Since X & 0.5, we can recover e,, and À from ē. Given À and either the condition for Lemma 2 or the condition for Lemma 3, we can recover UA and Ug from U.
By this theorem, there is other pair (G" G'B) from the training set C that can be mixed into G using any A. Thus, manifold intrusion does not occur under the mild condition of the theorem.
We note the intrusion-freenes, of the proposed ifMixup scheme relies on the fact that input graphs do not have soft (weighted) edges. We believe however that there is potential to extend the scheme to graphs with weighted edges. Promising directions include combination of the following techniques, First, instead of recovering edges and node features in tandem (as shown in the proof Theorem [ we may consider jointly recover both. Second we may quantize the edge weights to a set of discrete values and consider judiciously designed distribution for the mixing coefficient X. Third, we may insist the ordering of nodes in a graph to reflect certain semantics or graph topology of instance, whereby only allowing restricted family of alignment schemes of the two graphs before mixing them. It our interest to investigate in these directions further.
4
EXPERIMENTS
4.1 SETTINGS
Datasets We evaluate our method with eight graph classification tasks from the graph benchmark datasets collection TUDatasets (Morris et al. (2020): PTC MR, NCI109, NCII, and MUTAG for small molecule classification, ENZY MES and PROTEINS for protein categorization, and IMDB-M and IMDB-B for social networks classification. These datasets have been widely used for benchmarking such as in Xu et al. (2019) and can be downloaded directly using Py Torch Geometric (Fey & Lenssen 2019''s build-in function online H The social networks datasets IMDB-M and IMDB-B have no node features, and we use the node degrees as feature as in (Xu et al. 2019). Data statistics of these datasets are shown in Table including the number graphs, the average node number per graph, the average edge number per graph, the number of node features, and the number of classes.
Comparison Baselines We compare our method with four baselines: MixupGraph (Wang al. 2021), DropFdge (Rong et al., 2020), DropNode (Hamilton et al. 2017 Chen et al. 2018 8018] Huang ct al. 2018), and Baseline. For the Baseline model, we use two popular GNNs network architectures:
GCN (Kipf & Welling 2017) and GIN (Xu et al. 2019).
MixupGraph is the only available approach for applying Mixup on graph classification. It leverages simple way to avoid dealing with the arbitrary structure for mixing graph pair, through mixing the entire graph representation resulting from the READOUT function of the GNNs. DropEdge and DropNode are two widely used graph perturbation strategies for graph augmentation. DropEdge randomly removes a set of existing edges from a given graph. DropNode randomly deletes a portion of nodes and their connected edges.
GCN and GIN are two popular GNN architectures and have been widely adopted for graph classi- fication. GCN leverages apectral-baser convolutional operation to learn spectral features of graph

---

Under review as a conference paper at ICLR 2022
through aggregation, benefiting from normalized adjacency matrix, while GIN leverages the nodes' spatial relations to aggregate neighborhood features, representing the of-te-of-the-ar GNN network architecture. We use their implementations in the PyTorch Geometric platform GCN, we use the GCN with Skip Connection (He et al. 2016) as that in (Li et al. 2019), This Skip Connection powers the GCN to benefit from deeper layers in GNN networks.
Note that, for the
Detail Settings We follow the evaluation protocol and hyperparameters search of GIN (Xu et al. 2019) and DropEdge (Rong et al. 2020). We evaluate the models using 10-fold cross validation, and report the mean and standard deviation of three runs on a NVidia V100 GPU with 32 GB memory. Each fold is trained with 350 epochs with A optimizer (Kingma & Ba 2015), and the initial learning rate is reduced by half every 50 epochs. The hyper-paramettrr we search for all models on
each dataset are as follows: (1) initial learning rate E {0.01, 0.0005): (2) hidden unit of size E (64,
128); (3) batch size E (32. 128): : (4) dropout ratio after the dense layer E {0, 0.5): ; (5) DropNode and DropEdge drop ratio E (20%, 40%) ): (6) number of layers in GNNs E {5. 8): (7) Beta distribution
for ifMixup, MixupGraph and Manifold Mixup E {Beta(1, 1), Beta(2, 2), Beta(20, 1)}. Following
GIN (Xu et al. 2019) and DropEdge (Rong et al. 2020), we report the case giving the best 10-fold average cross validation accuracy.
4.2 RESULTS OF USING GCN AS BASELINE
The accuracy obtained by the GCN (Kipf & Welling 2017) baseline, ifMixup, MixupGraph, DropE- (best results in Bold).
dge, and DropNode with GCN on the eight datasets are presented in Table
GCN Baseline
ifMixup
MixupGraph
DropEdge
DropNode
Rel. Impr.
PTC.MR
0.601=0.018
0.00.
0.633=0.012
0.653=0.007
0.648
5.31%
NCT109
0.803=00001
0.820=0.005
0.801=0.005
0.801=0.001
0.793++0015
2.12%
NCII
0.8041.0.055
0.819-0.00
0.0004
0.811=0.002
0.805110.019
1.87%
MUTAG
0.850=0.011
0.879=0.003
0.860=#0.006
0.855=0.008
0.829=00.006
3.41%
ENZYMES
0.541=0.001
0.570=0.014
0.551=0.016
0.566=00006
0.532+000006
5,36%
PROTEINS
0.742-40.003
0.753 0.008
0.742
0.750=#0.003
0.748-+0.001
1.48%
IMDB-M
0.515++0.002
0.523 1 0.004
0.513++0.003
0.514++0.00.
0.512++0.003
1.55%
IMDB-B
0.758=0.004
0.063
0.759=0.002
0.762=0.004
0. 10.015
0.66%
Table Accuracy of the testing methods with GCN networks as baseline. We report mean accuracy over 3 runs of 10-fold cross validation with standard deviations (denoted +.). The relative improvement of ifMixup over the baseline GCN is provided in the last row of the table. Best results are in Bold.
Results in Table 1 show that ifMixup outperformed all the four comparison models against all the eight datasets. For example, when comparing with the GCN baseline, ifMixup obtained a relative accuracy improvement of 5.36%. 5.31% %. and 3.41% % on the ENZYMES, PTC_MR, and MUTAG datasets, respectively. When considering the comparison with the Mixup-like approach MixupGraph, ifMixup also obtained superior accuracy all the eight datasets. For example, ifMixup able to improve the accuracy over MixupGraph from 80.1 %6, 80.8%, 63.3%, and 51.3% to 82.0%, 81.9%, 65.4%, and 52.3% on the NCI109, NCII, PTC.MR and IMDB-M datasets, respectively.
Furthermore, as shown Table D unlike all the other augmentation methods (namely MixupGraph, DropEdge, and DropNode)), which can degrade the predictive performance of the baseline models, our method never degraded the baseline models' predictive accuracy.
4.2.1 MANIFOLD INTRUSION: MIXING RATIOS FOR GRAPH PAIRS
In this ablation study, we evaluate the sensitivity of the graph mixing ratio the two Mixup-like approaches: ifMixup and MixupGraph. We present the accuracy obtained by these two methods with Beta distribution as Beta(1, 1), Beta(2, 2), Beta(5, 1), Beta(10, 1) and Beta 1) the first six datasets of Table 3 Results are pre- sented in Figure 4 Note: the density functions of these five Beta distributions are depicted in Figure
Results in Figure 4 show that both MixupGraph and ifMixup ob- tained superior results on the six testing datasets with Beta 1). Nevertheless, MixupGraph seemed to very sensitive to the mixing ratio distribution. For example, when Beta distributions were (1, 1)
Figure 3: probability density
function of Beta distribution.
hhtps///tthmaccc//yytttamoyrrrr geometric
7

---

Under review as a conference paper at ICLR 2022
and (2, 2) (first two bars in Figure 4 MixupGraph significantly degraded its accuracy all the six tasks (except for MR). In contrast, ifMixup was robust to the five Beta distributions we tested.
We here conjecture that, the de- crease of MixupGraph's accu- racy obtained with Beta(1, 1) and Beta(2, 2) was due to the man- ifold intrusion issue. The mix- ing ratios sampled from Beta(1, 1) follow an uniform distribu- tion between [0, II, and those sampled from Beta(2, 2) fol- low Bell-Shaped distribution between [0. 1] (see Figure (. Those mixing ratios have wide range, and thus may aggravate the creation of mixed embeddings with conftict labels for MixupGraph. On the other hand, ratios being sampled from Beta(5, 1), Beta(10, 1) and Beta(20, 1) mostly fall in the range of [0.8, 1]. Such conservative mixing ratios may alleviate creating conflict training samples for MixupGraph. Promisingly, due to the intrusion-free nature, ifMixup did not suffer from the manifold intrusion problem, showing less sensitivity to the mixing ratios as in Figure
MC1109
NC1
MayDOuk
MUTAG
ENEYMES
PROTFINS
Figure 4: MixupGraph and ifMixup with mixing ratios from
Beta(1, 1), Beta(2, 2), Beta(5, 1), Beta(10, 1) and Beta(20, 1).
4.2.2 DVER-SMOOTIHING: IMPACT OF GNNS LAYERS
In this ablation study, we also evaluate the accuracy obtained by GCN, ifMixup and MixupGraph on the first six datasets of Table 3 when varying the number of layers of the GCN networks.
The results for all the six datasets are depicted in Figure 5 Results in this figure show that when increasing the GCN networks from 5 layers (blue bars) to 8 layers (red bars), both GCN and MixupGraph scemed to degrade its performance on all the six datasets. For example, for the NCI109 and NCII datasets, MixupGraph resulted in about 10% of accuracy drop when increasing the number of layers in GCNs (with Skip Connection) from 5 to 8. On the contrary, ifMixup was able to increase the accuracy on all the six test datasets.
Such decrease of accuracy ob- tained by GCN and MixupGraph may due to the over-smoothing problem (Li al.) 2018: Wu et al.) 2019). That is, with deeper net- works architectures (i.e., more lay- ers), the representations of all nodes of a graph may converge to a subspace that makes these representations unrelated to the in- put. This negative effect is mainly caused by the fact that the mes- sage passing between adjacent nodes is conducted along edge paths in GCNs. That is, each graph convolutional layer in the GCNs keeps pushing the representations of adjacent nodes to blend with each other, based on the fixed connections between nodes. Through generating new adjacency matrices for each training step by randomly deleting a portion of edges of the input graphs, DropE- dge (Rong al., 2020) has show its effectiveness on mitigating over-smoothing. Similar to DropEdge, ifMixup also creates graphs with changing node connections as inputs to the GCNs in each training step. That is, each mixed graph in ifMixup will provide a new adjacency matrix to the networks, making node connections very random and diverse that in DropEdge. These changing local neighborhood properties in the mixed graphs thus help ifMixup alleviate the over-smoothing problem when GCNs goes deeper.
FIC_EE
NOI
MUSS
FRZYWIS
PAOTEE
Figure 5: Varying the depth for GCN, ifMixup, and MixupGraph.
4.2.3 OVER-FITTING: REGULARIZATION EFFECT
In this ablation study, we evaluate the over-fitting effect of our method. We plot the training loss and validation accuracy of ifMixup, GCN, and MixupGraph methods across the 350 training epochs on both the NCI109 and NCII datasets in Figure 6
8

---

Under review as a conference paper at ICLR 2022
Figure 6 shows that the training loss of ifMixup (left subfigures) maintained a rel- atively high level, when compared to GCN and MixupGraph. For GCN, the training loss reduced to epochs. Compared to GCN, MixupGraph and ifMixup remained higher training loss, although the loss of MixupGraph kept de- creasing after 300 epochs.
NC1109
Phllos GCM Ailps
Acuuvny
NCCRDO
after 300 training
Phibux DCM bl Maxaaroophh
The relative high loss here allows the mod- els to keep tuning. Such high loss is due to the much larger space of the synthetic graphs as random and diverse inputs to the networks, thus preventing the model from being ever-fitted by limited number of graph samples in the original training set. As a result, as shown in the right subfigure, even training for a long time, the ifMixup models were not overfitting.
Figure 6: Training loss (left) and validation accuracy (right).
Note: a 2D visualization of the learned representations of the training graphs is presented in A.6
4.3 RESULTS OF USING GIN AS BASELINE
We also evaluate our method using the GIN (Xu et al. 2019 network architecture. The accuracy obtained by the GIN baseline, ifMixup. MixupGraph. DropEdge, and DropNode using GIN as where best results are in Bold.
baseline on the eight test datasets are presented in Table 2
GIN Baseline
ifMixup
MixupGraph
DropEdge
DropNode
Rel. Impr.
PTC MR NCI109
0.64410.007
0.002
0.601
0.669-10.003
0.66310.006
4.35%
0.82010.002
0.007=0.004
0.822=0.008
0.792-10.022
0.796110.002
2.07%
NCTI
0.818=0.009
0.809
0.822+0.001
0.791+0.005
0.785++00003
2.57%
MUTAG
0.886=0.011
0.090=0.006
0.884=0.009
0.854++0.003
0.859+0.000
0.45%
ENZYMES
0.52610.014
0.005
0.521=100077
0.488.10.015
0.528
3.23%
PROTEINS
0.745=00003
0.754
0.744=00005
0.749++0.002
0.751 005
1.21%
IMDB-M
0.519=0.001
0.002
0.518=0.004
0.517=0.0003
0.516 0.00
2.50%
IMDB-B
0.762=00004
0.765 : 0.005
0.701
0.762++0.005
0.764
0.39%
Table 2: Accuracy of the testing methods with GIN networks baseline. We report mean scores 3 runs of 10-fold cross validation with standard deviations (denoted =). The relative improvement of ifMixup over the baseline GIN is provided in the last row of the table. Best results are in Bold.
Results in Table show that, similar to the GCN case, the ifMixup with GIN as baseline outperformed all the four comparison models against all the eight datasets. For example, when comparing with GIN, ifMixup obtained a relative accuracy improvement of 4.35%, 3.23%, and 2.57% the PTC_MR. ENZYMES, and NCII datasets, respectively. When comparing with the Mixup-like approach MixupGraph, ifMixup also obtained higher accuracy on all the eight datasets. For example, ifMixup was able to improve the accuracy over MixupGraph from 82.2%, 82.2%, 63.1%, and 51.8% to 83.7%, 83.9%, 67. 67.2%, and 53.2% the NC1109, NCI1, PTC MRC and RMDB-M datasets, respectively.
5 CONCLUSIONS AND FUTURE WORK
We proposed the first input mixing schema for Mixup on graph classification. We proved that our mixing strategy can recover the source graphs from the mixed graph, and such invertibility in turn guarantees that the mixed graphs are free of manifold intrusion, a form of under-fitting which can significantly degrade Mixup-like model's predictive accuracy. We showed, using eight benchmark graph classification tasks from different domains, that our strategy obtained superior predictive accuracy over popular graph augmentation approaches and existing pair-wir wair-wise graph mixing methods.
In the future, we will extend our method for node classification in graph. Also, we will study the potential of our graph mixing schema on remantic-perseveringg graph mutation.

---

Under review as a conference paper at ICLR 2022
6 REPRODUCIBILITY STATEMENT
Our results are easily reproducible by following the experimental settings in Section 4.1 since our implementations used the PyTorch Geometric platform and the standard datasets from TUDatasets.
Also, we will make our PyTorch code publicly available upon the acceptance of the paper.
REFERENCES
Marco A. Alvarez and Changhui Yan. A new protein graph model for function prediction. Compula- lional Biology and Chemistry, 37:6-10, 2012.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. CoRR, abs/1409.0443 0473, 2014.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In Proceedings of the 37th international conference Machine learning, pp. 2729-222222222 2738. ACM, 2020.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over- smoothing problem for graph neural networks from the topological view. The Thirty-Fourth AAAI Conference on Artificial Intelligence, pp. -438-3445. AAAI Press, 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. CoRR, 2018.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learming on Graphs and Manifolds, 2019.
Kun Fu, Tingyun Mao, Yang Wang. Daoyu Lin, Y. Zhang, Junjian Zhan, Xi an Sun, and F. Li. Ts-extractor: large graph exploration via subgraph extraction based topological and semantic information. Journal of Visualization, pp. 1 18, 2020.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, 2017.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey E. Hinton. Speech recognition with deep recurrent neural networks. CoRR, abs/1303.577p 2013.
Hongyu Guo. Nonlinear mixup: Out-of-manifold data augmentation for text classification. Proceed- ings of the AAAI Conference on Artificial Intelligence, pp. 4044 4051, Apr. 2020.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Mixup as locally linear out-of out-of-manifold regulariza- tion. In AAA12019, 2019a.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Augmenting data with mixup for sentence classifica- tion: An empirical study. CoRR, 00044995.0 2019b.
William I.. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. NIPS' 17, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Wenbing Huang, Tong Zhang. Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. 2018.
Biaobin Jiang, Kyle Kloster, David F. Gleich, and Michael Gribskov. Aptrank: an adaptive pagerank model for protein function prediction on bi-relational graphs. Bioinformatics, 33(12):1829- 1836, 2017.
10

---

Under review as a conference paper at ICLR 2022
Amit Jindal, Arijit Ghosh Chowdhury, Aniket Didolkar, Di Jin, Ramit Sawhney, and Rajiv Ratn Shah. Augmenting NLP models using latent feature interpolations. In Proceedings of the 28th International Conference Computational Linguistics, December 2020.
Jang- Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. In International Conference on Machine Learning (ICML), 2020.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICI.), 2017.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. In Conference on Neural Information Processing Systems (NeurIPS), 2019.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convolu- tional neural networks. In NIPS, pp. 1097-1105, 2012.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In The IEEE International Conference on Computer Vision (ICCV), 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Sheila A. Mcllraith and Kilian Q. Weinberger (eds.), AAAI, 2018.
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs In ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL www. www.grrhheearninn....
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang. Ming Ding, Kuansan Wang, and Jie Tang. GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training, pp. 1150-1160. 2020.
Yu Rong. Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks node classification. In International Conference on Learning Representations, 2020.
Rui Song, Fausto Giunchiglia, Ke Zhao, and Hao Xu. Topological regularization for graph neural networks augmentation. CoRR, abs/2104.02447 2021.
Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. Sequence sequence learning with neural networks. CoRR, abss/140.32155 2014.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, (666):2579-2005 2008.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
Vikas Verma, Alex Lamb, Christopher Beckham, Aaron Courville, Ioannis Mitliagkas, and Yoshua Bengio. Manifold mixup: Encouraging meaningful on-manifold interpolation regularizer. CoRR, 2018
Vikas Verma, Meng Qu, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Regularized training of graph neural networks for semi-supervised learning. CoRR, 115/ 2019.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash (eds.), KDD '20, pp. 207-217.
Yiwei Wang. Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Graphcrop: Subgraph cropping for graph classification. CoRR, abs/2009. 10564, 2020.

---

Under review as a conference paper at ICLR 2022
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021. pp. 0663-666377 2021.
Zhenqin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learning. Chemical science, 92):513--30, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks. CoRR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L. Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 4805-4815, 2018.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 5812-5823. Curran Associates, Inc., 2020.
Chiyuan Zhang, Samy Bengio, Moritz, Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. 2021.
Guo Zhang, Hao He, and Dina Katabi. Circuit-gnn. gm:: Graph neural networks for distributed circuit design. In International Conference on Machine Learning, 2019.
Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. JCLR2018, 2018a.
Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Ustebay. Bayesian graph convolutional neural networks for semi-supervised classification. 2018b.
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11015-11023, 2021.
Jiajun Zhou, Jie Shen, and Qi Xuan. Data augmentation for graph classification. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management, pp. 2341-2344, 2020.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PROOF OF LEMMA
Proof: First note that the values in matrix ē can only take values in {0,A, X.1).
The set [r] x [n] of all node pairs can be partitioned into four sets:
Moo = {(i.j) E [n]
x
[x]] ea(t,f) 0, (,e((),)) = 0}
Mui = {(i,j) E [n]
x [2 :e((i,) = 0, (,e = 1}
M10 = {(i.5) E [n]
x [ :ea(i,)) L.eb(i,)) = 0}
M11 = {(i.5) E [n] x [2] :e((i,)) L.eB(( = =1}
is clear that
0,
if (i,j) E Moo
1 1- X
if (i.j) E Moi
E(1
X, if (t.J) E M10
1,
if (2,J) E Mn
Let e' and s be the solution of the equation in the lemma. On Mog we must have e = = ē. We only need to determine and e' on Moz and M1g- When & 0.5, we must have either
X, e(i,j) e(i,,)=
1, 0, (1,5) E Moi
(1,5) Miio and e'(,j)
{
0, 1,
(i, E Mio
(1, E Moi
or
8 = 1 eli, = 0, (i,j) M10
{
1,
(i,j) E M10
and el e'(i,))
(1,j) Moi
0, (1,j) E Mo
Comparing such solutions with e and éB, we prove the lemma.
A.2 PROOF OF LEMMA 2
Proof: We will prove the lemma by showing that for any i e [n]. based on u(i), we can uniquely recover uii) and (i)..
Case I: 0(i) = 0. It is obvious v(i) = (i) = 0.
for some E V and some scalar c. In this case, must be either or 1 - s. If c = s, then vii) = u, (i) 0. If c = 1 then vii) = 0, (1)) u.
Case 2: ((1) () V but T
V and any scalar o 0. For any two u, V, let SPAN(u, u') denote the vector space spanned u and v' Since V is a linearly independent set, it is clear every choice of (u, u') gives different space SPAN(u, u'), and w(i) must live in one and only one such space. After identifying this space, we can identify (u, u'). With the knowledge of we can precisely correspond and u' with vi) and v' (i) since either
Case 3: ō(i) V and ō * cu for any
v(i) and u' (i( are true, or u o' (i) and v(i) are true, but both can not be true at the same time.
Thus we have enumerated all possible cases, and each case, there unique solution to the equation of interest.
A.3 PROOF OF LEMMA 3 Proof:
Since the rows of B are linearly independent, there is unique T for which
TB.
We can recover 7 by projecting the rows of ē on the basis B. is clear sI' (1-+(1"s Then we only need to recover T and I' from T. But since T is linearly independent and T'T' E T, following a similar argument as in Case the proof for Lemma 2, we see that and T' can be uniquely recovered.
n.
13

---

Under review as a conference paper at ICLR 2022
A.4 STATISTICS OF BENCHMARK DATASETS
Table 3 details the statistics of the benchmark datasets used in the paper.
Name
graphs
nodes
edges
features
classes
PTC_MR
334
14.3
29.4
18
2
NC1109
4127
29.7
64.3
2
NCII
4110
29.9
64.6
37
2
MUTAG
188
17.9
39.6
2
ENZYMES
600
32.6
124.3
6
PROTEINS
1113
39.1
145.6
2
IMDB-M
1500
13.0
65.9
N/A
3
IMDB-B
1000
19.8
96.5
N/A
2
Table 3: Statistics of the graph classification benchmark datasets.
A.5 ILLUSTRATION OF MANIFOLD INTRUSION FROM MIXING GRAPH PAIRS
Intrusion
original graph: 1.0 class
original graph: 1.0 class
0.5 class1, 0.5 class
original graph 1.0 class
Figure 7: Manifold intrusion caused by connecting graph pair. The synthetic graph in the middle is created by connecting the two graphs from the left, but assigning soft label. This synthetic graph (with soft label) has the same structure the right graph with one-hot label.
Figure 7 depicts an intrusion caused by connecting a graph pair. The synthetic graph in the middle created by connecting the two graphs from the left, but assigning soft label (i.e., 50% of class and 50% of class 2). This synthetic graph has the same structure as the right graph from the original training set, with one-hot label (i.e., 100% of class 3).
A.6 VISUALIZATION OF THE LEARNED REPRESENTATIONS
In Figure 8 we also visualize the final layer representations formed by the GCN baseline, Mixup- Graph, and ifMixup on the original training graphs of the NC1109 and NCI1 datasets. We project these embeddings
using t-SNE (van Maaten & Hinton 2008).
The upper row of Figure 8 shows that for NCT109, both GCN and MixupGraph were not able to separate the two classes, while ifMixup completely separated the training graphs with different labels. Similarly, when considering the bottom of Figure aas for NCII, both GCN and MixupGraph did not completely divide the two classes, while ifMixup attained a perfect separation for the two.
A.7 UNEXPECTED RESULTS
We here also report an unexpected result.
We randomly shuffle the node order of one of the graphs in the graph pair before mixing for ifMixup. Such shuffling is able to significantly increase the number of synthetic graphs used for training for ifMixup, and expect this would further improve the model's predicative accuracy. The accuracy
14

---

Under review as a conference paper at ICLR 2022
baseling/hc1100
Mauppeaphh 10
ieeleupp NC1109
dlel dlea?
class clas2
00.0
Boreline/NC11
MisuGGaph/NCCI
IMbup/NCI1
130.00
10.0
<l8ss dD662
dass2 dass
Figure 8: 2D visualization of the learned representations of the training graphs NC1109 and NCII.
obtained over the first datasets of Table obtained by ifMixup with GCNs as baseline presented in Table
Unexpectedly, results in Table T that leveraging node order shuffling to increase the training data size did not help in terms of accuracy obtained. We hypothesis that this is may due to the modeling capability of the GCN networks. We will further investigate this hypothesis our future work.
iMMixup
without Shuffling
with Shuffling
PTC_MR
0,654
0.650110.004
NC1109
0.820:50.005
0.816:10.001
NCII
0,819:t0.004
0.817#0.001
MUTAG
0.879=00.003
0.864=0.006
ENZYMES
0.570+10.014
0.579+000008
PROTEINS
0.753++0.008
0.741+0.000
Table Accuracy of ifMixup with and without randomly shuffling the graph node order before mixing, with GCN networks as baseline.
A.8 A VARIANT OF MIXUPGRAPH
For GIN, the final-layer representation of a graph is the concatenation of all the represen- tations of each layer of the networks. In this sense, we can implement the idea of mixing on a random embedding layer as that in the Man- ifold Mixup Verma et al.) 2018) for vision.
MixupGraph
Manifold Mixup
PTC.MR
0.631=0.005
0.655#0.025
NC1109
0.82240.008
0.820=1.0007
NCI1
0.822+0.001
0.824+00005
MUTAG
0.88440.009
0.887+0..008
ENZYMES
0.501
0.505+100028
We compare Manifold Mixup with the Mixup- Graph, and the results are shown Table 5 Results in the table show that MixupGraph and Manifold Mixup obtained similar accu- racy on all the eight datasets. For example, for the PTC_MR and IMDB-M datasets, Man- ifold Mixup obtained higher accuracy, while the MESYMES and NC1109 datasets Manifold Mixup obtained lower accuracy than MixupGraph. For the other four datasets, the accuracy obtained by the two methods are comparable.
PROTEINS
0.744 0.747+10.008
IMDB-M
0.508
0.521+0.002
IMDB-B
0.761
0.764
Table 5: Accuracy of the MixupGraph and Man- ifold Mixup with GIN networks baseline. We report mean scores over 3 runs of 10-fold cross validation with standard deviations (denoted +).
15

---

Under review as a conference paper at ICLR 2022
A.9 SHALLOW GCN AND GIN
We also tested the performance of 3-layer GCN and 3-layer GIN baseline models. Results are presented in Table As can be seen in the table, both GCN and GIN baselines obtained inferior
GCN Baseline
GIN Baseline
PTC.MR
0.619 0.006
0.617: 0.003
NC1109
0.791 0.004
0.810 0.002
NCII
0.796 0.002
0.814 0.001
MUTAG
0.827 0.003
0.883:t 0.009
ENZYMES
0.508 0.015
0.497 0.003
PROTEINS
0.738 0.005
0.742: 0.007
IMDB-M
0.510 0.008
0.511 0.008
IMDB-B
0.748 0.008
0.758 0,002
Table 6: Accuracy of GCN and GIN with 3 layers. We report mean scores over 3 runs of 10-fold cross validation with standard deviations (denoted =).
accuracy than a deeper GNN networks, namely 5 or 8 layers as used the experiments in the main paper.
A.10 ILLUSTRATION OF MIXING AND GRAPH STRUCTURE RECOVERING
we illustrate how the mixed graph structure is formed and how the structures of the two source graphs can be recovered from the mixed graph.
In Figure g
forming mixed graph
recovering source graphs
1.0
1.0
10
2.
Graph
Graph (9a
Graph (vu.e))
Graph B: (g).
0.75
For each edge the mhxd graph: 1FF then and both exist
mdn, (1 206n
2 0.5, i, exists only
31 if 0.5, them eg exists onlly
75
F+10
0.75
0.15
mixed graph
mixad graph
Figure 9: Illustration of mixing and recovering in ifMixup.
16


Reviews:
[{"review_id": "sjDNdlUPozc", "reviewer": "Reviewer_n1Dk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Strength:\n\n1. Extending Mixup for Graph structured data is an important open problem and this paper attempts to address this.\n2. Paper is written clearly at most places, however the mathematical notation in Section 3.3 can be simplified. This section is presenting a very simple argument which can be given without using so much mathematical notations.\n\nWeakness:\n\nThe main claim of the paper that the proposed method avoids Manifold Intrusion, is unsubstantiated. It is correct that the edge connectivity of the individual graphs can be recovered from the mixed graph if the edges are unweighted, but how does it mean that the mixed graph  will not collide with some other existing graph or some other mixed graph. In the words of the authors \"By this lemma, we see that in ifMixup, the two source graphs can be uniquely recovered from the mixed graph, without the knowledge of the mixing coefficient. Thus it is impossible for the graph resulting from mixing to coincide with any other graph in the training set or with a mixed graph from any other graph pairs\" This is the main claim of the paper but there is no attempt to explain this.\"\n\nUnless, I am missing something very trivial, the above claim is not straightforward to deduce from the fact that the edge connectivity of the individual graphs can be recovered from the mixed graph. Moreover, the edge connectivity can not be recovered from the mixed graph if the edges are weighted. Similarly the node features of the individual graphs can not be recovered from the mixed graph. If the authors can address this in the rebuttal, I am willing to increase the score.\n\nThe results are marginally better than the baseline that does the mixing in the representation space, and other baselines such as DropNode and DropEdge.\n", "summary_of_the_paper": "The paper proposes a mixing strategy for graph structured samples. This strategy is works as follows : 1) take a pair of graphs 2) assign a node index from 1 to N to each node in the graphs, where N is the number of nodes in the larger graph. 3) for the smaller graph, create dummy nodes so that the total number of nodes in smaller graph becomes N. 4) Mix (interpolate) the node features and edge connectivity of the nodes with same indexes from the two graphs.\n\nThe main claim of this paper is that, such kind of mixing avoids the \"manifold intrusion\" problem.", "summary_of_the_review": "The paper proposes a mixing strategy for the graph structured datasets, but the main claim of the paper that the method is \"Intrusion Free\" is not correct in my opinion.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "ONCvpId1kC", "reviewer": "Reviewer_7hBS", "summary": "", "questions": "", "limitations": "", "rating": 5, "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- the proposed mixup strategy is simple\n- motivation for alleviating the manifold intrusion issue is clear  \n- I am satisfied with the parts on page 8 (the last sentence before section 4.2.3) and Figure 5, as the over-smoothing problem has been well-discussed. They demonstrate the proposed mixup method can work better when the over-smoothing issue is serious.  \n- eight graph classification benchmark datasets are used for evaluation. \n\nWeaknesses\n- in section 3.3, the authors proved the invertibility and concluded that the proposed method is manifold intrusion-free. \n> 1) The proof of invertibility assumes the graph edge’s weight must be 0 or 1. Can the proposed method be used for the graph with real-value edges [0,1]? \n> 2) When using a graph with real-value edge weights, does the proposed method still satisfy the invertibility?  \n> 3)The proof also requires the lambda not to be 0.5. But in standard mixup, the mixed sample can be generated in the case of lambda being 0.5. Thus, the assumption in this proof may not be correct. \n> 4)The most important question in this part is how the invertibility can induce “manifold intrusion free”? The connection between them is unclear. Assume your mixed sample can recover two original interpolation graphs, how to ensure that there is no conflict between the mixed sample’s representation and other training samples’ ones. Please explain this connection.\n- As you used 5- and 8-layer GNNs in experiments, why not consider shallower GNNs? As seen in Figure 5, baselines show better performance when using a shallower structure. \n- it is unclear what do you want to prove in section 4.3.1 as there are no connections to the proposed method. \n- there are several existing related papers that all use mixup for graph node-classification tasks. As your proposed method can be used for mixing two graphs, it can also mix one graph with itself. Besides, as in your title, it should be a general mixup method for graphs, right? For these reasons, it will be good to also do the evaluation on node-classification tasks. \nThen SOTA graph mixup method should be [1]. I would like to see a comparison between the proposed method and baseline [1]. ([2] should be a weak baseline as it does not work significantly better than the basic baseline GNN, see Table3.)  \n[1] 2021AAAI GraphMix: Improved Training of GNNs for Semi-Supervised Learning\n[2]2021 WWW MixupGrpah: Mixup for node and graph classification", "summary_of_the_paper": "This manuscript develops a mixup strategy for graphs. Specifically, as claimed by the authors, the proposed method is manifold intrusion-free. This is achieved by mixing two input graph pairs (some dummy nodes are needed, see Figure2) based on the standard mixup formulation. ", "summary_of_the_review": "Overall, the proposed method is simple. Its main limitation is their theory on invertibility and their experiments. In their experiments, as a general data augmentation method for graphs, node-classification tasks are also needed. The baseline of MixupGrpah is a bit weak. Stronger baseline - GraphMix is encouraged to be used for comparison. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "82hLPpbpvyr", "reviewer": "Reviewer_d3Ri", "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": "This paper proposes a very simple and logical algorithm for performing input mixup on graphs, and achieves excellent results with this technique across a wide variety of datasets.  It is also shown that this logically allows one to gain improvements from larger models and also from larger mixing rates.  It suggests many natural and interesting follow-ups, such as doing this same mixing in random layers, yet I feel this is a healthy and useful contribution for the field.  \n\nSmall Comments: \n  -Improvements are pretty nice and the table is very readable!  \n  -Additionally, improvement's stability as we increase mixing rate is nice to see.  \n  \n", "summary_of_the_paper": "This paper shows a very simple technique for performing input-space mixup on graphs, in which the vertices are put into an arbitrary order and dummy vertices are added to make the two graphs being mixed have the same number of vertices.  Mixing is then performed on the vertices and edges.  The improvements are excellent and seem to be SOTA on all benchmarks considered, often by nice margins.  \n\nDetailed Notes from reading paper: \n  -Mixing on graphs.  Theoretical guarantee that mixed graphs avoid intrusions.  \n  -Example of intrusion on mixed graphs is interesting, simple, and logical.  \n  -Proposed algorithm is \"Intrusion-Free Mixup\" ifMixup.  \n  -Edges and nodes take interpolated values.  Labels are interpolated based on edges.  \n  -Can recover source graphs from mixed graphs.  \n  -Task is to convert each graph into a single class (as opposed to each node having a class label).  \n  -Each node is assigned a distinct index, dummy nodes are created to make each \"graph\" same size.  Dummy nodes have no edges.  \n  -First construct \"soft\" edges by mixing edges between two graphs.  Network needs to be able to take soft edges.  \n  -Proof that this graph mixing operation is invertible.  \n  -ifMixup also shows benefit from more depth, as compared to baseline (which is probably badly overfitting).  \n", "summary_of_the_review": "The paper shows a way of interpolating graphs for graph classification and achieves excellent empirical results while showing that the interpolated graphs are invertible functions of the original graphs, avoiding the underfitting issues that may occur with other techniques for applying input mixup to graphs.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "1fw0aA9QEQC", "reviewer": "Reviewer_q8bs", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 research problem of data augmentation for graph classification is interesting and woth studying. \n2. This paper is overall easy to follow.\n3. The authors theoratically showed that the proposed ifMixup method is intrusion free.\n\nCons:\n1. The performance improvements shown in Tables 2 and 3 are quite marginal.\n2. The technical novelty is marginal considering the proposed ifMixup is basically a direct usage of Mixup on graphs.\n3. From my point of view, one of the main challenges of applying Mixup on graphs is that the nodes in different graphs are not aligned. For example, the first feature of two different data objects indicates the same physical feature in regular data. However, the nodes in graph data are not nicely aligned like the features in regular data. Therefore, the way that the authors arbitrarily assign the node indeces (as stated in Sec3.2) is not very reasonable to me. I would appreciate if the authors can give more explaination and motivation on why they choose this random index and why this is a good solution.\n4. Typos. e.g., A->B in Fig2; mixed usage of neighbor and neighbour.", "summary_of_the_paper": "This work studied the research problem of data augmentation for supervised graph classification. The authors proposed ifMixup, which is a Mixup-based data augmentation method on graph data. The authors also showed that ifMixup is free of the known manifold intrusion problem of Mixup-based methods.", "summary_of_the_review": "This work is very interesting, but I have slight concerns about part of the model design.", "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": {}}]

Author rebuttal:

Meta-review: This paper proposes a “Mixup” type of data augmentation for graphs that accounts for the difficulty of mixing graphs of different number of nodes. The authors show that the mixed graphs are invertible functions of the original graphs.

Reviewer d3Ri liked the simplicity and effectiveness of the technique. They called it a “healthy and useful contribution for the field”. Reviewer n1Dk thought that the paper explored an important problem and thought the paper was clear, though some of the math could have been simplified. This reviewer was concerned that a central claim of the paper, that the method avoids “Manifold Intrusion” was unsubstantiated. Specifically that it could not be deduced from the fact that edge connectivity could be recovered from the mixed graphs. The reviewer claimed that node features of the individual graphs were unrecoverable. The authors responded in detail to the reviewer’s criticism, adding two new lemmas which purportedly guaranteed node feature vectors could be uniquely recovered. The authors admitted to some conversion between “Manifold intrusion” and invertibility and added a Theorem and its proof that invertibility guarantees no manifold intrusion. The authors also responded to reviewer n1Dk’s concern about the significance of the reported improvements. Reviewer n1Dk responded to the author rebuttal with concerns about the strong and unrealistic assumption of linear independence of the feature matrix. They had further concerns that for the case of weighted edges the “Intrusion-free” property could not be enforced. Discussion ensued, with the authors arguing that the independence assumption was not as strong as the reviewer claimed and that the “Intrusion-free” property was only every for graphs with binary edge weights. 

Reviewer 7hBS and q8bs were both on the fence. 7hBS also raised some concern with the case of non-binary weighted edges. They also raised the same issue with respect to the connection b/w invertibility and the “Intrusion-free” property, which the authors addressed. Reviewer q8bs also thought the problem was interesting, the paper was clear, yet like n1Dk thought the performance improvement was marginal and had concerns with technical novelty of the work.

This was a tough call, so I engaged the reviewers in further discussion. 7hBS agreed with n1Dk’s opinion that the central claim of the paper (the method being intrusion-free) was not presented with strong evidence. They also raised another concern, which was that the paper didn’t evaluate on node classification like most other graph mixup-style models. Q8bs agreed with n1Dk’s concerns and felt that post discussion the technical novelty of the work was limited. Without strong support from the reviewers, I think that this paper could use further development, either lightening the “intrusion-free” claim or presenting evidence for it in other settings.
Decision: Reject