IntraMix: Intra-Class Mixup Generation for Accurate Labels and Neighbors
Authors: Shenghe Zheng
Hongzhi Wang
Xianglong Liu
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Machine Learning
Graph Data Augmentation
Graph Neural Networks
Primary area: graph_neural_networks
TL;DR: This paper introduces IntraMix, a graph augmentation method that employs Intra-Class Mixup and high-confidence neighbor selection. IntraMix addresses both the issues of scarce high-quality labels and missing neighborhoods in most graphs.

Abstract: Graph Neural Networks (GNNs) have shown great performance in various tasks, with the core idea of learning from data labels and aggregating messages within the neighborhood of nodes. However, the common challenges in graphs are twofold: insufficient accurate (high-quality) labels and limited neighbors for nodes, resulting in weak GNNs. 
Existing graph augmentation methods typically address only one of these challenges, often adding training costs or relying on oversimplified or knowledge-intensive strategies, limiting their generalization.
To simultaneously address both challenges faced by graphs in a generalized way, we propose an elegant method called IntraMix. Considering the incompatibility of vanilla Mixup with the complex topology of graphs, IntraMix innovatively employs Mixup among inaccurate labeled data of the same class, generating high-quality labeled data at minimal cost. 
Additionally, it finds data with high confidence of being clustered into the same group as the generated data to serve as their neighbors, thereby enriching the neighborhoods of graphs. IntraMix efficiently tackles both issues faced by graphs and challenges the prior notion of the limited effectiveness of Mixup in node classification. IntraMix is a theoretically grounded plug-in-play method that can be readily applied to all GNNs. Extensive experiments demonstrate the effectiveness of IntraMix across various GNNs and datasets. Our code is available at:  [https://github.com/Zhengsh123/IntraMix](https://github.com/Zhengsh123/IntraMix).

IntraMix: Intra-Class Mixup Generation for Accurate Labels and Neighbors
Shenghe Zheng, Hongzhi Wang' Xianglong Liu
Massive Data Computing Lab, Harbin Institute of Technology shenghez. www.egggainnnnnnneecmoooomo com wangzh@hit, edu. on
Abstract
Graph Neural Networks (GNNs) have shown great performance in various tasks, with the core idea learning from data labels and aggregating messages within the neighborhood of nodes. However, the common challenges in graphs are twofold: insufficient accurate (high-quality) labels and limited neighbors for nodes, resulting in weak GNNs. Existing graph augmentation methods typically address only these challenges, often adding training costs or relying on oversimplified or strategies, limiting their generalization. To simultancously address both challenges faced by graphs in a generalized way, we propose an elegant method called IntraMix. Considering the incompatibility of vanilla Mixup with the complex topology of graphs, IntraMix innovatively employs Mixup among inaccurate labeled data of the same class, generating high-quality labeled data minimal cost. Additionally, it finds data with high confidence of being clustered into the same group the generated data to serve their neighbors, thereby enriching the neighborhoods of graphs. IntraMix efficiently tackles both issues faced by graphs and challenges the prior notion of the limited effectiveness of Mixup in node classification. IntraMix is theoretically grounded plug inng-in-play method that can be readily applied to all GNNs. Extensive experiments demonstrate the effectiveness of IntraMix across various GNNs and datasets. Our code is available at: https:/giitub.com//henggg 23/IntraMix.
Introduction
Graph Neural Networks (GNNs) have demonstrated great potential in various tasks [52]. How- ever, most graph datasets lack high-quality labeled data and node neighbors, underscoring two key challenges for GNNs: the dual demands for accurate labels and rich neighborhoods [5].
Data augmentation is one way address these two issues, research on graph data augmentation
insufficient. Additionally, it is challenging apply widely studied data augmentation ways designed for Euclidean data such as images to graphs due to their non- -on-Euciidean nature [15]. Therefore, unique graph augmentation methods are needed. While graph augmentation aims to generate high- quality labeled data and enrich node neighbors, most methods either focus on one aspect and often suffer from poor generalization ability. For example, some require generators, incurring additional training costs [51, 24]. Others rely on overly simplistic ways such as random drop, yielding little improvements [7]. Still, some depend excessive prior knowledge, weakening generalization abilities [48]. Therefore, there is an urgent need for an effective and generalized augmentation method that can produce high-quality labeled nodes and adequately enrich node neighbors.
Reviewing existing methods, we find that they overlook the potential of low-quality labeled data, which can be obtained at low cost. Extracting information from such data could enrich data diversity.
CCorespooning author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The cause of luw-quality labels is the noise in labels, which results in distribution different from the real one [10]. The noise direction usually mixed, so a natural idea is to blend noisy data, leveraging noise directionality to neutralize it and produce accurate labels. Therefore, Mixup [50] comes into our eyes as a method that involves mixing data. is defined as ě = Az; + (1 2) y = Ay/; + (1 A)yj- where ( y:); ( Uÿ) represent selected data, and represents the label. Despite Mixup excels in Euclidean data, experiments suggest its limited ability in node classification task [45]. Therefore, a question emerges: Can Mixup solve augmentation problems for node classification?
Due to the characteristics of graphs, using Mixup is challenging. The main reason Mixup performs poorly in node classification can be attributed to the graph topology. In Euclidean data such as images, the data generated by Mixup are independent [23], whereas in graphs, the generated nodes need to be connected to other nodes to be effective. This means that graphs, the data generated by vanilla Mixup is difficult to determine its neighbors and connecting them to any class of nodes is inappropriate,
Label(Noisy)
True Label
Mixup Label
Mixup Process
Yrong Messagi
Passing
its distribution does not belong to any current class of data [45]. Hence, the complex topology of the graph directly leads to the inapplicability of vanilla Mixup.
Wronz Mixup Label
(a). Vallina Mixup Graph
High Quality Label
To address the issues, we propose IntraMix, novel augmentation method for node classification, as shown in Figure (b). The core idea is that since nodes generated by Mixup between different class data are hard to find neighbors for, we mix nodes within the same class obtaining by pseudo-labeling (low-quality labels) instead [21]. Hereby, the main benefit of this approach is that it addresses the primary challenge about neighborhood of applying Mixup on graphs. The generated node features are no longer mixture of features from multiple groups, making easier to find neighbors based on their respective groups. Additionally, the generated nodes have higher quality labels. Intuitively, if we simplify the label noise (O, o²), the mean distribution of two noises ē ~ NO, fa²). with a smaller variance, increases the likelihood that the generated label is accurate. Therefore, we address the sparse high-quality labels by Intra- Intra-Class Mixup. It is important to emphasize that although some works have used Intra- Class Mixup [25]. we are the first to use it as the sole augmentation method and analyze it in depth.
Cprrect Message
Passing
High Quality Mixup Labe
(b). Intra Clas- Mixup of IntraMix Graph
Figure 1: a). Vanilla Mixup may retain la- bel noise, and connecting generated nodes to original nodes may lead to incorrect propaga- tion. b). IntraMix generates high-quality data by Intra-Class Mixup and enriches neighbor- hoods while preserving correctness by con- necting generated data to high-quality nodes.
Once the method for generating data is determined, the neighborhood selection method becomes very straightforward. For the neighbor selection strategy of the generated node v, connect to two nodes with high confidence of the same class with v. This has two benefits. Firstly, based on the assumption that nodes of the same class are more likely to appear as neighbors (neighborhood assumption) [53], we reasonably find neighbors for v. providing it with information gain in training and inferencing. Secondly, by connecting v two nodes that belong to the same class, we not only bring message interaction to the neighbors of these two nodes but also reduce the impact of noise that may still be present in direct connecting high-quality labels. In this neighbor selection way. we construct rich and reasonable neighborhood for nodes, enhancing the knowledge on the graph, which allows for the development of stronger GNN models for downstream tasks.
Therefore, IntraMix simultaneously addresses two challenging issues faced by graphs and exhibits strong generalization capabilities in elegant way. Our key contributions are as follows:
For the first time, we introduce Intra-Class Mixup as the core data augmentation in node classifica- tion, highlighting its effectiveness in generating high-quality labeled data.
The proposed IntraMix tackles sparse labels and incomplete neighborhoods faced by graph datasets through an elegant and generalized way of mntrs Mixup and neighborhood selection.
Extensive experiments demonstrate that IntraMix improves the performance of GNNs on diverse datasets. Theoretical analysis elucidates the rationale behind IntraMix.

---

Generate Low Quality Label
Intra-Class Mixup
Generate Neighbor
Label Generator
Output
Find High Quality Labell
(with Sparse Labels)
Input Graph
Labeled Graph
Low Quality
GNN
dropout,
Label Ieteeaae
dropout, dropout,
Uniabeled
Mixup
Labeled Node
Labeled Node
Node
Progress
Edge
Figure 2: The workflow of IntraMix involves three main steps. First, it utilizes pseudo-labeling to generate low-quality labels for unlabeled nodes. Following that, Intra-Class Mixup is employed to generate high-quality labeled nodes from low-quality ones. Additionally, it identifies nodes with high confidence in the same class and connects them, thus constructing rich and reasonable neighborhood.
2
Preliminaries
Given a graph G = (V, E), where [ma) the node set, and E represents the edge set, the adjacency relationship between nodes can be represented by A E {0, 1j_xx.. where Ag 1 if and only if (us, Uz) E E. We use X E R to denote the node feature. The node labels are represented by Y. Based on the presence or absence of labels, can be divided into Di {2), Mt, ....(%,,,, ( M1y) }} and D. s..us...uu }. We
Notations:
pseudo-labeling to assign low-quality labels Y, to nodes in D.. getting a low-quality set Dp {(z.. Yu, )..,)... (Zxx yax }}- N; (1 (uylA4 }} are the neighhors of u4 Detailed notation list can be found in Appendix A.
Node Classification with GNNs: Given graph G, the node classification involves determining the category of nodes on G. GNNs achieve this by propagating messages on G, representing each node as vector hy. The propagation for the k-th layer of a GNN represented as follows:
h COM(N AGG(U Iu E N.)))
where COM and AGG are COMBINE and AGGREGATE functions, respectively, and Ny denotes feature of at the k-th layer. The output h, in the last layer of GNN is used for classification as y/ so tmax(ho,) where ye is the predicted label for v.
3 Methodology
In this section, we provide a detailed explanation of IntraMix. Firstly, we present the Intra-Class Mixup in 3.1. It generates high-quality labeled nodes from low-quality data, addressing the issue of label sparsity. Then, we show the method for finding node neighbors 3.2. Next, in 3.3, we conclude the workflow and conduct complexity analysis in 3.4. The framework is shown in Figure 2.
3.1 Intra-Class Mixup
supervised learning, having more labels typically allows for learning finer classi- fication boundaries and getting better result [39]. However, obtaining accurately labeled data is costly in node classification. Nevertheless, directly utilizing low-quality labels from pseudo-labeling introduces noise detrimental to learning. As we know, low-quality pseudo-labeled data are often closer to boundaries that models can learn from current data, containing useful information for classification [21]. It is possible to generate high-quality data from them as mentioned in Sec 1. Due to the fact that label noise typically spread in multiple directions, we take full advantage of the directional nature of the noise. By blending data, make the noise distribution closer zero,
Motivation:

---

