On the Equivalence of Graph Convolution and Mixup
Authors: Xiaotian Han
Hanqing Zeng
Yu Chen
Shaoliang Nie
Jingzhou Liu
Kanika Narang
Zahra Shakeri
Karthik Abinav Sankararaman
Song Jiang
Madian Khabsa
Qifan Wang
Xia Hu
Venue: Accepted by TMLR ()

Abstract: This paper investigates the relationship between graph convolution and Mixup techniques. Graph convolution in a graph neural network involves aggregating features from neighboring samples to learn representative features for a specific node or sample. On the other hand, Mixup is a data augmentation technique that generates new examples by averaging features and one-hot labels from multiple samples. One commonality between these techniques is their utilization of information from multiple samples to derive feature representation. This study aims to explore whether a connection exists between the two. Our investigation reveals that, under two mild modifications, graph convolution can be viewed as a specialized form of Mixup that is applied during both the training and testing phases. The two modifications are 1) \textit{Homophily Relabel} - assigning the target node's label to all its neighbors, and 2) \textit{Test-Time Mixup} - Mixup the feature during the test time. We establish this equivalence mathematically by demonstrating that graph convolution networks and simplified graph convolution can be expressed as a form of Mixup. We also empirically verify the equivalence by training an MLP using the two modifications to achieve comparable performance.

Published in Transactions on Machine Learning Research (09/2024)
On the Equivalence of Graph Convolution and Mixup
Xiaotian Han' Hanqing Zeng² Yu Chen Shaoliang Nie² Jingzhou Liu? Kanika Narang
Zahra Shakeri? Karthik Abinav Sankararaman Song Jiang' Madian Khabsa² Qifan Wang Xia Hu
Case Western Reserve University Mela AI 3 Anglime AI UCLA Ricee University
Reviewed on OpenReview: https: // openreview. net/ porun id- koC62yaf73
Abstract
This paper investigates the relationship between graph convolution and Mixup techniques. Graph convolution in graph neural network involves aggregating features from neighboring samples to learn representative features for a specific node or sample. On the other hand, Mixup data augmentation technique that generates new examples by averaging features and one-hot labels from multiple samples. One commonality between these techniques is their utilization of information from multiple samples derive feature representation. This study aims to explore whether connection exists between the two. Our investigation reveals that, under two mild modifications, graph convolution can be viewed as a specialized form of Mixup that is applied during both the training and testing phases. The two modifications are 1) Homophily Relabel - assigning the target node's label to all its neighbors, and 2) Test-Time Mixup Mixup the feature during the test time. We establish this equivalence mathematically by demonstrating that graph convolution networks and simplified graph convolution can be expressed as form of Mixup. We also empirically verify the equivalence by training MLP using the two modifications to achieve comparable performance.
1 Introduction
Graph Neural Networks (GNNs) (Wu et al., 2020; Zhou et al., 2020) have recently been recognized as the de facto stato-of-the-art algorithm for graph learning. The core idea behind GNNs is neighbor aggregation, which involves combining the features of a node's neighbors. Specifically, for a target node with feature X one-hot label yı, and neighbor set Ni, the graph convolution operation in GCN is essentially as follows:
9)
Xk. y1
[
KEN.
In parallel, Mixup (Zhang et al., 2018) is proposed to train deep neural networks effectively, which also essentially generates a new sample by averaging the features and labels of multiple samples:
N
N
()
X
Σ AAY
s.t.
Σ
1=1,
1=1
where x:/y; are the feature/label of sample i. Mixup typically takes two data samples (N = 2).
Equation (1) and Equation (2) highlight a remarkable similarity between graph convolution and Mixup, i.e., the manipulation of data samples through averaging the features. This similarity prompts us to investigate the relationship between these two techniques as follows:
Is there a connection between graph convolution and Mixup?
*Corresponds xhan@rase.edu. The cade http:://gisaabb.cc//aatt//rggggp Mixup.

---

Published in Transactions on Machine Learning Research (09/2024)
(a) Three-sample Mixup
GEN (Cora)
Feature
Label
9039
yo
Xo
Yo
X1
Y1
Assuraet Sstura
880
X2
Y2
700%
GCN
(b) Graph convolution (target node is
60%
Miop
X
10% 30%
Training Data Ratio
50%
70% 90%
X1
Yo
X2
GCN ICiteSeer)
You
Graph Convolution
Assign NoUL to all neighbors
75%
Equal
(Homophily Relabel)
F00
MLP
You
yo
Mixup
Xn Yo
Moxp
60%
X1 Yo
Yo
x
10% 30%
50% 70% 90%
X2
Training
Yo A
(d) GCN Mixup
(c) Mixup with Homophily Relabel
Figure Graph convolution is Mixup. (a) illustrates the basic idea of Mixup: averaging the features and
one-hot labels of multiple samples the target node is the weighted average of the features of all its neighbors. (b) (c) shows that graph
(b) shows the graph convolution operation where the feature of
convolution is Mixup if we assign the label (O00) of the target node to all of its neighbors
(d)
shows that Mixup is empirically equivalent to GCN.
In this paper, we answer this question by establishing the connection between graph convolutions and Mixup, and further understanding the graph neural networks through the lens of Mixup. We show that graph convolutions are intrinsically equivalent to Mixup by rewriting Equation (1) as follows:
(x,
Σ Yi.y REN.
(
XR.
EM
Σ
A== Mill
A
Σ Aay
N
N
REN, M
KEA,
KEN;
kEN;
where x; and y; are the feature and label of the target node n,, This equation states that graph convolution is equivalent to Mixup we assign the y; to all the neighbors of node n, set N;
To demonstrate the equivalence between graph convolutions and Mixup, begin by illustrating that one-layer graph convolutional network (GCN) (Kipf & Welling, 2016b) can be transformed into input Mixup. A two-layer GCN can be expressed as hybrid of imput and manifold Mixup (Verma et al., 2019). Similarly, simplifing graph convolution (SGC) (Wu et al., 2019) can be reformulated as an input Mixup. We thus establish the mathematical equivalence between graph convolutions and Mixup, under two mild and reasonable modifications: 1) assign the target node's label to neighbors the training time (referred as Homophily Relabel); 2) perform feature mixup in the test time (referred as Test- Time Micup).
We further investigate the modifications required for the equivalence between graph convolution and Mixup, focusing on the effect of Homophily Relabel and Test- Time Mizup. To explore Homophily Relabel, we demonstrate that training an MLP with Homophily Relabel (called HMLP) is equivalent to training GCN in terms of prediction accuracy. This finding provides a novel perspective for understanding the relationship between graph convolution and Mixup and suggests a new direction for designing efficient GNNs. To investigate Test-Time Mixup, we train GNNs without connection information, perform neighbor aggregation during inference, and find that this approach can achieve performance comparable to traditional GNNs. This result reveals that Time Mixup can be powerful alternative to traditional GNNs in some scenarios, and suggests that Mixup may have a broader range of applications beyond traditional data augmentation. Our investigation on Homophily Relabeling and Test-Time Mirup provides valuable insights into the theoretical properties of GNNs and their potential applications in practice. We highlight our contributions as follows:
We establish for the first time connection between graph convolution and Mixup, showing that graph convolutions are mathenatically and empirically equivalent to Mixup. This simple yet novel finding potentially opens the door toward deeper understanding of GNNs.
2

---

Published in Transactions on Machine Learning Research (09/2024)
Given that both graph convolution and Mixup perform a weighted average the features of samples, we reveal that graph convolution is conditionally equivalent to Mixup by assigning the label of a target node to all its neighbors during training time (Homophily Relabel). Also, we also reveal that in the test time, graph convolution is also Mixup (Test- Mirup).
Based on Homophily Relabel and Test- Dist-Time Mizup, we propose two variants of ML.S based on the Mixup strategy, namely HMLP and TMLP, that can match the performance of GNNs.
Related Work. Graph neural networks are widely adopted in various graph applications, including social network analysis (Fan et al., 2019), recommendation (Wei et al., 2022; Deng et al., 2022; Cai et al., 2023; Tang et al., 2022), knowledge graph (Cao et al., 2023; Zhao et al., 2023), molecular analysis (Sun et al., 2022; Zhu et al., 2023a; ZHANG et al., 2023; Wang et al., 2023b; Corso et al., 2023; Liao & Smidt, 2023; Xia el al., 2023; Hladiš et al., 2023), drug discovery (Sun et al., 2022: Zhang et al., 2023c), link prediction (Chamberlain et al., 2023; Cong et al., 2023) and others (Chen et al., 2023a). Understanding the generalization and working mechanism of graph neural networks is still in its infaney (Garg et al., 2020; Zhang et al., 2023a; Yang et al., 2023; Baranwal et al,, 2023). The previous work attempts to understand graph neural networks from different perspectives, such as signal processing (Nt & Maehara, 2019; Bo et al., 2021; Bianchi et al., 2021), gradient flow (Di Giovanni et al., 2022), dynamic Doogramming(Dudiae kernels (Yang et al., 2023; Du et al., 2019; Sabanayagam et al., 2022) and influence function (Chen et al., 2023b). There is also a line of works that analyzes the connection between GNNs and MLPs (Baranwal et al., 2023; Han et al., 2022b; Yang et al., 2023; Tian et al., 2023), which is similar to the proposed method in Section 3. In this work, we understand graph neural networks through a fresh perspective, Mixup. We believe that this work will inspire further research and lead to the development of new techniques to improve the performance and interpretability of GNNs. In parallel, Mixup (Zhang et al., 2018) and its variants (Verma et al., 2019; Yun et al., 2019; Kim et al., 2020; 2021) have emerged as popular data augmentation technique that improves the generalization performance of deep neural networks. More specifically, deep neural networks trained with Mixup achieve better generalization (Chun et al., 2020; Zhang et al., 2020; Chidambaram et al., 2022), calibration (Thulasidasan et al., 2019; Zhang el al., 2022a), adversarial robustness (Pang et al., 2019; Archambault et al., 2019; Zhang et al., 2020; Lamb et al., 2019), and explain ensemble (Lopez-Paz al., 2023). More related work in Appendix A.
& Veličković, 2022), neural tangent
The Scope of Our Work. 1 This work not only provides a fresh perspective for comprehending Graph Convolution through Mixup, but also makes valuable contributions to the practical and theoretical aspects of graph neural networks, facilitating efficient training and inference for GNNs when dealing with large-scale graph data. Practical Potentials: Both HMLP and TMLP hold potential value for practical usage. TMLP is training-efffcient, as its backbone and training process are both MI.P-based; however, the inference requires Test-Time Mizup (neighbor aggregation), which can be time-consuming. This limitation also exists in previous works (Han et al., 2022b; Yang et al., 2023). HMLP, on the other hand, is both training and test efficient, both processes are based on MLP. This suggests the potential of HMLP for practical usage large-scale graphs. Theorctical Potentials: HMLP, derived from the Mixup, have the theoretical potential to understand the expressiveness of GNNs from the Mixup perspective. With the connection between Mixup and graph convolution, HMLP goes beyond traditional methods to understand the learning capability of GNNs.
2 Graph Convolution is Mixup
In this section, we reveal that the graph convolution is essentially equivalent to Mixup. We first present the notation used in this paper. Then we present the original graph convolution network (GCN) (Kingma & Ba, 2015) and simplifying graph convolutional networks (SGC) (Wu et al., 2019) can be expressed mathematically as form of Mixup. Last, we present the main claim, ie., graph convolution can be viewed as special form of Mixup under mild and reasonable modifications.
Notations. We denote a graph as G(V,E), where V is the node set and E is the edge set. The number of nodes is N = |V| and the number of edges is M = -E). We denote the node feature matrix as X = (x), X2, ... xN) Nxd where x; is the node feature for node n, and d is the dimension of features. We
Note that our work only focuses the node-wise predictions made by GCNs.
3

