Learning-Augmented Hierarchical Clustering
Vladimir Braverman, Jon C. Ergun, Chen Wang, Samson Zhou
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.
BibTeX
@inproceedings{
braverman2025learningaugmented,
title={Learning-Augmented Hierarchical Clustering},
author={Vladimir Braverman and Jon C. Ergun and Chen Wang and Samson Zhou},
booktitle={Forty-second International Conference on Machine Learning},
year={2025},
url={https://openreview.net/forum?id=FU527ycGgW}
}