論文の概要: Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
- arxiv url: http://arxiv.org/abs/2607.13217v1
- Date: Tue, 14 Jul 2026 19:25:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-16 16:39:12.57314
- Title: Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
- Title（参考訳）: Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and bounded Diameter Graphs
- Abstract要約: 本稿では,線形プログラミングに基づく階層クラスタリング問題を近似する枠組みを提案する。
我々は,p_mathcalF$-Partitioning と呼ばれる平らなクラスタリング問題に対して,自然に ILP を定式化することで,フレームワークが適用可能であることを示す。
また,木への階層的クラスタリングと境界直径グラフのどちらも,小集合展開仮説の下での任意の定数係数内では近似できないことを示す。
- 参考スコア（独自算出の注目度）: 0.8594140167290095
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Consider the following variation on the Hierarchical Clustering problem: Usually, while building a hierarchical clustering, one recursively partitions the data until each cluster becomes a singleton. We relax the halting condition of the recursive process to stop whenever the remaining cluster is a graph belonging to a class $\mathcal{F}$. We call this problem Hierarchical $\mathcal{F}$-Clustering and we measure the quality of any solution using adapted Dasgupta's clustering objective. We study two natural choices of $\mathcal{F}$: trees and graphs of bounded diameter. We present the first polynomial time $\mathcal{O}(\log n\cdot\log\log n)$ and $\mathcal{O}(\log n)$-approximation algorithms for clustering into trees and bounded diameter graphs respectively. Our main technical contribution is a framework for approximating such problems based on linear programming. In fact, we characterize graphs classes $\mathcal{F}$ for which our approach can be applied and show that it includes both trees and bounded diameter graphs. However, our ideas are not limited to them and might be useful for other structures as well. Broadly speaking, our framework applies whenever the corresponding flat clustering problem, which we call $p_{\mathcal{F}}$-Partitioning, admits a natural ILP formulation together with a rounding procedure with provable approximation guarantees. Intuitively, given a set of vertices called terminals, the problem is to find an edge set whose removal results in satisfying certain vertex-dependent structural predicate for each terminal. We then use these ingredients to build clustering trees with the aforementioned approximation guarantees. To complement these results, we show that both Hierarchical Clustering into trees and into bounded diameter graphs cannot be approximated within any constant factor under the Small Set Expansion Hypothesis.
- Abstract（参考訳）: 階層的なクラスタリングを構築する際、各クラスタがシングルトンになるまで再帰的にデータを分割する。
再帰過程の停止条件を緩和し、残りのクラスタがクラス $\mathcal{F}$ に属するグラフであるときに停止する。
この問題をHierarchical $\mathcal{F}$-Clusteringと呼び、適応されたDasguptaのクラスタリングの目的を用いて任意のソリューションの品質を測定する。
我々は、$\mathcal{F}$:木と有界な直径のグラフの2つの自然選択について研究する。
最初の多項式時間 $\mathcal{O}(\log n\cdot\log n)$ と $\mathcal{O}(\log n)$-approximation algorithm for clustering into tree and bounded diameter graph。
我々の主な技術的貢献は、線形プログラミングに基づくそのような問題を近似するためのフレームワークである。
実際、我々は、我々のアプローチを適用することができるグラフクラス $\mathcal{F}$ を特徴づけ、木と有界径グラフの両方を含むことを示す。
しかしながら、私たちのアイデアはそれらに限らず、他の構造にも役立つかもしれません。
広く言えば、我々のフレームワークは、対応するフラットクラスタリング問題($p_{\mathcal{F}}$-Partitioning)が必ず適用されます。
直感的には、端末と呼ばれる頂点の集合が与えられたとき、問題は各端末に対して頂点依存構造述語を満たすようなエッジ集合を見つけることである。
次に、上記の近似保証付きクラスタリングツリーを構築するためにこれらの材料を使用します。
これらの結果を補うために、木への階層的クラスタリングと境界直径グラフへのクラスタリングは、小集合展開仮説の下では任意の定数係数で近似できないことを示す。
関連論文リスト
- Learning-Augmented Hierarchical Clustering [29.438861266606573]
自然のオラクルから補助情報を得た階層的クラスタリングの問題を考察する。
分割オラクルは、アルゴリズムが標準のHCアプローチより優れていることを示す。
我々のアプローチはサブ線形設定にまで拡張され、保証を改善した新しいストリーミングとPRAMアルゴリズムが示されます。
論文 参考訳（メタデータ） (2025-06-05T18:22:40Z) - IsoSEL: Isometric Structural Entropy Learning for Deep Graph Clustering in Hyperbolic Space [57.036143666293334]
グラフクラスタリングは、機械学習における長年のトピックである。
本稿では,K を含まない深層グラフクラスタリングという,現実の非均衡を考慮した問題について検討する。
深層グラフクラスタリングのための新しいIsoSELフレームワークを提案する。このフレームワークでは、双曲空間のローレンツモデルにおける分割木を学習するための双曲型ニューラルネットワークを設計する。
論文 参考訳（メタデータ） (2025-04-14T08:21:41Z) - A Unified Framework for Center-based Clustering of Distributed Data [46.86543102499174]
我々は、ユーザのネットワーク上で動作する分散センターベースのクラスタリングアルゴリズムのファミリーを開発する。
私たちのフレームワークは、$K$-meansやHuber Losといった一般的なクラスタリング損失を含む、スムーズな凸損失関数の幅広いクラスを可能にします。
ブレグマン損失の特別の場合、固定点がロイド点の集合に収束することを示す。
論文 参考訳（メタデータ） (2024-02-02T10:44:42Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。
ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。
クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。
ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
論文 参考訳（メタデータ） (2023-05-28T15:33:24Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Robust Correlation Clustering with Asymmetric Noise [3.8073142980733]
相関クラスタリング(英語版)はグラフクラスタリングの定式化であり、(1) ノード間の類似性/異性度を示すエッジウェイトを持つ符号付きグラフを入力とし、(2) 入力グラフ内のクラスタ数を事前に見積もる必要がない。
グラフノードの特徴ベクトル/埋め込みの生成に基づく新しいグラフ生成モデルNode Factors Model (NFM)を提案する。
論文 参考訳（メタデータ） (2021-10-15T21:47:27Z) - Exact and Approximate Hierarchical Clustering Using A* [51.187990314731344]
クラスタリングのA*探索に基づく新しいアプローチを紹介します。
A*と新しいエンフォレリスデータ構造を組み合わせることで、禁止的に大きな検索空間を克服します。
実験により,本手法は粒子物理利用事例や他のクラスタリングベンチマークにおいて,ベースラインよりもかなり高品質な結果が得られることを示した。
論文 参考訳（メタデータ） (2021-04-14T18:15:27Z) - Exact Recovery of Clusters in Finite Metric Spaces Using Oracle Queries [22.672233769934845]
オラクルクエリを用いたクラスタ依存の正確な問題について検討する。
任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意の任意
論文 参考訳（メタデータ） (2021-01-31T18:00:29Z) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
データの局所構造とグローバル構造の両方を保存するためのグラフ学習フレームワークを提案する。
本手法は, サンプルの自己表現性を利用して, 局所構造を尊重するために, 大域的構造と適応的隣接アプローチを捉える。
我々のモデルは、ある条件下でのカーネルk平均法とk平均法の組合せと等価である。
論文 参考訳（メタデータ） (2020-08-31T08:41:20Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z) - Explainable $k$-Means and $k$-Medians Clustering [25.513261099927163]
我々は、小さな決定木を使ってデータセットをクラスタに分割し、クラスタを直接的な方法で特徴付けることを検討する。
一般的なトップダウン決定木アルゴリズムが任意のコストでクラスタリングに繋がる可能性があることを示す。
我々は、$k$の葉を持つ木を用いて説明可能なクラスタを生成する効率的なアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-02-28T04:21:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。