LPRules: Rule Induction in Knowledge Graphs Using Linear Programming
  Knowledge graph (KG) completion is a well-studied problem in AI. Rule-based
methods and embedding-based methods form two of the solution techniques.
Rule-based methods learn first-order logic rules that capture existing facts in
an input graph and then use these rules for reasoning about missing facts. A
major drawback of such methods is the lack of scalability to large datasets. In
this paper, we present a simple linear programming (LP) model to choose rules
from a list of candidate rules and assign weights to them. For smaller KGs, we
use simple heuristics to create the candidate list. For larger KGs, we start
with a small initial candidate list, and then use standard column generation
ideas to add more rules in order to improve the LP model objective value. To
foster interpretability and generalizability, we limit the complexity of the
set of chosen rules via explicit constraints, and tune the complexity
hyperparameter for individual datasets. We show that our method can obtain
state-of-the-art results for three out of four widely used KG datasets, while
taking significantly less computing time than other popular rule learners
including some based on neuro-symbolic methods. The improved scalability of our
method allows us to tackle large datasets such as YAGO3-10.
