Powered adjacency spectral clustering achieves weak recovery above the SBM threshold
Powered adjacency spectral clustering achieves weak recovery above the SBM threshold
Let be the two-community stochastic block model, let be its powered adjacency matrix, and let 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 satisfy , let , and let . If is the eigenvector of with eigenvalue of second-largest absolute value, then dividing the vertices into those with entries in 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.