Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs
This work addresses the computational bottleneck in hierarchical clustering for graphs with clear cluster structures, offering a significant speed-up over previous methods.
The paper tackles the problem of efficient hierarchical clustering for well-clustered graphs by presenting two algorithms that run in nearly-linear time and achieve an O(1)-approximation to Dasgupta's cost function, showing comparable or better results with much lower running time on synthetic and real-world datasets.
This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function. For any input graph $G$ with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of $G$, and return an $O(1)$-approximate HC tree with respect to Dasgupta's cost function. We compare the performance of our algorithm against the previous state-of-the-art on synthetic and real-world datasets and show that our designed algorithm produces comparable or better HC trees with much lower running time.