Rethinking Semi-Supervised Imbalanced Node Classification from Bias-Variance Decomposition

Summary

The paper studies imbalanced node classification problem and propose a novel perspective to understand graph imbalance via bias-variance decomposition.By leveraging graph data augmentation, the paper develops a regularization technique to approximate the model's variance. The effectiveness of the method is evaluated across multiple settings and datasets, where the proposed method largely outperforms the compared baselines.

Strengths

- The idea is novel and has solid theoretical motivation. - Strong performance improvement + extensive experiments. - The paper is clearly written and well-structured.

Weaknesses

- As someone not working directly in the same field, I think it would be very helpful if the related work section could be more comprehensive than its current shape. Plus, the method design in Sec. 4 shares similarity with many existing techniques. For example, the "confidence-based label-guided consistency regularization" in Eq. 8 has been widely used in standard semi-supervised learning (UDA, FixMatch, FlexMatch) for a long time. And the idea of intra-class aggregation for contrastive learning is also studied in Supervised Contrastive Learning paper. IMHO, it would be better if the paper could discuss the difference with them and tune down accordingly, which does not harm the originality of this paper. Unconfident comments: - I appreciate the analysis on that overall variance increases with the increase of imbalance ratio. But it is a bit surprising there was not any analysis like this before even in the field of long-tailed recognition. Could the authors please comment on this?

Questions

- What value does "v" at Line 208 take? Is it a fixed value across the training or it is dynamically adapted? - What does it mean in Sec. 2.2 that "We randomly mask node properties"? Does it mean dropping nodes and the corresponding edges of the original graph at random? Is this a standard way of performing data augmentation on graph? What are other alternative data augmentation methods? It would be great if the authors could give more information on this either in Sec. 2.2 or in related work.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

None

Summary

This paper is majoring on the imbalance problem in graph node classification. The authors confirmed the relationship between model variance and the degree of dataset imbalance by adopting the Bias-Variance Decomposition. Furthermore, they diverted a regularization term for approximating the variance of the model from the above theoretical analysis.

Strengths

This paper discovers the relation between imbalance and variance, estimates the variance with graph argumentation, and solves the imbalance problem by adopting two proposed regularization terms, which is an important problem in node classification. The regularization term is theoretically derived from the Bias-variance Decomposition, and the author, for the first time, fits this theory into the field of imbalance by making two weak assumptions, which is a good contribution to this field.

Weaknesses

- Overall, this paper contains many typos and abuse of the notation that may make the reader uncomfortable. I list those points in the limitations. - In this work, the authors make a strong assumption that all embeddings follow the multivariate normal distribution with the same sample variance ($h(x)^T\Lambda^ih(x)$ in the paper) between each class. And the authors use this assumption to derive the core relation between variance and imbalance, then the regularization term. However, this assumption is strongly related to the quality of the extracted embeddings. One important guarantee for this assumption is a well-trained feature extractor with a clear boundary between each class. However, at the initial stage, the model is not well-trained, meaning that a large variance of $h(x)^T\Lambda^ih(x)$ in each class. It is unclear how this will affect the power of regularization though the overall results look good, and the authors did not make a discussion of the above problem in the paper.

Questions

1. Why do the authors assume node embeddings follow the multivariate normal distribution? 2. Could the authors provide the significance of the results in Fig1 (e.g., using hypothesis testing)?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The author could improve their manuscript by solving the below points and typos: - line 25-27: sentence should be shortened. - line 76: no definition for $N$, $F$ and $D$. - Section 3.1: Is there a lack of citations of Bias-variance Decomposition? - The term between Eq(2) and line 111, line 114 is different. - line 140: "condition on" should be replaced by "conditioning on". - line 208: indicator function is often denoted as $\\mathbf{1}_{ \\{ \\cdots \\} }$.

Summary

This paper focuses on semi-supervised imbalanced node classification tasks. Specifically, the authors first establish a theoretical result that connects the imbalance ratio with the model variance and then propose a new regularization term related to the variance based on the graph augmentation technique. Experimental results show the effectiveness of the proposal.

Strengths

1. The authors give theoretical results that connect the imbalance ratio to the model variance. The results are insightful. 2. The experimental results show the proposal can achieve the SOTA performance on various class-imbalanced datasets.

Weaknesses

1. The theoretical results rely on strong assumptions, which may be difficult to satisfy in real-world tasks. 2. From Figure 3, it looks like the performance is highly influenced by the hyper-parameters. So how to determine the hyper-parameter should be discussed in the paper. 3. Moreover, I doubt that the performance of the proposal is not related to the theoretical results, it may rely on graph augmentation. Thus, more ablation studies should be conducted.

Questions

1. How to determine the hyper-parameters in different datasets? 2. How to demonstrate the superiority of algorithm performance is related to theoretical results?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

Summary

This paper introduces a new approach to address the issue of class imbalance in graph neural networks (GNNs) for learning on graph-structured data. It also provides a novel theoretical perspective for addressing the problem of imbalanced node classification in GNNs.

Strengths

1 The article is well written and easy to understand. 3 The authors prove their claim by theoretical derivation. 4 The experimental results further corroborate the authors' view.

Weaknesses

1 The use of L to represent the set of labeled nodes is still relatively rare in the definition of graphs, and the authors are advised to describe the definition involved further in the opening paragraph of the method. 2 Is the authors considering restructuring the article? Putting the theoretical derivation before the introduction of the method may not give the reader a good reading experience. 3 I am curious about this one: the authors point out that the full graph noise distribution is taken into account when sampling the graph in order to sample the training set that has approximate variance. However, if one considers graph learning in an open world, then the noise from the added data might be quite different from the original graph data. 4 In Table 1, the authors can consider further reporting the percentage of performance improvement compared to SOTA. 5 In Fig 3(a), it seems that the performance improvement from VR loss is not significant. Are you considering the Sup+VR combination? Also, can you further diet why VR loss gives a smaller boost to GAT?

Questions

No more questions.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

This paper proposes a theory that relates data imbalance to model variance and designs a method to mitigate the bias of class imbalance. For the theory, this paper finds that the variance of each class is proportional to the invert of the number of samples in that class. For the method, this paper uses a regularization term to approximate the model variance and construct a varied training distribution with graph augmentation. The regularization term is added to the original loss function. Results on public-split datasets and naturally imbalanced datasets verify the proposal.

Strengths

This paper first connects the model variance and class imbalance in graph learning.

Weaknesses

1. L_IR objective is more closely related to variance than contrastive learning. It would help to clarify the difference between your work and contrastive graph learning. 2. This paper does not discuss previous work on variance and imbalance in traditional imbalanced learning. Since the variance calculated in this paper does not use graph-specific settings, it is not unique to graph learning.

Questions

1. Why can you assume that node embeddings follow a multivariate normal distribution? 2. Many elements of Figure 2 need descriptions. E.g., What do yellow and blue circles mean?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

1 poor

Limitations

This paper does not discuss limitations. But I think the novelty and unique contribution is limited.

I'll raise my score.

The authors clearly addressed my concern. Thus, I will raise my score as 6.

Further Clarification (1/2) about the Underlying Assumptions of this Work for Reviewer bhDb, j7Kz

## Assumptions that node embeddings follow a multivariate normal distribution - **Standing on the Shoulders of Giants:** The adoption of the multivariate normal distribution assumption is primarily anchored in the Central Limit Theorem (CLT). We can notice there already have influential works [1, 2, 3, 4, 5, 6] in the GNN domain that have similarly leveraged this assumption for their theoretical analyses and derivations, a few of which we have enumerated in our manuscript (as referenced). We have duly cited these pioneering works in the appropriate sections in our revised version, thus ensuring that our adoption of this assumption does not appear arbitrary or unwarranted. [1] Hajiramezanali, Ehsan, et al. "Variational graph recurrent neural networks." Advances in neural information processing systems 32 (2019). [2] Shi, Min, et al. "Multi-class imbalanced graph convolutional network learning." Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20). 2020. [3] Chen, Kaixuan, et al. "Distribution knowledge embedding for graph pooling." IEEE Transactions on Knowledge and Data Engineering (2022). [4] Funke, Thorben, et al. "Low-dimensional statistical manifold embedding of directed graphs." arXiv preprint arXiv:1905.10227 (2019).'' [5] Cavallari, Sandro, et al. "Learning community embedding with community detection and node embedding on graphs." Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2017. [6] Xu, Mengjia. "Understanding graph embedding methods and their applications." SIAM Review 63.4 (2021): 825-853. *** - **Striking a Balance:** We acknowledge that this assumption might not mirror the intricate realities perfectly. However, it offers a means to streamline our theoretical framework. Building on this foundation, we introduced Lemma 1, which provides our $L_{VR}$ loss term, acting as the model's variance estimation component. *** - **Empirical Validation:** In light of the discussions, we've undertaken a more comprehensive ablation study during the rebuttal phase. This study sheds light on the efficacy of the model variance estimation term derived from this assumption. We believe our findings will underscore its merit and the practical relevance of the choices we've made. | | **Dataset** | **CiteSeer-Semi** | **PubMed-Semi** | **Computers-Semi** | |:-----------------------:|:--------------------:|:----------------------:|:----------------------:|:----------------------:| | **SAGE** | | F1-Score(%) | F1-Score(%) | F1-Score(%) | | | Sup | 44.43 | 64.80 | 77.16 | | | Sup+IR | 60.92 | 68.35 | 78.62 | | | Sup+VR | 62.33 | 73.68 | 79.54 | | | Sup+IR+VR | 64.91 | 76.44 | 80.40 | | **GAT** | | | | | | | Sup | 48.08 | 65.91 | 74.04 | | | Sup+IR | 65.35 | 67.04 | 74.35 | | | Sup+VR | 65.67 | 72.87 | 77.65 | | | Sup+IR+VR | 65.70 | 74.46 | 78.12 | | **GCN** | | | | | | | Sup | 43.98 | 62.28 | 73.54 | | | Sup+IR | 53.94 | 66.16 | 76.32 | | | Sup+VR | 57.43 | 72.34 | 77.09 | | | Sup+IR+VR | 59.73 | 74.48 | 78.49 |

