mlsanityData to 7 Oct 2026

Rule Induction in Knowledge Graphs Using Linear Programming

arXiv 2110.08245 ↗First posted 15 Oct 2021cs.AI cs.LGcited by 4

Not on the map. Why?

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.

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

Builds on

31 of 62 references.

References · 31

  1. 2019A Survey on Bias and Fairness in Machine Learningcited by 1,911
  2. 2014Embedding Entities and Relations for Learning and Inference in Knowledge Basescited by 929
  3. 2016Complex Embeddings for Simple Link Predictioncited by 897
  4. 2019RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Spacecited by 893
  5. 2017Convolutional 2D Knowledge Graph Embeddingscited by 729
  6. 2020A Survey on Knowledge Graphs: Representation, Acquisition and Applicationscited by 643
  7. 2021Interpretable Machine Learning: Fundamental Principles and 10 Grand Challengescited by 364
  8. 2019TuckER: Tensor Factorization for Knowledge Graph Completioncited by 290
  9. 2017DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoningcited by 265
  10. 2019Inductive Relation Prediction by Subgraph Reasoningcited by 237
  11. 2017Learning Explanatory Rules from Noisy Datacited by 210
  12. 2020Low-Dimensional Hyperbolic Knowledge Graph Embeddingscited by 195
19 more
  1. 2019DRUM: End-To-End Differentiable Rule Mining On Knowledge Graphscited by 173
  2. 2017Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learningcited by 161
  3. 2018Canonical Tensor Decomposition for Knowledge Base Completioncited by 150
  4. 2020RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphscited by 117
  5. 2018Multi-Hop Knowledge Graph Reasoning with Reward Shapingcited by 102
  6. 2018Boolean Decision Rules via Column Generationcited by 79
  7. 2019A Re-evaluation of Knowledge Graph Completion Methodscited by 73
  8. 2020Learning programs by learning from failurescited by 73
  9. 2019Probabilistic Logic Neural Networks for Reasoningcited by 69
  10. 2017Knowledge Graph Embedding with Iterative Guidance from Soft Rulescited by 51
  11. 2019Learn to Explain Efficiently via Neural Logic Inductive Learningcited by 38
  12. 2021Universal Representation Learning of Knowledge Bases by Jointly Embedding Instances and Ontological Conceptscited by 37
  13. 2018Improving Knowledge Graph Embedding Using Simple Constraintscited by 36
  14. 2018M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Searchcited by 34
  15. 2020Survey of explainable machine learning with visual and granular methods beyond quasi-explanationscited by 20
  16. 20205* Knowledge Graph Embeddings with Projective Transformationscited by 19
  17. 2020On the Ambiguity of Rank-Based Evaluation of Entity Alignment or Link Prediction Methodscited by 13
  18. 2020Type-augmented Relation Prediction in Knowledge Graphscited by 12
  19. 2019LogicENN: A Neural Based Knowledge Graphs Embedding Model with Logical Rulescited by 8

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 2; 2024: 1.

4 papers.

  1. 2023Neurosymbolic AI for Reasoning over Knowledge Graphs: A Surveycited by 21
  2. 2022Efficient Learning of Interpretable Classification Rulescited by 5
  3. 2023Neurosymbolic AI for Reasoning on Biomedical Knowledge Graphscited by 4
  4. 2024MARS: A neurosymbolic approach for interpretable drug discoverycited by 2