Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Abstract

The binary symmetric stochastic block model deals with a random graph of n vertices partitioned into two equal-sized clusters, such that each pair of vertices is connected independently with probability p within clusters and q across clusters. In the asymptotic regime of p=a n/n and q=b n/n for fixed a,b and n , we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold for exactly recovering the partition from the graph with probability tending to one, resolving a conjecture of Abbe et al. Abbe14. Furthermore, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold in the planted dense subgraph model containing a single cluster of size proportional to n.

Tasks

Reproductions