thereby reducing the noise in the labels. At the same time, considering that data generated by vallina Mixup is hard to find neighbors, we innovatively propose Intra-Class Mixup. It generates data with only single label, making it easy to determine the neighborhood. It not only generates high-quality data but also facilitates the finding of neighbors. Additionally, we can provide theoretical guarantees.
We use pseudo-labeling to transform the unlabeled nodes D., into nodes with low-quality labels Dr. Then, we get D Dr U Dy, where there are few high-quality and many low-quality labels. In contrast to the vanilla Mixup, which is performed between random samples, we perform Mixup among nodes with the same oow-uuality labels to obtain high-quality labeled data guaranteed by Theorem 3.1. The generated dataset is represented as:
Approach:
Dm = {(0 0) Mx bz); 1 = yı = ,)
where
MA 23) = Ar; + (1 2)z3, (1). (I.. E D.
The number of generated nodes is manually set. The labels in D... are of higher quality compared to D, a guarantee provided by Theorem 3.1. The proof can be found in Appendix 1. In other words, the generated labels exhibit less noise than those of their source nodes. Through Intra-Class Mixup, we obtain a dataset with high-quality labels, leading to improved performance of GNNs.
Assumption 3.1. Different classes of data have varying noise levels, i.e., Pmoise (y/ (z) = P(W+(r)+ + G.. where Paoise (y4[z) and P(y, (z:) represent the label distribution of class i with and without noise, and 4 ~ NO0 of) represent the noise.
Theorem 3.1. For Intra-Class Mixup satisfying Equation 2 and Assumption 3.1, P(ê < E) 2 ( + (1 - -1)-))3--3 b), and E(E)
F(e) = [X2 + (1 - 2} < L, where E(-) represents the expectation, and é and e denote the noise in the generated data and the original data, respectively.
3.2 Neighbor Selection
The strength of GNN lies in gathering information from neighborhoods to mine node features [14]. After generating node v in Sec 3.1, to leverage the advantages of GNN, it is necessary to find neighbors for u. We aim to construct neighborhood that satisfies two requirements: a). The neighborhood is suitable for v; b). The neighbors of u can obtain richer information through v. If is simply connected nodes that generated it, as the nodes used for Mixup mostly have low-quality labels, it is prone to resulting in incorrect information propagation. Since nodes of the same class are more likely to appear in the neighborhood in homogeneous graphs, natural idea to connect y with nodes of high confidence in the same class. In this way, we can find the correct neighbors for and, acting as a bridge, connect the neighbors of two nodes of the same class through obtain more information from the graph, as shown in Figure 1(b).
Motivation:
Approach: As mentioned above, neighborhood selection involves two steps. First, finding nodes highly likely to be of the same class as u, and second, determining how to connect v with these nodes. We will now introduce them separately in the following.
Finding nodes with a high probability of belonging to the same class can be transformed into the problem of finding high-quality labeled data. Then, we ingeniously design an ensemble method without extra training costs. We employ the GNN for pscudo-labeling to predict the label of nodes under dropout probabilities. Nodes consistently predicted in all n trials are considered high-quality. This is an ensemble method with n GNNs but without n training costs, significantly reducing cost. Details are in Appendix D.3. It is expressed as:
Dx {1,, 1) (x) =.. fn(),, E D),
where f. represents GNNs with different dropout probabilities. After obtaining the high-quality set DR. it is time to establish neighborhoods between D, and D,,, generated by Mixup. To ensure the correctness of neighbors, we adopt the way of randomly connecting the generated data to high-quality nodes of the same class. The augmented edge set É of the original set E can be expressed as:
= E U (e(t, (2) y) E Di, (x4, y) E Da
where e(a, b) represents an edge between nodes a and In this way, we not only find reasonable neighbors for the generated nodes but also establish an information exchange path between two nodes

---

Algorithm Workflow of IntraMix
Input: Graph G = EV, V can be divided into Dj and D.. Class of nodes C, GNN model
1: Generate pscudo labels for D. using f. get D.
2: D = Di U Du
3: Generate Mixup set Dm = {Vm, Em} as Equation.2
4: V= VU Vm
5: Generate high-quality set Dr according to Equation.4
6: for (G: 9) E Dm do
7: E' E fe(E, zi), x(f,,,,) where (z4/2j, 9) E Dr.
8: end for
Output: the augmented graph G = EV)
of the same class. Additionally, by not directly connecting the two nodes, potential noise impacts are avoided. The elimination effect of noise is guaranteed by Theorem 3.2. The detailed proof can be found in Appendix B.2. Through this method, the issue of missing neighborhoods in the graph is alleviated, and graph with richer structural information is constructed for downstream tasks.
Assumption 3.2. The label noise can be represented as node noise, i.e., Pnoise (2ly)) = P(x 8,, where 6; ~ (0, ).)). Equation simplifies to h MMLP + ) + [. EuEN, h k[11] where is learnable. m and are nodes from the i-th class, ~ P(xlv:), on ~ Proise (xlvz).
B(d) V(2++ +1 x)2) + 4(2+++ where 8
Theorem 3.2. In two-layer GNN, we have
E(d)
represents the noise impact directly connecting m and n and 8 is the impact through IntraMix.
B(3) The E(J] in Theorem 3.2 can be controlled be less than by adjusting the learnable 7). indicating that the neighbor selection method of IntraMix leads smaller noise impact. Therefore, Theorem 3.2 guarantees that the neighborhood selection strategy proposed by IntraMix can increase the richness of information in the graph while reducing the impact of noise.
3.3 Workflow
In this section, we introduce the overall workflow IntraMix. For details, please refer to Algorithm 1. The data augmentation begins by generating low-quality labels for unlabeled nodes through pseudo- labeling (lines I). Following that, high-quality labeled data is generated by Intra-Class Mixup. Subsequently, we use the neighborhood selection strategy to select appropriate neighbors for the generated nodes (lines 6-8). The output is graph that is better suited for downstream tasks.
3.4 Complexity Analysis
Overall, the time consumption of using IntraMix can be divided into four aspects: generating pseudo- labels for nodes, generating new nodes, neighborhood discovery, and the downstream task. Next, we will analyze the time complexity of each aspect separately.
In the pseudo-labe generation process, there is no additional training cost since the model used is the same GNN employed for downstream tasks. The second part of the time cost comes from the pseudo-labeling process, which only involves &N inference steps, where N represents the number of nodes selected for pseudo-labeling and k represents the number of pseudo-labeling is performed in parallel. The time cost for this step is minimal.
Next is the process of generating new nodes. Assuming the number of generated nodes is m, the time cost incurred during the Mixup generation is (()). Simultancously, the time cost for finding the neighborhood for these m nodes is also ((m). Next, we analyze the subsequent training time consumption of IntraMix. Assuming the original time complexity the GNN is O(VV x F F')
O x F*), where F denotes the input feature dimension of nodes, and F' is the hidden layer dimension of GNN. The time complexity after using IntraMix O(VV F x F') + O( x F') O(m x F x F') + O(2m x F') O(m). As in most cases, m & VV. the time complexity is in the same order of magnitude as the original GNN. Therefore, from an overall perspective, IntraMix does not introduce significant additional time cost to the original framework.
5

---

Table 1: Semi-supervised node classification accuracy(%) medium-scale graphs. The average
result of 30 runs is reported on five datasets.
Models
Strategy
Cora
CiteSeer
Pubmed
CS
Physies
Original
81.51 =
70.30 0.54
19.06:0....
91.24 0.43
92.56 L.31
GraphMix
82.29 3.71
74.55 4
$
91.90
90,43 1.76
CODA
83.47 03.3
73.48:0..2
7.35
91.01
92.57
DropMessage
0.35
0.25
0.31
9..74
GCN
MH-Aug
8.38
73.82
0.32
9.33
92.91 0.46
LA-GCN
74.70 8.557
8.77
93.26 0.26
NodeMixup
83.47 0.32
7..12
81.1
92.4
93.97
0.45
IntraMix
8.425
74,80
0.46
82.98 + 0.54
94.27 0.14
Original
0.662
71.82
0.83
7.700
90.52
91.97 =
GraphMix
8.676
7350
0.44
90.57
1.03
0.44
CODA
83.3
79.37 7.493
90.41 +
92.09 0.62
DropMessage
0.22
7.37
0.25
0.50
92.03 0.72
GAT
MH-Aug
8491
0.81
0.55
9.356
92.72
LA-GAT
73.71 0.45
0.44
0.35
73.42#0.44
NodeMixup
74.30 0.31
0.32
9..2
93.87 0.30
IntraMix
0.443
74.50 +: 0.24
8.32
9.24
94.12 - 0.24
Original
68.0 0.32
0.774
91.01 +
93.09 = 0.41
GraphMix
7..97 0.82
79.85 +
91.55
93.25 + 0.33
CODA
0.14
0.22
79.28
0.46
93.42 01.6
SAGE
MH-Aug
8.39
7
80.68 0.36
92.27 #
93.58 = 0.53
LA-SAGE
0.35
7.31
8.472
92.41 0.554
93.41 = 0.31
NodeMixup
81.93
0.59
94.76 + 0.25 91.97 0.24
IntraMix
84.72 0.34
74.37
8
92.80 + 0.26
94.87 + 0.04
Original
0053
0.61
0.57 7..67
92.36 # 0.8T
GraphMix
0.42
0.43
94.12 0.61 0.45
DropMessage
0.23
0.53
0.42
93.54 0.52
APPNP
MH-Aug
0.41
74.52
8.331
0.39
94.03 = 0.25
LA-APPNP
7 8..3
8.55
92.71
94.52 0.27
NodeMixup
2.31 0.45
0.12
9.22
94.34 + 0.22
IntraMix
85.99 0.48
75.25 + 0.42
81.96 0.34
93.24
94.79 = 0.14
4 Experiment
In this section, we show the excellent performance of IntraMix in both semi-supervised and full- supervised tasks with various GNNs across multiple datasets in Sec 4.1 and Sec 4.2. Sec 4.3 highlights the inductive learning ability of IntraMix while detailed ablation experiments for in-depth analysis presented in Sec 4.4. Additionally, we analyze how IntraMix overcomes over-smoothing in Sec 4.5 and evaluate IntraMix on heterophilic and heterogeneous graphs in Sec 4.6 and Sec 4.7, respectively.
4.1 Semi-supervised Learning
We evaluate IntraMix on commonly used medium-scale semi-supervised datasets for node classification, including Cora, CiteSeer, Pubmed [34), CS, and Physics [35]. We follow the original splits for these datasets. We also conduct semi-supervised experiments on large-scale graphs, including ogbn-arxiv [16] and Flickr [49]. To alter the original splits for full-supervised training on these datasets, we use 1% and 5% of the original training data for semi-supervised experiments, respectively. Details can be found in Appendix C.
Datasets:
Baselines: We utilize four popular GNNs: GCN [19], GAT [40], GraphSAGE (SAGE) [14], and APPNP [11]. Additionally, we compare IntraMix with various mainstream graph augmentation methods [42, 6, 7, 30, 24, 25]. Details of the baselines can found in Appendix C.2. For each graph augmentation applied to each GNN, use the same hyperparameters for fairness. When comparing with other methods, we use the settings from their open- source code and report the average results over 30 runs. All experiments
conducted on single NVIDIA RTX-3090.
Result: It is crucial to note that semi-supervised experiments are more important than full-supervised ones. This is primarily due to the sparse labels in most real-world graphs. The semi-supervised results reflect the method's potential when applied to real-world situations. Observing the results in Table 1, it is evident that IntraMix shows superior performance across almost all GNNs and datascts.

---

Table Semi- and full-supervised node classification accuracy on large-scale graphs. The average result of 10 runs is reported. Training size refers to the proportion of training data used for training.
Model
Strategy
ogbn-arxiv
Flickr 5%
Training Size
5%
100%
1%
100%
Original
62.99 + 1.01
68.65 + 0.31
71.74 4 0.29
46.02 = 1.25
48.50 + 0.49
51.88 + 0.41
FLAGG
63.68 + 0.91
0..44
72.04
0.220
46.524 0.77
0:46
52.05 0.16
GCN
LAGCN
64.09 + 0.65
19.6220.22
72.08 0.14
47.124 0.63
0.44
52.63 0.16
Modu
6.87
6.23
0..26
46.65# 1.66
0.21 0.56
IntraMix
64.84 0.38
7.12
7.221
48.18: 0.68
5.31
53.03 0.25
Original
0.94
6.475
0.11
45.88
1.23
0.53
49.88 0.32
FLAG
0.88
6.51
03.11
46.24 0.75
51.34 4..43
0.27
GAT
LAGAT
0.52
6.22
73.17=0.12
4.265
52.63 = 0.16
ModeMixup
64.26 0.47
70.05
0.324
47.02 1.29
49.05 0.61
$2.82 0.36
IntraMix
65.01 0.35
0.27
0.12
48.32 0.61
50.33
53,49 0.09
Original
6.88
68.42
48.65 4.12 71.49
50.47 0.21
FLAG
63.35
6.304
02.1
0.78
0.44
52.39 0.28
SAGE
LASAGE
64,26 0.557
69.93
0.13
47.33
50.82 + 0.38
54.24
ModeMixup
64.01 # 0.44
69.79 0.23
72.01 0.33
47.13
50.91 0.24
53.49 0.24
IntraMix
65.32 0.26
70.56 0.22
73.61 0.09
48.24 0.51
51.42 0.29
54.65 0.26
Additionally, Table shows that the semi-supervised results with 1% and 5% of the training data on large datasets also demonstrates excellent performance. This indicates that the IntraMix generation of high-quality labeled nodes and neighborhoods, enriches the knowledge on the graph, making the graph more conducive for GNNs. Moreover, it is noteworthy that IntraMix exhibits greater advantages on SAGE and APPNP. This is attributed to the neighbor sampling for message aggregation of SAGE and the customized message-passingg passing of APPNP, both of which prioritize the correct and richness of neighborhoods. The superiority on these two models further validates the rationality and richness of the neighborhoods constructed by IntraMix and the correctness of the generated nodes.
4.2 Full-supervised Learning
Datasets: To evaluate IntraMix full-supervised datasets, utilize the well-known egbn-arxiv and Flickr, following standard partitioning ways. Detailed information can be found in Appendix C.I.
Baselines: In this part, we consider three GNNs: GCN, GAT, and GraphSAGE. We compare IntraMix with various mainstream methods, and details about these methods can be found in C.2.
Results: The results in Table 2 show that IntraMix consistently outperforms all GNNs and datasets in full-supervised experiments, aligning with the outcomes in semi-supervised learning. Although graphs typically adhere to eeii-supervised settings, some graphs, like citation networks, have sufficient labels [34]. Thus, we conduct supervised experiments show that the generality of IntraMix. The success in full-supervised settings primarily demonstrates the effectiveness of our neighbor selection strategy, as the ample labeled data the training set reduces the influence of the high-quality labeled data generated by IntraMix. This further proves that our neighbor selection strategy constructs graph more conducive to downstream tasks by enriching the high-quality neighborhoods of nodes.
4.3 Inductive Learning
The experiments mentioned above are ducted transductive settings. In node-level tasks, the common setting is transductive, where the test distribution is known during training, fitting many static graphs. Inductive learning refers to not knowing the test distribution dur- ing training. Since many real-world graphs are dynamic, inductive learning is also crucial. To demonstrate the reliability of IntraMix induc- tive setups, we conduct experiments on Cora and CiteSeer, utilizing GraphSAGF and GAT. The results are presented in Table 3. In inductive learning, GNNs can only observe non-test data during training.
Table 3: Node Classification in inductive settings.
Models
Strategy
Cora
CiteSeer
Original
81.3 # 0.5
70.4
LAGAT
82.7 : 0.8
72.1 = 0.7
GAT
NodeMixup
71.8 0.5
IntraMix
72.9 0.6
0.6
Original
1.7
69.1
LAGSAGE
8..7
73.0 1.1
SAGE
NodeMixup
8.
73.1 1.3
IntraMix
82,9
73.9 0.8
7

---

Table 4: Ablation of Intra-Class Mixup on GCN. con is vallina mixup connection, and sim con is similar connection. f the improvement.
Table 5: Effectt of Neighbor Selection on GCN,
means improvement compared to the original, while indicates a reduction.
Strategy
Cora
CiteScer
Pubmed
Strategy
Cora
CiteSeer
Pubmed
Original
0.4
79.0 0.5
OriginalGGCh GCN 81.5 + 0.4 0.5
79.0 0.3
Only PL
82.9 0.2
79.5 0.3
0.2
Direct Con 83.6 2.1) 73.4 (t 3.1) 78.0 1.0)
Only UPS
0.4
79.7 0.6
0.4
Random Con 76.7 (L 4.8) 67.0 (1 3.3) 65.1 ( 13.9)
Mixup(w/o con)
58.9 + 22.3 52.3
17.6
70.0 10.8
Without Con
82.9 (f 1.4) 72.8 2:5) 79.4 0.4)
Mixup(w con)
83.0 + 1.2
71.3 3.5
7
Vallina Con 84.3 (1 2.8) 73.6 (1 3.3) 79.8 (1 0.8)
Mixup(sim con)
83.1 + 1.8
71.5 1.9
79.8 3.8
Similar Con
84.5 (1 3.0) 74.0 (1 3.7) 80.3 (1 1.3)
Intra-Class Mixup 85.2 (13.7) 74.8 (14.5) 82.9 (13.9)
IntraMix
85.2 (f 3.7) 74.8 (1 4.5) 82.9
From the results, it is evident that IntraMix also exhibits excellent performance in inductive learning settings. This strongly validates that the generated nodes with more high-quality labels and rich neighborhoods constructed by IntraMix indeed provide the graph with more information beneficial to downstream tasks. As a result, GNNs trained with IntraMix can learn more comprehensive patterns and make accurate predictions even for unseen nodes, confirming IntraMix as generalizable graph augmentation framework applicable to real-world scenarios.
4.4 Ablation Experiment
To demonstrate the effects of each IntraMix component, we conduct detailed ablation experiments using GCN on Cora, CiteSeer, and Pubmed. All other parts of IntraMix are kept unchanged except for the mentioned ablated components.
Firstly, we use a simple ex- periment show that part of the improvement is closely related to the high-quality data generated by Intra-Class Mixup. In Table 6, we replace the generated data with all-zero and all-one vectors and find that both perform worse than IntraMix. This indicates that the nodes generated by In- traMix are indeed helpful for downstream tasks.
Intra-Class Mixup:
Table 6: Explore the effect of generating node with Intra-Class Mixup. Zeros means replacing the generated nodes with an all zero vector, and Ones means replacing them with an all-one vector.
Strategy Original
Cora
CiteSeer
Pubmed
81.5 0 0.4
70.3 + 0.5
79.0 + 0.3
Ones Zeros
31.9 (1 49)
21.5 (J 48)
38.1 (L 40)
83.8 (1 2.3)
73.6 (1 3.3)
80.7 (f 1.7)
Then, we discuss the effectiveness of Intra- Class Mixup. We compare it with methods that do not use Mixup, relying solely on pseudo- labeling(PL), and introduce an advanced PL method called UPS [32]. Additionally, we compare Intra-Class Mixup with vallina Mixup, which employs various connection methods. The results are shown in Table 4. Among these methods, Intra-Class Mixup has the best performance, showing nearly 3.5% improvement in accuracy compared to the original GCN. This is because, compared to methods using only pseudo-labels, Intra-Class Mixup generates higher-quality labeled nodes, enabling GNNs to get more information useful for downstream tasks.
IntraMix
85.2 (13.7)
74.8 (14.5)
82.9 (13.9)
Regarding Mixup, we utilize three connecting methods: treating generated nodes as isolated (w/o con), connecting them with nodes used for generation (w con), and connecting them with nodes with similar embeddings (sim con). However, none of these methods perform well. As Theorem 3.1 suggests, Intra-Class Mixup ensures the improvement of label quality for each class, a guarantee that Mixup cannot provide. Furthermore, the fact that Intra-Class Mixup data have single label makes it convenient to select similar neighbors. In contrast, Mixup generates data with mixed labels, introducing the risk of connecting to any class of node and potentially causing errors in propagation. This is key reason for the poor performance of Mixup in node classification.
This part shows the importance of Neighbor Selection. We compare various selection methods in Table 5. We observe that these methods are less effective than IntraMix. Direct con indicates connecting the generated data to low-quality labeled nodes of the same class, and its poor performance proves the necessity of our proposed approach to finding high-quality nodes of the same class as neighboring nodes. The experimental results validate Theorem 3.2.
Neighbor Selection:
Compared to other neighbor selection methods, IntraMix proposes a simple way to select nodes more likely to serve neighbors, leading to more accurate message passing. Among the methods,
8

