Powered adjacency eigenvectors achieve weak recovery in the geometric block model

Let GBM(n,s,t)\mathrm{GBM}(n,s,t) be the geometric block model, let GG be a graph from this model, let d=diam(G)d=\operatorname{diam}(G), and let A(r)A^{(r)} denote the powered adjacency matrix. For sufficiently small ε>0\varepsilon>0, set r=εdr=\varepsilon d. Weak recovery is the task of recovering the communities with nontrivial accuracy.

Powered adjacency conjecture. Let s,t0s,t\geq 0 and suppose GBM(n,s,t)\mathrm{GBM}(n,s,t) has a giant component. Taking the second-largest eigenvector of A(r)A^{(r)}, with r=εdiam(G)r=\varepsilon\cdot\operatorname{diam}(G) for sufficiently small ε\varepsilon, and rounding it by signs or by the median solves weak recovery in GBM(n,s,t/n)\mathrm{GBM}(n,s,t/\sqrt{n}) 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

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.