# Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 70 references that are in the map.
- First posted on arXiv 4 Apr 2024.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (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)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Self-supervised Graph Learning for Recommendation](https://mlsanity.com/paper/2010.10783/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Towards a Unified Framework for Fair and Stable Graph Representation Learning](https://mlsanity.com/paper/2102.13186/) (2021)
- [The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization](https://mlsanity.com/paper/2008.06786/) (2020)
- [DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification](https://mlsanity.com/paper/1906.02319/) (2019)
- [Understanding convolution on graphs via energies](https://mlsanity.com/paper/2206.10991/) (2022)
- [Local Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2109.03856/) (2021)
- [GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation](https://mlsanity.com/paper/2310.00800/) (2023)
- [LTE4G: Long-Tail Experts for Graph Neural Networks](https://mlsanity.com/paper/2208.10205/) (2022)
- [Uncovering the Structural Fairness in Graph Contrastive Learning](https://mlsanity.com/paper/2210.03011/) (2022)
- [Incorporating Bias-aware Margins into Contrastive Loss for Collaborative Filtering](https://mlsanity.com/paper/2210.11054/) (2022)
- [On Generalized Degree Fairness in Graph Neural Networks](https://mlsanity.com/paper/2302.03881/) (2023)
- [RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network](https://mlsanity.com/paper/2202.13547/) (2022)
- [Should Graph Convolution Trust Neighbors? A Simple Causal Inference Method](https://mlsanity.com/paper/2010.11797/) (2020)
- [Learning How to Propagate Messages in Graph Neural Networks](https://mlsanity.com/paper/2310.00697/) (2023)

## Built on by (most cited first, 4 of 4)

- [Subgraph Federated Learning for Local Generalization](https://mlsanity.com/paper/2503.03995/) (2025)
- [View Space: Learning Representation across Arbitrary Graphs](https://mlsanity.com/paper/2512.11561/) (2025)
- [Glance for Context: Learning When to Leverage LLMs for Node-Aware GNN-LLM Fusion](https://mlsanity.com/paper/2510.10849/) (2025)
- [The Urban Impact of AI: Modeling Feedback Loops in Next-Venue Recommendation](https://mlsanity.com/paper/2504.07911/) (2025)

## Abstract (arXiv)

Graph Neural Networks (GNNs) often perform better for high-degree nodes than low-degree nodes on node classification tasks. This degree bias can reinforce social marginalization by, e.g., privileging celebrities and other high-degree actors in social networks during social and content recommendation. While researchers have proposed numerous hypotheses for why GNN degree bias occurs, we find via a survey of 38 degree bias papers that these hypotheses are often not rigorously validated, and can even be contradictory. Thus, we provide an analysis of the origins of degree bias in message-passing GNNs with different graph filters. We prove that high-degree test nodes tend to have a lower probability of misclassification regardless of how GNNs are trained. Moreover, we show that degree bias arises from a variety of factors that are associated with a node's degree (e.g., homophily of neighbors, diversity of neighbors). Furthermore, we show that during training, some GNNs may adjust their loss on low-degree nodes more slowly than on high-degree nodes; however, with sufficiently many epochs of training, message-passing GNNs can achieve their maximum possible training accuracy, which is not significantly limited by their expressive power. Throughout our analysis, we connect our findings to previously-proposed hypotheses for the origins of degree bias, supporting and unifying some while drawing doubt to others. We validate our theoretical findings on 8 common real-world networks, and based on our theoretical and empirical insights, describe a roadmap to alleviate degree bias.