---

Published in Transactions on Machine Learning Research (09/2024)
denote the binary adjacency matrix A (0,1).xx,, where As = 1 if there is an edge between node na and node nj in edge set E, and Ai = 0 otherwise. We denote the neighbor set of node as Mi, and its 2-hop neighbor set as N? For the node classification task, we denote the prediction targets of nodes as onc-hot labels Y {0, (OCC-), where C is the number of classes. For graph convolution network, we use A A as the normalized adjacency matrix?, where D E RNN diagonal degree matrix, and D is the degree of node ng- We use à E RIIN, i-th row of A, as the normalized adjacency vector of node n,.
2.1 Preliminaries
Graph Convolution. Graph Convolution Network (GCN) (Kipf & Welling, 2016a), as the pioneering work of GNNs, proposes Y softmax(A ( o - X W1) W2), where W₁ and W₂ are the trainable weights of the layer one and two, respectively. Simplifying Graph Convolutional Networks (SGC) (Wu et al., 2019) is proposed as Y = softmax(A A X .W). In this work, we take these two widely used GNNs to show that graph convolution is essentially Mixup.
Mixup. The Mixup technique, introduced by Zhang et al. (2018), is a simple yet. effective data augmentation method to improve the gencralization of deep learning models. The basic idea behind Mixup is to blend the features and one-hot labels of a random pair of samples to generate synthetic samples. The mathematical expression of the two-sample Mixup is as follows:
(x,y) = (Ax; + (1 - X)x,, Xy, + (1 A)y,) (Aix, + X2X,, A1y + )2y;),
(3)
where + > Based on the two-sample Mixup, the multiple-sample Mixup is presented in Equation (2). The mathematical expression presented above demonstrates that Mixup computes a weighted average of the features from multiple original samples to generate synthetic samples.
2.2 Connecting Graph Convolution and Mixup
We demonstrate that graph convolution, using GCN and SGC as examples, conditionally Mixup. To do this, we mathematically reformulate the expressions of GCN and SGC a Mixup form, thereby illustrating that graph convolutions indeed Mixup.
One-layer GCN is Mixup We begin analysis by examining simple graph convolution neural network (Kipf & Welling, 2016a) with one layer, referred to as the one-layer GCN. We demonstrate that the one-layer GCN can be mathematically understood as an implementation of the input Mixup technique. The expression of the onc-layer GCN is given by: Ý = softmax(A (A X W) where W E RDC is the trainable weight matrix. Let us focus on a single node n, in the graph. The predicted one-hot label for this node is given by y: = softmax(ā, X W), where å I i-th row of A, is the normalized adjacency vector of node n4- NG is the neighbors set of node n4- We make the following observations:
ā X results in a weighted sum of the features of the neighbors of node ni, which is the multiple-sample Mixup. Explicitly, we can rewrite å X to x = [VT ΣkEN, Xx.
If we assign node n,'s 's label to all its neighbors, the label y; of node n, can be interpreted as a weighted average of the labels of its neighboring nodes, which is equivalent to performing Mixup on the labels.
Thus we have ý y: = M.. EkEN, yk-
From the previous observations, we can see that one-layer GCN synthesizes new Mixup sample for node n, by mixing up its neighbors' features and one-hot labels, which is defined as follows:
Σv²
9x)
Xk:
yk
(4)
W
REN.
KEN.
Therefore, conclude that a one-layer GCN is Mirup machine, which essentially synthesizes new sample by averaging its neighhors' features and one-hot labels.
20ur following analysis can be easily generalized to other normalization methods, such D- ADD
4

---

Published in Transactions on Machine Learning Research (09/2024)
Two-layer GCN is Mixup We extend our analysis to consider two-layer GCN. The expression for two-layer GCN is given by Y = ===soff softmax ( aA X Wi) W2), Let us focus node ni in the graph. For the first layer of the two-layer GCN, we have h, = Relu(ā, X Wi) E 1xd where å E RIXN is the normalized adjacency vector node n4. The first layer the same as the one-layer GCN as discussed above, which can be regarded as a multiple-sample input Mixup.
For the second layer of the two-layer GCN, we have y; Softmax(3, E RIxC, H E RNxd is the hidden representation of all nodes obtained from the first layer, and W2 E R is the weight matrix. The predicted one-hot label for node n,; Yr, is obtained through softmax activation function. The 2-nd layer can be regarded multiple-sample manifold Mixup (Verma et al., 2019) in the following:
à; - H is the multiple-sample Mixup of the hidden represenlation of the neighbors of node ni. We rewrite the å to x = à; H पित EKEN, hy.
Therefore, we conclude that a multi-layer GCN is a hybrid of imput Mirup (first layer) and manifold Mirup (second layer).
SGC is Mixup The 2-layer SGC architecture is represented by the following expression, Ý = softmax (A Á X. W). Similar to one-layer GCN, for the node n, in a 2-layer SGC, we have
y, softmax(a X K), L Cross (anss-nnttrotytyy..
(5)
where a? E RIXN is the adjacency vector within 2-hop neighbors of node n,. The 2-hop neighbor set of node ny is represented by N²², Hereby we have
a? is the multiple Mixup of the features of the neighbors of node n.. We rewrite the äi X to x = ? X= [A7 Σ> N?
From the above, we have a Mixup of samples for node n, is
(x. v)
Σ yk
(6)
[N?1
IN?1
KEN?
REN?
Thus conclude that an SGC is input Mirup machine.
2.3 Graph Convolution is (Conditionally) Mixup
It straightforward to derive the Mixup form of 1-layer, 2-layer GCN, and SGC as discussed above. This leads to the conclusion that 1-layer, 2-layer GCN, and SGC can all be reformulated in the form of Mixup. This establishes mathematical connection between graph neural networks and the Mixup method. Building these findings, in this section, we introduce main contribution follows:
Main Results
Graph convolution is Train- and Test-Time Mixup, under two mild and reasonable modifications: Homophily Relabel and Test-time Mirup.
The two primary differences between GNNs and Mixup are as follows:
Homophily Relabel At training time, if assign the label of the target node to all its neighbors, the Graph Neural Network can be naturally rewritten form of Mixup.
West-Time Micup At test time, the GNNs perform feature mixing on the nodes and then use the mixed feature for the inference.
Both of the above modifications are mild and reasonable and have practical implications for GNN design and analysis. The Homophily Relabel operation can be understood as imposing the same label on the target node and all its neighbors, which corresponds to the homophily assumption for graph neural networks. The homophily assumption posits that nodes with similar features should have the same label, which is common
5

---

Published in Transactions on Machine Learning Research (09/2024)
assumption in many real-world graph applications. On the other hand, Test-time Mirup can be understood Mixup at the test. time by mixing the features from neighbors for prediction. We examine the above differences in depth in Section 3 and Section 4.
2.4 Discussion
Comparison to Other Work. Hereby, we compare our work and previous work. Yang et al. (2023); Han et al. (2022b) propose to train an MLP and transfer the converged weight from MLP to GNN, which can achieve comparable performance to GCN. In this work, these two methods are all included in part of our work, Test-Time Mirup. Different from previous work, we provide a fresh understanding of this phenomena by connecting graph convolution Mixup and also derive TMLP Appendix C.2 to implement Test- Time Merup. Baranwal et al. (2022) understand the effect of graph convolution by providing rigorous theoretical analysis based synthetic graph. Different from this work, work understands graph convolution with well-studied technique, Mixup.
Why MLP is more efficient to GNN: GNN is Y= Table 1:
The running time of one epoch compari- son of original MLP vs. GNN.
softmax(A (À X. W), where A is a large sparse matrix, resulting in significant computation time. This is well studied previous work Zhang et al. (2021): Yang al. (2023). We also conducted experiments to measure the actual runtime of MLP and GNN. The results demonstrate the efficiency of MLP compared to GNN. With mixup, the nunber of data points will double. The rumning time of MLP will at most double, resulting in running time ratio of MLP to GNN = (1.8396 2) 174.1459 = 1: 47.
MLP
GNN
Running time 1. 1.8396+0.0264 174.1459-7.0611
3 Is Homophily Relabel Equivalent to GCNs Training ?
In this section, we conduct experiments to examine the Homophily Relabel proposed in Section 2.3. The empirical evidence substantiates our claims, emphasizing the significant effect of Homophily Relabel on GNNs. This understanding can facilitate the design of an ML.P equivalent that competes with the performance of GNNs. Note that we explore the transductive setting in our experiments.
3.1 Homophily Relabel Yields a SaaiinngEquivalent MLP to GCN
We utilize the simple example graph to demonstrate the calculation of the loss function in a GCN in the transductive setting. The example graph, in Figure 2, comprises three nodes. The blue and red nodes belong to the training set, while the gray node belongs to the test set. In the transductive scenario, the loss function is computed for the entire graph during the training phasc, incorporating both the training and test nodes. In our simple example graph, the loss function will be calculated on the blue and red nodes with their actual labels. Notably, the prediction for the gray node, despite being part of the test set, will also contribute to the overall loss calculation in the transductive setting. For node n,, the prediction (po, P1); the loss of the example graph will be follows
X Yo
X1 [1.0]
yi 10
X;
Figure 2: The example graphs. X; is the target node, The loss of x; that connected two nodes with different labels.
Lg = cross-entropy YY Y) cross-entrooy Yo) + cross-entrooy(yx....)
Yoo log(po) Yo1 log(p)) ) - 3/0 log(po) y11 log(p1)
-1 log(po) - 0 log(p1) - * log(po) 1 log(pp))
= -1 1og(po)-1 log(pı) = - * (0.5 # log(po)+0.. 0.5 log(p1)).
where y00/y01 is the Oth/1s /Ist elements in the one-hot label yo for node no. The above analysis shows that the actual training label for target node n, is (0.5, 0.5). From the Mixup perspective, in an idcally well-trained model utilizing a two-sample Mixup, as shown in previous work (Guo et al., 2019; Pang al., 2019), the following approximation will hold f f(Ax+ (1 -x)))a))) (1 (xx). Intuitively, this approximation
6

---

Published in Transactions on Machine Learning Research (09/2024)
holds because the model is trained with mixup examples (Enewr Vnew) (Az, + (1 A)zz, Ay + + \)8,)- The linear correlation between Inew and Unew leads to a model that can be approximated by a linear function. If we regard the neighbor aggregation as Mixup, we can easily derive that
8o = f Xu + Xi
= (f(xo) + f(xx)) 81
X1 + x,
=
1 (f((x) + + f(x:))
(8)
2
2
see that f(x,) are trained with the labels of all its neighbors xo and X1. Thus in the next, we propose explicitly training the nodes in the test set with the label of their neighbors if they are in the training set. In our example graph, we explicitly train the gray node with label (0.5,
From the above two equations,
HMLP Based on the above analysis, we proposed Homophily Relabel MLP (HMLP), which achieves the comparable performance of GCN via training an MLP as a backbone with Homophily Relabel. In detail, the proposed method HMLP has two major steps: 1) relabel all the nodes in the graph with the mixed label Y A Y. 2) train an MLP on all the nodes with Y on relabeled graph, only using node features. We illustrate our proposed HMLP with the example graph in Figure 2. 1) we relabel all the nodes using Homophily Relabel, the node with new label will be (Xo, (1,0)), (x1, (0, 1)), (x;, (0.5, 0.5)) 2) then train the HMLP with these data samples. The test sample will be (x,, ?) during the test time.
3.2 Can HMLP Achieve Comparable Performance to GCN?
To verify the proposed HMLP can achieve comparable per- formance to the original GCN, we train the one-layer GCN (GCN-1), two-layer GCN (GCN-2), SGC, and HMLP on the training set and report the test accuracy based on the highest accuracy achieved on the validation set. We exper- imented with different data splits of train/validation/ peptatiioo//tstttttt test (the training data ratio span from 10% - 90%), and we also conducted experiments with the public split on Cora, CiteSeer, and PubMed datasets. We present the results in
Table 2: Performance comparison of GCN and HMLP.
Datasets
MLP
GCN
HMLP
Cora
73.57 es
18.04_1.m0 .6
86.4211.7
CiteSeer
71.90 L.
15.69=1.a
75.94
PubMed
86, =6.90=
87.94=0.c4
88, 88.34+0.4
Average 77.45
83.89
83.57
Table 2 and Figure We also present the training and test curves of the MLP. GCN and HMLP in Figure 3.
From the results in Table and Figure 4, HMLP achieves comparable performance to GCN when the ratio of training to test data is large. For the Figure 4, the performance of HMLP is significantly better than MLP, and on par with GCN, especially when the training data ratio is large. The results also show that when the training data ratio is small, HMLP performs worse than GCN. The training and test curves show that HMLP achieve the similar test curves (red and green lines in the right subfigure) even though the training curve are not the same. This may be because the labels of nodes are changed.
Training curve
Test curve
MLP
MLP
GCN
1.5
GCN
LOBs
HMLP
HMLP
1.0
0.5
100
200
300
0
100
200
300
400
Epoch
Epoch
Figure 3: The training and test curves of GCN and HMLP.
4 How Does
Mixup Affect GCN Inference?
In this section, we aim to investigate how Test-time Mirup affects the GCN inference process. We conduct an empirical study to understand the functionality of Test-time Mizup (neighbor aggregation during the test time). To this end, we propose an MLP involving Test-time Micup only (TMLP).
TMLP The proposed method TMLP follows the steps: 1) we train an MLP using only the node features of the training set. 2) we employ the well-trained MLP for inference with neighbor aggregation during testing. This paradigm has also been investigated in previous works (Han et al., 2022b; Yang et al., 2023). We call this method TMLP. We illustrate the TMLP with the example graph in Figure 2. Specifically, train the model
7

