Spectral Algorithms Optimally Recover Planted Sub-structures
Souvik Dhara, Julia Gaudioa, Elchanan Mossel, Colin Sandonb
- a( ) The Simons Institute for the Theory of Computing , University of California , Berkeley ( )
- bDepartment of Industrial Engineering and Management Sciences , Northwestern University ( ) Department of Mathematics , Massachusetts Institute of Technology
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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.
TL;DRFor the PDS model, it is shown that a simple spectral algorithm based on the top two eigenvectors of the adjacency matrix can recover S (cid:63) up to the information theoretic threshold, and for the CDPS model, the information theoretic limit for the recovery problem is obtained. (Semantic Scholar)