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

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}\cup 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:

where

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

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:

where $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 $\hat{E}$ of the original set $E$ can be expressed as:

where $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 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.

The $\frac{E(\hat{\delta})}{E(\delta)}$ in Theorem 3.2 can be controlled to be less than 1 by adjusting the learnable $\eta$, 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 pseudo-labeling (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 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-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 is $O(|V|\times F\times F^{\prime})+O(|E|\times F^{\prime})$, where $F$ denotes the input feature dimension of nodes, and $F^{\prime}$ is the hidden layer dimension of GNN. The time complexity after using IntraMix is $O(|V|\times F\times F^{\prime})+O(|E|\times F^{\prime})+O(m\times F\times F^{\prime})+O(2m\times F^{\prime})+O(m)$. As in most cases, $m\ll|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.

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.

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

The experiments mentioned above are conducted in 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 during training. Since many real-world graphs are dynamic, inductive learning is also crucial. To demonstrate the reliability of IntraMix in inductive setups, we conduct experiments on Cora and CiteSeer, utilizing GraphSAGE and GAT. The results are presented in Table 3. In inductive learning, GNNs can only observe non-test data during training.

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

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 $\lambda$: This part discusses the impact of $\lambda$ 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 $\lambda=0.5$. The results validate our theoretical analysis, showing that the performance of GCN gradually improves as $\lambda$ varies from 0 to 0.5. Therefore, we choose $\lambda\sim B(2,2)$, where $B$ denotes Beta Distribution.

Analysis of pseudo-label quality: 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 over-smoothing. 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 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.

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.