---

Published in Transactions on Machine Learning Research (09/2024)
GCN-2 (Cora)
CCN-2 (CiteSeer)
GCN-2 (PubNed)
GCN-2 (Full CoraaL
90%
80%
90%
86%
Accureey
80%
73%
80%
86%
70%
70%
84%
70%
63%
GCN-2
60%
82%
HMLP
60%
60%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
Training Data Ratio
Training Data Ratio
Training Data Ratio
Training Data
Figure 4: The performance comparison of the GCN, MLP and HMLP (Ours). The x-axis represents the ratio of training data, and the y-axis represents the accuracy of classification. The results show that our proposed method (HMLP) achieves comparable performance to GCN. Note that the architecture of our method in train and test time are both MT.P. More experimental results on other datasets and GNNs are presented in Appendix C.I.
using the following training examples, (Xo, (1, 0)), (x1, (0, 1)). Note that the backbone of TMLP is an MLP, In the following, we explore the performance of TMLP.
4.1 How Does TMLP Perform Compared GCN?
In the section, we conducted experiments to verify the effect of Test-Time Mirup. In the experiments, during the training, we only use the node feature lo train an MLP, and then during the test time, we use the well-trained MLP with the neighbor aggregation to perform the inference. We present the results of varying training data ratio in Figure 6, and we also present the accuracy in Table 3 when the training data ratio is 0.6. Additionally, compare the learned representation of GNNs and TMLP using t-SNE Van der Maaten & Hinton (2008). From these results, make the following observations:
From these results, we make the following observations: TMLP almost achieves comparable performance to GNNs. In the Figure 6, the performance of TMLP is signif- icantly better than MLP and on par with GCN, especially when the training data ratio is large. In some datasets (i.e., Cora, FullCoraML), the performance of TMLP is slightly worse than GCN but still significantly better than MLP. It is worth noting that our proposed TMLP is only trained with the node features, ignoring the connection informa- tion. Table show the average accuracy (84.06) of TMLP is comparable to that of GCN (83.89).
Table 3: Performance comparison of GCN and HMLP.
Datasets
MLP
GCN
TMLP
Cora 73.57
88.04-1.2
88.26+1.0
CiteSeer
71.90
75.69 as
76.35 13
PubMed
86.90
87.94=0.e4
87.5820.44
Average
77.45
83.89
84.06
Based on the node representation, Test- Time Mirup make the node representation more discriminative than MLP. The visualization clearly illustrates that the node representations within the same class, as learned by TMLP, are clustered together. This clustering pattern demonstrates the advanced predictive power of TMLP, as it appears to have a keen ability to distinguish similar group classes effectively. Consequently, this capacity al- lows TMLP to deliver superior classification performance.
MLP
TMLP
GCN
Figure 5: Visualization of node representations Icarned by MLP and TMLP. Node representations from the same class, after Test- Time Minup, be- come clustered together.
The node representation clearly shows what TMLP does from the representation perspective.
4.2 How Does Test-time Mixup Benefit GCN? Investigating Decision Boundary
In this section, we evaluate the effect of Test- Time Mirup on the decision boundary change from MLP TMLP. To do so, we compare the distance between node features and the decision boundary of MLP before
8

---

Published in Transactions on Machine Learning Research (09/2024)
GCN-2 (Cora)
CCN-2 (CiteSeer)
GCN-2 (PubWed)
GCN-2 (FullCoraM)
90%
80%
585
Accurecy
80%
73%
96%
70%
70%
MLP
63%
60%
82%
TMLP
60%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
910%
10%
30%
50%
70%
90%
Training Data. Ratio
Troining Data.
Troining Data Ratio
Training Data Racio
Figure 6: The performance comparison of the GCNs, ML. and TMLP (Ours). GCN-1 one-layer GCN, and GCN-2 is two-layer GCN. The results show that TMLP achieves comparable performance to GCN and SGC. Note that the architecture is essentially MLP in training time and GCN in the test time. More results on other datasets and GNNs are presented in Appendix C.2.
MLP (Class Class
TMLP (Class D Clase 1)
MLP (Chee Clos 2; TMLP (Clasi 1 va Class
MLP (Class Class G)
TMLP (Clusi Class
TMLP (Clea
(Cliss
TMLP (Clee
MLP (Cliss 6)
TMLP (Clise
1)
G)
Figure 7: Decision Boundary of MLP and TMLP. TMLP can cause node features to move away from the learned boundary, as shown with O+O More experimental details are in Appendix C.3
and after applying Test Time Mirup. After training a model with training time data mixup, we evaluate its decision boundary, which separates different classes in the feature space. We then apply test-time mixup techniques node fcatures and reassess the decision boundary. Our findings indicate that O Test- Time Micup can cause node features to move away from the learned boundary, enhancing model robustness to unseen data. However, it's crucial to strike balance between Test- Time Mizup and model performance, overdoing Mixup may reduce accuracy.
5 Unifying HMLP and TMLP: Verifying the Main Results
In this section, unify HMLP and TMLP into single MLP, which integrates both Homophily Relabel and Test-time Mizup, They are supposed to be equivalent to graph convolution. To unify these two MLPs, 1) relabel all the nodes in the graph with the mixed label Y A Y. 2) train an MLP on all the nodes with Y on relabeled graph, only using node features. 3) employ the well-trained MLP for inference with neighbor aggregation during testing. To test the efficacy of this combined approach, we perform experiments comparing the performance of the unified MLP with that of individual HMLP and TMLP, as well as other GCN. The experimental setup remains consistent with the previous setting with HMLP and TMLP. We present the results in Figure 8. 0 Unifying HMLP and TMLP achieve comparable performance to original GNNs.

---

Published in Transactions on Machine Learning Research (09/2024)
GON-1 (Cora)
GCN-1 (CiteSeer)
GON-1 (PubMed)
GCN-1 (PullCoraMM)
90%
86%
90%
Accuracy
80%
867%
90%
70%
70%
84.7
70%
MLP
60%
60%
82%
60%
GCN-1
Mixup
10%
30%
50%
70%
70%
90%
70%
70%
GCN-2 (Cora)
GCN-2 (CiteSeer)
GCN-2 (PubMed)
GCN-2 (PullCoraML)
90%
90%
9056
88%
Accuracy
80%
73%
80%6
5659
70%
70%
84%
70%
MLP
35%
GCN
82%
Mixup
90%
60%
900%
10%
30%
50%
70%
10%
30%
50%
70%
SGC (Cora.)
SGC (CiteSeer)
SGC (Publedd
SGC (PualCrraML)
90%
80%
8896
75%
Aonuaag
40%
865
.80%
70%
84.5
70%
605
MI.P
82%
SGC
60%
60%
Mixup
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
50%
70%
90%
10%
30%
50%
70%
90%
Training
Training Ratio
Training Data Ratio
Training Data
Figure Unifying HMLP and TMLP. these methods together achieve performance comparable GNNs (excluding the PubMed dataset, the MLPs also exhibit better performance than GNNs.).
6 Discussion and Future Work
In this paper, we reveal the relation between graph neural networks and Mixup that graph neural networks are esscntially Mixup, in the sense that they can seen as a continuous interpolation between nodes in the graph. This equivalence allows for new interpretation of GNNs as a form of regularization, and provides a new perspective on the design GNNs.
Efficient Alternative Training and Inference Method for GNNs on Large Graph Data. HMLP presents efficient solution for both training and testing large-scale graphs, it completely eliminates the need for connection information during both stages. TMLP, though also MI.P-basd,, emphasizes training efficiency. The improved training efficiency of TMLP can still be advantageous for reducing the training cost on large graph.
Opening a New Door for Understanding Graph Convolution. The introduction of mixup, a simple node-level operation, offers novel perspective on graph convolution by representing it in a mixup form. Traditional graph convolution employs the adjacency matrix of the entire graph, concept. that can be complex to comprehend articulate. By approaching the understanding of graph neural networks from the entire graph level, we can demystify these complexities. This presents an essential avenue for exploration in future work related to our paper.
Future Work. Based on the above practical and theoretical potentials the proposed methods in this paper. Here are some potential future works: 1) improve HMLP make it more practical for largo-scale graphs and the performance when the training data ratio is small. 2) The well-studied Mixup strategy would be helpful for understanding the expressiveness of graph neural networks.
10

---

Published in Transactions on Machine Learning Research (09/2024)
Acknowledgements
This work was donc while Xiaotian Han an intern at Meta. We are grateful for the detailed reviews from the reviewers. Their thought,ful comments and suggestions were invaluable in strengthening this paper. Portions of this research were conducted with high performance research computing resources provided by Texas A&M University (https://hpres hhppc.tamm..duu) This work was supported in part by the National Science Foundation (NSF) IIS-2224843 and by the US Department of Transportation (USDOT) Tierl University Transportation Center (UTC) Transportation Cybersecurity Center for Advanced Research and Education (CYBER-CARE) grant #69A3552348332.
References
Guillaume P Archambault, Yongyi Mao, Hongyu Guo, and Richong Zhang. Mixup as directional adversarial training. Xiv preprint S5x:1996006877 2019.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in deep networks. arXiv preprint S.i::2204.09299 2022.
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In International Conference Learning Representations, 2023. URL https::/openreeview.
pet/fforum?id---33JPPP
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Graph neural networks with convolutional arma filters. IEEE transactions on pattern anelysis and machine intelligence, 4497):3496-3507, 2021.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950 3957, 2021.
Chen Cai, Dingkang Wang, and Yusu Wang. Graph coarsening with neural networks. In International Conference on Learning Representations, 2020.
Xuheng Cai, Chao Huang, Lianghao Xia, and Xubin Ren. LightGCL: Simple yet effective graph contrastive learning for recommendation. In The Eleventh International Conference on Learning Representalions, 2023. net formm?rrmm?m -ddFFkvKKFFyy..
URL htttps://openrete
Kaidi Cao, Jiaxuan You, Jiaju Liu, and Jure Leskovec. Autotransfer: AutoML with knowledge transfer an application to graph neural networks. In International Conference on Learning Representations, 2023.
URL https://openreriii httpiiiieennneetetteooeeeeeeeeee net/forum?id-yyipplk
Benjamin Paul Chamberlain, Sergey Shirobokov, Fmanuele Rossi, Fabrizio Frasca, Thomas Markovich, Nils Yannick Hammerla, Michael M. Bronstein, and Max Hansmire. Graph neural networks for link prediction with subgraph sketching. In International Conference on Learning Represenlations, 2023. URL https:// http:://pppaerrrieeeeeeeoortrrra
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pp. 1725-1735. PMLR, 2020.
Ziang Chen, Jialin Liu, Xinshang Wang, and Wotao Yin. On representing linear programs by graph neural networks. Tn International Conference on Learning Representations, 2023a. URL nel/forrum/dd-dPPVV--vaa
Zizhang Chen, Peizhao Li, Hongfu Liu, and Pengyu Hong. Characterizing the influence of graph elements. In International Conference on Learning Representations, 2023b. URL https: //pp:/evie/e/eeee//// net/ffrrm? id=51GXyzOKOp.
11

---

Published in Transactions on Machine Learning Research (09/2024)
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.
Muthu Chidambaram, Xiang Wang, Yuzheng Hu, Chenwei Wu, and Rong Gc. Towards understanding the data dependency of mixup-style training. In International Conference on Learning Representations, 2022.
URL https://openreviee..tt httpa//wre........oooooooaaaaaia
Sanghyuk Chun, Seong Joon Oh, Sangdoo Yun, Dongyoon Han, Junsuk Choe, and Youngjoon Yoo. An empir- ical evaluation on robustness and uncertainty of regularization methods. arxiv preprint arXic:2003.038 033809 2020.
Weilin Cong, Si Zhang, Jian Kang, Baichuan Yuan, Hao Wu, Xin Zhou, Hanghang Tong, and Mehrdad Mahdavi. Do we really need complicated model architectures for temporal networks? In International Conference on Learning Representations, 2023. URL https: https:s//ppeeeviers mtt//oorumrddeeapPooSyy..
Gabricle Corso, Hannes Stärk, Bowen Jing, Regina Barzilay, and Tommi S. Jaakkola. Diffdock: Diffusion steps, twists, and turns for molecular docking. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreviee www.rrvvieeweeeeeeee wwt./eotwt/dd-ntree.....e K-BbS..
Leyan Deng, Defu Lian, Chenwang Wu, and Enhong Chen. Graph convolution network based recommender systems: Learning guarantee and item mixture powered strategy. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Neural Information Processing Systems, 2022. URL
https://openrevieet sett/forum//d=aaloggj...
Francesco Di Giovanni, James Rowbottom, Benjamin P Chamberlain, Thomas Markovich, and Michael M Bronstein. Graph neural networks as gradient flows. Xiv preprint arXiv:2206. 10991, 2022.
Simon S Du, Kangeheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in newral information processing systems, 32, 2019.
Andrew Dudzik and Petar Veličković. Graph noural networks are dynamic programmers. arXiv preprint Xrxi::2203. 0ttti2223..5544 15544, 2022.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiu:200,.11198, 2020.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pp. 3419-3430. PMLR, 2020.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Hongyu Guo, Yongyi Mao, and Richong Zhang. Mixup as locally lincar out-of-manifold regularization. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 3712-3722, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NewrlPS, pp. 1024 1034, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. International Conference on Machine Learning, pp. 8230 8248. PMLR, 2022a.
Xiaotian Han, Tong Zhao, Yozen Liu, Xia Hu, and Neil Shah. Mlpinit: Embarrassingly simple gnn training acceleration with mlp initialization. arXiv preprint arXiv:2210.001 001002 2022b.
12

---

Published in Transactions on Machine Learning Research (09/2024)
Matej Hladiš, Maxence Lalis, Sebastien Fiorucci, and Jérémic Topin. Matching receptor to odorant with protein language and graph neural networks. In International Conference on Learning Represenlations, 2023. URL
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yuc Gao. Graph-mlp: node classification without message passing in graph. arXiv preprint arXiv:2106. 200.01006,00,1, 2021.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXio:2010.1399. 2020.
Bo Hui, Da Yan, Xiaolong Ma, and Wei-Shinn Ku. Rethinking graph lottery tickets: Graph sparsity matters. In International Conference Learning Representations, 2023. URL http:://opparrereew.ntttt wwt.:rerwwiieeee/oornne... id=f
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. -285-5288. PMLR, 2020.
Jang-Hyun Kim, Wonho Choo, Hosan Jeong, and Hyun Oh Song. Co-mixup: Saliency guided joint mixup with supermodular diversity. arXiv preprinl arXiv:2102. 03065, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv
preprint ar (rX:::6609.0 029007, 2016a.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. ar preprint arXiv:1611.07300 2016b.
Alex Lamb, Vikas Verma, Juho Kannala, and Yoshua Bengio. Interpolated adversarial training: Achieving robust neural networks without sacrificing too much accuracy. In Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security, pp. 95-103, 2019.
Yi-Lun Liao and Tess Smidt. Equiformer: Equivariant graph attention transformer for 3d atomistic graphs. In International Conference on Learning Representations, 2023. URL id=KwmPfARgOTD.
wtwponrrreee..ntfoorrrrr.. net/forum?
Zirui Luu, Kaixiong Zhou, Fan Yang, Li Lí, Rui Chen, and Xia Hu. EXACT: Scalable graph neural networks training via extreme activation compression. In International Conference Learning Representations, 2022. URL https://openreevew htwpaarwwwwii.eetoooouo/aa/a/ooe net//oormmid
David Lopez-Pazz Ishmael Belghazi, Diane Bouchacourt, Elvis Dohmatob, Badr Youbi Idrissi, Levent Sagun, and Andrew M Saxe. An ensemble view on mixup, 2023. URL https://openreviece http://awrrvveeeeeeeeef/rraaaaaa net/forum?id=k. iNqflnekU.
Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have low-pass filters. arXiv preprint Xrx:::1905.0 09550,, 2019.
Tianyu Pang, Kun Xu, and Jun 7hu. Mixup inference: Better exploiting mixup defend adversarial attacks. arXiv preprint ar wrXic:1909.11511 2019.
Mahalakshmi Sabanayagam, Pascal Essor, and Debarghya Ghoshdastidar, Representation power of graph convolutions: Neural tangent kernel analysis. arXiv preprint arXiw:2210.098 099009 2022.
Zhihao Shi, Xize Liang, and Jie Wang. LMC: Fast training of GNNs via subgraph sampling with provable convergence. In The Eleventh International Conference on Learning Representations, 2023. URL https: //openreview.netee wwtp:///////.om/////////A
Chuxiong Sun, Hongming Gu, and Jie Hu. Scalable and adaptive graph neural networks with self-label- enhanced training. arXio preprint ar arxiv:2104 09376, 2021.
13

---

Published in Transactions on Machine Learning Research (09/2024)
Ruoxi Sun, Hanjun Dai, and Adams Wei Yu. Does GNN pretraining help molecular representation? In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022. URL sttps://oppereviee
Xianfeng Tang, Yozen Liu, Xinran He, Suhang Wang, and Neil Shah. Friend story ranking with edge- contextual local graph convolutions. In Proceedings of the Fifteenth ACM International Conference on Web Search and Dala Mining, pp. 1007 1015, 2022.
Sunil Thulasidasan, Gopinath Chennupati, Jeff A Bilmes, Tanmoy Bhattacharya, and Sarah Michalak. On mixup training: Improved calibration and predictive uncertainty for deep neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh Chawla. Learning MLPs graphs: A unified view of effectiveness, robustness, and efficiency. In International Conference on Learning Representations, 2023. URL https://openreviee wtt.ppparrrieeeeee/oooiiieeeeeee
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne, Journal of machine learning research, 9(11), 2008.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Indernational Conference on Learning Representations, 2018.
Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najañi, loannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International Conference on Machine Learning, pp. 6438 6447. PMLR, 2019.
Kun Wang, Yuxuan Liang, Pengkun Wang, Xu Wang, Pengfei Gu, Junfeng Fang, and Yang Wang. Searching lottery tickets in graph neural networks: A dual perspective. In The Fleventh International Conference Learning Representations, 2023a. URL https: httpp:///operreview http:////pppaeeeeeeeeeeeeeeeraad
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-306 163-367,, 2021.
Zichao Wang, Weili Nie, Zhuoran Qiao, Chaowei Xiao, Richard Baraniuk, and Anima Anandkumar. Retrieval- based controllable molecule generation. In International Conference on Learning Representations, 2023b. URL https://
Chunyu Wei, Jian Liang, Di Liu, and Fei Wang. Contrastive graph structure learning via information bottleneck for recommendation. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Advances in Newral Information Processing Systems, 2022. URL https://openreviii wttprreeiiiieeeeeffuuuree net/ffrum? sd==hhl_YYlddtt
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
Jun Xia, Chengshuai Zhao, Bozhen Hu, Zhangyang Gao, Cheng Tan, Yue Liu, Siyuan Li, and Stan Z. Li. Mole-BERT: Rethinking pre-training graph neural networks for molecules. In The Eleventh International Conference on Learning Representations, 2023. URL http::///gpaaeereee..ee////rrrrr
Keyulu Xu, Chenglao 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. PMLR, 2018.
Chenxiao Yang, Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging guns and mlps. International Conference on Learning Representations, 2023.
14

---

Published in Transactions on Machine Learning Research (09/2024)
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. Advances in Neural Information Processing Systems, 10000000-17,,, 2020.
Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regularization strategy train strong classifiers with localizable features. In Proceedings of the IEFE/CVF international conference computer vision, pp. 6023 033-6032, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2019.
Bohang Zhang, Shengjie Luo, Liwei Wang, and Di He. Rethinking the expressive power of GNNs via graph biconnectivity. In International Conference on Learning Representations, 2023a. URL https: //openreview .ett:/oruunnddxr9M//6666011
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. In International Conference on Learning Represenlations, 2018.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, Amirata Ghorbani, and James Zou. How does mixup help with robustness and generalization? In International Conference on Learning Regresenlations, 2020.
Linjun Zhang, Zhun Deng, Kenji Kawaguchi, and James Zou. When and how mixup improves calibration. International Conference on Machine Learning, pp. 26135 26160. PMLR, 2022a.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. In International Conference on Learning Representations, 2021.
Shuai Zhang, Meng Wang, Pin-Yu Chen, Sijia Liu, Songtao Lu, and Miao Liu. Joint edge-model sparse learning is provably efficient for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b. URL httpss//opeerrviiee wtw.eeeeeeiiieeeeeoeoooiiiiiiiee net/forumnid-4U1dFL...
Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. arXiv preprint arXi::200.04955,, 2022b.
Yangtian Zhang, Huiyu Cai, Chence Shi, and Jian Tang. E3bind: An end-to-end equivariant network for protein-ligand docking. In International Conference on Learning Representations, 2023c. URL https://openrreview net/forummid==s011A...
ZAIXI ZHANG, Qi Liu, Shuxin Zheng, and Yaosen Min. Molecule generation for target protein binding with structural motifs. In International Conference on Learning Representations, 2023. URL https:
//openreview.o wwtpppnreree..nnt//orrrr.......
Jianan Zhao, Meng Qu, Chaozhuo Li, Hao Yan, Qian Liu, Rui Li, Xing Xie, and Jian Tang. Learning on large-scale text-attributed graphs via variational inference. In International Conference on Learning Representations, 2023. URL //tere///perreviee
wtwpiiiwwwweee/ffrooeeeeee net net:/formmid--g0mmmooamm
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57 81, 2020.
Jinhua Zhu, Kchan Wu, Bohan Wang, Yingee Xia, Shufang Xie, Qi Meng, Lijun Wu, Tao Qin, Wengang Zhou, Houqiang Li, and Tie-Yan Liu. 8' [O) incorporating ring priors into molecular modeling. In International Conference on Learning Representations, 2023a. URL https: id=5cFfz6yNVPU.
net/forum?
Zeyu Zhu, Fanrong Li, Zitao Mo, Qinghao Hu, Gang Li, Zejian Liu, Xiaoyao Liang, and Jian Cheng. 8' 3rrm& a 2q8: Aggregation-aware quantization for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023b. URL https: //perreviee met//foum?id-=712ng1000
15

---

Published in Transactions on Machine Learning Research (09/2024)
Appendix
Table of Contents
A Related Works
16
A.1 Graph Neural Networks
16
A.2 Mixup and Its Variants
................................
17
A.3 Efficient Graph Neural Networks
17
B Connection between Mixup and More Graph Convolutions
B.1 Discussion on More Graph Convolutions
................................
17
B.2 Experiments on APPNP
................................
B.3 GNN with trainable mixing parameter X
Additional Experiments
18
C.1 More Experiments for HMLP
18
C.2 More Experiments for TMLP
20
C.3 More Experiments Decision Boundary
................................
20
C.4 More Experiments on Deeper GCNs
................................
20
C.5 Experiments on More Datasets
22
D Experiment Setting
D.1 Rumning Environments
23
D.2 Experiment Setup for Figure 4
23
D.3 Experiment Setup for Figure 6
23
D.4 Experiment Setup for Figure 8
23
E Datasets
23
A Related Works
In this appendix, we discuss more related work to our paper.
A.1 Graph Neural Networks
Starting from graph convolutional network (Kipf & Welling, 2016a), graph neural networks have been applied to various graph learning tasks and show great power for graph learning tasks. Despite the practical power of graph neural network, understanding the generalization and working mechanism of the graph neural networks are still its infancy (Garg et al., 2020; Zhang al., 2023a; Vang et al., 2023; Baranwal al., 2023). The previous works try understand graph neural networks from different perspectives, such as signal processing (Nt & Maehara, 2019; Bo al., 2021; Bianchi al., 2021), gradient flow (Di Giovanni al., 2022), dynamic programming( (Dudaai Dudzik & Veličković, 2022), neural tangent kernels (Yang et al., 2023; Du et al., 2019; Sabanayagan et al., 2022) and influence function (Chen et al., 2023b). There is also line of works try to understand graph neural networks by analyzing the connection between GNNs and MLPs (Baranwal et al., 2023; Han et al., 2022b; Yang el al., 2023; Tian et al., 2023).
In our work, we understand graph neural networks through a fresh perspective, Mixup. We believe this work will inspire further research and lead the development of new techniques for improving the performance and interpretability of GNNs.
16

---

Published in Transactions on Machine Learning Research (09/2024)
A.2 Mixup and Its Variants
Mixup (Zhang et al., 2018) and its variants (Verma el al., 2019; Yun el al., 2019; Kim et al., 2020; 2021) are important data augmentation methods that are effective in improving the generalization performance of deop neural networks. Mixup is used to understand or improve many machine learning techniques. More specifically, deep neural networks trained with Mixup achieve better generalization (Chun et al., 2020; Zhang et al., 2020; Chidambaram et al., 2022), calibration (Thulasidasan et al., 2019; Zhang et al., 2022a), and adversarial robustness (Pang et al., 2019; Archambault al., 2019; Zhang et al., 2020; Lamb et al., 2019). As studies data augmentation method, Mixup can be understood as regularization term to improve the effectiveness and robustness of neural network (Pang et al., 2019; Archambault et al., 2019; Zhang et al., 2020; Lamb et al., 2019). Mixup are also used to explain some other techniques, such as ensmeble (Lopez-Paz et al., 2023). Additionally, Mixup technique is also used to augment graph data for better performance of GNNs Han et al. (2022a); Wang et al. (2021).
In this work, we use Mixup to explain and understand the graph neural network, and based on the Mixup, we propose two kinds of MLP that achieve almost equivalent performance to graph neural networks. Also, our work is different form the works that chance the GNN training with Mixup, while we connect the graph convolution and Mixup.
A.3 Efficient Graph Neural Networks
Although the graph neural networks are powerful for graph lcarning tasks, they suffer slow computational problems since they involve either sparse matrix multúplication neighbors fetching during the inference, resulting in active research on the efficiency of graph neural networks. The recent advances in efficient graph neural networks are as follows. Efficient graph neural network (Wang et al., 2023a; Shi et al., 2023; Hui et al., 2023; Zhang et al., 2023b; Zhu et al., 2023b) includes the sampling-bass Chiang et al., 2019; Zeng et al., 2019), quantization (Tiu et al., 2022), knowledge distillation (Zhang et al., 2021; Tian et al., 2023), and graph sparsification (Cai et al., 2020). There is a line of work to try to use MLP to accelcrate the GNN training and inference (Zhang et al., 2022b; Wu et al., 2019; Frasca et al., 2020; Sun et al., 2021; Huang et al., 2020; Hu et al., 2021). Simplifying graph convolutional (SGC) (Wu et al., 2019) "simplifying" graph convolutional network by decoupling the neighbor aggregation and feature transformation, the following work such as You et al. (2020) employ the similar basic idea. Zhang et al. (2021) leverage knowledge distillation to transfer the knowledge from GNN to MLP. Han et al. (2022b) and Yang et al. (2023) transfer the weight from ML.P to GNN. These kinds of methods use MT. for efficient graph neural networks.
method (Hamilton et al., 2017;
Our proposed methods HMLP and TMLP are efficient for training and inference, which can be categorized an efficient graph neural network. Besides, our proposed method provides a new perspective to understand graph neural networks.
B Connection between Mixup and More Graph Convolutions
B.1 Discussion on More Graph Convolutions
We examine the connection bet complex graph convolutions used in various graph neural networks and Mixup. We aim to approximately rewrite complex graph convolutions (like those in graph attention networks) into Mixup forms. We present general Mixup form of graph convolution for node n; in the graph as follows
(x,
Σ HHH,, Σ A,yi JEN;
(9)
JEN;
Equation (9) shows that graph neural networks architectures vary depending on: 1) how to select neighbors set (Ni), 2) how to select aggregation coefficient (Ay), and 3) what is mixed up (H₂). For example, if we
set. N = N?, X 1
p the above equation will be SGC. However, there are lot of advanced graph neural
networks, such as GAT (Veličković et al., 2018)) (attention-based GNN), and PPNP (Gasteiger et al., 2018)
17

---

Published in Transactions on Machine Learning Research (09/2024)
Table 4: Examples of the relation between graph convolutions to Mixup at k-layer.
(NC)
(A,)
(H))
GCN N
a
H
SGC
N
a
X
GAT
N
Attention Score
H
PPNP
N
B,
Logit
(MLP the backbone). Table 4 shows the relationship between those graph convolutions to Mixup. To include residual connections in some graph convolutions (Chen et al., 2020; Xu et al., 2018); we can expand the neighbors set M₁ of node to include its node representation of the previous time step.
B.2 Experiments APPNP
APPNP essentially performs the neighbor aggregation in the last layer. Thus, TMLP and HMLP, according APPNP, are equivalent GCN. We report the performance in the table below. The results show that TMLP and HMLP achieve better performance than APPNP.
Table 5: Performance Metrics of Different Methods
MLP
PPNP
TMLP
HMLP
73.57
83.80
88.26
86.42
B.3 GNN with trainable mixing parameter
In this experiment, we adopted a method similar to GAT to examine the performance of our proposed method, with the mixing parameter À being learned during the training process. The Softmax (Li et al., 2020) is a learnable aggregation operator that normalizes the features of neighbors based on lcarnable temperature term. We report the performance in the table below. The results show that the TMLP performed worse than the MLP. This indicates that the learnable mixing parameter À does not work well for our proposed method
Table Performance Metrics of Different Methods
MLP
GAT-alike
TMLP
73.57
88.42
65.62
C
Additional Experiments
This appendix presents more experiment results on HMLP and TMLP, including 1) comparison experiments of MIP, GCN, and HMLP/TMLP: 2) more experimental results decision boundary.
C.1 More Experiments for HMLP
We present further experiments comparing MLP, GCN, and HMLP. These experiments complement those discussed in Figure 4. We expand on that work by evaluating these methods with more GNN architectures. The results are presented in Figure
The results on more GNN architectures indicate that our proposed HMLP method not only outperforms traditional ML.P, but also attains performance that is largely par with GNNs in the majority of instances.
18

---

Published in Transactions on Machine Learning Research (09/2024)
GCN-1 (Cora)
GCN-1 (CiteSeer)
GCN-1 (PabYed)
GCN-1 (PullCoreML)
90%
90%
Acarray
80%
86%
80%
70%
84.%
70%
60%
82%
60%
HMLP
GCN-1
1036
30%
50%
70%
900
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
GON-2 (Cors)
GCN-2 (CiteSeer)
GCN 2 (PabMed)
GCN (PullCoreMM))
90%
80%
90%
989
Accaracy
80%
75%
9696
80%
70%
70%
841%
70%
MLP
65%
GCN
60%
82%
HMLP
60%
1056
30%
30%
70%
900%
10%
30%
50%
70%
90%
50%
70%
90%
10%
30%
50%
70%
90%
SGC (Cora)
SGC (CiteSeer)
SGC (PubMed)
SGC (PallCoraML)
90%
80%
88%
90%
75%
Accuracy
30%
80%
80%
70%
84.5
70%
65%
70%
82%
SGC
60%
60%
60%
HMLP
90%
10%
300
30%
70%
90%
10%
330%
50%
70%
90%
10%
30%
50%
70%
900%
10%
30%
50%
70%
90%
Training Ratio
Training Data Ratio
Training Data Ratio
Training
Ratio
Figure 9: The performance comparison of the GCN, MLP and HMLP (Ours) with GNN architectures. The x-axis represents the ratio training data, and the y-axis represents the classification accuracy. The results show that our proposed method (HMLP) achieves comparable performance to GCN.
19

