Source-linked AI summary
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
Charles Bordenave, Marc Lelarge, Laurent Massoulié
TL;DR
The paper asks whether non-backtracking spectra can characterize sparse random graphs and support community detection at the conjectured feasibility threshold. It analyzes leading eigenvalues and eigenvectors in Erdős-Rényi and stochastic block models, proving spectral separation and confirming the spectral redemption conjecture. The results also yield consequences for Ihara zeta poles and non-regular Ramanujan behavior.
Problem
The paper addresses whether communities can be detected from leading non-backtracking eigenvectors above the feasibility threshold |µ2| > √α.
Method
The paper analyzes the non-backtracking spectrum of sparse Erdős-Rényi and stochastic block model graphs through leading eigenvalues, eigenvectors, and powers of B.
Results
The r0 leading eigenvalues of B are asymptotic to µ1,...,µr0, while the remaining eigenvalues have modulus at most (1 + o(1))√α.
Takeaways & Limitations
The results prove the spectral redemption conjecture and characterize the leading eigen-elements relevant to community detection with an arbitrary number of communities.
Takeaways & Limitations
For Erdős-Rényi graphs, the paper conjectures the lower bound |λ2(B)| ≥ √α −o(1) but proves only a weaker lower bound.
Abstract
from arXiv · showhide
A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.
1 Introduction
The paper studies the non-backtracking spectrum of sparse Erdős-Rényi and Stochastic Block Model graphs, characterizing leading eigenvalues and eigenvectors as the number of vertices grows. These results establish spectral community detection above the feasibility threshold and connect sparse random graphs to non-regular Ramanujan phenomena.
- Non-backtracking matrices: The non-backtracking matrix B is indexed by oriented edges and encodes transitions that do not immediately reverse the preceding edge.Its powers count non-backtracking walks in the graph.
- Problem setting: The paper characterizes the asymptotic leading eigenvalues and associated eigenvectors of B for sparse random graphs as n →∞.The focus is the regime where expected node degrees remain of order 1.
- Main spectral result: For a stochastic block model with expected degree α, the r0 leading eigenvalues of B are asymptotic to µ1,...,µr0, while the remaining eigenvalues have modulus at most (1 + o(1))√α.Here r0 is determined by the eigenvalues of the expected adjacency matrix relative to √α.
- Community detection: The work proves the spectral redemption conjecture and characterizes the leading eigen-elements relevant to community detection with an arbitrary number of communities.The conjectured detectability threshold is |µ2| > √α.
- Ihara zeta connection: The non-backtracking spectrum also determines the localization of poles of the Ihara zeta function because those poles are reciprocals of B’s eigenvalues.This follows from the Ihara zeta identity involving B.
- Ramanujan interpretation: For Erdős-Rényi graphs, the results imply ρB ∼α and all other eigenvalues satisfy |λ| ≤√α + o(1) with high probability.This gives an analogue of Friedman’s theorem and supports a non-regular graph Riemann-hypothesis interpretation.
2 Preliminaries on non-backtracking matrices
The preliminaries develop a symmetry-based analysis of powers of the non-backtracking matrix and relate its singular values to graph structure. They also introduce non-backtracking analogues of spectral-gap, expansion, diameter, and Alon-Boppana ideas.
- Spectral analysis: For large k, the decomposition of B^k is used to study the eigenvalues and eigenvectors of B, with nearly orthogonal vectors associated with distinct limiting modes.The paper exploits this phenomenon in its main proofs.
- Oriented path symmetry: Although B is generally non-normal, the involution reversing oriented edges makes B^kP symmetric.This yields a singular value decomposition of B^k through the eigenvectors of B^kP.
- Oriented path symmetry: For k = 1, the singular values of B depend only on the graph’s degree sequence, with eigenvalues of BP given by deg(v)−1 and −1 with multiplicity m−n.Larger powers are expected to carry more structural information about the graph.
- Diameter bounds: If x1,k(e)x1,k(f) > s2,k/s1,k, then the initial vertices of e and f are at graph distance at most k + 1.The bound follows from the non-backtracking walk expansion and an s2,k control on the remaining singular components.
- Expansion inequalities: The quantity E_k(X,Y) measures non-backtracking connectivity between edge-symmetric sets over proximity range k + 1, supporting a k-th expansion ratio.The associated spectral gap is σ1,k −σ2,k.
- Spectral bounds: The Perron eigenvalue of B equals the universal-cover growth rate when G is connected, while non-backtracking walk counts provide a lower bound on the second singular value of B^k.These facts parallel classical spectral statements for adjacency matrices.
3 Main results
The paper establishes non-backtracking spectral results for sparse Erdős–Rényi graphs and stochastic block models, including eigenvector alignment and implications for community estimation.
- Erdős–Rényi graphs: The normalized Perron–Frobenius eigenvector associated with λ1(B) is asymptotically aligned with the paper’s specified reference vector.
- Stochastic Block Model: For the stochastic block model, λk(B) = µk + o(1) for k ∈ [r0], while all later eigenvalues satisfy |λk(B)| ≤ √α + o(1).
- Stochastic Block Model: When µk is a simple eigenvalue of M, the corresponding normalized eigenvector is asymptotically aligned with the paper’s specified type-dependent vector, and such eigenvectors are asymptotically orthogonal.
- Community estimation: Non-trivial estimation of node types is feasible from eigenvectors {ξk}2≤k≤r0 when r0 > 1, using the paper’s overlap criterion.
- Community estimation: For equal-sized communities and a simple informative eigenvalue µk with k ∈ {2, …, r0}, thresholding with a suitable signing and partition yields asymptotically positive overlap.
4 Algebraic tools: Perturbation of Eigenvalues and Eigenvectors
The section develops perturbation tools for locating eigenvalues and eigenvectors of structured, not necessarily symmetric matrices. Bauer-Fike is applied after decomposing the matrices into a diagonal part plus a controlled perturbation.
- Perturbation theorem: Bauer-Fike bounds eigenvalues of a perturbed diagonalizable matrix using the perturbation size and the diagonalizing matrix.The theorem is stated for D = V^−1ΛV with perturbation E, and applies to every eigenvalue of D + E.
- Rank-one perturbations: The leading eigenvalue λ1 is simple, and its eigenvector is close to the normalized vector xℓ.Proposition 7 establishes both eigenvalue simplicity and an eigenvector approximation under the perturbation assumptions.
- Rank-one perturbations: The rank-one analysis writes S = UDU^−1 and reduces Ak to D + U^−1RkU.The eigenvalues of Ak coincide with those of the perturbed diagonal matrix, while the condition number of U controls the perturbation bound.
- Rank-one perturbations: A unique eigenvalue of Ak lies near ν, while all remaining eigenvalues lie near zero.Under the stated separation condition, the corresponding disks are disjoint, yielding a simple leading eigenvalue.
- Higher-rank perturbations: The arbitrary-rank extension matches leading eigenvalues of A to the rank-r signal values and gives eigenvector control when the corresponding signal value is simple.The perturbation argument separates distinct diagonal eigenvalues and identifies a permutation matching λi with νs(i).
5 Erd˝os-R´enyi graph: proof strategy for Theorem 3
The Erdős-Rényi proof combines local branching-process analysis with a matrix expansion and norm bounds for non-backtracking walks. These ingredients establish the leading eigenvalue scale and control the remaining spectrum with high probability.
- Spectral conclusion: w.h.p., the signal scale satisfies c0α^ℓ ≤ θ ≤ c1α^ℓ, while the leading eigenvector aligns with the normalized Perron vector.The proof then applies the perturbation proposition to transfer these estimates to B.
- Spectral conclusion: The second spectral scale is asymptotically tight up to logarithmic factors, giving a weak Ramanujan property for Erdős-Rényi graphs.w.h.p., s2,ℓ is bounded below by c0α^ℓ/2, matching the upper bound up to logarithmic factors.
- Local analysis: Local neighborhoods are coupled to a Galton-Watson branching process to analyze neighborhood statistics and derive weak laws.The argument combines branching-process estimates with asymptotic decorrelation between neighborhoods.
- Matrix expansion: The non-backtracking matrix B^(ℓ) is expanded into tractable terms using a matrix expansion for tangle-free graphs.The expansion is paired with norm inequalities and the decomposition of K^2 into L + χχ* components.
- Norm control: w.h.p., G is ℓ-tangle-free for ℓ ∼ κ log_α n with κ < 1/2.This structural property permits the tangle-free matrix bounds used in the proof.
6 Proof of Proposition 14: path count combinatorics
The proof of Proposition 14 uses the trace method and combinatorial encodings of non-backtracking path families. Tangle-free structure limits cycling patterns, enabling the required norm bounds.
- Moment method: The method of moments reduces norm estimates to bounding traces of powers of path-counting matrices.Expectations are evaluated using independence of Erdős-Rényi edges.
- Moment bounds: Nonzero trace contributions require every relevant unoriented edge to be visited at least twice.This restriction sharply limits the possible path graphs and supports the moment estimates.
- Path encoding: Canonical path families are encoded by first times, tree edges, excess edges, and marks that permit reconstruction.The enumeration tracks vertices and edges visited by sequences of non-backtracking paths.
- Norm bounds: The canonical-path enumeration and Markov inequality produce the norm bounds in Proposition 14.The argument uses the bounds on numbers of vertices and edges together with the chosen moment parameter m.
- Path encoding: Tangle-free paths have controlled short-cycling and long-cycling times, yielding an enumeration bound for path families.At most one short cycling time and a bounded number of long cycling times occur on each path under the stated conditions.
- Norm bounds: The bound on ∥KB^(k)∥ improves the crude product estimate by a factor √n.This improvement follows because ∥K∥ is of order n.
7 Stochastic Block Model : proof of Theorem 4
The stochastic block model proof decomposes B^ℓ into signal subspaces and a remainder, then applies the higher-rank perturbation result. Local analysis and combinatorial norm bounds control the approximation errors.
- Signal decomposition: The proof introduces vectors χk and separates signal directions according to their associated parameters θk.The decomposition distinguishes indices with θk = 0 from those with nonzero signal values.
- Signal decomposition: Proposition 19 supplies high-probability control of the signal vectors and their orthogonalization.Gram-Schmidt produces an orthonormal family while preserving the relevant approximations.
- Remainder control: Proposition 20 provides the complementary high-probability norm control needed for the perturbation argument.Its proof uses a matrix expansion together with combinatorial norm bounds parallel to the Erdős-Rényi analysis.
- Remainder control: B^ℓ is decomposed as D0 + R, with D0 acting on the principal signal subspace and R collecting the remaining terms.The remainder is further written as C + D1 to handle the two signal groups separately.
- Spectral conclusion: Applying Proposition 8 to this decomposition yields Theorem 4 w.h.p.The preceding approximations allow the perturbation result to be used with the orthogonalized signal vectors.
8 Controls on the growth of Poisson multi-type branching processes
This section develops martingale and moment controls for multi-type Poisson Galton–Watson processes, including cross-generation functionals used later in the local analysis.
- Branching-process setup: Multi-type branching processes assign Poi(M_ij) offspring of type i to particles of type j and track generation populations through Z_t.The natural filtration F_t supports the martingale arguments.
- Martingale controls: X_k(t) is an F_t-martingale with mean zero that converges almost surely and in L2 under the stated bounds.The proof uses Doob’s martingale convergence theorem after establishing uniform second-moment control.
- Growth bounds: With probability at least 1−n^-β, Theorem 24 simultaneously controls the growth of the leading coordinates across all generations and time intervals.The theorem applies to all k∈[r_0] and all 0≤s<t.
- Growth bounds: For k outside the leading eigenspace range, E|⟨φ_k,Z_t⟩|^2 is bounded by C(t+1)^3µ_1^t.These bounds control modes whose eigenvalues do not dominate the principal growth rate.
9 Local structure of random graphs
The section couples logarithmic-depth neighborhoods in the stochastic block model to multi-type Galton–Watson trees and derives high-probability controls for local non-backtracking growth.
- Neighborhood exploration: The exploration process reveals neighborhoods breadth-first while tracking discovered vertices through the filtration generated by the exploration.This construction underlies the coupling to a branching process.
- Local tree-likeness: If ℓ∼κ log_α n with κ<1/2, the graph is ℓ-tangle-free with high probability, and fewer than ᾱ^ℓ log n vertices have cyclic ℓ-neighborhoods.Thus most logarithmic-depth neighborhoods are tree-like.
- Branching-process coupling: The total variation distance between logarithmic-depth graph neighborhoods and the corresponding multi-type Galton–Watson trees is O((log n)^αℓ n^{-γ∧(1−κ)}).The result applies to both directed-edge-rooted and vertex-rooted neighborhoods.
- Uniform local controls: With high probability, only at most (log n)^{2αℓ}n^{1−γ} directed edges fail the event controlling local type-population coordinates.The event bounds projections onto both leading and non-leading eigendirections.
- Non-backtracking growth: For most directed edges, ⟨B^tχ_k,δ_e⟩ grows nearly geometrically at rate µ_k, with error of order α^{t/2}.This provides the local growth estimate used for non-backtracking eigenvector analysis.
- Local laws: The local weak convergence results extend to logarithmic distance parameters and support weak laws of large numbers for local functions.The convergence is to the multi-type Galton–Watson process under uniform root selection.
10 Norm of non-backtracking matrices
The proof adapts the non-backtracking norm analysis from Erdős–Rényi graphs to the stochastic block model by controlling type-dependent path weights and residual matrices.
- Matrix decomposition: The stochastic block model analysis repeats the Erdős–Rényi argument after redefining the weighted non-backtracking matrices on the complete graph.The non-backtracking relation requires e_2=f_1 and e≠f^-1.
- Path counting: Type-dependent path moments are controlled by spanning-tree decompositions, bounding non-tree edges by a/n and summing leaf labels by ᾱ_n/n.This yields the analogue of the key path-counting estimate used in the Erdős–Rényi proof.
- Norm bounds: Because ᾱ_n=α+O(n^-γ), the bounds on ∥∆∥, ∥R^(ℓ)∥, and related quantities continue to hold for the stochastic block model.The remaining proof then follows the earlier argument.
- Matrix decomposition: For the stochastic block model, the residual matrix L has nonzero entries only for a small set of edge configurations, each bounded by a.These configurations include equality, non-backtracking adjacency, inverse transitions, and related two-step relations.
11 Stochastic Block Model : proof of Theorem 5
The proof shows that a suitable leading non-backtracking eigenvector induces a nonconstant class-dependent statistic, which can be converted into an estimator with asymptotically positive overlap.
- Overlap strategy: The strategy reduces community detection to finding a Boolean graph function that is nonconstant over the classes.Such a function is sufficient for an estimator with asymptotically positive overlap.
- Estimator construction: A nonconstant class-dependent function yields a nontrivial partition of the communities whose conditional threshold probabilities differ.The resulting labels are sampled uniformly within the two partition blocks.
- Limiting distributions: The normalized cross-generation statistic converges to a centered random variable Y_k with finite first-moment control, providing class-dependent limiting distributions.For each class i, the corresponding variables Y_{k,i} have mean zero and finite expectation.
- Eigenvector statistic: For a leading eigenvalue µ_k satisfying the theorem’s simplicity assumptions, the associated eigenvector ξ_k is the object used to construct the estimator.The construction analyzes suitably thresholded eigenvector coordinates.
- Estimator construction: The resulting estimator has asymptotically positive overlap, including cases where the eigenvector sign is known, symmetric, or handled by the general construction.The sign ambiguity is addressed by selecting an appropriate partition and permutation of labels.