# On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 43 references that are in the map.
- First posted on arXiv 24 Oct 2025.

## Builds on (most cited first, 18 of 18)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks](https://mlsanity.com/paper/2012.07690/) (2020)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Generalization Analysis of Message Passing Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2202.00645/) (2022)
- [A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants](https://mlsanity.com/paper/2201.07083/) (2022)
- [Towards Understanding the Generalization of Graph Neural Networks](https://mlsanity.com/paper/2305.08048/) (2023)
- [Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks](https://mlsanity.com/paper/2006.08550/) (2020)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Sampling](https://mlsanity.com/paper/2207.03584/) (2022)
- [Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs](https://mlsanity.com/paper/2411.05464/) (2024)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Almost Surely Asymptotically Constant Graph Neural Networks](https://mlsanity.com/paper/2403.03880/) (2024)

## Abstract (arXiv)

Local convergence has emerged as a fundamental tool for analyzing sparse random graph models. We introduce a new notion of local convergence, color convergence, based on the Weisfeiler-Leman algorithm. Color convergence fully characterizes the class of random graphs that are well-behaved in the limit for message-passing graph neural networks. Building on this, we propose the Refined Configuration Model (RCM), a random graph model that generalizes the configuration model. The RCM is universal with respect to local convergence among locally tree-like random graph models, including ErdHos-R'enyi, stochastic block and configuration models. Finally, this framework enables a complete characterization of the random trees that arise as local limits of such graphs.