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

Thank you for your constructive comments and suggestions. Next is our response.

Q1.The method involves several steps, which might complicate the implementation and increase the computational overhead.

A1. Concerns about complexity are reasonable but unnecessary for IntraMix.

First, we analyze the implementation complexity. As detailed in Alg 1, only minimal pipeline modifications are needed.

The time complexity analysis is in Sec 3.4. We break it down: Pre-Training: The model trained after data augmentation is the one for pseudo-labeling, so there is no great additional training cost. Pseudo-labeling: This only involves minimal inference overhead. Mixup: It only has a time complexity of O(m), where m is the number of generated data. Neighbor Selection: This requires only O(m) inferences, much less time-consuming than learnable ways. The time complexity for IntraMix is very low. Below, we present the time cost(s).

The setting is consistent with Sec 4.1. Compared to GCN, IntraMix does not greatly increase costs, consistent with our analysis. We can reduce the generated data to further reduce costs.

In summary, implementation and time complexity of IntraMix is not a concern.

Q2. If the pseudo-labels are of very low quality, the subsequent steps may not generate significantly improved labels.

A2. This is a great question. If the model cannot learn from data (e.g., pseudo-label accuracy is below 1%), IntraMix is likely to fail. However, such situations are extremely rare and instead of data augmentation, data collection is recommended in such cases. GNNs typically lead to reasonable pseudo-label quality.

When pseudo-label quality is relatively low, IntraMix performs well. We use 5% of the semi-supervised training set for training.

We find that when the pseudo-label quality is low, IntraMix can effectively improve performance.

Additionally, iteration can improve performance. We use the model trained in the previous step for the next pseudo-labeling.

Iteration provides a way to enhance the performance of IntraMix on low-quality data.

In summary, IntraMix effectively enriches the knowledge with low-quality pseudo-labels. Furthermore, iteration can help alleviate information bottlenecks for IntraMix.

Q3. The performance of IntraMix on graphs with highly heterogeneous or unusual structures.

A3. Thank you for this question. We conduct experiments to show that IntraMix is useful for heterogeneous graphs. In such data, nodes of the same type (e.g., movies in IMDB) often do not have direct connections. Therefore, we adjust our neighbor selection by connecting the neighbors of selected nodes. This minor modification does not impact the analysis.

IntraMix also improves performance in heterogeneous graphs, highlighting its versatility. More details will be shown in the paper.

Q4. The method assumes a normal distribution for noise, limiting the generalizability.

This is a great question. We now analyze it.

Reasonableness: Gaussian distribution is the most common noise distribution in reality, and many works[2,3] use it for simplification. The effectiveness of these works and our experiments support this approximation.

Extensibility: Our proof can be extended to other distributions. For example, suppose in eq. (17), $\delta_i \sim Q$, where Q is an unknown distribution with a mean of 0 (we will explain why this is reasonable). According to GMM[4], $p(\delta_i) = \sum_{j=1}^M \alpha_j N_j(\mu_j,\Sigma_j)$, where $\sum_{j=1}^M \alpha_j = 1$. This means our theorems are applicable to nearly all distributions. Details will be shown in the paper.

Then we address why we can assume $\mu_{\delta} = 0$. Considering $P$ as a manifold, the internal noise of $P$ is scattered because each point within $P$ has varying similarity to other manifolds. The noise in all directions makes the assumption reasonable, indicating noise does not affect the manifold's centroid.

In summary, our theory is sound and can be extended to nearly all noise distributions.

We hope the revised version better meets your expectations, if you can improve the score then we appreciate it.

Reference:

[1] Yang, Xiaocheng, et al. "Simple and efficient heterogeneous graph neural network." Proceedings of the AAAI conference on artificial intelligence. Vol. 37. No. 9. 2023.

[2] Lee, Kuang-Huei, et al. "Cleannet: Transfer learning for scalable image classifier training with label noise." Proceedings of the IEEE conference on computer vision and pattern recognition. 2018.

[3] Zhu, Xingquan, and Xindong Wu. "Class noise vs. attribute noise: A quantitative study." Artificial intelligence review 22 (2004): 177-210.

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

Thank you for your constructive comments and suggestions. Next is our response.

Q1. In Table 1, the improvements of the proposed method is not significant, which should be discussed more clearly.

A1. Thank you for raising this question. We will discuss it further.

Significance: We believe that exploring new research directions impacts the field's development more than achieving high performance. The most significant contribution of IntraMix is not in substantially improving performance but in uncovering the largely overlooked potential of Intra-Class Mixup, and providing ample analysis. IntraMix effectively addresses the challenges of generating low-noise nodes and constructing their neighbors. It opens new possibilities for graph augmentation, which is of great importance for the development of graph domain.

