Learning-Augmented Hierarchical Clustering

Vladimir Braverman, Jon C. Ergun, Chen Wang, Samson Zhou
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:5454-5507, 2025.

Abstract

Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. We consider the problem of hierarchical clustering given auxiliary information from natural oracles in the learning-augmented framework. Our main results are algorithms that, given learning-augmented oracles, compute efficient approximate HC trees for the celebrated Dasgupta’s and Moseley-Wang objectives that overcome known hardness barriers.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-braverman25b, title = {Learning-Augmented Hierarchical Clustering}, author = {Braverman, Vladimir and Ergun, Jon C. and Wang, Chen and Zhou, Samson}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {5454--5507}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/braverman25b/braverman25b.pdf}, url = {https://proceedings.mlr.press/v267/braverman25b.html}, abstract = {Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. We consider the problem of hierarchical clustering given auxiliary information from natural oracles in the learning-augmented framework. Our main results are algorithms that, given learning-augmented oracles, compute efficient approximate HC trees for the celebrated Dasgupta’s and Moseley-Wang objectives that overcome known hardness barriers.} }
Endnote
%0 Conference Paper %T Learning-Augmented Hierarchical Clustering %A Vladimir Braverman %A Jon C. Ergun %A Chen Wang %A Samson Zhou %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-braverman25b %I PMLR %P 5454--5507 %U https://proceedings.mlr.press/v267/braverman25b.html %V 267 %X Hierarchical clustering (HC) is an important data analysis technique in which the goal is to recursively partition a dataset into a tree-like structure while grouping together similar data points at each level of granularity. Unfortunately, for many of the proposed HC objectives, there exist strong barriers to approximation algorithms with the hardness of approximation. We consider the problem of hierarchical clustering given auxiliary information from natural oracles in the learning-augmented framework. Our main results are algorithms that, given learning-augmented oracles, compute efficient approximate HC trees for the celebrated Dasgupta’s and Moseley-Wang objectives that overcome known hardness barriers.
APA
Braverman, V., Ergun, J.C., Wang, C. & Zhou, S.. (2025). Learning-Augmented Hierarchical Clustering. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:5454-5507 Available from https://proceedings.mlr.press/v267/braverman25b.html.

Related Material