Powered adjacency spectral clustering achieves weak recovery above the SBM threshold

About 8 years old · traced to

Let SBM(n,a,b)\mathrm{SBM}(n,a,b) be the two-community stochastic block model, let A(r)A^{(r)} be its powered adjacency matrix, and let ww be an eigenvector associated with the eigenvalue of second-largest absolute value. Weak recovery means recovering the communities with nontrivial accuracy.

Powered adjacency recovery conjecture. Let a,b≥0a,b\geq 0 satisfy (a−b)2>2(a+b)(a-b)^2>2(a+b), let r=Θ(log⁡n)r=\Theta(\sqrt{\log n}), and let G∼SBM(n,a,b)G\sim\mathrm{SBM}(n,a,b). If ww is the eigenvector of A(r)A^{(r)} with eigenvalue of second-largest absolute value, then dividing the vertices into those with entries in ww above the median and those with entries below the median solves weak recovery.

The inequality is the stated spectral detectability condition, and the conjecture claims that a square-root-logarithmic power suffices. The source gives no resolution.

References

Primary source

Emmanuel Abbe, Enric Boix, Peter Ralli and Colin Sandon, “Graph powering and spectral robustness”, arXiv:1809.04818 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.