# GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 59 references that are in the map.
- First posted on arXiv 1 Oct 2023.

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

- [Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2006.11239/) (2020)
- [High-Resolution Image Synthesis with Latent Diffusion Models](https://mlsanity.com/paper/2112.10752/) (2021)
- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (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)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Deep Graph Contrastive Representation Learning](https://mlsanity.com/paper/2006.04131/) (2020)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [GPT-GNN: Generative Pre-Training of Graph Neural Networks](https://mlsanity.com/paper/2006.15437/) (2020)
- [Graph Contrastive Learning Automated](https://mlsanity.com/paper/2106.07594/) (2021)
- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Aleatoric uncertainty estimation with test-time augmentation for medical image segmentation with convolutional neural networks](https://mlsanity.com/paper/1807.07356/) (2018)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [Graph Clustering with Graph Neural Networks](https://mlsanity.com/paper/2006.16904/) (2020)
- [Motif-based Graph Self-Supervised Learning for Molecular Property Prediction](https://mlsanity.com/paper/2110.00987/) (2021)
- [Better Aggregation in Test-Time Augmentation](https://mlsanity.com/paper/2011.11156/) (2020)
- [Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization](https://mlsanity.com/paper/2009.05204/) (2020)

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

- [Uncertainty in Graph Neural Networks: A Survey](https://mlsanity.com/paper/2403.07185/) (2024)
- [Correcting False Alarms from Unseen: Adapting Graph Anomaly Detectors at Test Time](https://mlsanity.com/paper/2511.07023/) (2025)
- [Revisiting, Benchmarking and Understanding Unsupervised Graph Domain Adaptation](https://mlsanity.com/paper/2407.11052/) (2024)
- [Matcha: Mitigating Graph Structure Shifts with Test-Time Adaptation](https://mlsanity.com/paper/2410.06976/) (2024)
- [Beyond Generalization: A Survey of Out-Of-Distribution Adaptation on Graphs](https://mlsanity.com/paper/2402.11153/) (2024)
- [A Survey of Few-Shot Learning on Graphs: from Meta-Learning to Pre-Training and Prompt Learning](https://mlsanity.com/paper/2402.01440/) (2024)
- [How Does Message Passing Improve Collaborative Filtering?](https://mlsanity.com/paper/2404.08660/) (2024)
- [View Space: Learning Representation across Arbitrary Graphs](https://mlsanity.com/paper/2512.11561/) (2025)
- [Theoretical and Empirical Insights into the Origins of Degree Bias in Graph Neural Networks](https://mlsanity.com/paper/2404.03139/) (2024)
- [Aggregation Buffer: Revisiting DropEdge with a New Parameter Block](https://mlsanity.com/paper/2505.20840/) (2025)
- [MARS: A neurosymbolic approach for interpretable drug discovery](https://mlsanity.com/paper/2410.05289/) (2024)
- [Structural Alignment Improves Graph Test-Time Adaptation](https://mlsanity.com/paper/2502.18334/) (2025)
- [Mitigating Message Imbalance in Fraud Detection with Dual-View Graph Representation Learning](https://mlsanity.com/paper/2507.06469/) (2025)
- [Food4All: An Agentic Framework and Benchmark for Food Resource Navigation with Adaptive User Understanding](https://mlsanity.com/paper/2510.18289/) (2025)
- [PreScam: A Benchmark for Predicting Scam Progression from Early Conversations](https://mlsanity.com/paper/2605.12243/) (2026)
- [FALCON: Feature-Label Constrained Graph Net Collapse for Memory Efficient GNNs](https://mlsanity.com/paper/2312.16542/) (2023)
- [Motif-driven Subgraph Structure Learning for Graph Classification](https://mlsanity.com/paper/2406.08897/) (2024)
- [Agent+P: Guiding UI Agents via Symbolic Planning](https://mlsanity.com/paper/2510.06042/) (2025)
- [Does Homophily Help in Robust Test-time Node Classification?](https://mlsanity.com/paper/2510.22289/) (2025)
- [GFMate: Empowering Graph Foundation Models with Test-time Prompt Tuning](https://mlsanity.com/paper/2605.14809/) (2026)
- [Fair Graph Machine Learning under Adversarial Missingness Processes](https://mlsanity.com/paper/2311.01591/) (2023)
- [Towards Pattern-aware Data Augmentation for Temporal Knowledge Graph Completion](https://mlsanity.com/paper/2501.00252/) (2024)
- [Variational Graph Convolutional Neural Networks](https://mlsanity.com/paper/2507.01699/) (2025)
- [Evaluating Out-of-Distribution Robustness in Graph-Based Android Malware Classification: A New Principled Benchmark](https://mlsanity.com/paper/2508.06734/) (2025)
- [When LLM Agents Meet Graph Optimization: An Automated Data Quality Improvement Approach](https://mlsanity.com/paper/2510.08952/) (2025)
- [RADE: Random Add-Drop Edge as a Regularizer](https://mlsanity.com/paper/2606.00757/) (2026)
- [SupraBench: A Benchmark for Supramolecular Chemistry](https://mlsanity.com/paper/2606.13477/) (2026)
- [HoosierHelp: Benchmarking LLM Agents for Social Service Navigation](https://mlsanity.com/paper/2608.09946/) (2026)
- [GATTA: Graph Active Learning with Test-Time Augmentation](https://mlsanity.com/paper/2608.15084/) (2026)
- [Temporal Memory-Aware Online Test-Time Adaptation on Dynamic Graphs](https://mlsanity.com/paper/2608.27948/) (2026)

## Abstract (arXiv)

Recent studies have shown that graph neural networks (GNNs) exhibit strong biases towards the node degree: they usually perform satisfactorily on high-degree nodes with rich neighbor information but struggle with low-degree nodes. Existing works tackle this problem by deriving either designated GNN architectures or training strategies specifically for low-degree nodes. Though effective, these approaches unintentionally create an artificial out-of-distribution scenario, where models mainly or even only observe low-degree nodes during the training, leading to a downgraded performance for high-degree nodes that GNNs originally perform well at. In light of this, we propose a test-time augmentation framework, namely GraphPatcher, to enhance test-time generalization of any GNNs on low-degree nodes. Specifically, GraphPatcher iteratively generates virtual nodes to patch artificially created low-degree nodes via corruptions, aiming at progressively reconstructing target GNN's predictions over a sequence of increasingly corrupted nodes. Through this scheme, GraphPatcher not only learns how to enhance low-degree nodes (when the neighborhoods are heavily corrupted) but also preserves the original superior performance of GNNs on high-degree nodes (when lightly corrupted). Additionally, GraphPatcher is model-agnostic and can also mitigate the degree bias for either self-supervised or supervised GNNs. Comprehensive experiments are conducted over seven benchmark datasets and GraphPatcher consistently enhances common GNNs' overall performance by up to 3.6% and low-degree performance by up to 6.5%, significantly outperforming state-of-the-art baselines. The source code is publicly available at https://github.com/jumxglhf/GraphPatcher.