Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

Steinar Laenen; Bogdan Adrian Manghiuc; He Sun

ICML 2023poster6 citations

Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs

Steinar Laenen, Bogdan Adrian Manghiuc, He Sun

Abstract

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.

BibTeX

@inproceedings{icml2023_nearlyoptimalhie,
  title = {Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs},
  author = {Steinar Laenen and Bogdan Adrian Manghiuc and He Sun},
  booktitle = {ICML 2023},
  year = {2023}
}