論文の概要: Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching

• arxiv url: http://arxiv.org/abs/2201.11251v1
• Date: Tue, 25 Jan 2022 00:10:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-29 06:52:49.216659
• Title: Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching
• Title（参考訳）: 強化学習に基づく部分グラフマッチングのためのクエリ頂点順序付けモデル
• Authors: Hanchen Wang, Ying Zhang, Lu Qin, Wei Wang, Wenjie Zhang, Xuemin Lin
• Abstract要約: グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
• 参考スコア（独自算出の注目度）: 58.39970828272366
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Subgraph matching is a fundamental problem in various fields that use graph structured data. Subgraph matching algorithms enumerate all isomorphic embeddings of a query graph q in a data graph G. An important branch of matching algorithms exploit the backtracking search approach which recursively extends intermediate results following a matching order of query vertices. It has been shown that the matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In recent years, many advanced techniques for query vertex ordering (i.e., matching order generation) have been proposed to reduce the unpromising intermediate results according to the preset heuristic rules. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms. Instead of using the fixed heuristics to generate the matching order, our model could capture and make full use of the graph information, and thus determine the query vertex order with the adaptive learning-based rule that could significantly reduces the number of redundant enumerations. With the help of the reinforcement learning framework, our model is able to consider the long-term benefits rather than only consider the local information at current ordering step.Extensive experiments on six real-life data graphs demonstrate that our proposed matching order generation technique could reduce up to two orders of magnitude of query processing time compared to the state-of-the-art algorithms.
• Abstract（参考訳）: グラフ構造データを使用する様々な分野において,サブグラフマッチングは基本的な問題である。 データグラフGにおけるクエリグラフqのすべての同型埋め込みをサブグラフマッチングアルゴリズムで列挙する。マッチングアルゴリズムの重要な分岐は、クエリ頂点の整合順序に従って中間結果を再帰的に拡張するバックトラック検索アプローチを利用する。 これらのバックトラッキングに基づくサブグラフマッチングアルゴリズムの時間効率において、マッチング順序が重要な役割を果たすことが示されている。 近年、事前設定されたヒューリスティックルールに従って予測できない中間結果を減らすために、クエリ頂点順序付け(すなわち、一致順序生成)のための多くの高度な技術が提案されている。 本稿では,強化学習(rl)とグラフニューラルネットワーク(gnns)の手法を初めて適用し,サブグラフマッチングアルゴリズムの高品質マッチング順序を生成する。 一致順を生成するために固定ヒューリスティックスを使う代わりに、我々のモデルはグラフ情報をフル活用して、冗長列挙数を大幅に削減できる適応学習に基づく規則でクエリ頂点順序を決定することができる。 強化学習フレームワークの助けを借りて,現在の注文ステップにおける局所的な情報のみを考えるのではなく,長期的メリットを検討することができる。6つの実生活データグラフを用いた拡張実験により,提案手法が提案するマッチング順序生成手法が,最先端アルゴリズムと比較して最大2桁のクエリ処理時間を削減できることが示されている。

関連論文リスト

• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。 最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。 データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2024-03-11T06:34:05Z)
• ProvG-Searcher: A Graph Representation Learning Approach for Efficient Provenance Graph Search [13.627536649679577]
  ProvG-Searcherは,システムセキュリティログ内の既知のAPT動作を検出する新しい手法である。 グラフマッチング問題として前駆体グラフを探索するタスクを定式化し,グラフ表現学習法を用いる。 標準データセットに対する実験結果から,ProvG-Searcherはクエリの振る舞いを検出する精度が99%を超え,優れたパフォーマンスを実現していることが示された。
  論文  参考訳（メタデータ） (2023-09-07T11:29:01Z)
• Subgraph Matching via Query-Conditioned Subgraph Matching Neural Networks and Bi-Level Tree Search [33.9052190473029]
  サブグラフマッチングは、グラフデータベース検索、バイオメディカル分析、ソーシャルグループ検索などにおける中核的な操作である。 本稿では,クエリと対象グラフのマッチング情報を動的に計算する,新しいエンコーダ・デコーダニューラルネットワークアーキテクチャを提案する。 5つの大きな実世界のターゲットグラフの実験により、N-BLSはサブグラフマッチング性能を大幅に改善できることが示された。
  論文  参考訳（メタデータ） (2022-07-21T04:47:21Z)
• Sublinear Algorithms for Hierarchical Clustering [14.124026862687941]
  本稿では,3つの線形計算モデルに基づく大規模グラフの階層クラスタリングについて検討する。 すべてのモデルにおいて階層クラスタリングのためのサブ線形アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-06-15T16:25:27Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Effective and efficient structure learning with pruning and model averaging strategies [9.023722579074734]
  本稿では,2つの新しい手法と丘登り探索を組み合わせたBN構造学習アルゴリズムについて述べる。 アルゴリズムは探索空間グラフをプルーニングすることから始まり、プルーニング戦略をプルーニング戦略のアグレッシブバージョンと見なすことができる。 そして、ヒルクライミング探索プロセスで平均化を行い、目的関数を最大化する近隣グラフに移動する。
  論文  参考訳（メタデータ） (2021-12-01T10:35:34Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  本稿では,グラフマッチングを向上するための信頼度の高いグラフ構造を探索するために,GLAMという共用電子グラフ学習とマッチングネットワークを提案する。 提案手法は,3つの人気ビジュアルマッチングベンチマーク (Pascal VOC, Willow Object, SPair-71k) で評価される。 すべてのベンチマークにおいて、従来の最先端のグラフマッチング手法よりも大きなマージンを達成している。
  論文  参考訳（メタデータ） (2021-09-01T08:24:02Z)
• Second-Order Pooling for Graph Neural Networks [62.13156203025818]
  グラフプーリングとして2次プールを提案するが、これは上記の課題を自然に解決する。 グラフニューラルネットワークによる2次プールの直接利用は、実用的な問題を引き起こすことを示す。 本稿では,2次プールに基づく2つの新しいグローバルグラフプーリング手法,すなわちバイリニアマッピングと2次プールを提案する。
  論文  参考訳（メタデータ） (2020-07-20T20:52:36Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。