# Structure-Aware Spectral Sparsification via Uniform Edge Sampling

arXiv: https://arxiv.org/abs/2510.12669 · HTML: https://mlsanity.com/paper/2510.12669/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 14 Oct 2025.

## Builds on (most cited first, 9 of 9)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [Coresets for Clustering in Euclidean Spaces: Importance Sampling is Nearly Optimal](https://mlsanity.com/paper/2004.06263/) (2020)
- [The Power of Uniform Sampling for Coresets](https://mlsanity.com/paper/2209.01901/) (2022)
- [A Tighter Analysis of Spectral Clustering, and Beyond](https://mlsanity.com/paper/2208.01724/) (2022)
- [Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap](https://mlsanity.com/paper/1301.5584/) (2013)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Local Algorithms for Estimating Effective Resistance](https://mlsanity.com/paper/2106.03476/) (2021)
- [The Power of Uniform Sampling for k-Median](https://mlsanity.com/paper/2302.11339/) (2023)

## Built on by (most cited first, 1 of 1)

- [Approximating Gaussian Whittle-Matern Fields over Well-Centered Triangulations of Riemannian Manifolds](https://mlsanity.com/paper/2606.13827/) (2026)

## Abstract (arXiv)

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 Upsilon(k) = λk+1 / ρG(k), uniform sampling preserves the spectral subspace used for clustering. Specifically, we prove that uniformly sampling O(γ2 n log n / ε2) edges, where γ is the Laplacian condition number, yields a sparsifier whose top (n-k)-dimensional eigenspace is approximately orthogonal to the cluster indicators. This ensures that the spectral embedding remains faithful, and clustering quality is preserved. Our analysis introduces new resistance bounds for intra-cluster edges, a rank-(n-k) effective resistance formulation, and a matrix Chernoff bound adapted to the dominant eigenspace. These tools allow us to bypass importance sampling entirely. Conceptually, our result connects recent coreset-based clustering theory to spectral sparsification, showing that under strong clusterability, even uniform sampling is structure-aware. This provides the first provable guarantee that uniform edge sampling suffices for structure-preserving spectral clustering.