Achieving the Bayes Error Rate in Synchronization and Block Models by SDP, Robustly
This provides a theoretically optimal and robust solution for clustering in network analysis, with implications for community detection and synchronization problems.
The paper demonstrates that semidefinite programming (SDP) relaxations achieve the Bayes error rate, with an error rate of exp[-(1-o(1))n̄ I*], for clustering under random graph models including Z₂ Synchronization, Censored Block Model, and Stochastic Block Model, and shows robustness against adversarial modifications.
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.