論文の概要: Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues

• arxiv url: http://arxiv.org/abs/2306.09128v1
• Date: Thu, 15 Jun 2023 13:41:17 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-16 14:37:06.336583
• Title: Fast Algorithms for Directed Graph Partitioning Using Flows and Reweighted Eigenvalues
• Title（参考訳）: フローと重み付き固有値を用いたグラフ分割の高速アルゴリズム
• Authors: Lap Chi Lau, Kam Chuen Tung, Robert Wang
• Abstract要約: 我々は,有向エッジ拡張に対する$O(sqrtlogn)$-approximationとCheeger型保証を実現するために,ほぼ線形時間アルゴリズムを導出する。 これは、有向グラフ分割のための最もよく知られたアルゴリズムを得るための、原始二重フローベースのフレームワークを提供する。
• 参考スコア（独自算出の注目度）: 6.094384342913063
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a new semidefinite programming relaxation for directed edge expansion, which is obtained by adding triangle inequalities to the reweighted eigenvalue formulation. Applying the matrix multiplicative weight update method to this relaxation, we derive almost linear-time algorithms to achieve $O(\sqrt{\log{n}})$-approximation and Cheeger-type guarantee for directed edge expansion, as well as an improved cut-matching game for directed graphs. This provides a primal-dual flow-based framework to obtain the best known algorithms for directed graph partitioning. The same approach also works for vertex expansion and for hypergraphs, providing a simple and unified approach to achieve the best known results for different expansion problems and different algorithmic techniques.
• Abstract（参考訳）: 再重み付けされた固有値の定式化に三角不等式を加えることによって得られる有向辺展開に対する新しい半定値プログラミング緩和を考える。 この緩和に行列乗算重み更新法を適用することで、有向エッジ拡張のための$O(\sqrt{\log{n}})$-approximationとCheeger型保証を実現するためのほぼ線形時間アルゴリズムと、有向グラフのためのカットマッチングゲームが導出される。 これは、有向グラフ分割のための最もよく知られたアルゴリズムを得るために、原始的フローベースのフレームワークを提供する。 同じアプローチは頂点展開やハイパーグラフにも有効であり、異なる拡張問題と異なるアルゴリズム技術に対して最もよく知られた結果を得るための単純で統一的なアプローチを提供する。

関連論文リスト

• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• An Alternative Graphical Lasso Algorithm for Precision Matrices [0.0]
  本稿では,スパース精度行列を推定するためのDP-GLassoアルゴリズムを提案する。 正規化された正規対数型は自然に凸関数を最小化しやすい2つの和に分解するが、そのうちの1つはラッソ回帰問題である。 提案アルゴリズムは,最適化対象とする精度行列を最初から備えており,DP-GLassoアルゴリズムの良好な特性をすべて保持している。
  論文  参考訳（メタデータ） (2024-03-19T02:01:01Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Robust empirical risk minimization via Newton's method [9.797319790710711]
  実験的リスク最小化のためのニュートン法の新しい変種について検討した。 目的関数の勾配と Hessian は、ロバストな推定器に置き換えられる。 また,共役勾配法に基づくニュートン方向のロバストな解を求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T18:54:54Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition [10.620193291237262]
  これらのアルゴリズムは、ポリアジック分解形態におけるローランクテンソルの因子行列の積空間上の非ユークリッド計量を利用する。 提案された勾配降下アルゴリズムがテンソル完備問題の定常点にグローバルに収束することを証明する。 合成データと実世界のデータの数値計算結果から,提案アルゴリズムは最先端アルゴリズムよりもメモリと時間において効率的であることが示唆された。
  論文  参考訳（メタデータ） (2021-01-26T22:11:06Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Alternating minimization algorithms for graph regularized tensor completion [8.26185178671935]
  我々は、低ランクテンソル完備化(LRTC)に対するカノニカルポリアディック(CP)分解法を考える。 グラフ正規化の使用にはLRTCの学習精度のメリットが伴うが、同時に結合グラフラプラシア語を誘導する。 基礎となるCP分解モデルにおけるブロック構造を利用して, 効率の良い同期最小化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-08-28T23:20:49Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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