Set-Centric Subgraph Isomorphism

Abstract

We investigate techniques for accelerating subgraph isomorphism (SI). SI is the task of finding occurrences of a pattern graph in a target graph and relevant to many practical applications. Our key idea is to use set algebra based formulations of SI. This facilitates employing set data structures to test the feasibility of partial mappings from the pattern graph to the target graph. The methods we use involve a range of algorithm variants with different set-centric formulations of subgraph isomorphism, different set data structures, and different parallelization schemes. Our results show that our set-centric variants outperform the baseline on some, but not all, pattern and target graphs. We conclude that the relative performance of the algorithm variants is strongly impacted by the choice of the input and propose further research directions to develop a more powerful algorithm.