Adjacency Spectral Radius Under Laplacian Sparsification: Deterministic and Probabilistic Bounds
2026-06-05 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how well a method called spectral sparsification preserves the largest eigenvalue of a graph's adjacency matrix, which is important for understanding things like epidemic spreading and clustering. They provide precise mathematical bounds showing how much this eigenvalue can change after sparsification, improving on previous results. They also explore conditions under which these bounds get better, especially for certain types of graphs like random graphs and expanders. Finally, they show their results are nearly the best possible for regular graphs.
spectral sparsificationadjacency spectral radiusPerron-Frobenius theoryMatrix Bernstein inequalityeigenvector delocalizationspectral gapErdos-Renyi graphsexpandersstochastic block modelsgraph Laplacian
Authors
Joshua Steier
Abstract
Spielman-Srivastava spectral sparsification preserves Laplacian quadratic forms to within (1 +/- epsilon), but does not directly control the adjacency spectral radius lambda_1, which governs the NIMFA epidemic threshold and arises in spectral clustering. We prove |lambda_1(A_H) - lambda_1(A_G)| <= epsilon(2 Delta - lambda_1) deterministically, with a sharp epsilon*lambda_1 bound for reweighting sparsifiers via Perron-Frobenius monotonicity. Under effective-resistance sampling, Matrix Bernstein gives O(epsilon Delta / sqrt(c)) with high probability. Combining eigenvector delocalization with resolvent perturbation theory, we establish that for graphs with delocalized Perron eigenvectors and spectral gap = Omega(Delta), the distortion is O(epsilon Delta sqrt(log n) / sqrt(n)) + O(epsilon^2 Delta^2 / delta_gap), with corollaries for Erdos-Renyi graphs, regular expanders, and stochastic block models. Lower bounds establish tightness for regular graphs.