# Position-aware Structure Learning for Graph Topology-imbalance by Relieving Under-reaching and Over-squashing

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 58 references that are in the map.
- First posted on arXiv 17 Aug 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [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)
- [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)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [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)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Learning to Reweight Examples for Robust Deep Learning](https://mlsanity.com/paper/1803.09050/) (2018)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Graph Structure Learning for Robust Graph Neural Networks](https://mlsanity.com/paper/2005.10203/) (2020)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Hierarchical Graph Pooling with Structure Learning](https://mlsanity.com/paper/1911.05954/) (2019)
- [Graph Structure Learning with Variational Information Bottleneck](https://mlsanity.com/paper/2112.08903/) (2021)
- [SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanism](https://mlsanity.com/paper/2101.08170/) (2021)
- [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)
- [Reinforced Structured State-Evolution for Vision-Language Navigation](https://mlsanity.com/paper/2204.09280/) (2022)
- [MTTrans: Cross-Domain Object Detection with Mean-Teacher Transformer](https://mlsanity.com/paper/2205.01643/) (2022)

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

- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [Does Graph Distillation See Like Vision Dataset Counterpart?](https://mlsanity.com/paper/2310.09192/) (2023)
- [SE-GSL: A General and Effective Graph Structure Learning Framework through Structural Entropy Optimization](https://mlsanity.com/paper/2303.09778/) (2023)
- [Class-Imbalanced Graph Learning without Class Rebalancing](https://mlsanity.com/paper/2308.14181/) (2023)
- [Environment-Aware Dynamic Graph Learning for Out-of-Distribution Generalization](https://mlsanity.com/paper/2311.11114/) (2023)
- [Class-Imbalanced Learning on Graphs: A Survey](https://mlsanity.com/paper/2304.04300/) (2023)
- [Hyperbolic Geometric Graph Representation Learning for Hierarchy-imbalance Node Classification](https://mlsanity.com/paper/2304.05059/) (2023)
- [Over-Squashing in Graph Neural Networks: A Comprehensive survey](https://mlsanity.com/paper/2308.15568/) (2023)
- [Exposition on over-squashing problem on GNNs: Current Methods, Benchmarks and Challenges](https://mlsanity.com/paper/2311.07073/) (2023)
- [Oversmoothing, Oversquashing, Heterophily, Long-Range, and more: Demystifying Common Beliefs in Graph Machine Learning](https://mlsanity.com/paper/2505.15547/) (2025)
- [DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing](https://mlsanity.com/paper/2401.12780/) (2024)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (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)
- [The Effectiveness of Curvature-Based Rewiring and the Role of Hyperparameters in GNNs Revisited](https://mlsanity.com/paper/2407.09381/) (2024)
- [A Comprehensive Survey on Imbalanced Data Learning](https://mlsanity.com/paper/2502.08960/) (2025)
- [Self-organization Preserved Graph Structure Learning with Principle of Relevant Information](https://mlsanity.com/paper/2301.00015/) (2022)
- [DG-Mamba: Robust and Efficient Dynamic Graph Structure Learning with Selective State Space Models](https://mlsanity.com/paper/2412.08160/) (2024)
- [Poincar'e Differential Privacy for Hierarchy-Aware Graph Embedding](https://mlsanity.com/paper/2312.12183/) (2023)
- [Heterogeneous Graph Neural Network for Privacy-Preserving Recommendation](https://mlsanity.com/paper/2210.00538/) (2022)
- [Dynamic Graph Information Bottleneck](https://mlsanity.com/paper/2402.06716/) (2024)
- [Tokenized Graph Transformer with Neighborhood Augmentation for Node Classification in Large Graphs](https://mlsanity.com/paper/2305.12677/) (2023)
- [Edge Classification on Graphs: New Directions in Topological Imbalance](https://mlsanity.com/paper/2406.11685/) (2024)
- [PhoGAD: Graph-based Anomaly Behavior Detection with Persistent Homology Optimization](https://mlsanity.com/paper/2401.10547/) (2024)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Revisiting Edge Perturbation for Graph Neural Network in Graph Data Augmentation and Attack](https://mlsanity.com/paper/2403.07943/) (2024)
- [textttSynC: Synergistic Boosting of Structure and Representation for Deep Graph Clustering](https://mlsanity.com/paper/2406.15797/) (2024)
- [Mitigating Message Imbalance in Fraud Detection with Dual-View Graph Representation Learning](https://mlsanity.com/paper/2507.06469/) (2025)
- [Conditional Shift-Robust Conformal Prediction for Graph Neural Network](https://mlsanity.com/paper/2405.11968/) (2024)
- [Graph Size-imbalanced Learning with Energy-guided Structural Smoothing](https://mlsanity.com/paper/2412.17591/) (2024)

## Abstract (arXiv)

Topology-imbalance is a graph-specific imbalance problem caused by the uneven topology positions of labeled nodes, which significantly damages the performance of GNNs. What topology-imbalance means and how to measure its impact on graph learning remain under-explored. In this paper, we provide a new understanding of topology-imbalance from a global view of the supervision information distribution in terms of under-reaching and over-squashing, which motivates two quantitative metrics as measurements. In light of our analysis, we propose a novel position-aware graph structure learning framework named PASTEL, which directly optimizes the information propagation path and solves the topology-imbalance issue in essence. Our key insight is to enhance the connectivity of nodes within the same class for more supervision information, thereby relieving the under-reaching and over-squashing phenomena. Specifically, we design an anchor-based position encoding mechanism, which better incorporates relative topology position and enhances the intra-class inductive bias by maximizing the label influence. We further propose a class-wise conflict measure as the edge weights, which benefits the separation of different node classes. Extensive experiments demonstrate the superior potential and adaptability of PASTEL in enhancing GNNs' power in different data annotation scenarios.