Large Subgraph Matching: A Comprehensive and Efficient Approach for Heterogeneous Graphs
Hongtai Cao, Qihao Wang, Xiaodong Li, Matin Najafi, Kevin Chen–Chuan Chang, Reynold C. K. Cheng · 2024
The subgraph matching problem is crucial in graph analysis, involving identifying all instances of a given pattern$P$within a graph$G$. Advances in this field aim to uncover larger patterns across diverse graph types and subgraph matching tasks. However, existing methods often prove inefficient for such tasks. To address this gap, we propose CSCE, which generates efficient plans for various problem settings. CSCE utilizes clustered compressed sparse rows for heterogeneous graphs and sequential candidate equivalence to reduce redundant computations. Moreover, our approach seamlessly supports different subgraph matching variants, such as edge-induced, vertex-induced, and homomorphic scenarios. Experiments show that our work is up to two orders of magnitude faster than the state of the art on graphs of millions scale.