Mining Path Association Rules in Large Property Graphs (with Appendix)
This work addresses the need for discovering regular path patterns in large property graphs, which is incremental as it extends association rule mining to a new graph-based context.
The paper tackles the problem of mining frequent path regularities from large property graphs with edge labels and vertex attributes, introducing path association rule mining (PARM) and developing an efficient algorithm called PIONEER that exploits anti-monotonicity for pruning, with experimental verification on real-world data showing its significance and efficiency.
How can we mine frequent path regularities from a graph with edge labels and vertex attributes? The task of association rule mining successfully discovers regular patterns in item sets and substructures. Still, to our best knowledge, this concept has not yet been extended to path patterns in large property graphs. In this paper, we introduce the problem of path association rule mining (PARM). Applied to any \emph{reachability path} between two vertices within a large graph, PARM discovers regular ways in which path patterns, identified by vertex attributes and edge labels, co-occur with each other. We develop an efficient and scalable algorithm PIONEER that exploits an anti-monotonicity property to effectively prune the search space. Further, we devise approximation techniques and employ parallelization to achieve scalable path association rule mining. Our experimental study using real-world graph data verifies the significance of path association rules and the efficiency of our solutions.