Contextual Stochastic Block Model: Sharp Thresholds and Contiguity

Chen Lu, Subhabrata Sen; 24(54):1−34, 2023.

Abstract

This study focuses on community detection in the “contextual stochastic block model” (Yan and Sarkar, 2020; Deshpande et al., 2018). Deshpande et al. (2018) previously examined this problem in the context of sparse graphs with high-dimensional node-covariates. They used the non-rigorous “cavity method” from statistical physics (Mezard and Montanari, 2009) to calculate the sharp limit for community detection in this scenario. They also verified that the limit aligns with the information theoretic threshold when the average degree of the observed graph is large. Furthermore, they conjectured that the limit remains valid as long as the average degree exceeds one. This study confirms this conjecture and characterizes the sharp threshold for detection and weak recovery.

[abs]

[pdf][bib]