TY - GEN

T1 - Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees

AU - Mossel, Elchanan

AU - Sly, Allan

AU - Sohn, Youngtak

N1 - Publisher Copyright:
© 2023 Owner/Author.

PY - 2023/6/2

Y1 - 2023/6/2

N2 - In this paper, we rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block model, in particular in the case of q=3 and q=4 communities. We prove that for q=3 and q=4 there is no computational-statistical gap if the average degree is above some constant by showing that it is information theoretically impossible to detect below the Kesten-Stigum bound. We proceed by showing that for the broadcast process on Galton-Watson trees, reconstruction is impossible for q=3 and q=4 if the average degree is sufficiently large. This improves on the result of Sly (2009), who proved similar results for d-regular trees when q=3. Our analysis of the critical case q=4 provides a detailed picture showing that the tightness of the Kesten-Stigum bound in the antiferromagnetic regime depends on the average degree of the tree. We also prove that for q≥ 5, the Kesten-Stigum bound is not sharp. Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborová (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborová (2019). Our proofs are based on a new general coupling of the tree and graph processes and on a refined analysis of the broadcast process on the tree.

AB - In this paper, we rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block model, in particular in the case of q=3 and q=4 communities. We prove that for q=3 and q=4 there is no computational-statistical gap if the average degree is above some constant by showing that it is information theoretically impossible to detect below the Kesten-Stigum bound. We proceed by showing that for the broadcast process on Galton-Watson trees, reconstruction is impossible for q=3 and q=4 if the average degree is sufficiently large. This improves on the result of Sly (2009), who proved similar results for d-regular trees when q=3. Our analysis of the critical case q=4 provides a detailed picture showing that the tightness of the Kesten-Stigum bound in the antiferromagnetic regime depends on the average degree of the tree. We also prove that for q≥ 5, the Kesten-Stigum bound is not sharp. Our results prove conjectures of Decelle, Krzakala, Moore, Zdeborová (2011), Moore (2017), Abbe and Sandon (2018) and Ricci-Tersenghi, Semerjian, and Zdeborová (2019). Our proofs are based on a new general coupling of the tree and graph processes and on a refined analysis of the broadcast process on the tree.

KW - Broadcast models

KW - Community detection

KW - Reconstruction on trees

KW - Stochastic block models

UR - http://www.scopus.com/inward/record.url?scp=85163094944&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85163094944&partnerID=8YFLogxK

U2 - 10.1145/3564246.3585155

DO - 10.1145/3564246.3585155

M3 - Conference contribution

AN - SCOPUS:85163094944

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 96

EP - 102

BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing

A2 - Saha, Barna

A2 - Servedio, Rocco A.

PB - Association for Computing Machinery

T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023

Y2 - 20 June 2023 through 23 June 2023

ER -