Reaching Kesten-Stigum Threshold in the Stochastic Block Model under
  Node Corruptions
Jingqiu Ding Tommaso d'Orsi Yiding Hua David Steurer
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.