Learning Augmented Graph $k$-Clustering
This work addresses the limitation of existing clustering methods to complex, non-Euclidean data, making it more applicable to real-world domains like graph analysis, though it is incremental in extending prior Euclidean-focused approaches.
The paper tackles the problem of extending learning-augmented k-clustering from Euclidean metrics to general metrics, such as graph-structured data, and relaxes cluster size constraints for imbalanced datasets, achieving a theoretical lower bound of approximately Ω(k/α) queries for a (1+α)-approximation under the Exponential Time Hypothesis.
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.