Papers › GuP: Fast Subgraph Matching by Guard-based Pruning

GuP: Fast Subgraph Matching by Guard-based Pruning

11 Jun 2023arXiv:2306.06557archive 2025-07-28

Junya Arai, Yasuhiro Fujiwara, Makoto Onizuka

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.

PaperPDFCode

Syntology This paper's arXiv id is not in Syntology's Atlas id list (549,449 ids, as this build read them; the read time is in the build record), so this page links to no Syntology page for it. The list is not the whole graph; Syntology's feed shows papers as they enter the graph.

Code

araij/gup officialmentioned in paperSyntology: not harvested report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Information RetrievalRetrieval

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

Pruning

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections