acceptodds
Under review as a conference paper at ICLR 2027

Dynamic Spectral Sparsification: Theory and Practice

Abstract

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 , supports updates in amortized time, and achieves an amortized recourse of only . 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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
Low Diameter Decompositions, Dynamic Algorithms, Spectral Sparsificaion, Graphs

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_6hv5OpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies fully dynamic spectral sparsification of weighted undirected graphs against an oblivious adversary. In this problem, the graph is defined by a sequence of edge insertions and deletions, and the goal is to maintain a (1±ε)(1\pm\varepsilon)-spectral sparsifier at all times. This paper obtains a dynamic algorithm that returns a sparsifier with size O(nε−2log⁡3nlog⁡log⁡n)O(n\varepsilon^{-2}\log^3 n\log\log n), using O(log⁡6nlog⁡log⁡n)O(\log^6 n\log\log n) expected amortized update time and achieving O(1)O(1) expected amortized recourse. This improves the previous results from [Abraham et al., 2016] and [Kyng et al., 2017], which obtained sparsifier size O(nε−2log⁡7n)O(n\varepsilon^{-2}\log^7 n), amortized update time O(ε−2log⁡7n)O(\varepsilon^{-2}\log^7 n), and recourse at least Ω(log⁡n)\Omega(\log n).

The algorithm dynamically maintains the LDD-based resistance estimates of [Baumann–Zöcklein, 2026], makes the sampling probabilities monotone during deletions, and uses geometric bucketing to handle insertions. A second sparsification further reduces the output size. The constant-recourse guarantee comes from the monotonicity of the sampling probabilities. Specifically, under deletions, each edge retains its largest observed resistance estimate and a fixed random threshold, so its sampling probability only increases and it enters the sparsifier at most once. The probabilities increase geometrically, which bounds the expected number of weight changes, giving O(1)O(1) expected amortized recourse through the bucketing method.

Critical strengths

S1. The result improves the previous results simultaneously in sparsifier size, update time, and recourse. Particularly, it improves the log⁡n\log n dependence of the sparsifier size while removing the ε−2\varepsilon^{-2} dependence from the update time. More importantly, it demonstrates that a constant expected amortized recourse is achievable, while previous work obtained at least Ω(log⁡n)\Omega(\log n) recourse, serving as an important conceptual improvement.

S2. The recourse analysis provides a novel technical contribution. The idea of forcing monotone sampling probabilities is nice and intuitive.

S3. The paper conducts a systematic practical implementation, showing that its proposed algorithm outperforms the optimized version of the algorithm in [Abraham et al., 2016] in sparsifier size and update time, under matched approximation accuracies.

Critical weaknesses

W1. The algorithm mainly extends the static LDD-based graph sparsification framework of [Baumann–Zöcklein, 2026] to the dynamic setting, and this extension is largely based on the decremental LDD data structure of [Forster-Goranci, 2019] and the bucketing method of [Abraham et al., 2016]. Although the resulting bounds improve on prior work, the technical novelty appears limited.

W2. The technical overview is not well-written. It describes the construction but does not adequately explain why it improves on previous approaches. In particular, the paper should more clearly establish which construction is followed from previous methods and what obstacles require new ideas beyond combining these ingredients, especially the constant-recourse improvement.

W3. The experiments only evaluate relatively coarse approximation accuracies, e.g., κ∈{3,5,10}\kappa\in\{3,5,10\}. More importantly, the experiments do not measure recourse, despite constant recourse being a central claimed contribution. This point is minor, as the main contribution of this paper is theoretical.

I still lean toward weak acceptance despite these weaknesses because of the conceptual contribution of proving constant recourse, but I believe the paper's quality could be improved substantially.

Questions for authors

Q1. Can you explain the key idea to prove the claimed Ω(log⁡n)\Omega(\log n) recourse lower bound for the prior algorithm? It would be beneficial to include a formal proof to support this claim.

Q2. Related to W3: Can you compare recourse against the Abraham et al. baseline at matched approximation accuracy?

Q3. Related to W3: What is the approximation factor ε\varepsilon of graph sparsification corresponding to the three choices of κ\kappa? Can you compare the algorithms at higher accuracy?

Q4. Is it possible to further improve the polylogarithmic factors in the sparsifier size and the update time, and what is the main technical obstacle?

2 comments

