# Neural Graph Navigation for Intelligent Subgraph Matching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 55 references that are in the map.
- First posted on arXiv 22 Nov 2025.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer](https://mlsanity.com/paper/1904.06690/) (2019)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Spatiotemporal-Augmented Graph Neural Networks for Human Mobility Simulation](https://mlsanity.com/paper/2306.09381/) (2023)
- [Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding (Technical Report)](https://mlsanity.com/paper/2309.15641/) (2023)
- [Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching](https://mlsanity.com/paper/2201.11251/) (2022)
- [Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction](https://mlsanity.com/paper/2304.12610/) (2023)
- [GNN-based Anchor Embedding for Efficient Exact Subgraph Matching](https://mlsanity.com/paper/2502.00031/) (2025)

## Abstract (arXiv)

Subgraph matching, a cornerstone of relational pattern detection in domains ranging from biochemical systems to social network analysis, faces significant computational challenges due to the dramatically growing search space. Existing methods address this problem within a filtering-ordering-enumeration framework, in which the enumeration stage recursively matches the query graph against the candidate subgraphs of the data graph. However, the lack of awareness of subgraph structural patterns leads to a costly brute-force enumeration, thereby critically motivating the need for intelligent navigation in subgraph matching. To address this challenge, we propose Neural Graph Navigation (NeuGN), a neuro-heuristic framework that transforms brute-force enumeration into neural-guided search by integrating neural navigation mechanisms into the core enumeration process. By preserving heuristic-based completeness guarantees while incorporating neural intelligence, NeuGN significantly reduces the textitFirst Match Steps by up to 98.2% compared to state-of-the-art methods across six real-world datasets.