# Rule Induction in Knowledge Graphs Using Linear Programming

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 62 references that are in the map.
- First posted on arXiv 15 Oct 2021.

## Builds on (most cited first, 30 of 31)

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [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)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [Interpretable Machine Learning: Fundamental Principles and 10 Grand Challenges](https://mlsanity.com/paper/2103.11251/) (2021)
- [TuckER: Tensor Factorization for Knowledge Graph Completion](https://mlsanity.com/paper/1901.09590/) (2019)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [Low-Dimensional Hyperbolic Knowledge Graph Embeddings](https://mlsanity.com/paper/2005.00545/) (2020)
- [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)
- [Canonical Tensor Decomposition for Knowledge Base Completion](https://mlsanity.com/paper/1806.07297/) (2018)
- [RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2010.04029/) (2020)
- [Multi-Hop Knowledge Graph Reasoning with Reward Shaping](https://mlsanity.com/paper/1808.10568/) (2018)
- [Boolean Decision Rules via Column Generation](https://mlsanity.com/paper/1805.09901/) (2018)
- [A Re-evaluation of Knowledge Graph Completion Methods](https://mlsanity.com/paper/1911.03903/) (2019)
- [Learning programs by learning from failures](https://mlsanity.com/paper/2005.02259/) (2020)
- [Probabilistic Logic Neural Networks for Reasoning](https://mlsanity.com/paper/1906.08495/) (2019)
- [Knowledge Graph Embedding with Iterative Guidance from Soft Rules](https://mlsanity.com/paper/1711.11231/) (2017)
- [Learn to Explain Efficiently via Neural Logic Inductive Learning](https://mlsanity.com/paper/1910.02481/) (2019)
- [Universal Representation Learning of Knowledge Bases by Jointly Embedding Instances and Ontological Concepts](https://mlsanity.com/paper/2103.08115/) (2021)
- [Improving Knowledge Graph Embedding Using Simple Constraints](https://mlsanity.com/paper/1805.02408/) (2018)
- [M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search](https://mlsanity.com/paper/1802.04394/) (2018)
- [Survey of explainable machine learning with visual and granular methods beyond quasi-explanations](https://mlsanity.com/paper/2009.10221/) (2020)
- [5* Knowledge Graph Embeddings with Projective Transformations](https://mlsanity.com/paper/2006.04986/) (2020)
- [On the Ambiguity of Rank-Based Evaluation of Entity Alignment or Link Prediction Methods](https://mlsanity.com/paper/2002.06914/) (2020)
- [Type-augmented Relation Prediction in Knowledge Graphs](https://mlsanity.com/paper/2009.07938/) (2020)

## Built on by (most cited first, 4 of 4)

- [Neurosymbolic AI for Reasoning over Knowledge Graphs: A Survey](https://mlsanity.com/paper/2302.07200/) (2023)
- [Efficient Learning of Interpretable Classification Rules](https://mlsanity.com/paper/2205.06936/) (2022)
- [Neurosymbolic AI for Reasoning on Biomedical Knowledge Graphs](https://mlsanity.com/paper/2307.08411/) (2023)
- [MARS: A neurosymbolic approach for interpretable drug discovery](https://mlsanity.com/paper/2410.05289/) (2024)

## Abstract (arXiv)

We present a simple linear programming (LP) based method to learn compact and interpretable sets of rules encoding the facts in a knowledge graph (KG) and use these rules to solve the KG completion problem. Our LP model chooses a set of rules of bounded complexity from a list of candidate first-order logic rules and assigns weights to them. The complexity bound is enforced via explicit constraints. We combine simple rule generation heuristics with our rule selection LP to obtain predictions with accuracy comparable to state-of-the-art codes, even while generating much more compact rule sets. Furthermore, when we take as input rules generated by other codes, we often improve interpretability by reducing the number of chosen rules, while maintaining accuracy.