mlsanityData to 7 Oct 2026

Subgroup Generalization and Fairness of Graph Neural Networks

arXiv 2106.15535 ↗First posted 29 Jun 2021cs.LG cs.AIcited by 69

Not on the map. Why?

Abstract (arXiv)

Despite enormous successful applications of graph neural networks (GNNs), theoretical understanding of their generalization ability, especially for node-level tasks where data are not independent and identically-distributed (IID), has been sparse. The theoretical investigation of the generalization performance is beneficial for understanding fundamental issues (such as fairness) of GNN models and designing better learning methods. In this paper, we present a novel PAC-Bayesian analysis for GNNs under a non-IID semi-supervised learning setup. Moreover, we analyze the generalization performances on different subgroups of unlabeled nodes, which allows us to further study an accuracy-(dis)parity-style (un)fairness of GNNs from a theoretical perspective. Under reasonable assumptions, we demonstrate that the distance between a test subgroup and the training set can be a key factor affecting the GNN performance on that subgroup, which calls special attention to the training node selection for fair learning. Experiments across multiple GNN models and datasets support our theoretical results.

Key facts. Cited by 69 papers in the map (data through 7 Oct 2026). Builds on 36 of its 54 references that are in the map. First posted on arXiv 29 Jun 2021.

Builds on

36 of 54 references.

References · 36

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  5. 2019Simplifying Graph Convolutional Networkscited by 1,470
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  7. 2017Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecastingcited by 1,125
  8. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,099
  9. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  10. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  11. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  12. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 647
24 more
  1. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  3. 2017A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networkscited by 309
  4. 2019Revisiting Graph Neural Networks: All We Have is Low-Pass Filterscited by 260
  5. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  6. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  7. 2020Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Informationcited by 168
  8. 2019Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernelscited by 160
  9. 2018Contextual Stochastic Block Modelscited by 134
  10. 2019A Primer on PAC-Bayesian Learningcited by 130
  11. 2021Towards a Unified Framework for Fair and Stable Graph Representation Learningcited by 128
  12. 2019Compositional Fairness Constraints for Graph Embeddingscited by 126
  13. 2018Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approachcited by 125
  14. 2015On the properties of variational approximations of Gibbs posteriorscited by 121
  15. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  16. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  17. 2019Stability and Generalization of Graph Convolutional Neural Networkscited by 81
  18. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  19. 2020On the role of data in PAC-Bayes boundscited by 64
  20. 2015Risk Bounds for the Majority Vote: From a PAC-Bayesian Analysis to a Learning Algorithmcited by 50
  21. 2020All of the Fairness for Edge Prediction with Optimal Transportcited by 36
  22. 2021CrossWalk: Fairness-enhanced Node Representation Learningcited by 34
  23. 2021Fair Representation Learning for Heterogeneous Information Networkscited by 28
  24. 2021The KL-Divergence between a Graph Model and its Fair I-Projection as a Fairness Regularizercited by 17

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 18; 2023: 22; 2024: 14; 2025: 12; 2026: 3.

69 papers.

Sort:

By area:

  1. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 163
  2. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  3. 2022Trustworthy Graph Neural Networks: Aspects, Methods and Trendscited by 88
  4. 2022Debiasing Graph Neural Networks via Learning Disentangled Causal Substructurecited by 83
  5. 2022Fairness in Graph Mining: A Surveycited by 76
  6. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  7. 2023Energy-based Out-of-Distribution Detection for Graph Neural Networkscited by 67
  8. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  9. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  10. 2022FMP: Toward Fair Graph Message Passing against Topology Biascited by 35
  11. 2024Alleviating Structural Distribution Shift in Graph Anomaly Detectioncited by 31
  12. 2024Graph Out-of-Distribution Generalization via Causal Interventioncited by 30
38 more
  1. 2023On Generalized Degree Fairness in Graph Neural Networkscited by 28
  2. 2022Fair Node Representation Learning via Adaptive Data Augmentationcited by 27
  3. 2023Fairness-Aware Graph Neural Networks: A Surveycited by 22
  4. 2022Adversarial Weight Perturbation Improves Generalization in Graph Neural Networkscited by 21
  5. 2022A Survey on Fairness for Machine Learning on Graphscited by 20
  6. 2023GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Expertscited by 19
  7. 2025On the Benefits of Attribute-Driven Graph Domain Adaptationcited by 19
  8. 2022Interpreting Unfairness in Graph Neural Networks via Training Node Attributioncited by 18
  9. 2022RouteNet-Fermi: Network Modeling with Graph Neural Networkscited by 17
  10. 2024A Manifold Perspective on the Statistical Generalization of Graph Neural Networkscited by 16
  11. 2023Multi-dimensional discrimination in Law and Machine Learning -- A comparative overviewcited by 15
  12. 2023A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directionscited by 15
  13. 2023Explaining and Adapting Graph Conditional Shiftcited by 14
  14. 2023On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networkscited by 13
  15. 2022Partition-Based Active Learning for Graph Neural Networkscited by 12
  16. 2022Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networkscited by 12
  17. 2023FairGAT: Fairness-aware Graph Attention Networkscited by 12
  18. 2023GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networkscited by 12
  19. 2023Chasing Fairness in Graphs: A GNN Architecture Perspectivecited by 12
  20. 2025Homophily Enhanced Graph Domain Adaptationcited by 9
  21. 2024FairSample: Training Fair and Accurate Graph Convolutional Neural Networks Efficientlycited by 8
  22. 2023On the Limitation and Experience Replay for GNNs in Continual Learningcited by 7
  23. 2023Toward Operationalizing Pipeline-aware ML Fairness: A Research Agenda for Developing Practical Guidelines and Toolscited by 7
  24. 2023Supercharging Graph Transformers with Advective Diffusioncited by 7
  25. 2024How does promoting the minority fraction affect generalization? A theoretical study of the one-hidden-layer neural network on group imbalancecited by 6
  26. 2024Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functionscited by 6
  27. 2024Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarkscited by 6
  28. 2022Shift-Robust Node Classification via Graph Adversarial Clusteringcited by 5
  29. 2024Towards Standardizing AI Bias Explorationcited by 5
  30. 2022FairNorm: Fair and Fast Graph Neural Network Trainingcited by 4
  31. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  32. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  33. 2025CoS: Towards Optimal Event Scheduling via Chain-of-Schedulingcited by 4
  34. 2023Towards Label Position Bias in Graph Neural Networkscited by 3
  35. 2023Sharpness-Aware Graph Collaborative Filteringcited by 3
  36. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  37. 2024On the Topology Awareness and Generalization Performance of Graph Neural Networkscited by 3
  38. 2024Foundations and Frontiers of Graph Learning Theorycited by 3

50 most cited of 69 All 69 (JSON)