- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies hierarchical clustering under vertex insertions and deletions. DynamicHC retains historical splits using membership counters and a deletion-adjusted cut certificate, rebuilding the highest invalid subtree. LCA-based edge ownership allows reconstruction from induced edges without scanning boundary edges. Given a -approximate balanced-cut oracle and for fixed , the method maintains an approximation to the unrestricted Dasgupta optimum. The analysis includes update-time and recourse bounds, while experiments compare dynamic repair with full reconstruction on five datasets.
Critical strengths
(1) The deletion-adjusted certificate provides a concrete way to preserve valid historical splits under both insertions and deletions, with a guarantee for the global Dasgupta objective.
(2) LCA-based edge ownership addresses an important implementation issue: rebuilding a subtree requires only its induced edges, while boundary edges remain untouched.
(3) The analysis separates approximation correctness from conditional amortized efficiency and includes recourse bounds and examples demonstrating repeated large-subtree reconstruction.
Critical weaknesses
(1) The scope of the fast amortized bound remains limited. Theorem 3.7 requires the execution-dependent regularity condition in Remark 3.6, bounded incident update weight, and an efficient cut oracle. The paper acknowledges these assumptions, but does not establish representative settings where they hold together. Without them, its repair strategy can repeatedly rebuild the entire hierarchy.
(2) The experimental cut routine is not fully connected to the theoretical oracle. Appendix F.1 describes exact enumeration and spectral sweeps, but does not specify the rho and Gamma used in the validity tests or how spectral certificates enter the stored lower bounds.
(3) All experiments use an active window of only 64 vertices and compare against full reconstruction. Processing 10,000 updates does not establish scalability with the number of active vertices. Larger-window behavior and the distribution of rebuilt-subtree sizes remain unknown, limiting the practical conclusions.
Questions for authors
(1) What values of rho and Gamma are used in the experiments, and how are zero or very small spectral certificates handled?
(2) Can the authors identify a representative graph and update model satisfying Remark 3.6 with controlled parameters?
(3) How often do the evaluated streams trigger root reconstruction, and what fraction of active vertices is typically included in a rebuilt subtree?
Response to Reviewer CbWy
Thank you for your comments. We have revised the manuscript to clarify the theoretical assumptions, strengthen the experimental validation, and explicitly report the limitations of our approach.
Weakness 1: Limited scope of the amortized bound. We clarify in Section 3.4 that Theorem 3.7 requires an efficient cut oracle, bounded update-star weight, and the execution-dependent regularity condition in Remark 3.6. These assumptions are not required for the approximation guarantee or the event-based bound in Theorem 3.5. We also emphasize that Proposition E.7 proves repeated root reconstruction is possible even on sparse graphs with constant-size update stars. To demonstrate that the assumptions of Theorem 3.7 can hold simultaneously, we added a concrete bounded-clique-block model in Appendix D.4. This establishes compatibility of the assumptions, but not their validity for general graphs.
Weakness 2: Experimental oracle and theoretical guarantees.
We replaced the uncertified spectral protocol with a certificate-checked implementation (Appendix G.1). The revised experiments use ρ=25 and Γ=50. Cuts are obtained through exact enumeration, zero-cut detection, spectral candidates, and MILP fallback. A positive cut is accepted only when its weight satisfies the required bound against a valid positive lower certificate. Otherwise, the implementation attempts MILP certification or fails closed. The stored historical bound is λx=cx0/25, not the spectral certificate. We explicitly acknowledge numerical tolerances and do not claim a fully machine-verified oracle or a general efficient oracle guarantee.
We added certificate-checked scaling experiments at h∈{64,128,256} (Appendix I), with 5/5, 4/5, and 1/5 completed runs, respectively. We explicitly report incomplete runs and certification failures. We also added reconstruction-size statistics and root-rebuild frequencies (Table 1 and Appendix I). The 95th-percentile rebuilt fraction reaches 1.0, demonstrating that large reconstructions remain frequent enough to limit scalability. These results are presented as implementation limitations rather than evidence of general sublinear updates.
The revised experiments use ρ=25 and Γ=50. For spectral certification, we compute the lower-bound candidate ℓspec=21λ2⌈s/4⌉dmin. Zero-weight cuts are accepted as optimal. If the spectral certificate is zero or numerically negligible, a positive cut cannot pass the spectral test. The implementation then attempts MILP certification and fails closed if certification remains unavailable. Accepted cuts store λx=cx0/25, independently of the spectral lower bound. These procedures are specified in Appendix G.1.
We added Appendix D.4, considering a graph formed by disjoint unit-weight clique blocks of bounded size r. Each update inserts or deletes one vertex, with insertions anchored at an active same-block neighbor when available. This model satisfies hereditary sparsity with κ=(r−1)/2 and bounded update-star weight W⋆=r−1. It admits an efficient exact balanced-cut oracle with ρ=1. Ratio-triggered nodes have positive balanced-cut values and base sizes below 4r, yielding μ=1/(4r). Thus, all assumptions of Theorem 3.7 hold with controlled parameters for fixed r. This is a restricted existence example, not a claim about general similarity graphs.
We added these statistics in Table 1 and Appendix I. In the certified h=64 experiments, root reconstruction occurs in 24.22%--30.47% of the 128 updates across the five datasets. The mean rebuilt fraction ranges from 0.449 to 0.502, the median from 0.250 to 0.254, and the 95th percentile is 1.0. Non-rebuild updates contribute zero to these statistics. We also report corresponding reconstruction-size statistics for h=128 and h=256 in Appendix I.
These measurements confirm that root rebuilding remains a significant practical limitation of our current approach.