CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching

Subgraph matching finds all distinct isomorphic embeddings of a query graph on a data graph. For large graphs, current solutions face the scalability challenge due to expensive joins, excessive false candidates, and workload imbalance. In this paper, we propose a novel framework for subgraph listing based on Compact Embedding Cluster Index (CECI), which divides the data graph into multiple embedding clusters for parallel processing. The CECI system has three unique techniques: utilizing the BFS-based filtering and reverse-BFSbased refinement to prune the unpromising candidates early on, replacing the edge verification with set intersection to speed up the candidate verification, and using search cardinality based cost estimation for detecting and dividing large embedding clusters in advance. The experiments performed on several real and synthetic datasets show that the CECI system outperforms state-of-the-art solutions on average by 20.4x for listing all embeddings and by 2.6x for enumerating the first 1,024 embeddings.