Powered adjacency spectral clustering is optimally accurate in the geometric block model
Powered adjacency spectral clustering is optimally accurate in the geometric block model
Let denote the powered adjacency matrix, let be the graph diameter, and let with . Weak recovery means recovering the communities with nontrivial accuracy.
Powered adjacency conjecture. For all , , , and , the algorithm that finds the eigenvector of 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 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
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.