Powered adjacency eigenvectors achieve weak recovery in the geometric block model

About 8 years old · traced to

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,t≥0s,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.

References

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.