論文の概要: Subgraph Matching via Query-Conditioned Subgraph Matching Neural
Networks and Bi-Level Tree Search
- arxiv url: http://arxiv.org/abs/2207.10305v1
- Date: Thu, 21 Jul 2022 04:47:21 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-22 13:33:25.234364
- Title: Subgraph Matching via Query-Conditioned Subgraph Matching Neural
Networks and Bi-Level Tree Search
- Title（参考訳）: 問合せ付き部分グラフマッチングニューラルネットワークと二レベル木探索による部分グラフマッチング
- Authors: Yunsheng Bai, Derek Xu, Yizhou Sun, Wei Wang
- Abstract要約: サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。
本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。
5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
- 参考スコア（独自算出の注目度）: 33.9052190473029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recent advances have shown the success of using reinforcement learning and
search to solve NP-hard graph-related tasks, such as Traveling Salesman
Optimization, Graph Edit Distance computation, etc. However, it remains unclear
how one can efficiently and accurately detect the occurrences of a small query
graph in a large target graph, which is a core operation in graph database
search, biomedical analysis, social group finding, etc. This task is called
Subgraph Matching which essentially performs subgraph isomorphism check between
a query graph and a large target graph. One promising approach to this
classical problem is the "learning-to-search" paradigm, where a reinforcement
learning (RL) agent is designed with a learned policy to guide a search
algorithm to quickly find the solution without any solved instances for
supervision. However, for the specific task of Subgraph Matching, though the
query graph is usually small given by the user as input, the target graph is
often orders-of-magnitude larger. It poses challenges to the neural network
design and can lead to solution and reward sparsity. In this paper, we propose
N-BLS with two innovations to tackle the challenges: (1) A novel
encoder-decoder neural network architecture to dynamically compute the matching
information between the query and the target graphs at each search state; (2) A
Monte Carlo Tree Search enhanced bi-level search framework for training the
policy and value networks. Experiments on five large real-world target graphs
show that N-BLS can significantly improve the subgraph matching performance.
- Abstract（参考訳）: 近年の進歩は、トラベリングセールスマン最適化やグラフ編集距離計算など、NPハードなグラフ関連課題を解決するために強化学習と検索が成功していることを示している。
しかし, グラフデータベース検索, バイオメディカル分析, ソーシャルグループ検索などのコア操作である, 大規模ターゲットグラフにおける小クエリグラフの発生を, 効率よく, 正確に検出する方法については, いまだに不明である。
このタスクはサブグラフマッチングと呼ばれ、クエリグラフと大きなターゲットグラフの間のサブグラフ同型チェックを実行する。
この古典的な問題の1つの有望なアプローチは「学習と探索」のパラダイムであり、強化学習(RL)エージェントは学習ポリシーで設計され、探索アルゴリズムを誘導し、解決されたインスタンスを監督せずに迅速に解を見つける。
しかし、サブグラフマッチングの特定のタスクでは、通常、クエリグラフはユーザが入力として与える割合は小さいが、ターゲットグラフは、しばしば桁違いに大きい。
ニューラルネットワーク設計に課題を提起し、ソリューションと報酬の分散につながる可能性がある。
本稿では,(1)クエリと対象グラフ間のマッチング情報を動的に計算する新しいエンコーダ・デコーダニューラルネットワークアーキテクチャ,(2)ポリシーと価値ネットワークをトレーニングするための2段階検索フレームワークを改良したモンテカルロ木探索を提案する。
5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
関連論文リスト
- SPGNN: Recognizing Salient Subgraph Patterns via Enhanced Graph Convolution and Pooling [25.555741218526464]
グラフニューラルネットワーク(GNN)は、グラフやネットワークのような非ユークリッドデータ上での機械学習の分野に革命をもたらした。
本稿では,ノード表現をインジェクティブに更新する結合型グラフ畳み込み機構を提案する。
また,WL-SortPoolと呼ばれるグラフプーリングモジュールを設計し,重要なサブグラフパターンをディープラーニングで学習する。
論文 参考訳（メタデータ） (2024-04-21T13:11:59Z) - Learning to Count Isomorphisms with Graph Neural Networks [16.455234748896157]
グラフ上の部分グラフ同型カウントは重要な問題である。
本稿では,グラフアイソモーフィズムカウントのための新しいグラフニューラルネットワークであるCount-GNNを提案する。
論文 参考訳（メタデータ） (2023-02-07T05:32:11Z) - Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。
これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。
4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文 参考訳（メタデータ） (2022-05-31T10:38:04Z) - Arch-Graph: Acyclic Architecture Relation Predictor for
Task-Transferable Neural Architecture Search [96.31315520244605]
Arch-Graphはタスク固有の最適アーキテクチャを予測するトランスファー可能なNASメソッドである。
Arch-Graphの転送性と,多数のタスクにわたる高いサンプル効率を示す。
わずか50モデルの予算の下で、2つの検索スペースで平均して0.16%と0.29%のアーキテクチャを見つけることができる。
論文 参考訳（メタデータ） (2022-04-12T16:46:06Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳（メタデータ） (2022-03-03T09:53:53Z) - Interactive Visual Pattern Search on Graph Data via Graph Representation
Learning [20.795511688640296]
視覚分析システムGraphQは、ループ内、サンプルベース、サブグラフパターン検索をサポートする。
高速で対話的なクエリをサポートするために、グラフニューラルネットワーク(GNN)を使用して、グラフを固定長潜在ベクトル表現としてエンコードする。
また,NuroAlignと呼ばれるノードアライメントのための新しいGNNを提案し,クエリ結果の検証と解釈を容易にする。
論文 参考訳（メタデータ） (2022-02-18T22:30:28Z) - Reinforcement Learning Based Query Vertex Ordering Model for Subgraph
Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。
マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。
本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文 参考訳（メタデータ） (2022-01-25T00:10:03Z) - Second-Order Pooling for Graph Neural Networks [62.13156203025818]
グラフプーリングとして2次プールを提案するが、これは上記の課題を自然に解決する。
グラフニューラルネットワークによる2次プールの直接利用は、実用的な問題を引き起こすことを示す。
本稿では,2次プールに基づく2つの新しいグローバルグラフプーリング手法,すなわちバイリニアマッピングと2次プールを提案する。
論文 参考訳（メタデータ） (2020-07-20T20:52:36Z) - Neural Subgraph Matching [57.05893848555512]
NeuroMatchは、サブグラフマッチングに対する正確で効率的で堅牢な神経アプローチである。
NeuroMatchは、既存の幾何学的アプローチよりも100倍高速で、既存のサブグラフマッチング手法よりも18%精度が高い。
論文 参考訳（メタデータ） (2020-07-06T22:06:38Z) - GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。
このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。
我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文 参考訳（メタデータ） (2020-02-08T10:03:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。