iGraphMix: Input Graph Mixup Method for Node Classification
Authors: Jongwon Jeong
Hoyeop Lee
Hyui Geon Yoon
Beomyoung Lee
Junhee Heo
Geonsoo Kim
Kim Jin Seon
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Network
Mixup
Node Classification
Data Augmentation
Theoretical Analysis
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Recently, Input Mixup, which augments virtual samples by interpolating input features and corresponding labels, is one of the promising methods to alleviate the over-fitting problem on various domains including image classification and natural language processing because of its ability to generate a variety of virtual samples, and ease of usability and versatility. However, designing Input Mixup for the node classification is still challenging due to the irregularity issue that each node contains a different number of neighboring nodes for input and the alignment issue that how to align and interpolate two sets of neighboring nodes is not well-defined when two nodes are interpolated. To address the issues, this paper proposes a novel Mixup method, called iGraphMix, tailored to node classification. Our method generates virtual nodes and their edges by interpolating input features and labels, and attaching sampled neighboring nodes. The virtual graphs generated by iGraphMix serve as inputs for graph neural networks (GNNs) training, thereby facilitating its easy application to various GNNs and enabling effective combination with other augmentation methods. We mathematically prove that training GNNs with iGraphMix leads to better generalization performance compared to that without augmentation, and our experiments support the theoretical findings.

Published as a conference paper at ICLR 2024
IGRAPHMIX: INPUT GRAPH MIXUP METHOD FOR NODE CLASSIFICATION
Jongwon Jeong's Hoyeop Lee², Hyui Geon Yoon², Beomyoung Junhee Heo?, Geonsoo Kim², Jin Seon Kim²
KRAFTON NCSOFT Co.
ABSTRACT
Recently, Input Mixup, which augments virtual samples by interpolating input features and corresponding labels, one of the promising methods alleviate the over-fitting problem on various domains including image classification and natural language processing because of its ability to generate a variety of virtual samples, and ease of usability and versatility. However, designing Input Mixup for the node classification is still challenging due to the irregularity issue that each node contains a different number of neighboring nodes for input and the alignment issue that how to align and interpolate two sets of neighboring nodes is not well-defined when two nodes are interpolated. To address the issues, this paper proposes novel Mixup method, called iGraphMix, tailored to node classification. Our method gen- erates virtual nodes and their edges by interpolating input features and labels, and attaching sampled neighboring nodes. The virtual graphs generated by iGraphMix serve as inputs for graph neural networks (GNNs) training, thereby facilitating its easy application to various GNNs and enabling effective combination with other augmentation methods. We mathematically prove that training GNNs with iGraphMix leads to better generalization performance compared to that without augmentation, and our experiments support the theoretical findings.
INTRODUCTION
Mixup (Zhang et al. 2018) is one of the effective data augmentation methods that help prevent the over- fitting problem of neural networks, particularly caused by a lack of labeled data in training. Mixup augments data by randomly selecting two samples from training sets and linearly interpolating samples and corresponding labels. Previous Mixup methods can be categorized into Input Mixup (Zhang eet al. 2018; Yun et al.] 2019). which directly interpolates input features and corresponding labels. and Manifold Mixup (Guo et al. 2019; Verma et al. 2019), which accesses the intermediate layer of neural networks to get hidden representations and interpolates them and corresponding labels.
Recent studies in Mixup have been primarily focused on Input Mixup in various domains including image classification and natural language processing, due to its two advantages. First, Input Mixup allows for the generation a wider range of samples compared to Manifold Mixup. This because Input Mixup can generate variety of virtual samples by employing several interpolation methods via input characteristics of each domain, such as patch incorporation from two images (Yun et al.. 2019) and substructure merging from two sentences (Zhang al.) 2022). In contrast, the mixing hidden representation has limitations on the diversity of interpolation because the embedding model projects an input space into ambiguous space Yoon et al. (021). Second, Input Mixup has ease of usability and versatility. It does not need to access the intermediate layers, thus eliminating the need for modifications to the models and making applicable any model architecture (Yoon et al.) 2021). In addition, it can be versatile with other augmentation techniques, enabling further extension studies (Berthelot et al.) 2019).
Due to the dissimilar input structure of graph neural networks (GNNs), irregularity and alignment issues may arise in applying Input Mixup straightforwardly to the node classification (Wang et al.. 2021). These issues render the application of Input Mixup challenging in the context of GNNs for
"This work done NCSOFT Co. Correspondence to: Jongwon boong<jjjeonggkraffee comp.

---

Published as a conference paper at ICLR 2024
node classification. GNNs receive not only the target nodes but also their corresponding neighboring nodes for the inputs. Then, GNNs employ a message- message-passing process to propagate information from neighboring nodes to the target nodes, followed by an aggregation process that combines the information of the neighboring and target nodes for prediction. This process introduces the irregularity and alignment issues that make it difficult to design Input Mixup for GNNs. The irreularity issue arises from the input of various numbers of neighboring nodes among target nodes, resulting in different input sizes between two target nodes in GNNs for interpolation. The alignment issue stems from the lack of inherent ordering among two neighboring node sets, leading to the challenge of how the nodes are applied the message- paassggg and the aggregation process even though the inputs are interpolated. As a result, previous works [Verma et al. 2021 Wang et al.) 2021) on Mixup for node classification have relied on Manifold Mixup. They prevent these issues but sacrifice the advantages of Input Mixup due to accessing hidden representations.
To cope with the two issues of designing Input Mixup to node classification in GNNs while sustaining the two advantages, we propose a simple yet effective Input Mixup method, called iGraphMix. The proposed method interpolates two nodes' input features, labels, and edges as follows. First, to generate a virtual feature and label for virtual training node, iGraphMix interpolates nodes' input features and associated labels, as the original Input Mixup does. Second, to construct virtual edges for a virtual node, iGraphMix randomly selects the neighboring nodes from each node. Then, our method attaches all selected neighboring nodes to generate the virtual edges. This attaching process for the virtual edges enables iGraphMix to avoid the irregularity issue occurring at interpolating the different edges of two nodes. Our method also helps to prevent the aligmment issue by employing the pessagg-passing and aggregation processes with the virtual edges. Furthermore, randomly selecting neighboring nodes in our method enables the generation of diverse virtual nodes without model modification, thus retaining the two advantages of Input Mixup.
Our study provides three main contributions. First, to the best of our knowledge, iGraphMix is the first Input Mixup method designed specifically for node classification the graph domain, addressing the irregularity and alignment issues of designing Input Mixup for GNNs. We believe that this work can serve as foundation research for Input Mixup on graphs, similar to recent developments in various domains such as image classification (Yun et al. 2019) and natural language processing (Kong et al. 2022). Second, we provide theoretical ana analysis ysis and experimental validation of how our method reduces the generalization gap. The results emphasize the importance and effectiveness of iGraphMix to regularize GNNs. Last, we experimentally confirm that training GNNs with the proposed method outperforms GNNs trained without augmentations by average of 2.84% in terms of the micro-F1 score across five benchmark datasets using three GNN models. We conclude that iGraphMix is an effective method to prevent the over-fitting problem and improve the performance of GNNs.
2 RELATED WORKS
Mixup Mixup has been recently highlighted due to its ability to mitigate the distorted interrelation-
ship problem arising in input data augmentation methods (Shorten & Khoshgoftaar [0019]
Naveed
et al. (021). Since they perturb only inputs VDeVries & Taylor 2017] (Singh et al. 2018 Edunoy
et al. 2018 Kobayashi (0188), neural networks may learn the distorted interrelationship between aug-
mented inputs and their corresponding labels (Zhang et al. 2018). Mixup can alleviate this problem by interpolating samples and their labels. While Mixup can be categorized into Input Mixup (Zhang al. 2018) and Manifold Mixup (Verma et al. 2019), recent studies have mainly focused on Input Mixup due to the ability to generate diverse virtual nodes and usability and versatility. Therefore, several Input Mixup methods were proposed to generate a variety of virtual samples depending on the characteristics of input structures in many domains (Kim et al. 2020 Qin et al. 20200] Liu et al.. 2022b Kong et al. 2022, Zhang et al., 2022). For instance, the image classification, Yun et al. (2019) extracted patches from two images and replaced each other to get augmented images. In natural language processing, Yoon et al. (202I) mixed two sentences by replacing a span of words, which is meaningful set of words in one sentence, with that in others. In contrast, iGraphMix is the first Input Mixup method designed especially for node classification that considers the characteristics of the input graph structure, setting it apart from Input Mixup methods in other domains.
Data Augmentation for Node Classification Data augmentation is an effective regularization technique to alleviate the over-fitting problem that often occurs in node classification due a lack of
2

---

Published as a conference paper at ICLR 2024
labeled nodes (Zhao al., this problem. For instance, DropEdge (Rong et al. 2020 and its variant (Gao et al.
2022). Several works tried to augment imput graph structures alleviate
2021 randomly
drop edges in the training graphs. DropNode (Feng et al. 2020: You et al. 2020) arbitrarily masks nodes and connected edges to augment training graphs. DropMessage (Fang et al.
2023) randomly
permutes passing messages from neighboring nodes. Other methods (Wang al.
2020 Zhao et al.)
2021
Park et al. 2021 Liu et al. 2022a) generate synthetic sub-graphs via auxiliary models or losses.
Meanwhile, some methods (Verma al. 2021 Wang al. 2021) were proposed design Manifold Mixup methods to augment inputs and corresponding labels for node classification due to alleviating the distorted interrelationship problem. They relied on auxiliary techniques to access hidden represen- tations due to the irregularity and alignment issues on the input graph. Specifically, GraphMix (Verma) et al. 202T utilizes not only GNNs but also introduces an additional fully connected neural network. Then, it applies Manifold Mixup on the nodes' hidden representation of the additional network. M-Mixup (Wang et al. 202T) augments two graph batches by permuting the order of nodes and edges in its augmentation process. Then, it interpolates the hidden representations of these two graph batches at each layer within GNNs. However, it was often challenging to generate diverse samples from those methods due to linearly interpolating hidden representation. Additionally, they lacked theoretical insights into the factors that contribute to the enhanced performance of GNNs through their methods. This paper proposes iGraphMix that directly addresses the issues for designing Input Mixup on node classification as well as preserves the two advantages that Input Mixup has. Also, we provide theoretical insight into why iGraphMix in node classification reduces the generalization gap.
3 PRELIMINARIES
Notations Let G = EV,E) be an undirected graph with n nodes Uy E V and edges (vi, U/) E E. For ease of mathematical manipulation, we define the matrix X E "R is the node feature matrix of n nodes with feature dimension do. A E Ruxn the adjacency matrix with Aij
if (v,, 0j) E and Aij = 0 if (Ui, vj) & &. Y E _R=x is the one-hot label matrix for nodes with given e classes. Note that, X indicates a v-th row vector of matrix X. means that each node v associates features X. and corresponding label Y...
Graph Neural Networks GNNs have shown remarkable success in node classification through
message- message-passing and aggregation processes (Kipl' & Welling 2017 Veličković et al. 2018 Wu 2.19p. The objective of training GNNs to learn a differentiable function f such that Y ~ Z = f(X, A). One basic structure of GNNs is graph convolutional network (GCN). The
K K-layer GCN model f is formulated as
H = a (AH* W*), Ak (1,........ K 1-
= AH
where W E Xdd=1 and WKK E Rdxx-ixe are the weight matrix of k-th layer for k: < K and K-th layer respectively, and Á the adjacency diffusion operator. Here, we initialize H = X, and are the point- pose activation functions that are assumed to be Lipschitz functions with Lipschitz constant Lg, respectively. The most popular adjacency diffusion operators are
A I and
A D + I) - (A + () + I) where D is a degree matrix of A (Kipf & Welling 2017). Also, diffusion operators are formulated attention methods that different importance weights of edges are applied to the aggregation process (Veličković et al. 2018 Brody et al. 2022).
Theoretical Analysis GNNs For the theoretical analysis, we focus GCN on the transductive node classification task. In transductive node classification, GNNs are trained on a subset of nodes within a specific graph and subsequently evaluated on the remaining nodes of that same graph. When training, the information of labeled nodes is backpropagated. Then, we state the generalization loss L and empirical loss L of GCN model f as follows:
C(fIX,Y.A 1
Σ
eZ Y.),
(2)
m
i=m+1
e eZ Yi).
(3)
m
3

