Fully Dynamic Hierarchical Clustering for Well-Clustered Graphs

*Hierarchical Clustering* (HC) is a fundamental problem in data science. Its objective is to compute a hierarchical partition of the input data while minimizing the cost function (Dasgupta, STOC 2016). We study the HC problem on well-clustered graphs, which admit a partition into $k$ clusters with high inner conductance ${\varphi }_{in}$. We show that such a $(k,{\varphi }_{in})$-decomposition always exists for every connected graph, and that our assumption can be naturally derived from other notions of clusterability in the literature. We prove that a simple bucketing-and-concatenation procedure achieves an $O(k/{\varphi }_{in})$-approximation for this problem, which becomes an $O(1)$-approximation for constant values of $k$ and ${\varphi }_{in}$, with linear running time. Our result requires strictly weaker assumptions, and achieves a substantially better approximation ratio in less time than the previous state-of-the-art method (Laenen et al., ICML 2023). Due to its simplicity, our algorithm is directly applicable in the fully dynamic setting and, with an update time of $O(1)$, achieves the same approximation guarantee in the static setting. The excellent performance of our algorithm is demonstrated by the experiments on both synthetic and real-world graphs.