Learning Augmented Graph $k$-Clustering

• URL: http://arxiv.org/abs/2506.13533v1
• Date: Mon, 16 Jun 2025 14:23:16 GMT
• Title: Learning Augmented Graph $k$-Clustering
• Authors: Chenglin Fan, Kijun Shin,
• Abstract summary: Clustering is a fundamental task in unsupervised learning.<n>In this paper, we generalize learning-augmented $k$-clustering to operate on general metrics.<n>Our framework also relaxes restrictive cluster size constraints.
• Score: 3.6042771517920724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 $\Omega(k / \alpha)$ queries to achieve a $(1 + \alpha)$-approximation. These contributions strengthen both the theoretical foundations and practical applicability of learning-augmented clustering, bridging gaps between traditional methods and real-world challenges.

Related papers

• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  This paper focuses on generalization error, excess risk and consistency in ensemble clustering.<n>By assigning varying weights to finite clusterings, we minimize the error between the empirical average clusterings and their expectation.<n>We instantiate our theory to develop a new ensemble clustering algorithm.
  arXiv  Detail & Related papers  (2025-06-01T09:34:52Z)
• Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective [52.662463893268225]
  Self-supervised heterogeneous graph learning (SHGL) has shown promising potential in diverse scenarios.<n>Existing SHGL methods encounter two significant limitations.<n>We introduce a novel framework enhanced by rank and dual consistency constraints.
  arXiv  Detail & Related papers  (2024-12-01T09:33:20Z)
• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  We build on widely adopted $k$-center clustering and model its input background knowledge as must-link (ML) and cannot-link (CL) constraint sets.<n>We arrive at the first efficient approximation algorithm for constrained $k$-center with the best possible ratio of 2.
  arXiv  Detail & Related papers  (2024-01-23T07:16:32Z)
• Stable Cluster Discrimination for Deep Clustering [7.175082696240088]
  Deep clustering can optimize representations of instances (i.e., representation learning) and explore the inherent data distribution. The coupled objective implies a trivial solution that all instances collapse to the uniform features. In this work, we first show that the prevalent discrimination task in supervised learning is unstable for one-stage clustering. A novel stable cluster discrimination (SeCu) task is proposed and a new hardness-aware clustering criterion can be obtained accordingly.
  arXiv  Detail & Related papers  (2023-11-24T06:43:26Z)
• A Machine Learning-Based Framework for Clustering Residential Electricity Load Profiles to Enhance Demand Response Programs [0.0]
  We present a novel machine learning based framework in order to achieve optimal load profiling through a real case study. In this paper, we present a novel machine learning based framework in order to achieve optimal load profiling through a real case study.
  arXiv  Detail & Related papers  (2023-10-31T11:23:26Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  In differentially private clustering, the goal is to identify $k$ cluster centers without disclosing information on individual data points. We provide implementable differentially private clustering algorithms that provide utility when the data is "easy" We propose a framework that allows us to apply non-private clustering algorithms to the easy instances and privately combine the results.
  arXiv  Detail & Related papers  (2021-12-29T08:13:56Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Learning to Cluster via Same-Cluster Queries [26.284461833343403]
  We study the problem of learning to cluster data points using an oracle which can answer same-cluster queries. We propose two algorithms with provable theoretical guarantees and verify their effectiveness via an extensive set of experiments on both synthetic and real-world data.
  arXiv  Detail & Related papers  (2021-08-17T00:37:11Z)
• Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints [32.19047459493177]
  We introduce a novel family of emphstochastic pairwise constraints, which we incorporate into several essential clustering objectives. We show that these constraints can succinctly model an intriguing collection of applications, including emphIndividual Fairness in clustering and emphMust-link constraints in semi-supervised learning.
  arXiv  Detail & Related papers  (2021-03-02T20:27:58Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.