Practicality: Regarding accuracy, unlike previous methods that perform poorly on some datasets, IntraMix is the only one that maintains a stable advantage across most datasets. This means we can always trust IntraMix. For larger improvements, we can replace the simple pseudo-labeling method or switch to more refined neighbor selection methods. They can be easily integrated into IntraMix.

The superiority of a method is not only reflected in its accuracy but also in its ease of use. IntraMix excels here, requiring minimal workflow modifications and no complex learnable ways. Sec 3.4 highlights its low time complexity, making it practical for deployment. Minor adjustments in the graph learning pipeline can greatly improve performance with minimal additional cost, facilitating the method's application.

In summary, IntraMix is highly meaningful not only for its stable performance improvement but also for introducing an overlooked way in graph augmentation. Additionally, it offers great advantages in terms of ease of use.

Q2. The generated data containing sufficient information for classification is needed.

A2. Thank you for raising this issue. We provide a brief analysis here. Details will be updated in the paper.

According to [1], consider $\lambda\sim Beta(\alpha,\alpha),j \sim U(n),\alpha>0$. Our loss function can be represented as:

$$l(f)=\frac{1}{n}\sum_{i=1}^nl(\hat y_i,f(\hat x_i))+R_1(f)+R_2(f)+R_3(f)+R_4(f),$$

where

$$R_1(f)=\frac{1}{2n}\sum_{i=1}^n||(\nabla f(\hat x_i)-J^{(i)})^T(\nabla^2_{uu}l(\hat y_i,f(\hat x_i)))^\frac{1}{2}||^2_{\Sigma_{\hat x\hat x}^i},$$ $$R_2(f)=\frac{1}{2n}\sum_{i=1}^n<\Sigma_{\hat x \hat x}^i,{\nabla_ul(\hat y_i,f(\hat x_i))\nabla^2f(\hat x_i)}>,$$ $$R_3(f)=-\frac{1}{2n}\sum_{i=1}^n||\Sigma_{\hat x\hat y}^i\nabla^2_{yu}l(\hat y_i,f(\hat x_i))(\nabla^2_{uu}l(\hat y_i,f(\hat x_i)))^{-\frac{1}{2}}||^2_{(\Sigma_{\hat x\hat x}^i)^{-1}},$$ $$R_4(f)=\frac{1}{2n}\sum_{i=1}^n<\Sigma_{\hat y\hat y}^i,{\nabla^2_{yy}l(\hat y_i,f(\hat x_i))>}.$$

Then, Intra-Class Mixup can be seen as better utilizing data by adding regularization terms. From this perspective, it does not lead to a loss of information.

Moreover, many works [2] have shown that Mixup enhances the ability to utilize data rather than causing information loss. Based on these theoretical foundations and validated by the effectiveness of IntraMix in experiments, IntraMix does not lead to information loss.

Q3. The proposed method should contain sufficient information and the analysis should be proofed.

A3. Please refer to A2.

Q4. What is the advantage of the proposed method compared with GSL methods?

A4. Thank you for raising this question.

Our biggest advantage over GSL methods lies in training and deployment costs. GSL methods require learnable ways for graph topologies, leading to high training costs (e.g., GAUG[3] uses GAE for edge probabilities, and Nodeformer[4] uses differentiable ways). In contrast, as analyzed in Sec 3.4, IntraMix has very low time costs, making it more practical for deployment.

Secondly, we present comparative results with GSL methods.

We find that IntraMix outperforms current popular GSL methods due to its effective use of low-quality labels and efficient topology optimization.

Next, we incorporate a GAE in IntraMix, as detailed in [3].

While this improves performance, it adds training costs for GAE, 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, highlighting its potential for performance enhancement.

We hope the revised version better meets your expectations, if you can improve our score then we appreciate it.

Reference:

[1] Carratino, Luigi, et al. "On mixup regularization." Journal of Machine Learning Research 23.325 (2022): 1-31.

[2] Beckham, Christopher, et al. "On adversarial mixup resynthesis." Advances in neural information processing systems 32 (2019).

[3] Zhao, Tong, et al. "Data augmentation for graph neural networks." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 12. 2021.

[4] Wu, Qitian, et al. "Nodeformer: A scalable graph structure learning transformer for node classification." Advances in Neural Information Processing Systems 35 (2022): 27387-27401.

[5] Zou, Dongcheng, et al. "Se-gsl: A general and effective graph structure learning framework through structural entropy optimization." Proceedings of the ACM Web Conference 2023.

Thank you for your constructive comments and suggestions. Next is our response.

Q1.Why does the proposed method achieves better performance than NodeMixup?

