# Topology-Imbalance Learning for Semi-Supervised Node Classification

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

## Key facts

- Cited by 56 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 81 references that are in the map.
- First posted on arXiv 8 Oct 2021.

## Builds on (most cited first, 30 of 34)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Class-Balanced Loss Based on Effective Number of Samples](https://mlsanity.com/paper/1901.05555/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss](https://mlsanity.com/paper/1906.07413/) (2019)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Learning to Reweight Examples for Robust Deep Learning](https://mlsanity.com/paper/1803.09050/) (2018)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [A Survey of Deep Active Learning](https://mlsanity.com/paper/2009.00236/) (2020)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [A systematic study of the class imbalance problem in convolutional neural networks](https://mlsanity.com/paper/1710.05381/) (2017)
- [Hard Negative Mixing for Contrastive Learning](https://mlsanity.com/paper/2010.01028/) (2020)
- [Rethinking the Value of Labels for Improving Class-Imbalanced Learning](https://mlsanity.com/paper/2006.07529/) (2020)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [GraphSMOTE: Imbalanced Node Classification on Graphs with Graph Neural Networks](https://mlsanity.com/paper/2103.08826/) (2021)
- [Unifying Graph Convolutional Neural Networks and Label Propagation](https://mlsanity.com/paper/2002.06755/) (2020)

## Built on by (most cited first, 30 of 56)

- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2206.12917/) (2022)
- [Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing](https://mlsanity.com/paper/2208.08302/) (2022)
- [Class-Imbalanced Graph Learning without Class Rebalancing](https://mlsanity.com/paper/2308.14181/) (2023)
- [Semi-supervised Domain Adaptation in Graph Transfer Learning](https://mlsanity.com/paper/2309.10773/) (2023)
- [Class-Imbalanced Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.04300/) (2023)
- [FreeKD: Free-direction Knowledge Distillation for Graph Neural Networks](https://mlsanity.com/paper/2206.06561/) (2022)
- [Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification](https://mlsanity.com/paper/2304.05059/) (2023)
- [GraphSHA: Synthesizing Harder Samples for Class-Imbalanced Node Classification](https://mlsanity.com/paper/2306.09612/) (2023)
- [Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural Networks](https://mlsanity.com/paper/2302.02922/) (2023)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [Rethinking Semi-Supervised Imbalanced Node Classification from Bias-Variance Decomposition](https://mlsanity.com/paper/2310.18765/) (2023)
- [TopoImb: Toward Topology-level Imbalance in Learning from Graphs](https://mlsanity.com/paper/2212.08689/) (2022)
- [NodeMixup: Tackling Under-Reaching for Graph Neural Networks](https://mlsanity.com/paper/2312.13032/) (2023)
- [Leveraging Label Non-Uniformity for Node Classification in Graph Neural Networks](https://mlsanity.com/paper/2305.00139/) (2023)
- [BeMap: Balanced Message Passing for Fair Graph Neural Network](https://mlsanity.com/paper/2306.04107/) (2023)
- [Rethinking Fair Graph Neural Networks from Re-balancing](https://mlsanity.com/paper/2407.11624/) (2024)
- [A Comprehensive Survey on Imbalanced Data Learning](https://mlsanity.com/paper/2502.08960/) (2025)
- [Semantic-aware Node Synthesis for Imbalanced Heterogeneous Information Networks](https://mlsanity.com/paper/2302.14061/) (2023)
- [LOGIN: A Large Language Model Consulted Graph Neural Network Training Framework](https://mlsanity.com/paper/2405.13902/) (2024)
- [Over-Sampling Strategy in Feature Space for Graphs based Class-imbalanced Bot Detection](https://mlsanity.com/paper/2302.06900/) (2023)
- [Imbalanced Node Classification Beyond Homophilic Assumption](https://mlsanity.com/paper/2304.14635/) (2023)
- [DIVE: Subgraph Disagreement for Graph Out-of-Distribution Generalization](https://mlsanity.com/paper/2408.04400/) (2024)
- [Synthetic Over-sampling for Imbalanced Node Classification with Graph Neural Networks](https://mlsanity.com/paper/2206.05335/) (2022)
- [Mitigating Label Noise on Graph via Topological Sample Selection](https://mlsanity.com/paper/2403.01942/) (2024)
- [Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shifts](https://mlsanity.com/paper/2408.09490/) (2024)
- [Omni-Granular Ego-Semantic Propagation for Self-Supervised Graph Representation Learning](https://mlsanity.com/paper/2205.15746/) (2022)
- [Disambiguated Node Classification with Graph Neural Networks](https://mlsanity.com/paper/2402.08824/) (2024)
- [Edge Classification on Graphs: New Directions in Topological Imbalance](https://mlsanity.com/paper/2406.11685/) (2024)

## Abstract (arXiv)

The class imbalance problem, as an important issue in learning node representations, has drawn increasing attention from the community. Although the imbalance considered by existing studies roots from the unequal quantity of labeled examples in different classes (quantity imbalance), we argue that graph data expose a unique source of imbalance from the asymmetric topological properties of the labeled nodes, i.e., labeled nodes are not equal in terms of their structural role in the graph (topology imbalance). In this work, we first probe the previously unknown topology-imbalance issue, including its characteristics, causes, and threats to semi-supervised node classification learning. We then provide a unified view to jointly analyzing the quantity- and topology- imbalance issues by considering the node influence shift phenomenon with the Label Propagation algorithm. In light of our analysis, we devise an influence conflict detection -- based metric Totoro to measure the degree of graph topology imbalance and propose a model-agnostic method ReNode to address the topology-imbalance issue by re-weighting the influence of labeled nodes adaptively based on their relative positions to class boundaries. Systematic experiments demonstrate the effectiveness and generalizability of our method in relieving topology-imbalance issue and promoting semi-supervised node classification. The further analysis unveils varied sensitivity of different graph neural networks (GNNs) to topology imbalance, which may serve as a new perspective in evaluating GNN architectures.