Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.13533 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908408892882944 |
|---|---|
| author | Fan, Chenglin Shin, Kijun |
| author_facet | Fan, Chenglin Shin, Kijun |
| contents | Clustering is a fundamental task in unsupervised learning. Previous research has focused on learning-augmented $k$-means in Euclidean metrics, limiting its applicability to complex data representations. In this paper, we generalize learning-augmented $k$-clustering to operate on general metrics, enabling its application to graph-structured and non-Euclidean domains. Our framework also relaxes restrictive cluster size constraints, providing greater flexibility for datasets with imbalanced or unknown cluster distributions. Furthermore, we extend the hardness of query complexity to general metrics: under the Exponential Time Hypothesis (ETH), we show that any polynomial-time algorithm must perform approximately $Ω(k / α)$ queries to achieve a $(1 + α)$-approximation. These contributions strengthen both the theoretical foundations and practical applicability of learning-augmented clustering, bridging gaps between traditional methods and real-world challenges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_13533 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Augmented Graph $k$-Clustering Fan, Chenglin Shin, Kijun Machine Learning Data Structures and Algorithms Clustering is a fundamental task in unsupervised learning. Previous research has focused on learning-augmented $k$-means in Euclidean metrics, limiting its applicability to complex data representations. In this paper, we generalize learning-augmented $k$-clustering to operate on general metrics, enabling its application to graph-structured and non-Euclidean domains. Our framework also relaxes restrictive cluster size constraints, providing greater flexibility for datasets with imbalanced or unknown cluster distributions. Furthermore, we extend the hardness of query complexity to general metrics: under the Exponential Time Hypothesis (ETH), we show that any polynomial-time algorithm must perform approximately $Ω(k / α)$ queries to achieve a $(1 + α)$-approximation. These contributions strengthen both the theoretical foundations and practical applicability of learning-augmented clustering, bridging gaps between traditional methods and real-world challenges. |
| title | Learning Augmented Graph $k$-Clustering |
| topic | Machine Learning Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.13533 |