IntraMix: Intra-Class Mixup Generation for Accurate Labels and Neighbors

Authors: shenghe  zheng
hongzhi  wang
xianglong  liu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 18:02:33

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

Main paper: 
 introduction: 
 Graph Neural Networks (GNNs) have demonstrated great potential in various tasks [52] . However, 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 to address these two issues, but research on graph data augmentation is insufficient. Additionally, it is challenging to apply widely studied data augmentation ways designed for Euclidean data such as images to graphs due to their non-Euclidean nature [15] . Therefore, unique graph augmentation methods are needed. While graph augmentation aims to generate highquality 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 on 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 a low cost. Extracting information from such data could enrich data diversity.The cause of low-quality labels is the noise in labels, which results in a distribution different from the real one [10] . The noise direction is 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. It is defined as x = λx i + (1 -λ)x j , ŷ = λy i + (1 -λ)y j , where (x i , y i ), (x j , y j ) represent selected data, and y 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 in graphs, the data generated by vanilla Mixup is difficult to determine its neighbors and connecting them to any class of nodes is inappropriate, as 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.To address the issues, we propose IntraMix, a novel augmentation method for node classification, as shown in Figure 1 (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 a mixture of features from multiple groups, making it easier to find neighbors based on their respective groups. Additionally, the generated nodes have higher quality labels. Intuitively, if we simplify the label noise as ϵ ∼ N (0, σ 2 ), the mean distribution of two noises ε ∼ N (0, 1 2 σ 2 ), with a smaller variance, increases the likelihood that the generated label is accurate. Therefore, we address the sparse high-quality labels by 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 to analyze it in depth.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, we connect v 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 to 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 an elegant way. Our key contributions are as follows:• For the first time, we introduce Intra-Class Mixup as the core data augmentation in node classification, 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 Intra-Class Mixup and neighborhood selection.• Extensive experiments demonstrate that IntraMix improves the performance of GNNs on diverse datasets. Theoretical analysis elucidates the rationale behind IntraMix. 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 a rich and reasonable neighborhood. 
preliminaries: 
 Notations: Given a graph G = (V, E), where V = {v i } N i=1 is the node set, and E represents the edge set, the adjacency relationship between nodes can be represented by A ∈ {0, 1} N ×N , where A ij = 1 if and only if (v i , v j ) ∈ E. We use X ∈ R N ×D to denote the node feature. The node labels are represented by Y . Based on the presence or absence of labels, V can be divided into D l = {(x l1 , y l1 ), ...(x l N , y l N )} and D u = {x u1 , ...x u N }. We can use pseudo-labeling to assign low-quality labels Y u to nodes in D u , getting a low-quality set D p = {(x u1 , y u1 ), ...(x u N , y u N )}. N i = {v j |A ij = 1} are the neighbors of v i . Detailed notation list can be found in Appendix A.Node Classification with GNNs: Given a 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 a vector h v . The propagation for the k-th layer of a GNN is represented as follows:EQUATIONwhere COM and AGG are COMBINE and AGGREGATE functions, respectively, and h k v denotes the feature of v at the k-th layer. The output h v in the last layer of GNN is used for classification as y v = sof tmax(h v ), where y v is the predicted label for v. 
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 in 3.2. Next, in 3.3, we conclude the workflow and conduct complexity analysis in 3.4. The framework is shown in Figure 2 .Motivation: In supervised learning, having more labels typically allows for learning finer classification 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 the 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 is typically spread in multiple directions, we take full advantage of the directional nature of the noise. By blending data, we make the noise distribution closer to zero, 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 a 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.Approach: We use pseudo-labeling to transform the unlabeled nodes D u into nodes with low-quality labels D p . Then, we get D = D l ∪ D p , where there are a 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 low-quality labels to obtain high-quality labeled data guaranteed by Theorem 3.1. The generated dataset is represented as:EQUATIONwhereEQUATIONThe number of generated nodes is manually set. The labels in D m are of higher quality compared to D, a guarantee provided by Theorem 3.1. The proof can be found in Appendix B.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. P (ε < ϵ) = 2 π arctan((λ 2 + (1 -λ) 2 ) -12 ), andE(ε) E(ϵ) = [λ 2 + (1 -λ) 2 ] 1 2 < 1, where E(•) represents the expectation, and ε and ϵ denote the noise in the generated data and the original data, respectively.Motivation: 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 v. We aim to construct a neighborhood that satisfies two requirements: a). The neighborhood is suitable for v; b). The neighbors of v can obtain richer information through v. If v is simply connected to 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, a natural idea is to connect v with nodes of high confidence in the same class. In this way, we can find the correct neighbors for v and, acting as a bridge, connect the neighbors of two nodes of the same class through v to obtain more information from the graph, as shown in Figure 1(b) .Approach: As mentioned above, neighborhood selection involves two steps. First, finding nodes highly likely to be of the same class as v, 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 pseudo-labeling to predict the label of nodes under n 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:EQUATIONwhere f i represents GNNs with different dropout probabilities. After obtaining the high-quality set D h , it is time to establish neighborhoods between D h and D m 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:EQUATIONwhere e(a, b) represents an edge between nodes a and b. In this way, we not only find reasonable neighbors for the generated nodes but also establish an information exchange path between two nodes E ∪ {e(x, x i ), e(x, x j )}, where (x i /x j , ŷ) ∈ D h 8: end for Output: the augmented graph G = (V, E) 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 a graph with richer structural information is constructed for downstream tasks. Assumption 3.2. The label noise can be represented as node noise, i.e., P noise (x|y i ) = P (x|y i ) + δ i , whereδ i ∼ N (0, σ 2 xi ). Equation 1 simplifies to h k v = M LP k [(1 + η k )h k-1 v + 1 |Nv| u∈Nv h k-1 u ], where η k is learnable. m and n are nodes from the i-th class, x m ∼ P (x|y i ), x n ∼ P noise (x|y i ).Theorem 3.2. In a two-layer GNN, we haveE( δ) E(δ) = (λ 2 + (1 -λ) 2 ) + 1 4(2+η1+η2), where δ represents the noise impact directly connecting m and n and δ is the impact through IntraMix.The E( δ) E(δ) in Theorem 3.2 can be controlled to be less than 1 by adjusting the learnable η, indicating that the neighbor selection method of IntraMix leads to a 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.In this section, we introduce the overall workflow of IntraMix. For details, please refer to Algorithm 1. The data augmentation begins by generating low-quality labels for unlabeled nodes through pseudolabeling (lines 1). 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 a graph that is better suited for downstream tasks.Overall, the time consumption of using IntraMix can be divided into four aspects: generating pseudolabels 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-label 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 kN 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 O(m). Simultaneously, the time cost for finding the neighborhood for these m nodes is also O(m). Next, we analyze the subsequent training time consumption of IntraMix. Assuming the original time complexity of the GNN isO(|V | × F × F ′ ) + O(|E| × 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 isO(|V | × F × F ′ ) + O(|E| × F ′ ) + O(m × F × F ′ ) + O(2m × F ′ ) + O(m).As in most cases, m ≪ |V |, 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. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]Answer: [Yes] Justification:The paper provides open access to the data and code, with instructions to 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. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 F 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.• The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is a 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 are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
semi-supervised learning: 
 Datasets: 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.1.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 be found in Appendix C.2. For each graph augmentation applied to each GNN, we 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 are conducted on a 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 datasets. Additionally, Table 2 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-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.Datasets: To evaluate IntraMix on full-supervised datasets, we utilize the well-known ogbn-arxiv and Flickr, following standard partitioning ways. Detailed information can be found in Appendix C.1.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.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 semi-supervised settings, some graphs, like citation networks, have sufficient labels [34] . Thus, we conduct supervised experiments to 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 in the training set reduces the influence of the high-quality labeled data generated by IntraMix. This further proves that our neighbor selection strategy constructs a graph more conducive to downstream tasks by enriching the high-quality neighborhoods of nodes. 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 a generalizable graph augmentation framework applicable to real-world scenarios.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. Intra-Class Mixup: Firstly, we use a simple experiment to 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.Then, we discuss the effectiveness of Intra-Class Mixup. We compare it with methods that do not use Mixup, relying solely on pseudolabeling(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.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 a 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 a key reason for the poor performance of Mixup in node classification.Neighbor Selection: 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.Compared to other neighbor selection methods, IntraMix proposes a simple way to select nodes more likely to serve as neighbors, leading to more accurate message passing. Among the methods, 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 measurement. 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 an all-zero vector to eliminate the influence of Mixup still shows an 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 a bottleneck in information gain, hindering GNNs from learning enough knowledge. Despite the labels provided by pseudo-labeling for unlabeled data being low-quality, Intra-Class Mixup enhances the label quality, thus providing GNNs with ample knowledge.Sensitivity Analysis of λ: This part discusses the impact of λ in Intra-Class Mixup. The experiment is 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 λ = 0.5. The results validate our theoretical analysis, showing that the performance of GCN gradually improves as λ varies from 0 to 0.5. Therefore, we choose λ ∼ B(2, 2), where B denotes Beta Distribution.In this part we discuss the performance of IntraMix when the quality of pseudo-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 pseudo-labeling. This iterative method provides a way to enhance the performance of IntraMix on low-quality data. In summary, IntraMix effectively enriches the knowledge with extremely low-quality pseudo-labels.As is well known, deep GNNs may result in over-smoothing, a 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 a larger MADgap indicates a milder oversmoothing. Surprisingly, although IntraMix is not specifically designed to address over-smoothing, it shows a strong ability to counteract over-smoothing, reaching a level similar to GRAND [9] , a 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 in a random manner. This process resembles random information propagation, providing effective resistance against over-smoothing. Additionally, the richer neighbors and node features generated by IntraMix inherently mitigate over-smoothing [17] . The detailed discussion can be found in Appendix D.1. In this section, we analyze the performance of IntraMix on heterophilic graphs on the Cornell, Texas and Wisconsin datasets [4] . Although the neighbor selection utilizes the neighborhood assumption, we find from the results in Figure 4 (b) that IntraMix can also enhance GNN on heterophilic graphs. This is because, despite the existing connections in heterophilic graphs tending to link different types of nodes, they do not exclude connections between similar nodes. The connections between highquality 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.In this section, we discuss the performance of IntraMix on heterogeneous graphs. In this setting, neighboring nodes may belong to different types of entities. For example, different papers can be linked through authors, but there is no direct link between them. This is a common graph configuration. We 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. 
related work: 
 Graph Augmentation: The primary purpose of graph augmentation is to address two common challenges in 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 involvement [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.1.Mixup: Mixup is a 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 in node classification. Details about the related Mixup works can be found in Appendix E.2. 
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 of limited neighborhoods, we connect the generated nodes with nodes that are highly likely from the same class. IntraMix provides an elegant solution to the dual challenges faced by graphs. Moreover, IntraMix is a flexible method that can be applied to all GNNs. Future work will focus on exploring neighbor selection methods to construct more realistic graphs. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The paper poses no such risks.Guidelines:• The answer NA means that the paper poses no 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 a best faith effort.12. Licenses for existing assets Question: 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?Answer: [Yes] Justification: The creators or original owners of assets (e.g., code, data, models), used in the paper, are properly credited, and the license and terms of use explicitly are mentioned and properly respected.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. 
 
 Appendix: We first list the notations for key concepts in our paper. The set of nodes with labels at begining.The set of nodes without labels at begining.The set of nodes with low-quaility labels.The set of nodes with high-quaility labels.The set of nodes generated by Intra-Class Mixup. D TThe set of nodes for training.The neighbors of a node v. h vThe hidden feature vector of node v. nThe number of nodes mThe number of edges cThe number of node categories.B.1 Theorem 3.1In this part, we will prove Theorem 3.1. We will start by introducing the notation used in the proof.The category-specific noise is represented as:EQUATIONwhere ϵ i ∼ N (0, σ 2 i ). For simplification of the solution, we use the expression involving the label matrix transfer [28] , denoted as (x, y) ∼ Q. And get the noise label matrix transfer as:Q noise = T t Q (7)where T y,y ′ ≥ 0 represents the probability, under the influence of noise, that data with the true label y is mislabeled as y ′ .And T can be represented as :EQUATIONHere, ϵ = ϵ i ∼ N (0, σ 2 i )|C| i=1 represents the noise for each class, I denotes the diagonal matrix, and J represents the matrix of all ones. Therefore, f (ϵ)J is the noise matrix, and the purpose of f is to control the range of noise. It satisfies three properties: 1).0 ≤ f (x) ≤ 1; 2).f (x) exhibits the same monotonicity as |x|; 3).f (x) + f (y) = f (x + y); Satisfying property 1 is essential because, in Equation 8, f is used to control the range of noise, and probabilities represented by matrix entries should remain within the meaningful range of [0, 1].Satisfying property 2 is due to the representation in Equation 6, where |ϵ i | represents the magnitude of the deviation from the correct distribution, indicating larger noise for greater magnitudes. The positive or negative sign of ϵ i indicates the direction of the noise, but in Equation 8, this directionality is not explicitly represented. Therefore, using the absolute value captures the magnitude of noise.Satisfying property 3 is because the noise in Equation 6has directionality; two noises may cancel each other out due to opposite directions. When represented using Equation 8, 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.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:EQUATIONwhereϵ i ∼ N (0, σ 2 i ), ϵ ′ i ∼ N (0, σ 2 i ), and x 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:EQUATIONwhereϵ 1 = {ϵ i ∼ N (0, σ 2 i )} |C| i=1 and ϵ 2 = {ϵ i ∼ N (0, σ 2 i )} |C| i=1 . The measurement of noise in T and T intra is essentially comparing f (ϵ) with f (λϵ 1 + (1 -λ)ϵ 2 ).According to property 2 satisfied by f , this can be transformed into comparing |ϵ| with |λϵ 1 + (1λ)ϵ 2 |. A larger value in this comparison indicates greater noise. For the i-th class label, it is a calculation of:EQUATIONwhere ϵ i ∼ N (0, σ 2 i ), ϵ i , ϵ i1 , ϵ i2 are independent and identically distributed variables, and |ϵ| follows the folded normal distribution [22] , let c = λ 2 + (1 -λ) 2 , we have:EQUATIONProof 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 of |ϵ|. Then we have:EQUATIONSimilarly, we have:E(|ϵ i |) = √ 2σ √ π .Therefore, the ratio of the expected noise after Intra-Class Mixup to the original noise in class i is given by:EQUATIONThis implies that the expected noise in each class is reduced after Intra-Class Mixup.When we use Vallina Mixup, i.e., performing Mixup randomly between samples, it can be expressed according to the derivation in [2] and Equation 8 as follows:EQUATIONwhereϵ = 1 |C| |C| i=1 ϵ i .Then, following similar derivations of Equation 12, letσ i2 = λ 2 σ 2 i + (1 -λ) 2 σ 2 , σ = 1 |C||C| i=1 σ i , we have:EQUATIONThe Equation 16cannot guarantee that it is greater than 0.5 for all σ i . This implies that although Vallina Mixup acts as a form of regularization during training, implicitly introducing data denoising [50] , it does not ensure label quality improvement for every class. In this regard, it has limitations compared to our proposed Intra-Class Mixup.In this section, we will prove Theorem 3.2. We will begin by introducing the notation used in the proof process.In the proof of this section, the labeling noise in Equation 6 is transformed into equivalent node feature noise as follows:EQUATIONwhere δ i ∼ N (0, σ 2 xi ). The equivalence proof with Equation 6 is as follows:EQUATIONTherefore, from Equation 17, we have:EQUATIONP (x) P (yi) is a constant related to the dataset. Thus, the equation P noise (x|y i ) = P (x|y i ) + δ i holds, where δ i ∼ N (0, σ 2 xi ). 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 at the k-th layer is simplified to:EQUATIONWhere h k v is used to represent the feature representation of node v at the k-th layer, η k represents the learnable variable at the k-th layer, N v denotes the set of neighboring nodes of node v. W k can be used to represent the parameter matrix of the MLP in the k-th layer of the GNN, and b k 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 y i under high-confidence labeling. Node m has a node feature x m following the distribution P (x|y i ), while the node feature x n of node n follows the distribution P noise (x|y i ). We have:EQUATIONFor convenience in derivation, without loss of generality, we can assume that m 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 n through the node v = (x, y i ) 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 2) 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.When connecting nodes m and n directly, we have:EQUATIONSimilarly, we have:EQUATIONThen, after the second-layer message passing, node m can be represented as:P (h 2 m |y i ) = W 1 [(1 + η 2 )P (h 1 m |y i ) + P (h 1 n |y i )] = W 2 {(1 + η 2 )[W 1 [(2 + η 1 )P (x|y i ) + δ i ] + b 1 ] + W 1 [(2 + η 1 )P (x|y i ) + (1 + η 1 )δ i ] + b 1 } + b 2 = W 2 {(2 + η 1 )[(1 + η 2 )W 2 W 1 + W 1 ]P (x|y i ) + (2 + η 2 )b 1 } + b 2 value + W 2 W 1 (2 + η 1 + η 2 )δ i noise (24)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 v generated by Intra-Class Mixup satisfies P (x|y i ) = P (x|y i ) + δ ′ i , where δ ′ i ∼ N (0, (λ 2 + (1 -λ) 2 )σ 2 xi ). Following the same reasoning as above, we have:EQUATIONThen, after the second-layer message passing, m can be represented as:EQUATIONAssuming the parameters of MLP are the same, the value parts of Equation 24and Equation 26 are the same. Now, what needs to be compared is the ratio of the expected values of the noise parts in the two equations. Similar to property 3 mentioned in Sec B.1.1, when comparing noise expectations, absolute values should be considered. That is, the farther the noise is from the 0, the larger it is, and the sign indicates the direction. Let noise m and noise ′ m represent the noise terms in Equation 24 and Equation 26, respectively. We have:EQUATIONSimilar to the derivation in Equation 13, we have:EQUATIONThen, Equation 27 can be represented as:EQUATION)As η 1 and η 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 Intra-Class Mixup leads to smaller noise compared to directly connecting them.In this section, we present detailed information about the datasets used in the experiments, including the split method. Additionally, we provide a thorough introduction to the comparative methods and the setups of GNNs in the experiments.In this part, we introduce the datasets used in this paper. Detailed information can be found in Table 8 .We utilize five medium-scale datasets in a semi-supervised 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 on 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 to adhere to the semi-supervised configuration.On the other hand, CS and Physics datasets represent datasets related to collaboration among researchers. In these datasets, each node represents a researcher, and edges denote collaborative 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 set to meet the semi-supervised configuration.We also use two large-scale datasets for semi-supervised and full-supervised 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% and 10% of the original training data to simulate the semi-supervised setting. The ogbn-arxiv is a dataset of the ogb standard dataset, where each node represents an Arxiv paper, and directed edges indicate citations between papers. Each paper is associated with a 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 a 40-class classification problem. The dataset partitioning follows the original paper [16] , with papers published until 2017 serving as the training set, papers published in 2018 as the validation set, and papers published after 2019 as the test set. Unlike the limited training set in semi-supervised 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. If 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 SIFT-extracted features. A 500-dimensional bag-of-visual-words 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 7 categories. Each image belongs to 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.This section introduces the methods compared in the experiments. For the fairness of the experiments, 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. It incorporates learnable noise into node features and optimizes GNN training by finding the most challenging noise in each iteration. However, inevitably, it requires 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 a target distribution based on the existing graph, samples a series of augmented graphs from the distribution using a sampling method proposed in the paper, and trains using a 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, thereby 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 to 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 a detailed explanation in Sec E.1. 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 a concise yet powerful solution that efficiently tackles both challenges, making it a highly promising approach.In this section, we explain some analyses in the main text and introduce future research directions.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 a 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 a 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-smoothing to some extent. We attribute this phenomenon to two main reasons. First, IntraMix generates a large number of accurately labeled nodes, providing each node with numerous accurate neighbors. For any given node, a 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 information and reduces the impact of over-smoothing. The second reason is somewhat similar to why GRAND [9] performs well in resisting over-smoothing.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 Student, Faculty, Staff, Department, Course, or Project. Without loss of generality, we only consider Student, Staff and Course. We can construct a simplified relationship 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 Student 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, B 1 and B 2 , which also holds valid in reality and can represent a relationship between these two students. Intuitively, this relationship is logical and effective for downstream tasks. Through such relationships, IntraMix can enhance the effectiveness of the graph for downstream tasks. Therefore, IntraMix also has a certain effect on heterophilic graphs.In this part, we provide a further introduction to 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 n yields the best performance. The results are shown in the table. It can be observed that n is not always better when larger; the optimal value is achieved at n = 5, while the performance declines at n = 6. This is quite understandable. As n increases, it can be seen as an increase in the number of models used in ensemble learning, leading to more accurate node labeling. In other words, as n increases, if the labels of a node are consistent across all n inferences, the probability of it being correctly labeled increases. However, it is important to note that as n increases, the number of nodes that are consistently labeled the same across all n 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, in practical use, a trade-off needs to be made between these factors when choosing the best value of n.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 in training and deployment costs. GSL methods require learnable ways for optimizing, leading to high training costs e.g., [51] uses GAE for edge probabilities, and Nodeformer [46] uses differentiable ways. In contrast, as 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 lowquality labels and efficient topology optimization. At the same time, incorporating GAE improve the performance, but it also increase the training cost, presenting a trade-off.In summary, IntraMix offers advantages over GSL methods with lower training and deployment costs and shows versatility by integrating various GSL methods.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 in 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.In this section, we present an expanded version of the Related Work Section 5.Graph data augmentation is a method aimed at addressing issues such as missing label data and incomplete neighborhoods in graph data. As mentioned in Sec 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 distribution to diverge in various directions [26] , exceeding 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 a few works that have recently focused on Mixup in the context of graph augmentation [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 strategies 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 to the low-quality annotations on graphs, leading to incorrect message propagation. The subpar experimental results of these methods also substantiate this point [42] .While some works have attempted to use intra-class Mixup [25] , they often treat it merely as a 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 to a node'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 labels and neighborhood incompleteness in graphs through a sophisticated Intra-Class Mixup approach and a high-confidence neighborhood selection method. The theoretical justification provided further supports the rationale behind this method.Mixup is a 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 a 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, a 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 easier 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.NeurIPS Paper Checklist • 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.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. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The statement of theoretical results looks problematic.
- Theorem 3.1:
  - 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.
  - As a formal theorem statement, Theorem 3.1 should state line 128 using math equations for clarity.
  - I encourage the authors to discuss how $\lambda$ should be chosen based on this theorem.
- Theorem 3.2
  - The first sentence should be clearly stated as an assumption.
  - 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.

2. Some details of the experiment seem missing in the paper.
- 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.
- 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.

3. Other issues.
- Line 91: Current definition implies that $|D_l|=|D_u|$, which is not general enough.
- Line 146: dropout rates $\to$ dropout probabilities.
- Line 169: lines 1 $\to$ line 1.
questions: 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: limitations: The authors discuss the limitation of this paper in Appendix D.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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? 
2. The novelty of the proposed method is somehow limited as it is similar to NodeMixup.
questions: questions: 1. What are the values of $\eta_1$ and $\eta_2$ when the proposed method achieves the best performance on different datasets?
2. 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?
3. 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?
4. What's the performance of Vanilla Mixup on the heterophilic graphs? Does the proposed method has better performance than Vanilla Mixup?
limitations: limitations: The authors list the limitation of the proposed method in appendix D.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. 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.
questions: 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.

2. 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: limitations: Please refer to weakness and questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The method involves several steps, including pseudo-labeling, mixup, and neighbor selection, which might complicate the implementation and increase the computational overhead.
2. 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.
3. While the paper shows results on multiple datasets, the performance of IntraMix on graphs with highly heterogeneous or unusual structures is not thoroughly explored.
4. 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.
questions: questions: See weaknesses.
limitations: limitations: Yes.

Comments: title: Dear reviewers, please read and respond to authors' rebuttal (if you haven't done so)
Rebuttal by Authors
Reply to authors' rebuttal
comment: Thank you for your response. We are pleased that we were able to address your concerns. We also want to express our sincere gratitude once again for your selfless efforts during the review process.
Thanks for your detailed feedback, which has addressed my concerns on the improvements in experiments and comparison with GSL methods. Thus, I will maintain my positive score.
Dear reviewers, please read and respond to authors' rebuttal (if you haven't done so). Thanks.

