論文の概要: Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
- arxiv url: http://arxiv.org/abs/2404.16131v1
- Date: Wed, 24 Apr 2024 18:39:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-26 18:02:25.922179
- Title: Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better
- Title（参考訳）: クラスタ削除のための組合せ近似: よりシンプルで、より速く、より良く
- Authors: Vicente Balmaseda, Ying Xu, Yixin Cao, Nate Veldt,
- Abstract要約: クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
- 参考スコア（独自算出の注目度）: 18.121514220195607
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Cluster deletion is an NP-hard graph clustering objective with applications in computational biology and social network analysis, where the goal is to delete a minimum number of edges to partition a graph into cliques. We first provide a tighter analysis of two previous approximation algorithms, improving their approximation guarantees from 4 to 3. Moreover, we show that both algorithms can be derandomized in a surprisingly simple way, by greedily taking a vertex of maximum degree in an auxiliary graph and forming a cluster around it. One of these algorithms relies on solving a linear program. Our final contribution is to design a new and purely combinatorial approach for doing so that is far more scalable in theory and practice.
- Abstract（参考訳）: クラスタ削除はNPハードグラフクラスタリングの目的であり、計算生物学やソーシャルネットワーク分析の応用において、グラフを斜めに分割するために最小限のエッジを削除することが目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
さらに、補助グラフにおいて最大等級の頂点を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
これらのアルゴリズムの1つは線形プログラムの解法に依存する。
私たちの最後の貢献は、理論と実践においてはるかにスケーラブルになるように、新しく純粋に組み合わせたアプローチを設計することです。
関連論文リスト
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs [6.523602840064548]
このようなグラフに特化された効率的な(epsilon,$delta$)-DPアルゴリズムを提供する。
我々のアルゴリズムは、ほぼバランスの取れたクラスタに対して$k$のグラフを扱う。
論文 参考訳（メタデータ） (2024-03-21T11:57:16Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Faster Approximation Algorithms for Parameterized Graph Clustering and
Edge Labeling [6.599344783327054]
グラフクラスタリングは、グラフの他の部分と疎結合なノードの集合を検出することを目的としている、ネットワーク分析における基本的なタスクである。
NPハードなパラメータ化クラスタリングフレームワークLambdaCCに対して,高速な近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-08T02:29:37Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
点雲を符号化するグラフ上での効率的な場積分のためのアルゴリズムを2種類提案する。
第1のクラスであるSeparatorFactorization(SF)は、ポイントメッシュグラフの有界属を利用するが、第2のクラスであるRFDiffusion(RFD)は、ポイントクラウドの一般的なepsilon-nearest-neighborグラフ表現を使用する。
論文 参考訳（メタデータ） (2023-02-02T08:33:36Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Scalable and Effective Conductance-based Graph Clustering [9.938406925123722]
グラフクラスタリングフレームワーク textitPCon を開発した。
既存のソリューションの多くをフレームワークに還元できることを示します。
本稿では,線形時間と空間の複雑さを考慮した2つの新しいアルゴリズムである textitPCon_core と emphPCon_de を提案する。
論文 参考訳（メタデータ） (2022-11-22T12:45:27Z) - Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。
すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
論文 参考訳（メタデータ） (2022-06-15T16:25:27Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。