Adjacency Spectral Radius Under Laplacian Sparsification: Deterministic and Probabilistic Bounds
For researchers using spectral sparsification in network epidemiology or spectral clustering, this provides the first rigorous control of the adjacency spectral radius, a key quantity not covered by standard Laplacian guarantees.
The paper proves deterministic and probabilistic bounds on the distortion of the adjacency spectral radius under Laplacian sparsification, showing that for graphs with delocalized eigenvectors the distortion can be as small as O(εΔ√(log n)/√n).
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.