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

About 8 years old · traced to

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(r′d)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.

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.