An Efficient Algorithm for Subgraph Isomorphism using Dynamic Programming on Directed Acyclic Graphs

Abstract

Subgraph isomorphism (or subgraph matching) is one of the fundamental problems in graph analysis. It is an NP-hard problem, and extensive research has been done to develop practical solutions for subgraph isomorphism. Although a great deal of progress has been made, the existing solutions still show a limited scalability in handling large real graphs. The state-of-the-art algorithms are based on the general framework of backtracking which recursively finds all embeddings of a query graph in a data graph. In this thesis we introduce three new techniques: dynamic programming on directed acyclic graphs, the adaptive matching order with DAG-ordering, and pruning by failing sets, which together lead to a much faster and more scalable algorithm DP-iso for subgraph isomorphism. Extensive experiments with real datasets show that DP-iso outperforms the fastest existing solution by up to 4 orders of magnitude with respect to the running time and up to 6 orders of magnitude with respect to the number of recursions.