It is common to find graphs with millions of nodes and billions of edges in, e.g., social networks. Queries on such graphs are often prohibitively expensive. These motivate us to propose query preserving graph compression, to compress graphs relative to a class Q of queries of users' choice. We compute a small G r from a graph G such that (a) for any query Q ∈ Q, Q(G) = Q (Gr), where Q ∈ Q can be efficiently computed from Q; and (b) any algorithm for computing Q(G) can be directly applied to evaluating Q on Gr as is. That is, while we cannot lower the complexity of evaluating graph queries, we reduce data graphs while preserving the answers to all the queries in Q. To verify the effectiveness of this approach, (1) we develop compression strategies for two classes of queries: reachability and graph pattern queries via (bounded) simulation. We show that graphs can be efficiently compressed via a reachability equivalence relation and graph bisimulation, respectively, while preserving query answers. (2) We provide techniques for maintaining compressed graph G r in response to changes ΔG to the original graph G. We show that the incremental maintenance problems are unbounded for the two classes of queries, i.e., their costs are not a function of the size of ΔG and changes in G r . Nevertheless, we develop incremental algorithms that depend only on ΔG and G r , independent of G, i.e., we do not have to decompress G r to propagate the changes. (3) Using real-life data, we experimentally verify that our compression techniques could reduce graphs in average by 95% for reachability and 57% for graph pattern matching, and that our incremental maintenance algorithms are efficient.
Fan et al. REF propose query-preserving graph compression that retains equivalent query results on two particular query classes.
Query preserving graph compression
SIGMOD Conference
Computer Science