# MPRM: A Markov Path-based Rule Miner for Efficient and Interpretable Knowledge Graph Reasoning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 49 references that are in the map.
- First posted on arXiv 18 May 2025.

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

- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space](https://mlsanity.com/paper/1902.10197/) (2019)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphs](https://mlsanity.com/paper/1911.00055/) (2019)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Multi-Hop Knowledge Graph Reasoning with Reward Shaping](https://mlsanity.com/paper/1808.10568/) (2018)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Knowledge Graph Completion via Complex Tensor Factorization](https://mlsanity.com/paper/1702.06879/) (2017)
- [Knowledge Graphs: Opportunities and Challenges](https://mlsanity.com/paper/2303.13948/) (2023)
- [Modeling Relation Paths for Representation Learning of Knowledge Bases](https://mlsanity.com/paper/1506.00379/) (2015)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Knowledge Graph Contrastive Learning Based on Relation-Symmetrical Structure](https://mlsanity.com/paper/2211.10738/) (2022)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search](https://mlsanity.com/paper/1802.04394/) (2018)
- [HousE: Knowledge Graph Embedding with Householder Parameterization](https://mlsanity.com/paper/2202.07919/) (2022)
- [Variational Knowledge Graph Reasoning](https://mlsanity.com/paper/1803.06581/) (2018)
- [Rule-Guided Compositional Representation Learning on Knowledge Graphs](https://mlsanity.com/paper/1911.08935/) (2019)
- [Learning to Walk with Dual Agents for Knowledge Graph Reasoning](https://mlsanity.com/paper/2112.12876/) (2021)
- [Brain-inspired Search Engine Assistant based on Knowledge Graph](https://mlsanity.com/paper/2012.13529/) (2020)
- [Best-Effort Inductive Logic Programming via Fine-grained Cost-based Hypothesis Generation](https://mlsanity.com/paper/1707.02729/) (2017)
- [Generalizing Knowledge Graph Embedding with Universal Orthogonal Parameterization](https://mlsanity.com/paper/2405.08540/) (2024)
- [RulE: Knowledge Graph Reasoning with Rule Embedding](https://mlsanity.com/paper/2210.14905/) (2022)
- [KnowFormer: Revisiting Transformers for Knowledge Graph Reasoning](https://mlsanity.com/paper/2409.12865/) (2024)

## Abstract (arXiv)

Rule mining in knowledge graphs enables interpretable link prediction. However, deep learning-based rule mining methods face significant memory and time challenges for large-scale knowledge graphs, whereas traditional approaches, limited by rigid confidence metrics, incur high computational costs despite sampling techniques. To address these challenges, we propose MPRM, a novel rule mining method that models rule-based inference as a Markov chain and uses an efficient confidence metric derived from aggregated path probabilities, significantly lowering computational demands. Experiments on multiple datasets show that MPRM efficiently mines knowledge graphs with over a million facts, sampling less than 1% of facts on a single CPU in 22 seconds, while preserving interpretability and boosting inference accuracy by up to 11% over baselines.