Non-backtracking eigenvalues and eigenvectors of random regular graphs and hypergraphs

The non-backtracking operator of a graph is a powerful tool in spectral graph theory and random matrix theory. Most existing results for the non-backtracking operator of a random graph concern only eigenvalues or top eigenvectors. In this paper, we take the first step in analyzing its bulk eigenvector behaviors. We demonstrate that for the non-backtracking operator B of a random d -regular graph, its eigenvectors corresponding to nontrivial eigenvalues are completely delocalized with high probability. Additionally, we show complete delocalization for a reduced 2 n × 2 n non-backtracking matrix B ˜ . By projecting all eigenvalues of B ˜ onto the real line, we obtain an empirical measure that converges weakly in probability to the Kesten-McKay law for fixed d ≥ 3 and to a semicircle law as d → ∞ with n → ∞ . We extend our analysis to random regular hypergraphs, including the limiting measure of the real part of the spectrum for B ˜ , ℓ ∞ -norm bounds for the eigenvectors of B ˜ and B , and a deterministic relation between eigenvectors of B and the eigenvectors of the adjacency matrix. As an application, we analyze the non-backtracking spectrum of the ( d 1 , d 2 ) -regular stochastic block model (RSBM) and provide a spectral method based on eigenvectors of B ˜ to recover the community structure exactly. We also show that there exists an isolated real eigenvalue with an informative eigenvector inside the circle of radius d 1 + d 2 − 1 in the spectrum of B , analogous to the “eigenvalue insider” phenomenon previously observed for the Erdős-Rényi stochastic block model.