Structure-Aware Spectral Sparsification via Uniform Edge Sampling

Spectral clustering is a fundamental method for graph partitioning, but its reliance on eigenvector computation limits scalability to massive graphs. Classical sparsification methods preserve spectral properties by sampling edges proportionally to their effective resistances, but require expensive preprocessing to estimate these resistances. We study whether uniform edge sampling--a simple, structure-agnostic strategy--can suffice for spectral clustering. Our main result shows that for graphs admitting a well-separated k-clustering, characterized by a large structure ratio Υ(k) = λk+1/ρG(k), uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling O(γ2nlogn/ε2) edges, where γ is the Laplacian condition number, yields a sparsifier whose top (n k)dimensional eigenspace is approximately orthogonal to the cluster indicators.