# Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- Builds on 80 of its 113 references that are in the map.
- First posted on arXiv 2 Jun 2023.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Prototypical Networks for Few-shot Learning](https://mlsanity.com/paper/1703.05175/) (2017)
- [Matching Networks for One Shot Learning](https://mlsanity.com/paper/1606.04080/) (2016)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Survey on Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2303.10993/) (2023)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)

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

- [Exploring the Potential of Large Language Models (LLMs) in Learning on Graphs](https://mlsanity.com/paper/2307.03393/) (2023)
- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [AnyGraph: Graph Foundation Model in the Wild](https://mlsanity.com/paper/2408.10700/) (2024)
- [Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights](https://mlsanity.com/paper/2406.10727/) (2024)
- [Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matching](https://mlsanity.com/paper/2402.05011/) (2024)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (2024)
- [No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasets](https://mlsanity.com/paper/2502.02379/) (2025)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [One Model for One Graph: A New Perspective for Pretraining with Cross-domain Graphs](https://mlsanity.com/paper/2412.00315/) (2024)
- [Rethinking Sensors Modeling: Hierarchical Information Enhanced Traffic Forecasting](https://mlsanity.com/paper/2309.11284/) (2023)
- [A Topological Perspective on Demystifying GNN-Based Link Prediction Performance](https://mlsanity.com/paper/2310.04612/) (2023)
- [Graph Transformers for Large Graphs](https://mlsanity.com/paper/2312.11109/) (2023)
- [Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation](https://mlsanity.com/paper/2410.06976/) (2024)
- [Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective](https://mlsanity.com/paper/2402.04621/) (2024)
- [Homophily Enhanced Graph Domain Adaptation](https://mlsanity.com/paper/2505.20089/) (2025)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [DA-MoE: Addressing Depth-Sensitivity in Graph-Level Analysis through Mixture of Experts](https://mlsanity.com/paper/2411.03025/) (2024)
- [A Pure Transformer Pretraining Framework on Text-attributed Graphs](https://mlsanity.com/paper/2406.13873/) (2024)
- [Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shifts](https://mlsanity.com/paper/2408.09490/) (2024)
- [Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarks](https://mlsanity.com/paper/2410.04287/) (2024)
- [Clarify Confused Nodes via Separated Learning](https://mlsanity.com/paper/2306.02285/) (2023)
- [Provable Filter for Real-world Graph Clustering](https://mlsanity.com/paper/2403.03666/) (2024)
- [View Space: Learning Representation across Arbitrary Graphs](https://mlsanity.com/paper/2512.11561/) (2025)
- [NetInfoF Framework: Measuring and Exploiting Network Usable Information](https://mlsanity.com/paper/2402.07999/) (2024)
- [Simplified PCNet with Robustness](https://mlsanity.com/paper/2403.03676/) (2024)
- [Aggregation Buffer: Revisiting DropEdge with a New Parameter Block](https://mlsanity.com/paper/2505.20840/) (2025)
- [Graph Few-Shot Learning via Adaptive Spectrum Experts and Cross-Set Distribution Calibration](https://mlsanity.com/paper/2510.12140/) (2025)
- [Talos: A More Effective and Efficient Adversarial Defense for GNN Models Based on the Global Homophily of Graphs](https://mlsanity.com/paper/2406.03833/) (2024)
- [Edge-Splitting MLP: Node Classification on Homophilic and Heterophilic Graphs without Message Passing](https://mlsanity.com/paper/2412.08310/) (2024)
- [Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspective](https://mlsanity.com/paper/2412.09805/) (2024)

## Abstract (arXiv)

Recent studies on Graph Neural Networks(GNNs) provide both empirical and theoretical evidence supporting their effectiveness in capturing structural patterns on both homophilic and certain heterophilic graphs. Notably, most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns, exhibiting a structural disparity. However, the analysis of GNN performance with respect to nodes exhibiting different structural patterns, e.g., homophilic nodes in heterophilic graphs, remains rather limited. In the present study, we provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes within homophilic graphs and heterophilic nodes within heterophilic graphs while struggling on the opposite node set, exhibiting a performance disparity. We theoretically and empirically identify effects of GNNs on testing nodes exhibiting distinct structural patterns. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity, namely the aggregated feature distance and homophily ratio difference between training and testing nodes. Furthermore, we demonstrate the practical implications of our new findings via (1) elucidating the effectiveness of deeper GNNs; and (2) revealing an over-looked distribution shift factor on graph out-of-distribution problem and proposing a new scenario accordingly.