Powered adjacency eigenvectors achieve weak recovery in the geometric block model
Let be the geometric block model, let be a graph from this model, let , and let denote the powered adjacency matrix. For sufficiently small , set . Weak recovery is the task of recovering the communities with nontrivial accuracy.
Powered adjacency conjecture. Let and suppose has a giant component. Taking the second-largest eigenvector of , with for sufficiently small , and rounding it by signs or by the median solves weak recovery in whenever weak recovery is solvable.
The conjecture asserts that graph powering followed by a spectral partition reaches the efficient weak-recovery threshold in the geometric block model. No resolution is supplied in the source.
References
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
No solutions have been posted yet.