# Mining Path Association Rules in Large Property Graphs (with Appendix)

arXiv: https://arxiv.org/abs/2408.02029 · HTML: https://mlsanity.com/paper/2408.02029/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 81 references that are in the map.
- First posted on arXiv 4 Aug 2024.

## Builds on (most cited first, 9 of 9)

- [Collecting a Large-Scale Gender Bias Dataset for Coreference Resolution and Machine Translation](https://mlsanity.com/paper/2109.03858/) (2021)
- [Reinforced Anytime Bottom Up Rule Learning for Knowledge Graph Completion](https://mlsanity.com/paper/2004.04412/) (2020)
- [Foundations of Modern Query Languages for Graph Databases](https://mlsanity.com/paper/1610.06264/) (2016)
- [Measuring Social Bias in Knowledge Graph Embeddings](https://mlsanity.com/paper/1912.02761/) (2019)
- [An Analytical Study of Large SPARQL Query Logs](https://mlsanity.com/paper/1708.00363/) (2017)
- [Rule Mining over Knowledge Graphs via Reinforcement Learning](https://mlsanity.com/paper/2202.10381/) (2022)
- [Language-aware Indexing for Conjunctive Path Queries](https://mlsanity.com/paper/2003.03079/) (2020)
- [The LDBC Graphalytics Benchmark](https://mlsanity.com/paper/2011.15028/) (2020)
- [Computational Complexity of Three Central Problems in Itemset Mining](https://mlsanity.com/paper/2012.02619/) (2020)

## Abstract (arXiv)

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 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.