FASTiso: Fast Algorithm on Search state Tree for subgraph ISOmorphism in graphs of any size and density

Subgraph isomorphism is a combinatorial problem that involves finding one or all occurrences of a pattern graph within a target graph. Subgraph isomorphism has numerous applications in fields such as biology, chemistry, social network analysis, and pattern recognition. Although subgraph isomorphism is generally NP-complete, there are polynomial algorithms for special cases of graphs and efficient heuristics for the general case. However, the increasing size and complexity of graphs datasets require continuous improvements to existing methods.

In this article, we present FASTiso, a novel subgraph isomorphism algorithm for any type of graphs with new heuristics for efficient exploration and pruning of the search state tree. We compared FASTiso to an ensemble of state-of-the-art solvers (VF3, VF3l, RI, Glasgow) on 7 synthetic and real datasets from the literature. The results show a significant reduction in the execution time of FASTiso compared to VF3 and other state-of-the-art algorithms. We also demonstrate that FASTiso is particularly efficient on large and dense graphs, and that it performs better than other solvers on different datasets. In addition to its execution speed, FASTiso has a smaller memory footprint than almost all other algorithms as only RI uses less memory.

The FASTiso code is available at https://gitlab.info.uqam.ca/cbe/fastiso as a C++ implementation, a python module, and integrated in a NetworkX fork. Our implementations support graphs and multigraphs, directed or not, and can include labels on nodes, edges, or both.