Powered adjacency spectral clustering achieves weak recovery above the SBM threshold

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,b0a,b\geq 0 satisfy (ab)2>2(a+b)(a-b)^2>2(a+b), let r=Θ(logn)r=\Theta(\sqrt{\log n}), and let GSBM(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.

Sources & referencesView supporting material

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.