# inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 17 references that are in the map.
- First posted on arXiv 26 Feb 2024.

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

- [An SDP-Based Algorithm for Linear-Sized Spectral Sparsification](https://mlsanity.com/paper/1702.08415/) (2017)
- [Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions](https://mlsanity.com/paper/1805.12051/) (2018)
- [GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis](https://mlsanity.com/paper/1911.04382/) (2019)
- [HyperEF: Spectral Hypergraph Coarsening by Effective-Resistance Clustering](https://mlsanity.com/paper/2210.14813/) (2022)
- [SF-GRASS: Solver-Free Graph Spectral Sparsification](https://mlsanity.com/paper/2008.07633/) (2020)
- [Similarity-Aware Spectral Sparsification by Edge Filtering](https://mlsanity.com/paper/1711.05135/) (2017)
- [Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model](https://mlsanity.com/paper/2007.14204/) (2020)
- [Pursuing More Effective Graph Spectral Sparsifiers via Approximate Trace Reduction](https://mlsanity.com/paper/2206.06223/) (2022)

## Abstract (arXiv)

This work presents inGRASS, a novel algorithm designed for incremental spectral sparsification of large undirected graphs. The proposed inGRASS algorithm is highly scalable and parallel-friendly, having a nearly-linear time complexity for the setup phase and the ability to update the spectral sparsifier in O(log N) time for each incremental change made to the original graph with N nodes. A key component in the setup phase of inGRASS is a multilevel resistance embedding framework introduced for efficiently identifying spectrally-critical edges and effectively detecting redundant ones, which is achieved by decomposing the initial sparsifier into many node clusters with bounded effective-resistance diameters leveraging a low-resistance-diameter decomposition (LRD) scheme. The update phase of inGRASS exploits low-dimensional node embedding vectors for efficiently estimating the importance and uniqueness of each newly added edge. As demonstrated through extensive experiments, inGRASS achieves up to over 200 × speedups while retaining comparable solution quality in incremental spectral sparsification of graphs obtained from various datasets, such as circuit simulations, finite element analysis, and social networks.