  Graph pattern matching, one of the fundamental graph mining problems, aims to
extract structural patterns of interest from an input graph. The
state-of-the-art graph matching algorithms and systems are mainly designed for
undirected graphs. Directed graph matching is more complex than undirected
graph matching because the edge direction must be taken into account before the
exploration of each directed edge. Thus, the technologies (e.g. storage,
exploiting symmetry for graph matching) for undirected graph matching may not
be fully applicable to directed graphs. For example, the redundancy implied in
directed graph pattern can not be detected using the symmetry breaking for
undirected pattern graph. Here, we present XMiner for efficient directed graph
pattern matching whose core idea is 'pattern reduction'. It first analyzes the
relationship between constraints implied in a pattern digraph. Then it reduces
the pattern graph into a simplified form by finding a minimum constraint cover.
Finally, XMiner generates an execution plan and follows it to extract matchings
of the pattern graph. So, XMiner works on simplified pattern graph and avoids
much data access and redundant computation throughout the matching process. Our
experimental results show that XMiner outperforms state-of the-art stand-alone
graph matching systems, and scales to complex graph pattern matching tasks on
larger graph.