---

Published as a conference paper at ICLR 2024
Mbop
CNN
MEuD
DrupEdge
M-Mixup
iGraphMiix (surs)
Figure 1: Illustrative comparison of DropEdge, M-Mixup, and iGraphMix. Red and blue circles indicate labeled nodes, and pink and sky-blue circles are neighboring nodes. When red and blue circles are mixed, they become purple. DropEdge randomly drops edge connection, and M-Mixup interpolates hidden representations. iGraphMix generates a virtual training node by selecting neigh- boring nodes and interpolating node features.
where the first m nodes are labeled nodes, also called training nodes, and is the loss function, e.g., cross-entropy loss.
Esser al. (202T) have recently provided a theoretical understanding of GCN. They provided the generalization gap bound of GCN, i.e., [(f Y, Y AA Y, by weights and biases parameter bounds. For simplicity,
restate the generalization gap bound of two-layer GCN without Il be the maximum absolute sum of rows and
bias terms as in Remark 3.1 Here, we refer
|| 1|2- be the maximum 2-norm of columns.
Remark 3.1 (Generalization Gap Bound for GCN (Esser al. 2021)). If = (S c W S for h E (1, 2}} and a is Tig-L.ppschizz continuous, the generalization gap bound for two-layer
GCN f satisfies
nab
- -UIX, m(n -m) || 2 (lgg(n) O (n, m, 8),
with probability 1 - given certain small E (0, a = 2Low, w and O (n, m, 6) is certain function of m, 8.
prevents over-fitting by randomly dropping edges during the training. This edge perturbation produces a new graph similar to the original graph so that allows the model to be learned through diverse graphs. The only difference between the standard GNN learning procedure and DropEdge is the adjacency matrix. Let A be the original adjacency matrix, and Mp be the masking matrix that makes dropping edges with probability p. During the training. DropEdge replaces the adjacency matrix A with
DropEdge DropEdge (Rong
2020
ApropEdge Mp A,
where o the Hadamard product of the matrix. Remark that, M, is shared with all layers, and we apply the adjacency diffusion operator on A DropEdge-
4 OUR METHOD: IGRAPHMIX
In this section, we introduce iGraphMix, a simple yet effective Input Mixup method for node classification, as illustrated Figure To provide an intuitive understanding of the proposed method, we present motivating example that involves two papers from various domains: one in machine learning and the other chemistry, each with its own set of citation papers. When writing new multidisciplinary paper (i.e., mixing labels) that combines the two aforementioned papers, such as synthesizing chemical molecules via machine learning, straightforward approach is to mix the main text (i.e., mixing features) and cited papers (i.e., mixing adjacency matrix) from both papers. This
4

---

Published as a conference paper at ICLR 2024
simplistic example shows what iGraphMix aims to do. In Definition 4.1 iGraphMix on node classification a batch-wise manner.
present the process of
Definition 4.1 (iGraphMix for node classification). Let M, be the masking matrix with À dropping probability. iGraphMix mixes feature matrix, one-hot label matrix, and adjacency matrix as follows:
X = XX + ()-A) Y AY + +1
= MI A+ MA o A',
where (X', Y,,A)
A') is the permuted batch within labeled nodes of (X, Y.).
The most important point of mixing two nodes is blending the edges shown in the last equation of Eq. (4. The last equation in Eq. may be quite different from our intuition. This is because we regard the masking matrix as selecting neighbor matrix. In other words, M and M, indicate that neighbors are chosen with probability À and 1 1 X, respectively. Thus. in order to apply the importance to neighbors, we have to multiply M1 by A and vice versa. Here, the mixing coefficient À is drawn from Beta(a, at) in Mixup Zhang al. 2018). This distribution is symmetric and becomes a uniform distribution when a = 1. When a becomes smaller and smaller, sampled with values in the vicinity of zero one. It means that the proposed method generates new virtual node that is very similar to one of the original nodes when a is small. On the contrary, when becomes larger and larger, À is sampled with values in the vicinity of 0.5. In this case, the proposed method produces a new virtual node in which two original nodes are evenly mixed. Note that MA and M are shared with all layers. For the detailed implementation of iGraphMix in Pytorch- like code, please refer to Appendix A
5 THEORETICAL ANALYSIS
In this section, we theoretically analyze why GCNs trained with iGraphMix prevent over-fitting and generalize well compared to GCNs trained without data augmentation on the transductive node classification. Our theoretical analysis is inspired by Zhang et al. (202I) who analyzed Mixup in the generalization view, and [Esse al. (2027 who attempted to theoretically explain GCNs' behavior on the transductive node classification.
For the theoretical analysis, we consider simple two-layer GCN with a point-wise ReLU activation function and one-onneeeet me--immesioonl output that classifies two classes -1 or 1. The GCN output logits of m training nodes are
Z.m (Ao (AXW)) W2) mm
= WAH,WW)
where Z.m first m rows of Z. We denote that 2 from substituting node features and adjacency diffusion operator on Eq. 5 to those defined in Eq. (4). Also, Ze,e' states the v-th output logit interpolated v-th and e' nodes by iGraphMix. Then, we introduce the empirical loss for iGraphMix train the GCN model in Eq. (5) as Definition 5.1
Definition 5.1 (Empirical loss iGraphMix). Let À ~ Beta(a, a),, M be the masking matrix. Then, the empirical loss for iGraphMix can be formulated as
2 Y,
A)
PA,M
Σ v,y'=1
m
e (Zuarr Yesor)
m
Note that the labeled nodes in Eq. (6) are the same those in Eq. 33. It means that the only difference between them is using the Mixup dataset or not. Also, we consider the mean-square error (MSE) loss function for y-th node defined as l (Z., Y.)
Z Y (Zhang et al. 2021).
For the theoretical analysis, we suppose that there is no connection between labeled nodes. This assumption is quite reasonable for two-layer and the semi- cemi-supervised setting, e.g., Citeseer dataset contains only 1.71% % connected edges of labeled nodes out of all edges. Then, L.2 shows that iGraphMix induces additional regularization of the trainable weights for the standard training.
5

---

Published as a conference paper at ICLR 2024
Lemma 5.2. Let R(22) be the certain function of the second-order of W2. Then, L(f|X, Y L(J|X,Y, A) + 2))
From the regularization point of view, we can reduce the weight space for iGraphMix with a related dual form of regularization term as
JiGraphMix := ( C fill Will 11x S w, and R (22) S w),
where wi is the certain scalar values such that > 0. Then, we provide the generalization gap bound with given weight space SiCraphMix in Theorem 5.3
Theorem 5.3 (Generalization Gap Bound for GNN trained with iGraphMix). For any f in the weight space of iGraphMix fiGraphMix. we have the generalization gap bound as follows:
nabe
C(fIX,Y,A A) [(f) Y. A) m(n m)
|A|l |A
llg(n) + +0 Axlla-)oooog())
m.
where a 2Lig b - / 2/d1, and Q (a, X) when Q(-) the certain function of (-)
Theorem 5.3 providees the evidence that weight space induced by iGraphMix could provide a tighter upper bound of generalization gap than standard training for the certain condition of beta distribution's 's parameter a and the data statistics (A, X). implies that the optimal a could vary with respect to the graph characteristics. Thus, we easily confirm Corollary Corollary(5.4tthr that an upper bound of the generalization gap tends to be smaller in iGraphMix compared to standard training with appropriate a.
Corollary 5.4. Let Ian and fiGraphMix be the optimally trained model by standard training and iGraphMix training respectively. Further, U (-) means the upper bound of (.). With appropriate a for A and X, the following inequality holds with high probability.
U (Cifaial X, Y. A) -(faia X, Y. A1) 2 U (ClfiGraphMis X, X,Y, A) 2 fiGraphMii X,Y, .)).
The detailed proofs are referred to Appendix
B
EXPERIMENTS
We compared the iGraphMix with five graph data augmentation methods: (1) None that trains GNNs
with the graph which is not applied any augmentation methods; (2) DropEdge (Rong et al. 2020
that trains GNNs with the graph whose edges are randomly removed each training epoch; (3)
DropNode (Feng et al. 2020) that trains GNNs with the graph whose nodes are randomly masked at
each training epoch: (4) DropMessage (Fang et al. 2023) that trains GNNs with perturbing propagated messages at each training epoch; (5) M-Mixup ( (Wang et al. (02T) that trains GNNs by interpolating nodes' hidden representations and corresponding labels. As some previous methods (Verma et al..
2021 Zhao al. 102 Liu et al. 2022a) require additional modifications to the model, auxiliary loss, and training techniques, there is potential for deviating from the authors' original intent while forcing them to other GNN models. Therefore, excluded these methods from our experiments.
For the transductive node classification, We considered five datasets: CiteSeer, CORA, PubMed (Sen) et al. 2008), ogbn-arxiv (Hu al., 2020), and Flickr (McAuley & Leskovee 2012). In CiteSeer, CORA, PubMed, and ogbn-arxiv, the nodes are the papers, and there are edges when one paper cites another paper. The goal of these datasets is to predict the subject class of each paper. Flickr is dataset from an image-sharing SNS. In Flickr, nodes are images, and edges are connected when images share certain information, e.g. common hashtag. aims to predict the category or community class of nodes. Furthermore, we conducted experiments on inductive node classification and link prediction tasks, and the results are shown in Appendix E In short, our method experimentally outperformed comparative methods even for these tasks.
In order to demonstrate the superiority of various GNN models trained using iGraphMix over the baselines, this study selected three GNNs as the backbone models for evaluation: GCN (Kipf & Welling 2017). GATv1 (Veličković et al. 2018), and GATv2 (Brody et al., 2022). We evaluated the generalization gap and the performance of iGraphMix and other augmentation baselines. Then, we examined the proposed method and other baselines by manipulating the number of layers and the number of nodes per class to show consistent improvement of method. Lastly, we confirmed the versatility of iGraphMix by combining it with other augmentation methods. We refer to Appendix C for more details of experimental settings.

---

Published as a conference paper at ICLR 2024
Table Overall Micro-Fl score (%) on the datasets. The results are the average scores and standard deviations of ten trials with different random seeds. OOM means the out- out-of-memory.
Data
Datasets
Backbone
Augmentation
CiteSeer
CORA
PubMed
ogbn-arxiv
Flickr
None
72.05 (0.56)
82.65 (0.55)
79.32 (0.15)
67.11 (0.75)
52.77 (0.14)
DropEdge
72.07 (0.28)
83.20 (0.07)
79.38 (0.19)
68.17 (0.39)
53.59 (0.07)
DropNode
72.48 (0.44)
82.65 (0.23)
79.52 (0.11)
67.61 (1.17)
53.29 (0.18)
GCN
DropMessage
73.35 (0.46)
83,40 (0.61)
79.60 (0.60( (0.32)
68.71 (0.30)
53.55 (0.10)
M-Mixup
71.52 (0.80)
80.28 (0.66)
78.63 (0.32)
65.82 (0.61)
(0.25)
iGraphMix (ours)
73.67 (0.61)
83.78 (0.42)
79.93 (0.60)
68.93 (0.35)
53.61 (0.12)
None
(1.13)
79.98 (0.69)
77.75 (0.63)
65.08 (1.03)
52.07 (0.28)
DropEdge
71.45 (1.02)
82.65 (0.60)
77.85 (0.28)
67.98 (0.40)
53.07 (0.21)
DropNode
70.78 (0.65)
81.33 (1.00)
77.11 (0.75)
67.49 (0.65)
53.05 (0.25)
GATvI
DropMessage
72.20 (0.52)
83.39 (0.60)
78.00 (0.55)
68.45 (0.35)
52.95 (0.30)
M-Mixup
72.02 (0.64)
82.06 (0.85)
78.93 (0.58)
OOM
52.09 (0.20)
iGraphMix (ours)
72.28 (0.60)
83.20
78.41 (0.31)
69.49 (0.41)
53.22 (0.18)
None
70,41 (1.91)
79.11 (0.80)
77.87 (0.51)
65.63 (0.75)
$1.79 (0.43)
DropEdge
71.15 (0.78)
82.20 (0.62)
77.94 (0.51)
67.84 (0.74)
53.23 (0.21)
DropNode
70.33 (1.59)
80.44 (1.84)
77.90 (0.42)
68.64 (0.61)
53.38 (0.61)
GATv2
DropMessage
71.49 (1.02)
82.27 (1.28)
78.19 (0.63)
68.66 (0.45)
53.06 (0.23)
M-Mixup
72.90 (1.47)
82.06 (0.91)
78.36(0.55)
OOM
52.38 (0.20)
iGraphMix (ours)
71.97 (0.66)
82.80 (0.49)
78.73 (0.33)
69.82 (0.31)
53,90 (0.20)
Train
2.2
iGraphMix
GDA Mehool
1.2
1.8
DrupEdge
DropNodee
0.8
1.4
DropMessage
0.6
M-Mixup-
1.0
1000
2000
1000
2000
0.0
0.2
0.4
0.6
0.3
Ejoch
Gencrslizaiinn Glpp Train)
(a) Without augmentation
(b) With iGraphMix
(c) Final Generalization Gap
Figure 2: Generalization ability of GCN. (a)-(b): Train and test loss with respect to the training epochs ((a): Without augmentation, (b): With iGraphMix). (c): Final generalization gap over all augmentation methods.
6.1 OVERALL RESULTS
The overall results on node classification are summarized in Table [ We compared iGraphMix with five graph data augmentation methods in terms of the test micro-F1 score of models at the best validation micro-F1 score epoch. We found that the proposed method outperforms the models without data augmentation by 2.84% on average. Reminding Lemma 5.2 this result may indicate that iGraphMix is the effective regularization method to improve the test micro-F1 score in the various datasets and backbone models. We also confirmed that iGraphMix outperforms DropEdge, DropNode, and DropMessage across the five datasets and three backbone models. This result may imply that iGraphMix generates augmented graph data that mitigates the distorted interrelationship between augmented graphs and labels better than DropEdge, DropNode, and DropMessage do. In addition, from the result that iGraphMix outperformed M-Mixup by an average of 2.41% 1,, we may infer that iGraphMix generates more diverse virtual nodes from the vicinity of original nodes than M-Mixup, preventing the over-fitting problem more effectively.
7

---

Published as a conference paper at ICLR 2024
0.70
0.59
0.0
0:30
6:0
0:5
(a) CiteSeer
(h) oghn-arxiv
(c) Flickr
Figure 3: Generalization gap with respect to Beta distribution's parameter a on various three datasets.
6.2 GENERALIZATION GAP
Compared with Baselines We examined whether iGraphMix can improve the generalization ability by reducing the generalization gap analyzed in Section | Figure the generalization gap of GCNs trained with six augmentation methods on CiteSeer. Compared the loss in Figures 2a and 2b we found that the gap between the test and the training loss of GCN trained with iGraphMix is consistently smaller than that of GCN trained without augmentation methods. This result empirically supports our theoretical finding that iGraphMix improves the generalization ability of GNN. We compared the generalization gap of iGraphMix with other augmentation methods in Figure 2c It empirically shows that GNNs trained with iGraphMix have a smaller or comparable generalization gap than GNNs trained with other augmentation methods. We also found the similar results in other datasets as shown in Appendix D.I
Beta Distribution Parameters We verified Corollary 5.4 that the generalization gap becomes smaller depending on the appropriate beta distribution parameter a for the graph characteristics. Beta distribution parameter controls the amount of diverse augmented graphs of iGraphMix for training. When we set a small, iGraphMix is likely to generate graphs similar to the original graph. Conversely, when is large, iGraphMix is likely to generate well-mixed graphs. The generalization gap with respect to the parameter a is illustrated in Figure 3 We confirmed that the performance of iGraphMix, which utilizes the data augmentation approach, is similar to the method without augmentation when a is near zero. Also, we found that the generalization gap of iGraphMix becomes smaller when a large. This result reveals that the generalization ability becomes better when well-mixed graphs are used in training. In addition, by comparing the optimal generalization gap in CiteSeer, ogbn-arxiv, and Flickr in Figure we verified that the optimal a these datasets are 100, 10, and 50, respectively. This result empirically supports Corollary 5.4 that the different datasets require different optimal a to achieve the small generalization gap.
Corollary5..41th
6.3 ANALYSIS ON VARIOUS SETTINGS
In this section, examined how manipulating the number of layers and labeled nodes affects the performance of iGraphMix. The results of GCN on the CiteSeer are presented and analyzed. Comprehensive results obtained from other datasets and models can be found in Appendix D.2
Number of Layers K We evaluated the micro-Fl score depending on the number of layers K. Increasing K of GNN leads to the over-smoothing problem (Li al. 2018). as node embeddings become indistinguishable by considering the larger- hop relationship between nodes. Thus, this experiment also tested that the proposed method mitigates the wer-shhothing problem. Figure 4a shows the performance of the proposed method for the different K. We found that training GCN with iGraphMix improves the micro-F1 score by 2.33%, 6.25%, and 6.39% for two-, four-, and eight-layer GCNs respectively compared to that without augmentations. This result may imply that our method improves the micro-Fl score of GNNs with various K. More importantly, the results indicate that training GNNs with method may diminish the over-smoothing problem regardless of K. Since iGraphMix changes connected edges and corresponding labels in each iteration, the proposed method mitigate the representation collapse of connected nodes at each training step.
Number of Labeled Nodes per Class L As illustrated in Figure 4b] score of the proposed method by changing the number of labeled nodes per class L. We confirmed
we assessed the micro-FI
8

---

Published as a conference paper at ICLR 2024
Noce (Gapbiii
Noce Kiispblii
Mope Soote (95)
Map-Fi Sueee 196
78
60
20
50
160
Pill
Nan. Larer
Labcled Nosios Class
(a)
(h)
Figure 4: Analysis of iGraphMix on the various number of (a) layers and (b) nodes per class by Micro-F1 score (%).
that training GCN with iGraphMix increases the micro-F1 score compared that without augmen- tations by 1.41%, 2.33%, 5.22%, 1.39%, 0.80%. and 0.61% % for L = 10, 20, 40, 80, 160, and Full, respectively. Notably, we found that our method can be more effective in improving the micro-FI score when training with fewer I. than fully labeled nodes. This result may imply that iGraphMix alleviates the over-fitting problem, especially for the lack of labeled data.
6.4 COMBINATION WITH OTHER AUGMENTATION METHODS
We verified the versatility of our method by applying iGraphMix after other aug- mentation methods were employed at each train- ing step. Table 2 shows the comparison between the performance of None, DropEdge, DropNode, and DropMixup with that of unifying iGraphMix and them on CiteSeer with 2- layer GCN. We found that unifying iGraphMix with other augmentation meth-
Table 2: Micro-Fl score (%) of unifying iGraphMix with other aug- mentations on CiteSeer.
Data Augmentation Methods
Performance
DropEdge
DropNode
DropMessage
iGraphMix
72.05
73.67
72.07
73.97
72.48
73.75
73.35
73.93
ods leads to performance improvement with 1.86% average. This result shows that iGraphMix is versatile with other augmentation methods to boost the performance of GNNs, similar to Berthelot al. 2019)).
7 CONCLUSION
Summary This paper proposed iGraphMix that addresses the irregularity and alignment issues of Input Mixup on node classification. Specifically, to address the two issues, iGraphMix does not only interpolate node features and labels but also aggregates the sampled neighboring nodes. Theoretical analysis of the generalization gap and our experiments on the real-world graphs showed that the proposed method effective in regularizing GNNs by generating diverse virtual samples and preserving high usability and versatility.
Future Works There are two possible directions for future works. The first direction is to find a better edge sampling method for Input Mixup on node classification, similar to the research on Input Mixup in the other domains (Kim et al. 2020 Kong et al. 2022). The second direction to combine improvements of other techniques in graph learning, such pseudo- pseudo-labeling (Verma et al.) 2021 and consistency loss (Feng et al.] 2020). with iGraphMix. We hope this work could be the crucial step improving Input Mixup node classification.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
Our method may not consider mitigating biases or inequalities. Our work initially focused on the technical aspects and did not explicitly address potential biases inequalities that might arise. However, we believe that there can be potential future direction to address biases and inequalities in algorithms based on our method.
REPRODUCIBILITY STATEMENT
Our method is built on Pytorch 1.12.1. Paszke al., 2019) and Pytorch Geometric 2.1.0 (Fey & Lenssen 2019). The licenses of Pytorch and Pytorch Geometric are available under BSD-style and MIT respectively. Our experiments were conducted on NVIDIA V100 with CUDA version 11.3. Refer to the appendices for further reproducibility details, such code, hyper-parameters, and so on.
ACKNOWLEDGEMENT
We appreciate Youngin Cho from NCSOFT Co. and Moonseok Choi from KAIST for their valuable feedback on this paper.
REFERENCES
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin Raf- fel. Mixmatch: A holistic approach to semi-supervised learning, Advances in Neural Information Processing Systems, 32, 2019.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Interna- fional Conference on Learning Representations, 2022.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with
variance reduction. In International Conference on Machine Learming, 942-950, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Terrance DeVries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint 17X1v:170..04555: 04552, 2017.
Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. Understanding back- translattn at scale. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 489-500, 2018.
Ran El- Caniv and Dmitry Pechyony. Transductive rademacher complexity and its applications. Journal of Artificial Intelligence Research, 35:193-234, 2009.
Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances Neural Information Processing Systems, 34:27043-27056, 2021.
Taoran Fang, Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. Dropmessage: Unifying random dropping for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp. 4267-4275. 2023.
Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han. Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for superiuper learning on graphs. Advances in Neural Information Processing Systems, 33:22092-22111 221033, 2020.
10

