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

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