Scalable Optimization of Graph Pattern Queries Using Summary Graphs

Graph pattern matching is a fundamental operation for querying, exploring and analyzing graph data, widely used not only on web applications like social networks but also in various other domains. We focus on evaluating graph pattern queries involving direct (edge-to-edge matching) and reachability (edge-to-path matching) relationships under homomorphisms on data graphs. Most existing algorithms focus on isomorphic matching of patterns involving only direct edges. Given that this problem is NP-hard even for the restricted case of isomorphic patterns, these algorithms are space- and time-inefficient for general graphs. We address the problem of optimizing pattern queries on graphs using materialized views to prune the pattern matching search space. We propose a compact way of materializing the views that losslessly summarizes all the homomorphic matches of the query without explicitly storing all the query results. We design an algorithm for optimizing pattern queries in the presence of materialized views. We conducted experiments on various data graphs, query patterns, and materialized views. Our results demonstrate that our optimization algorithm can substantially speed up query evaluation, achieving improvements of several orders of magnitude depending on the query coverage provided by the materialized views. In addition, our approach scales smoothly, outperforming a previous graph simulation-based method.