A1. This is a great question. We discuss our advantages over NodeMixup in Sec 1, and Appendix E.2. We analyze the reasons in terms of accuracy and time complexity.

A1.1 Accuracy: We discuss Mixup and neighbor selection separately.

Mixup: According to Appendix B.1.2, Inter-Class Mixup cannot guarantee the noise reduction within each class, while NodeMixup, which primarily relys on Inter-Class Mixup, is more susceptible to label noise compared to IntraMix.

Neighbor Selection: NodeMixup uses neighborhood similarity as a similarity metric, but this fails because the generated data lack neighbors. IntraMix avoids this by selecting same-class nodes, enabling a cold start on generated data. Additionally, NodeMixup's selected nodes are overly similar, resulting in less information gain. In contrast, neighbors selected by IntraMix may not have high feature similarity, leading to greater information gain.

A1.2 Time complexity: As analyzed in Sec 3.4, our neighbor selection process has a time complexity of O(n) compared to NodeMixup's $O(n^2)$, where n is the number of augmented nodes. Thus, IntraMix has a time complexity advantage. We show experimental results below.

As observed, NodeMixup is much more costly than IntraMix, demonstrating IntraMix's cost superiority and greater advantage for large graphs, proving its general applicability.

Q2. The novelty of the proposed method is somehow limited as it is similar to NodeMixup.

A2. We believe that IntraMix represents a significant innovation, rather than just a minor improvement of NodeMixup. Next, we will discuss this.

Intra-Class Miuxp: The importance of IntraMix lies in its being the first work to seamlessly integrate Mixup into node-level learning, providing detailed experimental and theoretical analysis. Through IntraMix, we shift the perspective that Inter-Class Mixup is more important for node-level tasks. Previous works, including NodeMixup, primarily focused on Inter-Class Mixup. They involved a transplant of Mixup into the graph domain with little consideration of graph-specific characteristics. Through rigorous experiments and theorems, we show that the neglected Intra-Class Mixup, is indeed more suitable for node-level learning. This is important for the graph field as it explores a more promising and theoretically supported data augmentation way.

Neighborhood Selection: The innovation of our neighbor selection lies in using an efficient method to achieve superior results compared to previous computationally intensive ways. Details can be found in Sec 3.2. We naturally leverages the characteristics of Intra-Class Mixup to address a major challenge in applying Mixup to graphs—neighbor selection for generated data—and provides rigorous theoretical and experimental validation. Previous neighbor selection schemes, including NodeMixup, require significant costs. IntraMix achieves superior results in a more efficient way. Therefore, we consider our neighborhood selection method to be highly innovative. Moreover, it combines with Intra-Class Mixup to form a beautiful and effective data augmentation framework.

In summary, IntraMix exhibits significant innovation over NodeMixup. Its elegant design, rigorous proof, and extensive experiments challenge previous understandings of node-level data augmentation. This has important implications for graph machine learning and will inspire future research.

Q3. What are the values of $\eta$ when IntraMix achieves the best performance?

A3. This is a great question. We present the results on GIN and show the values of $\eta$ related to the best results, averaged over 10 runs.

According to Theorem 3.2, a larger $\eta$ reduces noise better. However, since learnable $\eta$ also affects the GNN's learning capability, isolating the optimal values for these two tasks is difficult. Thus, observing its value in relation to noise reduction is not very meaningful.

Q4. By saying "replacing ... with all-zero vector" do you mean that the node feature is a all-zero vector?

A4. We apologize for any confusion caused. Your understanding is correct. We conduct such experiments, showing that IntraMix's improvement is due not only to optimal topology but also to the nodes generated through Mixup.

Q5. Does IntraMix have better performance than Vanilla Mixup on the heterophilic graphs?

A5. This is a great question. We conduct experiments on four heterophilic graphs.

We find that IntraMix achieves stable improvements on heterophilic graphs, unlike Vanilla Mixup and NodeMixup, which degrade in performance. This is due to the critical role of neighbor selection in heterophilic data, where Vanilla Mixup and NodeMixup fail to identify suitable neighbors, leading to impacting performance. IntraMix contributes to information gain, as detailed in Appendix D.2, thus demonstrating its advantage on heterophilic graphs and general applicability.

We hope the response meets your expectations, if you can improve the score then we appreciate it.

Thank you for your constructive comments and suggestions. Next is our response.

Q1. The authors should clarify the distribution assumption on noises, since the constraint cannot be satisfied if $\epsilon_1,...\epsilon_{|C|}$ are i.i.d. Gaussian random variables.

