Relative mutual-information loss conjecture for shuffled stochastic block models

Let $(G_1,G_2)\sim \rho$-SBM$(K,\vec{n},b,\Lambda)$, with $K$ and $\Lambda$ fixed in $n$, and let $\boldsymbol{\sigma}$ be uniformly distributed on $\Pi(n)$. Relative information-loss conjecture. If $\rho=o(\sqrt{\log n/n})$, then

$$\frac{I(G_1;G_2)-I(G_1;\boldsymbol{\sigma}(G_2))}{I(G_1;G_2)}=\Theta(1).$$

This conjectures that below the matchability threshold, a nontrivial fraction of the mutual information between the two graphs is lost under vertex shuffling. The preceding theorem establishes non-matchability in a related low-correlation regime, but the asserted information-loss estimate is not proved in the supplied text.