# Neural Subgraph Matching

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

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2020.

## Built on by (most cited first, 30 of 47)

- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2202.13538/) (2022)
- [Logic Embeddings for Complex Query Answering](https://mlsanity.com/paper/2103.00418/) (2021)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Graph Edit Distance with General Costs Using Neural Set Divergence](https://mlsanity.com/paper/2409.17687/) (2024)
- [SG-PGM: Partial Graph Matching Network with Semantic Geometric Fusion for 3D Scene Graph Alignment and Its Downstream Tasks](https://mlsanity.com/paper/2403.19474/) (2024)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2303.03379/) (2023)
- [RAHNet: Retrieval Augmented Hybrid Network for Long-tailed Graph Classification](https://mlsanity.com/paper/2308.02335/) (2023)
- [Towards A Universal Graph Structural Encoder](https://mlsanity.com/paper/2504.10917/) (2025)
- [Graph-Reward-SQL: Execution-Free Reinforcement Learning for Text-to-SQL via Graph Matching and Stepwise Reward](https://mlsanity.com/paper/2505.12380/) (2025)
- [Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching](https://mlsanity.com/paper/2201.11251/) (2022)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [DeepGAR: Deep Graph Learning for Analogical Reasoning](https://mlsanity.com/paper/2211.10821/) (2022)
- [Representation Learning for Frequent Subgraph Mining](https://mlsanity.com/paper/2402.14367/) (2024)
- [Schema-Guided Event Graph Completion](https://mlsanity.com/paper/2206.02921/) (2022)
- [GNNPipe: Scaling Deep GNN Training with Pipelined Model Parallelism](https://mlsanity.com/paper/2308.10087/) (2023)
- [FLEX: Feature-Logic Embedding Framework for CompleX Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.11039/) (2022)
- [Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning](https://mlsanity.com/paper/2210.10643/) (2022)
- [D2Match: Leveraging Deep Learning and Degeneracy for Subgraph Matching](https://mlsanity.com/paper/2306.06380/) (2023)
- [Neural Graduated Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2505.12325/) (2025)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (2022)
- [Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings](https://mlsanity.com/paper/2505.13087/) (2025)
- [SCENIR: Visual Semantic Clarity through Unsupervised Scene Graph Retrieval](https://mlsanity.com/paper/2505.15867/) (2025)
- [Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval](https://mlsanity.com/paper/2510.22538/) (2025)
- [Interactive Visual Pattern Search on Graph Data via Graph Representation Learning](https://mlsanity.com/paper/2202.09459/) (2022)
- [Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search](https://mlsanity.com/paper/2207.10305/) (2022)
- [PharmacoMatch: Efficient 3D Pharmacophore Screening via Neural Subgraph Matching](https://mlsanity.com/paper/2409.06316/) (2024)
- [Functional Matching of Logic Subgraphs: Beyond Structural Isomorphism](https://mlsanity.com/paper/2505.21988/) (2025)
- [Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks](https://mlsanity.com/paper/2507.20226/) (2025)

## Abstract (arXiv)

Subgraph matching is the problem of determining the presence and location(s) of a given query graph in a large target graph. Despite being an NP-complete problem, the subgraph matching problem is crucial in domains ranging from network science and database systems to biochemistry and cognitive science. However, existing techniques based on combinatorial matching and integer programming cannot handle matching problems with both large target and query graphs. Here we propose NeuroMatch, an accurate, efficient, and robust neural approach to subgraph matching. NeuroMatch decomposes query and target graphs into small subgraphs and embeds them using graph neural networks. Trained to capture geometric constraints corresponding to subgraph relations, NeuroMatch then efficiently performs subgraph matching directly in the embedding space. Experiments demonstrate NeuroMatch is 100x faster than existing combinatorial approaches and 18% more accurate than existing approximate subgraph matching methods.