EUVIMEDEUVIMED entdecken
Crossref

Enumerating Graph Pattern Matches with ML Oracles

Wenfei Fan, Yixuan Luo, Ping Lu, Xiaoke Zhu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →