# Subgroup Generalization and Fairness of Graph Neural Networks

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

## Key facts

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

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [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)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Spatio-Temporal Graph Convolutional Networks: A Deep Learning Framework for Traffic Forecasting](https://mlsanity.com/paper/1709.04875/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (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)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Junction Tree Variational Autoencoder for Molecular Graph Generation](https://mlsanity.com/paper/1802.04364/) (2018)
- [Geometric deep learning on graphs and manifolds using mixture model CNNs](https://mlsanity.com/paper/1611.08402/) (2016)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information](https://mlsanity.com/paper/2009.01454/) (2020)
- [Graph Neural Tangent Kernel: Fusing Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/1905.13192/) (2019)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach](https://mlsanity.com/paper/1804.05862/) (2018)
- [Compositional Fairness Constraints for Graph Embeddings](https://mlsanity.com/paper/1905.10674/) (2019)
- [On the properties of variational approximations of Gibbs posteriors](https://mlsanity.com/paper/1506.04091/) (2015)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Stability and Generalization of Graph Convolutional Neural Networks](https://mlsanity.com/paper/1905.01004/) (2019)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)

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

- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Debiasing Graph Neural Networks via Learning Disentangled Causal Substructure](https://mlsanity.com/paper/2209.14107/) (2022)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [A Comprehensive Survey on Deep Graph Representation Learning](https://mlsanity.com/paper/2304.05055/) (2023)
- [Energy-based Out-of-Distribution Detection for Graph Neural Networks](https://mlsanity.com/paper/2302.02914/) (2023)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [FMP: Toward Fair Graph Message Passing against Topology Bias](https://mlsanity.com/paper/2202.04187/) (2022)
- [Alleviating Structural Distribution Shift in Graph Anomaly Detection](https://mlsanity.com/paper/2401.14155/) (2024)
- [Graph Out-of-Distribution Generalization via Causal Intervention](https://mlsanity.com/paper/2402.11494/) (2024)
- [On Generalized Degree Fairness in Graph Neural Networks](https://mlsanity.com/paper/2302.03881/) (2023)
- [Fair Node Representation Learning via Adaptive Data Augmentation](https://mlsanity.com/paper/2201.08549/) (2022)
- [Fairness-Aware Graph Neural Networks: A Survey](https://mlsanity.com/paper/2307.03929/) (2023)
- [Adversarial Weight Perturbation Improves Generalization in Graph Neural Networks](https://mlsanity.com/paper/2212.04983/) (2022)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [GraphMETRO: Mitigating Complex Graph Distribution Shifts via Mixture of Aligned Experts](https://mlsanity.com/paper/2312.04693/) (2023)
- [On the Benefits of Attribute-Driven Graph Domain Adaptation](https://mlsanity.com/paper/2502.06808/) (2025)
- [Interpreting Unfairness in Graph Neural Networks via Training Node Attribution](https://mlsanity.com/paper/2211.14383/) (2022)
- [RouteNet-Fermi: Network Modeling with Graph Neural Networks](https://mlsanity.com/paper/2212.12070/) (2022)
- [A Manifold Perspective on the Statistical Generalization of Graph Neural Networks](https://mlsanity.com/paper/2406.05225/) (2024)
- [Multi-dimensional discrimination in Law and Machine Learning -- A comparative overview](https://mlsanity.com/paper/2302.05995/) (2023)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Explaining and Adapting Graph Conditional Shift](https://mlsanity.com/paper/2306.03256/) (2023)
- [On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks](https://mlsanity.com/paper/2306.05557/) (2023)
- [Partition-Based Active Learning for Graph Neural Networks](https://mlsanity.com/paper/2201.09391/) (2022)
- [Adversarial Inter-Group Link Injection Degrades the Fairness of Graph Neural Networks](https://mlsanity.com/paper/2209.05957/) (2022)
- [FairGAT: Fairness-aware Graph Attention Networks](https://mlsanity.com/paper/2303.14591/) (2023)
- [GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks](https://mlsanity.com/paper/2306.11264/) (2023)

## 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.