# Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2018.

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

- [Adversarial Laws of Large Numbers and Optimal Regret in Online Classification](https://mlsanity.com/paper/2101.09054/) (2021)
- [SAGMAN: Stability Analysis of Graph Neural Networks on the Manifolds](https://mlsanity.com/paper/2402.08653/) (2024)
- [SALMAN: Stability Analysis of Language Models Through the Maps Between Graph-based Manifolds](https://mlsanity.com/paper/2508.18306/) (2025)
- [LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs](https://mlsanity.com/paper/2111.05694/) (2021)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition](https://mlsanity.com/paper/2402.16990/) (2024)
- [A Spectral Framework for Evaluating Geodesic Distances Between Graphs](https://mlsanity.com/paper/2406.10500/) (2024)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collection of short cycles, plus few extra edges. A simple observation gives that every graph G on n vertices with m edges can be decomposed in O(mn) time into cycles of length at most 2log n, and at most 2n extra edges. We give an m1+o(1) time algorithm for constructing a short cycle decomposition, with cycles of length no(1), and n1+o(1) extra edges. These decompositions enable us to make progress on several open questions: * We give an algorithm to find (1±ε)-approximations to effective resistances of all edges in time m1+o(1)ε-1.5, improving over the previous best of tildeO(minmε-2,n2 ε-1). This gives an algorithm to approximate the determinant of a Laplacian up to (1±ε) in m1 + o(1) + n15/8+o(1)ε-7/4 time. * We show existence and efficient algorithms for constructing graphical spectral sketches -- a distribution over sparse graphs H such that for a fixed vector x, we have w.h.p. x'LHx=(1±ε)x'LGx and x'LH^+x=(1±ε)x'LG^+x. This implies the existence of resistance-sparsifiers with about nε-1 edges that preserve the effective resistances between every pair of vertices up to (1±ε). * By combining short cycle decompositions with known tools in graph sparsification, we show the existence of nearly-linear sized degree-preserving spectral sparsifiers, as well as significantly sparser approximations of directed graphs. The latter is critical to recent breakthroughs on faster algorithms for solving linear systems in directed Laplacians. Improved algorithms for constructing short cycle decompositions will lead to improvements for each of the above results.