将学习增强的聚类扩展到图结构数据，提升实际应用灵活性。
Learning Augmented Graph $k$-Clustering
- 提出适用于一般度量空间的聚类框架，支持图结构数据
- 在ETH假设下证明需至少Ω(k/α)次查询才能达到(1+α)近似
- 放宽簇大小限制，适合不平衡或未知分布的数据
聚类是无监督学习中的基础任务。以往研究主要聚焦于欧氏空间中的学习增强k-均值，限制了其在复杂数据表示中的应用。本文将学习增强的k-聚类推广至一般度量空间，使其适用于图结构与非欧氏域。该框架还放宽了对簇大小的严格约束，提升了对不平衡或未知簇分布数据的适应性。此外，在指数时间假设（ETH）下，我们证明任何多项式时间算法必须执行约Ω(k/α)次查询才能实现(1+α)近似。这些贡献强化了学习增强聚类的理论基础与实际应用价值，弥合了传统方法与现实挑战之间的差距。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。