論文の概要: Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2603.18314v1
• Date: Wed, 18 Mar 2026 21:53:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-20 17:19:05.862749
• Title: Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning
• Title（参考訳）: ニューラルグラフ表現と強化学習を用いた近似部分グラフマッチング
• Authors: Kaiyang Li, Shihao Ji, Zhipeng Cai, Wei Li,
• Abstract要約: 本稿では,強化学習に基づく近似部分グラフマッチング(RL-ASM)アルゴリズムを提案する。 このモデルでは,2つの入力グラフから1対のノードを1対選択し,潜在的なマッチングを行うアルゴリズムを構築している。 合成データセットと実世界のデータセットの両方の実験により、我々のRL-ASMは、有効性と効率の点で既存の手法よりも優れていることが示された。
• 参考スコア（独自算出の注目度）: 15.3743761404157
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate subgraph matching (ASM) is a task that determines the approximate presence of a given query graph in a large target graph. Being an NP-hard problem, ASM is critical in graph analysis with a myriad of applications ranging from database systems and network science to biochemistry and privacy. Existing techniques often employ heuristic search strategies, which cannot fully utilize the graph information, leading to sub-optimal solutions. This paper proposes a Reinforcement Learning based Approximate Subgraph Matching (RL-ASM) algorithm that exploits graph transformers to effectively extract graph representations and RL-based policies for ASM. Our model is built upon the branch-and-bound algorithm that selects one pair of nodes from the two input graphs at a time for potential matches. Instead of using heuristics, we exploit a Graph Transformer architecture to extract feature representations that encode the full graph information. To enhance the training of the RL policy, we use supervised signals to guide our agent in an imitation learning stage. Subsequently, the policy is fine-tuned with the Proximal Policy Optimization (PPO) that optimizes the accumulative long-term rewards over episodes. Extensive experiments on both synthetic and real-world datasets demonstrate that our RL-ASM outperforms existing methods in terms of effectiveness and efficiency. Our source code is available at https://github.com/KaiyangLi1992/RL-ASM.
• Abstract（参考訳）: 近似部分グラフマッチング(英: Approximate subgraph matching, ASM)は、与えられたクエリグラフが大きなターゲットグラフに存在するかどうかを決定するタスクである。 NP-hard問題であるASMは、データベースシステムやネットワーク科学、生化学、プライバシーなど、無数のアプリケーションでグラフ解析に欠かせない問題である。 既存の手法では、しばしばヒューリスティックな探索戦略を採用しており、グラフ情報を十分に活用できないため、準最適解が導かれる。 本稿では,グラフ変換器を利用した強化学習に基づく近似部分グラフマッチング(RL-ASM)アルゴリズムを提案する。 このモデルでは,2つの入力グラフから1対のノードを1対選択し,潜在的なマッチングを行うアルゴリズムを構築している。 ヒューリスティックスを使う代わりに、グラフトランスフォーマーアーキテクチャを使用して、全グラフ情報をエンコードする特徴表現を抽出する。 RLポリシーのトレーニングを強化するために、エージェントを模倣学習段階に誘導するために教師付き信号を使用する。 その後、ポリシーは、エピソードに対する累積的な長期報酬を最適化するPPO(Proximal Policy Optimization)によって微調整される。 我々のRL-ASMは、実世界のデータセットと実世界のデータセットの両方で大規模な実験を行い、有効性と効率の点で既存の手法よりも優れていることを示した。 ソースコードはhttps://github.com/KaiyangLi 1992/RL-ASMで公開されています。

関連論文リスト

• Graph-GRPO: Training Graph Flow Models with Reinforcement Learning [14.937302684130257]
  グラフフローモデル(GFM)を学習するためのオンライン強化学習フレームワークであるGraph-GRPOを提案する。 わずか50ステップで95.0%と97.5%のValid-Unique-Noveltyスコアが得られた。
  論文  参考訳（メタデータ） (2026-03-11T04:20:45Z)
• Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignment [38.485929062532925]
  本稿では,グラフの一般化可能な学習を,学習後の合成データとの整合性で解き放つことを提案する。 我々はGRPOやDPOといったポストトレーニング後のアライメントアルゴリズムを採用し、合成グラフデータに基づいて、既製のLLMとLLMの両方を微調整する。 大規模な実験により、我々のトレーニング後のアライメントレシピは、5つのデータセットに対して統計的に有意な改善をもたらすことが示された。
  論文  参考訳（メタデータ） (2025-06-01T05:39:56Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  合成グラフ理論タスクにおける強化学習(RL)はグラフ推論能力を著しく拡張することができる。 RL on ErdosでG1はグラフ推論の大幅な改善を実現し、微調整された3BモデルはQwen2.5-72B-Instruct(24倍)よりも優れています。 我々の研究は、グラフ理論上のRLでLLMを微調整することで、強力なグラフ推論器を構築するための効率的でスケーラブルな経路を提供する。
  論文  参考訳（メタデータ） (2025-05-24T04:33:41Z)
• Compile Scene Graphs with Reinforcement Learning [69.36723767339001]
  次世代予測は大規模言語モデル(LLM)の訓練の基本原理である 本稿では,マルチモーダルLLM(M-LLM)であるR1-SGGを紹介する。 私たちは、Hard Recall、Hard Recall+Relax、Soft Recallの3つのリコールベースのバリエーションを含む、グラフ中心の報酬セットを設計します。
  論文  参考訳（メタデータ） (2025-04-18T10:46:22Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  テキストグラフ学習におけるフラストレーションに富んだアプローチであるSimTeGを提案する。 まず、下流タスクで予め訓練されたLM上で、教師付きパラメータ効率の微調整(PEFT)を行う。 次に、微調整されたLMの最後の隠れ状態を用いてノード埋め込みを生成する。
  論文  参考訳（メタデータ） (2023-08-03T07:00:04Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Designing Heterogeneous GNNs with Desired Permutation Properties for Wireless Resource Allocation [11.66835230109271]
  グラフニューラルネットワーク(GNN)は、さまざまな無線ポリシを学ぶために設計されている。 本稿では,所望の置換特性を満たすための設計手法を提案する。
  論文  参考訳（メタデータ） (2022-03-08T08:02:54Z)
• Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
  動的グラフ変換器 (DGT) を用いた動的グラフ学習手法を提案する。 DGTは、グラフトポロジを効果的に学習し、暗黙のリンクをキャプチャするための時空間符号化を持つ。 DGTはいくつかの最先端のベースラインと比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2021-11-19T21:44:23Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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