Fully Dynamic Hierarchical Clustering

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-$\rho$ oracle for $1/4$-balanced cut and any fixed $\Gamma >\rho$, our algorithm maintains a $1/5$-balanced hierarchy with a $\frac{15}{2}\Gamma$-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 $O(1)$ time, while reporting the complete hierarchy takes $\Theta (1+n_t)$ time, where $n_t$ is the current number of active vertices. For a rebuild involving $s$ vertices, the stable set recourse is $O(s)$ and the stable mass recourse is $O(s\log (2+s))$.