Machine Learning-Based Per-Instance Algorithm Selection for High-Performance Subgraph Isomorphism Enumeration

The Subgraph Isomorphism Enumeration (SIE) problem requires discovering all the embeddings of a pattern (or query) subgraph in a given data graph. The problem is NP-complete, and numerous exact heuristic algorithms have been proposed to speed up the execution of the problem. Based on the observation that no heuristic is the fastest for all pattern and data graph pairs, we design a metaheuristic for per-instance algorithm selection to determine the fastest heuristic for each graph pair. We hypothesise that the connections and properties of vertices in the graph pair are indicative of the best-performing heuristic algorithm. As such, we design a Machine Learning (ML)-based metaheuristic algorithm and investigate 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 up to 1.54 times across 8 data graphs compared to any single heuristic algorithm. The analysis furthermore identifies remaining challenges unique to specific data graphs in the SIE problem.