# Homophily modulates double descent generalization in graph convolution networks

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 83 references that are in the map.
- First posted on arXiv 26 Dec 2022.

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

- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Understanding deep learning requires rethinking generalization](https://mlsanity.com/paper/1611.03530/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Deep Double Descent: Where Bigger Models and More Data Hurt](https://mlsanity.com/paper/1912.02292/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (2019)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)

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

- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [Generalization of Geometric Graph Neural Networks with Lipschitz Loss Functions](https://mlsanity.com/paper/2409.05191/) (2024)
- [Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalization](https://mlsanity.com/paper/2410.08473/) (2024)
- [Asymptotic generalization error of a single-layer graph convolutional network](https://mlsanity.com/paper/2402.03818/) (2024)
- [Learning from one graph: transductive learning guarantees via the geometry of small random worlds](https://mlsanity.com/paper/2509.06894/) (2025)
- [Spring-block theory of feature learning in deep neural networks](https://mlsanity.com/paper/2407.19353/) (2024)
- [Statistical physics analysis of graph neural networks: Approaching optimality in the contextual stochastic block model](https://mlsanity.com/paper/2503.01361/) (2025)
- [Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks](https://mlsanity.com/paper/2412.13754/) (2024)
- [Exact Generalisation Error Exposes Benchmarks Skew Graph Neural Networks Success (or Failure)](https://mlsanity.com/paper/2509.10337/) (2025)
- [Deep Exploration of Epoch-wise Double Descent in Noisy Data: Signal Separation, Large Activation, and Benign Overfitting](https://mlsanity.com/paper/2601.08316/) (2026)
- [Different Statistical Perspectives for Understanding Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2605.25452/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) excel in modeling relational data such as biological, social, and transportation networks, but the underpinnings of their success are not well understood. Traditional complexity measures from statistical learning theory fail to account for observed phenomena like the double descent or the impact of relational semantics on generalization error. Motivated by experimental observations of ``transductive'' double descent in key networks and datasets, we use analytical tools from statistical physics and random matrix theory to precisely characterize generalization in simple graph convolution networks on the contextual stochastic block model. Our results illuminate the nuances of learning on homophilic versus heterophilic data and predict double descent whose existence in GNNs has been questioned by recent work. We show how risk is shaped by the interplay between the graph noise, feature noise, and the number of training labels. Our findings apply beyond stylized models, capturing qualitative trends in real-world GNNs and datasets. As a case in point, we use our analytic insights to improve performance of state-of-the-art graph convolution networks on heterophilic datasets.