Robust Recovery for Stochastic Block Models, Simplified and Generalized
STOC ’24, June 24–28, 2024, Vancouver, BC, Canada
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/155672 |
| _version_ | 1826203822842707968 |
|---|---|
| author | Mohanty, Sidhanth Raghavendra, Prasad Wu, David X. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Mohanty, Sidhanth Raghavendra, Prasad Wu, David X. |
| author_sort | Mohanty, Sidhanth |
| collection | MIT |
| description | STOC ’24, June 24–28, 2024, Vancouver, BC, Canada |
| first_indexed | 2024-09-23T12:44:03Z |
| format | Article |
| id | mit-1721.1/155672 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:21:51Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1556722025-01-09T04:47:30Z Robust Recovery for Stochastic Block Models, Simplified and Generalized Mohanty, Sidhanth Raghavendra, Prasad Wu, David X. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory STOC ’24, June 24–28, 2024, Vancouver, BC, Canada We study the problem of robust community recovery: efficiently recovering communities in sparse stochastic block models in the presence of adversarial corruptions. In the absence of adversarial corruptions, there are efficient algorithms when the signal-to-noise ratio exceeds the Kesten–Stigum (KS) threshold, widely believed to be the computational threshold for this problem. The question we study is: does the computational threshold for robust community recovery also lie at the KS threshold? We answer this question affirmatively, providing an algorithm for robust community recovery for arbitrary stochastic block models on any constant number of communities, generalizing the work of Ding, d’Orsi, Nasser & Steurer on an efficient algorithm above the KS threshold in the case of 2-community block models. There are three main ingredients to our work: (1) The Bethe Hessian of the graph is defined as HG(t) ≜ (DG−I)t2 − AGt + I where DG is the diagonal matrix of degrees and AG is the adjacency matrix. Empirical work suggested that the Bethe Hessian for the stochastic block model has outlier eigenvectors corresponding to the communities right above the Kesten-Stigum threshold. We formally confirm the existence of outlier eigenvalues for the Bethe Hessian, by explicitly constructing outlier eigenvectors from the community vectors. (2) We develop an algorithm for a variant of robust PCA on sparse matrices. Specifically, an algorithm to partially recover top eigenspaces from adversarially corrupted sparse matrices under mild delocalization constraints. (3) A rounding algorithm to turn vector assignments of vertices into a community assignment, inspired by the algorithm of Charikar & Wirth for 2XOR. 2024-07-12T16:20:11Z 2024-07-12T16:20:11Z 2024-06-10 2024-07-01T07:51:24Z Article http://purl.org/eprint/type/ConferencePaper 979-8-4007-0383-6 https://hdl.handle.net/1721.1/155672 Mohanty, Sidhanth, Raghavendra, Prasad and Wu, David X. 2024. "Robust Recovery for Stochastic Block Models, Simplified and Generalized." PUBLISHER_CC en 10.1145/3618260.3649761 Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Mohanty, Sidhanth Raghavendra, Prasad Wu, David X. Robust Recovery for Stochastic Block Models, Simplified and Generalized |
| title | Robust Recovery for Stochastic Block Models, Simplified and Generalized |
| title_full | Robust Recovery for Stochastic Block Models, Simplified and Generalized |
| title_fullStr | Robust Recovery for Stochastic Block Models, Simplified and Generalized |
| title_full_unstemmed | Robust Recovery for Stochastic Block Models, Simplified and Generalized |
| title_short | Robust Recovery for Stochastic Block Models, Simplified and Generalized |
| title_sort | robust recovery for stochastic block models simplified and generalized |
| url | https://hdl.handle.net/1721.1/155672 |
| work_keys_str_mv | AT mohantysidhanth robustrecoveryforstochasticblockmodelssimplifiedandgeneralized AT raghavendraprasad robustrecoveryforstochasticblockmodelssimplifiedandgeneralized AT wudavidx robustrecoveryforstochasticblockmodelssimplifiedandgeneralized |