# GLSearch: Maximum Common Subgraph Detection via Learning to Search

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Feb 2020.

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

- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Retrieval-Guided Reinforcement Learning for Boolean Circuit Minimization](https://mlsanity.com/paper/2401.12205/) (2024)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning](https://mlsanity.com/paper/2205.15083/) (2022)
- [Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks](https://mlsanity.com/paper/2210.11020/) (2022)
- [Commute-Time-Optimised Graphs for GNNs](https://mlsanity.com/paper/2407.08762/) (2024)
- [Neural Graduated Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2505.12325/) (2025)
- [Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness](https://mlsanity.com/paper/2112.03404/) (2021)
- [Learning Universe Model for Partial Matching Networks over Multiple Graphs](https://mlsanity.com/paper/2210.10374/) (2022)
- [Self-Localized Collaborative Perception](https://mlsanity.com/paper/2406.12712/) (2024)
- [DiffGED: Computing Graph Edit Distance via Diffusion-based Graph Matching](https://mlsanity.com/paper/2503.18245/) (2025)
- [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)
- [Hybrid Learning with New Value Function for the Maximum Common Subgraph Problem](https://mlsanity.com/paper/2208.08620/) (2022)
- [Solving the Kidney-Exchange Problem via Graph Neural Networks with No Supervision](https://mlsanity.com/paper/2304.09975/) (2023)
- [SEGMN: A Structure-Enhanced Graph Matching Network for Graph Similarity Learning](https://mlsanity.com/paper/2411.03624/) (2024)
- [Approximate Subgraph Matching with Neural Graph Representations and Reinforcement Learning](https://mlsanity.com/paper/2603.18314/) (2026)
- [Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs](https://mlsanity.com/paper/2609.32661/) (2026)

## Abstract (arXiv)

Detecting the Maximum Common Subgraph (MCS) between two input graphs is fundamental for applications in drug synthesis, malware detection, cloud computing, etc. However, MCS computation is NP-hard, and state-of-the-art MCS solvers rely on heuristic search algorithms which in practice cannot find good solution for large graph pairs given a limited computation budget. We propose GLSearch, a Graph Neural Network (GNN) based learning to search model. Our model is built upon the branch and bound algorithm, which selects one pair of nodes from the two input graphs to expand at a time. Instead of using heuristics, we propose a novel GNN-based Deep Q-Network (DQN) to select the node pair, allowing the search process faster and more adaptive. To further enhance the training of DQN, we leverage the search process to provide supervision in a pre-training stage and guide our agent during an imitation learning stage. Experiments on synthetic and real-world large graph pairs demonstrate that our model learns a search strategy that is able to detect significantly larger common subgraphs given the same computation budget. Our GLSearch can be potentially extended to solve many other combinatorial problems with constraints on graphs.