Minimax Rates for Robust Community Detection

arXiv2207.11903MaRDI QIDQ6405896FDOQ6405896

Authors: Allen P. Liu, Ankur Moitra 

Publication date: 25 July 2022

Abstract: In this work, we study the problem of community detection in the stochastic block model with adversarial node corruptions. Our main result is an efficient algorithm that can tolerate an $epsilon$-fraction of corruptions and achieves error $O(epsilon)+e^{-fracC2(1pmo(1))}$ where $C=(sqrta-sqrtb{)}^2$ is the signal-to-noise ratio and $a/n$ and $b/n$ are the inter-community and intra-community connection probabilities respectively. These bounds essentially match the minimax rates for the SBM without corruptions. We also give robust algorithms for $mathbb{Z}_2$-synchronization. At the heart of our algorithm is a new semidefinite program that uses global information to robustly boost the accuracy of a rough clustering. Moreover, we show that our algorithms are doubly-robust in the sense that they work in an even more challenging noise model that mixes adversarial corruptions with unbounded monotone changes, from the semi-random model.

This page was built for publication: Minimax Rates for Robust Community Detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405896)