論文の概要: Combinatorial Learning of Graph Edit Distance via Dynamic Embedding
- arxiv url: http://arxiv.org/abs/2011.15039v2
- Date: Tue, 1 Dec 2020 02:05:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-06 14:40:18.869889
- Title: Combinatorial Learning of Graph Edit Distance via Dynamic Embedding
- Title(参考訳): 動的埋め込みによるグラフ編集距離の組合せ学習
- Authors: Runzhong Wang, Tianqi Zhang, Tianshu Yu, Junchi Yan, Xiaokang Yang
- Abstract要約: 本稿では,従来の検索手法による編集経路の解釈可能性を組み合わせたハイブリッド手法を提案する。
動的プログラミングにインスパイアされたノードレベルの埋め込みは、動的再利用方式で指定され、サブ最適分岐がプルーニングされることが推奨される。
異なるグラフデータセットを用いた実験結果から,A* の探索処理は精度を犠牲にすることなく極めて容易であることが示唆された。
- 参考スコア(独自算出の注目度): 108.49014907941891
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Edit Distance (GED) is a popular similarity measurement for pairwise
graphs and it also refers to the recovery of the edit path from the source
graph to the target graph. Traditional A* algorithm suffers scalability issues
due to its exhaustive nature, whose search heuristics heavily rely on human
prior knowledge. This paper presents a hybrid approach by combing the
interpretability of traditional search-based techniques for producing the edit
path, as well as the efficiency and adaptivity of deep embedding models to
achieve a cost-effective GED solver. Inspired by dynamic programming,
node-level embedding is designated in a dynamic reuse fashion and suboptimal
branches are encouraged to be pruned. To this end, our method can be readily
integrated into A* procedure in a dynamic fashion, as well as significantly
reduce the computational burden with a learned heuristic. Experimental results
on different graph datasets show that our approach can remarkably ease the
search process of A* without sacrificing much accuracy. To our best knowledge,
this work is also the first deep learning-based GED method for recovering the
edit path.
- Abstract(参考訳): グラフ編集距離 (Graph Edit Distance, GED) は、ペアグラフの類似度測定として人気があり、ソースグラフからターゲットグラフへの編集パスの回復も指している。
従来のa*アルゴリズムは、探索ヒューリスティックが人間の事前知識に大きく依存しているため、拡張性の問題に苦しんでいる。
本稿では,従来の検索に基づく編集パス作成手法の解釈可能性と,コスト効率の高いgedソルバを実現するための深層埋め込みモデルの効率と適応性を組み合わせたハイブリッド手法を提案する。
動的プログラミングにインスパイアされたノードレベルの埋め込みは、動的再利用方式で指定され、サブ最適分岐がプルーニングされる。
この目的のために,本手法は動的にA*プロシージャに容易に組み込むことができ,学習ヒューリスティックによる計算負担を大幅に削減することができる。
異なるグラフデータセットを用いた実験結果から,A* の探索処理は精度を犠牲にすることなく極めて容易であることがわかった。
我々の知る限りでは、この研究は編集パスを復元する最初のディープラーニングベースのGED手法でもある。
関連論文リスト
- GALA: Graph Diffusion-based Alignment with Jigsaw for Source-free Domain Adaptation [13.317620250521124]
ソースコードのないドメイン適応は、現実世界で多くのアプリケーションを含むため、重要な機械学習トピックである。
最近のグラフニューラルネットワーク(GNN)アプローチは、ドメインシフトとラベルの不足により、パフォーマンスが著しく低下する可能性がある。
本稿では, ソースフリーなグラフドメイン適応に適した Jigsaw (GALA) を用いたグラフ拡散に基づくアライメント法を提案する。
論文 参考訳(メタデータ) (2024-10-22T01:32:46Z) - EggNet: An Evolving Graph-based Graph Attention Network for Particle Track Reconstruction [0.0]
我々は,一組のヒットから粒子トラックを直接再構成するワンショットOCアプローチを検討する。
このアプローチは、グラフを反復的に更新し、各グラフを横断するメッセージをより容易にする。
TrackMLデータセットに関する予備研究は、固定された入力グラフを必要とする方法と比較して、トラック性能が向上したことを示している。
論文 参考訳(メタデータ) (2024-07-18T22:29:24Z) - Preserving Node Distinctness in Graph Autoencoders via Similarity Distillation [9.395697548237333]
グラフオートエンコーダ(GAE)は、平均二乗誤差(MSE)のような距離ベースの基準に依存して入力グラフを再構築する。
単一の再構築基準にのみ依存すると 再建されたグラフの 特徴が失われる可能性がある
我々は,再構成されたグラフにおいて,必要な相違性を維持するための簡易かつ効果的な戦略を開発した。
論文 参考訳(メタデータ) (2024-06-25T12:54:35Z) - MATA*: Combining Learnable Node Matching with A* Algorithm for
Approximate Graph Edit Distance Computation [12.437507185260577]
正確なグラフ編集距離(GED)計算はNP完全であることが知られている。
グラフニューラルネットワーク(GNN)とA*アルゴリズムに基づく近似GED計算のためのデータ駆動型ハイブリッドアプローチMATA*を提案する。
論文 参考訳(メタデータ) (2023-11-04T09:33:08Z) - Efficient Dynamic Graph Representation Learning at Scale [66.62859857734104]
本稿では,学習損失による時間依存性を選択的に表現し,計算の並列性を改善するための効率的な動的グラフ lEarning (EDGE) を提案する。
EDGEは、数百万のノードと数億の時間的イベントを持つ動的グラフにスケールでき、新しい最先端(SOTA)パフォーマンスを実現することができる。
論文 参考訳(メタデータ) (2021-12-14T22:24:53Z) - Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
動的グラフ変換器 (DGT) を用いた動的グラフ学習手法を提案する。
DGTは、グラフトポロジを効果的に学習し、暗黙のリンクをキャプチャするための時空間符号化を持つ。
DGTはいくつかの最先端のベースラインと比較して優れた性能を示す。
論文 参考訳(メタデータ) (2021-11-19T21:44:23Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳(メタデータ) (2021-06-09T09:18:18Z) - 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) - Deep Reinforcement Learning of Graph Matching [63.469961545293756]
ノードとペアの制約下でのグラフマッチング(GM)は、最適化からコンピュータビジョンまでの領域におけるビルディングブロックである。
GMのための強化学習ソルバを提案する。
rgmはペアワイズグラフ間のノード対応を求める。
本手法は,フロントエンドの特徴抽出と親和性関数学習に焦点をあてるという意味において,従来のディープグラフマッチングモデルと異なる。
論文 参考訳(メタデータ) (2020-12-16T13:48:48Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳(メタデータ) (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。