論文の概要: Partial Optimality in Cubic Correlation Clustering for General Graphs
- arxiv url: http://arxiv.org/abs/2510.20431v1
- Date: Thu, 23 Oct 2025 11:07:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-25 03:08:17.818065
- Title: Partial Optimality in Cubic Correlation Clustering for General Graphs
- Title（参考訳）: 一般グラフの立方体相関クラスタリングにおける部分最適性
- Authors: David Stein, Bjoern Andres, Silvia Di Gregorio,
- Abstract要約: グラフの高階相関クラスタリング問題である$G$と$G$のcliqueに関連するコストは、すべて同じクラスタに属しているこれらのcliqueのコストの和を最小化するために$G$のクラスタリングを見つけることである。
このNP-hard問題に実際に取り組むために、応用の文脈において局所探索が提案され研究されている。
ここでは、立方体相関クラスタリング(英語版)のための部分最適条件、すなわち、少なくとも3つの斜めの特別な場合の最適条件を確立する。
- 参考スコア（独自算出の注目度）: 10.539905433361811
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The higher-order correlation clustering problem for a graph $G$ and costs associated with cliques of $G$ consists in finding a clustering of $G$ so as to minimize the sum of the costs of those cliques whose nodes all belong to the same cluster. To tackle this NP-hard problem in practice, local search heuristics have been proposed and studied in the context of applications. Here, we establish partial optimality conditions for cubic correlation clustering, i.e., for the special case of at most 3-cliques. We define and implement algorithms for deciding these conditions and examine their effectiveness numerically, on two data sets.
- Abstract（参考訳）: グラフの高階相関クラスタリング問題である$G$と$G$のcliqueに関連するコストは、すべて同じクラスタに属しているこれらのcliqueのコストの和を最小化するために$G$のクラスタリングを見つけることである。
このNP-hard問題に実際に取り組むために、局所探索ヒューリスティックス(英語版)が提案され、応用の文脈で研究されている。
ここでは、立方体相関クラスタリング(英語版)のための部分最適条件、すなわち、少なくとも3つの斜めの特別な場合の最適条件を確立する。
本研究では,これらの条件を決定するアルゴリズムを定義し,その妥当性を2つのデータセット上で数値的に検証する。
関連論文リスト
- Evolution of $K$-means solution landscapes with the addition of dataset
outliers and a robust clustering comparison measure for their analysis [0.0]
我々は、データセットのアウトリージの増加の結果、K$-meansのソリューション空間の変化をマッピングするために、エネルギーランドスケープアプローチを使用します。
速度論的解析により、全てのケースにおいて、全体のファンネルは浅い局所的に燃やされた地域で構成されていることが明らかとなった。
本稿では,速度解析から得られた速度がクラスタリング類似性の新たな尺度となることを提案する。
論文 参考訳（メタデータ） (2023-06-25T21:22:21Z) - Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。
IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
論文 参考訳（メタデータ） (2023-06-18T08:46:06Z) - Partial Optimality in Cubic Correlation Clustering [6.372499127940625]
最適性の証明はNPハードであり、問題文の複雑さによって事実上妨げられている。
ここでは、完備グラフと立方体目的関数の特殊ケースに対する部分最適条件の確立に焦点をあてる。
さらに、これらの条件をテストするアルゴリズムを定義し、その効果を2つのデータセット上で数値的に検証する。
論文 参考訳（メタデータ） (2023-02-09T15:25:52Z) - Near-Optimal Correlation Clustering with Privacy [37.94795032297396]
相関クラスタリングは教師なし学習における中心的な問題である。
本稿では,相関クラスタリング問題と証明可能なプライバシ保証のための,シンプルで効率的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-02T22:30:19Z) - Differentially-Private Clustering of Easy Instances [67.04951703461657]
異なるプライベートクラスタリングでは、個々のデータポイントに関する情報を公開せずに、$k$のクラスタセンターを特定することが目標だ。
我々は、データが"簡単"である場合にユーティリティを提供する実装可能な差分プライベートクラスタリングアルゴリズムを提供する。
我々は、非プライベートクラスタリングアルゴリズムを簡単なインスタンスに適用し、結果をプライベートに組み合わせることのできるフレームワークを提案する。
論文 参考訳（メタデータ） (2021-12-29T08:13:56Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Efficient Algorithms for Generating Provably Near-Optimal Cluster
Descriptors for Explainability [36.11663695534294]
本稿では,クラスタに対する簡潔な表現を構築するための最近のアプローチを拡張して,クラスタをより解釈しやすくする問題について検討する。
我々は,その問題に対する性能保証を証明可能な近似アルゴリズムを開発した。
また、異なる脅威レベルを表すゲノム配列のクラスタを含むデータセットからのクラスタを説明するアプリケーションを示す。
論文 参考訳（メタデータ） (2020-02-06T19:49:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。