---

Published in Transactions on Machine Learning Research (09/2024)
C.2 More Experiments for TMLP
We present further experiments comparing MLP, GCN, and TMLP. These experiments complement those discussed in Figure 6. We expand on that work by evaluating these methods with more GNN architectures. The results are presented in Figure 10.
With the evaluation of an expanded selection of GNN architectures, the results reveal that our proposed method TMLP typically achieves performance comparable traditional GNNs in most situations.
GCN-1 (Cora)
GCN-1 (CiteSeer)
GCN-1 (Publed)
GCN-1 (PullCoraNL)
90%
80%
887
90%
Accuracy
80%
86%
80%
70%
70%
844
MLP
60%
60%
82%
60%
TMLP
GCN
10%
30%
50%
70%
90%
10%
30%
50%
70%
907
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
GCN-2 (Core)
GCN-2 (CiteSeer)
GCN-2 (PubMed)
GCN-2 (PullCoraNL)
90%
80%
88%
90%
Accuracy
980%
75%
88%
70%
70%
8-4%6
MLP
65%
GCN-2
60/%
82%
60%
10%
30%
50%%
70%
90%
10%
30%
50%
70%
90%
10%
30%
509%
70%
90%
10%
30%
50%
70%
90%
SGC (Cora)
SGC (CiteSeez)
SGC (PubMeed)
SGC (FullCoraML)
80%
90%
75%
Accuracy
30%
86%
8096
70%
70%
65%
84%
70%
MLP
82%
SGC
60%
80%
60%
TMLP
80%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
Training Data Ratio
Training Data Ratão
Training Data Ratão
Training Data Ratio
Figure 10: The performance comparison of the GCNs, MLP and TMLP (Ours). GCN-1 is a one-layer GCN, and GCN-2 two-layer GCN. The results show that TMLP achieves comparable performance to GCN and SGC. Note that the architecture is essentially MLP in training time and GCN in the test time.
C.3 More Experiments Decision Boundary
We provide additional experimental results pertaining the decision boundary of TMLP. Our findings indicate that TMLP tends to shift the node features in the test set away from the pre-learned decision boundary by TMLP.
C.4 More Experiments on Deeper GCNs
We conducted additional experiments on multi-layer graph neural network (SGC) on the Cora datasel. We use the 20% 20%\40% 40%), 40% for train) vall data split. The test accuracy was determined based on the results from the validation datasct. The test accuracy is reportod the following table. We observe from the results that our proposed HMLP+TMLA method achieves performance comparable that of SGC when multiple graph convolutions utilized.
20

