Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching
Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27
DOI: 10.1145/3802022 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Zhijie Zhang und 4 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Key Projects of the National Natural Science Foundation of China.
Abstract (Originalsprache)
Subgraph matching, a fundamental operation in graph analytics, delivers all occurrences of a query pattern within a large data graph. Graph systems often require processing large batches of such queries simultaneously. The existing multi-query approaches typically aim to optimize this process by exploiting the maximum common subgraph (MCS) among query graphs. However, identifying MCS is computationally prohibitive and does not necessarily maximize computational reuse, leading to substantial redundancy and limited scalability. In this paper, we propose MASC, a novel framework for subgraph matching with M ulti-query A cceleration via S hared C omputation. We introduce signature-based joint filtering that enables shared computation in the filtering phase, significantly improving filtering efficiency across queries. Building on this, we propose the visit-once paradigm that leverages shared candidates rather than just shared structure size, ensuring each shared candidate in the data graph is processed only once and further maximizing computation sharing. To further enhance sharing, we develop the shared block reuse that exploits multiple overlapping substructures among queries. Compared to existing methods that leverage only a single overlap, the shared computations are further substantially increased. We conducted extensive experiments on real-world datasets across various domains. The results demonstrate that MASC achieves significant improvements, achieving substantial speedup over state-of-the-art methods, with up to two orders of magnitude improvement.
Förderung
- National Natural Science Foundation of China
- Key Projects of the National Natural Science Foundation of China
Zitieren
APA
Zhang, Z., Yang, S., Zheng, W., Zhou, Q., & Hong, C. (2026). Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802022
Vancouver
Zhang Z, Yang S, Zheng W, Zhou Q, Hong C. Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802022
BibTeX
@article{Zhang2026,
author = {Zhang, Zhijie and Yang, Sitao and Zheng, Weiguo and Zhou, Qiang and Hong, Chuntao},
title = {Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {3},
pages = {1--27},
doi = {10.1145/3802022}
}
EUVIMED