acceptodds
Under review as a conference paper at ICLR 2027

Fully Dynamic Hierarchical Clustering

Abstract

Hierarchical clustering provides a multiscale representation of similarity data and is a fundamental tool in machine learning. While static hierarchical clustering has been extensively studied, maintaining a high-quality hierarchy under continuous changes in the underlying similarity graph remains challenging. In the fully dynamic setting, repeated reconstruction is often too expensive when vertices and their incident edges are inserted or removed. Existing dynamic approaches mainly focus on incremental maintenance, linkage-based merge rules, or graph summaries. These techniques do not directly maintain an explicit hierarchy whose global Dasgupta cost remains competitive after arbitrary vertex insertions and deletions. We propose a fully dynamic algorithm for explicit hierarchical clustering with approximation guarantees for Dasgupta cost. Our method is based on a local invariant that combines a deletion-adjusted cut lower bound with a counter that tracks changes in cluster membership. This enables the algorithm to preserve valid parts of the hierarchy and repair only affected subtrees. By organizing edges according to their lowest common ancestors, reconstruction can be restricted to the relevant induced subproblems. Given a finite- oracle for -balanced cut and any fixed , our algorithm maintains a -balanced hierarchy with a -approximation guarantee. The running time is bounded by the direct update work and the cost of rebuilding affected subtrees. A separate, explicitly stated regularity condition yields a compact amortized bound. The approximation and event-based time bounds do not use it. Queries for the exact cost take time, while reporting the complete hierarchy takes time, where is the current number of active vertices. For a rebuild involving vertices, the stable set recourse is and the stable mass recourse is .

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Approximation clustering, Hierarchical clustering, Fully dynamic

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_CbWyOpenReview ↗
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 ρ\rho-approximate balanced-cut oracle and Γ=(1+ε)ρ\Gamma = (1+\varepsilon)\rho for fixed ε>0\varepsilon > 0, the method maintains an O(ρ)O(\rho) 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?

1 comment

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.

  1. 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.

  2. 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\rho=25 and Γ=50\Gamma=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\lambda_x=c_x^0/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.

  1. Weakness 3: Experimental scalability and reconstruction sizes.

