Research map / Graph learning / Graph algorithms and clustering
On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces color convergence (defined via color refinement/Weisfeiler-Leman colors), shows it exactly characterizes MPNN probabilistic consistency of empirical risk, and proposes the Refined Configuration Model, a universal sparse random graph model for color/local limits.
Problem
Local convergence does not capture what MPNNs can distinguish, and there is no universal sparse random graph limit; the paper asks which random graphs allow MPNNs to learn (generalize) from a single large graph for node classification.
Approach
Define color convergence via convergence in probability of the distribution of depth-k color refinement trees of uniformly sampled nodes; prove it is equivalent to MPNN consistency of empirical risk, and build the refined configuration model (typed configuration model with per-type stub matching) that is universal for color convergence and local convergence to Galton-Watson trees.
Key results
- Color convergence is shown to be equivalent to probabilistic consistency of empirical risk for all k-layer MPNNs on random graphs (theorem).
- Every sofic PMF on refinement colors is realized as the color-convergence limit of some RCM with involution-invariant finite-degree parameters (corollary).
- For locally tree-like graphs, color convergence and local convergence to depth k are equivalent (proposition).
Surprising findings
- Dense Erdős–Rényi graphs with growing average degree are incompatible with MPNN learning, since empirical risk fails to concentrate.
- Color convergence is strictly weaker than local convergence: a deterministic graph of triangles or a single cycle is color convergent but not locally convergent.
Limitations
- Results are limited to the expressivity of color refinement; higher-order GNNs and subgraph-based models are not covered.
- No convergence rates or error bounds for learnability are established.
- Guarantees hold only for fixed depth k, so deep dependencies may not be captured.
Experimental setup
Metrics: convergence in probability of color distributions empirical vs true risk gap
Baselines: Erdős–Rényi stochastic block model configuration model
Builds on: configuration model local weak convergence color refinement
Closest papers by meaning
- Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.88)
- Random Sparse Lifts: Construction, Analysis and Convergence of finite sparse networks (ICLR 2024 · similarity 0.86)
- The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis (NeurIPS 2025 · similarity 0.85)
- How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step? (NeurIPS 2026 · similarity 0.85)
- Random Search Neural Networks for Efficient and Expressive Graph Learning (NeurIPS 2025 · similarity 0.85)
- Convergence Guarantees for the DeepWalk Embedding on Block Models (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.