Exact recovery in Gaussian weighted stochastic block model and planted dense subgraphs: Statistical and algorithmic thresholds

Understand

In this paper, we study the exact recovery problem in the Gaussian weighted version of the Stochastic block model with two symmetric communities.

• We provide the information-theoretic threshold in terms of the signal-to-noise ratio (SNR) of the model and prove that when SNR $<1$, no statistical estimator can exactly recover the community structure with probability bounded away from zero.
• On the other hand, we show that when SNR $>1$, the Maximum likelihood estimator itself succeeds in exactly recovering the community structure with probability approaching one.
• Then, we provide two algorithms for achieving exact recovery.