---

Published in Transactions on Machine Learning Research (09/2024)
MLP (Chess w. Cles 1)
TMLP (Clas O ve Cbee I]
MLP (Claes ta Glose 2)
TMLPP (Clivs 6 ae Class Xt
MLP (Chox O v Cluvs S)
TMLP (Class O we Clas 3)
MLP (Clve 0)
MLP (Chos 1)
MLP (Cless
TMLP (Cloa 0)
MLP (Class 0)
TMLP (Chvas
0)
(Cloos
(Chew
(Clae
(Cluse
(Clver
MLP (Clisss vs Close 4)
TMLP (Cliss 0 va Cliss 4)
MLP (Class vs Class 6)
TMLP (Clua 0 sa Class
MI.P (Chuss O1 ss Class 6)
TMLP (Clnss D us Class
MLP (Class 0)
TMLP (Clozs 0)
MIP (Claze
TMLP CCloz
MLP /Cloze
TMLP (Cloz:
4)
Figure 11: Decision Boundary of MLP and TMLP. TMLP node features to move away from the learned boundary.
Table 7: Performance comparison of GNNs and proposed method with different layers.
1-layer
2-layer
3-layer
4-layer
MLP
69.11
68.95
68.39
69.22
SGC
82.38
84.50
84.23
83.95
HMLP
78.56
80.41
80.96
81.15
TMLP
82.10
83.76
83.49
83.67
HMLP +TMLP
83.
83.95
84.87
84.41
21

---

Published in Transactions on Machine Learning Research (09/2024)
GCN-1 (Fu11DBLP)
GCN-1 (FeerCiteSeerr
GCN (FullCora)
70%
80%
90%
Accuracy
Aecuracy
Accuracy
-60%
75%
80%
50%
MLP
GCN-1
70%
70%
40%
Mixup
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
Training Data Ratio
Training Data Ratio
Training Data Ratio
GCN-2 (Fu11DBLP)
GCN-2 (FullCiteSeer)
GCN-2 (Ful1DBLP)
85%
85%
Accuracy
80%
Accuracy
90%
Accuracy
80%
75%
80%
75%
MLP
GCN-2
Mixup
70%
70%
70%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
Training Data Ratio
Training Data Ratio
Training Data Ratio
SGC (FullDBLP)
SGC (FullCiteSeer
SGC (Ful Coraa)
85%
70%
90%
Accuracy
80%
Accuracy
Accuracy
-0%
75%
80%
50%
MLP
SGC
70%
70%
40%
Mixup
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
10%
30%
50%
70%
90%
Training Data Ratio
Training Data Ratio
Training Data Ratio
Figure 12: The additional experimental result on unifying HMLP and TMLP. These methods together achieve performance comparable to GNNs on these additional datasets. The additional results show that graph convolution is a mixup under our proposed modifications.
C.5 Experiments on More Datasets
We conducted additional experiments on more datasets, including FullCora, FullSiteSoer, FulIDBLP, and the results are presented in Figure 12. The additional results provide more evidence that graph convolution is a mixup under our proposed modifications.
D Experiment Setting
In this appendix, we present the running environment for our experiment and the experimental setup for all the experiments.
22

---

Published in Transactions on Machine Learning Research (09/2024)
D.1 Running Environments
We run all the experiments NVIDIA RTX A100 on AWS. The code is based on PyTorch 3 and torch geometric 4, The datasets used in this paper are built-in datasets in torch geometric, which will be automatically downloaded via the torch geommtric API.
D.2 Experiment Setup for Figure 4
We provide details of the experimental sctup associated with Figure 4. The primary objective of this experiment was to compare the performance of our proposed HMLP model with that of the GCN model. We utilized diverse datasets to facilitate a comprehensive evaluation. We set the learning rate to 0.1 for all methods and datascts, and each was trained for 400 spochs.Morcovee model training. The test. accuracy reported is based on the best results from the validation set. The node classification accuracy served the evaluation metric for this experiment.
we did use weight decay for
D.3 Experiment Setup for Figure
We provide details of the experimental setup associated with Figure We the learning rate 0.1 for all methods, and cach was trained for 400 epochs. Additionally, weight decay was not utilized in this process. The lest accuracy reported is based on the best results from the validation set. The node classification accuracy served as the evaluation metric for this experiment.
D.4 Experiment Setup for Figure 8
We provide details of the experimental setup associated with Figure 8. We set the learning rate to 0.1 for all methods, and cach was trained for 400 epochs. Additionally, weight decay was not utilized in this process. The lest accuracy reported is based on the best results from the validation set. The node classification accuracy served as the evaluation metric for this experiment.
E
Datasets
In this experiment, we use widely adopted node classification benchmarks involving different types of networks: three citation networks (Cora, CiteSeer and PubMed). The datasets used in this experiment are widely adopted node classification benchmarks. These networks are often used as standard evaluation benchmarks in the field of graph learning.
Cora: widely used benchmark data for graph lcarning, which a citation network, where cach node represents a research paper, and edges denote the citation relation. Node features are extraceed from the abstract of the paper.
CiteSeer is another citation network used frequently in GNN literature. It follows similar structure to the Cora dataset, where each node represents scientific document, and the edges are citation information between them. The node features are derived from the text of the documents.
PubMed: PubMed is a citation network composed of scientific papers related to biomedicine. As with the other datasets, nodes represent documents, and edges indicate citation relationships. Node fcatures correspond term frequeney-inverso document frequency (TF-IDF) representations of the documents.
FullCoraML is subset of the full Cora dataset. It retains the same structure the Cora dataset but is restricted to documents and citations within the field of machine learning. The node features are the bag-of-words representation ion for the papers.
hnttpe:/ppyoorch.org httpps://sg..rrg/
23


Reviews:
[{"review_id": "V4ITz5iB8t", "reviewer": "Reviewer_M7XU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n* Reading the paper feels intuitive. Plots look clear.\n* The mathematical treatment on top of separation of the two conditions for equivalence help understanding.\n* Experiments and analysis on Cora, CiteSeer, and PubMed datasets demonstrate similarity between GCNs and the proposed methods.\n\n**Weaknesses:**\n* It is not clear who the audience is and it is not clear if the paper is more about Mixup, GCNs, or both. Compared to an audience that is coming from Mixup, the paper is more focused on graph problems. Is the audience graph neural network researchers and practitioners? Section 6 discusses potential impacts but that is already very late in the writing.\n* It wasn't clear to me how the $\\lambda$ component in Mixup is handled or what the definition of a neighborhood is, especially when comparing to the original Mixup paper's setting. $\\lambda$ is randomized, but in GCNs the weight is fixed and a function of the neighborhood? If Mixup combines two random samples, is it then equivalent to say that Mixup is a fully-connected graph? The title implies GCNs and Mixup are the same, but these differences make it appear there is only partial overlap.\n* The paper seems repetitive at times, where the same argument is being applied in multiple sections, but with different degrees of detail.\n* Section 3.1 was difficult to understand, partially because notation is not used consistently ($x_i$ is $n_i$?). The linearization of the model function also seems to have little justification.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a way to link graph convolution networks (GCNs) with Mixup. It does so by showing mathematical equivalence of GCN with mixup under certain conditions. The two conditions are Homophily Relabel and Test-Time Mixup. Empirically, a mixup-inspired procedure applied to Multilayer Perceptrons (MLPs) is tested again GCNs to demonstrate comparable performance gains over vanilla MLPs.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above weaknesses for recommended changes.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "B3VjlEoyse", "reviewer": "Reviewer_gvvd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The discovery presented in this paper is interesting from both mathematical and empirical perspectives.\n\n- Solid mathematical analysis is included to show the equivalence of the graph neural network and mixup.\n\n- Concrete experimental results are provided to understand the discovery. \n\nWeaknesses:\n\n- A minor concern was that some of the proposed future work is not that heavy, which should be included in this paper to make the content more self-included. To be more concrete, I think the discussion of the computation efficiency of the potential proposed modification based on this discussion should be included in this paper with some computation complexity analysis and empirical  study.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents an interesting discovery regarding the relationship between graph neural networks and the mixup method. Based on this observation, the paper further discussed two interesting methods: \n\n- **Homophily Relabel**: graph convolution is conditionally equivalent to Mixup by assigning the label of a target node to all its neighbors during training time. \n- **Test-Time Mixup**: in the test time, graph convolution is also Mixup.\n\nAnd a solid empirical study is presented to support the discovery. \n\nIn general, I want to endorse the acceptance of the paper with a light-weight modification.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See my listed minor weakness above.", "broader_impact_concerns": "No applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7lezkGrHSG", "reviewer": "Reviewer_uJ4g", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "__Strengths:__\n\nClaims are backed up by experiments, which show interesting results. In particular, it is interesting to see that with such a simple tweak on MLP training and testing, one is able to achieve results that are competitive to GCNs. The results suggest that the high performance of GCNs can be partly attributed to the Mixup-like effect that happens within the GCN architecture.\n\n__Weaknesses:__\n\nThe writing is a little careless overall, which can be fixed to improve the overall readability. Some claims in the paper are also not entirely rigorous. These arguments can be elaborated more. Please see more details in \"Requested Changes\" below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates connections between Graph Convolution networks and Mixup, a popular data augmentation technique in deep learning. By establishing that a single layer of GCN is equivalent to Mixup up to \"Homophily Relabel\" and \"Test-time Mixup\", the authors empirically demonstrate that MLPs can achieve similar test performance to GCNs by including these modifications.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I think the expression \"graph convolution can be viewed as a special form of Mixup under mild and reasonable conditions\" (page 3) or similar phrases used throughout the paper is a little misleading as that seems to imply that under certain conditions met by the data or the model architecture, Mixup, by itself, can be re-expressed as graph convolution. However, from my understanding of the authors' arguments, this isn't really the case - in order to get equivalence to GCNs, one has to actually make changes to the original Mixup method, by imposing homophily relabelling and doing test-time Mixup. In my view, these are not really \"conditions\" but rather tweaks to the original Mixup method. Also, the arguments in the paper only applies to node-wise predictions made by GCNs and not graph-wise predictions (e.g. molecular predictions), which should be noted somewhere.\n- Some concepts are introduced without explanation. It would help to add a line or two about these to help readability. This includes:\n   - Multi-sample manifold Mixup (page 5)\n   - t-SNE (page 8)\n- I don't understand the argument that led to claiming $f(\\lambda_k x + (1-\\lambda_k)x_k) \\approx \\lambda_k f(x) + (1 - \\lambda_k) f(x)$ in page 6. First of all, the notation $f$ is not introduced, which I assume is a neural network. Even so, I do not see how the approximate linearity should hold. Further explanation is needed here to make the argument more convincing.\n- Can the authors explain why the MLP and Mixup curves in Figures 8, 9, 10 and 12 vary from row to row? From what I understand, the only thing that changes from row to row in these figures are the particular GCN architectures used as baselines. Then, why should the performance curves of the MLP baseline and Mixup change also?\n- In HMLP, it is unclear whether we apply Mixup in the inputs as usual, or not. This should be clarified.\n- One of the benefits the authors claim in using the Mixup alternative to GNNs is the increased training/testing efficiency. Why should this be true? I don't see how the total computational cost would change (if we also include the data augmentation time into consideration in Mixup). Please could you elaborate more?\n- There are several misprints in the manuscript and sentences that need improvement. This includes:\n    - \"ensmeble\" (page 3) -> \"ensemble\".\n    - \"In the training time\" / \"In the test time\" (page 4) -> \"At training time\" / \"At test time\".\n    - \"phoneme\" in page 6. I believe this is supposed to be \"phenomena\".\n    - The sentence \"...achieves comparable performance of GCN for via training a MLP as a backbone\" (page 6) is convoluted and hard to understand.\n    - \"data training data split ratio\" (page 7). It might be better to phrase this as \"the ratio of training to test data\".\n    - \"same test curves\" (page 7). I would suggest using the word \"similar\" instead, as it is not really the \"same\".\n    - \"train the following training examples\" (page 8). The object that is trained is the model, not the training examples.\n    - Title of section 4.1 \"How TMLP Perform...\" -> \"How Does TMLP Perform...\".\n    - \"In the Figure 4, the performance of ...\" (page 8) should be \"In Figure 6, the performance of ...\". If I understand, the authors are referring to Figure 6, not Figure 4.\n    - \"Here is some potential future works\" (page 9) -> \"Here are some potential future works\".\n    - \"despite the PubMed dataset ...\" (page 10) -> \"excluding the PubMed dataset...\" or something along this line.", "broader_impact_concerns": "As far I can see there are no negative ethical implications of this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper contributes, mainly from an empirical point of view, in relating graph convolution with Mixup approach for augmenting a dataset via derived examples. Specifically, the authors discuss a specific setting involving two modifications under which graph convolution can be viewed as a specialized form of Mixup. Although the modifications are a bit unusual (Homophily Relabel and Test-Time Mixup), the contribution helps to give a novel interpretation of graph convolution that can potentially lead to interesting future developments.
Decision: Accept (poster)