An Alon-Boppana Bound for the Non-Backtracking Operator

Abstract

For any fixed $k$, we prove a lower bound on the $k$th largest modulus of an eigenvalue of the non-backtracking matrix $B$. Specifically, consider any deterministic or random family of graphs that converges locally to the unimodular Galton-Watson tree with root degree distribution $D$, and set $\kappa:=\mathbb E[D(D-1)]/\mathbb E[D]$. Given $\kappa>1$ and an exponential-moment bound on the empirical degree distributions, we show that $|\lambda_k(B)|\geq\sqrt{\kappa}-o_N(1)$, where $N$ is the number of vertices. When restricted to locally tree-like regular graphs, this recovers a well-known consequence of the Ihara-Bass formula. In the specific case where the graph is generated through the Erd\H{o}s-R\'{e}nyi model with expected degree $d>1$, this proves a conjecture of Bordenave, Lelarge, and Massouli\'{e}. To do this, we show that the normalized log-determinant of the Bethe-Hessian of the graph is bounded by that of the Bethe-Hessian of its local limit. This bound is violated if the eigenvalues of the non-backtracking matrix are too small. We establish this using an effective-conductance interpretation of the tree Green's function recursion.