EUVIMEDOpdag EUVIMED
Crossref

Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching

Zhijie Zhang, Sitao Yang, Weiguo Zheng, Qiang Zhou, Chuntao Hong

Proceedings of the ACM on Management of Data · 2026-05-18 · 4 (3) · 1-27

DOI: 10.1145/3802022 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-05-18. Written by Zhijie Zhang and 4 co-authors. 52 references. Funded by: National Natural Science Foundation of China, Key Projects of the National Natural Science Foundation of China.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

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.

Funding

  • National Natural Science Foundation of China
  • Key Projects of the National Natural Science Foundation of China

Cite

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}
}
Start for free →