Conjecture that exact community recovery is possible near the matching threshold

Let $G_1$ and $G_2$ be correlated stochastic block model graphs with community assignment $\boldsymbol{\boldsymbol{\sigma}}$, parameters $\alpha$, $\beta$, and correlation parameter $s$. Let $\mathsf{ov}(\widehat{\boldsymbol{\sigma}},\boldsymbol{\sigma})$ denote the overlap between an estimator and the true community assignment, and let

denote the community-recovery achievability condition. **Exact community recovery conjecture.** There \exists $\epsilon=\epsilon(\alpha,\beta,s)>0$ such that, if

holds and

$$s^2\left(\frac{\alpha+\beta}{2}\right)\geq 1-\epsilon,$$

then there is an estimator $\widehat{\boldsymbol{\sigma}}=\widehat{\boldsymbol{\sigma}}(G_1,G_2)$ such that

$$\lim_{n\to\infty}\mathbb{P}\left(\mathsf{ov}(\widehat{\boldsymbol{\sigma}},\boldsymbol{\sigma})=1\right)=1.$$

The conjecture asks whether exact graph matching is necessary for exact community recovery. The preceding impossibility result is tight when $s^2(\alpha+\beta)/2>1$, while the precise information-theoretic threshold remains unknown when $s^2(\alpha+\beta)/2<1$, the regime where exact graph matching fails.