EUVIMEDObjevte EUVIMED
Crossref

Enumerating Graph Pattern Matches with ML Oracles

Wenfei Fan, Yixuan Luo, Ping Lu, Xiaoke Zhu

Proceedings of the ACM on Management of Data · 2026-04-02 · 4 (1) · 1-28

DOI: 10.1145/3786648 ↗

At a glance

Journal article in Proceedings of the ACM on Management of Data, published online on 2026-04-07. Written by Wenfei Fan and 3 co-authors. 130 references. Funded by: National Natural Science Foundation of China, State Key Laboratory of Complex & Critical Software Environment.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

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.

Funding

  • National Natural Science Foundation of China
  • State Key Laboratory of Complex & Critical Software Environment

Cite

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