Enumerating Graph Pattern Matches with ML Oracles
Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-28
DOI: 10.1145/3786648 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Wenfei Fan und 3 weiteren Autor:innen. Die Arbeit nennt 130 Literaturangaben. Gefördert von: National Natural Science Foundation of China, State Key Laboratory of Complex & Critical Software Environment.
Abstract (Originalsprache)
This paper presents an ML-based method for SubIso, the graph pattern matching problem. Given a graph G and a pattern Q , SubIso aims to enumerate all subgraphs of G that are isomorphic to Q . We show that SubIso is EnumP-complete, where EnumP is the enumeration counterpart of NP. We then study revisions VF3 M of the classical VF3 algorithm by incorporating an ML oracle ℻. The model ℻ predicts candidate matches, while VF3 M verifies them, thereby reducing costly backtracking. We examine whether VF3 M is (a) output-polynomial, i.e., its runtime is polynomial in the sizes of input and output; (b) consistent, i.e., its accuracy reaches 100% with error-free predictions from ℻; and (c) β-robust, i.e., it guarantees accuracy of at least β even with arbitrarily bad predictions. We establish several results, positive and negative. On the negative side, we show that it is impossible for VF3 M to be both output polynomial and β-robust with a positive constant β unless P = fewP, a problem as hard as P = NP. On the positive side, we develop three versions of VF3 M that are (a) consistent, and (b) either 1-robust or output polynomial with a high probability. We also train a model ℻ for VF3 M . Using real-life and synthetic data, we show that VF3 M is up to 15.75x--21x faster than VF3, with F1-score 0.98.
Förderung
- National Natural Science Foundation of China
- State Key Laboratory of Complex & Critical Software Environment
Zitieren
APA
Fan, W., Luo, Y., Lu, P., & Zhu, X. (2026). Enumerating Graph Pattern Matches with ML Oracles. Proceedings of the ACM on Management of Data, 4(1), 1-28. https://doi.org/10.1145/3786648
Vancouver
Fan W, Luo Y, Lu P, Zhu X. Enumerating Graph Pattern Matches with ML Oracles. Proceedings of the ACM on Management of Data. 2026;4(1):1-28. doi:10.1145/3786648
BibTeX
@article{Fan2026,
author = {Fan, Wenfei and Luo, Yixuan and Lu, Ping and Zhu, Xiaoke},
title = {Enumerating Graph Pattern Matches with ML Oracles},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {1},
pages = {1--28},
doi = {10.1145/3786648}
}
EUVIMED