Jun, 2024
准确社群恢复（在给定辅助信息下）：谱算法的最优性
Exact Community Recovery (under Side Information): Optimality of
Spectral Algorithms
TL;DR在这篇论文中，我们研究了在一般的二元博弈和高斯矩阵模型中的精确社区恢复问题，这两种模型分别捕捉了随机块模型、子矩阵定位和Z2同步作为特例。我们还研究了有关社区分配标签的智能信息可用的情况，将其建模为通过噪声通道传递真实标签：二进制擦除通道（其中某些社区标签已知而其他被抹去）或二进制对称通道（其中某些标签被翻转）。我们对智能信息对精确恢复的信息论极限的影响提供了统一的分析，扩展了之前的研究并拓展到新的设定。此外，我们设计了一个简单但最优的谱算法，将智能信息（如有）与矩阵观测的特征向量结合起来。利用入元素特征向量分析的强大工具[Abbe, Fan, Wang, Zhong 2020]，我们表明我们的谱算法可以模仿所谓的“精灵辅助估计器”，其中第i个精灵辅助估计器在精灵揭示其他标签的情况下，最优计算第i个标签的估计。这一观点为最近的一系列工作中各种精确恢复问题的谱算法的最优性提供了统一的理解。