---

01
Loep Radi
060
(14
10.3
Acning
U6
Arcnnay
150-
Artuaayya
00
90-
74
Pulaned
Cltefioe
0.4
Cora
CiteSerr
Pubnudd
(a) Utilization of unlaheled data
(b) Sensitivity analysis of A
(c) Pseudo-label quality analysis
Figure 3: a) Experimental results using different proportions of unlabeled nodes show that perfor- mance improves as more unlabeled nodes are utilized. b) Sensitivity analysis of À indicates that the best performance achieved when À 0.5. c) Analysis with low-quality pseudo-labels. The model from the previous step is used for pseudo-labeling in the next step.
Vallina Con indicates connecting generated nodes to the nodes used for generation. Similar Con (SC) denotes connecting the nodes to nodes with similar embeddings. SC performs great, highlighting the importance of selecting similar nodes as neighbors, aligning with our intuition. However, SC is not as good as IntraMix, mainly because the initial neighbors for generated nodes are empty, making it hard to provide accurate embeddings for similarity mcasurement. What's more, connecting overly similar nodes resulted in insufficient information. In comparison, IntraMix connects nodes with the same label, maintaining neighborhood correctness while connecting nodes that are not extremely similar. In Table 6, using all-zero vector eliminate the influence of Mixup still shows improvement. This reflects the rationality of our neighbor selection method, which is effective for graphs.
Utilization of unlabeled data: In this part, we show the importance of using unlabeled nodes to obtain low-quality data, and the results are shown in Figure 3(a). Even though Mixup can augment the label information to some extent, the insufficient nodes used for generation create bottleneck in information gain, hindering GNNs from learning enough knowledge. Despite the labels provided by eseudo-labeling for unlabeled data being low-quality, Intra-Class Mixup enhances the label quality, thus providing GNNs with ample knowledge.
Sensitivity Analysis of X: This part discusses the impact of in Intra-Class Mixup. The experiment conducted using GCN on Cora, and details are presented in Figure 3 (b). According to Theorem 3.1, the best noise reduction in each class label is achieved when X 0.5. The results validate our theoretical analysis, showing that the performance of GCN gradually improves as varies from to 0.5. Therefore, we choose X ~ B2 2), where B denotes Beta Distribution.
Analysis of pseudo-label quality: In this part we discuss the performance of IntraMix when the quality of pscudo-labels is extremely low. This situation may occur when the initial labeled nodes are extremely sparse. We use 5% of the semi-supervised training dataset for training. As shown in Figure 3 (c), we find that when the pseudo-label quality is low, IntraMix can effectively improve performance. Additionally, we use the model trained in the previous step for the next labuein....ling. This iterative method provides way to enhance the performance of IntraMix on low tow-quality data. In summary, IntraMix effectively enriches the knowledge with extremely low low-quality pseudo-labels.
4.5
Over-smoothing Analysis
As is well known, deep GNNs may result in over-smoothing, phenomenon characterized by the convergence of node embeddings. We show the ability of IntraMix to alleviate over-smoothing in Figure 4(a). We use MADgap [3] as the metric, where larger MADgap indicates a milder over- smoothing. Surprisingly. although IntraMix is not specifically designed to address over-smoothing, it shows strong ability counteract smoothing. reaching a level similar to GRAND [9], method specialized in handling over-smoothing. This is attributed to the bridging effect of the generated nodes, connecting nodes of the same class with high confidence resembles random information propagation, providing effective resistance against over-smoothing. Additionally, the richer neighbors and node features generated by IntraMix inherently mitigate smor-smoo [17]. The detailed discussion can be found in Appendix D.I.
random manner. This process

---

08
077
90
96
Acturayyii)
04-
GLN
113
GAT
GOgRAAGE
GRAND
Carrdd
Whearein
Squtrre
ma0He micreff
Layer
(a) Ovor-shog Analysis
(b) Heterophilic Graphs Analysis (c) Heterogeneous Graphs Analysis
Figure 4: a) Analysis reveals that IntraMix shows effective capabilities in overcoming wer-ssoothing with deep GNNs. b) Evaluation on heterophilic graphs. c) Evaluation on heterogeneous graphs.
4.6 Evaluation on Heterophilic Graphs
In this section, we analyze the performance of IntraMix heterophilic graphs on the Cornell, Texas and Wisconsin datasets [4]. Although the neighbor selection utilizes the neighborhood assumption, find from the results in Figure 4(b) that IntraMix can also enhance GNN on heterophilic graphs. This is because, despite the cxisting connections heterophilic graphs tending to link different types of nodes, they do not exclude connections between similar nodes. The connections between high- quality nodes generated by IntraMix can increase the information on the graph, thereby improving the performance of GNN. More detailed discussion is in Appendix D.2.
4.7 Evaluation on Heterogeneous Graphs
In this section, we discuss the performance of IntraMix heterogeneous graphs. In this setting, neighboring nodes may belong to different types entities. For example, different papers can be linked through authors, but there is no direct link between them. This is common graph configuration. use SeHGNN[ 54] as the base model and incorporate IntraMix to conduct experiments on the IMDB [47] and DBLP [38] datasets. The results are shown in Figure 4(c). IntraMix also improves performance in heterogeneous graphs, highlighting its versatility.
5 Related Work
The primary purpose of graph augmentation to address two common challenges graphs encountered by GNN, scarcity of labels and incomplete neighborhoods [5]. Graph augmentation can be categorized into Node Manipulation [42]. Edge Manipulation [33], Feature Manipulation [8], and Subgraph Manipulation [31]. However, existing methods either require complex generators [24] or extensive empirical involvemen [44], failing to effectively address the two issues. The proposed IntraMix offers a simple solution to simultaneously tackle the two challenges faced by GNNs. Details about the related augmentation methods can be found in Appendix E.
Graph Augmentation:
Mixup is promising data augmentation medthod [50], enhancing the generalization of various tasks [41, 37]. However, there has been limited focus on the application in node classification on graphs. We address the shortcomings of vallina Mixup in node classification, proposing IntraMix. IntraMix provides richer information for graphs, improving GNNs node classification. Details about the related Mixup works can be found in Appendix E.2.
Mixup:
Conclusion
This paper presents IntraMix, an elegant graph augmentation method for node classification. We utilize Intra- Class Mixup to generate high-quality labels to address the issue of sparse high-quality labels. To address the problem limited neighborhoods, we connect the generated nodes with nodes that are highly likely from the same class. IntraMix provides elegant solution to the dual challenges faced by graphs. Moreover, IntraMix is flexible method that can be applied to all GNNs. Future work will focus exploring neighbor selection methods to construct more realistic graphs.
10

---

Acknowledgements
This work supported by National Natural Science Foundation of China (NSFC) (62232005, 62202126); the National Key Research and Development Program of China (2021 YFB330000)))
References
[1] Christopher Beckham, Sina Honari, Vikas Verma, Alex M Lamb, Farnoosh Ghadiri, R Devon Hjelm, Yoshua Bengio, and Chris Pal. On adversarial mixup resynthesis. Advances in neural information processing systems, 32, 2019.
[2] Luigi Carratino, Moustapha Cissé, Rodolphe Jenatton, and Jean-Philippe Vert. On mixup regularization. The Journal of Machine Learning Research, 23(1):14632 146114466666622,011-111111114441 2022.
[3] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI conference artificial intelligence, volume 34, pages 3438-3445, 2020.
[4] Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam, and Scán Slattery. Learning to extract symbolic knowledge from the world wide web, AAAI/AAAI, 3(3.6):2, 1998.
[5] Kaize Ding, Zhe Xu, Hanghang Tong. and Huan Liu. Data augmentation for deep graph learning: A survey. ACM SIGKDD Explorations Newsletter, 24(2):61-77, 2022.
[6] Rui Duan, Chungang Yan, Junli Wang, and Changjun Jiang. Class-homophilic- data augmentation for improving graph neural networks. Knowledge- Systems, 269:1 10518, 2023.
[7] Taoran Fang. Zhiqing Xiao, Chunping Wang, Jiarong Xu, Xuan Yang, and Yang Yang. Dropmes- sage:
Unifying random dropping for graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 4267-4275, 2023.
[8] Fuli Feng, Xiangnan He, Jie Tang, and Tat-Seng Chua. Graph adversarial training: Dynamically regularizing based on graph structure. IEEE Transactions on Knowledge and Data Engineering. 33(6):2493-25 2504, 2019.
[9] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092-22103, 2020.
[10] Benoît Frénay and Michel Verleysen. Classification in the presence of label noise: a survey. IEEE transactions neural networks and learning systems, 25(5))845 8499 2013.
[11] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification graphs. In International Conference on Learning Representutions, 2019.
[12] Hongyu Guo and Yongyi Mao. ifmixup: Towards intrusion-free graph mixup for graph classification. arXiv e-prints, pages arXiv-2110, 2021.
[13] Hongyu Guo, Yongyi Mao, and Richong Zhang. Mixup as locally linear out-of-manifold regularization. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 3714-3722 2019.
[14] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances neural information processing systems, 30, 2017.
[15] Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference on Machine Learning, pages 0230-8248. PMLR, 2022.
11

---

