Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions

Jingqiu Ding, Tommaso d’Orsi, Yiding Hua, David Steurer
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:4044-4071, 2023.

Abstract

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 Z2 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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v195-hua23a, title = {Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions}, author = {Ding, Jingqiu and d'Orsi, Tommaso and Hua, Yiding and Steurer, David}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {4044--4071}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/hua23a/hua23a.pdf}, url = {https://proceedings.mlr.press/v195/hua23a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions %A Jingqiu Ding %A Tommaso d’Orsi %A Yiding Hua %A David Steurer %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-hua23a %I PMLR %P 4044--4071 %U https://proceedings.mlr.press/v195/hua23a.html %V 195 %X 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.
APA
Ding, J., d’Orsi, T., Hua, Y. & Steurer, D.. (2023). Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:4044-4071 Available from https://proceedings.mlr.press/v195/hua23a.html.

Related Material