一句话：提出可编程查询优化框架 Geo，用重写规则与等价饱和自动组合图模式等价，并保持结果正确与可重构。
图模式挖掘通常需要回答模式匹配查询，其中子图同构问题是 NP 完全的。领域专家常基于模式间的子结构相似性手写优化器，但模式的子对称等复杂结构性质使优化器开发困难，也限制了不同优化策略的交互探索与持续扩展。本文提出可编程模式匹配查询优化器 Geo，它提供简洁而灵活的语言，将模式等价表示为重写规则，并自动管理规则间交互、保证结果正确性。Geo 在等价饱和过程中维护生成模式的规范表示，避免同构模式的语法差异问题；同时提出嵌入式可重构性 EmRec，跨等价关系跟踪 provenance，以满足不同输出的可重构需求。评估显示，Geo 能通过复杂规则组合发现新查询等价，使优化查询成本较先前工作最多降低 99%；在近似模式匹配和准团挖掘两个案例中，成本最多降低 71%。
Graph pattern mining is important for analyzing graph data. Graph mining systems typically require answering pattern matching queries, which involve solving the NP-complete subgraph isomorphism problem. To address this, domain experts often develop custom pattern matching query optimization strategies based on exploiting substructural similarities across different patterns. While these optimizers can be effective, their development is challenging due to the complex structural properties of the patterns (e.g., subsymmetries), which are difficult to address. This complexity limits the exploration of interactions between different optimization strategies and restricts experts from continuously improving the optimizers—such as by incorporating additional custom or general pattern-based equivalences over time. In this paper, we present a programmable pattern matching query optimizer called Geo , which automatically manages the interactions between various equivalences, ensures the optimizations maintain correctness of results, and simplifies the management of substructure equivalences. Geo exposes a simple but flexible language for expressing pattern equivalences as rewrite rules. By maintaining canonical representations of generated patterns during equality saturation, Geo avoids issues arising from syntactic differences in isomorphic patterns. Additionally, we develop embedded reconstructablility ( EmRec ) that tracks provenance across equivalences to ensure various reconstructability needs of desired outputs. Our evaluation demonstrates that Geo can discover novel query equivalences through complex composition of various rewrite rules, enabling our optimized queries to achieve a cost reduction of up to 99% compared to the queries in prior work. We further test Geo ’s effectiveness at speeding up practical graph mining problems by using it in two representative case studies – approximate pattern matching and quasi-clique mining, and find it is highly effective at optimizing these tasks, enabling cost reductions of up to 71%.
@article{paperbot3844,
title = {Geo: A Query Rewrite Framework for Graph Pattern Mining},
author = {Nazanin Yousefian and Kasra Jamshidi and Keval Vora and Anders Miltner},
journal = {Proceedings of the ACM on Programming Languages},
volume = {10},
number = {OOPSLA1},
year = {2026},
doi = {10.1145/3798239}
}