Paper Info
Title
Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together
Abstract
Subgraph matching (or subgraph isomorphism) is one of the fundamental problems in graph analysis. Extensive research has been done to develop practical solutions for subgraph matching. The state-of-the-art algorithms such as \textsfCFL-Match and \textsfTurbo\textsubscriptiso convert a query graph into a spanning tree for obtaining candidates for each query vertex and obtaining a good matching order with the spanning tree. However, by using the spanning tree instead of the original query graph, it could lead to lower pruning power and a sub-optimal matching order. Another limitation is that they perform redundant computation in search without utilizing the knowledge learned from past computation. In this paper, we introduce three novel concepts to address these inherent limitations: 1) dynamic programming between a directed acyclic graph (DAG) and a graph, 2) adaptive matching order with DAG ordering, and 3) pruning by failing sets, which together lead to a much faster algorithm \textsfDAF for subgraph matching. Extensive experiments with real datasets show that \textsfDAF outperforms the fastest existing solution by up to orders of magnitude in terms of recursive calls as well as in terms of the elapsed time.
Year
DOI
Venue
2019
10.1145/3299869.3319880
Proceedings of the 2019 International Conference on Management of Data
Keywords
Field
DocType
adaptive matching order, dynamic programming, failing set, subgraph isomorphism, subgraph matching
Dynamic programming,Data mining,Vertex (geometry),Computer science,Power graph analysis,Directed acyclic graph,Theoretical computer science,Spanning tree,Subgraph isomorphism problem,Recursion,Computation
Conference
ISSN
ISBN
Citations 
0730-8078
978-1-4503-5643-5
10
PageRank 
References 
Authors
0.46
0
5
Name
Order
Citations
PageRank
Myoungji Han1111.50
Hyun-joon Kim29310.19
Geonmo Gu3102.15
Kunsoo Park41396171.00
Wook-Shin Han580557.85