  Subgraph matching is a compute-intensive problem that asks to enumerate all
the isomorphic embeddings of a query graph within a data graph. This problem is
generally solved with backtracking, which recursively evolves every possible
partial embedding until it becomes an isomorphic embedding or is found unable
to become it. While existing methods reduce the search space by analyzing graph
structures before starting the backtracking, it is often ineffective for
complex graphs. In this paper, we propose an efficient algorithm for subgraph
matching that performs on-the-fly pruning during the backtracking. Our main
idea is to `learn from failure'. That is, our algorithm generates failure
patterns when a partial embedding is found unable to become an isomorphic
embedding. Then, in the subsequent process of the backtracking, our algorithm
prunes partial embeddings matched with a failure pattern. This pruning does not
change the result because failure patterns are designed to represent the
conditions that never yield an isomorphic embedding. Additionally, we introduce
an efficient representation of failure patterns for constant-time pattern
matching. The experimental results show that our method improves the
performance by up to 10000 times than existing methods.
