mlsanityData to 7 Oct 2026

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

arXiv 2510.21392 ↗First posted 24 Oct 2025cs.DM cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

18 of 43 references.

References · 18

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Inductive Representation Learning on Large Graphscited by 6,284
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2019Provably Powerful Graph Networkscited by 385
  5. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  6. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  7. 2020A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networkscited by 84
  8. 2014Exact Recovery in the Stochastic Block Modelcited by 77
  9. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  10. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  11. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  12. 2020Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networkscited by 31
6 more
  1. 2023WL meet VCcited by 30
  2. 2013Limits of local algorithms over sparse random graphscited by 23
  3. 2022Generalization Guarantee of Training Graph Convolutional Networks with Graph Topology Samplingcited by 23
  4. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  5. 2024Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphscited by 13
  6. 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7

Built on by

Not cited yet.