Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
This provides a theoretical guarantee for clustering algorithms in network analysis, though it is incremental as it confirms an existing conjecture.
The paper tackles the problem of exactly recovering clusters in stochastic block models and planted dense subgraph models, showing that a semidefinite programming relaxation achieves the optimal threshold for exact recovery with probability tending to one, resolving a known conjecture.
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 \log n/n$ and $q=b \log n/n$ for fixed $a,b$ and $n \to \infty$, 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. \cite{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$.