We added certificate-checked scaling experiments at h∈{64,128,256}h\in\{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.

  1. Question 1: Values of ρ\rho, Γ\Gamma, and handling of small certificates.

The revised experiments use ρ=25\rho=25 and Γ=50\Gamma=50. For spectral certification, we compute the lower-bound candidate ℓspec=12λ2⌈s/4⌉dmin⁡\ell_{\mathrm{spec}}=\frac{1}{2}\lambda_2\lceil s/4\rceil d_{\min}. 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\lambda_x=c_x^0/25, independently of the spectral lower bound. These procedures are specified in Appendix G.1.

  1. Question 2: A graph and update model satisfying Remark 3.6.

We added Appendix D.4, considering a graph formed by disjoint unit-weight clique blocks of bounded size rr. 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\kappa=(r-1)/2 and bounded update-star weight W⋆=r−1W_\star=r-1. It admits an efficient exact balanced-cut oracle with ρ=1\rho=1. Ratio-triggered nodes have positive balanced-cut values and base sizes below 4r4r, yielding μ=1/(4r)\mu=1/(4r). Thus, all assumptions of Theorem 3.7 hold with controlled parameters for fixed rr. This is a restricted existence example, not a claim about general similarity graphs.

  1. Question 3: Root reconstruction frequency and rebuilt fraction.

We added these statistics in Table 1 and Appendix I. In the certified h=64h=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=128h=128 and h=256h=256 in Appendix I.

These measurements confirm that root rebuilding remains a significant practical limitation of our current approach.

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

This paper focuses on Dasgupta hierarchical clustering problem under fully dynamic setting, where vertex may be inserted or delete. The paper argues that if there exists an oracle that can return ρ\rho-approximation for 1/41/4-balanced cut, then the proposed algorithm maintains an O(Γ)O(\Gamma)-approximation for Dasgupta optimal. The basic idea is to build the hierarchy statically and to repair it locally and lazily. The paper analyses the update time complexity and claims a polylogarithmic time complexity under some certain assumption stated in Remark 3.6. Finally, this paper includes a small experimental part to test the running time of the proposed algorithm.

Critical strengths
  1. The theoretical contribution is solid and well presented. The problem they study, hierarchical clustering in fully dynamic setting, is a natural and important open problem. The proofs are careful and clear.
  2. Theorem 3.7 provides a polylogarithmic amortized update time under certain assumptions.
Critical weaknesses
  1. (Major concern) It is not clear how to build such an ρ\rho-approximation balanced cut oracle. The overall analysis relies on such an oracle but the authors never mention where it comes from. The authors refer to (Agarwal et al.,2022) when mentioning the oracle, but the oracle in (Agarwal et al.,2022) is different from this paper. Additionally, it is not clear how the oracle influences the update time complexity, for example, if the oracle runs in tot_o time to return such a approximate balanced cut, what is the relation between tot_o with the amortized/worst case update time?

  2. (Major concern) In general case (without the assumption in Remark 3.6), the proposed algorithm provide no advantage comparing to simply reconstruction. Theorem 3.5 provides the formal statement of the update time complexity, where Bκ(s)B_{\kappa}(s) denote the reconstruction time of some dirty node ss. Hence, if the dirty node ss happens to be the root, then the algorithm has to simply reconstruct the whole hierarchy, and I don't see any evidence stopping such the worst case happening frequently.

  3. (Minor weakness) I appreciate the theoretical contribution of this paper, but I think this paper deserves a better experimental part. It is encouraged to add comparisons with some baselines mentioned in the introduction part.

Questions for authors
  1. The first two weaknesses contain some critical questions.
  2. Remark 3.6 needs further discussion. Why do we need Remark 3.6 assumptions to obtain Theorem 3.7? What is the intuition behind these assumptions? It seems that Remark 3.6 indicates that the given graph contains no cheap cut, which makes the whole graph very dense. How strong is it? Does the similar assumption appear in previous work?
2 comments

Response to Reviewer nEkU

Thank you for your comments. We have revised the paper to clarify the theoretical assumptions, update-time limitations, and experimental evidence.

  1. Weakness 1: Balanced-cut oracle and complexity.

In revised Section 2, we clarify that our oracle requires a same-balance 1/41/4-balanced cut. Exact enumeration satisfies this interface with ρ=1\rho=1 but takes exponential time. The oracle in Agarwal et al.\ (2022) does not directly establish this guarantee, and we do not claim a generally efficient oracle.

We explicitly account for oracle complexity through Bκ(s)B_\kappa(s) in Theorem 3.5. Proposition C.3 derives the construction cost from individual oracle calls. The polylogarithmic amortized bound in Theorem 3.7 therefore requires a sufficiently efficient oracle.

  1. Weakness 2: Full reconstruction and worst-case updates.

We clarify that Theorem 3.5 provides an event-based bound, not an unconditional sublinear update guarantee. If the root becomes dirty, full reconstruction is required.

Proposition E.7 proves that repeated root reconstruction is possible even on forests with at most two edges and constant-size update stars. Thus, sparsity alone cannot prevent this behavior. We explicitly distinguish this general bound from the conditional amortized guarantee in Theorem 3.7.

  1. Weakness 3: Experimental comparisons.

We added a matched insertion-only DynHAC comparison on five datasets (Appendices G--H). Our method achieves lower Dasgupta cost, whereas DynHAC achieves lower snapshot recourse; no matched update-time advantage is claimed.

We also added certificate-checked scaling experiments at h∈{64,128,256}h\in\{64,128,256\} (Appendix I), with 5/5, 4/5, and 1/5 completed runs, respectively. Reconstruction sizes, root-rebuild frequencies, and certification failures are reported to expose scalability limitations.

  1. Question 1: Clarification of Weaknesses 1 and 2.

The approximation guarantee requires a valid finite-factor cut oracle, and its running time is included in Bκ(s)B_\kappa(s). Theorem 3.5 accounts for actual reconstruction costs without guaranteeing sublinear updates. Theorem 3.7 additionally requires an efficient oracle, regularity, and bounded update-star weight.

  1. Question 2: Necessity and strength of Remark 3.6.

The regularity condition converts weight-based amortized charges into reconstruction costs by requiring the historical balanced-cut value to be proportional to the base subtree size. Without it, arbitrarily small cut values can permit repeated expensive rebuilding.

This is an execution-dependent condition on ratio-triggered node lifetimes, not a global density requirement. It does not follow from sparsity or expansion alone. Appendix D.4 provides a bounded-clique-block model satisfying regularity, sparsity, bounded update-star weight, and an efficient exact oracle simultaneously. We do not claim that this condition holds for general graphs or that it is inherited from prior work.

Regularity is needed only for Theorem 3.7, not for the approximation or event-based guarantees.

We hope these revisions address the reviewer's concerns.

Thanks for the response. My concerns remain so far. I will remain my current rating.

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

The paper studies fully dynamic hierarchical clustering on a nonnegative, weighted, undirected similarity graph. The algorithm receives vertex insertions and deletions, where inserting a vertex also introduces all its incident edges, and deleting a vertex removes all its incident edges. The goal is to maintain an explicit hierarchical clustering, represented by a rooted binary tree TT whose leaves correspond to the current vertices. The objective is to minimize Dasgupta's cost, which is the weighted sum of the set of leaves below the lowest common ancestor of pairs u and v.

Prioir work: For dynamic hierarchical clustering, prior work includes GRINCH and GraphGrove, which use local tree rearrangements to incorporate arriving points, but do not provide fully dynamic Dasgupta-cost approximation guarantees. More recently, (Yu et al., 2025) studied fully dynamic hierarchical agglomerative clustering and maintained a (1+ε)(1+\varepsilon)-approximate average-linkage hierarchy under vertex insertions and deletions. However, its guarantee concerns approximate linkage merges rather than Dasgupta's global cost objective.

Contribution: The main result is a 7.5Γ7.5\Gamma-approximation for Dasgupta-cost , assuming access to a ρ\rho-approximation oracle for 1/4-balanced minimum cut, where Γ>ρ\Gamma>\rho.

Techniques: The main algorithmic ideas are:

  1. Local validity certificates: Each cluster stores its original cut value, a membership-change counter, and deleted internal edge weight.
  2. Local rebuilding: After an update, the algorithm identifies the highest invalid cluster and reconstructs its subtree.
  3. LCA-based edge ownership: Each edge is stored at its endpoints' lowest common ancestor, allowing an induced subtree to be reconstructed without scanning boundary edges. The paper establishes an event-based update-time bound and, under additional regularity and efficient-oracle assumptions, a polylogarithmic amortized overhead beyond processing the update star.
Critical strengths
  • A meaningful theoretical problem. Maintaining a hierarchy with a global Dasgupta-cost guarantee is different from maintaining flat clustering or approximate average-linkage merges.

  • The local invariant is interesting. They certify historical splits without solving a fresh cut problem after every change.

Critical weaknesses

The efficient-update result relies on a strong regularity assumption More importantly, the authors prove in Proposition E.7 that their algorithm can perform Ω(n)\Omega(n) work repeatedly, even when every update has at most two incident edges and every intermediate graph is a forest. Thus, hereditary sparsity and constant-size update stars do not suffice to guarantee efficient updates.

  • small active set in experiments
Questions for authors

Can you give me intuition on why the regularity assumption is needed?

1 comment

Response to Reviewer BU4K

Thank you for your comments. We have revised the manuscript to clarify the regularity assumption and provide additional experimental evidence.

  1. Response to Weakness 2: Limited active-set size.

We added certificate-checked scaling experiments with active-window sizes h∈{64,128,256}h\in\{64,128,256\} (Appendix I). The completed runs are 5/5, 4/5, and 1/5, respectively. We also report update times, rebuilt-subtree sizes, root-rebuild frequencies, and certification failures. The 95th-percentile rebuilt fraction reaches 1.0, revealing the limitations of our current implementation at larger scales.

  1. Response to Question 1: Necessity of the regularity assumption.

The amortized analysis charges ratio-triggered rebuilds to inserted and deleted edge weight, while reconstruction cost depends on subtree size. Remark 3.6 ensures that the historical cut certificate λx\lambda_x is proportional to the base subtree size, allowing these weight-based charges to cover reconstruction costs. Without regularity, a large subtree with a zero or arbitrarily small cut value may require repeated reconstruction after constant-size updates, as demonstrated by Proposition E.7.

We clarified this intuition in Remark 3.6 and Appendix D and added a concrete model satisfying the assumption in Appendix D.4. The condition is required only for the amortized bound, not for correctness or approximation quality.

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

The paper studies the dynamic version for the problem of hierarchical clustering, where nodes can be inserted or deleted, under the Dasgupta cost function for hierarchical clustering.

The paper gives a fully dynamic local-repair algorithm that provides a balanced hierarchy while maintaining a good approximation to Dasguptas cost. Similar to results in approximation algorithms, their approach here is based on a blackbox oracle to a good approximation to balanced cut. The main theorem is 3.5 that states both the approximation in terms of the objective function, and the balancendeness property. The proof is provided in Appendix C.

The algorithm has several ingredients on how to maintain the right balanced tree, when a new vertex is inserted or deleted. Notice that here a vertex deletion may significantly impact the tree, and so this setting is quite challenging. In their proof, the algorithm uses several subroutines such as Prune, Register, Unregister, Build, Bucket, Link, and in total the authors present 10 different algorithms (see appendix C).

Critical strengths

-The dynamic version of hierarchical clustering is interesting and well-motivated. It is also challenging to maintain the hierarchies.

Critical weaknesses

-the paper is extremely hard to read. Moreover, the proof of the main theorem is not presented at all in the main paper of 9 pages. The authors haven't made a significant effort to present how and why the algorithm works which makes it extremely hard to understand how the algorithm proceeds. I believe the authors need to completely rewrite the technical parts of the paper and explain each step.

-no proof is provided in the main paper (other than a lemma that seems a bit uninteresting. The proof ideas are not sufficiently highlighted in the main paper.

-As is the paper is not ready for publication, since it is extremely hard to read, and little intuition provided for the main claims.

Questions for authors

-Can you elaborate more about the high-level idea of the proof? For example in the insertion case, what are the main steps and which among the 10 presented algorithms in Appendix C, should the reader focus on?

-What are the main novel steps compared to prior works, where they had already used the connection to balanced splits and sparsest cut? Can you clarify what is the relation between rho and Gamma?

-Also, have the authors tried to lighten the notation in the various lemma/theorem statements? There are several indices and subscripts that honestly do not seem to make sense in several places, or at least they are not well explained.

2 comments

Response to Reviewer MJrK

Thank you for your comments. We have revised the manuscript to clarify the algorithm, highlight the main proof ideas, and improve readability.

  1. Response to Weaknesses 1--3: Technical presentation and proof intuition.

We added a \textit{Technical Overview} in Section 1 and a \textit{Proof Outline for Theorem 3.5} in Section 3.4. These additions explain the algorithmic intuition, the connection between local invariants and the global approximation guarantee, and the main proof steps. We also clarified the update procedures and notation, while retaining complete technical proofs in Appendices B--D.

  1. Response to Question 1: Proof idea and key algorithms.

For insertion, the algorithm (i) inserts the new vertex beside an anchor and assigns new edges to LCA buckets, (ii) checks the affected ancestor path, and (iii) rebuilds the highest dirty subtree.

The proof follows three steps: Lemma 3.2 transfers historical cut lower bounds to the current graph while preserving balance; Lemmas C.4 and C.6 establish single-path invalidation and invariant restoration; Lemma 3.4 converts local cut guarantees into the global (15/2)Γ(15/2)\Gamma approximation.

The main reading path is Algorithm 1, followed by Algorithms 8 (Insert), 10 (Rebuild), and 5 (Build). Algorithms 6--7 provide the edge-bucketing details.

  1. Response to Question 2: Novelty and the relationship between ρ\rho and Γ\Gamma.

We do not claim balanced splitting or sparsest-cut techniques as novel. Our contributions are deletion-adjusted certificate transfer, single-path invalidation detection, and LCA-based induced-edge extraction for maintaining an explicit hierarchy under insertions and deletions. We clarified these distinctions in Section 1.1 (\textit{Novelty Scope}).

Here, ρ\rho is the approximation factor of the assumed 1/41/4-balanced-cut oracle, while Γ>ρ\Gamma>\rho is the threshold for retaining historical splits. The oracle provides λx=cx0/ρ\lambda_x=c_x^0/\rho, and Γ\Gamma controls when rebuilding is necessary. Setting Γ=(1+ε)ρ\Gamma=(1+\varepsilon)\rho yields an O(ρ)O(\rho) approximation for fixed ε>0\varepsilon>0.

  1. Response to Question 3: Notation and clarity.

We clarified the notation in the new \textit{Technical Overview}, distinguishing creation-time values, current subtree quantities, lifetime counters, and LCA edge buckets. We also refined their explanations throughout the technical sections to make the lemma and theorem statements easier to follow.

Reviewer_MJrKOpenReview ↗

thank you for your response

I appreciate your efforts and I believe these are good steps towards a better version of the paper. However, I looked at the revised version and still believe there are major things to improve related to the critical weaknesses mentioned above.

Based on the above, I will maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.