論文の概要: $p$-Norm Flow Diffusion for Local Graph Clustering

• arxiv url: http://arxiv.org/abs/2005.09810v3
• Date: Mon, 20 Jul 2020 09:09:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-01 05:16:04.663623
• Title: $p$-Norm Flow Diffusion for Local Graph Clustering
• Title（参考訳）: 局所グラフクラスタリングのための$p$-norm Flow Diffusion
• Authors: Kimon Fountoulakis, Di Wang, Shenghao Yang
• Abstract要約: 我々は、p-ノルムネットワークフローとの拡散を$pin (1,infty)$とする凸最適化定式化の族を示す。 局所クラスタリングでは,入力種子の周囲の低コンダクタンスカットの発見に有用であることを示す。 提案手法は,pge 2$の強い局所実行時間で解き,合成グラフと実世界のグラフの両方で実験的な評価を行い,既存の手法とよく比較できることを示す。
• 参考スコア（独自算出の注目度）: 18.90840167452118
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Local graph clustering and the closely related seed set expansion problem are primitives on graphs that are central to a wide range of analytic and learning tasks such as local clustering, community detection, nodes ranking and feature inference. Prior work on local graph clustering mostly falls into two categories with numerical and combinatorial roots respectively. In this work, we draw inspiration from both fields and propose a family of convex optimization formulations based on the idea of diffusion with p-norm network flow for $p\in (1,\infty)$. In the context of local clustering, we characterize the optimal solutions for these optimization problems and show their usefulness in finding low conductance cuts around input seed set. In particular, we achieve quadratic approximation of conductance in the case of $p=2$ similar to the Cheeger-type bounds of spectral methods, constant factor approximation when $p\rightarrow\infty$ similar to max-flow based methods, and a smooth transition for general $p$ values in between. Thus, our optimization formulation can be viewed as bridging the numerical and combinatorial approaches, and we can achieve the best of both worlds in terms of speed and noise robustness. We show that the proposed problem can be solved in strongly local running time for $p\ge 2$ and conduct empirical evaluations on both synthetic and real-world graphs to illustrate our approach compares favorably with existing methods.
• Abstract（参考訳）: ローカルグラフクラスタリングと密接に関連するシードセット拡張問題は、ローカルクラスタリング、コミュニティ検出、ノードランキング、特徴推論など、幅広い分析および学習タスクの中心となるグラフ上のプリミティブである。 局所グラフクラスタリングの先行研究は、それぞれ数値と組合せの根を持つ2つのカテゴリに分類される。 本研究では,両分野から着想を得て,p-ノルムネットワークフローを用いた拡散の考え方に基づく凸最適化の一群を,$p\in (1,\infty)$で提案する。 局所クラスタリングの文脈において,これらの最適化問題に対する最適解を特徴付け,入力シード集合周辺の低コンダクタンスカットを求める際に有用性を示す。 特に、スペクトル法のチーガー型境界に類似した$p=2$の場合のコンダクタンスの2次近似、最大フロー法に類似した$p\rightarrow\infty$の定数係数近似、および一般の$p$値に対する滑らかな遷移を達成する。 したがって,この最適化定式化は数値的手法と組合せ的手法の橋渡しと見なすことができ,速度と雑音のロバスト性の観点から両世界のベストを実現できる。 提案手法は,p\ge 2$に対して強い局所実行時間で解くことができ,実世界のグラフと合成グラフの双方で実験的な評価を行い,既存の手法とよく比較できることを示す。

関連論文リスト

• Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings [7.6275971668447005]
  消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。 本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。 さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
  論文  参考訳（メタデータ） (2024-02-22T05:48:54Z)
• Faster Convergence with Multiway Preferences [99.68922143784306]
  本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。 本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
  論文  参考訳（メタデータ） (2023-12-19T01:52:13Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Pick your Neighbor: Local Gauss-Southwell Rule for Fast Asynchronous Decentralized Optimization [37.85806148420504]
  分散最適化環境では、$n$最適化ノードのネットワーク内の各エージェント$i$は、プライベート関数$f_i$を持つ。 最適化対応の選択ルールを導入し、高い2倍のコスト改善で隣人を選択する。 提案したセットワイズGSルールは,ネットワークの最大次数による高速化を実現する。
  論文  参考訳（メタデータ） (2022-07-15T15:37:03Z)
• $\ell_2$-norm Flow Diffusion in Near-Linear Time [18.263667346853698]
  我々は$ell$-normフロー拡散問題に対して$widetildeO(m)$-timeランダム化アルゴリズムを提供する。 これは単純に双対解ベクトルを網羅することによって実現される。 Laplacianシステムソルバの高レベルなアルゴリズムフレームワークに適応するが、いくつかの新しいツールが必要である。
  論文  参考訳（メタデータ） (2021-05-30T21:27:58Z)
• Laplace Matching for fast Approximate Inference in Generalized Linear Models [27.70274403550477]
  本論文では,高い近似品質を実現しつつ,計算的に安価に設計した近似推論フレームワークを提案する。 我々が emphLaplace Matching と呼ぶこの概念は、指数群のパラメータ空間間の閉形式、近似、双方向変換を含む。 これにより、GLMにおける推論を(小さな近似誤差で)共役推論に変換する。
  論文  参考訳（メタデータ） (2021-05-07T08:25:17Z)
• The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communication [61.60069865891783]
  間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。 本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
  論文  参考訳（メタデータ） (2021-02-02T16:18:29Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  局所グラフクラスタリングのためのネットワークLasso法の統計的および計算的性質について検討する。 nLassoによって提供されるクラスタは、クラスタ境界とシードノードの間のネットワークフローを通じて、エレガントに特徴付けられる。
  論文  参考訳（メタデータ） (2020-04-25T17:52:05Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  直交群 $O(d)$ 上の幾何駆動最適化アルゴリズムの新しいクラスを示す。 提案手法は,深層,畳み込み,反復的なニューラルネットワーク,強化学習,フロー,メトリック学習など,機械学習のさまざまな分野に適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-30T15:37:50Z)
• Optimization of Graph Total Variation via Active-Set-based Combinatorial Reconditioning [48.42916680063503]
  本稿では,この問題クラスにおける近位アルゴリズムの適応型事前条件付け手法を提案する。 不活性エッジのネスト・フォレスト分解により局所収束速度が保証されることを示す。 この結果から,局所収束解析は近似アルゴリズムにおける可変指標選択の指針となることが示唆された。
  論文  参考訳（メタデータ） (2020-02-27T16:33:09Z)

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

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