Machine learning-based per-instance algorithm selection for high-performance subgraph isomorphism enumeration

The Subgraph Isomorphism Enumeration (SIE) problem requires discovering allthe embeddings of a pattern (or query) subgraph in a given data graph. The problem isNP-complete, and numerous exact heuristic algorithms have been proposed to speed up theexecution of the problem. Based on the observation that no heuristic is the fastest for allpattern and data graph pairs, we design a metaheuristic for per-instance algorithm selectionto determine the fastest heuristic for each graph pair. We hypothesise that the connectionsand properties of vertices in the graph pair are indicative of the best-performing heuristicalgorithm. As such, we design a Machine Learning (ML)-based metaheuristic algorithm andinvestigate how well various types of graph features and ML algorithms predict performance.Our best-performing metaheuristic improves the execution speed of the SIE problem by upto 1.54 times across 8 data graphs compared to any single heuristic algorithm. The analysisfurthermore identifies remaining challenges unique to specific data graphs in the SIE problem.