Powered adjacency spectral clustering is optimally accurate in the geometric block model

Let A(r)A^{(r)} denote the powered adjacency matrix, let dd be the graph diameter, and let m,s,t>0m,s,t>0 with 0<r<1/20<r'<1/2. Weak recovery means recovering the communities with nontrivial accuracy.

Powered adjacency conjecture. For all m>0m>0, s>0s>0, t>0t>0, and 0<r<1/20<r'<1/2, the algorithm that finds the eigenvector of A(rd)A^{(r'd)} with the second-largest eigenvalue and then divides the vertices according to whether the entries corresponding to incident edges lie above or below the median recovers the communities on GBM(n,s,t)\mathrm{GBM}(n,s,t) with optimal accuracy.

This is presented as the adjacency-matrix analogue of the powered nonbacktracking claim, motivated by the abundance of short cycles in the geometric block model. No resolution is stated.

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.