Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
- 13 January 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (6) , 3929-3953
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 (CBM) and Stochastic Block Model (SBM), we show that SDP achieves an error rate of the form $\exp [-(1-o(1)) \bar { n}{ {I}^{*}}]$ . 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
Funding Information
- National Science Foundation (1657420, CCF-1704828)
- School of Operations Research and Information Engineering, Cornell University
This publication has 40 references indexed in Scilit:
- Robust and computationally feasible community detection in the presence of arbitrary outlier nodesThe Annals of Statistics, 2015
- Decoding Binary Node Labels from Censored Edge Measurements: Phase Transition and Efficient RecoveryIEEE Transactions on Network Science and Engineering, 2014
- Improved Graph ClusteringIEEE Transactions on Information Theory, 2014
- Reconstruction and estimation in the planted partition modelProbability Theory and Related Fields, 2014
- Rényi divergence measures for commonly used univariate continuous distributionsInformation Sciences, 2013
- Singular vectors under random perturbationRandom Structures & Algorithms, 2011
- Heuristics for Semirandom Graph ProblemsJournal of Computer and System Sciences, 2001
- Local Operator Theory, Random Matrices and Banach Spaces2001
- Coloring Random and Semi-Random k-Colorable GraphsJournal of Algorithms, 1995
- Stochastic blockmodels: First stepsSocial Networks, 1983