[16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 13:22118-22216 2020.
[17] Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35:2268- 22811, 2022.
[18] Jang-Hyun Kim, Wonho Choo, and Hyun Oh Song. Puzzle mix: Exploiting saliency and local statisties for optimal mixup. In International Conference on Muchine Learning, pages 5275-5285 PMLR, 2020.
[19] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[20] Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Robust optimization as data augmentation for large-scale graphs. In 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 60 69,69, 2022.
[21] Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, volume 3, page 896, Atlanta, 2013.
[22] Fred C Leone, Lloyd S Nelson, and RB Nottingham. The folded normal distribution. Techno- metrics, 3(4):543-555 550, 1961.
[23] Junnan Li, Richard Socher, and Steven C.H. Hoi. Dividemix: Learning with noisy labels as semi-supervised learning. In International Conference on Learning Representations, 2020.
[24] Songtao Liu, Rex Ying. Hanze Dong, Lanqing Li, Tingyang Xu, Yu Rong, Peilin Zhao, Junzhou Huang, and Dinghao Wu. Local augmentation for graph neural networks. In International Conference on Machine Learning, pages 14054-14072. PMLR, 2022.
[25] Weigang Lu, Ziyu Guan, Wei Zhao, and Long Jin. Nodemixup: Tackling under-reaching for graph neural networks. arXiv preprint arXiv:2312.13032. 2023.
[26] Michal Lukasik, Srinadh Bhojanapalli, Aditya Menon, and Sanjiv Kumar. Does label smoothing mitigate label noise? In International Conference on Machine Learning, pages 6448-6458 PMLR, 2020.
[27] Linghui Meng, Jin Xu, Xu Tan, Jindong Wang. Tao Qin, and Bo Xu. Mixspeech: Data augmentation for low-resource automatic speech recognition. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7008- 7012. IEEE, 2021.
(28) Rafael Müller, Simon Kornblith, and Geoffrey E. Hinton. When does label smoothing help? Advances in neural information processing systems, 32, 2019.
[29] Khang Nguyen, Nong Minh Hieu, Vinh Due Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using ollivier-ricci curvature. In International Conference on Machine Learning, pages 25956-25979. PMLR, 2023.
[30] Hyconjin Park, Seunghun Lee, Sihyeon Kim, Jinyoung Park, Jisu Jeong, Kyung-Min Kim, Jung-Wop Woo Ha, and Hyunwoo Kim. Mctropolis hastingss data augmentation for graph neural networks. Advances Neural Information Processing Systems, 34:19010-19020, 2021.
[31] Joonhyung Park, Hajin Shim, and Eunho Yang. Graph transplant: Node saliency-guiee guided graph mixup with local structure preservation. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 7966-7974, 2022.
[32] Mamshad Nayeem Rizve, Kevin Duarte, Yogesh S Rawat, and Mubarak Shah. In defense of pseudo-labeling: An uncertainty-aware pseudo-label selection framework for semi-supervised learning. In International Conference on Learning Representations, 2021.
12

---

[33] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
[34] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al Magazine, page 93, Jul 2017.
[35] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:/811.05860 2018.
[36] Jy-yong Sohn, Liang Shang, Hongxu Chen, Jaekyun Moon, Dimitris Papailiopoulos, and Kangwook Lee. Genlabel: Mixup relabeling using generative models. arXiv preprint arXiv:2201.02354 2022.
[37] Lichao Sun, Congying Xia, Wenpeng Yin, Tingting Liang, Philip Yu, and Lifang He. Mixup- transformer: Dynamic data augmentation for NLP tasks. In Donia Scott, Nuria Bel, and Chengqing Zong, editors, Proceedings of the 28th International Conference on Computa- tional Linguistics, pages 3436-3440, Barcelona, Spain (Online), December 2020, International Committee on Computational Linguistics.
[38] Jie Tang, Jing Zhang. Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 990-998, 2008
[39] Jesper Van Engelen and Holger H Hoos. A survey on semi-supervised learning. Machine learning, 109(2):373-44,, 2020.
[40] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[41] Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez- Paz, and Yoshua Bengio. Manifold mixup: Better representations by interpolating hidden states. In International conference on machine learning, pages 6438-6447. PMLR, 2019.
[42] 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, volume 35, pages 10024-10032, 2021.
[43] Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. Proceedings of the Web Conference 2021, pages 3663-3674, 2021.
[44] 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, pages 207-217, 2020.
[45] Lirong Wu, Jun Xia, Zhangyang Gao, Haitao Lin, Cheng Tan, and Stan Z. Li. Graphmixup: Improving class-imbalanced node classification by reinforcement mixup and self-supervised context prediction. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2022, Grenoble, France, September 19-23, 2022, Proceedings, Part IV. page 519-535, Berlin, Heidelberg, 2023. Springer-Verlag.
[46] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27400 2022.
[47] Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
[48] Jaemin Yoo, Sooyeon Shim, and Kang. agdel-ae augmentation for accurate graph classification. In Proceedings of the ACM Web Conference 2022, pages 1281-1291, 2022.
13

---

[49] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
[50] Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. International Conference on Learning Representations. 2018.
[51] 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 artificial intelligence, volume 35, pages 1015-11023, 2021.
[52] 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.
[53] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
[54] Dongcheng Zou, Hao Peng, Xiang Huang, Renyu Yang. Jianxin Li, Jia Wu, Chunyang Liu, and Philip Yu. Se-gsl: A general and effective graph structure learning framework through structural entropy optimization. In Proceedings of the ACM Web Conference 2023, pages 499-510, 2023.
14

---

A Notations
We first list the notations for key concepts in our paper.
Table 7: Notations
Notations
Descriptions
A graph.
The set of nodes in a graph.
A
The graph adjacency matrix.
The set of edges in graph.
X
Raxd
The feature matrix of nodes in the graph. The labels of nodes in the graph.
Y E Roxe
Dr
The set of nodes with labels at begining. The set of nodes without labels at begining.
Du
Dp
The set of nodes with low-quaility labels.
Dp
The set of nodes with high-quaility labels.
Dm
The set of nodes generated by Intra-Class Mixup. The set of nodes for training.
Dr
N
The neighbors a node u.
hy
The hidden feature vector of node
n
The number nodes The number of edges The number of node categories.
B Proofs
B.1 Theorem 3.1
In this part, we will prove Theorem 3.1. We will start by introducing the notation used the proof.
B.1.1 Notation and preliminaries
The capegory-specific noise is represented as:
Pnoize (Belx) P()((x) +
(6)
where E; N0, of)-
For simplification of the solution, the expression involving the label matrix transfer [28].
denoted as (x, y) ~ Q. And get the noise label matrix transfer as:
Qnoise
T
(7)
where Tw represents the probability, under the influence of noise, that data with the true label is mislabeled as y'.
And T can be represented as
= -1- -1- f(e)J
(8)
Here, c 6 ((0 [ represents the noise for each class, denotes the diagonal matrix, and represents the matrix of all ones. Therefore, f(e). is the noise matrix, and the purpose of f is to control the range of noise. It satisfies three properties: 1).0 < f(x) < f). exhibits the same monotonicity |z]: fx) ) + f(v)= f(x +):
Satisfying property is essential because, in Equation 8, f used to control the range of noise, and probabilities represented by matrix entries should remain within the meaningful range of [0, 1).
Satisfying property due to the representation in Equation where |e:| represents the magnitude of the deviation from the correct distribution, indicating larger noise for greater magnitudes. The positive or negative sign of e; indicates the direction of the noise, but in Equation 8, this directionality not explicitly represented. Therefore, using the absolute value captures the magnitude of noise.
15

---

