Powered adjacency eigenvectors achieve weak recovery in the geometric block model
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.
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.