Accelerating Subgraph Matching through Fine-grained and Powerful Equivalences

Download PDF

Abstract

Subgraph matching, a cornerstone of graph analytics, crit ically suffers from redundant computations during the search process. Existing methods primarily target identical computations redundant operations that are localized to individual query vertices but fail to address similar redundancies that recur across multiple query vertices. In this paper, we present a novel algorithm, called FiPE, that accelerates subgraph matching through Fi ne-grained and P owerful E quivalences. FiPE redefines redundancy elimination by shifting the optimization granularity from isolated vertices to vertex pairs and multiple vertex patterns. It introduces vertex-pair equivalence to cluster candidate pairs with isomorphic neighbor structures, even if their individual vertices differ, enabling pruning of similar computations between these vertex pairs. FiPE proposes group equivalence to defer equivalence checks to later search depths, capturing potential redundancies incrementally. To fully exploit the advantages of the equivalence, we introduce two optimization techniques: a matching order generation method to reduce the overall search space and an efficient conflict resolution mechanism to avoid two query vertices being mapped to the same data vertex. Experiments on real-world graphs highlight the superiority of FiPE. FiPE achieves a speedup of 2 to 3 orders of magnitude on various graphs under the EPS (embeddings per second) metric.