mlsanityData to 7 Oct 2026

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

arXiv 2306.01323 ↗First posted 2 Jun 2023cs.LG cs.AIcited by 41

Not on the map. Why?

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.

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

Builds on

80 of 113 references.

References · 80

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2017Prototypical Networks for Few-shot Learningcited by 3,001
  5. 2016Matching Networks for One Shot Learningcited by 2,246
  6. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  7. 2019Simplifying Graph Convolutional Networkscited by 1,470
  8. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,134
  9. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  10. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  11. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  12. 2020Simple and Deep Graph Convolutional Networkscited by 857
38 more
  1. 2018Link Prediction Based on Graph Neural Networkscited by 829
  2. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  3. 2019Graph Neural Networks for Social Recommendationcited by 711
  4. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  5. 2019Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological Viewcited by 544
  6. 2019Multi-scale Attributed Node Embeddingcited by 543
  7. 2017Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Datacited by 527
  8. 2019DeepGCNs: Can GCNs Go as Deep as CNNs?cited by 527
  9. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  10. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 395
  11. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  12. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 332
  13. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  14. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  15. 2020Towards Deeper Graph Neural Networkscited by 296
  16. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 273
  17. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 246
  18. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  19. 2020Graph Neural Networks with Heterophilycited by 202
  20. 2020Data Augmentation for Graph Neural Networkscited by 200
  21. 2019Topology Attack and Defense for Graph Neural Networks: An Optimization Perspectivecited by 196
  22. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  23. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  24. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  25. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  26. 2022Revisiting Heterophily For Graph Neural Networkscited by 169
  27. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 163
  28. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  29. 2021Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillationcited by 151
  30. 2022GOOD: A Graph Out-of-Distribution Benchmarkcited by 140
  31. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  32. 2020A Unified View on Graph Neural Networks as Graph Signal Denoisingcited by 110
  33. 2016Community detection in networks: A user guidecited by 105
  34. 2021Robustness of Graph Neural Networks at Scalecited by 100
  35. 2021On the Role of Neural Collapse in Transfer Learningcited by 100
  36. 2021EDITS: Modeling and Mitigating Data Bias for Graph Neural Networkscited by 92
  37. 2021Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Datacited by 86
  38. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84

50 most cited of 80 All 80 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 22; 2025: 11; 2026: 3.

41 papers.

Sort:

By area:

  1. 2023Exploring the Potential of Large Language Models (LLMs) in Learning on Graphscited by 271
  2. 2024Position: Graph Foundation Models are Already Herecited by 84
  3. 2024AnyGraph: Graph Foundation Model in the Wildcited by 51
  4. 2024Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insightscited by 44
  5. 2024Navigating Complexity: Toward Lossless Graph Condensation via Expanding Window Matchingcited by 28
  6. 2024Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approachcited by 17
  7. 2025No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasetscited by 16
  8. 2024Understanding Heterophily for Graph Neural Networkscited by 15
  9. 2024One Model for One Graph: A New Perspective for Pretraining with Cross-domain Graphscited by 12
  10. 2023Rethinking Sensors Modeling: Hierarchical Information Enhanced Traffic Forecastingcited by 11
  11. 2023A Topological Perspective on Demystifying GNN-Based Link Prediction Performancecited by 11
  12. 2024Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptationcited by 10
29 more
  1. 2023Graph Transformers for Large Graphscited by 9
  2. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  3. 2025Homophily Enhanced Graph Domain Adaptationcited by 9
  4. 2024Cross-Domain Graph Data Scaling: A Showcase with Diffusion Modelscited by 8
  5. 2024DA-MoE: Addressing Depth-Sensitivity in Graph-Level Analysis through Mixture of Expertscited by 7
  6. 2024A Pure Transformer Pretraining Framework on Text-attributed Graphscited by 6
  7. 2024Leveraging Invariant Principle for Heterophilic Graph Structure Distribution Shiftscited by 6
  8. 2024Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarkscited by 6
  9. 2023Clarify Confused Nodes via Separated Learningcited by 5
  10. 2024Provable Filter for Real-world Graph Clusteringcited by 5
  11. 2025View Space: Learning Representation across Arbitrary Graphscited by 4
  12. 2024NetInfoF Framework: Measuring and Exploiting Network Usable Informationcited by 3
  13. 2024Simplified PCNet with Robustnesscited by 3
  14. 2025Aggregation Buffer: Revisiting DropEdge with a New Parameter Blockcited by 3
  15. 2025Graph Few-Shot Learning via Adaptive Spectrum Experts and Cross-Set Distribution Calibrationcited by 3
  16. 2024Talos: A More Effective and Efficient Adversarial Defense for GNN Models Based on the Global Homophily of Graphscited by 2
  17. 2024Edge-Splitting MLP: Node Classification on Homophilic and Heterophilic Graphs without Message Passingcited by 2
  18. 2024Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspectivecited by 2
  19. 2026Relatron: Automating Relational Machine Learning over Relational Databasescited by 2
  20. 2024Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variantscited by 1
  21. 2024BSG4Bot: Efficient Bot Detection based on Biased Heterogeneous Subgraphscited by 1
  22. 2025Glance for Context: Learning When to Leverage LLMs for Node-Aware GNN-LLM Fusioncited by 1
  23. 2026Learning Adaptive Distribution Alignment with Neural Characteristic Function for Graph Domain Adaptationcited by 1
  24. 2025DeltaGNN: Graph Neural Network with Information Flow Controlcited by 0
  25. 2025Towards Anomaly-Aware Pre-Training and Fine-Tuning for Graph Anomaly Detectioncited by 0
  26. 2025Heterophily-informed Message Passingcited by 0
  27. 2025Subgraph Generation for Generalizing on Out-of-Distribution Linkscited by 0
  28. 2025GraphTorque: Torque-Driven Rewiring Graph Neural Networkcited by 0
  29. 2026Disentangling Homophily and Rarity: Explaining Failure in Graph Neural Networkscited by 0