多图关联下实现精准社区划分的理论边界
Harnessing Multiple Correlated Networks for Exact Community Recovery
- 利用多个相关网络的联合信息进行社区推断
- 证明了任意常数个网络下精确社区恢复的理论阈值
- 在无法完全匹配顶点的情况下仍可实现社区恢复
本文研究从多个相关网络中学习隐含社区结构的问题，聚焦于两个平衡社区的边相关随机块模型。先前的工作（Gaudio, Rácz, Sridhar, COLT 2022）确定了使用两个相关图进行精确社区恢复的信息论阈值；特别地，揭示了社区恢复与图匹配之间的微妙关系。本文研究更自然的多于两个图的情形。主要挑战在于：当任意两图间的潜在顶点对应关系都无法精确恢复时，如何聚合多个图的信息。我们的主要结果给出了任意常数个相关图下精确社区恢复的精确信息论阈值，回答了Gaudio、Rácz和Sridhar提出的问题。具体而言，对每个 $K \geq 3$，我们发现并刻画了一个参数空间区域，在该区域内，使用 $K$ 个相关图可以实现精确社区恢复，尽管（1）使用其中任意 $K-1$ 个图在信息论上不可能实现，且（2）所有潜在匹配均无法精确恢复。
原文摘要 · Abstract (English)
We study the problem of learning latent community structure from multiple correlated networks, focusing on edge-correlated stochastic block models with two balanced communities. Recent work of Gaudio, Rácz, and Sridhar (COLT 2022) determined the precise information-theoretic threshold for exact community recovery using two correlated graphs; in particular, this showcased the subtle interplay between community recovery and graph matching. Here we study the natural setting of more than two graphs. The main challenge lies in understanding how to aggregate information across several graphs when none of the pairwise latent vertex correspondences can be exactly recovered. Our main result derives the precise information-theoretic threshold for exact community recovery using any constant number of correlated graphs, answering a question of Gaudio, Rácz, and Sridhar (COLT 2022). In particular, for every $K \geq 3$ we uncover and characterize a region of the parameter space where exact community recovery is possible using $K$ correlated graphs, even though (1) this is information-theoretically impossible using any $K-1$ of them and (2) none of the latent matchings can be exactly recovered.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。