# An SDP-Based Algorithm for Linear-Sized Spectral Sparsification

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2017.

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

- [Graph Neural Networks Inspired by Classical Iterative Algorithms](https://mlsanity.com/paper/2103.06064/) (2021)
- [Graph Coarsening with Neural Networks](https://mlsanity.com/paper/2102.01350/) (2021)
- [A Generic Graph Sparsification Framework using Deep Reinforcement Learning](https://mlsanity.com/paper/2112.01565/) (2021)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [Fast Approximation of Similarity Graphs with Kernel Density Estimation](https://mlsanity.com/paper/2310.13870/) (2023)
- [inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition](https://mlsanity.com/paper/2402.16990/) (2024)
- [SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning](https://mlsanity.com/paper/2410.10875/) (2024)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)

## Abstract (arXiv)

For any undirected and weighted graph G=(V,E,w) with n vertices and m edges, we call a sparse subgraph H of G, with proper reweighting of the edges, a (1+varepsilon)-spectral sparsifier if [ (1-varepsilon)xintercalLGx≤ xintercal LH x≤ (1+varepsilon) xintercal LGx ] holds for any x∈ℝn, where LG and LH are the respective Laplacian matrices of G and H. Noticing that Omega(m) time is needed for any algorithm to construct a spectral sparsifier and a spectral sparsifier of G requires Omega(n) edges, a natural question is to investigate, for any constant varepsilon, if a (1+varepsilon)-spectral sparsifier of G with O(n) edges can be constructed in tildeO(m) time, where the tildeO notation suppresses polylogarithmic factors. All previous constructions on spectral sparsification require either super-linear number of edges or m1+Omega(1) time. In this work we answer this question affirmatively by presenting an algorithm that, for any undirected graph G and varepsilon>0, outputs a (1+varepsilon)-spectral sparsifier of G with O(n/varepsilon2) edges in tildeO(m/varepsilonO(1)) time. Our algorithm is based on three novel techniques: (1) a new potential function which is much easier to compute yet has similar guarantees as the potential functions used in previous references; (2) an efficient reduction from a two-sided spectral sparsifier to a one-sided spectral sparsifier; (3) constructing a one-sided spectral sparsifier by a semi-definite program.