Your AC
We sincerely appreciate your response and the time you dedicated to reviewing our paper. Your valuable suggestions have been immensely helpful, and we will incorporate these into the revised version of our paper. We are also pleased to have addressed the concerns you raised about our work. If you would be willing to consider a potential increase in our score, we would be most grateful. Thank you once again for your support and guidance.
Thank you for your response. We also greatly appreciate your selfless effort during the review process, pointing out the unclear expressions and areas that needed more detailed discussion. We will incorporate detailed discussions of these aspects in the revision of our paper to improve its quality.

**Here, we provide a more detailed explanation of Q5**. We will explain why $\eta \geq 0$ from the perspectives of the meaning of $\eta$ and the experimental results. 

First, let's analyze the role of $\eta$. As described in [1], $\eta$ represents the extent to which the original features of the current node influence its feature embedding after learning through the GNN. Since the embedding representation of each node used in downstream tasks is derived from both its original features and the features of its neighbors, we generally believe that these two factors complement each other, with the current node's features playing a dominant role. Therefore, $\eta \geq 0$ is consistent with practical expectations. If $\eta < 0$, it would imply that, in generating the embedding representation of the current node, the neighborhood information is more important than the node's own features, which is unreasonable. For example, consider the task of node classification in a social network, where each node represents a user. Assuming that data collection is accurate and the machine learning model is properly trained, each user's own features should play the most significant role in their embedding representation, while the information from their friends serves only as an auxiliary factor. Therefore, $\eta \geq 0$ aligns with the practical scenario. Moreover, as long as $\eta > -1$, the noise reduction effect described in Theorem 3.2 holds. Thus, Theorem 3.2 is reasonable for practical use.

