Synthesizing Graph Queries from Demonstrations
Open Access
- 1 October 2026
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 10 (OOPSLA2) , 2162-2189
Abstract
Writing graph queries is challenging for non-experts due to the complexity of graph data models and the need to identify proper graph patterns. While recent research has advanced query synthesis for relational and document databases, the problem of synthesizing graph queries remains under-explored. We present a novel approach for synthesizing graph queries from computation demonstrations, where users specify the desired output through expressions over properties of input graphs. Our method addresses the challenge of inferring meaningful graph patterns for matching and efficiently constructing the remaining components of the query. Specifically, we combine graph mining, which identifies candidate patterns across input graphs, with deduction-based pruning, which guides an efficient synthesis of the filtering predicate and return clause. We have implemented our approach in a tool called DMiner and evaluated it on 90 benchmarks. Experimental results show that DMiner successfully synthesizes desired queries for 87 benchmarks, with an average synthesis time of 0.6 seconds per query. This outperforms both enumerative search and LLM baselines. We also conducted a user study, which shows that users can provide demonstrations with modest effort and 87.5% of the provided demonstrations are sufficient for DMiner to synthesize the desired query.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada (RGPIN-2022-04983)
- Natural Sciences and Engineering Research Council of Canada (RGPIN-2025-04775)
- Natural Sciences and Engineering Research Council of Canada (DGECR-2022-00417)
- Natural Sciences and Engineering Research Council of Canada (Undergraduate Student Research Award)
- Simon Fraser University (Startup Grant)
This publication has 19 references indexed in Scilit:
- Enhancing knowledge graph interactions: A comprehensive Text-to-Cypher pipeline with large language modelsInformation Processing & Management, 2025
- Learning programs by learning from failuresMachine Learning, 2021
- Automated repair by example for firewallsFormal Methods in System Design, 2020
- Syntax-guided synthesis2013
- Program sketchingInternational Journal on Software Tools for Technology Transfer, 2012
- Graph Mining Applications to Social Network Analysis2010
- Graph miningACM Computing Surveys, 2006
- Finding Frequent Patterns in a Large Sparse Graph*Data Mining and Knowledge Discovery, 2005
- Programming by Demonstration Using Version Space AlgebraMachine Learning, 2003
- An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data2000