# Fully Dynamic Spectral Vertex Sparsifiers and Applications

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2019.

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

- [SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networks](https://mlsanity.com/paper/2207.07888/) (2022)
- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)
- [A Fast Algorithm for Moderating Critical Nodes via Edge Removal](https://mlsanity.com/paper/2309.06392/) (2023)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)

## Abstract (arXiv)

We study dynamic algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals T of our choice. Such objects preserve pairwise resistances, solutions to systems of linear equations, and energy of electrical flows between the terminals in T. We give a data structure that supports insertions and deletions of edges, and terminal additions, all in sublinear time. Our result is then applied to the following problems. (1) A data structure for maintaining solutions to Laplacian systems L x = b, where L is the Laplacian matrix and b is a demand vector. For a bounded degree, unweighted graph, we support modifications to both L and b while providing access to ε-approximations to the energy of routing an electrical flow with demand b, as well as query access to entries of a vector tildex such that leftlVert tildex-Ldagger b rightrVertL ≤ ε leftlVert Ldagger b rightrVertL in tildeO(n11/12ε-5) expected amortized update and query time. (2) A data structure for maintaining All-Pairs Effective Resistance. For an intermixed sequence of edge insertions, deletions, and resistance queries, our data structure returns (1 ± ε)-approximation to all the resistance queries against an oblivious adversary with high probability. Its expected amortized update and query times are tildeO(min(m3/4,n5/6 ε-2) ε-4) on an unweighted graph, and tildeO(n5/6ε-6) on weighted graphs. These results represent the first data structures for maintaining key primitives from the Laplacian paradigm for graph algorithms in sublinear time without assumptions on the underlying graph topologies.