Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs
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.
Cite
Text
Laenen et al. "Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs." International Conference on Machine Learning, 2023.Markdown
[Laenen et al. "Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/laenen2023icml-nearlyoptimal/)BibTeX
@inproceedings{laenen2023icml-nearlyoptimal,
title = {{Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs}},
author = {Laenen, Steinar and Manghiuc, Bogdan Adrian and Sun, He},
booktitle = {International Conference on Machine Learning},
year = {2023},
pages = {18207-18249},
volume = {202},
url = {https://mlanthology.org/icml/2023/laenen2023icml-nearlyoptimal/}
}