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.

本文提出了一种算法，用于在恶意干扰下检测包含损坏节点的随机模型中的社区结构，并在 $Z_2$ 同步问题中实现了最优恢复阈值。借助关键的可识别性证明和Grothendieck范数的推动效应，该算法突破了Kesten-Stigum阈值的技术瓶颈。

在节点损坏下的随机块模型达到Kesten-Stigum阈值