# Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching

arXiv: https://arxiv.org/abs/2201.11251 · HTML: https://mlsanity.com/paper/2201.11251/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 63 references that are in the map.
- First posted on arXiv 25 Jan 2022.

## Builds on (most cited first, 25 of 25)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generation](https://mlsanity.com/paper/1806.02473/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations](https://mlsanity.com/paper/1911.07979/) (2019)
- [Neural Optimizer Search with Reinforcement Learning](https://mlsanity.com/paper/1709.07417/) (2017)
- [Graph Transformation Policy Network for Chemical Reaction Prediction](https://mlsanity.com/paper/1812.09441/) (2018)
- [Graph Policy Network for Transferable Active Learning on Graphs](https://mlsanity.com/paper/2006.13463/) (2020)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Inductive Link Prediction for Nodes Having Only Attribute Information](https://mlsanity.com/paper/2007.08053/) (2020)
- [GoGNN: Graph of Graphs Neural Network for Predicting Structured Entity Interactions](https://mlsanity.com/paper/2005.05537/) (2020)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Binarized Graph Neural Network](https://mlsanity.com/paper/2004.11147/) (2020)
- [Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?](https://mlsanity.com/paper/1909.11830/) (2019)
- [Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems](https://mlsanity.com/paper/1803.09930/) (2018)
- [HUGE: An Efficient and Scalable Subgraph Enumeration System](https://mlsanity.com/paper/2103.14294/) (2021)

## Built on by (most cited first, 6 of 6)

- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Intrinsically motivated graph exploration using network theories of human curiosity](https://mlsanity.com/paper/2307.04962/) (2023)
- [Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search](https://mlsanity.com/paper/2207.10305/) (2022)
- [A Survey on Machine Learning Solutions for Graph Pattern Extraction](https://mlsanity.com/paper/2204.01057/) (2022)
- [Neural Graph Navigation for Intelligent Subgraph Matching](https://mlsanity.com/paper/2511.17939/) (2025)
- [Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning](https://mlsanity.com/paper/2603.18314/) (2026)

## Abstract (arXiv)

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.