# GraphSB: Boosting Imbalanced Node Classification on Graphs through Structural Balance

arXiv: https://arxiv.org/abs/2511.10022 · HTML: https://mlsanity.com/paper/2511.10022/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 56 references that are in the map.
- First posted on arXiv 13 Nov 2025.

## Builds on (most cited first, 29 of 29)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks](https://mlsanity.com/paper/2103.08826/) (2021)
- [G-Mixup: Graph Data Augmentation for Graph Classification](https://mlsanity.com/paper/2202.07179/) (2022)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Generative Adversarial Minority Oversampling](https://mlsanity.com/paper/1903.09730/) (2019)
- [Deep Over-sampling Framework for Classifying Imbalanced Data](https://mlsanity.com/paper/1704.07515/) (2017)
- [Topology-Imbalance Learning for Semi-Supervised Node Classification](https://mlsanity.com/paper/2110.04099/) (2021)
- [ImGAGN:Imbalanced Network Embedding via Generative Adversarial Graph Networks](https://mlsanity.com/paper/2106.02817/) (2021)
- [TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2206.12917/) (2022)
- [Class-Imbalanced Graph Learning without Class Rebalancing](https://mlsanity.com/paper/2308.14181/) (2023)
- [Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification](https://mlsanity.com/paper/2304.05059/) (2023)
- [Modularity-Aware Graph Autoencoders for Joint Community Detection and Link Prediction](https://mlsanity.com/paper/2202.00961/) (2022)
- [GraphSR: A Data Augmentation Algorithm for Imbalanced Node Classification](https://mlsanity.com/paper/2302.12814/) (2023)
- [GraphSHA: Synthesizing Harder Samples for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2306.09612/) (2023)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [RA-GCN: Graph Convolutional Network for Disease Prediction Problems with Imbalanced Data](https://mlsanity.com/paper/2103.00221/) (2021)
- [Rethinking Semi-Supervised Imbalanced Node Classification from Bias-Variance Decomposition](https://mlsanity.com/paper/2310.18765/) (2023)
- [IceBerg: Debiased Self-Training for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2502.06280/) (2025)

## Abstract (arXiv)

Imbalanced node classification is a critical challenge in graph learning, where most existing methods typically utilize Graph Neural Networks (GNNs) to learn node representations. These methods can be broadly categorized into the data-level and the algorithm-level. The former aims to synthesize minority-class nodes to mitigate quantity imbalance, while the latter tries to optimize the learning process to highlight minority classes. However, neither category addresses the inherently imbalanced graph structure, which is a fundamental factor that incurs majority-class dominance and minority-class assimilation in GNNs. Our theoretical analysis further supports this critical insight. Therefore, we propose GraphSB (Graph Structural Balance), a novel framework that incorporates Structural Balance as a key strategy to address the underlying imbalanced graph structure before node synthesis. Structural Balance performs a two-stage structure optimization: Structure Enhancement that adaptively builds similarity-based edges to strengthen connectivity of minority-class nodes, and Relation Diffusion that captures higher-order dependencies while amplifying signals from minority classes. Thus, GraphSB balances structural distribution before node synthesis, enabling more effective learning in GNNs. Extensive experiments demonstrate that GraphSB significantly outperforms the state-of-the-art methods. More importantly, the proposed Structural Balance can be seamlessly integrated into state-of-the-art methods as a simple plug-and-play module, increasing their accuracy by an average of 3.67%.