論文の概要: GLSearch: Maximum Common Subgraph Detection via Learning to Search

• arxiv url: http://arxiv.org/abs/2002.03129v3
• Date: Wed, 12 May 2021 17:12:33 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 22:38:42.200109
• Title: GLSearch: Maximum Common Subgraph Detection via Learning to Search
• Title（参考訳）: glsearch: 検索への学習による最大共通サブグラフ検出
• Authors: Yunsheng Bai, Derek Xu, Yizhou Sun, Wei Wang
• Abstract要約: 検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。 このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。 我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
• 参考スコア（独自算出の注目度）: 33.9052190473029
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Detecting the Maximum Common Subgraph (MCS) between two input graphs is fundamental for applications in drug synthesis, malware detection, cloud computing, etc. However, MCS computation is NP-hard, and state-of-the-art MCS solvers rely on heuristic search algorithms which in practice cannot find good solution for large graph pairs given a limited computation budget. We propose GLSearch, a Graph Neural Network (GNN) based learning to search model. Our model is built upon the branch and bound algorithm, which selects one pair of nodes from the two input graphs to expand at a time. Instead of using heuristics, we propose a novel GNN-based Deep Q-Network (DQN) to select the node pair, allowing the search process faster and more adaptive. To further enhance the training of DQN, we leverage the search process to provide supervision in a pre-training stage and guide our agent during an imitation learning stage. Experiments on synthetic and real-world large graph pairs demonstrate that our model learns a search strategy that is able to detect significantly larger common subgraphs given the same computation budget. Our GLSearch can be potentially extended to solve many other combinatorial problems with constraints on graphs.
• Abstract（参考訳）: 2つの入力グラフ間の最大共通部分グラフ(MCS)の検出は、薬物合成、マルウェア検出、クラウドコンピューティング等における応用に不可欠である。 しかし、MCS計算はNPハードであり、最先端のMCS解法はヒューリスティック検索アルゴリズムに依存しており、計算予算が限られているため、実際には大きなグラフ対に対して良い解を見つけることができない。 検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習であるGLSearchを提案する。 我々のモデルは分岐・バウンドアルゴリズムに基づいており、2つの入力グラフから1対のノードを選択して一度に拡大する。 ヒューリスティックスの代わりに,ノードペアを選択するための新しいGNNベースのディープQ-ネットワーク(DQN)を提案する。 DQNの訓練をさらに強化するために,我々は,DQNの探索プロセスを活用し,事前学習段階における指導と模倣学習段階におけるエージェントの指導を行う。 合成および実世界の大規模グラフペア実験により,同じ計算予算で非常に大きな共通部分グラフを検出可能な探索戦略を学習できることが証明された。 我々のGLSearchは、グラフ上の制約で他の多くの組合せ問題を解くために拡張できる可能性がある。

関連論文リスト

• Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
  NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。 AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
  論文  参考訳（メタデータ） (2024-06-05T02:43:41Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。 まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。 次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
  論文  参考訳（メタデータ） (2023-08-03T07:00:04Z)
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
  グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。 グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。 低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
  論文  参考訳（メタデータ） (2023-03-10T21:18:34Z)
• Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
  まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。 我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
  論文  参考訳（メタデータ） (2022-11-26T00:01: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)
• 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)
• 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)
• DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks [45.075163625895286]
  我々はメタグラフを探索し、メタパスよりも複雑なセマンティック関係をキャプチャし、グラフニューラルネットワークが異なるタイプのエッジに沿ってメッセージを伝播する方法を決定する。 我々は、HINの候補メタグラフを表すために、有向非巡回グラフ(DAG)の形式で表現型検索空間を設計する。 本稿では,1回のGNNトレーニングに匹敵する検索コストを1対1に抑えるための,新しい効率的な探索アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-07T08:09:29Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。 GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。 より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。 本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
  論文  参考訳（メタデータ） (2020-08-31T23:15:40Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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