Research map / Graph learning / Graph algorithms and clustering
SAT-Based Algorithms for Regular Graph Pattern Matching
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Regular Graph Patterns (ReGaP), a generalization of graph isomorphism with wildcard nodes for variable-length sequences and subgraphs, matched via a SAT encoding plus a node-merging preprocessing step, evaluated on control-flow graphs from CodeSearchNet.
Problem
Graph isomorphism only tests strict equality, and approximate graph matching and regular-path queries cannot express complex structural properties such as arbitrary-length sequences followed by arbitrary subgraphs, which is needed for code pattern detection.
Approach
Define Regular Graph Patterns with any-0+/1+ sequence and subgraph wildcards, decide matching by expanding wildcards into bounded copies and encoding the mapping to CNF for a SAT solver, and shrink the graph beforehand by merging nodes that cannot match any non-wildcard pattern node.
Key results
- Node merging reduces nodes by 15.4% on average and clauses by 25.7% on average.
- With node merging, timeouts drop from 34,110 to 26,487 out of 946,556 instances (60 s timeout).
- Execution time grows with the number of wildcards, with the edge-between-wildcards ReGaP showing the most timeouts (11.0%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add node merging preprocessing (ablation) | SAT-based ReGaP matcher · CodeSearchNet graphs and evaluated ReGaPs | number of SAT clauses: 25.7% less clauses | Helped |
| add node merging preprocessing (ablation) | SAT-based ReGaP matcher · CodeSearchNet graphs and evaluated ReGaPs | instances solved in less than 10 seconds: 42 498 more instances | Helped |
| add node merging preprocessing (ablation) | SAT-based ReGaP matcher · CodeSearchNet graphs and evaluated ReGaPs | timeouts: 34 110 -> 26 487 | Helped |
| add node merging preprocessing (ablation) | SAT-based ReGaP matcher · CodeSearchNet graphs and evaluated ReGaPs | timeouts on instances solved by the base encoding: 940 instances | Hurt |
| increase the number of wildcards | SAT-based ReGaP matcher without node merging · CodeSearchNet graphs and evaluated ReGaPs | average execution time (s) | Mixed |
Surprising findings
- Node merging is slower on some instances, with 940 instances timing out only with merging, attributed to solver instability from small formula changes.
Limitations
- Wildcard expansion with k=|V| is naive and can blow up the encoding size.
- Evaluation uses a preliminary set of 13 ReGaPs from a single use case.
- Not compared with regular-path query systems.
Experimental setup
Datasets: CodeSearchNet
Benchmarks: CodeSearchNet control-flow graphs (946,556 instances)
Metrics: execution time timeouts encoding size (variables and clauses)
Baselines: Glucose (no node merging, base encoding)
Builds on: maximum common subgraph SAT encoding conflict-driven clause learning
Closest papers by meaning
- On the Power of the Weisfeiler-Leman Test for Graph Motif Parameters (ICLR 2024 · similarity 0.86)
- End-to-End Verification for Subgraph Solving (AAAI 2024 · similarity 0.85)
- Breaking Symmetries in Quantified Graph Search: A Comparative Study (AAAI 2025 · similarity 0.84)
- Iteratively Refined Early Interaction Alignment for Subgraph Matching based Graph Retrieval (NeurIPS 2024 · similarity 0.84)
- Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS (ICML 2024 · similarity 0.84)
- Homomorphism Counts for Graph Neural Networks: All About That Basis (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.