论文标题
光谱算法最佳恢复种植的子结构
Spectral Algorithms Optimally Recover Planted Sub-structures
论文作者
论文摘要
光谱算法是机器学习和图形算法的重要组成部分。我们有兴趣研究何时可以直接应用此类算法来为推理任务提供最佳解决方案。 Abbe，Fan，Wang和Zhong（2020）以及Dhara，Gaudio，Mossel和Sandon（2022）的先前作品显示了在随机块模型（SBM）中的社区检测最佳性，以及在SBM的审查变体中。在这里，我们表明，这种最优性有些普遍，因为它涉及其他种植的子结构，例如种植的密集子图问题和子矩阵本地化问题，以及对种植的密集子学问题的审查版本。
Spectral algorithms are an important building block in machine learning and graph algorithms. We are interested in studying when such algorithms can be applied directly to provide optimal solutions to inference tasks. Previous works by Abbe, Fan, Wang and Zhong (2020) and by Dhara, Gaudio, Mossel and Sandon (2022) showed the optimality for community detection in the Stochastic Block Model (SBM), as well as in a censored variant of the SBM. Here we show that this optimality is somewhat universal as it carries over to other planted substructures such as the planted dense subgraph problem and submatrix localization problem, as well as to a censored version of the planted dense subgraph problem.
