# GuP: Fast Subgraph Matching by Guard-based Pruning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2023.

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

- [Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks](https://mlsanity.com/paper/2507.20226/) (2025)
- [Can Aggregate Invariants Accelerate Continuous Subgraph Matching? Limits, Laws, and a Dynamic Spectral Index](https://mlsanity.com/paper/2606.24421/) (2026)

## Abstract (arXiv)

Subgraph matching, which finds subgraphs isomorphic to a query, is the key to information retrieval from data represented as a graph. To avoid redundant exploration in the data, existing methods restrict the search space by extracting candidate vertices and candidate edges that may constitute isomorphic subgraphs. However, it still requires expensive computation because candidate vertices induce many subgraphs that are not isomorphic to the query. In this paper, we propose GuP, a subgraph matching algorithm with pruning based on guards. Guards are a pattern of intermediate search states that never find isomorphic subgraphs. GuP attaches a guard on each candidate vertex and edge and filters out them adaptively to the search state. The experimental results showed that GuP can efficiently solve various queries, including those that the state-of-the-art methods could not solve in practical time.