提出颜色收敛新概念，统一分析稀疏图极限行为。
On Local Limits of Sparse Random Graphs: Color Convergence and the Refined Configuration Model
- 基于魏斯费勒-莱曼算法定义颜色收敛新范式。
- 构建广义配置模型RCM，实现局部树状图的通用建模。
- 揭示消息传递GNN在极限下的稳定行为，适合图学习研究者。
局部收敛已成为分析稀疏随机图模型的核心工具。本文引入基于魏斯费勒-莱曼（Weisfeiler-Leman）算法的新局部收敛概念——颜色收敛，该概念完全刻画了对消息传递图神经网络而言具有良好极限行为的随机图类。在此基础上，提出一种推广的配置模型——精化配置模型（Refined Configuration Model, RCM），其在局部树状随机图模型中具有局部收敛意义下的普遍性，涵盖埃拉多什-雷尼（Erdős-Rényi）、随机块模型和标准配置模型等。最终，该框架实现了对这类图局部极限所产生随机树的完整表征。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。