Nonbacktracking spectral clustering is not optimally accurate in the geometric block model
Nonbacktracking spectral clustering is not optimally accurate in the geometric block model
Let , where and are chosen so that has a single giant component with high probability. Let be the nonbacktracking walk matrix of the main component. Weak recovery is performed by partitioning vertices according to the median of the sums of eigenvector entries on incident directed edges.
Nonbacktracking failure conjecture. Computing the eigenvector of with the second-largest eigenvalue and dividing the vertices into those with above-median and below-median sums of its entries does not recover the communities with optimal accuracy.
The conjecture reflects the claim that short cycles and feedback in the geometric block model undermine the usual nonbacktracking spectral method. The source gives no resolution.
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.