# Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2015.

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

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [Graph Coarsening with Message-Passing Guarantees](https://mlsanity.com/paper/2405.18127/) (2024)
- [A Generic Graph Sparsification Framework using Deep Reinforcement Learning](https://mlsanity.com/paper/2112.01565/) (2021)
- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification: Technical Report](https://mlsanity.com/paper/2501.04570/) (2025)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [Robust Offline Active Learning on Graphs](https://mlsanity.com/paper/2408.07941/) (2024)
- [Taxonomy of reduction matrices for Graph Coarsening](https://mlsanity.com/paper/2506.11743/) (2025)
- [Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation](https://mlsanity.com/paper/2212.00642/) (2022)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Semi-supervised Active Regression](https://mlsanity.com/paper/2106.06676/) (2021)
- [PRIMO: Private Regression in Multiple Outcomes](https://mlsanity.com/paper/2303.04195/) (2023)
- [Almost linear time differentially private release of synthetic graphs](https://mlsanity.com/paper/2406.02156/) (2024)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)

## Abstract (arXiv)

We present the first almost-linear time algorithm for constructing linear-sized spectral sparsification for graphs. This improves all previous constructions of linear-sized spectral sparsification, which requires Omega(n2) time. A key ingredient in our algorithm is a novel combination of two techniques used in literature for constructing spectral sparsification: Random sampling by effective resistance, and adaptive constructions based on barrier functions.