論文の概要: Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Learning

• arxiv url: http://arxiv.org/abs/2205.08115v1
• Date: Tue, 17 May 2022 06:26:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-18 13:54:15.187295
• Title: Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Learning
• Title（参考訳）: グラフ学習におけるgromov-wassersteinの高速収束アルゴリズム
• Authors: Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cho So, Jose Blanchet
• Abstract要約: 2つのアルゴリズム、Bregman Alternating Projected Gradient (BAPG) とハイブリッドBregman Proximal Gradient (hBPG) は(ほぼ)収束することが証明されている。 グラフアライメント,グラフ分割,形状マッチングなど,タスクのホスト上での手法の有効性を検証するための総合的な実験を行った。
• 参考スコア（独自算出の注目度）: 37.89640056739607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we study the design and analysis of a class of efficient algorithms for computing the Gromov-Wasserstein (GW) distance tailored to large-scale graph learning tasks. Armed with the Luo-Tseng error bound condition~\cite{luo1992error}, two proposed algorithms, called Bregman Alternating Projected Gradient (BAPG) and hybrid Bregman Proximal Gradient (hBPG) are proven to be (linearly) convergent. Upon task-specific properties, our analysis further provides novel theoretical insights to guide how to select the best fit method. As a result, we are able to provide comprehensive experiments to validate the effectiveness of our methods on a host of tasks, including graph alignment, graph partition, and shape matching. In terms of both wall-clock time and modeling performance, the proposed methods achieve state-of-the-art results.
• Abstract（参考訳）: 本稿では,大規模グラフ学習タスクに適応したgromov-wasserstein (gw) 距離を計算するための効率的なアルゴリズム群の設計と解析について検討する。 Luo-Tseng 誤差境界条件~\cite{luo 1992error} によって、Bregman Alternating Projected Gradient (BAPG) とハイブリッドBregman Proximal Gradient (hBPG) と呼ばれる2つのアルゴリズムが(ほぼ)収束することが証明されている。 さらに,タスク固有の特性から,最適な方法を選択する方法についての新たな理論的洞察を提供する。 その結果,グラフアライメント,グラフ分割,形状マッチングなど,タスクのホスト上での手法の有効性を検証するための総合的な実験が可能となった。 壁時計時間とモデリング性能の両面で,提案手法は最先端の結果を得る。

関連論文リスト

• Fast Semi-supervised Learning on Large Graphs: An Improved Green-function Method [93.04936336359502]
  グラフに基づく半教師付き学習において、グリーン関数法はグラフ空間におけるグリーン関数の計算によって機能する古典的な方法である。 そこで本研究では,最適化の観点から詳細な解析を行い,新しい手法を提案する。 従来の手法とは異なり,改良手法ではガウス除去法とアンコレッドグラフ法という2つの高速化手法を適用できる。
  論文  参考訳（メタデータ） (2024-11-04T04:27:18Z)
• Convergence Guarantees for the DeepWalk Embedding on Block Models [9.898607871253775]
  ブロックモデル(SBM)から得られたグラフ上でDeepWalkアルゴリズムの使い方を示す。 単純化されているにもかかわらず、SBMは大きなグラフ上のアルゴリズムを解析するための古典的なモデルであることが証明されている。
  論文  参考訳（メタデータ） (2024-10-26T18:35:11Z)
• Learning Heuristics for the Maximum Clique Enumeration Problem Using Low Dimensional Representations [0.0]
  本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。 本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。 分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
  論文  参考訳（メタデータ） (2022-10-30T22:04:32Z)
• CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
  グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。 グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。 この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
  論文  参考訳（メタデータ） (2022-08-01T17:34:07Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。 提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。 いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
  論文  参考訳（メタデータ） (2021-12-15T01:45:32Z)
• Effective and efficient structure learning with pruning and model averaging strategies [9.023722579074734]
  本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。 アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。 そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
  論文  参考訳（メタデータ） (2021-12-01T10:35:34Z)
• Graph Matching via Optimal Transport [11.93151370164898]
  グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。 現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。 我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
  論文  参考訳（メタデータ） (2021-11-09T19:18:18Z)
• Combinatorial Learning of Graph Edit Distance via Dynamic Embedding [108.49014907941891]
  本稿では,従来の検索手法による編集経路の解釈可能性を組み合わせたハイブリッド手法を提案する。 動的プログラミングにインスパイアされたノードレベルの埋め込みは、動的再利用方式で指定され、サブ最適分岐がプルーニングされることが推奨される。 異なるグラフデータセットを用いた実験結果から,A* の探索処理は精度を犠牲にすることなく極めて容易であることが示唆された。
  論文  参考訳（メタデータ） (2020-11-30T17:41:02Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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