論文の概要: Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy

• arxiv url: http://arxiv.org/abs/2106.07501v2
• Date: Thu, 13 Jul 2023 05:51:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-14 17:54:07.879375
• Title: Balanced Coarsening for Multilevel Hypergraph Partitioning via Wasserstein Discrepancy
• Title（参考訳）: wassersteinの不一致によるマルチレベルハイパーグラフ分割のためのバランスのとれた粗さ処理
• Authors: Zhicheng Guo, Jiaxuan Zhao, Licheng Jiao, Xu Liu
• Abstract要約: マルチレベルハイパーグラフのためのバランスの取れた粗大化方式を提案する。 初期分割アルゴリズムはk-wayハイパーグラフの品質を向上させるために設計されている。
• 参考スコア（独自算出の注目度）: 40.93626211612559
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a balanced coarsening scheme for multilevel hypergraph partitioning. In addition, an initial partitioning algorithm is designed to improve the quality of k-way hypergraph partitioning. By assigning vertex weights through the LPT algorithm, we generate a prior hypergraph under a relaxed balance constraint. With the prior hypergraph, we have defined the Wasserstein discrepancy to coordinate the optimal transport of coarsening process. And the optimal transport matrix is solved by Sinkhorn algorithm. Our coarsening scheme fully takes into account the minimization of connectivity metric (objective function). For the initial partitioning stage, we define a normalized cut function induced by Fiedler vector, which is theoretically proved to be a concave function. Thereby, a three-point algorithm is designed to find the best cut under the balance constraint.
• Abstract（参考訳）: マルチレベルハイパーグラフ分割のためのバランスの取れた粗大化方式を提案する。 さらに,k方向ハイパーグラフ分割の品質向上のために,初期分割アルゴリズムが設計された。 LPTアルゴリズムにより頂点重みを割り当てることで、緩和バランス制約の下で先行ハイパーグラフを生成する。 先行ハイパーグラフを用いて,粗粒化過程の最適移動をコーディネートするために,wassersteinの不一致を定義した。 そして、最適輸送行列をシンクホーンアルゴリズムにより解く。 我々の粗面化スキームは接続距離(目的関数)の最小化を十分に考慮している。 最初の分割の段階では、フィドラーベクトルによって誘導される正規化カット関数を定義し、理論的には凹関数であることが証明される。 これにより、バランス制約の下で最適なカットを見つけるための3点アルゴリズムが設計される。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。 本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
  論文  参考訳（メタデータ） (2024-06-28T02:56:22Z)
• Graph Cuts with Arbitrary Size Constraints Through Optimal Transport [18.338458637795263]
  任意のサイズ制約下でグラフを分割するグラフカットアルゴリズムを提案する。 我々は,大域収束を臨界点に保証する高速化された近位GDアルゴリズムを用いてこの問題を解決する。
  論文  参考訳（メタデータ） (2024-02-07T10:33:09Z)
• Decentralized Inexact Proximal Gradient Method With Network-Independent Stepsizes for Convex Composite Optimization [39.352542703876104]
  本稿では,非方向および接続ネットワーク上での分散凸複合最適化について考察する。 CTA(Combine-Then-Adapt)に基づく新しい分散アルゴリズムは、非協調的なネットワーク非依存の定数ステップサイズの下で提案される。
  論文  参考訳（メタデータ） (2023-02-07T03:50:38Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。 このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
  論文  参考訳（メタデータ） (2021-12-22T05:38:33Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Hypergraph Partitioning using Tensor Eigenvalue Decomposition [19.01626581411011]
  我々は、k-ユニフォームハイパーグラフの分割のための新しいアプローチを提案する。 既存の手法のほとんどは、ハイパーグラフをグラフに還元し、次に標準的なグラフ分割アルゴリズムを適用することで機能する。 我々は、テンソルベースのハイパーグラフ表現を利用することでこの問題を克服する。
  論文  参考訳（メタデータ） (2020-11-16T01:55:43Z)
• S-ADDOPT: Decentralized stochastic first-order optimization over directed graphs [16.96562173221624]
  有向ネットワークノード上に分散する関数のスムーズかつ高コストな関数の和を最小化するために,分散凸最適化を提案する。 特に,各ノードに1次オラクルを仮定するtextbftextttS-ADDOPTアルゴリズムを提案する。 崩壊するステップサイズ$mathcalO (1/k)$に対して、textbfttS-ADDOPT が$mathcalO (1/k)$ で正解に達し、その収束はネットワーク非依存であることを示す。
  論文  参考訳（メタデータ） (2020-05-15T21:14:22Z)

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

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