Research map / Graph learning / Graph self-supervised learning
Class-Imbalanced Graph Learning without Class Rebalancing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes BAT, a lightweight plug-and-play topological augmentation that adds virtual class-prototype nodes guided by node misclassification risk to mitigate AMP/DMP-driven bias in class-imbalanced node classification, without class rebalancing.
Problem
Class-imbalanced node classification on graphs suffers predictive bias against minority classes; existing methods rely on class rebalancing, while the topological causes of this bias are not well understood.
Approach
Theoretically identifies two local topological phenomena (ambivalent message-passing and distant message-passing) that amplify minority-class bias, then uses prediction uncertainty to locate high-risk nodes and connects them to per-class virtual nodes via risk-discounted posterior-likelihood edges, orthogonal to reweighting/resampling.
Key results
- Boosts best CIGL baseline balanced accuracy by 4.1/13.8/5.8 points on Cora/CiteSeer/PubMed (IR=10).
- Achieves up to 46.27% performance gain and up to 72.74% bias reduction over existing techniques (abstract).
- Overhead is milliseconds per augmentation, adding only about 0.015-3% virtual edges/nodes relative to the original graph.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add BAT with 0th-order posterior likelihood estimation | GCN · Cora | Balanced accuracy: 64.5 -> 70.5 | Helped |
| Add BAT with 1st-order posterior likelihood estimation | GCN · CiteSeer | Balanced accuracy: 43.2 -> 59.2 | Helped |
| Add BAT with 0th-order posterior likelihood estimation | GCN · PubMed | Balanced accuracy: 69.1 -> 73.0 | Helped |
| Replace TV-distance uncertainty with random scores (ablation) | BAT 0th-order · Cora (IR=10) | Balanced accuracy: 65.54±1.25 -> 61.64±1.89 | Hurt |
| Replace TV-distance uncertainty with information entropy (ablation) | BAT 0th-order · Cora (IR=10) | Balanced accuracy: 65.54±1.25 -> 65.18±1.68 | No clear effect |
| Replace TV-distance uncertainty with information entropy (ablation) | BAT 0th-order · CiteSeer (IR=10) | Balanced accuracy: 52.65±1.08 -> 51.87±2.96 | No clear effect |
| Replace TV-distance uncertainty with information entropy (ablation) | BAT 0th-order · PubMed (IR=10) | Balanced accuracy: 68.62±0.77 -> 67.72±1.27 | No clear effect |
| Replace 0th-order posterior likelihood estimation with random likelihoods (ablation) | BAT · Cora (IR=10) | Balanced accuracy: 65.54±1.25 -> 63.85±2.17 | Hurt |
| Replace 0th-order posterior likelihood estimation with random likelihoods (ablation) | BAT · CiteSeer (IR=10) | Balanced accuracy: 52.65±1.08 -> 46.51±3.27 | Hurt |
| Replace 0th-order posterior likelihood estimation with random likelihoods (ablation) | BAT · PubMed (IR=10) | Balanced accuracy: 68.62±0.77 -> 64.32±1.23 | Hurt |
| Use 1st-order instead of 0th-order posterior likelihood estimation (ablation) | BAT · Cora (IR=10) | Balanced accuracy: 65.54±1.25 -> 69.80±1.30 | Helped |
| Use 1st-order instead of 0th-order posterior likelihood estimation (ablation) | BAT · CiteSeer (IR=10) | Balanced accuracy: 52.65±1.08 -> 55.37±1.39 | Helped |
Surprising findings
- Theory implies eliminating DMP bias on Cora would require minority label rate above 1 - 5.05e-8, which is practically infeasible, so labeling more minority nodes cannot solve the problem.
Limitations
- Gains depend on the quality of the model's uncertainty estimates; random uncertainty substantially degrades performance.
- Experiments use semi-supervised node classification on five citation/co-author benchmarks with GCN-style backbones and step/natural imbalance settings.
Experimental setup
Datasets: Cora CiteSeer PubMed CS Physics
Benchmarks: Cora CiteSeer PubMed CS Physics
Metrics: Balanced Accuracy Macro-F1 PerfStd
Baselines: ERM Reweight ReNode Resampling (oversampling) SMOTE GraphSMOTE GraphENS
Builds on: GraphSMOTE GraphENS ReNode GCN SMOTE
Closest papers by meaning
- Cluster-guided Contrastive Class-imbalanced Graph Classification (AAAI 2025 · similarity 0.91)
- Geometric Imbalance in Semi-Supervised Node Classification (NeurIPS 2025 · similarity 0.89)
- IGL-Bench: Establishing the Comprehensive Benchmark for Imbalanced Graph Learning (ICLR 2025 · similarity 0.89)
- Automated Loss function Search for Class-imbalanced Node Classification (ICML 2024 · similarity 0.87)
- Topology-Aware Dynamic Reweighting for Distribution Shifts on Graph (ICML 2025 · similarity 0.87)
- Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.