論文の概要: $\ell_2$-norm Flow Diffusion in Near-Linear Time

• arxiv url: http://arxiv.org/abs/2105.14629v1
• Date: Sun, 30 May 2021 21:27:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-01 16:53:22.284718
• Title: $\ell_2$-norm Flow Diffusion in Near-Linear Time
• Title（参考訳）: $\ell_2$-norm Flow Diffusion in Near-Linear Time
• Authors: Li Chen, Richard Peng, and Di Wang
• Abstract要約: 我々は$ell$-normフロー拡散問題に対して$widetildeO(m)$-timeランダム化アルゴリズムを提供する。 これは単純に双対解ベクトルを網羅することによって実現される。 Laplacianシステムソルバの高レベルなアルゴリズムフレームワークに適応するが、いくつかの新しいツールが必要である。
• 参考スコア（独自算出の注目度）: 18.263667346853698
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Diffusion is a fundamental graph process and has been a basic building block in the study of graph clustering and graph learning tasks such as node classification. In this paper, we initiate the study of computationally efficient diffusion primitives beyond random walk. We provide an $\widetilde{O}(m)$-time randomized algorithm for the $\ell_2$-norm flow diffusion problem, obtaining the approximation factor of $1+1/\mathrm{poly}(n)$. Using the connection between its dual solution and local cut structure, we give an alternative approach for finding locally-biased low conductance cuts. It is done simply by sweeping over the dual solution vector. This algorithm demonstrates a novel way of dealing with inequality constraints in graph optimization problems. It adapts the high-level algorithmic framework of Laplacian system solvers, but requires several new tools: vertex elimination under constraints, a new family of graph ultra-sparsifiers, and accelerated proximal gradient methods with inexact proximal mapping computation.
• Abstract（参考訳）: 拡散は基本的なグラフプロセスであり、グラフクラスタリングやノード分類などのグラフ学習タスクの研究において基礎的な構成要素となっている。 本稿では,ランダムウォークを超える計算効率の良い拡散プリミティブの研究を開始する。 我々は$\ell_2$-normフロー拡散問題に対して$\widetilde{O}(m)$-timeランダム化アルゴリズムを提供し、近似係数を1+1/\mathrm{poly}(n)$とする。 双対解と局所切断構造との接続を用いて,局所バイアスによる低導電率切断を見つける方法を提案する。 これは単に双対解ベクトルの上を掃くことによって行われる。 このアルゴリズムはグラフ最適化問題において不等式制約を扱う新しい方法を示す。 これはラプラシアン・システム・ソルバの高レベルなアルゴリズム・フレームワークに適応するが、制約下での頂点除去、グラフ超分離器の新たなファミリー、不正確な近位写像計算による近位勾配法などの新しいツールを必要とする。

関連論文リスト

• Combinatorial Approximations for Cluster Deletion: Simpler, Faster, and Better [18.121514220195607]
  クラスタ削除は、計算およびソーシャルネットワーク分析におけるNPハードグラフクラスタリングの目的である。 まず,2つの近似アルゴリズムの厳密な解析を行い,その近似保証を4から3に改善する。 補助グラフにおいて最大等級を優しく取り、その周囲にクラスタを形成することにより、両アルゴリズムを驚くほど単純な方法でデランドマイズすることができることを示す。
  論文  参考訳（メタデータ） (2024-04-24T18:39:18Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• 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)
• Optimal Gradient Sliding and its Application to Distributed Optimization Under Similarity [121.83085611327654]
  積 $r:=p + q$, ここで$r$は$mu$-strong convex類似性である。 エージェントの通信やローカルコールにマスターされた問題を解決する方法を提案する。 提案手法は$mathcalO(sqrtL_q/mu)$法よりもはるかにシャープである。
  論文  参考訳（メタデータ） (2022-05-30T14:28:02Z)
• Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions [9.29659220237395]
  本稿では,相関クラスタリングの解法を提案する。 我々は高効率な時間と空間の複雑さを持つサブ線形アルゴリズムを得る。 提案手法の主な要素はスパース線グラフ分解への新規な接続である。
  論文  参考訳（メタデータ） (2021-09-29T16:25:02Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。 MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
  論文  参考訳（メタデータ） (2021-02-15T07:10:33Z)
• Multiway $p$-spectral graph cuts on Grassmann manifolds [0.3441021278275805]
  直接マルチウェイスペクトルクラスタリングアルゴリズムを$p$-norm, for $p in (1, 2]$で提案する。 グラフ $p$-Laplacian の多重固有ベクトルを計算する問題は、グラスマン多様体上の制約のない最小化問題として再キャストされる。 バランスの取れたグラフの単調な減少を監視することは、検討された$p$レベルから最高の解が得られることを保証します。
  論文  参考訳（メタデータ） (2020-08-30T16:25:04Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• $p$-Norm Flow Diffusion for Local Graph Clustering [18.90840167452118]
  我々は、p-ノルムネットワークフローとの拡散を$pin (1,infty)$とする凸最適化定式化の族を示す。 局所クラスタリングでは,入力種子の周囲の低コンダクタンスカットの発見に有用であることを示す。 提案手法は,pge 2$の強い局所実行時間で解き,合成グラフと実世界のグラフの両方で実験的な評価を行い,既存の手法とよく比較できることを示す。
  論文  参考訳（メタデータ） (2020-05-20T01:08:17Z)

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

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