Second, we validate the condition $\eta \geq 0$ from an experimental perspective. We present the results on GIN [1]. The table below shows the values of $\eta$ corresponding to the best experimental results when $\lambda=0.5$, averaged over 10 runs.

|          | $\eta_1$  | $\eta_2$  |
| -------- | --------- | --------- |
| Cora     | 1.79±0.13 | 1.72±0.09 |
| CiteSeer | 2.03±0.15 | 1.96±0.16 |
| Pubmed   | 1.26±0.44 | 1.14±0.40 |

From the experimental results, we can observe that $\eta \geq 0$ holds true. We will provide a more detailed discussion in the revised version of the paper.

**Our response is as outlined above. We hope the revised version better meets your expectations, and we would greatly appreciate it if you could consider improving our score. If you have any further questions or suggestions, please feel free to reach out at any time. Thank you again.**

**Reference:**

[1] Xu, Keyulu, et al. "How Powerful are Graph Neural Networks?." *International Conference on Learning Representations*. 2019.
I thank the authors for their thoughtful rebuttal. My concerns have been properly addressed and I will maintain my positive score.
Thank you for the response. I will maintain my positive rating.

Regarding Q5, I believe the correct way to state a theorem is to list $\eta\geq 0$ as an assumption and present experimental results to show this assumption holds in practice, otherwise the theorem itself is not mathematically correct.

I encourage the authors to include the discussions in the paper for better clarity.