  Graph association rule mining is a data mining technique used for discovering
regularities in graph data. In this study, we propose a novel concept, {\it
path association rule mining}, to discover the correlations of path patterns
that frequently appear in a given graph. Reachability path patterns (i.e.,
existence of paths from a vertex to another vertex) are applied in our concept
to discover diverse regularities. We show that the problem is NP-hard, and we
develop an efficient algorithm in which the anti-monotonic property is used on
path patterns. Subsequently, we develop approximation and parallelization
techniques to efficiently and scalably discover rules. We use real-life graphs
to experimentally verify the effective