---

Published as a conference paper at ICLR 2024
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Zhan Gao, Subhrajit Bhattacharya, Leiming Zhang, Rick S Blum, Alejandro Ribeiro, and Brian M Sadler. Training robust graph neural networks with topology adaptive edge dropping. arXiv preprint arXiv:2106.02855 2021.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 855 864, 2016.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Augmenting data with mixup for sentence classifica- tion: empirical study. arXiv preprint arXiv: 0094,, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Advances in Neural Information Processing Systems, 33:221 22133,, 2020.
Jang- Hyun Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statistics for optimal mixup. In International Conference on Machine Learning, pp. 5275-5285, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations, 2017.
Sosuke Kobayashi. Contextual augmentation: Data augmentation by words with paradigmatic relations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computationnl Linguisties: Human Language Technologies, Volume (Short Papers), pp- 452 452-457, 2018.
Fanshuang Kong, Richong Zhang, Xiaohui Guo, Samuel Mensah, and Yongyi Mao. Dropmix: A textual data augmentation combining dropout with mixup. In Proceedings of the 2022 Conference on Empirical Methods Natural Language Processing, pp. 890-899, 2022.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for suni-supervieed learning. In Proceedings of the AAAI conference on artificial intelligence, 2018.
Songtao Liu, Rex Ying. Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Jun Huang, and Dinghao Wu. Local augmentation for graph neural networks. In International Conference on Machine Learning, pp. 14054-14072, 2022a.
Zicheng Liu, Siyuan Li. Di Wu, Zihan Liu, Zhiyuan Chen, Lirong Wu, and Stan Z Li. Automix: Unveiling the power of mixup for stronger classifiers. In Computer Vision-ECCV 2022: 17th European Conference, Tel Aviy, Israel, October 23-27, 2022, Proceedings, Part XXIV, pp. 441 441-458. Springer, 2022b.
Julian McAuley and Jure Leskovec. Image labeling on network: using social-networe metadata for image classification. In European Conference on Computer Vision, pp. 828-841, 2012.
Humza Naveed, Saeed Anwar, Munawar Hayat. Kashif Javed, and Ajmal Mian. Survey: Image mixing and deleting for data augmentation. arXiv preprint arXiv: (XXi:2/06.00086 07085, 2021.
Hyeonjin Park. Seunghun Lee. Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung- Kim, Jung- Woo Ha, and Hyunwoo J Kim. Metropolis-hastings hastings data augmentation for graph neural networks. Advances in Neural Information Processing Systems, 34: 14:1900--19020, 2021.
11

---

Published as a conference paper at ICLR 2024
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Py PyTorch: An Imperative Style, High-Performance Deep Learning Library. Advances in Neural Information Processing Systems, pp. 8024-8033 2019.
Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pp. 1532-1543, 2014.
Global vectors for word
Jie Qin, Jiemin Fang, Qian Zhang, Wenyu Liu, Xingang Wang, and Xinggang Wang. Resizemix: Mixing data with preserved object information and true labels. arXiv preprint 1rXiv:2012.11101, 2020.
Yu Rong, Wenbing Huang, Tingyang Xu, and Jun Huang. Dropedge: Towards deep graph convolu- tional networks on node classification. International Conference on Leurning Representations, 2020.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Ran Rad. Collective classification in network data. Al Magazine, 29(3):93-93, 2008.
Connor Shorten and Taghi M Khoshgoftaar. A survey on image data augmentation for deep learning. Journal of Big Data, 6(1):1143 2019.
Krishna Kumar Singh, Hao Yu, Aron Sarmasi, Gautam Pradcep, and Yong Jae Lee, Hide-and-sedd A data augmentation technique for suply-super localization and beyond. arXiv preprint 1rI 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations, 2018.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In 2019.
International Conference Machine Learning, pp.
Vikas Verma, Meng Qu Kenji Kawaguchi, Alex Lamb, Yoshua Bengio, Juho Kannala, and Jian Tang. Graphmix: Improved training of gnns for semi-supervised learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 10024-10032, 2021.
Yiwei Wang, Wei Wang, Yuxuan Liang. Yujun Cai, Juncheng Liu, and Bryan Hooi. Nodeaug: Semi-supervised node classification with data augmentation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 207-217, 2020.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. In Proceedings of the Web Conference 2021, pp. 3663-3674, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp. 6861-6871, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453-5462, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. International Conference on Machine Learning, pp. 40-48, 2016.
Soyoung Yoon, Gyuwan Kim, and Kyumin Park. Ssmix: Saliency-based based span mixup for text classification. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pp. 3225-32234 2021.
12

---

Published as a conference paper at ICLR 2024
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33: 5812-5823, 2020.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp.
2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference Learning Representations, 2018.
Le Zhang, Zichao Yang, and Diyi Yang. Treemix: Compositional constituency-based data aug- mentation for natural language understanding. In Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 9243-5258, 2022.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou. How does mixup help with robustness and generalization? In International Conference on Learning Representations, 2021.
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, pp. 10015-1002,, 2021.
Tong Zhao, Gang Liu, Stephan Günnemann, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. arXiv preprint 1,8877 2022.
13

---

Published as a conference paper at ICLR 2024
APPENDICES
In the appendix, we provide the implementation details of iGraphMix, precise proof of our theoretical findings, and additional experiments on various settings that are not shown in the main text due to space limitations.
A IMPLEMENTATION DETAILS OF IGRAPHMIX
We provide the PyTorch-like style implementation of iGraphMix for node classification in Algo-
rithm !
Algorithm iGraphMix: Pytorch-like Implementation with Torch Geometric.
import numpy
isport
fron torch geonetrio, data import Data
fron tarch, gecnetric, utilli inport dropout ad3
data: Torch-geanetric Graph iipher llet distribut fon hyper-pereneter bateh_oize: Number of crain nodez
instance
reatures, edges,
L_greph_nize miip alpha, i dJ Sampie lambas lanoda_. up.randon.bbtee betall.eeell.................... beho alpha)
Index Pormutation
Index toreh. randpern (batch. size)
index torca. (ladex, torch. arange saatct__ize, data. (h)) dim-u; zeros index_new zeroh tindex (h)p dtype-torch... Long) [indee
arange index. anepee))
21 Mede festure Mixup c.coxecloone de
x_nixup lambda_
(1-lambda_) X[index)
# 31 Label HIXUP datt..y.coone setach
y. y_nixup Lamboa_ y [1-lambda_) yländex)
# d) 5dge Mixup edge_index 200, sdes_indox cione decach() (9], edge_irdex clona 1) detach [1]
wargge_ideexxoooooee clone detacai)
zow, csl iadex_new. (o.tant)dccccchh [row], ladex_new, con.coonn (o.one)..deetee detach [co1]
adoa_index_pomm stack.stack[[so) coll, dimet)
Propare Mixp Graph
edea_indes, a (adde (adro_ index, p-1 1al-lands__ training-Prue
cde__index_pem,, dzopout_ads iedos_ pemm, p lanbaa__ training True)
edp__index_nixup torch.cat cat (iedge_ caeedgg index, edgo_index pnsmx__emm_p_ din-11
daca_nixus (ata yey_nixu,, edge_index odde indossoo__odd
aspa_nixop.rrsiiumes treis_mask cata.croin_mak
data_nixup, valk data.val_mask
data_nixuo.tstt. data.
return data-riixp
def (modal,
eptimizor, alpha, bstch_size)
model. Lrain()
11 Hix-up gr4ph
data_nixup (ixdal alphe, batchaiiee
Inforence
oulggl = model (dala_nixup.s, dats wwdge indes)
Caiculate optinize Zoes
losx__une joulgut, deta-nixup. [rbetch_aize])
loss. bas.bback
ini zer.
14

---

Published as a conference paper at ICLR 2024
B PROOF IN THEORETICAL ANALYSIS
This section provides the proof details of theoretical findings. We state A, and A., be v-th row and column vector of the matrix A respectively. For the theoretical analysis, consider the adjacency diffusion operator A == A + I.
As in the Section we assume that there is connection between labeled train nodes. It means that AX = AX'= = AX as mixup only applies at labeled nodes. Thus, this assumption can induce the following equation.
(A +) = (M- + MA o x
- X + MA A' + X,
(8)
Then, we derive Lemma B.1 to change the output logits in Eq. from the general form to the iGraphMix form.
Lemma B.1.
Given any random variable X. the permutation P. and the masking matrix M, we have
P. Z.m] EA.P,M [((++)) mm
when there is no connection between labeled train nodes, and Hi = XH, + (1
Proof. EM
Z.m]
can be formulated as follows by Eq. (8)
EAPP,M
[um]
ExPP,M
((A+ D)o (Ā XWW W2 mL
[(A+ D)o (M AX MA A'X' + x) Wi) x)wi) Wa
-AAP.M
EMPP.M
((A+ ( D)o ((M1 AX + MA o A'X' +XX + (1 A) Wi) W:
( ((A+ D)o ((M AI) X + (M, o A' + (1-11))1 -)))) X Wi) W3
EAP...M
((A+ T)o (((AA+ + ((1 - A)A' + +1 (1-)) x') Wi Ws)
EAPP
((A++ D)o (AAXWI + AA) W₂)
EAP..M
((A I) (oo (AXW)) + - (1- (A'X'W;)) W₂
E.PP.M
(9)
EXPP.M
((Ā+ + 1)HH W₂
(10)
EAPP.M
(AA+T)
(11)
where Eq. 9 holds because o has a property that (A2)) Xa for any R. Eq. 10 is from definition of hidden feature, Eq. (II) is from the definition of mixed hidden feature.
15

---

Published as a conference paper at ICLR 2024
Also, we introduce Lemma B.2 that the mean of the aggregated representation from iGraphMix is the same as the mean of the original graph's 's aggregated representation. is utilized in the proof of Lemma 5.2 and Theorem 5.3]
Lemma B.2. Consider any X Px. P be the random permutation, i.e. Hi PH and A' PAPT, and M be the masking matrix. Then, L/mEv=1 Ep,M 1/m E H,
(A + 1), H) =
Proof. We begin with reformulate 1 1/m Ev= H, with H1 and (A I).
1
(HH)
(AH)).
1=1
m
(AH,), +11 2) (AH.)
m
Ep [A (AHH), + (1 (PAH1), .
Ep [MAH] + (1 -1- (1 PH))
(12)
m
Bp [AAH + (1 A)A (1-)))'HH
(13)
Ep (AĀ(AH)) AA(( ()HA)
A)A'H +1 -) A)HI) ]]
Ep (AA((1 (1-1))),,, -HH) + (1
() - H.),,) -H)), (14)
where Eq. (22) is due to normal matrix property for permutation matrix, Eq. 13 is due to the
definition A', H' based on permutation matrix. Since 1/m Em [E, (H HD Eq. (14 becomes 0. Then,
(AH))
Σ Ep (1-
(1- (1- (AH + (1 ())
1 m
Ep
+
m
1
+ (1- [1AA+(1-NAA)
Ep
m
Ep [(AA+ (1 (1-1)A
A)A' + 1)HA). ).]
1
m
EP.M
1)Hi)). [(A++))
+
(15)
m
1
EP.M
(Ā H1
m
16

---

Published as a conference paper at ICLR 2024
where Eq. 15 is due to the following equations.
+ A)A' A A + +1 - X)1 A
EM [M- A+ + M, o A
= EM [A]
B.1 PROOF OF LEMMA 5.2
Before providing the proof of Lemma 5.2 we show Lemma B.3 and LemmaB..4to get the approximate form of iGraphMix loss.
Lemma B.3. Let Dx ==
1, + at. Beta(B 1, be the permutation induced by the randomness for mixed larget samples, M be the masking mutrix. Also, consider Z, be the w-th virtual node output logits given X and A that are followed by the distribution D2 and the permutation P. Then, the empirical loss converted as follows.
1 Σ m
M Ep [e(Z,, Y.)
Proof.
m
C(fIX Y. A)
Σ
Ex. le
Vvree) )
m²
2,0'=1
Ex.M || - 8 8o.nr 112
m2
0,0'=1
Ex. 2T Zo,o - 2ÿ
Bo,y' - + T 1100 D,o!
m
0,0'=1
EA.M
2T Dow - + -) A) Y.r) Z0,0r E
E EAM A 2 Zo,orZu.0r Zo,0' -2Y.T Zo,er + Y, Y.)
m
2,0'=1
(1
ZT. E...'' -YY. Zoror + Y,!! Y:
EAM XY, (Ye,er Y.) + - (Ý Yor)
m
EX.M [e)Bern(A) [0 (ZtT. - 2Y.T Zo,o' + Y. X. |
+.TY.
m²
0,0'=l
EAM (Q) (1 (1- (2, Zn, - 2X Zo,ar or + YJJ Y.
E,0'=1
(16)
BerBer ( [Ex-Baslo+Q.841100) [Qe(Zo.r' Y.)
m²
0,0'=1
m
E Eqw 2. (Ex.Betal(o+0.841111 (1-Q)(((2 20,(Z Y..)
(17)
17

---

Published as a conference paper at ICLR 2024
E. (e [1(2
(( Y.)]
m2
m
E Bx- [(Zu..r k3r)
(18)
m 2
a +
1;00
where
Eq.
due
to Bernoulli
distribution Em
property
and
Emn'=1 AY, (Y v.o Y,) (1 A (Y a. Y.))
Y, 1,00 Y.)
(1- 2) Ex [ (Y, Y,) 0. Eq. 17 holds due to conjugate property of beta and Bernoulli distribution, Eq. (18) due mean Q is a (a + (3) when Q 1, and mean of Q when Q ==0.
a+8
As Beta(a, 1) and Beta(8 1, a.) are the same distribution and Ze (1 - A) Zz (A).
we have
m
Í Y. A)
Σ
a
Bow ((Zo,,r
m
a
+ 3
v,0'=1
3
Ex BA- (
m
+
0,0"
(((2 e, X.)
N~ tg Beta(a++1,))+ ass Beta(S+1a)
v,y'=1
m
EX-DA.M ((Zu,,'
(19)
m²
0,0/=1
where Eq. 19
is due to DA Beta((a 1, utg Bela (3+ +1, o.) and satisfying distribution
a+B
property of Dx. From the definition of P and Z., have
1 Σ
201 8, A)
E D..M
(Zo Y..
v'=1
1
m
E BX
Ep
[((Z.: Y.)]
m
Lemma B.4. When D and P are the distribution of lambda and the permutation of mixed target samples defined in Lemma B.3 Then. we approximate the empirical loss of GCN trained with iGraphMix by that of GCN trained without augmentation method as follows.
20 /
R1 R2.
1
where Rí
Ex M.
Ep [((A+ I). H, A, W2(Z, -Y)]]
m v=1
R2
E By
Ep
W. ((Á H, A.H.) T ((Á
I). A. We
m
Proof. Note that Z, A, W2 and Z, (A H) Wa as shown in Lemma B.1 Then, apply the second-order Taylor Theorem e (,., Y,) with respect to A, H. W2. We have
18

---

Published as a conference paper at ICLR 2024
02 (2. Y,) HA,H:W
(2), 2 (Z. Y,) + ((A+ H) A.H,
1
8 (Z. Y.) (A - H.W - (.H.
((A H, W. - A,H,W,)
2
W2)²
(20)
Since 8 (Z,, Y.) = 111z. - Y. 11, we have the first-order and second-order term of l as follows.
(e Y,
az.
dE (Z. Y.)
0A H.W. 2 0A H. W
dZv
(21)
Zu Yu.
(Z,, Y,)
0e 0e(2,, (Zu, Y.)
A, H w2)
OA H
OA, H W2
(1Z -Y,))
DA H W₂
(22)
Oz.
0
dz, (Z. - Y.)
DA H. W₂
I.
Substituting Eq. 21 and Eq. 22 to Eq.
20
we get
((Z Y.) ~ l( Yo) + +1 + 72.
s.t. r1 ((Å +I, A H W2 -Y,,,
1
F2 2 ((Å+ +
) () A.H.W,))
W ((Å+ 1)+ - - (( I), AA, W2.
2
Thus, we obtain the result as follows.
m
[( Y. A)
E M.DD.M
Ep [((Z., Y.)
(23)
m
E D M
Ep [L Y.) +
0=1
E X D
M Ep [[ Y.)I]
m
m
E x W...
Ep [ri]]
D. . Ep
M
m
Yo) +
E Ex~DAM m Ep [rill
m Σ
1
E VDDD.. M [Ep [ra]]
C X Y, A) + R1 + Ro,
where Eq. 23 is due to Lemma B.3
Now, we are ready prove Lemma 5.2 Remind Lemma B.4 we have
f A) 2 Y A) R R2,
19

---

Published as a conference paper at ICLR 2024
m
s.t. R1
Σ
Ex .M
Ep ((Á
I). A.Hi) T (2 - -Y))
(Zu
R2
1
Ex.M
Ep
2 ((A+ 1). 11 - )1) ((A+
1,H W₁
2
where X' o+3 Beta (a 1,
atp Beta (8 + 1, 1,
3
Then, should verify what Ri and Rg are. First, from Lemma B.2 we can get Ri 0.
For R2, we have
m
1
W ((A + I1 A.H.)) T ((A+I) -.HH. A,H:) W2
R2
Ex.
Ep
m
W
Ex.M
Ep
[(A + H1 A,H,)) ((A 11 A.H.)) W2
2m
==1
= R(W2).
B.2 PROOF OF THEOREM 5.3
Let S = 1/m T Ex.M Ep ((Á + (I.+)). - -., T ((A
I) A. H.Hl
Rdixd1, We reformulate R(W2) for short-hand notation of the remaining proof.
m
BX. Ep [(A+ A.H.)) ((A+I), H) A.H.)] W₂
R 2)
W m
W2 SW2.
Next, we consider the constraint R(W2) S w where wt be the certain scalar value in Eq. the weight space fiGraphMix is represented follows.
Then,
fiGraphMix {f fll I w. W. SW2 s 2w..
(24)
Then, we introduce Transductive Rademacher Complexity (TRC) and the generalization error bound induced by TRC in Definition B.5 (El-Yaniv & Pechyony 2009 Esser et al. (021).
Definition B.5 (Transductive Rademacher Complexity EEl Yaniv & Pechyony 2009 Esser et al.
2021)). Suppose we have m labeled samples over total samples, and p [0, 0.5L. Let 2 C T be the possible output logit space with n samples and Φ = {Ø1,... ... .on } be the independent and identical distributed random vector where Φe + 1 with probability 2p and Φ 0 with probability
1 - 2p. Then, TRC is defined as follows.
1
Rm. (Z)
E.
sup & Z
(25)
m
n
Z
For any f whose output logit Z E 2 and the input graph (X, Y, and A), the generalization error bound is bounded with TRC as follows.
C(f) Y. A) L() < Rm (2) + O (n, m, 5,
(26)
with probability 1 - 5 where L(f) and Ż(f) be the generalization and empirical error of f.
Also, TRC has the scalar multiplication and convex hull property as in the below lemmas. Those lemmas are proved in Esser et al. (2021).
Lemma B.6 (Linear combination). Let C R", C C R", and E R. Then,
I) Scalar multiplication: Rm (tbb/bb E B}) ||t|l (B), 2) Addition: Rm
C) Rm,, (B) + Rm (C).
20

---

Published as a conference paper at ICLR 2024
Lemma B.7 (Convex hull). Let B R", B' -E 3 NN, 60) E BB B, 0), and [1,- - ..]. Then, Rm, (B) = 1131|19mm.. (B").
Then, we need find the TRC bound with output logit space induced by fiGraphMix to get the generalization error bound. Let W = [[ ....,..... [W2la]] Rd. Similar to the lemma given in Esser et al. (202I), we can get the second-layer TRC bound as follows.
Lemma B.8 (Second- layer TRC bound). Let (-)t/2 be the squared inverse matrix given (-), and Ro (H) be the TRC of the first-layer hidden representation space. Then, we get the second-layer output logit space TRC upper bound follows.
Rm (2) < 21 |am (H).
Proof. We first get the following inequality.
Z [AH, W2lv
W 2 AH,
W2l Σ
A
H
===1
W2/1
A
Hi)
1==1
Y
A. A'
W2l1
H1).
||||
[[
(27)
1=1
where Eq. 27 is due to the definition of ||
1l.o. From the above inequality, we define the new logit spaces F as follows.
di
W H
W. SW₂ s 2w 2
Since || is a scalar, we upply Lemma B.6 to get the upper bound of Rm, with the above inequality as follows:
Rm,, n (2) $ || Hm,
Let V S1/2 Rd4 and H. = St/2 gaxd, Then, we have the logit spaces F. Fm and Fi as follows.
V2ll2 s 2w 2 ).
V2l 1
d2
Fint
Voll A
V2ll1 S 22 dzw
F
1el J.
V2ll =2ddiw
21

---

Published as a conference paper at ICLR 2024
Note that FF and FF are equivalent. Since \V2l22 I dd V2l22, we have F Fmt.. Also, maximum
value over V/2 with inequality constraints is converged at the borderline, i.e. ||V/||1 = 2/djw. This induces a (Fint) FFm,((Fnn Thus, we have
Rm, (2) - A Rm,, (F)
A ~c H (F)
< || A Rmm (Fint)
A Rr (Frt).
Since can think 1/2 as the (3 in Lemma B.7
Rm (3) < | V/2 R (Hine)
s 2| A || no V diwR (Hlin)s
where Win be the hidden logit space of H1 as
d2 Hilba
Hime
Then, we get the following inequality.
d
d1
Σ
Hila
Σ Im1
H [St/ 1
d1
H 1r [S 1//2 /2,rr
('=1 i=1
d1
St/2 V.
41
<
H 11. |||
P=1
di
< ||st/|||0 60 Σ
H b...
Thus, from Lemma B.6
we have
Rm (hatt
st Ilo (H).
Therefore, have the TRC upper bound as follows.
Rm, (2) s All / |]w|] |/ Rm, (H).
Also, we get directly the first-layer TRC upper bound from Proposition 3 in Esser et al. (2021). Lemma B.9 (First-layer TRC bound (Esser et al.) 2021)). Let Rm (H) be the TRC of the first-layer hidden representation space, and bog be the Lipschitz constant. Then, we have the TRC upper bound of Rm (H) as follows.
2log n d1
R Rm m (H) Lo
AX 12- V
m(n - m)
Applying Lemma B.8 and Lemma B.9 to Eq. (26). we have
c(fix, Y, A) [( Y. A)
R m (Z) + O (n, 6)
2 A ~0 / | |122 Rm (H) + O (n, m,
2 2 n
2 L
|| || 00 v / St/2 bowl AX 12
+ 0 On,
m(n
m)
d1
n
abell A l| oc
2-300 AX
V log + 0 (n, m, 6)
m(n - m)
22

---

Published as a conference paper at ICLR 2024
where 2Low, b = w and vdi | Note that, in the definition of S, is function of X' A, and H1. This means that e is the function of a, A, X. Therefore, Q(o, A, X) where Q is the certain function, then Theorem 5.3 is satisfied.
C EXPERIMENTAL SETTINGS
C.I DATASETS
We used CiteSeer, CORA, PubMed, ogbn-arxiv, and Flickr for the transductive setting, The detailed statistics for each dataset are summarized in Table
Table 3: Datasets statistics for the transductive setting.
Dataset
CiteSeer
CORA
PuhMed
oghn-arxiv
Flickr
Nodes
3,327
2,708
19,717
169,343
89,2500
Edges
4,552
5,278
88,648
1,166,243
899,756
Features
3,703
1,433
500
128
500
# Class
3
40
7
# Valid Nodes
500
500
500
29,799
22,313
# Test Nodes
1,000
1,000
1,000
48,603
22,313
Sparsity
0.082
0.144
0.023
0.008
0.011
Average Degree
2.74
3.90
4.50
2.74
10.08
Edges Between Labeled Nodes Ratio (%)
1.78
0.40
0.00
0.32
0.21
Planetoid Benchmark We considered the three benchmark citation network datasets for the transductive node classification task: CiteSeer, CORA, and PubMed (Sen et al.) 2008). The goal of the node classification of these datasets is to predict the appropriate subject class for each paper. CiteSeer, CORA, and PubMed contain scientific publications, machine learning publications, and biomedical publications respectively. Thus, they consist of the papers as the nodes, citation links between papers as the edges, and the subject of the papers as the labels. Node features are constructed via the bag-of-wo words feature representation of the paper document. We followed the labeled node per class and the train/test dataset split settings for Table used in Yang et (Yang al. (2066).
Open Graph Benchmark (OGB) We also considered the one citation network dataset for the transductive node classification task: ogbn-arxiv (Hu et al. 2020). The goal of the node classification of those datasets is to predict the appropriate subject class for each paper. ogbn-arxiv contains all computer science (CS) arxiv papers provided by Hu et al. (Hu et al. 2020). Thus, it consists of papers as the nodes, citation links between papers as the edges, and the subject of the papers the labels. Node features are constructed via the kip-gram representation of papers' titles and abstracts. To make ogbn-arxiv semi-supervised, we sampled 10% nodes from the original training node set for Table I (Fng et al. 2003).
social network dataset for the transductive node classification task: Flickr (McAuley & Leskoved 2012). The goal of the dataset is to predict the category and the community of each post. The nodes for Flickr is the image posts. The edges between nodes exist if the images share common properties, e.g., geometric location, gallery, etc. Node features are the image pixels. The training and evaluation nodes are split by creating dates of post (Hamilton et 2017). For Flickr, we used the original training node sets, similar to Fang et al. (2023) for Table
Flickr We considered
C.2 BACKBONE ARCHITECTURE
To evaluate the effect of iGraphMix various GNNs, we utilized three well-known backbone GNNs. First, we used GCN (Kipf & Welling 2017). which is the simple version of the diffusion operator in GNNs. Second, we utilized GAT (Veličković et al. (2118) and GATv2 (Brody et al. 2022). which use attention mechanisms in the diffusion operator in GNNs.
C.3 HYPERPARAMETERR
Hyperparameter settings all datasets and models are as follows. For CiteSeer, CORA, and Pubmed, used Adam Optimizer (Kingma & Ba 2015) with 0.01 learning rate and 5e-4 weight decaying,
23

---

Published as a conference paper at ICLR 2024
dropout with 0.5 probability, and 16 hidden units for GCN. Also, we used Adam Optimizer with learning rate of 0.005 and weight decaying of 5e-4, dropout of 0.5 probability, 16 hidden units, and 1 head for GAT and GATv2 (Zhao et al. 202T; Verma et al. 2021]. We trained the above models by 2000 epochs and reported the test scores when the validation scores were the maximum. For ogbn-arxiv, used Adam Optimizer (Kingma & Ba 2013) with 0.005 learning rate and 5e-4 weight decaying, dropout with 0.0 probability. 256 hidden units, and 3 number of layers for GCN, GAT, and GATv2 (Fang al. ).23). Also, we used head for GAT and GATv2. We added batch normalization layers between GNN layers. We trained the above models by 200 epochs and reported the test scores when the validation scores are the maximum. For Flickr, we used Adam Optimizer (Kingma & Ba 2013) with 0.001 learning rate and 5e-5 weight decaying, dropout with 0.0 probability, 256 hidden units, and number of layers for GCN, GAT, and GATv2 (Fang et al. 2023 Also, we used head for GAT and GATv2. We trained the above models by 2000 epochs and reported the test scores when the validation scores were the maximum.
C.4 GRAPH DATA AUGMENTATION METHODS
For the baseline augmentation methods, we found the best drop probability parameters from [0.1. 0.9 for DropEdge (Rong et al. 2020), DropNode (Feng et al. 2020), and DropMessage (Fang et al. 2023), and beta distribution probability from (0.001, 0.005, 0.01, 0.05, 0.1, 0.5, 1,5, 10, 50, 100 for M-Mixup (Wang et al. 2021), and iGraphMix.
C.5 EXPERIMENTAL DETAILS
We conducted our experiments on the V-100 with CUDA version 11.3. GNNs for our experiments are built on Pytorch Paszke et al. (0119) with version 1.12.1. and Pytorch Geometrie (Fey & Lenssen 2019) with version 2.1.0. For the baseline augmentation methods, we used the implementation of DropEdge (Rong et al. 2020) and DropNode (Feng et al. (2200 in Pytorch Geometric and employed
the original paper implementation for DropMessage (Fang al. 2023) For M-Mixup (Wang et al.
2021 we utilized the original paper implementation
D ADDITIONAL RESULTS
We reported the additional results that were not handled in the main context due to the space limitation.
D.1 GENERALIZATION GAP
Compared with Baselines We reported the generalization gap analysis for GCN on the other transductive datasets; CORA, PubMed, Flickr, and ogbn-arxiv. Figure Figure Showed the generalization gap results on CORA, PubMed, Flickr, and ogbn-arxiv, similar Figure 2 We could confirm consistently smaller generalization gap in iGraphMix compared to no augmented training. This result may support our theoretical claim in Section 5 that iGraphMix showed a smaller generalization gap compared to standard training with high probability. Furthermore, we found that the final generalization gap of iGraphMix tends to be consistently smaller than other augmentation baseline methods in these datasets. This can empirically support the claim in Section 6.2 that iGraphMix does make a smaller generalization gap not only in CiteSecr but also in other datasets, such as CORA, PubMed, Flickr, and agbn-arxiv.
Beta distribution parameters a We observed the generalization gap with respect to a on CORA, and Pubmed for 2-layer GCN in Figure Similar the results in Section 6.2 the generalization gap of iGraphMix in CORA and PubMed becomes smaller when a is large. Notably, we verified that the optimal a of these datasets is 50. On the other hand, as shown in Figure 3, the optimal of CiteSeer, ogbn-arxiv, and Flickr are 100, 10 and 50, respectively. Therefore, these results may strengthen the claim in Section 6.2 that the different datasets require different optimal achieve the small generalization gap.
http:://yyoorrr.ooooooootetteaaa geometric
24

---

Published as a conference paper at ICLR 2024
Train Test
Truin Test
1.15
Nose
1.75
Xlrghhis
GDA Medhod
1205
1.50
Umopiddee
1.25
DropNode
1.00
DmpMesage
M Mixup
0.25
1000
2000
1000 Epoch
2000
0.0
0.1
0.3
Epoch
Grnemiization Gap (Test- Trint
(a) Without augmentation
(b) With iGraphMix
(c) Generalization Gap
Train
Train
Text
1.2
XimphMix
1.0
GDA Mechol
1005
0.6
Droplidge
0.8
DropNode
0.4
DmpMessage
0.2
Mixup
0
1006
2000
0
1000
2000
Gap (Test- Thia)
(d) Without augmentation
(c)
iGraphMix
(f) Generalization Gap
4.0
Train
3.0
Test
Test
2.5
3.0
XimphMix
GDA Meñtod
2.0
Dropidge
2.5
DrepNode
2.0
1.0
DmpMessage
0.5
M-Misup
100 Epoch
200
Epoch
Generlization Gap (Test Trim)
(g) Without augmentation
(h) With iGraphMix
(i) Generalization Gap
Train
1.8
Tes
1.8
Test
None
XimphMix
1.6
1.6
ODA Methed
105
Drolidge
1.4
DropNede
DmpMesage
1.2
12
M-Mlsup
0
1000 Epoch
2000
1000
2000
0.06
0.10
0.15
0.25
Epoch
Goneriliaation
Without augmentation
(k) With iGraphMix
()) Generalization Gap
Figure 5: Generalization Results of GCN with CORA ((a)-co), PubMed ((d)-(e)), ogbn-arxiv ((g)-(h)), and Flickr (i)-()).
25

---

Published as a conference paper at ICLR 2024
0.50
Choeraleattin ExpClea- Thaie)
0.44
0.425
0.46
0.400
10.44
Generiiiaaiinn Clg
0.375
0.42
0.350
0.40
0.325
0.38
None
Nose
Mis
0.300
KGrghhixx
0.36
10
10
(a) Cora
(b) PubMed
Figure 6: Generalization gap results on other datasets with respect Beta distribution's parameter for 2-layer GCN, A small generalization gap reveals a better result.
Table 4: Ablation results on three transductive datasets.
Augmentation Methods
CiteSeer
Cora
PubMed
None
72.05 (0.56)
82.65 (0.55)
79.32 (0.15)
iGraphMix (input+label)
71.50 (0.47)
81.26 (0.27)
79.18 (0.53)
iGrraphMix (edge+lahel)
72.44 (0.81)
82.72 (0.21)
79.18 (0.33)
iGraphMix (Input+edge+label)) (proposed)
73.67 (0.61)
83.78 (0.42)
79.93 (0.60)
D.2 ANALYSIS ON VARIOUS SETTINGS
We assessed the performance GCN with various settings, such as the various number of layers and labeled nodes on CORA, PubMed, ogbn-arxiv, and Flickr, which we did not describe in the main context due to paper limitations. Figure showed the micro-F1 score of the various number of layers and the number of labeled nodes on CORA, PubMed, ogbn-arxiv, and Flickr with the 2-layer GCN model. Note that we considered the ratio of labeled samples rather than the number of labeled nodes per class on ogbn-arxi arxiv and Flickr. This is because these datasets originally provided labeled nodes based on the overall labeled ratio, not the per-class ratio.
From Figures 7a 7c 7c and 7g observed consistent improvement of the micro-Fl score in iGraphMix with varying numbers of layers on these datasets, similar to the result on CiteSeer shown in Figure 4a These results may support claim that iGraphMix improves the micro-F1 score in the various number of layers. Additionally, these results may imply that the proposed method mitigates the over-smoothing problem.
7f and 7h showed that the proposed method improves the micro-F1 score regardless of the number of nodes. Importantly, we found that our method be more effective in improving the micro-Fl score when training with fewer L than fully labeled nodes on these datasets, like the result on CiteSeer shown Figure 4b] This result may also imply that our method addresses the over-fitee fitting problem, especially with fewer labeled nodes.
Moreover, Figures 7b 7
D.3 ABLATION STUDY
We We conducted the ablation study on iGraphMix and the result is summarized in Table 4
compared our method with 1) applying mixup only to input and label, iGraphMix (input+label), and 2) applying mixup only to edge and label, iGraphMix (edge+label), on three transductive datasets, CiteSeer, Cora, and PubMed, for node classification. We observed that iGraphMix (input + edge+ label) consistently outperforms not only the standard training but also iGraphMix (input+label), and iGraphMix (edge+label). This result may imply that interpolating all components of the graph is crucial, showing method's 's effectiveness. Furthermore, iGraphMix (input+label) consistently underperforms the standard training, and iGraphMix (edge+label) is better or comparable to the standard training. It may suggest the importance of applying mixup on the edge for graph datasets.
26

---

Published as a conference paper at ICLR 2024
None KinghMis
None iGriphMix
56
Mice-Fi Strre (8))
80.0
Mice-F] Score (%)
-44
77.5
75.0
82
72.5
20.0
07.5
78-
3
Nuss Layers
Labeted Nodes / Cllass
(a) Number of layers
(b) Number of labeled nodes per class
None
XimphMixx
[GrnghMix
MicioFl Scare (80
78
77
Micn-Fl Soore
-44
76-
82-
75
10
20
40
Num. Layers
Labeled Nodes / CClsss
(c) Number of layers
(d) Number of labeled nodes per class
XimphMix
71
iGrpphMix
MicceF1 Seore (%)
Micn-FI Scorer (8)
70
69
65
100
Num. Layers
Labeled Nodes (9)
(e) Number of layers
Labeled node ratio
54.0
None
KinghMis
(ClaphMiis
53.5
$3.0
Mcmo-FI Seore (6)
Scum (8)
$3.0
62.5
52.0
52.5
55.55
51.0-
31.5
50.5
3
20
80
80
100
Num. Layers
Labeled Nodes (%)
Number of layers
(h) Labeled node ratio
Figure 7: Micro-F1 score in various different number of layers and labeled node ratio on Cora((a)-(b)) (ubMed((c)-()), ogbn-arxiiv())-()), and Flickr((g)(h)) datasets. The results are the average scores of 10 trials.
27

---

Published as a conference paper at ICLR 2024
Table 5: Robustness results with feature noise on three transductive datasets.
Dataset
CiteSeer
Cora
PubMed
Noise level (%) 10%
20%
40%
10%
20%
40%
10%
20%
40%
None
66.90
66.89
66.12
78.10
77.76
77.92
75.46
74.62
73.36
iGraphMix
68.48
68.54
68.30
79.00
78.64
78.76
75.78
75.80
74.88
Table 6: Robustness results with structural noise on three transductive datasets.
Dataset
CiteSeer
Cora
PubMed
Noise level (%)
10%
20%
40%
10%
20%
40%
10%
20%
40%
None
67.62
61.88
54.90
78.62
73.14
60.96
73.92
71.88
60.20
iGraphMix
68.94
63.22
55.82
79.14
74.06
61.78
74.54
72.56
61.22
Table 7: Robustness results with label noise on three transductive datasets.
Dataset
CiteSeer
Cora
PubMed
Noise level (%)
10%
20%
40%
10%
20%
40%
10%
20%
40%
None
68.2 68.24
64.14
57.72
79.10
76.00
67.60
77.32
75.76
68.64
iGraphMix
69.08
65.92
58.62
80.02
76.42
69.08
77.66
76.00
69.04
D.4 ROBUSTNESS TEST
We evaluated the robustness of our method on three noise settings: 1) feature noise, 2) structural noise, and 3) label noise. We followed the noise setting used Fang et al. (2023); the feature noise is provided by adding standard Gaussian noise to input features with a probability of noise level; the structural noise is given by randomly adding and removing edges with a probability of noise level; for label noise, we randomly permuted training labels with probability of noise level for this experiment. We used GCN as the backbone model for all settings and assessed the robustness of Cora, CiteSeer, and PubMed. The results are summarized below.
We evaluated the robustness when the feature noise is introduced in the graph. The feature noise is provided by adding standard Gaussian noise to input features with a probability of noise level. Table 5 shows how robust our method is for the feature noise. We indicated that our method outperforms the standard training in noise levels.
Feature Noise
We assessed the robustness when the graph contains structural noise. The structural noise is given by randomly adding and removing edges with a probability of noise level. Table shows the results of how the proposed method is robust the structural noise. We found that when structural noise is introduced, GCN trained with iGraphMix outperforms GCN trained without iGraphMix (None). In addition, as the noise level increases from 10% 40%, our method achieves more performance improvement compared to the standard training (None).
Structural Noise
Label Noise We assessed the robustness when the graph contains label noise. We randomly permuted training labels with probability of noise level for this experiment. We trained GCN with the noisy training labels and evaluated GCN's performance. 7 shows how robust our method for noise labels is. We indicated that our method outperforms the standard training in all noise levels.
D.5 COMPUTATIONAL COMPLEXITY
We assessed the computational complexity of our method by Big O complexity analysis. Then, verified the computational complexity from the experiments on Cora and ogbn-arxiv.
Table 8 shows the time complexity with the Big O notation of all methods including five baselines and the proposed method. Specifically, let V be the number of nodes, E be the number of total edges, Err be the number of edges connected to training nodes, d be the hidden dimension of the GNN layer, and be the number of layers. Then, we split the complexity into two parts, i.c., augmented data preparation and graph convolution, and get the Big O complexity of the parts as follows. The time
28

---

Published as a conference paper at ICLR 2024
Table 8: Big O complexity for all data augmentation methods in GCN. We split the data augmentation process into 1) augmented data preparation and 2) graph convolution.
Dropkdge
DropNode
DropMessuge
M-Msupp + 2IV
Kirsphiix
1) Data Prepuration
o TPD
(
о T IVD
2) Graphh Convolatonn
(181ak)
(pletak)
(plEaak)
(1ela))
(218114)
(1E12*)
Table 9: Time complexity of all data augmentation methods in GCN on benchmark datasets.
Operatzen
Dropldge
DrepNode
DropMessage 0.8ee33
M-Mixup
1Grphhii
Cora
11 Dam Preparation
6.88-3
L.13-3
1.35633
19te:3
3.726-3
2) Graph Convolation
L1262
110e-2
1.0022
1i1e2
1.33e2
1.57e2
ogon-aran
Prepuration
13663
125e-3
Graph Convolation
3.32-2
1.7622
188e2
3.30-2
8.33-3
3.376-2
complexity of GCN (None) was represented in Veličković et al. (2018). Since there are dropping edges or nodes in Ddop and DropNode, the complexity for data preparation of DropEdge and DropNode is O (IEl) and O (|E) + [V]), respectively. Also, the complexity of graph convolution is O (p|ε) dd)) where E [o, 1] is dropping probability. DropMessage considers all edges and nodes all layers, their complexity the same as the standard GCN. For M-Mixup, the complexities for data preparation and graph convolution are O ((E) + 2 and O (2|E d respectively. Lastly, in the case of iGraphMix, the complexities for data preparation is O ((E) + [V]) and that for graph convolution O (E]dd)).
Table 9howws the computational time of data preparation and graph convolution Cora and ogbn- arxiv datasets. The below table shows the mean computational time (second) per epoch. We could find that the real computational time is consistent with Big O complexity calculation.
From the analysis, we found that our method would not need lots of computational complexity, especially compared to M-Mixup. Although some methods require less computational time, method leads to better performance when training GNNs, highlighting the necessity of the proposed method.
E EXPERIMENTS ON OTHER TASKS
In this section, we provided the details and results of other graph tasks, such as inductive node classification, and link prediction.
E. INDUCTIVE NODE CLASSIFICATION
PROBLEM DEFINITION
The inductive setting states that train the model only using the sub-graph with training nodes and edges between them and evaluate the model using the sub-graph with evaluation nodes and edges between them. Since the inductive setting is considered handle large-scale graphs in general, meth- ods for this setting are mainly focused on sub-graph sampling. For instance, GraphSAGE (Hamilton al. 2017) randomly samples neighboring nodes for each node. GraphSAINT (Zeng al. 2020) splits the original graphs into several sub-graphs, and randomly samples sub- -abb-graps from the original graphs. Other works proposed various sub-gras sub-graph sampling methods (Chen et al. 2018b
Chiang
et al. 2019)
DATASETS
We used Reddit and
for the inductive node classification. The detailed statistics for each dataset are summarized IO
Reddit We considered one social network dataset: Reddit (Grover & Leskovec, 2016 The goal of this dataset is to predict the category and the community of each post. The nodes for Reddit are the text posts. The edges are connected if the same users interact with both posts. Node features GloVE CommonCrawl word vectors (Pennington et al. 2014) of the post for Reddit. The training and evaluation nodes split by creating dates of post (Hamilton et al. 2017). To make the inductive
29

---

Published as a conference paper at ICLR 2024
setting semi-supervised, we sampled 10% nodes from the original training node set (Hamilton et al. Zeng et al. 2020).
2017
Open Graph Benchmarks (OGB) We also considered e-commerce network dataset: ogbn- products (Hu et al., 2020). The goal of this dataset is to predict the category of the products. The nodes for oghn-products
the products' descriptions. The edges are connected if two products purchased at the same time. Node features are constructed via bag-of-words and applied Principal Component Analysis reduce the dimensions of node features. The training and evaluation nodes are split by sales ranking. To make ogbn-products semi-supervised, we sampled 10% nodes from the original training node-set.
Table 10: Datasets statistics for the inductive setting
Dataset
Reddit
ogbn-products
Nodes
232,965
2,449,029
# Edges
14,,615,92
61,859,140
Features
602
100
# Class
41
47
# Valid Nodes
23,699
244,903
# Test Nodes
55,334
244.903
BACKBONE MODELS
Since one of our goals is to show the effect of iGraphMix in the various sampling methods in the inductive setting, we considered two well-known subgraph sampling methods. We utilized Random Walk sampling used in GraphSAGE (Hamilton et al. 2017) and Sub-graph sampling used in GraphSAINT (Zeng et al. 2020). For the base model architecture, we used GraphSAGE (Hamilton) et al. 2017) layers for GraphSAGE and GCN with JK-Nets (Xu al. 2018 for GraphSAINT. For both models, we used Adam Optimizer with 0.001 learning rate and 2e-4 weight decaying for Reddit. We used dropout with 0.2 probability. We also utilized 128 hidden units (Zeng et al. 2020). The maximum epochs are 200 for GraphSAGE and 50 for GraphS Similar to the transductive setting, we reported the test
when the validation score is the maximum. The other detailed parameters for sampling are followed by GraphSAGE (Hamilton et al. 2017) and GraphSAINT (Zeng
al. 2020
RESULTS
Although we do not provide the theoretical results on the inductive setting, we experimentally showed that iGraphMix helps model training even in this setting. The results for the inductive setting were represented in Table []] We could find that training GNNs with iGraphMix tends to outperform that without augmentation methods on various datasets and backbone architectures. Furthermore, we could observe that iGraphMix shows performance improvement comparable to other augmentation methods. These results verified that the proposed method could improve the performance not only in the transductive small graphs but also in the large inductive graphs.
E.2 LINK PREDICTION
PROBLEM DEFINITION
Link prediction is a task in graph analysis that predicts whether two nodes are connected or not. For mathematical notation, we denote the output of GNNs Z Raxa follows. Z
sigmoid [HK H where H Boxxx is the hidden representation matrix of GNNs with feature dimension dg.
As represented in Verma al. 20 link prediction can be represented form of two-class node classification. Specifically, when a new graph g' is generated by combining the input features and the edges of two pairs of nodes from the original graph G, the goal of link prediction becomes predicting the class of nodes in g'. These classes indicate whether the two pairs of nodes are connected or not in G. This process treats the link prediction in G the node classification in G'.
30

---

Published as a conference paper at ICLR 2024
Table 11:
Overall Micro-FI score (%) on inductive datasets when the number of layers is two. The results are the average scores and standard deviations with different random seeds. Since M-Mixup showed out-of me-oory for GraphSAGE and ggondproddcts, we represent the result as 0OM.
Datasets
Backbone
Data Augmentation
Reddit
ogbn-products
None
94.87 (0.03)
74.41 (0.61)
DropEdge
94.91 (0,05)
75.21 (0.17)
DropNode
95.31 (0.03)
74.98 (0.19)
GraphSAGE
DropMessage
94,86 (0.04)
74.70 (0.26)
M-Mixup
0OM
OOM
iGraphMix (ours)
95.33 (0.04)
75.04 (0.14)
None
89.13 (0.25)
50.41 (0.35)
DropEdge
89.30 (0.29)
56.02 (0.09)
DropNode
89.26 (0.24)
52.53 (0.18)
GraphSAINT
DropMessage
89.18 (0.27)
50.22 (0.48)
M-Mixup
89,91 (0.32)
OOM
iGraphMix (ours)
89.84 (0.33)
$3.49 (0.23)
DATASETS
We used CiteSeer, CORA, and PubMed for the link prediction task.
Planetoid Benchmark We considered the three benchmark citation network datasets for the link prediction task: CiteSeer, CORA, and PubMed. The goal of the link prediction of these datasets is to predict the existence of citation links between every two papers. The detailed statistics of the number of nodes and edges these datasets were summarized T Followed by [ey Lenssen (2019), sampled 5% and 10% edges from the original edges for valid and test edges respectively, and the remaining edges were used for training.
IGRAPHMIX FOR LINK PREDICTION
For link prediction, iGraphMix generates virtual graphs and labels in a batch-wise manner as in Definition E.I The difference between iGraphMix on node classification and link prediction the second equation of Eq. (28). While iGraphMix linearly interpolates two one-hot label matrices on node classification, the proposed method on link prediction generates a virtual label matrix for edges by masking the label matrices and aggregating them. Specifically, our method first masks the label matrices for edges using the masking matrices that are same the equation Eq. (28). Then, the proposed method adds the two masked label matrices to generate the virtual label matrix used for training.
Definition E.1 (iGraphMix for link prediction). Let M, be the masking matrix with À dropping probability. iGraphMix mixes feature matrix, label matrix, and adjacency matrix as follows:
X AX + A) X', P - A M, AY"
(28)
Å = MM A + MA A',
where (X', ,A'' is the permuted batch within labeled nodes of (X, AY A).
RESULTS
We experimentally assessed that iGraphMix helps GNNs improve performance on link prediction. We conducted the link prediction task on CiteSeer, Cora, and PubMed datasets and evaluated the performance of iGraphMix with other augmentation methods in terms of ROC-AUC. For the base model architecture, used two-layer GCN with 128 hidden units. Then, we used Adam Optimizer with 0.01 learning rate for all datasets, and the maximum epochs were 100. The results of GCN on link prediction were presented in Table 12 Similar to the other tasks, reported the test ROC-AUC when the ROC-AUC of the validation sets is the maximum. We found that the proposed method significantly outperforms baseline methods
datasets out of three. Although our method showed
31

---

Published as a conference paper at ICLR 2024
Table 12: Overall results link prediction task.
Link Prediction
Data
Backbone
CiteSeer (ROC-AUC)
Cora
PubMed
Augmentation
(ROC-AUC)
(ROC-AUC)
None
93.22 (0.33)
90.08 (0.54)
97.36 (0.06)
DropEdge
94.49 (0.31)
91.94 (0.84)
97.55 (0.09)
DropNode
93.30 (0.40)
89.43 (0.63)
97.33 (0.06)
GCN
DropMessage
94.03 (0.29)
90.58 (0.64)
97.75 (0.04)
M-Mixup
93.47 (0.34)
90.09 (0.92)
96.22 (0. 15)
iGraphMix (ours)
94.88 (0.40)
93.59 (0.45)
97.62 (0.05)
the second-best performance on PubMed, the average performance ranking of our method was 1.33, supporting the effectiveness of our method these datasets. This result may suggest that iGraphMix is effective in improving performance not only on the node classification but also on link prediction, showing the advantages of method to be proved in various graph tasks.
FURTHER DISCUSSIONS
Despite the effectiveness of work, iGraphMix may have limitations. First, the proposed method may not be as effective for certain types of graphs where the underlying assumption of our method may hold. This limitation suggests designing an advanced and adaptive edge sampling method for tailoring to each graph. Addressing it is a promising direction for future research, which could further optimize the applicability of iGraphMix across various graphs. Second, our theoretical analysis primarily focused on the two-layer GCN may not fully capture more complex and real- world scenarios. We believe that future works on extending multi-layer GCN could handle this limitation.
32


Reviews:
[{"review_id": "yUlo5zlrRf", "reviewer": "Reviewer_A2TK", "summary": "This paper proposed iGraphMix that addresses the irregularity and alignment issues of Input Mixup on node classification. Specifically, to address the two issues, iGraphMix does not only interpolate node features and labels but also aggregates the sampled neighboring nodes. Theoretical analysis of the generalization gap and related experiments on the real-world graphs showed that the proposed method is effective in regularizing GNNs by generating diverse virtual samples and preserving high usability and versatility.", "questions": "From the perspective of time complexity, how does the time cost of iGraphMix compare with other augmentation methods? Can you add a diagram to show it?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is well organized and theoretical.\n2. The proposed method iGraphMix is simple but effective.", "weaknesses": "1. In Section 5 THEORETICAL ANALYSIS, the author mentioned that “Citeseer dataset contains only 1.71% connected edges of labeled nodes out of all edges”, but the data “1.71%” lacks of related references.\n2. Considering iGraphMix that the essence of iGraphMix is to implement a mixed strategy for features, labels and adjacency matrix respectively, however, the experiment content lacks the ablation experiment for these three components. It would be better to add related ablation experiments to examine the effect of these three components.", "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": "", "extra_scores": {}}, {"review_id": "NiQpREzeYt", "reviewer": "Reviewer_mUwv", "summary": "This paper presents a new method called iGraphMix for node classification in graph neural networks. The method addresses the challenges of irregularity and alignment in generating virtual nodes and edges for GNNs training. iGraphMix generates virtual graphs that serve as inputs for GNNs training, leading to better generalization performance compared to training without augmentation. The authors evaluate iGraphMix on several benchmark datasets and show that it outperforms existing state-of-the-art methods. The contributions of this paper include a novel approach to graph augmentation, a comprehensive evaluation of the proposed method, and insights into the effectiveness of virtual graph generation for GNNs training.", "questions": "How sensitive is the performance of iGraphMix to the choice of hyperparameters, such as the number of virtual nodes or the strength of the mixing coefficient? Can the authors provide a detailed analysis of the impact of hyperparameters on the performance of iGraphMix?\n\nCan the authors provide an ablation study to analyze the contribution of each component of iGraphMix? This would help to better understand the importance of each component and how the performance of iGraphMix varies when different components are removed or modified.\n\nWhat are the limitations of iGraphMix? Can the authors provide a detailed discussion of the scenarios where iGraphMix may not be effective or where other methods may be more appropriate?\n\nCan the authors provide an analysis of the computational complexity of iGraphMix? How does the computational cost of iGraphMix compare to other graph augmentation methods, and how does it scale with the size of the graph?\n\nHow does iGraphMix perform on larger and more complex graphs? Can the authors provide an analysis of the scalability of iGraphMix to larger graphs with more nodes and edges?\n\nCan the authors provide a discussion of the potential applications of iGraphMix beyond node classification, such as link prediction or graph classification?\n\nHow does iGraphMix perform on graphs with different characteristics, such as sparsity or degree distribution? Can the authors provide an analysis of the robustness of iGraphMix to different graph properties?\n\nCan the authors provide a discussion of the potential limitations of the theoretical analysis presented in the paper? How well does the theoretical analysis capture the behavior of iGraphMix in practice?\n\nCan the authors provide a discussion of the potential ethical implications of using graph augmentation methods like iGraphMix? How can we ensure that these methods are used responsibly and do not perpetuate biases or inequalities in the data?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a novel method, iGraphMix, for addressing the challenges of irregularity and alignment in generating virtual nodes and edges for graph neural networks. The method is well-motivated and builds on existing work in Input Mixup for other domains. The authors provide a clear and comprehensive description of the method, including theoretical analysis and experimental validation of its effectiveness. The evaluation is thorough and includes comparisons to existing state-of-the-art methods on several benchmark datasets. The results show that iGraphMix outperforms existing methods in terms of micro-F1 score, demonstrating the significance of the proposed approach. \n\nOverall, the paper is well-written and easy to follow, with clear explanations of the technical details and experimental setup. The authors provide a detailed discussion of related work and highlight the contributions of their method. The theoretical analysis is insightful and provides a deeper understanding of the effectiveness of iGraphMix. The experimental results are convincing and demonstrate the superiority of iGraphMix over existing methods. \n\nIn terms of originality, iGraphMix is a novel approach to graph augmentation that addresses the challenges of irregularity and alignment in generating virtual nodes and edges for GNNs training. The method builds on existing work in Input Mixup for other domains but is specifically designed for node classification in the graph domain. The authors provide a clear motivation for the method and demonstrate its effectiveness through theoretical analysis and experimental validation. \n\nIn terms of quality, the paper is well-written and well-organized, with clear explanations of the technical details and experimental setup. The authors provide a thorough evaluation of the proposed method, including comparisons to existing state-of-the-art methods on several benchmark datasets. The results are convincing and demonstrate the superiority of iGraphMix over existing methods. \n\nIn terms of clarity, the paper is easy to follow, with clear explanations of the technical details and experimental setup. The authors provide a detailed discussion of related work and highlight the contributions of their method. The theoretical analysis is insightful and provides a deeper understanding of the effectiveness of iGraphMix. \n\nIn terms of significance, the paper presents a novel approach to graph augmentation that addresses the challenges of irregularity and alignment in generating virtual nodes and edges for GNNs training. The method is well-motivated and builds on existing work in Input Mixup for other domains. The authors provide a clear motivation for the method and demonstrate its effectiveness through theoretical analysis and experimental validation. The results show that iGraphMix outperforms existing methods in terms of micro-F1 score, demonstrating the significance of the proposed approach.", "weaknesses": "Overall, the paper is well-written and presents a novel approach to graph augmentation for node classification in GNNs. However, there are a few weaknesses that could be addressed to improve the paper:\n\n1. Limited analysis of the impact of hyperparameters: The authors do not provide a detailed analysis of the impact of hyperparameters on the performance of iGraphMix. It would be useful to see how the performance of iGraphMix varies with different hyperparameters, such as the number of virtual nodes or the strength of the mixing coefficient.\n\n2. Lack of ablation study: The authors do not provide an ablation study to analyze the contribution of each component of iGraphMix. It would be useful to see how the performance of iGraphMix varies when different components are removed or modified.\n\n3. Limited discussion of limitations: The authors do not provide a detailed discussion of the limitations of iGraphMix. It would be useful to see a discussion of the scenarios where iGraphMix may not be effective or where other methods may be more appropriate.\n\n4. Lack of analysis of computational complexity: The authors do not provide an analysis of the computational complexity of iGraphMix. It would be useful to see how the computational cost of iGraphMix compares to other graph augmentation methods and how it scales with the size of the graph.\n\nAddressing these weaknesses would strengthen the paper and provide a more comprehensive evaluation of the proposed method.", "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": "", "extra_scores": {}}, {"review_id": "m24IRIVWGN", "reviewer": "Reviewer_jPtV", "summary": "This paper proposes a node-level graph mixup method named iGraphMix to improve the model generation ability. To handle the irregularity and alignment issue for graph mixup, this paper proposes to generate virtual nodes and edges by interpolating features and labels, and attaching sampled neighborhoods. Theoretical analysis shows that iGraphMixup can be regarded as a regularization on the weight space to help improve the generalization. Experiments on real world datasets validate the effectiveness of the proposed method on node classification.", "questions": "-\tHow will the proposed method enhance the model robustness? Robustness w.r.t label/feature/structure noises is usually evaluated for mixup methods [1,2], and it is highly recommended to include these experiments in the paper.\n-\tMore baselines are needed. Currently, only M-mixup is a graph mixup for node classification, while other augmentation methods (e.g., [4]) are not included.\n-\tEq.(4): How can A,X and its permuted counterpart A’,X’ be directly added as they are not well-aligned? Is the masking matrix M a symmetric matrix?\n-\tWritting:\n  - Eq.(6), notations $\\tilde{Z}_{v,v’}$, $\\tilde{Y}_{v,v’}$ is quite misleading, as subscripts are used to denote columns and rows in the paper.\n  - Line below eq.(1): matrix->matrices.\n\nReference\n\n[1] Han, Xiaotian, et al. \"G-mixup: Graph data augmentation for graph classification.\" International Conference on Machine Learning. PMLR, 2022.\n\n[2] Ling, Hongyi, et al. \"Graph Mixup with Soft Alignments.\" arXiv preprint arXiv:2306.06788 (2023).\n\n[3] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. Advances in Neural Information Processing Systems, 34:27043–27056, 2021.\n\n[4] Verma, Vikas, et al. \"Graphmix: Improved training of gnns for semi-supervised learning.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 35. No. 11. 2021.\n\n[5] Wu, Lirong, et al. \"Graphmixup: Improving class-imbalanced node classification by reinforcement mixup and self-supervised context prediction.\" Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Cham: Springer Nature Switzerland, 2022.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "-\tA novel method is proposed to mixup graphs at the input level.\n-\tTheoretical analysis is provided to understand the effect of improving the model generalization.\n-\tExtensive experiments are provided to evaluate the method empirically.", "weaknesses": "-\tBaseline methods are quite limited and evaluation on robustness is highly recommended. See details in the question part.\n-\tPresentation could be further improved.", "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": "", "extra_scores": {}}, {"review_id": "E7fqY8PyDy", "reviewer": "Reviewer_TxAH", "summary": "The authors propose a new input mixup method for node classification problems. The proposed method, known as iGraphMix, generates virtual nodes by interpolating input features. The edges of these virtual nodes are generated by sampling neighboring nodes. The authors provide theoretical analysis to show that iGraphMix leads to better generalization performance compared to that without augmentation.", "questions": "Q1. I don't understand why iGraphMix is versatile with other augmentation methods. Can authors provide more explanations? \n\nQ2. Why do authors only use the Micro-F1 score as the only metric? Accuracy is a more common choice. \n\nQ3. Does iGraphMix train GNNs using all virtual nodes, like how it is done in Mixup? In other words, no original nodes are used during training.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "S1. The proposed method is easy to understand. \n\nS2. The authors conduct extensive experiments to show that their proposed method outperforms multiple baselines. \n\nS3. The authors provide a theoretical analysis of the generalization gap.", "weaknesses": "W1. The improvement of iGraphMix is marginal. Overall, the improvement beyond the second-best method is always less than 1%. I suggest the authors conduct experiments on more challenging datasets to make the result more convincing. \n\nW2. How do the authors compute the generalization gap in Sec. 6.2? Why the test loss of iGraphMix is much higher than the \"no augmentation\"?\n\nW3. In Appendix B, how can this $AX=AX'=A\\tilde{X}$ holds? It would be much better if the authors could provide a rough proof idea before presenting all the details. \n\nW4. The baselines compared are all very simple methods. There are more advanced graph data augmentation methods to compare with, such as [1].\n\nW5. There are many existing graph mixup methods for graph classification tasks. It would be nice to add a discussion to better place this work in the literature.\n\n[1] Kong, Kezhi, et al. \"Robust optimization as data augmentation for large-scale graphs.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.", "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": "", "extra_scores": {}}, {"review_id": "RNpMBUlCni", "reviewer": "Reviewer_vL8H", "summary": "The paper proposes iGraphMix, a novel Mixup method tailored for node classification in graph neural networks (GNNs), which generates virtual nodes and edges by interpolating input features, labels, and neighboring nodes. iGraphMix addresses the irregularity and alignment issues associated with applying Input Mixup to node classification, and the paper provides theoretical proof and experimental results demonstrating its effectiveness in improving GNN performance and reducing overfitting.", "questions": "* The paper mentions that iGraphMix can be combined with other augmentation methods. Can you provide examples or insights into how this combination can be done and what benefits it can bring to GNN performance?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides theoretical proof and experimental validation of the effectiveness of iGraphMix in reducing the generalization gap and improving GNN performance", "weaknesses": "* The experimental validation of iGraphMix is mentioned, but it would be helpful to have more details on the datasets used, the specific GNN models employed, and the performance metrics used for evaluation.\n\n* It would be beneficial to have experimental analysis about the computational cost and speed of the proposed method compared with the state-of-the-art approaches.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)