Nonbacktracking spectral clustering is not optimally accurate in the geometric block model

Let GGBM(n,s,t)G\sim\mathrm{GBM}(n,s,t), where ss and tt are chosen so that GG has a single giant component with high probability. Let BB 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 BB 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

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.