We thank the reviewer for their thoughtful feedback and address the main points below.

Technical Overview

W2: The technical overview is not well-written. It describes the construction but does not adequately explain why it improves on previous approaches.

We will make sure that the final version of the paper includes a detailed discussion comparing our approach with existing methods, highlighting where ours differs. We chose to omit this due to page limits.

Comparison with Abraham et al.

W3: The experiments only evaluate relatively coarse approximation accuracies, e.g., κ∈3,5,10\kappa \in 3,5,10..

Q3: What is the approximation factor ϵ\epsilon of graph sparsification corresponding to the three choices of κ\kappa? Can you compare the algorithms at higher accuracy?

Since κ\kappa does not change when HH is rescaled, a certified κ\kappa tells us that HH is a (1±ϵ)(1 \pm \epsilon)-sparsifier after the best rescaling, with ϵ=(κ−1)/(κ+1)\epsilon = (\kappa - 1)/(\kappa + 1). Our three targets therefore correspond to ϵ=1/2\epsilon = 1/2, 2/32/3 and 9/119/11. We did consider tighter targets, but the size of a sparsifier grows roughly like 1/ϵ21/\epsilon^2, so at the graph sizes we can still certify exactly, both algorithms would end up keeping almost the whole graph. At that point there is little left to compare, which is why we stopped at κ=3\kappa = 3.

Recourse of Abraham et al.

Q1: Can you explain the key idea to prove the claimed Ω(log⁡n)\Omega(\log n) recourse lower bound for the prior algorithm? It would be beneficial to include a formal proof to support this claim.

Abraham et al. do not mention a recourse upper bound. We arrived at an Ω(log⁡n)\Omega(\log n) recourse lower bound from the fact that they use the same bucketing scheme as our algorithm (without the additional layer) to achieve full dynamization. Even if the decremental algorithm has O(1)O(1) recourse, with no further guarantees, this bucketing scheme alone requires amortized recourse Ω(log⁡n)\Omega(\log n). We will include a discussion of this in the final version.

Q2: Can you compare recourse against the Abraham et al. baseline at matched approximation accuracy?

Thank you for the suggestion. Abraham's algorithm performs competitively with ours in terms of recourse in practice. We have measured the recourse of both implementations on the same update streams, at matched quality, across the three synthetic families, two densities and three streams, and we will add this comparison to the appendix. Both algorithms change only a few sparsifier edges per operation (between about 1.3 and 2.7), and ours has lower recourse in 17 of the 18 settings tested, with roughly 25% lower recourse on average.

Potential Improvements

Is it possible to further improve the polylogarithmic factors in the sparsifier size and the update time, and what is the main technical obstacle?

The sparsifier size contains three logarithmic factors: two come from effective resistance sampling and one from the LDD tradeoff between diameter and edge cut probabilities. Improving either contribution would require improving the corresponding black box.

The update time contains six logarithmic factors: three come from maintaining a single LDD, one from maintaining LDDs on O(log⁡n)O(\log n) sampling scales, one from doing this O(log⁡n)O(\log n) times in parallel at each scale to obtain the high-probability guarantee for effective resistance sampling, and one from the fully dynamic bucketing scheme. Similarly, the LDD black box might be improvable. The other factors appear inherent to our approach.

Note that, as mentioned in the appendix, the O(log⁡log⁡n)O(\log \log n) term in the sparsifier size can be improved to an O(log⁡∗n)O(\log^*n) term by adding further layers to the bucketing scheme, but we opted for a simpler presentation.

Thank you for the detailed reply. The explanation regarding the experiments is adequate. Including the results on recourse would increase the credibility. The authors promised to revise the technical overview and add a discussion regarding the Omega(log n) lower bound. I cannot verify these changes before seeing the revised version. I decided to keep my scores.

Reviewer_GvMoOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the fully dynamic spectral sparsification on graphs with both edge insertions and deletions while optimizing the amortized update time and number of changes made to the data structure (also called recourse). The paper builds on top of the static spectral sparsification based on low diameter decomposition (LDD) in a recent SPAA’26 paper by Baumann and Zöcklein. The static algorithm computes a robust connectivity estimate by sampling graph edges with different scales of probabilities to construct different sampled graphs, and then building LDD on the sampled graphs. The decremental method essentially needs to estimate the critical scale of each edge. When a node changes clusters (in any of the LDDs), its incidence edges are examined to update the critical scale to be the smallest value seen so far. Since each node can only change clusters constant times guaranteed by the algorithm of Baumann and Zöcklein and each examination takes constant time, the update time is linear in m. The authors set the critical scale to be the minimal scale seen for the recourse bound. The incremental method uses the bucketing scheme in (Abraham et al., 2016) to be transformed to fully dynamic. The experiments compare the proposed method with (Abraham et al., 2016), showing a speed up in most settings.

