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.
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: