Label Informativeness-based Minority Oversampling in Graphs (LIMO)

Authors: Rishav Das, Sikta Mohanty, Rucha Bhalchandra Joshi, Subhankar Mishra
Primary area: learning on graphs and other geometries & topologies
Keywords: class imbalance, graph neural networks, mutual information, label informativeness

Abstract:
Class imbalance is a pervasive issue in many real-world datasets, particularly in graph-structured data, where certain classes are significantly underrepresented. This imbalance can severely impact the performance of Graph Neural Networks (GNNs), leading to biased learning or over-fitting. The existing oversampling techniques often overlook the intrinsic properties of graphs, such as Label Informativeness (LI), which measures the amount of information a neighbor's label provides about a node's label. To address this, we propose Label Informativeness-based Minority Oversampling (LIMO), a novel algorithm that strategically oversamples minority class nodes by augmenting edges to maximize LI. This technique generates a balanced, synthetic graph that enhances GNN performance without significantly increasing data volume. Our theoretical analysis shows that the effectiveness of GNNs is directly proportional to label informativeness, with mutual information as a mediator. Additionally, we provide insights into how variations in the number of inter-class edges influence the LI by analyzing its derivative. Experimental results on various homophilous and heterophilous benchmark datasets demonstrate the effectiveness of LIMO in improving the performance of node classification for different imbalance ratios, with particularly significant improvements observed in heterophilous graph datasets. Our code is available at \url{https://anonymous.4open.science/r/limo-12CC/}

Decision: reject
Reviewer scores: 5, 6, 3, 5, 5

Reviews and discussion:
<thread>
creation date:
1730101208268

thread_type:
official_review

<thread_object>
creator: reviewer_c2ac

<content>
summary:
This paper investigates class imbalanced graph representation learning, where certain classes have significantly fewer nodes. Ignoring such kind of information will result in biased learning or overfitting. The authors claim that existing oversampling techniques overlook the label informativeness of the graphs, which measures the amount of information regarding to its neighbor’s labels. To this end, the authors propose LIMO to oversample minority class nodes by maximizing LI. Synthetic node features are generated with SMOTE, then edges are added by analyzing the derivative of its LI. Comprehensive experiments on both homophilous and heterophilous datasets demonstrate that the proposed model can outperform recent baselines under different imbalance ratios.

strengths:
1.	The paper is generally well-written and easy to understand, meanwhile, the results appear to be promising.

2.	Experiments are conducted on both homophilous and heterophilous datasets, which broadens its application. 

3.	Various ablation studies are given to show the impacts of the synthesized nodes and generated edges.

weaknesses:
1.	The calculation of $t$ value given in Theorem 1 is not rigorous, since the authors explore it in a certain range using predefined steps, which might not be the optimal value. The proof of Theorem 2 is also not convincing.

2.	The chosen baselines are too old, and some key baselines are not discussed and compared, e.g., GraphENS, and GraphSHA, etc.

3.	No time and space complexity analyses are given to show the efficiency of the proposed model.

questions:
1.	The calculation of $t$ value given in Theorem 1 is not rigorous, since the authors explore it in a certain range using predefined steps, which might not be the optimal value. The proof of Theorem 2 is also not convincing.

2.	The chosen baselines are too old, and some key baselines are not discussed and compared, e.g., GraphENS [1], and GraphSHA [2], etc.

3.	No time and space complexity analyses are given to show the efficiency of the proposed model. 

4.	The authors claim that the proposed model does not significantly increase the data volume. However, the authors synthesize nodes and edges in the graph, which indeed increases the data volume.

5.	The caption in Figure 1 does not provide any information, and the authors did not cite references appropriately. For instance, SMOTE was not cited upon its first mention. 

6.	What labels are used in the Amazon datasets? The original datasets do not include labels for the user nodes.


References:

[1] Park J, Song J, Yang E. Graphens: Neighbor-aware ego network synthesis for class-imbalanced node classification[C]//International conference on learning representations. 2021.

[2] Li W Z, Wang C D, Xiong H, et al. Graphsha: Synthesizing harder samples for class-imbalanced node classification[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 1328-1340.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730181056071

thread_type:
official_review

<thread_object>
creator: reviewer_3wuc

<content>
summary:
This paper presents LIMO, an algorithm designed to tackle class imbalance in graph data. It works by adding synthetic edges between minority class nodes to increase Label Informativeness. It aims to improve the performance of GNNs on imbalanced datasets without significantly increasing the volume of data. The authors provide theoretical analysis and experimental results, showing LIMO outperforms existing methods, especially on heterophilous graphs.

strengths:
* The paper is well-written and easy to understand.
* The paper focuses on the problem of class imbalance, a critical issue in many real-world applications.
* Rich experiments have been conducted on a variety of datasets, examining different aspects.

weaknesses:
* The paper lacks a discussion of several recent and relevant baselines for addressing class imbalance in graphs. Notably, recent methods such as GraphENS [1], TAM [2], and GraphSHA [3] are not included in the experimental comparisons.
* The theoretical proof with t=1.31167628 is derived from simulation, but the paper does not provide a detailed explanation or justification of the simulation settings used. This lack of transparency limits the reliability of this theoretical result.
* While the paper theoretically claims that LI is directly proportional to GNN accuracy, experimental results do not consistently support this. For instance, in Figure 9, the correlation between LI and accuracy weakens when added_fraction > 0.5, especially at fraction = 0.75, where no strong positive correlation is observed.

[1] Park, J., Song, J., & Yang, E. (2021). Graphens: Neighbor-aware ego network synthesis for class-imbalanced node classification. In International conference on learning representations.
[2] Song, J., Park, J., & Yang, E. (2022, June). TAM: topology-aware margin loss for class-imbalanced node classification. In International Conference on Machine Learning (pp. 20369-20383). PMLR.
[3] Li, W. Z., Wang, C. D., Xiong, H., & Lai, J. H. (2023, August). Graphsha: Synthesizing harder samples for class-imbalanced node classification. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1328-1340).

questions:
* In the experiments, what does the imbalance ratio represent specifically set within the range of 0.1 to 0.6?
* Different dataset seems to show different performance. For example, in Table 10 when imbalance ratio = 0.1/0.2, while the LI of LIMO is the largest, the performances of RW and GS are better. Why?
* The experiment results can be further explained. For instance, in Figures 5 and 10, no significant correlation is observed once the fraction exceeds 0.25. Additionally, in Table 8, when the imbalance ratio is set to 0.1, ACC and F1-Score remain the same across four baseline methods.
* It is unclear whether the effectiveness stems more from well-synthesized node features or from the generated edges. Which one is more important? What are the appropriate $\delta$ values for interpolating node features?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730453070817

thread_type:
official_review

<thread_object>
creator: reviewer_z2eq

<content>
summary:
To alleviate the class-imbalanced issue, this paper propose a novel algorithm,  Label Informativeness-based Minority Oversampling (LIMO), aiming to strategically synthesize minority nodes by augmenting edges to maximize label informativeness. And the experiments conducted on various homophilous and heterophilous benchmark datasets show the improvements compared with the baselines.

strengths:
1. The paper is easy-to-follow.

weaknesses:
1. The novelty is limited. It seems just simply inject SMOTE with label informativeness, however, the label informativeness is borrowed from previous work without clear explanation. Specifically, what is the meaning of the definition of LI in Eq.2? What situation will the LI(G) increase? And when will LI(G) decrease? More importantly, how does LI(G) influence the performance of class-imbalanced learning?

2. This paper fails to demonstrate its strengths compared with previous works. In lines 81-87, the authors claim that the proposed method take label informativeness to handle class-imbalanced issue. But  they fail to illustrate the limitations of previous works, and how the proposed method can tackle the limitations? Why does the previous works, like GraphSMOTE [1], GraphENS[2] and TAM[3], can not improve the label informativeness? What is the strengths of LIMO compared with these methods?

3. In line 152, during the node generation, LIMO need to find "its nearest neighbor $u$ in the same class". Does node $u$ belong to the labeled training set or the unlabeled nodes? If it comes from the training set, will it lead to overfitting when the number of minority classes is too small? If $u$ is an unlabeled node, how to get a reliable pseudo-label in the class-imbalanced scenario?

4. Lack of complexity analysis of the proposed method. In lines 11-13 of Algorithm 1, for each minority node $v$, LIMO need to determine the edge between $s$ and $w$, and $w \in \mathcal{V}-\{v\}$. The computation cost seems pretty high.

5. In line 216, "Specifically, it suggests that enhancing the connectivity between classes (increasing inter-class edges) can improve the informativeness of the labels". This conclusion seems to contradict graph homophily  [4] (the foundation of GNN), i.e., the connected nodes often come from the same class. In my opinion, we always want to add edges between two nodes from the same class, so that the nodes can aggregate more information from the same class, thus helping the node classification, just like GraphSMOTE[1] does. I have some doubt about the conclusion of line 216.

6. In addition, the baselines is out-of-date, there are many related works should be taken into comparison, for example, the oversampling methods like GraphENS[2] and GraphSHA[5], the pseudo-labeling method like GraphSR[6] and the loss adjustment method TAM[3].  The experimental setup is inappropriate.  In line 729, "When the minority class had fewer than three nodes, we allocated one node each for training, validation, and testing.",  It is unreasonable to have only one node for validation and testing. Why is the experimental setting not consistent with the previous method?



[1] Zhao T, Zhang X, Wang S. Graphsmote: Imbalanced node classification on graphs with graph neural networks[C]//Proceedings of the 14th ACM international conference on web search and data mining. 2021: 833-841.

[2] Park J, Song J, Yang E. Graphens: Neighbor-aware ego network synthesis for class-imbalanced node classification[C]//International conference on learning representations. 2021.

[3] Song J, Park J, Yang E. TAM: topology-aware margin loss for class-imbalanced node classification[C]//International Conference on Machine Learning. PMLR, 2022: 20369-20383.

[4] McPherson M, Smith-Lovin L, Cook J M. Birds of a feather: Homophily in social networks[J]. Annual review of sociology, 2001, 27(1): 415-44

[5] Li W Z, Wang C D, Xiong H, et al. Graphsha: Synthesizing harder samples for class-imbalanced node classification[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023: 1328-1340.

[6] Zhou M, Gong Z. GraphSR: a data augmentation algorithm for imbalanced node classification[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(4): 4954-4962.

questions:
See weakness.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730473446471

thread_type:
official_review

<thread_object>
creator: reviewer_11yk

<content>
summary:
The authors propose a new method for resolving class imbalances in graph-structured data based on a labeled informativeness-based minority oversampling method, called LIMO. By increasing the edges in a way that maximizes the amount of label information, LIMO strategically samples nodes of minority classes. And satisfactory results are obtained in node categorization dataset.

strengths:
1. The authors propose Label Informativeness-based Minority Oversampling and theoretically establish the relationship between label informativeness and model prediction accuracy in GNN.   
2. The authors analyze the effect of variation in the number of inter- and intra-class edges on LI.   
3. The manuscript is logical and well-structured. The methodology section is clearly presented.

weaknesses:
1. At the end of the first section, the authors show LIMO only in the figure, but there is no corresponding textual description in the text.
2. The currently proposed Label Informativeness-based Minority Oversampling (LIMO) approach is indeed a novel idea to solve the graph imbalance problem, but the core differences with existing approaches can be further highlighted in the introduction section or related work section such as 10.1109/IJCNN60899.2024.10650494, 10.1109/ICASSP48485.2024.10448064.  
3. Discussion on the generalizability of LIMO is lacking in the manuscript, the authors only validate the performance effect of LIMO in GraphSAGE and lack discussion on LIMO in other GNNs such as Graph Convolutional Networks (GCN), Graph Attention Networks (GAT/ GAN). The authors need to provide a theoretical discussion of how LIMO might be generalized to other GNN architectures, or validated experimentally.  
4. The experimental results are not comprehensive enough, and oversampling methods that specifically address the problem of graph data imbalance are missing from the comparison methods. Therefore, it is suggested that the authors should add methods that target graph data correlation in the experimental section, e.g., 10.1109/IJCNN60899.2024.10650494, 10.1109/ICASSP48485.2024.10448064.
5. Although the authors mention the inherent cost of the LIMO approach in generating and evaluating new edges in the summary section, the authors do not mention whether the added computational cost is within an acceptable range. The authors should provide actual runtime comparisons between LIMO and baseline methods, or a theoretical complexity analysis.

questions:
1. Compared to existing oversampling methods based on graph data, what research gaps are addressed by the method proposed in this paper?  
2. The authors proved Theorem 1 in the manuscript. Still, I am more interested in whether the variation of t for different problems affects the results of the experiments and how the optimal value of t is determined.
3. Is there a generalization of sacrificing significant computational cost to improve computational accuracy?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730693740556

thread_type:
official_review

<thread_object>
creator: reviewer_9twm

<content>
summary:
The paper presents an oversampling technique for imbalance classification in graph classification settings. The method is based on the label informativeness as the criteria to augment the minority class samples. The method started with the regular non-graph SMOTE technique for generating new samples. Then it uses LI criteria to determine which nodes are connected to the new samples, in such a way that maximizes the LI criteria. The authors then demonstrate the performance of the proposed model in the real experiments.

strengths:
1. Interesting ideas on using label informativeness to help tacking imbalance dataset.
2. The is built on top of SMOTE, a well known upsampling technique, and augment it to graph setting.
3. The experiments demonstrate the claimed benefit of the proposed approach.

weaknesses:
1. Presentation. In many places, terminologies/abbreviations/symbols/equations are used without explaining them. For examples:
    - “IR”. (Page 2)
    - “SMOTE”. (Page 3)
    - “Eq (6)”. (Page 4)
    - “Eq (7)”. (Page 4)
    - etc
2. Motivation. The motivation behind using LI for upsampling is not explained clearly. Why is using LI a good idea to do upsampling? Why is having high LIs desirable? etc.
3. Soundness. The data augmentation by creating new nodes with new features using SMOTE technique makes sense. However, the way the proposed method augments the edges by attaching the new nodes to potentially unrelated nodes (not a neighbor of the original node), does not necessarily make sense. I get that the goal is to improve the LI metric. However, edges in the original graph represent certain relationship patterns. Attaching the new nodes to unrelated nodes will create new relationship patterns that do not exist in the original graph. These relationship patterns in the graph are something that is not yet explored by the model.

questions:
1. Please address the weaknesses mentioned above.
2. In the evaluation, is the accuracy of the prediction computed using the augmented graph (after upsampling), or is it just based on the original graph?
</content>
</thread_object>

</thread>
<thread>
creation date:
1733154939249

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers, 

We thank you for taking time to review our paper. In response to your valuable feedback, we have revised the manuscript accordingly and conducted additional experiments to address the points raised. These changes have been carefully documented, and we believe your insights have significantly enhanced the quality of our work.

Should you have any further comments or suggestions, we would be most grateful to hear them. We appreciate your time and look forward to hearing from you.

Thank you.

Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1733302299586

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers and Area Chairs,

As the discussion period nears its conclusion, we would like to bring to your attention the significant revisions and improvements made to our manuscript in response to the reviewers’ feedback.

First, we would like to emphasize that all the points raised by the reviewers were addressable, and we have revised the manuscript accordingly. Specifically, we conducted additional experiments to benchmark our approach, LIMO, against state-of-the-art methods, including GraphSHA. These results, now included in the revised manuscript, demonstrate that LIMO consistently outperforms GraphSHA across various datasets and tasks.

While we understand that the initial version of our manuscript received low scores, these scores do not take into account the substantial updates made in the revised version. Furthermore, during the discussion period, we received comments from only one out of the five reviewers, leaving us uncertain whether the improvements have been fully evaluated.

ICLR provides authors with a unique opportunity to revise their submissions in response to reviewer feedback, setting it apart from many other conferences. We have taken this opportunity seriously and have addressed all the reviewers' concerns to the best of our ability. The revisions include new experimental results, clarifications to the methodology, and improvements in presentation, all of which are highlighted in blue in the revised manuscript for ease of review.

We kindly request that the Area Chair and reviewers consider the revised paper and our detailed responses before making a final decision. If the paper is ultimately rejected, we would deeply appreciate constructive feedback specific to the revised version. This will help us refine the work further and avoid resubmitting what has already been improved here.

Thank you for your time, feedback, and consideration.

Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper received five reviews with ratings of 5, 6, 3, 5, and 5. The reviewers raised several major concerns regarding the paper, including limited novelty, insufficient experimental evaluation with outdated baseline methods, unclear motivation and discussion regarding the contributions of LIMO, lack of complexity analysis, and insufficient clarity in the presentation. Despite the authors’ rebuttal, the reviewers remained unconvinced and retained their initial ratings. Consequently, this paper is recommended for rejection.