Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
Authors:
Preprint
Abstract
We study the statistical performance of semidefinite programming (SDP) relaxations for clustering under random graph models. Under the $\mathbb{Z}_{2}$ Synchronization model, Censored Block Model and Stochastic Block Model, we show that SDP achieves an error rate of the form \[ \exp\Big[-\big(1-o(1)\big)\bar{n} I^* \Big]. \] Here $\bar{n}$ is an appropriate multiple of the number of nodes and $I^*$ is an information-theoretic measure of the signal-to-noise ratio. We provide matching lower bounds on the Bayes error for each model and therefore demonstrate that the SDP approach is Bayes optimal. As a corollary, our results imply that SDP achieves the optimal exact recovery threshold under each model. Furthermore, we show that SDP is robust: the above bound remains valid under semirandom versions of the models in which the observed graph is modified by a monotone adversary. Our proof is based on a novel primal-dual analysis of SDP under a unified framework for all three models, and the analysis shows that SDP tightly approximates a joint majority voting procedure.
Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Norms of random matrices: Local and global problemsAdvances in Mathematics, 2018
- A Proof of the Block Model Threshold ConjectureCombinatorica, 2017
- Achieving Exact Cluster Recovery Threshold via Semidefinite ProgrammingIEEE Transactions on Information Theory, 2016
- Exact Recovery in the Stochastic Block ModelIEEE Transactions on Information Theory, 2015
- Improved Graph ClusteringIEEE Transactions on Information Theory, 2014
- Reconstruction and estimation in the planted partition modelProbability Theory and Related Fields, 2014
- Singular vectors under random perturbationRandom Structures & Algorithms, 2011
- Heuristics for Semirandom Graph ProblemsJournal of Computer and System Sciences, 2001
- Coloring Random and Semi-Random k-Colorable GraphsJournal of Algorithms, 1995
- Stochastic blockmodels: First stepsSocial Networks, 1983