# Semidefinite Programs for Exact Recovery of a Hidden Community

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2016.

## Built on by (most cited first, 2 of 2)

- [Multiple Support Recovery Using Very Few Measurements Per Sample](https://mlsanity.com/paper/2105.09855/) (2021)
- [Spectral Algorithms Optimally Recover Planted Sub-structures](https://mlsanity.com/paper/2203.11847/) (2022)

## Abstract (arXiv)

We study a semidefinite programming (SDP) relaxation of the maximum likelihood estimation for exactly recovering a hidden community of cardinality K from an n × n symmetric data matrix A, where for distinct indices i,j, Aij ~ P if i, j are both in the community and Aij ~ Q otherwise, for two known probability distributions P and Q. We identify a sufficient condition and a necessary condition for the success of SDP for the general model. For both the Bernoulli case (P=rm Bern(p) and Q=rm Bern(q) with p>q) and the Gaussian case (P=N(μ,1) and Q=N(0,1) with μ>0), which correspond to the problem of planted dense subgraph recovery and submatrix localization respectively, the general results lead to the following findings: (1) If K=ω( n /log n), SDP attains the information-theoretic recovery limits with sharp constants; (2) If K=Theta(n/log n), SDP is order-wise optimal, but strictly suboptimal by a constant factor; (3) If K=o(n/log n) and K → ∞, SDP is order-wise suboptimal. The same critical scaling for K is found to hold, up to constant factors, for the performance of SDP on the stochastic block model of n vertices partitioned into multiple communities of equal size K. A key ingredient in the proof of the necessary condition is a construction of a primal feasible solution based on random perturbation of the true cluster matrix.