Further Clarification on Q4 of Reviewer 8yVE.

## 1. Explanation of Randomly Masking Node Properties - "Randomly masking node properties" [1,2,3,4,5] does not refer to randomly dropping nodes and the corresponding edges of the original graph. Instead, it's a data preprocessing technique that involves randomly replacing or hiding specific attributes of certain nodes within the graph. This process is typically used during the training phase and helps the model learn to extract useful information from incomplete or partially corrupted data. [1] You, Yuning, et al. "Graph contrastive learning with augmentations." Advances in neural information processing systems 33 (2020): 5812-5823. [2] Zhao, Tong, et al. "Data augmentation for graph neural networks." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 12. 2021. [3] Zhao, Tong, et al. "Graph data augmentation for graph machine learning: A survey." arXiv preprint arXiv:2202.08871 (2022). [4] Ding, Kaize, et al. "Data augmentation for deep graph learning: A survey." ACM SIGKDD Explorations Newsletter 24.2 (2022): 61-77. [5] Zhou, Jiajun, Jie Shen, and Qi Xuan. "Data augmentation for graph classification." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020. *** ## 2. Is this a Standard Way of Performing Data Augmentation on Graph? - Randomly masking node properties can be considered a data augmentation method, particularly in the training of Graph Neural Networks (GNNs). By presenting the model with some masked or perturbed node information, it can enhance the robustness and generalization ability of the model. *** ## 3. What are Other Alternative Data Augmentation Methods? In addition to randomly masking node properties, there are many other methods [1,2,3,4,5,6,7,8] for data augmentation in graphs, including but not limited to: - Node/Edge Perturbation: Altering the graph's structure by randomly adding or removing some nodes or edges. - Subgraph Sampling: Randomly sampling subgraphs from the original graph for use as training samples. - Feature Noise Addition: Adding random noise to the features of nodes or edges. - Graph Rotation and Reflection: Applying geometric transformations like rotation and reflection to the graph structure. - Adjacency Matrix Perturbation: Changing the connectivity of the graph by altering the weights of the adjacency matrix. These methods can be used independently or in combination to enrich the training data and enhance the model's robustness and generalization performance. **We will expand on these points in detail in either Sec. 2.2 or in the related work section, to provide a more comprehensive background and explanation.** Thank you again for your valuable feedback! [1] You, Yuning, et al. "Graph contrastive learning with augmentations." Advances in neural information processing systems 33 (2020): 5812-5823. [2] Zhao, Tong, et al. "Data augmentation for graph neural networks." Proceedings of the aaai conference on artificial intelligence. Vol. 35. No. 12. 2021. [3] Zhao, Tong, et al. "Graph data augmentation for graph machine learning: A survey." arXiv preprint arXiv:2202.08871 (2022). [4] Ding, Kaize, et al. "Data augmentation for deep graph learning: A survey." ACM SIGKDD Explorations Newsletter 24.2 (2022): 61-77. [5] Zhou, Jiajun, Jie Shen, and Qi Xuan. "Data augmentation for graph classification." Proceedings of the 29th ACM International Conference on Information & Knowledge Management. 2020. [6] Zhu, Yanqiao, et al. "Graph contrastive learning with adaptive augmentation." Proceedings of the Web Conference 2021. 2021. [7] Liu, Yixin, et al. "Graph self-supervised learning: A survey." IEEE Transactions on Knowledge and Data Engineering 35.6 (2022): 5879-5900. [8] Zhao, Tong, et al. "Graph data augmentation for graph machine learning: A survey." arXiv preprint arXiv:2202.08871 (2022).

We've Carefully Addressed Each of the Questions You Raised and Eagerly Hoping for Your Valuable Feedback

Dear Reviewer bhDb, Thank you profoundly for your insightful review and invaluable feedback. We have earnestly considered each query you posed and have addressed them in depth where necessary. We genuinely hope that you will take some time to review our detailed responses, confident that they address your concerns. Your expertise and the time you've invested in reviewing our work are deeply appreciated by us. Warm Regards, Authors

We've Carefully Addressed Each of the Questions You Raised and Eagerly Hoping for Your Valuable Feedback

Dear Reviewer vtyV, From the bottom of our hearts, we thank you for your kind and insightful review. Each question you brought up has been tenderly considered, and we've endeavored to provide comprehensive answers where necessary. We warmly invite you to take a moment to go through our responses, hoping they resonate with your thoughts. The time and wisdom you've shared in reviewing our work touches us deeply. Warm Regards, Authors

We've Carefully Addressed Each of the Questions You Raised and Eagerly Hoping for Your Valuable Feedback

Dear Reviewer j7Kz, From the depths of our hearts, we express our sincerest gratitude for your thoughtful and perceptive review. Every question you posed has been carefully contemplated, and we've strived to offer thorough answers where appropriate. We cordially invite you to peruse our responses, with the hope that they align with your insights. The time and wisdom you've invested in reviewing our work profoundly moves us. Warm Regards, Authors