# Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 47 references that are in the map.
- First posted on arXiv 21 Jul 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (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)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2106.04927/) (2021)
- [GLSearch: Maximum Common Subgraph Detection via Learning to Search](https://mlsanity.com/paper/2002.03129/) (2020)
- [AntiBenford Subgraphs: Unsupervised Anomaly Detection in Financial Networks](https://mlsanity.com/paper/2205.13426/) (2022)
- [Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching](https://mlsanity.com/paper/2201.11251/) (2022)
- [Taming Subgraph Isomorphism for RDF Query Processing](https://mlsanity.com/paper/1506.01973/) (2015)

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

- [Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning](https://mlsanity.com/paper/2603.18314/) (2026)

## Abstract (arXiv)

Recent advances have shown the success of using reinforcement learning and search to solve NP-hard graph-related tasks, such as Traveling Salesman Optimization, Graph Edit Distance computation, etc. However, it remains unclear how one can efficiently and accurately detect the occurrences of a small query graph in a large target graph, which is a core operation in graph database search, biomedical analysis, social group finding, etc. This task is called Subgraph Matching which essentially performs subgraph isomorphism check between a query graph and a large target graph. One promising approach to this classical problem is the "learning-to-search" paradigm, where a reinforcement learning (RL) agent is designed with a learned policy to guide a search algorithm to quickly find the solution without any solved instances for supervision. However, for the specific task of Subgraph Matching, though the query graph is usually small given by the user as input, the target graph is often orders-of-magnitude larger. It poses challenges to the neural network design and can lead to solution and reward sparsity. In this paper, we propose NSUBS with two innovations to tackle the challenges: (1) A novel encoder-decoder neural network architecture to dynamically compute the matching information between the query and the target graphs at each search state; (2) A novel look-ahead loss function for training the policy network. Experiments on six large real-world target graphs show that NSUBS can significantly improve the subgraph matching performance.