Research map / Graph learning / GNN architectures
Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Surveys 38 degree-bias papers, then gives a theoretical and empirical analysis of why message-passing GNNs (RW, SYM, ATT filters) show degree bias at test and training time, validated on 8 real-world networks.
Problem
GNNs often perform better on high-degree nodes than low-degree nodes in node classification, and the proposed hypotheses for this degree bias are not rigorously validated and sometimes contradict each other.
Approach
Derives a probabilistic bound on misclassification for linearized message-passing GNNs with different graph filters, linking test error to node degree via inverse collision probability and prediction homogeneity, and analyzes training-time loss change via a Lipschitz argument; it then tests the surveyed hypotheses against these results.
Key results
- High-degree test nodes have lower test loss than low-degree nodes on CiteSeer for RW, SYM and ATT GNNs (error bars over 10 seeds).
- Inverse collision probability is positively associated with node degree for RW, SYM and ATT filters across datasets.
- SYM adjusts training loss on low-degree nodes more slowly than on high-degree nodes, while RW and ATT training loss curves overlap for the first ~20 epochs.
- Degree bias is not observed on heterophilic chameleon and squirrel, consistent with the theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Compare high-degree with low-degree test nodes | Message-passing GNNs · Homophilic real-world networks | test loss | Helped |
| Use a random-walk graph filter rather than evaluating low-degree nodes as a group | RW GNN · CiteSeer test nodes | representation variance | Mixed |
| Use a symmetric-normalized graph filter rather than evaluating low-degree nodes as a group | SYM GNN · Homophilic datasets | representation variance | Hurt |
| Use a symmetric-normalized graph filter rather than a random-walk filter | Message-passing GNN training · Real-world datasets | rate of training-loss decrease for low-degree nodes | Hurt |
| Train for sufficiently many epochs | Message-passing GNNs with static filters · Training nodes | training accuracy | Helped |
| Evaluate high-degree rather than low-degree nodes | SYM GNN · Heterophilic networks, including Chameleon and Squirrel | test performance | No clear effect |
Surprising findings
- SYM's training loss gap between low- and high-degree nodes emerges despite GNNs eventually reaching near 100% training accuracy, so expressive power does not limit accuracy.
- Many widely cited hypotheses for degree bias (e.g., high-degree nodes cluster more tightly, or higher-degree representations have larger variance) are contradicted or only partially supported by the analysis.
Limitations
- Theory focuses on linearized GNNs and node classification in the semi-supervised transductive setting.
- Empirical validation limited to 8 homophilic and heterophilic networks; inductive, heterogeneous and directed graphs not explored.
- Survey covers only 38 non-review degree bias papers, so hypothesis taxonomy may be incomplete.
Experimental setup
Datasets: Cora_ML CiteSeer CS Physics Amazon Photo Amazon Computers chameleon squirrel
Benchmarks: Cora_ML CiteSeer CS Physics Amazon Photo Amazon Computers chameleon squirrel
Metrics: test loss misclassification probability training accuracy inverse collision probability
Baselines: GCN GraphSAGE GAT
Builds on: graph convolutional networks jumping knowledge networks contextual stochastic block model
Closest papers by meaning
- Networked Inequality: Preferential Attachment Bias in Graph Neural Network Link Prediction (ICML 2024 · similarity 0.90)
- Implicit degree bias in the link prediction task (ICML 2025 · similarity 0.88)
- Graph Neural Networks Are More Than Filters: Revisiting and Benchmarking from A Spectral Perspective (ICLR 2025 · similarity 0.88)
- Chasing Fairness in Graphs: A GNN Architecture Perspective (AAAI 2024 · similarity 0.88)
- GOAt: Explaining Graph Neural Networks via Graph Output Attribution (ICLR 2024 · similarity 0.87)
- On the Interplay between Graph Structure and Learning Algorithms in Graph Neural Networks (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.