Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
This addresses the problem of robust community detection for network analysis under adversarial corruptions, representing a significant advance over prior state-of-the-art methods that failed near the Kesten-Stigum threshold.
The paper tackles robust community detection in the stochastic block model with node corruptions, presenting the first polynomial-time algorithm that achieves weak recovery at the Kesten-Stigum threshold despite a constant fraction of corrupted nodes, and extends this to the Z2 synchronization problem with optimal recovery thresholds.
We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $n$ vertices. We present the first polynomial-time algorithm that achieves weak recovery at the Kesten-Stigum threshold even in the presence of a small constant fraction of corrupted nodes. Prior to this work, even state-of-the-art robust algorithms were known to break under such node corruption adversaries, when close to the Kesten-Stigum threshold. We further extend our techniques to the $Z_2$ synchronization problem, where our algorithm reaches the optimal recovery threshold in the presence of similar strong adversarial perturbations. The key ingredient of our algorithm is a novel identifiability proof that leverages the push-out effect of the Grothendieck norm of principal submatrices.