A1. We apologize if our expression caused any confusion. We believe this issue does not exist. Firstly, $\epsilon_1+...\epsilon_{|C|}=0$ may not hold. Here, $\epsilon_{i}$ represents the noise when a node is classified into class i, and this noise varies across different classes. From eq. (17), We can derive that without other constraints, the sum is not necessarily 0. Secondly, $\epsilon_1, \ldots, \epsilon_{|C|}$ are not independent due to class relationships, and whether their sum is 0 does not affect our analysis. We will update details in our paper.

Q2. Theorem 3.1 should state line 128 using math equations for clarity.

A2. Thank you for pointing out this issue. We can express it as $P(\hat \epsilon<\epsilon)=\frac{2}{\pi} \arctan((\lambda^2+(1-\lambda)^2)^{-\frac{1}{2}})$, where $\hat \epsilon$ and $\epsilon$ represent the noise in the generated data and the original data, respectively.

Q3. Discuss how λ should be chosen based on theorem 3.1.

A3. This is a great question. In the ablation study (line 290-294), we discussed this. The result is that when $\lambda=0.5$, IntraMix performs best, which aligns with Theorem 3.1. Similar to Mixup, to introduce randomness for better results, we set $\lambda$~B(2,2), where B denotes the Beta Distribution. $\lambda$ is around 0.5. Next, we provide more results.

It can be observed that the best results are achieved when $\lambda$ is around 0.5, which aligns with our analysis.

Q4.Theorem 3.2: The first sentence should be clearly stated as an assumption.

A4. Thank you for pointing out our imprecise expression. We will correct it.

Q5. I'm suspicious about the correctness of the theorem 3.2. For example, if $\eta_1=\eta_2=-\frac{1}{8(1+\lambda^2+(1-\lambda)^2)}-1$, the formula in line 164 is wrong.

A5. This is a great question, but $\eta_1$ and $\eta_2$ are learnable parameters, and $\eta$ is typically positive. If $\eta<0$, it would imply that a node's own features negatively impact its classification, which is illogical. Such a situation would likely indicate issues with the dataset or training. Since $\eta<0$ does not typically occur, the values you mentioned would not arise.

Q6. It's not clear what inductive learning setting and supervised learning setting are and why they are important.

A6. Thank you for identifying this issue. Next, we will introduce them.

Inductive learning. In node-level tasks, the common setting is transductive, where the test distribution is known during training, fitting many static graphs. Inductive learning refers to not knowing the test distribution during training. Since many real-world graphs are dynamic, inductive learning is also crucial. For inductive learning settings, we use the subgraph composed of training data for training, as referenced in Section 4.3 of [1].

Supervised learning. Although graphs typically adhere to semi-supervised settings, some graphs, like citation networks, have enough labels. Therefore, we conduct supervised experiments to show that IntraMix is feasible not only in scenarios with scarce labels but also in those with sufficient labels, proving its generality. The setting involves using enough training labels, with details provided in Appendix C.1.

Q7. The experiment section needs to state the way that the pseudo labels are generated and the cost of doing so.

A7. Thank you for identifying this issue. The pseudo-labeling method involves training a GNN $f$ with scarce labeled data and using $f$ to get pseudo labels for unlabeled data, as referenced in [2]. We further train $f$ with the augmented data. The additional cost for pseudo-labeling is small; overall, we train only one model, and the combined cost of pre-training and training with augmented data does not greatly exceed normal training cost. We analyze the time complexity in Sec 3.4, and will update a detailed discussion.

Q8. Line 91: Current definition implies that $|D_l|=|D_u|$, which is not general enough.

A8. We apologize for the confusion caused by our expression; we will revise it in our paper. Typically, $|D_l| << |D_u|$, where $D_l$ denotes the set of labeled nodes and $D_u$ is the unlabeled node set.

Q9. Line 146: dropout rates → dropout probabilities；Line 169: lines 1 → line 1.

A9. Thank you for pointing out these issues. We will correct them.

Q10. Does Eq. (5) mean that for any $(\hat x,y)∈D_m$ and any $(\hat x_i,y)∈D_m$, $\hat x$ and $x_i$ are connected? And the authors need to state how to select and generate new edges.

A10. We apologize for the confusion caused by our expression. We establish edges between $(\hat x, y) \in D_m$, and $(x, y) \in D_h$. Here, $D_m$ is the set of data generated by IntraMix. $D_h$ is the high-quality pseudo-label set, with the generation way in Eq. (4). For each node in $D_m$, we randomly choose some nodes from $D_h$ with the same label as neighbors by directly connecting them.

We hope the revised version better meets your expectations, if you can improve the score then we appreciate it.

Reference:

[1] Liu, Songtao, et al. "Local augmentation for graph neural networks." International conference on machine learning. PMLR, 2022.

[2] Lee, Dong-Hyun. "Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks." Workshop on challenges in representation learning, ICML. Vol. 3. No. 2. 2013.

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.