Accelerating Subgraph Matching through Fine-Grained and Powerful Equivalences
Proceedings of the VLDB Endowment · 2025-07 · 18 (11) · 3896-3909
DOI: 10.14778/3749646.3749662 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 04.09.2025. Verfasst von Yujie Lu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 6-mal zitiert (Crossref) und nennt 47 Literaturangaben.
Abstract (Originalsprache)
Subgraph matching, a cornerstone of graph analytics, critically 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 Fine-grained and Powerful Equivalences. 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.
Zitieren
APA
Lu, Y., Zhang, Z., Zheng, W., & Zou, L. (2025). Accelerating Subgraph Matching through Fine-Grained and Powerful Equivalences. Proceedings of the VLDB Endowment, 18(11), 3896-3909. https://doi.org/10.14778/3749646.3749662
Vancouver
Lu Y, Zhang Z, Zheng W, Zou L. Accelerating Subgraph Matching through Fine-Grained and Powerful Equivalences. Proceedings of the VLDB Endowment. 2025;18(11):3896-3909. doi:10.14778/3749646.3749662
BibTeX
@article{Lu2025,
author = {Lu, Yujie and Zhang, Zhijie and Zheng, Weiguo and Zou, Lei},
title = {Accelerating Subgraph Matching through Fine-Grained and Powerful Equivalences},
journal = {Proceedings of the VLDB Endowment},
year = {2025},
volume = {18},
number = {11},
pages = {3896--3909},
doi = {10.14778/3749646.3749662}
}
EUVIMED