論文の概要: MATA*: Combining Learnable Node Matching with A* Algorithm for
Approximate Graph Edit Distance Computation
- arxiv url: http://arxiv.org/abs/2311.02356v1
- Date: Sat, 4 Nov 2023 09:33:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-07 18:10:57.219159
- Title: MATA*: Combining Learnable Node Matching with A* Algorithm for
Approximate Graph Edit Distance Computation
- Title（参考訳）: mata*:近似グラフ編集距離計算のための学習ノードマッチングとa*アルゴリズムを組み合わせる
- Authors: Junfeng Liu, Min Zhou, Shuai Ma, Lujia Pan
- Abstract要約: 正確なグラフ編集距離(GED)計算はNP完全であることが知られている。
グラフニューラルネットワーク(GNN)とA*アルゴリズムに基づく近似GED計算のためのデータ駆動型ハイブリッドアプローチMATA*を提案する。
- 参考スコア（独自算出の注目度）: 12.437507185260577
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph Edit Distance (GED) is a general and domain-agnostic metric to measure
graph similarity, widely used in graph search or retrieving tasks. However, the
exact GED computation is known to be NP-complete. For instance, the widely used
A* algorithms explore the entire search space to find the optimal solution
which inevitably suffers scalability issues. Learning-based methods apply graph
representation techniques to learn the GED by formulating a regression task,
which can not recover the edit path and lead to inaccurate GED approximation
(i.e., the predicted GED is smaller than the exact). To this end, in this work,
we present a data-driven hybrid approach MATA* for approximate GED computation
based on Graph Neural Networks (GNNs) and A* algorithms, which models from the
perspective of learning to match nodes instead of directly regressing GED.
Specifically, aware of the structure-dominant operations (i.e.,node and edge
insertion/deletion) property in GED computation, a structure-enhanced GNN is
firstly designed to jointly learn local and high-order structural information
for node embeddings for node matchings. Second, top-k candidate nodes are
produced via a differentiable top-k operation to enable the training for node
matchings, which is adhering to another property of GED, i.e., multiple optimal
node matchings. Third, benefiting from the candidate nodes, MATA* only performs
on the promising search directions, reaching the solution efficiently. Finally,
extensive experiments show the superiority of MATA* as it significantly
outperforms the combinatorial search-based, learning-based and hybrid methods
and scales well to large-size graphs.
- Abstract（参考訳）: グラフ編集距離 (Graph Edit Distance, GED) は、グラフ検索や検索タスクで広く使われているグラフ類似度を測定する一般的な、および、ドメインに依存しない尺度である。
しかし、正確なGED計算はNP完全であることが知られている。
例えば、広く使われているA*アルゴリズムは、必然的にスケーラビリティに悩む最適なソリューションを見つけるために、検索空間全体を探索する。
学習ベースの手法は、回帰タスクを定式化してGEDを学習するためにグラフ表現技術を適用し、編集パスを復元できず、不正確なGED近似につながる(すなわち、予測されたGEDは正確なよりも小さい)。
そこで本研究では,グラフニューラルネットワーク(GNN)とA*アルゴリズムに基づくGEDの近似計算のためのデータ駆動型ハイブリッドアプローチMATA*を提案する。
具体的には、GED計算における構造支配的操作(ノードとエッジの挿入/削除)の性質を認識し、ノードマッチングのためのノード埋め込みのための局所および高次構造情報を共同で学習する構造強化GNNを設計する。
第2に、top-k候補ノードは微分可能なtop-k操作によって生成され、gedの他の特性、すなわち複数の最適ノードマッチングに準拠したノードマッチングのトレーニングを可能にする。
第3に、候補ノードの恩恵を受けたmata*は、有望な検索方向のみを実行し、効率的にソリューションに到達する。
最後に、MATA*は組合せ探索法、学習法、ハイブリッド法を著しく上回り、大規模グラフに匹敵するスケール性を示す。
関連論文リスト
- Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳（メタデータ） (2024-07-26T03:14:13Z) - Efficient Graph Similarity Computation with Alignment Regularization [7.143879014059894]
グラフ類似性計算(GSC)は、グラフニューラルネットワーク(GNN)を用いた学習に基づく予測タスクである。
適応正規化(AReg)と呼ばれる,シンプルながら強力な正規化技術によって,高品質な学習が達成可能であることを示す。
推論段階では、GNNエンコーダによって学習されたグラフレベル表現は、ARegを再度使用せずに直接類似度スコアを計算するために使用される。
論文 参考訳（メタデータ） (2024-06-21T07:37:28Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳（メタデータ） (2023-10-05T02:58:29Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - A Simple and Scalable Graph Neural Network for Large Directed Graphs [11.792826520370774]
入力グラフ内のノード表現とエッジ方向認識の様々な組み合わせについて検討する。
そこで本研究では,A2DUGを簡易かつ包括的に分類する手法を提案する。
我々は、A2DUGが様々なデータセットで安定して動作し、最先端の手法と比較して11.29まで精度が向上することを示した。
論文 参考訳（メタデータ） (2023-06-14T06:24:58Z) - Graph Entropy Guided Node Embedding Dimension Selection for Graph Neural
Networks [74.26734952400925]
ノード埋め込み次元選択(NEDS)のための最小グラフエントロピー(MinGE)アルゴリズムを提案する。
ミンゲは、グラフ上の特徴エントロピーと構造エントロピーの両方を考えており、それらはそれらのリッチな情報の特徴に従って慎重に設計されている。
ベンチマークデータセット上で人気のグラフニューラルネットワーク(GNN)を用いた実験は,提案したMinGEの有効性と一般化性を示す。
論文 参考訳（メタデータ） (2021-05-07T11:40:29Z) - Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
グラフニューラルネットワーク(GNN)は、グラフ構造化データを学習するためのパラメトリックモデルの一般的なクラスである。
最近の研究は、GNNが主に機能をスムースにするためにグラフを使用しており、ベンチマークタスクで競合する結果を示していると主張している。
本研究では、これらの結果が異種グラフに拡張可能かどうかを問うとともに、異なるエンティティ間の複数のタイプの関係を符号化する。
論文 参考訳（メタデータ） (2020-11-19T06:03:35Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳（メタデータ） (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。