Critical strengths

Strengths:

  1. The authors present a fully dynamic algorithm for spectral sparsification with update time O(log⁡6nlog⁡log⁡n)O(\log^6 n \log\log n) and a constant amortized recourse. Notably, the update time is free of ϵ\epsilon, the approximation parameter, improving over the update time of O(log⁡7nϵ−2)O(\log^7 n\epsilon^{-2}) in (Abraham et al. 2016). I did not check the proof carefully but the proofing technique should work.

  2. Major contributions include combining three prior relate techniques to come up with an algorithm for spectral sparsification, and to analyze the recourse explicitly under both incremental and decremental cases and to add the monotonically increasing requirement on the critical scale in the decremental method.

  3. The authors provide experimental studies to compare the empirical performance with (Abraham et al. 2016) with source code open.

  4. The exposition of the paper is good and I enjoy reading it. The paper has its key ideas articulated in the main paper.

Critical weaknesses

Weakness:

The authors essentially provide a fully dymanic implementation of the static spectral sparsification algorithm of Baumann & Zöcklein (2026). Since the static algorithm makes use of LDD, the main techniques become how to maintain the node clustering and robust connectivity estimate in the fully dynamic setup. They directly use the decremental low-diameter decomposition algorithm of Forster & Goranci (2019). They develop the monotonically increasing property for the recourse bound. The incremental method uses the bucketing scheme of Abraham et al. (2016) to transform the decremental method into a fully dynamic one, which is a standard approach. While the improvement on update time and recourse is made, the main techniques largely follow from earlier work in this field.

Questions for authors

Comments:

  • There is a work on fully dynamic effective resistance. What are the result comparisons with the paper?

David Durfee, Yu Gao, Gramoz Goranci, Richard Peng. Fully Dynamic Effective Resistances. https://arxiv.org/abs/1804.04038

  • It would be helpful to clearly mark what intermediate graphs are unweighted and what are weighted.

  • It would be great to provide more details on the recourse analysis of Abraham et al. (2016). Why is it logarithmic?

  • Line 302: why does “the probability that an edge is ever added to the sparsifier is also monotonically increasing over time” result in that “an edge may ever enter and leave the output sparsifier at most once”?

  • The paper title is rather broad and not connected to LDD.

2 comments

We thank the reviewer for their thoughtful feedback and address the questions below.

Effective Resistance

There is a work on fully dynamic effective resistance. What are the result comparisons with the paper?

The dynamic maintenance of effective resistances is a harder problem than dynamic spectral sparsification. Existing (1+ϵ)(1+\epsilon)-approximate algorithms have update time Ω(poly(n))\Omega(poly(n)), whereas our algorithm works in the near-optimal O~(1)\tilde{O}(1) update time regime. This makes a comparison difficult.

Intermediate Graph Weights

It would be helpful to clearly mark what intermediate graphs are unweighted and what are weighted.

We will clarify this distinction in the final version of the paper. Note that both the decremental sparsifiers and the resulting fully dynamic sparsifiers are weighted. Only the sub-sampled graphs are unweighted.

Recourse of Abraham et al.

It would be great to provide more details on the recourse analysis of Abraham et al. (2016). Why is it logarithmic?

Abraham et al. do not mention a recourse upper bound. We arrived at an Ω(log⁡n)\Omega(\log n) recourse lower bound from the fact that they use the same bucketing scheme as our algorithm (without the additional layer) to achieve full dynamization. Even if the decremental algorithm has O(1)O(1) recourse, with no further guarantees, this bucketing scheme alone requires amortized recourse Ω(log⁡n)\Omega(\log n). We will include a discussion of this in the final version.

Exploiting Monotonicity

Line 302: why does “the probability that an edge is ever added to the sparsifier is also monotonically increasing over time” result in that “an edge may ever enter and leave the output sparsifier at most once”?

