論文の概要: Graph Cuts with Arbitrary Size Constraints Through Optimal Transport
- arxiv url: http://arxiv.org/abs/2402.04732v2
- Date: Fri, 04 Oct 2024 15:39:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-07 15:06:48.146520
- Title: Graph Cuts with Arbitrary Size Constraints Through Optimal Transport
- Title（参考訳）: 最適輸送による任意サイズ制約付きグラフカット
- Authors: Chakib Fettal, Lazhar Labiod, Mohamed Nadif,
- Abstract要約: 任意のサイズ制約下でグラフを分割するグラフカットアルゴリズムを提案する。
我々は,大域収束を臨界点に保証する高速化された近位GDアルゴリズムを用いてこの問題を解決する。
- 参考スコア（独自算出の注目度）: 18.338458637795263
- License:
- Abstract: A common way of partitioning graphs is through minimum cuts. One drawback of classical minimum cut methods is that they tend to produce small groups, which is why more balanced variants such as normalized and ratio cuts have seen more success. However, we believe that with these variants, the balance constraints can be too restrictive for some applications like for clustering of imbalanced datasets, while not being restrictive enough for when searching for perfectly balanced partitions. Here, we propose a new graph cut algorithm for partitioning graphs under arbitrary size constraints. We formulate the graph cut problem as a Gromov-Wasserstein with a concave regularizer problem. We then propose to solve it using an accelerated proximal GD algorithm which guarantees global convergence to a critical point, results in sparse solutions and only incurs an additional ratio of $\mathcal{O}(\log(n))$ compared to the classical spectral clustering algorithm but was seen to be more efficient.
- Abstract（参考訳）: グラフを分割する一般的な方法は、最小カットによるものである。
古典的最小カット法の欠点の1つは、それらが小さな群を生成する傾向があることである。
しかし、これらの変種では、バランスの制約は、不均衡なデータセットのクラスタリングのようないくつかのアプリケーションでは制限されすぎ、完全にバランスの取れたパーティションを探すのに十分な制限はない、と我々は信じている。
本稿では,任意のサイズ制約の下でグラフを分割するグラフカットアルゴリズムを提案する。
グラフカット問題を、凹正則化問題を持つグロモフ・ワッサーシュタインとして定式化する。
そこで我々は, 臨界点への大域収束を保証し, スパース解となり, 古典的スペクトルクラスタリングアルゴリズムと比較して$\mathcal{O}(\log(n))$の余剰比が$\mathcal{O}(\log(n))$となるような, 高速化された近位GDアルゴリズムを用いてこの問題を解決することを提案する。
関連論文リスト
- Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。
まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。
補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
論文 参考訳（メタデータ） (2024-04-24T18:39:18Z) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。
ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
論文 参考訳（メタデータ） (2023-08-12T02:47:57Z) - One-step Bipartite Graph Cut: A Normalized Formulation and Its
Application to Scalable Subspace Clustering [56.81492360414741]
両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。
本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。
このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
論文 参考訳（メタデータ） (2023-05-12T11:27:20Z) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
量子近似最適化アルゴリズム(QAOA)とクォーディットを用いた相関クラスタリング問題について検討する。
具体的には、中性原子量子コンピュータを検討し、相関クラスタリングのためのフルスタックアプローチを提案する。
ゲート数によって定量化されるように、quditの実装はqubitエンコーディングよりも優れていることを示す。
論文 参考訳（メタデータ） (2021-06-22T11:07:38Z) - Balanced Coarsening for Multilevel Hypergraph Partitioning via
Wasserstein Discrepancy [40.93626211612559]
マルチレベルハイパーグラフのためのバランスの取れた粗大化方式を提案する。
初期分割アルゴリズムはk-wayハイパーグラフの品質を向上させるために設計されている。
論文 参考訳（メタデータ） (2021-06-14T15:30:34Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳（メタデータ） (2021-01-19T04:24:23Z) - A Performance Guarantee for Spectral Clustering [0.6445605125467572]
スペクトルクラスタリングはいつ,最小比カット問題に対する大域的な解を見つけることができるのか?
我々は、グラフラプラシアンの不変部分空間に対して、$k$最小固有値に対応する決定論的2-無限ノルムを開発する。
これら2つの結果を組み合わせることで、スペクトルクラスタリングが保証され、大域的な解を最小比カット問題に出力する条件を与える。
論文 参考訳（メタデータ） (2020-07-10T22:03:43Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Computationally efficient sparse clustering [67.95910835079825]
我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。
ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
論文 参考訳（メタデータ） (2020-05-21T17:51:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。