Path-Centric Cardinality Estimation for Subgraph Matching

This paper presents PathCE, a path-centric cardinality estimation framework for subgraph matching. PathCE improves estimation accuracy by utilizing statistics from short graph queries. At its core is a novel data structure called the path-centric summary graph (PSG), which captures short path query statistics from a data graph G and represents them in a new graph G . Given a graph query Q and a PSG graph G for G, PathCE decomposes Q into a simpler query G , where each edge in G corresponds to a sub-path query in Q with statistics included in G . PathCE estimates the cardinality using G and G , requiring significantly fewer estimation iterations while ensuring that the estimate remains an upper bound on the true cardinality of Q ( G ). It also includes PSGBuilder, a parallelly scalable algorithm that constructs PSG's for any given graph in linear time, efficiently scaling with the number of processors. Empirical results on real-world and synthetic datasets show that PathCE outperforms state-of-the-art baselines in accuracy, estimation latency, and summary construction efficiency.