Enumerating Graph Pattern Matches with ML Oracles

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.