# An Efficient Algorithm for Unweighted Spectral Graph Sparsification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2014.

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

- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Sparse Spiking Neural Network: Exploiting Heterogeneity in Timescales for Pruning Recurrent SNN](https://mlsanity.com/paper/2403.03409/) (2024)
- [Graph Matching via convex relaxation to the simplex](https://mlsanity.com/paper/2310.20609/) (2023)

## Abstract (arXiv)

Spectral graph sparsification has emerged as a powerful tool in the analysis of large-scale networks by reducing the overall number of edges, while maintaining a comparable graph Laplacian matrix. In this paper, we present an efficient algorithm for the construction of a new type of spectral sparsifier, the unweighted spectral sparsifier. Given a general undirected and unweighted graph G = (V, E) and an integer ℓ < |E| (the number of edges in E), we compute an unweighted graph H = (V, F) with F subset E and |F| = ℓ such that for every x ∈ ℝV [ displaystyle fracxT LG xkappa ≤ xT LH x ≤ xT LG x, ] where LG and LH are the Laplacian matrices for G and H, respectively, and kappa ≥ 1 is a slowly-varying function of |V|, |E| and ℓ. This work addresses the open question of the existence of unweighted graph sparsifiers for unweighted graphs. Additionally, our algorithm can efficiently compute unweighted graph sparsifiers for weighted graphs, leading to sparsified graphs that retain the weights of the original graphs.