論文の概要: Sub-GMN: The Subgraph Matching Network Model
- arxiv url: http://arxiv.org/abs/2104.00186v2
- Date: Fri, 2 Apr 2021 11:52:02 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 10:28:07.911691
- Title: Sub-GMN: The Subgraph Matching Network Model
- Title（参考訳）: Sub-GMN:Subgraph Matching Network Model
- Authors: Zixun Lan, Limin Yu, Linglong Yuan, Zili Wu, Fei Ma
- Abstract要約: 本研究ではサブグラフマッチングネットワーク(Sub-GMN)と呼ばれるサブグラフマッチングタスクのエンドツーエンド学習に基づく近似手法を提案する。
提案したSub-GMNはまずグラフ表現学習を用いてノードをノードレベルの埋め込みにマッピングする。
次に、メトリクス学習と注意メカニズムを組み合わせて、データグラフとクエリグラフの一致するノード間の関係をモデル化します。
- 参考スコア（独自算出の注目度）: 4.879819291429471
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As one of the most fundamental tasks in graph theory, subgraph matching is a
crucial task in many fields, ranging from information retrieval, computer
vision, biology, chemistry and natural language processing. Yet subgraph
matching problem remains to be an NP-complete problem. This study proposes an
end-to-end learning-based approximate method for subgraph matching task, called
subgraph matching network (Sub-GMN). The proposed Sub-GMN firstly uses graph
representation learning to map nodes to node-level embedding. It then combines
metric learning and attention mechanisms to model the relationship between
matched nodes in the data graph and query graph. To test the performance of the
proposed method, we applied our method on two databases. We used two existing
methods, GNN and FGNN as baseline for comparison. Our experiment shows that, on
dataset 1, on average the accuracy of Sub-GMN are 12.21\% and 3.2\% higher than
that of GNN and FGNN respectively. On average running time Sub-GMN runs 20-40
times faster than FGNN. In addition, the average F1-score of Sub-GMN on all
experiments with dataset 2 reached 0.95, which demonstrates that Sub-GMN
outputs more correct node-to-node matches.
Comparing with the previous GNNs-based methods for subgraph matching task,
our proposed Sub-GMN allows varying query and data graphes in the
test/application stage, while most previous GNNs-based methods can only find a
matched subgraph in the data graph during the test/application for the same
query graph used in the training stage. Another advantage of our proposed
Sub-GMN is that it can output a list of node-to-node matches, while most
existing end-to-end GNNs based methods cannot provide the matched node pairs.
- Abstract（参考訳）: グラフ理論における最も基本的なタスクの1つとして、サブグラフマッチングは情報検索、コンピュータビジョン、生物学、化学、自然言語処理など、多くの分野において重要なタスクである。
しかし、部分グラフマッチング問題はNP完全問題である。
本研究では,エンド・ツー・エンド学習に基づくサブグラフマッチングタスクの近似手法であるsubgraph matching network (sub-gmn)を提案する。
提案したSub-GMNはまずグラフ表現学習を用いてノードをノードレベルの埋め込みにマッピングする。
次に、メトリック学習とアテンションメカニズムを組み合わせて、データグラフとクエリグラフの一致したノード間の関係をモデル化する。
提案手法の性能を検証するため,本手法を2つのデータベースに適用した。
比較基準としてGNNとFGNNの2つの既存手法を用いた。
実験の結果、データセット1では、サブGMNの精度は、それぞれGNNとFGNNの精度よりも12.21\%と3.2\%高いことがわかった。
平均走行時間では、Sub-GMNはFGNNの20～40倍高速である。
さらに、データセット2の全ての実験におけるSub-GMNの平均F1スコアは0.95に達し、Sub-GMNはより正確なノード間一致を出力することを示した。
提案したSub-GMNは,従来のGNNのサブグラフマッチングタスクと比較して,テスト/アプリケーション段階でのクエリやデータグラフの変化が可能であるのに対して,従来のGNNのほとんどのメソッドでは,トレーニング段階で使用されるのと同じクエリグラフのテスト/アプリケーション中にのみ一致するサブグラフを見つけることができる。
提案したSub-GMNのもう1つの利点は、ノード間一致のリストを出力できることである。
関連論文リスト
- Diffusing to the Top: Boost Graph Neural Networks with Minimal Hyperparameter Tuning [33.948899558876604]
グラフ条件付き潜在拡散フレームワーク(GNN-Diff)を導入し,高性能なGNNを生成する。
提案手法は,小,大,長距離グラフ上のノード分類とリンク予測という4つのグラフタスクを対象とした166の実験を通じて検証する。
論文 参考訳（メタデータ） (2024-10-08T05:27:34Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
本稿では,シーケンシャルノード表現,すなわちSeq-HGNNを用いた新しい異種グラフニューラルネットワークを提案する。
Heterogeneous Graph Benchmark (HGB) と Open Graph Benchmark (OGB) の4つの広く使われているデータセットについて広範な実験を行った。
論文 参考訳（メタデータ） (2023-05-18T07:27:18Z) - A Robust Stacking Framework for Training Deep Graph Models with
Multifaceted Node Features [61.92791503017341]
数値ノード特徴とグラフ構造を入力とするグラフニューラルネットワーク(GNN)は,グラフデータを用いた各種教師付き学習タスクにおいて,優れた性能を示した。
IID(non-graph)データをGNNに簡単に組み込むことはできない。
本稿では、グラフ認識の伝播をIDデータに意図した任意のモデルで融合するロバストな積み重ねフレームワークを提案する。
論文 参考訳（メタデータ） (2022-06-16T22:46:33Z) - Graph Pointer Neural Networks [11.656981519694218]
上述の課題に対処するために,グラフポインタニューラルネットワーク(GPNN)を提案する。
我々は、多数のマルチホップ地区から最も関連性の高いノードを選択するためにポインタネットワークを利用する。
GPNNは最先端手法の分類性能を著しく向上させる。
論文 参考訳（メタデータ） (2021-10-03T10:18:25Z) - On Local Aggregation in Heterophilic Graphs [11.100606980915144]
我々は,従来のGNNと多層パーセプトロンを適切に調整した手法が,ヘテロ親和性グラフ上の最近の長距離アグリゲーション手法の精度に適合しているか,あるいは超越しているかを示す。
本稿では,新しい情報理論グラフ計量であるNativeborhood Information Content(NIC)メトリックを提案する。
論文 参考訳（メタデータ） (2021-06-06T19:12:31Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳（メタデータ） (2020-07-03T09:30:07Z) - Towards Deeper Graph Neural Networks with Differentiable Group
Normalization [61.20639338417576]
グラフニューラルネットワーク(GNN)は、隣接するノードを集約することでノードの表現を学習する。
オーバースムーシングは、レイヤーの数が増えるにつれてGNNのパフォーマンスが制限される重要な問題のひとつです。
2つのオーバースムースなメトリクスと新しいテクニック、すなわち微分可能群正規化(DGN)を導入する。
論文 参考訳（メタデータ） (2020-06-12T07:18:02Z) - Graph Sequential Network for Reasoning over Sequences [38.766982479196926]
シーケンスから構築されたグラフよりも推論が必要な場合を考える。
既存のGNNモデルは、まずノード列を固定次元ベクトルに要約し、次にこれらのベクトルにGNNを適用することで、この目標を達成する。
本稿では,グラフシーケンスネットワーク(GSN)と呼ばれる新しいタイプのGNNを提案する。
論文 参考訳（メタデータ） (2020-04-04T19:18:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。