Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning

• URL: http://arxiv.org/abs/2603.18314v1
• Date: Wed, 18 Mar 2026 21:53:23 GMT
• Title: Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning
• Abstract summary: This paper proposes a Reinforcement Learning based Approximate Subgraph Matching (RL-ASM) algorithm.<n>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.<n>Experiments on both synthetic and real-world datasets demonstrate that our RL-ASM outperforms existing methods in terms of effectiveness and efficiency.
• Score: 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.

Related papers

• Graph-GRPO: Training Graph Flow Models with Reinforcement Learning [14.937302684130257]
  We propose Graph-GRPO, an online reinforcement learning framework for training graph flow models (GFMs) under verifiable rewards.<n>With only 50 denoising steps, our method achieves 95.0% and 97.5% Valid-Unique-Novelty scores on the planar and tree datasets.
  arXiv  Detail & Related papers  (2026-03-11T04:20:45Z)
• Incorporating Spatial Information into Goal-Conditioned Hierarchical Reinforcement Learning via Graph Representations [37.10671332775445]
  The integration of graphs with Goal-conditioned Reinforcement Learning (GCHRL) has recently gained attention.<n>Existing approaches typically rely on domain-specific knowledge to construct these graphs.<n>This paper proposes a solution by developing a graph encoder-decoder to evaluate unseen states.
  arXiv  Detail & Related papers  (2025-11-14T00:58:39Z)
• GRAIL:Learning to Interact with Large Knowledge Graphs for Retrieval Augmented Reasoning [13.481673780508215]
  GRAIL is a framework designed to interact with large-scale graphs for retrieval-augmented reasoning.<n>GRAIL achieves an average accuracy improvement of 21.01% and F1 improvement of 22.43% on knowledge graph question-answering datasets.
  arXiv  Detail & Related papers  (2025-08-07T15:34:41Z)
• Generalizable LLM Learning of Graph Synthetic Data with Post-training Alignment [38.485929062532925]
  We propose to unlock generalizable learning of graph with post-training alignment with synthetic data.<n>We employ post-training alignment algorithms such as GRPO and DPO, aligning both off-the-shelf LLMs and LLMs fine-tuned on synthetic graph data.<n>Extensive experiments demonstrate that our post-training alignment recipe leads to statistically significant improvement on 5 datasets.
  arXiv  Detail & Related papers  (2025-06-01T05:39:56Z)
• G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning [58.73279333365234]
  Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale graph reasoning abilities.<n>With RL on Erdos, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size)<n>Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks.
  arXiv  Detail & Related papers  (2025-05-24T04:33:41Z)
• Compile Scene Graphs with Reinforcement Learning [69.36723767339001]
  Next-token prediction is the fundamental principle for training large language models (LLMs)<n>We introduce R1-SGG, a multimodal LLM (M-LLM) initially trained via supervised fine-tuning (SFT) on the scene graph dataset.<n>We design a set of graph-centric rewards, including three recall-based variants -- Hard Recall, Hard Recall+Relax, and Soft Recall.
  arXiv  Detail & Related papers  (2025-04-18T10:46:22Z)
• Amplify Graph Learning for Recommendation via Sparsity Completion [16.32861024767423]
  Graph learning models have been widely deployed in collaborative filtering (CF) based recommendation systems. Due to the issue of data sparsity, the graph structure of the original input lacks potential positive preference edges. We propose an Amplify Graph Learning framework based on Sparsity Completion (called AGL-SC)
  arXiv  Detail & Related papers  (2024-06-27T08:26:20Z)
• Can Graph Learning Improve Planning in LLM-based Agents? [61.47027387839096]
  Task planning in language agents is emerging as an important research topic alongside the development of large language models (LLMs) In this paper, we explore graph learning-based methods for task planning, a direction that is to the prevalent focus on prompt design. Our interest in graph learning stems from a theoretical discovery: the biases of attention and auto-regressive loss impede LLMs' ability to effectively navigate decision-making on graphs.
  arXiv  Detail & Related papers  (2024-05-29T14:26:24Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  We present SimTeG, a frustratingly Simple approach for Textual Graph learning. We first perform supervised parameter-efficient fine-tuning (PEFT) on a pre-trained LM on the downstream task. We then generate node embeddings using the last hidden states of finetuned LM.
  arXiv  Detail & Related papers  (2023-08-03T07:00:04Z)
• Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons [50.33260238739837]
  Graph networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data.<n>There remains a lack of analysis comparing GNNs and generalizations from an optimization and generalization perspective.
  arXiv  Detail & Related papers  (2023-06-24T10:21:11Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Designing Heterogeneous GNNs with Desired Permutation Properties for Wireless Resource Allocation [11.66835230109271]
  Graph neural networks (GNNs) have been designed for learning a variety of wireless policies.<n>In this paper, we propose a systematic approach for the design to satisfy the desired permutation property.
  arXiv  Detail & Related papers  (2022-03-08T08:02:54Z)
• Dynamic Graph Representation Learning via Graph Transformer Networks [41.570839291138114]
  We propose a Transformer-based dynamic graph learning method named Dynamic Graph Transformer (DGT) DGT has spatial-temporal encoding to effectively learn graph topology and capture implicit links. We show that DGT presents superior performance compared with several state-of-the-art baselines.
  arXiv  Detail & Related papers  (2021-11-19T21:44:23Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  Graph representation learning has achieved a remarkable success in many graph-based applications, such as node classification, prediction, and community detection. However, for some kind of graph applications, such as graph compression and edge partition, it is very hard to reduce them to some graph representation learning tasks. In this paper, we propose to attack the graph ordering problem behind such applications by a novel learning approach.
  arXiv  Detail & Related papers  (2020-01-18T09:14:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.