# Spectral Algorithms Optimally Recover Planted Sub-structures

arXiv: https://arxiv.org/abs/2203.11847 · HTML: https://mlsanity.com/paper/2203.11847/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 19 references that are in the map.
- First posted on arXiv 22 Mar 2022.

## Builds on (most cited first, 7 of 7)

- [Achieving Exact Cluster Recovery Threshold via Semidefinite Programming](https://mlsanity.com/paper/1412.6156/) (2014)
- [Information Limits for Recovering a Hidden Community](https://mlsanity.com/paper/1509.07859/) (2015)
- [Faster Eigenvector Computation via Shift-and-Invert Preconditioning](https://mlsanity.com/paper/1605.08754/) (2016)
- [A simple SVD algorithm for finding hidden partitions](https://mlsanity.com/paper/1404.3918/) (2014)
- [Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms](https://mlsanity.com/paper/1412.7335/) (2014)
- [Semidefinite Programs for Exact Recovery of a Hidden Community](https://mlsanity.com/paper/1602.06410/) (2016)
- [Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in O(|E| log^*|V|) Time](https://mlsanity.com/paper/1510.02786/) (2015)

## Abstract (arXiv)

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.