Dynamic Spectral Sparsification: Theory and Practice

We study the problem of compressing an undirected, weighted graph by replacing it with a sparser representative, called a spectral sparsifier, while preserving its Laplacian spectrum to a specified precision. Spectral sparsifiers are a fundamental primitive in numerical linear algebra, with applications ranging from fast solvers for Laplacian systems to computing commute times and semi-supervised learning on graph data. In this paper, we focus on the dynamic setting, where the graph undergoes edge updates such as insertions or deletions, and the goal is to maintain a spectral sparsifier as efficiently as possible. We introduce a simple algorithmic framework for dynamic spectral sparsification based on maintaining a hierarchy of clusterings of graphs into low-diameter clusters, known as low-diameter decompositions. Our algorithm maintains a sparsifier of nearly optimal size $O(n{\log }^{3}n\log \log n/{ϵ}^2)$, supports updates in $O({\log }^{6}n\log \log n)$ amortized time, and achieves an amortized recourse of only $O(1)$. In each of these three performance measures, our theoretical guarantees improve those of Abraham, Durfee, Koutis, Krinninger, and Peng [FOCS '16]. On the practical side, we evaluate our framework on both real-world and synthetic datasets, where our algorithm shows competitive performance against natural baselines.