Non-Backtracking Walk Matrix and Kesten-Stigum Spectral Redemption

Non-Backtracking Walk Matrix and Kesten-Stigum Spectral Redemption is a spectral graph clustering framework introduced by Krzakala, Moore, Mossel, Neeman, Sly, Zdeborova, and Zhang (2013) that replaces the adjacency matrix A or graph Laplacian with the 2m x 2m Hashimoto directed-edge non-backtracking walk operator B_{(u -> v),(w -> x)} = 1(v = w and u != x) to detect communities in sparse networks down to the information-theoretic Kesten-Stigum belief-propagation phase transition. Whereas high-degree hubs and dangling trees generate localized eigenvectors of A with eigenvalues sqrt(d_max) that submerge the community eigenvector whenever c_in - c_out < sqrt(c) + 1/sqrt(c), non-backtracking walks cannot immediately reverse across an edge, annihilating tree components in the spectrum of B and confining all uninformative bulk eigenvalues of B inside the complex disk |lambda| <= sqrt(c). By the Ihara-Bass determinant formula det(I - z B) = (1 - z^2)^{m - n} det(I - z A + z^2(D - I)), all nontrivial eigenvalues and incoming-edge sum vectors g_v = sum_{u in partial v} v_{u -> v} can be computed from the compact 2n x 2n block matrix B' = [[0, D - I], [-I, A]] and thresholded by sign(g_v) whenever c_in - c_out > 2 sqrt(c).