論文の概要: Learning Augmented Graph $k$-Clustering

• arxiv url: http://arxiv.org/abs/2506.13533v1
• Date: Mon, 16 Jun 2025 14:23:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-17 17:28:48.688922
• Title: Learning Augmented Graph $k$-Clustering
• Title（参考訳）: グラフの強化による$k$-Clusteringの学習
• Authors: Chenglin Fan, Kijun Shin,
• Abstract要約: クラスタリングは教師なし学習における基本的なタスクである。 本稿では,一般的なメトリクスに基づいて,学習支援の$k$-clusteringを一般化する。 私たちのフレームワークは、制限的なクラスタサイズ制約も緩和します。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: クラスタリングは教師なし学習における基本的なタスクである。 これまでの研究は、ユークリッドのメトリクスにおける学習強化された$k$-meansに重点を置いており、複雑なデータ表現に適用性を制限する。 本稿では,学習強化された$k$-clusteringを一般化して一般的なメトリクスで運用し,グラフ構造化および非ユークリッド領域への応用を可能にする。 当社のフレームワークは,クラスタサイズ制限を緩和し,不均衡あるいは未知のクラスタ分布を持つデータセットの柔軟性を向上する。 指数時間仮説(ETH)では、任意の多項式時間アルゴリズムが約$\Omega(k / \alpha)$クエリを実行し、$(1 + \alpha)$-approximationを達成しなければならないことを示す。 これらの貢献は、学習強化クラスタリングの理論的基礎と実践的適用性、従来の手法と現実世界の課題の間のギャップを埋めることの両方を強化する。

関連論文リスト

• Generalization Performance of Ensemble Clustering: From Theory to Algorithm [57.176040163699554]
  本稿では,アンサンブルクラスタリングにおける一般化誤差,過剰リスク,一貫性に着目した。 有限クラスタリングに様々な重みを割り当てることで、経験的平均クラスタリングと期待値との誤差を最小化する。 我々は、新しいアンサンブルクラスタリングアルゴリズムを開発するために、我々の理論をインスタンス化する。
  論文  参考訳（メタデータ） (2025-06-01T09:34:52Z)
• Revisiting Self-Supervised Heterogeneous Graph Learning from Spectral Clustering Perspective [52.662463893268225]
  自己教師付きヘテロジニアスグラフ学習(SHGL)は様々なシナリオにおいて有望な可能性を示している。 既存のSHGLメソッドには2つの大きな制限がある。 ランクと二重整合性制約によって強化された新しいフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-12-01T09:33:20Z)
• Near-Optimal Algorithms for Constrained k-Center Clustering with Instance-level Background Knowledge [12.808663917871888]
  我々は、広く採用されている$k$-centerクラスタリングに基づいて、その入力背景知識を must-link (ML) および cannot-link (CL) 制約セットとしてモデル化する。 制約付き$k$-centerの最初の効率的な近似アルゴリズムに到達します。
  論文  参考訳（メタデータ） (2024-01-23T07:16:32Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [69.15976031704687]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Differentially-Private Clustering of Easy Instances [67.04951703461657]
  異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。 我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。 我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
  論文  参考訳（メタデータ） (2021-12-29T08:13:56Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Learning to Cluster via Same-Cluster Queries [26.284461833343403]
  我々は,同一クラスタクエリに応答可能なオラクルを用いて,データポイントのクラスタ化を学習する問題について検討する。 提案する2つのアルゴリズムは, 理論的保証を証明可能とし, 合成データと実世界のデータの両方に関する広範な実験により, 有効性を検証する。
  論文  参考訳（メタデータ） (2021-08-17T00:37:11Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。