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

Abstract

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 Erdős–Rényi, stochastic block and configuration models. Finally, this framework enables a complete characterization of the random trees that arise as local limits of such graphs.

PDF NeurIPS OpenReview Semantic Scholar

Cite

Text

Pluska and Malhotra. "On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model." Advances in Neural Information Processing Systems, 2025.

Markdown

[Pluska and Malhotra. "On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model." Advances in Neural Information Processing Systems, 2025.](https://mlanthology.org/neurips/2025/pluska2025neurips-local/)

BibTeX

@inproceedings{pluska2025neurips-local,
  title     = {{On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model}},
  author    = {Pluska, Alexander and Malhotra, Sagar},
  booktitle = {Advances in Neural Information Processing Systems},
  year      = {2025},
  url       = {https://mlanthology.org/neurips/2025/pluska2025neurips-local/}
}