Subpolynomial-power spectral methods fail on dense geometric block models

Let $A^{(r)}$ and $B^{(r)}$ be the powered adjacency and powered nonbacktracking matrices. Let $m>0$, $s,t>0$, and suppose graphs drawn from $\mathrm{GBM}(n,s,t)$ have a single giant component with high probability. Weak recovery with optimal accuracy means recovering the communities as accurately as information-theoretically possible.

Subpolynomial-power failure conjecture. There exists $s_0>0$ such that, for all $m>0$, $s\geq s_0$, $t>0$, and $r=n^{o(1)}$, the algorithm that finds the second-largest-eigenvalue eigenvector of $A^{(r)}$ or $B^{(r)}$ and partitions vertices using the above-median versus below-median sums on incident edges does not recover communities with optimal accuracy on $\mathrm{GBM}(n,s,t)$.

The conjecture attributes failure at practical, subdiameter powers to long cycles and localization near high-degree regions. No resolution is supplied.