Satisfying property 3 is because the noise in Equation 6 has directionality, two noises may cancel each other out due to opposite directions. When represented using Equation considering the directional of noise, operations need to be performed first, which might lead to cancellation due to different directions. Afterward, applying f is necessary to ensure the result falls within the (0, 1) range, adhering to the definition of probabilities. For simplicity, we assume that f directly satisfies property 3.
B.1.2 Details of proof
When we use Intra-Class Mixup, According to Equation 6, the distribution of labels for the generated data by Intra-class Mixup can be expressed as:
Pmntro (y, [+) X(P(). + +,) + +1 A)(P(u| + +
(9)
where 6, ~ (0, 0f),4 ~ ((0, d. and å represents the generated sample.
According to the definition of Intra-class Mixup and equation 8, the label transition matrix for the results of Intra-class Mixup can be expressed as:
T Tintra- (1 s(Ye + (1 1)62)) s(Aei + -1- X
(10)
where 61 = (& ~ NO0, !- and 62 = {e; ~ o(0,
The measurement of noise in T and Tixtra is essentially comparing f() with f(A; + (1 - A)e2).
According to property satisfied by f. this can be transformed into comparing |e| with [Xe + (1 A)r2|. A larger value in this comparison indicates greater noise. For the i-th class label, it is calculation of:
P(Ac1 + (1 A)G22 < (G))
(11)
where 6 ~ N(0, of), G, 611, 62 are independent and identically distributed variables, and |e| follows the folded normal distribution [22], let X² (1 2)2, have:
+00 22
+00
v2
2
P(Dea + (1 A)ez) < |(e))
=
20
c
26to
dy)
TTo
50
VTco,
2
to
22
22 dedu
== m2
TCC
J
M=rco50
2
1 1=42 v sin' dr
re
V=rsin9
TC
2
1
c
(12)
c2) ssin² d0
+ (1
1=tnn
2c
²² dt
1
arctam
arctan (X2 + (1 x)3)) >.5 0.5
π
Proof completed. This establishes that the likelihood of improving label quality after Intra-Class
Mixup for each class is greater than 0.5, demonstrating its effectiveness in enhancing label quality.
Next, let's consider the expectation of noise, which can be equivalently expressed in terms of the expectation |e]. Then we have:
+oc
B(Aen + (1 - A)Ex2)
=
dx e
2
J0
v TTO;
V200,
too
we
du
(13)
V
V20;
Vi
16

---

Similarly, we have: B((e,))
1/2
vir
Therefore, the ratio of the expected noise after Intra-Class Mixup to the original noise in class i is given by:
E(f(Ae + (1- ()6,2) E( +(1 A)62)l + E(les))
(14)
B(S(e:))
This implies that the expected noise each class reduced after Intra-Class Mixup.
When we use Vallina Mixup, i.e., performing Mixup randomly between samples, can be expressed according the derivation in [2] and Equation 8 as follows:
T Tixzup (1 f(1e + (1 A)E) + f( + (1 J
(15)
where E
[C1
1 EESLE Ex.
Then, following similar derivations of Equation 12, let 02 = v xPPo + (1- (1-1) σ =
Ss we have:
+00
+00
v2
x²
P([AG + (1 2)S < (c))
202
e
20 dy dz
VTOa
0
VTCo,
(16)
2
orctan
π
120 + +11 +1- +1-
The Equation 16 cannot guarantee that is greater than 0.5 for all Ø₁. This implics that although Vallina Mixup acts form of regularization during training, implicitly introducing data denois- ing [50], it does not ensure label quality improvement for every class. In this regard, it has limitations compared to proposed Intra-Class Mixup.
B.2 Theorem 3.2
In this section, we will prove Theorem 3.2. We will begin by introducing the notation used in the proof process.
B.2.1
Notation and preliminaries
In the proof of this section, the labeling noise in Equation 6 is transformed into equivalent node feature noise as follows:
Proise (2|y4 P(zly,) + 8,
(17)
where 6 NNO, o.)). The equivalence proof with Equation 6 is follows:
P(r)
Pnoise (2l Pnoise(ys1a))
P(y.)
(18)
P(x)
P(zlu) P(u(2))
P(t))
Therefore, from Equation 17, we have:
Proisee (x (xlvs) P Pnoise (yil P(x)
P(v:)
(P())) + <z) P(x)
P(ys)
(19)
= -P((llv:) P(v))
P(x)
+ 6:)
P(x)
P(vs)
P(xly)) + P(x)
P(y.)
17

---

Piz) is constant related to the dataset. Thus, the equation P ( = P(xlus) + 6; holds, p(.))
where 6, ~ (O, 2.) The equivalence between label noise and feature noise holds.
In this section, for the sake of convenience in derivation, the information propagation formula of the GNN in Equation 1 the k-th layer is simplified to:
h = MT.P*(( mh )
Σ NEN.
(20)
N
Where b. is used to represent the feature representation of node at the k-thh layer, Ths represents the learnable variable at the k-th layer, N,, denotes the set of neighboring nodes of node v. W₂ can be used to represent the parameter matrix of the MLP in the k-th layer of the GNN, and by represents the bias term of the MLP in the k-th layer.
In this part, consider two nodes m and n, both belonging to class yi under high-confidence labeling. Node has node feature F. following the distribution P(x y:), while the node feature nn of node n follows the distribution Pnoise ly:) We have:
P( (v:) = P(xnlue) = nosse Croise(x (zlvs) = P(rlys) + 6;
(21)
For convenience in derivation, without loss of generality, we can assume that and n have no neighbors in their initial states. We will prove that in a two-layer GNN: 1). By the approach proposed through IntraMix, connecting m and through the node (ś, yt) generated by Intra-Class Mixup. 2). Connecting nodes m and n directly. The ratio of the expected impact of n's noise on m in case 1) to the expected noise impact in case can be controlled to be less than 1 by adjusting learnable Therefore, the connection approach in IntraMix can to some extent overcome the potential noise disturbance that may exist when connecting high-quality labeled nodes directly.
B.2.2 Details of proof
When connecting nodes m and n directly, we have:
P(h (1s)) W1[(1 + P(5 P(zn ww:] + bj
(22)
+ 5c] bi
Similarly, we have:
P( w:) wi [ + (m) -)) (1 + m )o:] + b Then, after the second-layer message passing, node m can be represented as:
(23)
phh 1y:)
Wi[(1+ + 12) P(h [y:)]
(<)l)))) + 6,] + b.] )o.] + bbb +
=
Wi + (m)
Wo((2 +
W1 + (2 + m2)b1 + 62
(24)
value
W2 1/ + 12)
noise
When connecting through Intra-Class Mixup with the node v, we have:
According to Equation 17 and Equation 10, the feature distribution of the node u generated by Intra-Class Mixup satisfies P(oly.) = P(rly:) + 8% where 8% N(0, (X2 + (1 o)
Following the same reasoning as above, we have:
P P((m)ll))) W [1 + 7)) + P()lu)) + b1
= W, [2[ + mp) by
P'(hhllx)) = Wi((2++))P()w) (1 m1)6.] + bi
(25)
P'(N(lBz) = Wi[( +m)))()))))) pM (w:) + P(1 % w::]] + bn
- 5. +
1
=wi (2 [2 + 8
2
18

---

Then, after the second-layer message passing, can be represented as:
Pl(h (u) = =Wi(1 + -W 8. (1
= W2((1 + +2) [2] + bb]
+ WG ())p())))) 5,] + b1} b2
W22(( +2) Wi)P((ll)) + (2 m2)b1 bb
(26)
value
+ [2 m + 72)6 64]
noise
Assuming the parameters of MLP are the same, the value parts of Equation 24 and Equation 26 are the same. Now, what needs to compared is the ratio the expected values of the noise parts the two equations. Similar to property 3 mentioned in Sec B.I.I, when comparing noise expectations, absolute values should be considered. That is, the farther the noise from the 0, the larger it is, and the sign indicates the direction. Let noisem and noise,, represent the noise terms in Equation 24 and Equation 26, respectively. We have:
E(noisem
E + 11 + 72) + f
(27)
E(noisem))
E(1(2 + 12)
Similar to the derivation in Equation 13, we have:
(2 + 7n + 12)6; V2(2 + 171 + m2)
V
(28)
V20 / + (2 m (2)(((+((1))))
E[[(2 + m + 72)0 + 5/13
Then, Equation 27 can be represented
Ennoisemm)
(12 + (1 - X)2)
(29)
E(noisem)
4(2 + 77 + 172)
As h and 7/2 are learnable parameters, by controlling them, the value of Equation 29 can be made less than 1. This indicates that connecting nodes obtained through Aitra-Class Mixup leads to smaller noise compared to directly connecting them.
C Reproducibility
In this section, we present detailed information about the datasets used in the experiments, including the split method. Additionally, we provide a thorough introduction the comparative methods and the setups of GNNs in the experiments.
C.1 Datasets
In this part, introduce the datasets used in this paper. Detailed information can be found in Table 8.
We utilize five medium-scale datasets in a cuniviuperviee setting: Cora, CiteSeer, Pubmed [34], CS, and Physics [35]. All five datasets are related to citation networks. The first three datasets are standard citation datasets, where nodes represent papers, edges between nodes indicate citation relationships between papers, and node features are constructed by extracting key information from the papers, such as a one-hot vector indicating the presence of specific words in the paper. Node classification these three datasets involves assigning papers to their respective categories. During the dataset split process, we follow the standard partitioning method outlined in the literature [34], using a minimal amount of samples for training adhere the semi-supervised configuration.
On the other hand, CS and Physies datasets represent datasets related to collaboration among researchers. In these datasets, each node represents researcher, and edges denote collaborative
19

---

Table 8: Data statistics
Category
Name
Graphs
Nodes
Edges
Fcatures
Classes
Split Ratio
Metric
Cora
2,708
5,429
1,433
7
8.5/30.5/61
Accuracy
CiteSeer
I
3,327
4,732
3,703
7,4/30.9/61.
Accuracy
Seni--Spervised
Pubmed
I
19,717
44,338
500
3.8/32. 1/64.1
Accuracy
CS
I
18,333
163,788
6,805
15
1.6/2.4/96
Accuracy
Physics
I
34,493
495,924
8,415
5
0.28/0,43/99.2
Accuracy
Full-Supervised
ogbn-arxiv
I
169,343
1.166,243
128
40
54/18/23
Accuracy
Flickr
1
89,250
899,756
500
7
50/25/25
Accuracy
relationships between researchers in co-authored papers. Node features capture partial characteristics of researchers' papers. The process of node classification involves assigning researchers to their respective research directions. During the dataset split process, we follow the standard partitioning method [35], randomly selecting 20 samples from each class as training samples and using 1000 samples in total for the training to meet the semi-supervised configuration.
We also use two large-scale datasets for semi- uumi-supereieed and full sull-super training: ogbn-arxiv [16] and Flickr [49]. Their traditional splits are suitable for full-supervised training, while in the semi-supervised configuration, we used 5 5% and 10% of the original training data to simulate the semi-supervised setting. The ogbn-arxiv is a dataset of the ogh standard dataset, where each node represents an Arxiv paper, and directed edges indicate citations between papers. Each paper is associated with 128-dimensional feature vector obtained by averaging embeddings of words in the title and abstract. The classification task involves predicting the primary category of Arxiv papers, constituting 40-class classification problem. The dataset partitioning follows the original paper [16], with papers published until 2017 serving as the training set, paperss published in 2018 8 as the validation set, and papers published after 2019 as the test set. Unlike the limited training set in semi semi-supprrvied learning, the training set here is relatively larger.
On the other hand, Flickr is constructed by forming links between shared public images on Flickr. Each node in the graph represents an image uploaded to Flickr. two images share certain attributes (e.g., the same geographic location, the same gallery, comments posted by the same user), there is an edge between the nodes representing these two images. The dataset is collected from various sources, and images are represented using SiFTT-xtracted features. A 500-dimensional bag-of- coof-visul-wworr wordds representation from NUS-wide serves as the node feature. For labels, the paper [49] scans 81 tags for each image and manually merges them into categories. Each image belongs one of the 7 categories. The dataset partitioning follows the approach proposed in the paper [49], with 50% of the nodes as the training set, 25% as the validation set, and 25% as the test set.
C.2 Baselines
This section introduces the methods compared in the experiments. For the fairness of the experi- ments, we maintain consistent GNN structures when testing different augmentation methods. The configurations of GNNs are kept consistent with those described in [24]. We introduce several data augmentation methods compared in this paper:
GraphMix [42]: This is an effective exploration of using the Mixup method in graphs, attempting to perform Mixup in the hidden layer outputs of GNN to mitigate the impact of the topological structure of graphs on the Mixup. However, it overlooks the core issue we analyzed regarding Mixup on graphs: the inability to determine neighborhood relationships. The method used in this paper connects the generated sample with the samples used for generation, resulting in poor performance and only addressing the issue of missing high-quality nodes.
CODA [6]: The paper proposes to extract all nodes of the same class to generate a dense graph for each class, using dense graphs of each class as generated graphs. However, this approach simplifies the topological relationships on the graph, as not every node of the same class can appear as neighbors. Connecting each node of the same class makes the neighborhood very rich, but it leads to excessive message transfer that should not occur, resulting in poor performance.
FLAG [20]: This is a data augmentation method that uses advertisal learnable noise perturbations, quite effective on large graphs. incorporates learnable noise into node features and optimizes GNN training by finding the most challenging noise in each iteration. However, inevitably, it requires
20

---

fine-tuning between the magnitude of noise and its effectiveness in training, which can ultimately lead to noise being either too small or too large, both hindering learning. Moreover, it only addresses the issue of missing high-quality nodes.
DropMessage [7]: In this method, random dropout of information during message passing is considered, representing a unified form for drop node/drop edge-like strategies. However, as analyzed in the paper, this strategy is overly simplistic and fails to adapt well to graph augmentation tasks that require nuanced operations, resulting in poor performance.
MH-Aug [30]: This approach formulates target distribution based on the existing graph, samples series of augmented graphs from the distribution using a sampling method proposed in the paper. and trains using consistency approach. However, this method introduces certain prior knowledge, which may lead to suboptimal generalization.
GRAND [9]: Strictly speaking, this is not a data augmentation method, but it shares some similarities in terms of ideas. Grand randomly propagates information on the graph, significantly mitigating issues like over-smoothing. While it presents a novel solution, the strategy used is overly simplistic and requires further optimization based on dataset characteristics to achieve better performance. Additionally, it only addresses the problem of neighborhood deficiency.
Local Augmentation [24]: This method employs the conditional variational autoencoder (CVAE) as the generator to learn information about neighborhoods and generates features for nodes with sparse neighbors to compensate for the lack of information that cannot be obtained from the neighborhood, therehy obtaining better node representations for classification. This approach incurs a training cost. for the generator and only addresses the issue of missing high-quality nodes.
NodeMixup [25]: This is an exploratory approach to Mixup on graphs. However, it faces the challenge of not proposing an elegant and concise graph Mixup method. It focuses more on accurately determining node similarity to perform Mixup on similar nodes. The issue arises from the fact that the generated samples are excessively similar each other, resulting in generated samples being relatively similar to their parent samples. Generated samples that are overly similar to the original samples fail to provide sufficient information gain. We will provide detailed explanation in See E. Additionally, NodeMixup only addresses the issue of missing high-quality nodes.
In summary, existing methods often address only one aspect of the two challenges faced by graph data, failing to effectively solve the graph data augmentation problem. In contrast, our proposed method, IntraMix, presents concise yet powerful solution that efficiently tackles both challenges, making it a highly promising approach.
D More Discussions and Future Directions
In this section, we explain some analyses in the main text and introduce future research directions.
D.1 Over-smoothing Analysis
We further analyze the ability of IntraMix to resist over-smoothing. Over-smoothing results in the embeddings of different nodes on the graph become too similar, making it difficult for GNNs to distinguish between node classes based on the output layer. As the depth of the GNN increases, over-smoothing tends to worsen because deeper GNNs use broader range of neighbors for each node's embedding process, leading to excessive overlap in the neighborhoods and resulting in very similar node embeddings [3]. However, an interesting phenomenon is that within certain range, increasing the depth of the GNN does not reduce MADGap. This is because deeper GNNs have enhanced representational power, which can produce more distinct embeddings for each node despite the increased depth [29].
IntraMix is particularly impressive in its ability to resist over- over-smoothing to some extent. We attribute this phenomenon to two main reasons. First, IntraMix generates large number of accurately labeled nodes, providing each node with numerous accurate neighbors. For any given node, richer neighborhood naturally helps counteract over-smoothing [17]. Second, it is important to note that we use a random connection strategy during neighborhood selection. This means that nodes which might be far apart in the original graph can become connected through the generated nodes, bridging two neighborhoods that have some commonalities but are not very similar. This enriches the neighborhood
21

---

information and reduces the impact of over-smoothing. The second reason is somewhat similar to why GRAND [9] performs well in resisting over-smoothing.
D.2 Evaluation on heterophilic graphs
In this part, we analyze the effectiveness of IntraMix in heterophilic graphs. Despite the assumption we use when finding neighbors, which is that nodes of the same class are more likely to appear in the neighborhood, contradicting the nature of heterophilic graphs, the results from Figure 4(b) show that IntraMix still enhances GNN performance in heterophilic graphs. This is because, although the inherent connectivity in heterophilic graphs tends to favor connections between nodes of the different classes, it does not exclude connections between nodes of the same class. Therefore, connections between nodes of the same class can also enrich the information of the graph. In other words, although GNNs learned on heterophilic graphs cannot assume that nodes of the same class are more likely to appear in the neighborhood. adding connections between nodes of the same class to such graphs does not undermine their inherent properties.
This can be easily understood using the WebKB dataset [4] as an example. This is a classic heterophilic graph dataset, with each node representing one of Stu- dent, Faculty, Staff, Department, Course, or Project. Without loss of generality, we only consider Student, Staff and Course. We can construct simplified rela- tionship as shown in the Figure. Here, the connection between Staff A and Student B can represent that A is the advisor of B, while the connection between Stu- dent B and Course C can represent that B is enrolled in Course C. The inherent connections tend to favor such connections between different classes. However, In- traMix generates connections such as the one between two students, B1 and B2, which also holds valid in reality and can represent a relationship between these two students. Intuitively, this relationship logical and effective for downstream tasks. Through such re- lationships, IntraMix can enhance the effectiveness of the graph for downstream tasks. Therefore, IntraMix also has a certain effect on heterophilic graphs.
Staff:
Name: A
Stadents: B
Orpinel
Coneeated Data
Original Connection
Coronted Connection
Stadent:
Generated Student:
Student:
Name:
Name:
Name:
Advisor: A
Advisor:
Advisor: Ag
Courses: C....
Courses:
Courses:
Course:
Name: C
Figure 5: A simple example of IntraMix on WebKB. The original connections tend to link nodes of different classes, but the gener- ated connections between nodes of the same class are also logically consistent.
D.3 Analysis on Finding High-quality Nodes
In this part, we provide further introduction the method for finding high-quality labeled nodes mentioned in the main text and conduct a parameter sensitivity experiment. In the original text, we mentioned that we use multiple different dropout rates in a single GNN to approximate multiple distinct GNNs. By identifying nodes that are consistently labeled the same across all these GNN variants, we assume that these labels are approximately correct. This method serves as an alternative to ensemble learning. By using this approach, we avoid the need to pre-train multiple GNNs, and only incur the cost of inference n times, significantly reducing the time consumption.
We conduct a parameter sensitivity experiment on n, analyzing which value of yields the best performance. The results are shown in the table. can be observed that n is not always better when larger; the optimal value is achieved at 5, while the performance declines at n 6. This is quite understandable. As increases, it can be seen as an increase in the number of models used in ensemble learning, leading to more accurate node labeling. other words, as increases, if the labels of node are consistent across all n inferences, the probability of being correctly labeled increases. However, it is important to note that increases, the number of nodes that are consistently labeled the same across all
Table 9: Sensitivity Analysis of n. Experiments are conducted with GCN.
Cora
CiteSeer
Pubmed
n=1
84.30 + 0.60
73.60 0.67
80.42 = 0.23
n=2
84.68 + 0.74
73.86 + 0.57
81.92 + 0.43
n=3
84.78 + 0.54
74.01 0.36
82.16 + 0.28
0.28
n=4
85.17 + 0.55
74.41 + 0.48
82,52 + 0.38
n=5
85.25 + 0.42
74.80 + 0.46
82.98 = 0.54
n=6
85.02 + 0.65
74.15 + 0.66
82.34 + 0.60
22

---

Table 10: The comparison between IntraMix and Graph Structure Learning.
Cora
CiteSeer
Pubmed
GCN
81.51 + 0.42
70.30 + 0.54
79.06 = 0.31
SE-GSL [54]
71.08 # 0.76
80.11 = 0..45
LAGCN
84.61 0.57
74.70 0.51
81.73 0.71
IntraMix
85,25 2
74.80 + 0.46
82.98
IntraMi++GAE
85,99 +: 0.30
75.19 + 0.33
83.52 + 0.27
inferences decreases. This means that although the quality of these node labels is very high, their quantity is very low. Consequently, the feasible domain for selecting neighbors for the generated nodes becomes too small, failing to adequately enrich the information of graph. Therefore, practical use, a trade-off needs to be made between these factors when choosing the best value of n.
D.4 Comparison between IntraMix and Graph Structure Learning
In this section, we discuss the advantages of IntraMix compared to Graph Structure Learning(GSL) GSL is a method that optimizes graph structures and representations through learning. Therefore, it has overlap with data augmentation. Our biggest advantage over GSL methods lies training and deployment costs. GSL methods require learnable ways for optimizing, leading to high training costs e.g., GAUG [51] uses GAE for edge probabilities, and Nodeformer [46] uses differentiable ways. In contrast, analyzed in Sec 3.4, IntraMix has low time costs, making it practical for deployment. As real-world data continues to grow, the graphs in practical applications are becoming increasingly large, such as the expanding user networks in social media platforms. In this scenario, IntraMix offers a significant advantage in terms of training and deployment costs.
Secondly, in Table 10, we compare the performance of IntraMix and GSL. Additionally, we provided a method using IntraMix combined with GAE for structure selection, follow the setup of GAUG [51]. We find that IntraMix outperforms current popular GSL methods due to its effective use of low- quality labels and efficient topology optimization. At the same time, incorporating GAE improve the performance, but it also increase the training cost, presenting trade-off
In summary, IntraMix offers advantages over GSL methods with lower training and deployment costs and shows versatility by integrating various GSL methods.
D.5 Future Directions
In this part, we discuss our plans for future work. As mentioned above, although IntraMix has shown some improvements in heterophilic graphs, it is evident that IntraMix was not specifically designed for heterophilic graphs. However, heterophilic graphs are quite common real-world scenarios. Therefore, our future work will focus on better integrating IntraMix with heterophilic graphs. One possible approach is to gradually decrease the probability of connecting generated nodes with their surrounding neighbors during the training process. Initially, neighborhood selection satisfies homophily, meeting the requirements of this stage of homophilic graphs. Towards the end of this process, the generated nodes essentially exist as isolated nodes, abandoning the homophily assumption. This approach aims to satisfy the needs of both homophilic and heterophilic graphs. Further research is needed to explore this idea in detail.
E
Connection to Existing works
In this section, we present an expanded version of the Related Work Section 5,
E.1
Graph Augmentation Methods
Graph data augmentation is a method aimed at addressing issues such as missing label data and incomplete neighborhoods in graph data. As mentioned in See 5, existing methods often suffer from various problems and are typically capable of addressing only one aspect of the problems, leaving the other unresolved [5]. This limitation is insufficient for the challenges posed by graph data augmentation. We believe that generating high-quality labeled data from low-quality samples holds potential as mentioned in Section 1. As noise in low-quality samples often causes the data
23

---

distribution to diverge in various directions [26], exceeding the intended distribution range, we plan to leverage this directionality of noise. By blending multiple samples through the direction of noise, we aim to neutralize the noise and generate high-quality samples. Thus, we propose IntraMix.
Although there are few works that have recently focused Mixup in the context of graph augmen- tation [42, 45, 25, 12, 43], they tend to overlook the unique characteristics of graphs, specifically the topological structure mentioned earlier. Most Mixup methods applied to graphs borrow strate- gies from image-based approaches, randomly mixing samples from different classes [45]. These approaches directly lead to the challenge of determining the neighborhood of generated samples. These works often choose to connect generated samples with the samples used for generation. This can result in problems due the low-quality annotations on graphs, leading incorrect message propagation. The subpar experimental results of these methods also substantiate this point [42].
While some works have attempted to intra-class Mixup [25], they often treat it merely regularization component and do not realize its full potential. Similar to the use of inter-class Mixup, these approaches attempt to overcome the connectivity issues of Mixup by connecting nodes that have similar embeddings. However, this results in connected nodes being overly similar, providing limited meaningful information gain and leading to minimal performance improvement. These attempts highlight the inappropriate application of Mixup on graphs. Our proposed connection method ensures correctness in connections, while still providing rich information a node's 's neighborhood since the similarity in labels does not necessarily imply high similarity in node features.
In summary, the proposed IntraMix elegantly addresses both the challenges of scarce high-quality la- hels and neighborhood incompleteness in graphs through a sophisticated Intra-Class Mixup approach and high-confidence neighborhood selection method. The theoretical justification provided further supports the rationale behind this method.
E.2
Mixup
Mixup is data augmentation method that has demonstrated excellent performance in classical Euclidean data such as images [50], text [37], and audio [27]. The idea is to randomly sample data from the original dataset and mix the features and labels proportionally, generating new data. Both theoretically and experimentally, Mixup has been proven to enrich the distribution of the current data, allowing deep learning models to learn richer information [2, 1, 18). Mixup can also be approximated as an implicit regularization during the training process [13].
However, in the case of images, each data exists independently, and there is no assumed relationship between individual samples. The independence and identical distribution (i.i.d.) assumption holds for image data. In contrast, graph data exhibits neighbor relationship, and GNNs perform well due to this characteristic. This directly implies that when applying Mixup to graph data, the connectivity between generated samples and existing samples needs to be considered [45]. The full potential of GNNs can be realized only by constructing a reasonable neighborhood. This crucial aspect has been largely overlooked in almost all current Mixup approaches used in graphs.
Due to the necessity to consider connectivity and the assumption that neighboring nodes in the graph are more similar, challenge arises when applying vallina Mixup: the generated data distribution often falls between the existing distributions of the two classes [36], making it difficult to resemble any specific class. Determining neighborhood relationships becomes challenging in this scenario. Hence, we innovatively propose conducting Mixup within the same class. Through this approach, the generated sample distribution substantially overlaps with the class used for generation, making it casier to determine neighborhoods. Existing Mixup methods typically discourage intra-class Mixup to preserve the diversity of generated samples. However, we break away from the empirical practice of existing Mixup techniques that only blend random samples from two different classes, presenting an elegant solution for graph data augmentation.
F Broader Impacts
This paper presents work whose goal is to advance the field of Graph Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
24

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Please refer Appendix D
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
25

---

Justification:
Please refer to Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer Appendix C.2 and C.I.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
26

---

Answer: [Yes]
Justification: The paper provides open access to the data and code, with sufficient instructions faithfully reproduce the main experimental results, as described in the supplemental material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/
Seaidee//ooeSubmiin
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results, See the NeurIPS code and data submission guidelines (https:
/ //nips. cttpps..ccpbbbicc///c wwwpc//gg////eeeeee CodeeSummisee citommmsssion magiooooiccc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies all the training and test details in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The paper report error bars suitably and correctly in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
27

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: For each experiment, the paper provides sufficient information the computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https://neurip:: wwtpouurrps...pppupoeeeeeeeeeeee cc/ppbllcc/thhccsuuiiieie ines?
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The paper discuss both potential positive societal impacts and negative societal impacts of the work performed in Appendix and in the main text.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
28

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The creators or original owners of assets (e.g., code, data, models), used the paper, are properly credited, and the license and terms of explicitly mentioned and properly respected.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswi thwode.cooo..c.. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
29

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code is in Supplemental Materials.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "PV9MSrsUh1", "reviewer": "Reviewer_4UTx", "summary": "This paper propose IntraMix, a data augmentation approach for node classification with graph neural networks. IntraMix effectively mixes node features of nodes in the same class based on pseudo labels to generate new nodes, and then link the generated nodes to selected nodes in the graph. The authors conduct some mathematical analysis on the method and demonstrate its effectiveness empirically.", "questions": "- Does Eq. (5) mean that for any $(\\hat x, y)\\in D_m$ and any $(x_i, y)\\in D_m$, $\\hat x$ and $x_i$ are connected? If no, Eq. (5) should have been written differently, and the authors need to state how to select $(\\hat x, y)\\in D_m$ and any $(x_i, y)\\in D_m$ and generate new edges.", "limitations": "The authors discuss the limitation of this paper in Appendix D.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- The proposed data augmentation approach is interesting.\n\n- This paper conduct experiments on many datasets to justify the effectiveness of the proposed data augmentation approach. The authors report both accuracies and error bars in the results.\n\n- Sec. 4.5 & 4.6 additionally assess the over-smoothing problem and performance on heterophilic graphs, broadening the scope of the study.", "weaknesses": "1. The statement of theoretical results looks problematic.\n- Theorem 3.1:\n  - Note that $P_{noise}(\\cdot | x)$ and $P(\\cdot | x)$ are both probabilistic distributions. Thus, the noise satisfies $\\epsilon_1+\\cdots+\\epsilon_{|C|}=0$. The authors should clarify the distribution assumption on noises, since the constraint cannot be satisfied if $\\epsilon_1,\\cdots,\\epsilon_{|C|}$ are i.i.d. Gaussian random variables. Besides, the proof seems to have overlooked this fact.\n  - As a formal theorem statement, Theorem 3.1 should state line 128 using math equations for clarity.\n  - I encourage the authors to discuss how $\\lambda$ should be chosen based on this theorem.\n- Theorem 3.2\n  - The first sentence should be clearly stated as an assumption.\n  - I'm suspicious about the correctness of the theorem. For example, if one sets $\\eta_1=\\eta_2=-\\frac{1}{8(1+\\lambda^2+(1-\\lambda)^2)}-1$, then $(\\lambda^2+(1-\\lambda)^2)+\\frac{1}{4(2+\\eta_1+\\eta_2)}=-1$. Thus, the formula in line 164 is wrong.\n\n2. Some details of the experiment seem missing in the paper.\n- I believe that semi-supervised learning is the most standard setting for node classification. The authors provide no reference on the inductive learning setting and supervised learning setting. It's not clear what those settings are and why they are important.\n- The method relies on pseudo labels. The experiment section needs to state the way that the pseudo labels are generated and the cost of doing so.\n\n3. Other issues.\n- Line 91: Current definition implies that $|D_l|=|D_u|$, which is not general enough.\n- Line 146: dropout rates $\\to$ dropout probabilities.\n- Line 169: lines 1 $\\to$ line 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions. Next is our response.\n\n**Q1. The authors should clarify the distribution assumption on noises, since the constraint cannot be satisfied if $\\epsilon_1,...\\epsilon_{|C|}$ are i.i.d. Gaussian random variables.**\n\nA1. We apologize if our expression caused any confusion. We believe this issue does not exist. Firstly, $\\epsilon_1+...\\epsilon_{|C|}=0$ may not hold. Here, $\\epsilon_{i}$ represents the noise when a node is classified into class i, and this noise varies across different classes. From eq. (17), We can derive that without other constraints, the sum is not necessarily 0. Secondly, $\\epsilon_1, \\ldots, \\epsilon_{|C|}$ are not independent due to class relationships, and whether their sum is 0 does not affect our analysis. We will update details in our paper.\n\n**Q2. Theorem 3.1 should state line 128 using math equations for clarity.**\n\nA2. Thank you for pointing out this issue. We can express it as *$P(\\hat \\epsilon<\\epsilon)=\\frac{2}{\\pi} \\arctan((\\lambda^2+(1-\\lambda)^2)^{-\\frac{1}{2}})$, where $\\hat \\epsilon$ and $\\epsilon$ represent the noise in the generated data and the original data, respectively*.\n\n**Q3. Discuss how λ should be chosen based on theorem 3.1.**\n\nA3. This is a great question. In the ablation study (line 290-294), we discussed this. The result is that when $\\lambda=0.5$, IntraMix performs best, which aligns with Theorem 3.1. Similar to Mixup, to introduce randomness for better results, we set $\\lambda$~B(2,2), where B denotes the Beta Distribution. $\\lambda$ is around 0.5. Next, we provide more results.\n\n|                  | CiteSeer   | Pubmed     |\n| ---------------- | ---------- | ---------- |\n| $\\lambda$=0.0    | 73.40±1.08 | 81.56±0.72 |\n| $\\lambda$=0.1    | 74.08±0.69 | 82.04±0.59 |\n| $\\lambda$=0.3    | 74.28±0.47 | 82.39±0.52 |\n| $\\lambda$=0.5    | 74.58±0.59 | 82.77±0.49 |\n| $\\lambda$~B(2,2) | 74.80±0.46 | 82.98±0.54 |\n\nIt can be observed that the best results are achieved when $\\lambda$ is around 0.5, which aligns with our analysis.\n\n**Q4.Theorem 3.2: The first sentence should be clearly stated as an assumption.**\n\nA4. Thank you for pointing out our imprecise expression. We will correct it.\n\n**Q5. I'm suspicious about the correctness of the theorem 3.2. For example, if $\\eta_1=\\eta_2=-\\frac{1}{8(1+\\lambda^2+(1-\\lambda)^2)}-1$, the formula in line 164 is wrong.**\n\nA5. This is a great question, but $\\eta_1$ and $\\eta_2$ are learnable parameters, and $\\eta$ is typically positive. If $\\eta<0$,  it would imply that a node's own features negatively impact its classification, which is illogical. Such a situation would likely indicate issues with the dataset or training. Since $\\eta<0$ does not typically occur, the values you mentioned would not arise. \n\n**Q6. It's not clear what inductive learning setting and supervised learning setting are and why they are important.**\n\nA6. Thank you for identifying this issue. Next, we will introduce them.\n\n**Inductive learning.** In node-level tasks, the common setting is transductive, where the test distribution is known during training, fitting many static graphs. Inductive learning refers to not knowing the test distribution during training. Since many real-world graphs are dynamic, inductive learning is also crucial. For inductive learning settings, we use the subgraph composed of training data for training, as referenced in Section 4.3 of [1].\n\n**Supervised learning.** Although graphs typically adhere to semi-supervised settings, some graphs, like citation networks, have enough labels. Therefore, we conduct supervised experiments to show that IntraMix is feasible not only in scenarios with scarce labels but also in those with sufficient labels, proving its generality. The setting involves using enough training labels, with details provided in Appendix C.1. \n\n**Q7. The experiment section needs to state the way that the pseudo labels are generated and the cost of doing so.**\n\nA7. Thank you for identifying this issue. The pseudo-labeling method involves training a GNN $f$ with scarce labeled data and using $f$ to get pseudo labels for unlabeled data, as referenced in [2]. We further train $f$ with the augmented data. The additional cost for pseudo-labeling is small; overall, we train only one model, and the combined cost of pre-training and training with augmented data does not greatly exceed normal training cost. We analyze the time complexity in Sec 3.4, and will update a detailed discussion.\n\n**Q8. Line 91: Current definition implies that $|D_l|=|D_u|$, which is not general enough.**\n\nA8. We apologize for the confusion caused by our expression; we will revise it in our paper. Typically, $|D_l| << |D_u|$, where $D_l$ denotes the set of labeled nodes and $D_u$ is the unlabeled node set. \n\n**Q9. Line 146: dropout rates → dropout probabilities；Line 169: lines 1 → line 1.**\n\nA9. Thank you for pointing out these issues. We will correct them.\n\n**Q10. Does Eq. (5) mean that for any $(\\hat x,y)∈D_m$ and any $(\\hat x_i,y)∈D_m$, $\\hat x$ and $x_i$ are connected?  And the authors need to state how to select and generate new edges.**\n\nA10. We apologize for the confusion caused by our expression. We establish edges between $(\\hat x, y) \\in D_m$, and $(x, y) \\in D_h$. Here, $D_m$ is the set of data generated by IntraMix. $D_h$ is the high-quality pseudo-label set, with the generation way in Eq. (4). For each node in $D_m$, we randomly choose some nodes from $D_h$ with the same label as neighbors by directly connecting them. \n\nWe hope the revised version better meets your expectations, if you can improve the score then we appreciate it.\n\n**Reference:**\n\n[1] Liu, Songtao, et al. \"Local augmentation for graph neural networks.\" *International conference on machine learning*. PMLR, 2022.\n\n[2] Lee, Dong-Hyun. \"Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks.\" *Workshop on challenges in representation learning, ICML*. Vol. 3. No. 2. 2013.", "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": "ISlpskwOIA", "reviewer": "Reviewer_PZ8r", "summary": "This paper proposes an intra-class mixup generation method to generate high-quality labeled data to improve the performance in the node classification task.", "questions": "1. What are the values of $\\eta_1$ and $\\eta_2$ when the proposed method achieves the best performance on different datasets?\n2. In the ablation study, by saying \"replacing the generated nodes with all-zero vector\" do you mean that the node feature is a all-zero vector?\n3. NodeMixup has both the intra-class mixup and inter-class mixup. Why does the proposed method achieves much better performance than NodeMixup? What's the advantage of the proposed IntraMix over NodeMixup?\n4. What's the performance of Vanilla Mixup on the heterophilic graphs? Does the proposed method has better performance than Vanilla Mixup?", "limitations": "The authors list the limitation of the proposed method in appendix D.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The extensive experimental results show that the proposed IntraMixup outperforms most of the baseline methods across several datasets.\n2. The authors provide the theoretical analysis to support the effectiveness of the proposed method.\n3. The presentation of this paper is good and it's easy to follow.", "weaknesses": "1. I am not fully convinced by the effectiveness of IntraMix by only generating node based on pseudo-labeled nodes and labeled nodes. NodeMixup has both the intra-class mixup and inter-class mixup. NodeMixup has similar node selection method to generate nodes from the same class but the different neighbor selection criteria. Why does the proposed method achieves much better performance than NodeMixup? What's the advantage of the proposed IntraMix over NodeMixup? \n2. The novelty of the proposed method is somehow limited as it is similar to NodeMixup.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions.  Next is our response.\n\n**Q1.Why does the proposed method achieves better performance than NodeMixup?**\n\nA1. This is a great question. We discuss our advantages over NodeMixup in Sec 1, and Appendix E.2. We analyze the reasons in terms of accuracy and time complexity.\n\n**A1.1 Accuracy:** We discuss Mixup and neighbor selection separately.\n\n**Mixup:** According to Appendix B.1.2, Inter-Class Mixup cannot guarantee the noise reduction within each class, while NodeMixup, which primarily relys on Inter-Class Mixup, is more susceptible to label noise compared to IntraMix. \n\n**Neighbor Selection:** NodeMixup uses neighborhood similarity as a similarity metric, but this fails because the generated data lack neighbors. IntraMix avoids this by selecting same-class nodes, enabling a cold start on generated data. Additionally, NodeMixup's selected nodes are overly similar, resulting in less information gain. In contrast, neighbors selected by IntraMix may not have high feature similarity, leading to greater information gain.\n\n**A1.2 Time complexity:** As analyzed in Sec 3.4, our neighbor selection process has a time complexity of O(n) compared to NodeMixup's $O(n^2)$, where n is the number of augmented nodes. Thus, IntraMix has a time complexity advantage. We show experimental results below.\n\n|           | Pubmed(s) | ogbn-arxiv(5%)(s) |\n| --------- | --------- | ----------------- |\n| IntraMix  | 3.24±0.35 | 17.28±1.99        |\n| NodeMixup | 5.88±0.87 | 30.11±2.61        |\n\nAs observed, NodeMixup is much more costly than IntraMix, demonstrating IntraMix's cost superiority and greater advantage for large graphs, proving its general applicability.\n\n**Q2. The novelty of the proposed method is somehow limited as it is similar to NodeMixup.**\n\nA2. We believe that IntraMix represents a significant innovation, rather than just a minor improvement of NodeMixup. Next, we will discuss this.\n\n**Intra-Class Miuxp:** The importance of IntraMix lies in its being **the first work to seamlessly integrate Mixup into node-level learning, providing detailed experimental and theoretical analysis**. Through IntraMix, we shift the perspective that Inter-Class Mixup is more important for node-level tasks. Previous works, including NodeMixup, primarily focused on Inter-Class Mixup. They involved a transplant of Mixup into the graph domain with little consideration of graph-specific characteristics. Through rigorous experiments and theorems, we show that the neglected Intra-Class Mixup, is indeed more suitable for node-level learning. **This is important for the graph field as it explores a more promising and theoretically supported data augmentation way**.\n\n**Neighborhood Selection:** The innovation of our neighbor selection lies in using an **efficient method to achieve superior results compared to previous computationally intensive ways**. Details can be found in Sec 3.2. We naturally leverages the characteristics of Intra-Class Mixup to address a major challenge in applying Mixup to graphs—neighbor selection for generated data—and provides rigorous theoretical and experimental validation. Previous neighbor selection schemes, including NodeMixup, require significant costs. IntraMix achieves superior results in a more efficient way. Therefore, we consider our neighborhood selection method to be highly innovative. Moreover, it **combines with Intra-Class Mixup to form a beautiful and effective data augmentation framework**.\n\nIn summary, IntraMix exhibits significant innovation over NodeMixup. **Its elegant design, rigorous proof, and extensive experiments challenge previous understandings of node-level data augmentation**. This has important implications for graph machine learning and will inspire future research.\n\n**Q3. What are the values of $\\eta$ when IntraMix achieves the best performance?**\n\nA3. This is a great question. We present the results on GIN and show the values of $\\eta$ related to the best results, averaged over 10 runs.\n\n|          | $\\eta_1$ | $\\eta_2$ |\n| -------- | -------- | -------- |\n| Cora     | 1.8±0.1  | 1.7±0.1  |\n| CiteSeer | 2.0±0.2  | 2.0±0.1  |\n| Pubmed   | 1.3±0.4  | 1.1±0.4  |\n\nAccording to Theorem 3.2, a larger $\\eta$ reduces noise better. However, since learnable $\\eta$ also affects the GNN's learning capability, isolating the optimal values for these two tasks is difficult. Thus, observing its value in relation to noise reduction is not very meaningful.\n\n**Q4. By saying \"replacing ... with all-zero vector\" do you mean that the node feature is a all-zero vector?**\n\nA4. We apologize for any confusion caused. Your understanding is correct. We conduct such experiments, showing that IntraMix's improvement is due not only to optimal topology but also to the nodes generated through Mixup.\n\n**Q5. Does IntraMix have better performance than Vanilla Mixup on the heterophilic graphs?**\n\nA5. This is a great question. We conduct experiments on four heterophilic graphs.\n\n|                | Cornell  | Texas    | Wisconsin | Squirrel |\n| -------------- | -------- | -------- | --------- | -------- |\n| ACMGCN         | 85.1±6.0 | 89.1±3.0 | 86.6±4.6  | 55.1±1.5 |\n| +Vanilla Mixup | 84.5±3.4 | 87.9±4.2 | 82.8±4.1  | 54.2±1.3 |\n| +NodeMixup     | 84.9±2.4 | 88.8±3.9 | 84.9±3.8  | 54.8±1.3 |\n| +IntraMix      | 87.2±3.6 | 90.3±2.8 | 89.4±4.0  | 59.4±1.3 |\n\nWe find that IntraMix achieves stable improvements on heterophilic graphs, unlike Vanilla Mixup and NodeMixup, which degrade in performance. This is due to the critical role of neighbor selection in heterophilic data, where Vanilla Mixup and NodeMixup fail to identify suitable neighbors, leading to impacting performance. IntraMix contributes to information gain, as detailed in Appendix D.2, thus demonstrating its advantage on heterophilic graphs and general applicability.\n\nWe hope the response meets your expectations, if you can improve the score then we appreciate it.", "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": "HInjUaYiH4", "reviewer": "Reviewer_nFdn", "summary": "This paper aims to improve the performance of graph neural networks (GNNs) for node classification problem by generating high-quality labeled nodes and enriching node neighbors. It first uses pseudo-labeling to transform the unlabeled nodes into low-quality labeled nodes and performs mixup to generate high-quality labeled nodes. It then adopts an ensemble technique to establish an information exchange path between nodes of the same classes. Extensive experiments have been conducted to verify the proposed method.", "questions": "1. One of my concerns is that whether the proposed method might loss some useful information when eliminating the noise in the original graph? The proposed method should contain sufficient information for node classification and the corresponding analysis should be proofed or discussed.\n\n2. Since the neighbor selection operation is to enrich the node neighbors, it is similar to graph structure learning (GSL) methods that learn optimal graph structure for GNNs. What is the advantage of the proposed method compared with GSL methods?", "limitations": "Please refer to weakness and questions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method IntraMix could simultaneously generate high-quality labeled nodes and enrich node neighbors, and the experimental results on seven datasets show the superiority of the proposed method compared with other graph augmentation methods.\n\n2. The authors describe the motivations of the intra-class mixup and neighbor selection (section 3.1 and 3.2) clearly, and provide the corresponding theoretical proofs to guarantee the effectiveness of the method.\n\n3. Time complexity analysis is discussed (section 3.4), which illustrates the complexity of IntraMix is in the same of order of magnitude as the traditional GNN.\n\n4. Since IntraMix is a data augmentation framework, it is could be easily incorporated with existing GNNs.", "weaknesses": "1. In Table 1, the improvements of the node classification accuracy of the proposed method compared with other graph augmentation methods, such as NodeMixup and Local Augmentation, is not significant, which should be discussed more clearly.\n\n2. Although Theorem 3.1 and 3.2 proof that the noise in the generated data is smaller than that in the original data, the useful information for node classification should not be reduced and the theoretical analysis of the generated data containing sufficient information for classification is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions. Next is our response.\n\n**Q1. In Table 1, the improvements of the proposed method is not significant, which should be discussed more clearly.**\n\nA1. Thank you for raising this question. We will discuss it further.\n\n**Significance:** We believe that exploring new research directions impacts the field's development more than achieving high performance. **The most significant contribution of IntraMix is not in substantially improving performance but in uncovering the largely overlooked potential of Intra-Class Mixup, and providing ample analysis.** IntraMix effectively addresses the challenges of generating low-noise nodes and constructing their neighbors. It opens new possibilities for graph augmentation, which is of great importance for the development of graph domain. \n\n**Practicality:**  Regarding accuracy, unlike previous methods that perform poorly on some datasets, IntraMix is the only one that **maintains a stable advantage across most datasets. This means we can always trust IntraMix.** For larger improvements, we can replace the simple pseudo-labeling method or switch to more refined neighbor selection methods. **They can be easily integrated into IntraMix.**\n\nThe superiority of a method is not only reflected in its accuracy but also in **its ease of use**. IntraMix excels here, requiring minimal workflow modifications and no complex learnable ways. Sec 3.4 highlights its low time complexity, making it practical for deployment. Minor adjustments in the graph learning pipeline can greatly improve performance with minimal additional cost, facilitating the method's application.\n\nIn summary, IntraMix is highly meaningful not only for its stable performance improvement but also for introducing an overlooked way in graph augmentation. Additionally, it offers great advantages in terms of ease of use.\n\n**Q2. The generated data containing sufficient information for classification is needed.**\n\nA2. Thank you for raising this issue. We provide a brief analysis here. Details will be updated in the paper.\n\nAccording to [1], consider $\\lambda\\sim Beta(\\alpha,\\alpha),j \\sim U(n),\\alpha>0$. Our loss function can be represented as:\n$$\nl(f)=\\frac{1}{n}\\sum_{i=1}^nl(\\hat y_i,f(\\hat x_i))+R_1(f)+R_2(f)+R_3(f)+R_4(f),\n$$\nwhere\n$$\nR_1(f)=\\frac{1}{2n}\\sum_{i=1}^n||(\\nabla f(\\hat x_i)-J^{(i)})^T(\\nabla^2_{uu}l(\\hat y_i,f(\\hat x_i)))^\\frac{1}{2}||^2_{\\Sigma_{\\hat x\\hat x}^i},\n$$\n\n$$\nR_2(f)=\\frac{1}{2n}\\sum_{i=1}^n<\\Sigma_{\\hat x \\hat x}^i,{\\nabla_ul(\\hat y_i,f(\\hat x_i))\\nabla^2f(\\hat x_i)}>,\n$$\n\n$$\nR_3(f)=-\\frac{1}{2n}\\sum_{i=1}^n||\\Sigma_{\\hat x\\hat y}^i\\nabla^2_{yu}l(\\hat y_i,f(\\hat x_i))(\\nabla^2_{uu}l(\\hat y_i,f(\\hat x_i)))^{-\\frac{1}{2}}||^2_{(\\Sigma_{\\hat x\\hat x}^i)^{-1}},\n$$\n\n$$\nR_4(f)=\\frac{1}{2n}\\sum_{i=1}^n<\\Sigma_{\\hat y\\hat y}^i,{\\nabla^2_{yy}l(\\hat y_i,f(\\hat x_i))>}.\n$$\n\nThen, Intra-Class Mixup can be seen as better utilizing data by adding regularization terms. From this perspective, it does not lead to a loss of information.\n\nMoreover, many works [2] have shown that Mixup enhances the ability to utilize data rather than causing information loss. Based on these theoretical foundations and validated by the effectiveness of IntraMix in experiments, IntraMix does not lead to information loss.\n\n**Q3. The proposed method should contain sufficient information and the analysis should be proofed.**\n\nA3. Please refer to A2.\n\n**Q4. What is the advantage of the proposed method compared with GSL methods?**\n\nA4. Thank you for raising this question. \n\nOur biggest advantage over GSL methods lies in **training and deployment costs**. GSL methods require learnable ways for graph topologies, leading to high training costs (e.g., GAUG[3] uses GAE for edge probabilities, and Nodeformer[4] uses differentiable ways). In contrast, as analyzed in Sec 3.4, IntraMix has very low time costs, making it more practical for deployment.\n\nSecondly, we present comparative results with GSL methods.\n\n|            | Cora         | CiteSeer     | Pubmed       |\n| ---------- | ------------ | ------------ | ------------ |\n| GCN        | 81.51 ± 0.42 | 70.30 ± 0.54 | 79.06 ± 0.31 |\n| SE-GSL [5] | 82.52 ± 0.51 | 71.08 ± 0.76 | 80.11 ± 0.45 |\n| LAGCN      | 84.61 ± 0.57 | 74.70 ± 0.51 | 81.73 ± 0.71 |\n| IntraMix   | 85.25 ± 0.42 | 74.80 ± 0.46 | 82.98 ± 0.54 |\n\nWe find that IntraMix outperforms current popular GSL methods due to its effective use of low-quality labels and efficient topology optimization.\n\nNext, we incorporate a GAE in IntraMix, as detailed in [3].\n\n|          | Cora       | CiteSeer   | Pubmed     |\n| -------- | ---------- | ---------- | ---------- |\n| IntraMix | 85.25±0.42 | 74.80±0.46 | 82.98±0.54 |\n| +GAE     | 85.99±0.30 | 75.19±0.33 | 83.52±0.27 |\n\nWhile this improves performance, it adds training costs for GAE, presenting a trade-off.\n\nIn summary, IntraMix offers advantages over GSL methods with lower training and deployment costs and shows versatility by integrating various GSL methods, highlighting its potential for performance enhancement.\n\nWe hope the revised version better meets your expectations, if you can improve our score then we appreciate it.\n\n**Reference:**\n\n[1] Carratino, Luigi, et al. \"On mixup regularization.\" *Journal of Machine Learning Research* 23.325 (2022): 1-31.\n\n[2] Beckham, Christopher, et al. \"On adversarial mixup resynthesis.\" *Advances in neural information processing systems* 32 (2019).\n\n[3] Zhao, Tong, et al. \"Data augmentation for graph neural networks.\" *Proceedings of the aaai conference on artificial intelligence*. Vol. 35. No. 12. 2021.\n\n[4] Wu, Qitian, et al. \"Nodeformer: A scalable graph structure learning transformer for node classification.\" *Advances in Neural Information Processing Systems* 35 (2022): 27387-27401.\n\n[5] Zou, Dongcheng, et al. \"Se-gsl: A general and effective graph structure learning framework through structural entropy optimization.\" *Proceedings of the ACM Web Conference 2023*.", "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": "1fkqznrTf4", "reviewer": "Reviewer_bPiP", "summary": "The paper introduces IntraMix, a novel method for augmenting graph data to improve the performance of Graph Neural Networks. IntraMix addresses two major issues in graph datasets: the lack of high-quality labeled data and inadequate neighborhood information. The proposed method leverages Intra-Class Mixup to generate high-quality labeled data from low-quality labels and uses a neighbor selection strategy to enrich the neighborhoods. Extensive experiments demonstrate that IntraMix enhances GNN performance across various datasets.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. IntraMix effectively addresses both the lack of high-quality labels and inadequate neighborhood information, providing a comprehensive solution to two significant challenges in graph data augmentation.\n2. The authors conduct thorough experiments on multiple datasets and GNN models, showing the robustness and effectiveness of the proposed method.\n3. The paper provides theoretical analysis and guarantees for the reduction of noise in generated labels and the correctness of neighborhood enrichment, adding credibility to the method.\n4. IntraMix is designed to be easily integrated into existing GNN frameworks without additional training costs, making it practical for real-world applications.", "weaknesses": "1. The method involves several steps, including pseudo-labeling, mixup, and neighbor selection, which might complicate the implementation and increase the computational overhead.\n2. The initial pseudo-labeling step is crucial for the success of IntraMix. If the pseudo-labels are of very low quality, the subsequent steps may not generate significantly improved labels.\n3. While the paper shows results on multiple datasets, the performance of IntraMix on graphs with highly heterogeneous or unusual structures is not thoroughly explored.\n4. The method assumes a normal distribution for label noise, which may not hold in all real-world scenarios, potentially limiting the generalizability of the theoretical guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive comments and suggestions. Next is our response.\n\n**Q1.The method involves several steps, which might complicate the implementation and increase the computational overhead.**\n\nA1. Concerns about complexity are reasonable but unnecessary for IntraMix. \n\nFirst, we analyze the implementation complexity. As detailed in Alg 1, only minimal pipeline modifications are needed.\n\nThe time complexity analysis is in Sec 3.4. We break it down: **Pre-Training:** The model trained after data augmentation is the one for pseudo-labeling, so there is no great additional training cost. **Pseudo-labeling**: This only involves minimal inference overhead. **Mixup:** It only has a time complexity of O(m), where m is the number of generated data. **Neighbor Selection:** This requires only O(m) inferences, much less time-consuming than learnable ways. The time complexity for IntraMix is very low. Below, we present the time cost(s).\n\n|           | Pubmed    | ogbn-arxiv(5%) |\n| --------- | --------- | -------------- |\n| GCN       | 2.88±0.76 | 13.28±2.53     |\n| NodeMixup | 5.88±0.87 | 30.11±2.61     |\n| IntraMix  | 3.24±0.35 | 16.28±1.99     |\n\nThe setting is consistent with Sec 4.1. Compared to GCN, IntraMix does not greatly increase costs, consistent with our analysis. We can reduce the generated data to further reduce costs. \n\nIn summary, implementation and time complexity of IntraMix is not a concern.\n\n**Q2. If the pseudo-labels are of very low quality, the subsequent steps may not generate significantly improved labels.**\n\nA2. This is a great question. If the model cannot learn from data (e.g., pseudo-label accuracy is below 1%), IntraMix is likely to fail. However, such situations are extremely rare and instead of data augmentation, data collection is recommended in such cases. GNNs typically lead to reasonable pseudo-label quality. \n\nWhen pseudo-label quality is relatively low, IntraMix performs well. We use 5% of the semi-supervised training set for training.\n\n|          | Cora(5%)   | CiteSeer(5%) | Pubmed(5%) |\n| -------- | ---------- | ------------ | ---------- |\n| GCN      | 47.45±2.65 | 39.86±6.51   | 49.09±0.95 |\n| IntraMix | 54.66±1.61 | 47.70±2.13   | 57.60±0.83 |\n\nWe find that when the pseudo-label quality is low, IntraMix can effectively improve performance.\n\nAdditionally, iteration can improve performance. We use the model trained in the previous step for the next pseudo-labeling.\n\n|                           | Cora(5%)   | CiteSeer(5%) | Pubmed(5%) |\n| ------------------------- | ---------- | ------------ | ---------- |\n| step=0 (without IntraMix) | 47.45±2.65 | 39.86±6.51   | 49.09±0.95 |\n| step=1                    | 54.66±1.61 | 47.70±2.13   | 57.60±0.88 |\n| step=2                    | 56.19±1.54 | 52.45±2.89   | 64.88±0.82 |\n\nIteration provides a way to enhance the performance of IntraMix on low-quality data.\n\nIn summary, IntraMix effectively enriches the knowledge with low-quality pseudo-labels. Furthermore, iteration can help alleviate information bottlenecks for IntraMix.\n\n**Q3. The performance of IntraMix on graphs with highly heterogeneous or unusual structures.**\n\nA3. Thank you for this question. We conduct experiments to show that IntraMix is useful for heterogeneous graphs. In such data, nodes of the same type (e.g., movies in IMDB) often do not have direct connections. Therefore, we adjust our neighbor selection by connecting the neighbors of selected nodes. This minor modification does not impact the analysis. \n\n|           | DBLP       |            | IMDB       |            |\n| --------- | ---------- | ---------- | ---------- | ---------- |\n|           | macro-f1   | micro-f1   | macro-f1   | micro-f1   |\n| SeHGNN[1] | 94.99±0.19 | 95.34±0.14 | 67.11±0.25 | 69.17±0.43 |\n| +Mixup    | 95.08±0.31 | 95.57±0.21 | 67.66±0.31 | 69.82±0.45 |\n| +IntraMix | 95.61±0.22 | 95.89±0.10 | 68.71±0.26 | 70.77±0.32 |\n\nIntraMix also improves performance in heterogeneous graphs, highlighting its versatility. More details will be shown in the paper.\n\n**Q4. The method assumes a normal distribution for noise, limiting the generalizability.**\n\nThis is a great question. We now analyze it.\n\n**Reasonableness:** Gaussian distribution is the most common noise distribution in reality, and many works[2,3] use it for simplification. The effectiveness of these works and our experiments support this approximation.\n\n**Extensibility**: Our proof can be extended to other distributions. For example, suppose in eq. (17), $\\delta_i \\sim Q$, where Q is an unknown distribution with a mean of 0 (we will explain why this is reasonable). According to GMM[4], $p(\\delta_i) = \\sum_{j=1}^M \\alpha_j N_j(\\mu_j,\\Sigma_j)$, where $\\sum_{j=1}^M \\alpha_j = 1$. This means our theorems are applicable to nearly all distributions. Details will be shown in the paper.\n\nThen we address why we can assume $\\mu_{\\delta} = 0$. Considering $P$ as a manifold, the internal noise of $P$ is scattered because each point within $P$ has varying similarity to other manifolds. The noise in all directions makes the assumption reasonable, indicating noise does not affect the manifold's centroid.\n\nIn summary, our theory is sound and can be extended to nearly all noise distributions.\n\nWe hope the revised version better meets your expectations, if you can improve the score then we appreciate it.\n\n**Reference:**\n\n[1] Yang, Xiaocheng, et al. \"Simple and efficient heterogeneous graph neural network.\" *Proceedings of the AAAI conference on artificial intelligence*. Vol. 37. No. 9. 2023.\n\n[2] Lee, Kuang-Huei, et al. \"Cleannet: Transfer learning for scalable image classifier training with label noise.\" *Proceedings of the IEEE conference on computer vision and pattern recognition*. 2018.\n\n[3] Zhu, Xingquan, and Xindong Wu. \"Class noise vs. attribute noise: A quantitative study.\" *Artificial intelligence review* 22 (2004): 177-210.\n\n[4] Reynolds, Douglas A. \"Gaussian mixture models.\" *Encyclopedia of biometrics* 741.659-663 (2009).", "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:
We thank all reviewers for their diligent efforts in evaluating our submission. We will revise the paper to address the comments raised by each reviewer. We are glad the reviewers find that

- Our method is elegant and interesting, efficiently addressing two major challenges in graph data augmentation: data generation and topology optimization. [4UTx, nFdn, bPiP]
- We use ample experiments to demonstrate the effectiveness of our method and its generality across different types of data. [4UTx, PZ8r, nFdn, bPiP]
- We provide thorough theoretical analysis, enhancing the credibility. [PZ8r, nFdn, bPiP]
- Our proposed method can be easily integrated into the GNN framework. [nFdn, bPiP]
- Our paper is well-written. [PZ8r, nFdn]

Next, we summarize the contributions of our work.

Our proposed IntraMix is the **first to discover and explain the significant potential of Intra-Class Mixup in graph representation learning**. We correct the excessive and inappropriate focus on Inter-Class Mixup in previous research, which is a strategy that applies Mixup to the graph domain lacked consideration of the characteristics of the graph domain. In constract, IntraMix leverages the characteristics of the graph domain more effectively, addressing the two main challenges in graph data augmentation: the low quality of generated nodes and the difficulty of selecting neighbors for these nodes. Additionally, we provide ample theoretical support. With these enhancements, we are confident that our paper will make an impactful contribution to the NeurIPS conference and the graph machine learning field.

Next, we will summarize some common issues. Due to space constraints, we cannot discuss these in detail here. **All questions raised by the reviewers will be discussed in detail in the revised paper.**

**Q1. The significance and novelty of our proposed method.**

A1. We believe that correcting the misplaced focus of previous research and proposing new research directions with solid theoretical support is more meaningful than merely improving model performance. We find that almost all existing works involving Mixup in the field of graph data augmentation focus on Inter-Class Mixup. This method does not take into account the characteristics of the graph domain, making it difficult to solve the problem of neighbor selection for generated data. We have discussed this in detail in Sec 1 and Sec 3.1. Through extensive theoretical and experimental validation, we demonstrate that due to the unique characteristics of the graph domain, the previously overlooked Intra-Class Mixup is more effective for node-level learning. We also introduce an efficient neighborhood selection method, forming an elegant IntraMix framework.

**Overall, the significance and novelty of IntraMix lies in shifting the focus from the inappropriate emphasis on Inter-Class Mixup to a more reasonable and theoretically sound approach for graph data augmentation.** We believe this will contribute to the development of graph machine learning and inspire future work. Further performance improvements can be achieved by replacing the simple pseudo-labeling method in IntraMix with more refined techniques and making minor adjustments to the neighbor selection. These could serve as future research directions.

**Q2. The deployment complexity and time complexity of our proposed method.**

A2. **Deployment complexity.** As described in Alg 1, IntraMix can be integrated into any GNN pipeline with very simple modification without involving any additional models that need training. Therefore, the overall deployment complexity is low, making it highly advantageous for practical use.

**Time complexity.** In Sec 3.4, we analyze the overall time complexity, which shows only a slight increase compared to a pipeline without data augmentation. Since only one model is trained overall, the additional training cost is minimal. The pseudo-labeling process involves only a small amount of model inference, the Mixup involves lightweight feature mixing without any learnable methods, and the neighbor selection process also involves minimal model inference. Overall, the time complexity of IntraMix is very low, making it practical for real-world applications.

In summary, IntraMix has low deployment and time complexity, making it very practical for real-world applications. We believe this is a highly promising method.

**Q3. The generalizability of our proof.**

A3. In eq. (17), we express the relationship between noise and feature distribution as: $P_{noise}(x|y_i)=P(x|y_i)+\delta_i$, where $\delta_i$ represents the noise. In the proofs of Theorem 3.1 and Theorem 3.2, we assume that the noise follows a Gaussian distribution.

First, this assumption is reasonable and widely adopted in current research. The Gaussian distribution is the most common noise distribution in reality, covering most scenarios. The effectiveness of previous works and our experimental results also support the reasonableness of this assumption.

Second, our proof can be extended to other distributions. For example, suppose in eq. (17), $\delta_i \sim Q$, where Q is an unknown distribution. According to GMM [1], $p(\delta_i) = \sum_{j=1}^M \alpha_j N_j(\mu_j,\Sigma_j)$, where $\sum_{j=1}^M \alpha_j = 1$. This means our theorems are applicable to nearly all distributions. We will provide a more detailed discussion in the paper.

We sincerely appreciate the reviewers' invaluable feedback and insightful suggestions. 

**Reference:** 

[1] Reynolds, Douglas A. "Gaussian mixture models." *Encyclopedia of biometrics* 741.659-663 (2009).

Meta-review: This submission received four ratings (5, 5, 7 and 5), averaging 5.5, which is above the borderline score. After rebuttal, three of four reviewers clearly expressed that their concerns have been well addressed. After carefully checking the concerns of the remaining silent reviewer and the considerable effort of the authors during rebuttal, I suggest the acceptance. Hope the authors carefully incorporate the advice into the submission to improve the final version.
Decision: Accept (poster)