論文の概要: Graph Matching via Optimal Transport
- arxiv url: http://arxiv.org/abs/2111.05366v1
- Date: Tue, 9 Nov 2021 19:18:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-11 14:25:12.001413
- Title: Graph Matching via Optimal Transport
- Title(参考訳): 最適輸送によるグラフマッチング
- Authors: Ali Saad-Eldin, Benjamin D. Pedigo, Carey E. Priebe, Joshua T.
Vogelstein
- Abstract要約: グラフマッチング問題の解決は、運用研究、コンピュータビジョン、神経科学などへの応用により、ますます重要になっている。
現在の最先端のアルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は高い。
我々は,最新のグラフマッチングアルゴリズム "FAQ" (Vogelstein, 2015) を改良した GOAT を,その線形和割り当てステップを Cuturi (2013) の "Lightspeed Optimal Transport" メソッドに置き換える。
- 参考スコア(独自算出の注目度): 11.93151370164898
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The graph matching problem seeks to find an alignment between the nodes of
two graphs that minimizes the number of adjacency disagreements. Solving the
graph matching is increasingly important due to it's applications in operations
research, computer vision, neuroscience, and more. However, current
state-of-the-art algorithms are inefficient in matching very large graphs,
though they produce good accuracy. The main computational bottleneck of these
algorithms is the linear assignment problem, which must be solved at each
iteration. In this paper, we leverage the recent advances in the field of
optimal transport to replace the accepted use of linear assignment algorithms.
We present GOAT, a modification to the state-of-the-art graph matching
approximation algorithm "FAQ" (Vogelstein, 2015), replacing its linear sum
assignment step with the "Lightspeed Optimal Transport" method of Cuturi
(2013). The modification provides improvements to both speed and empirical
matching accuracy. The effectiveness of the approach is demonstrated in
matching graphs in simulated and real data examples.
- Abstract(参考訳): グラフマッチング問題は、隣接不一致の数を最小限に抑える2つのグラフのノード間のアライメントを求める。
グラフマッチングの解決は、オペレーションリサーチやコンピュータビジョン、神経科学などへの応用によって、ますます重要になっています。
しかし、現在の最先端アルゴリズムは、非常に大きなグラフのマッチングには非効率であるが、精度は良い。
これらのアルゴリズムの主な計算ボトルネックは線形割当問題であり、各イテレーションで解かなければならない。
本稿では,近年の最適移動の分野における進歩を活かし,線形割当てアルゴリズムの活用に取って代わる。
我々は,最先端グラフマッチング近似アルゴリズム "faq" (vogelstein, 2015) の改良として,その線形和割当てステップを cuturi (2013) の光速最適輸送法に置き換えた goat を提案する。
この修正は、スピードと経験的マッチングの精度を改善する。
このアプローチの有効性は、シミュレーションデータと実データ例のマッチンググラフで示される。
関連論文リスト
- Improved Exact and Heuristic Algorithms for Maximum Weight Clique [1.2074552857379273]
最大重量傾き問題の解法として,精度の向上とラベリングアルゴリズムを提案する。
提案アルゴリズムは, 局所グラフ構造を用いた新しいデータ削減規則を用いて, 成功した手法をインターリーブする。
我々は,アルゴリズムを合成および実世界のグラフで評価し,ほとんどの入力において,その技術の現状よりも優れていることを示す。
論文 参考訳(メタデータ) (2023-02-01T14:02:06Z) - CBAG: An Efficient Genetic Algorithm for the Graph Burning Problem [0.0]
グラフ燃焼問題の解法として,Centrality BAsed Genetic-algorithm (CBAG) という効率的な遺伝的アルゴリズムを提案する。
グラフバーニング問題の特徴を考慮し,新しい染色体表現法と評価法を提案する。
この結果から,提案アルゴリズムは従来の最先端の中央値と比較して性能が向上していることが明らかとなった。
論文 参考訳(メタデータ) (2022-08-01T17:34:07Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳(メタデータ) (2022-05-06T03:37:00Z) - FGOT: Graph Distances based on Filters and Optimal Transport [62.779521543654134]
グラフ比較は、グラフ間の類似点と相違点の識別を扱う。
大きな障害は、グラフの未知のアライメントと、正確で安価な比較指標の欠如である。
本研究では,フィルタグラフ距離近似を導入する。
論文 参考訳(メタデータ) (2021-09-09T17:43:07Z) - Learnable Graph Matching: Incorporating Graph Partitioning with Deep
Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。
既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。
そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文 参考訳(メタデータ) (2021-03-30T08:58:45Z) - Line Graph Neural Networks for Link Prediction [71.00689542259052]
実世界の多くのアプリケーションにおいて古典的なグラフ解析問題であるグラフリンク予測タスクについて検討する。
このフォーマリズムでは、リンク予測問題をグラフ分類タスクに変換する。
本稿では,線グラフをグラフ理論に用いて,根本的に異なる新しい経路を求めることを提案する。
特に、線グラフの各ノードは、元のグラフのユニークなエッジに対応するため、元のグラフのリンク予測問題は、グラフ分類タスクではなく、対応する線グラフのノード分類問題として等価に解決できる。
論文 参考訳(メタデータ) (2020-10-20T05:54:31Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳(メタデータ) (2020-06-24T11:37:33Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-03T20:37:05Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。