At initialization, for each edge, the decremental algorithm samples a random value xx in [0,1][0,1]. If its sampling probability bound (pep_e) ever exceeds this value, the edge is included in the sparsifier. Since the sampling probability bound increases monotonically, the edge may enter the sparsifier at most once and may be deleted from it once, when it is deleted from the input graph. Note that this is just a high-level intuitive explanation before the relevant lemma: the weight with which the edge is represented in the sparsifier might also undergo updates. Such an update is counted as a separate recourse event. We will make this explanation clearer in the final version.

Thank you for your reply and clarification. My overall evaluation on the manuscript's strengths and weakness remains the same, after reading the response.

Reviewer_QJtGOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes an algorithm to maintain high-quality sparsifiers while the original graph keeps changing. The new method guarantees that it maintains a (1±ε)(1\pm\varepsilon)-approximate spectral sparsifier with high probability and needs only O(log⁡6nlog⁡log⁡n)O(\log^6 n\log\log n) expected amortized update time for edge insertions and deletions. The output sparsified graph has O(nlog⁡3nlog⁡log⁡n/ε2)O(n\log^3 n\log\log n/\varepsilon^2) edges and undergoes expected amortized O(1)O(1) updates per update to the input graph. Compared with the earlier results of Abraham et al. (2016) and Kyng et al. (2017), which give sparsifier size O(nlog⁡7n/ε2)O(n\log^7 n/\varepsilon^2), amortized update time O(log⁡7n/ε2)O(\log^7 n/\varepsilon^2), and recourse at least Ω(log⁡n)\Omega(\log n) (according to this paper), the new method improves on all measures.

Critical strengths

The method proposed in this paper works for weighted dynamic graphs and handles both edge insertions and deletions.

The algorithm achieves better time complexity, sparsifier size, and recourse.

The paper proves these results theoretically and evaluates the practical performance.

The expected amortized update time and expected amortized recourse per update do not depend on the precision parameter ε\varepsilon.

Critical weaknesses

In the main text, the new method is only compared with Abraham et al. (2016) for time complexity, sparsifier size, and recourse. But there should be more methods worth considering and comparing with, especially some recent methods. And some comparisons with Abraham et al. (2016) seem unfair. The update-time guarantee in Abraham et al. (2016) is included in its high-probability guarantee, so it seems unfair to compare this with the expected amortized update time of the new method. And the paper states that the recourse of Abraham et al. (2016) is at least Ω(log⁡n)\Omega(\log n) without any analysis, and the original paper does not give this result.

Theorems are stated as holding “with high probability” instead of explicitly giving a probability.

The datasets used in the experiments do not seem very dense. Spectral sparsification is mainly used for large and dense graphs, but the datasets used in the paper do not seem to have a high average number of edges per vertex. And the paper does not state how many trials were run for each setting. Based on the results in Figure 1, the new method has better compression ratios, but its performance (certified κ\kappa) often seems worse than the baseline.

The main theorem is based on two layers of sparsification, but the appendix mentions that the second layer was not used in the experiments. This is confusing.

Some writing needs to be improved. For example, “[FOCS ’16]” in the abstract seems to be a citation.

Questions for authors

See weaknesses.

3 comments

We thank the reviewer for their thoughtful feedback and address the main points below.

Lack of Comparisons

In the main text, the new method is only compared with Abraham et al. (2016) for time complexity, sparsifier size, and recourse. But there should be more methods worth considering and comparing with, especially some recent methods.

We are unaware of other comparable algorithms with theoretical guarantees for constant-approximation fully dynamic undirected spectral sparsification, the focus of this paper. Bernstein et al. (ICALP22) and Meierhans et al. (SODA26) have shown algorithms with O(poly(log⁡n))O(poly(\log n)) approximation. However, their algorithms work against adaptive adversaries (whereas ours is limited to oblivious adversaries), so a comparison would have been unfair to their work. Ghaffari-Koo (SPAA25) have presented a batch-dynamic (therefore somewhat slower) implementation of Abraham et al., making a comparison difficult.

We will make sure that the final version of the paper contains a detailed discussion of these comparisons. For the sake of completeness, we have included comparisons against dyGRASS, a dynamic heuristic-based algorithm, and against the static GRASS, both in Appendix G.6 of the submission.

