- 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 -spectral sparsifier at all times. This paper obtains a dynamic algorithm that returns a sparsifier with size , using expected amortized update time and achieving expected amortized recourse. This improves the previous results from [Abraham et al., 2016] and [Kyng et al., 2017], which obtained sparsifier size , amortized update time , and recourse at least .
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 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 dependence of the sparsifier size while removing the dependence from the update time. More importantly, it demonstrates that a constant expected amortized recourse is achievable, while previous work obtained at least 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., . 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 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 of graph sparsification corresponding to the three choices of ? 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
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.
We thank the reviewer for their thoughtful feedback and address the main points below.
Technical Overview
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.
Since κ does not change when H is rescaled, a certified κ tells us that H is a (1±ϵ)-sparsifier after the best rescaling, with ϵ=(κ−1)/(κ+1). Our three targets therefore correspond to ϵ=1/2, 2/3 and 9/11. We did consider tighter targets, but the size of a sparsifier grows roughly like 1/ϵ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.
Recourse of Abraham et al.
Abraham et al. do not mention a recourse upper bound. We arrived at an Ω(logn) 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) recourse, with no further guarantees, this bucketing scheme alone requires amortized recourse Ω(logn). We will include a discussion of this in the final version.
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
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(logn) sampling scales, one from doing this O(logn) 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(loglogn) term in the sparsifier size can be improved to an O(log∗n) term by adding further layers to the bucketing scheme, but we opted for a simpler presentation.