Comparison to Abraham et al.

And some comparisons with Abraham et al. (2016) seem unfair.

Abraham et al.’s algorithm does have a high-probability upper bound on its update time, whereas our algorithm is faster by a factor of O(log⁡n/log⁡log⁡n/ϵ2)O(\log n/ \log \log n /\epsilon^2). Our algorithm can also be implemented with a high-probability update time bound at the cost of an O(log⁡n)O(\log n) factor in terms of update time using standard techniques. We will include a discussion on this in the final version of the paper. Note that Abraham’s algorithm does not allow for an implementation with an expected update time guarantee that shaves off an O(log⁡n)O(\log n) factor in a black-box way.

Recourse of Abraham et al.

And the paper states that the recourse of Abraham et al. (2016) is at least Ω(log⁡n))\Omega(\log n)) without any analysis, and the original paper does not give this result.

Abraham et al. do not mention a recourse upper bound. We arrived at an Ω(log⁡n)\Omega(\log n) recourse lower bound from the fact that they use the same bucketing scheme as our algorithm (without the additional layer) to achieve full dynamization. Even if the decremental algorithm has O(1)O(1) recourse, with no further guarantees, this bucketing scheme alone requires amortized recourse Ω(log⁡n)\Omega(\log n). We will include a discussion of this in the final version.

High Probability

Theorems are stated as holding “with high probability” instead of explicitly giving a probability.

We use the standard notion of an algorithmic high-probability guarantee: a high-probability event occurs with probability 1−1/nc1-1/n^c for any choice of constant cc. Note that Abraham et al. use the same convention.

Density of Test Datasets

The datasets used in the experiments do not seem very dense.

Our synthetic graphs already go up to 250 edges per vertex, while real networks are a different matter: public datasets (often used for testing similar algorithms) average only 3 to 5 edges per vertex, which is why we evaluated on their dense kk-cores, with 41 to 90 edges per vertex. We kept the densities in a range where certifying every state remained affordable. This is also the regime studied for the static version of this framework by Baumann & Zöcklein (2026), whose largest instances have about 29 edges per vertex and are sparsified to a quarter of their edges for use as preconditioners. Moreover, since the size of the sparsifier is governed by nn rather than by mm, the fraction of edges kept only shrinks as the graph gets denser, so denser graphs would make the results of sparsification stronger but would make comparisons between existing algorithms harder.

Number of Trials

And the paper does not state how many trials were run for each setting.

Thank you for pointing this out. We will add, for every figure, the number of graph seeds and operation orders it is based on.

Number of Sparsification Layers

The main theorem is based on two layers of sparsification, but the appendix mentions that the second layer was not used in the experiments. This is confusing.

Our experiments follow the single-layer algorithm of Lemma 5.1, and we left out the second layer because, in our proof, each layer runs at accuracy ϵ/3\epsilon/3, which makes them about nine times larger, while at n=16,000n = 16{,}000, the second layer of sparsification saves only a factor of about 4. It would therefore only pay off on graphs far larger than the ones we can certify. This choice is already stated in Appendix D, but we agree it is easy to miss, so we will make it clearer, both in Section 6 and in the wording of Appendix D itself.

Thanks for the response. It addresses some of my concerns. For the remaining points, the authors have said what they plan to change, but I haven’t seen those changes in the manuscript, so I can’t check

We thank the reviewer for their response.

We have updated the submission to address the reviewer's suggestions. In particular:

  • We have added an explanation of our claimed Ω(log⁡n)\Omega(\log n) recourse lower bound for the algorithm of Abraham et al. to the introduction. We have also added experiments in Appendix G.5 comparing its recourse with that of our algorithm on our test datasets.

  • We have formally defined the notion of high probability in the preliminaries.

  • We have added a related work paragraph to the introduction discussing other dynamic spectral sparsification algorithms and the challenges of comparing them experimentally with our work.

  • The figures presenting our experimental results now include the number of trials in their descriptions.

  • We have explained how our expected amortized update-time guarantee can be strengthened to hold with high probability, at the cost of an additional O(log⁡n)O(\log n) factor.

  • We have emphasized in Section 6.3 that our experiments implement our algorithm with a single sparsification layer and have included references to the explanations for this choice.

We would be grateful for any further suggestions the reviewer may have and would be happy to address any remaining questions or concerns.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.