End-to-end Differentiable Proving

Tim Rocktäschel, Sebastian Riedel

TL;DR

Researchers have developed Neural Theorem Provers (NTPs), a novel architecture that makes symbolic logic "fuzzy" and differentiable. By replacing discrete unification with vector similarity, NTPs can learn logical rules and perform multi-hop reasoning directly from data. This approach outperforms state-of-the-art link prediction models on complex reasoning tasks while remaining entirely human-interpretable.

The Challenge of Knowledge Base Completion

Automated Knowledge Base (KB) completion—predicting missing facts like grandfatherOf(ABE, BART)—traditionally falls into two distinct camps, each with significant trade-offs:

  1. Neural Link Prediction: Models like ComplEx learn "subsymbolic" representations (dense vector embeddings). They excel at recognizing similarities (e.g., that grandfatherOf is semantically close to grandpaOf), but they struggle with complex, multi-step reasoning (e.g., explicitly understanding that "a parent of a parent is a grandfather").
  2. Symbolic Logic: Systems like Prolog use hard-coded rules to perform multi-hop reasoning perfectly. However, they are brittle; if a symbol is slightly different, the logic breaks. Furthermore, they cannot easily learn new representations or rules directly from raw, noisy data.

The authors aim to bridge this gap, creating a system that possesses the rigorous reasoning depth of a theorem prover and the learning flexibility of a neural network.

Methods: The Neural Theorem Prover

The core innovation is the Neural Theorem Prover (NTP). The authors take Prolog’s backward chaining algorithm—which recursively breaks a goal into sub-goals using OR and AND operations—and reimplement it as a differentiable neural network.

  • Differentiable Unification: In standard logic, two symbols must be identical to "unify" (match). NTPs replace this strict matching with a Radial Basis Function (RBF) kernel that compares the vector embeddings of symbols. If the vectors are close in space, the "unification" succeeds with a high continuous score.
  • Recursive Construction: For a specific query, the model dynamically builds a computation graph representing all possible proof paths up to a predefined depth.
Differentiable backward chaining proof tree for a grandfatherOf query.
  • Neural Inductive Logic Programming (ILP): Instead of requiring hard-coded rules, users can provide "rule templates" (e.g., P(X, Y) :- Q(X, Z), R(Z, Y)). The model then uses gradient descent to learn which actual predicates (like fatherOf or parentOf) best fit those templates to solve the task.
  • NTP$\lambda$ (Hybrid Training): To handle the "cold start" problem where embeddings are initially random, the authors jointly train the NTP with ComplEx. ComplEx helps the model learn basic similarities, while the NTP focuses on the multi-hop logic.

Key Insights

  • Reasoning as Computation: By making the proving process differentiable, the "success" of a proof becomes a continuous value. This allows the model to "backpropagate" through a logical argument to update symbol embeddings.
  • Interpretability by Design: Unlike most "black box" neural networks, NTPs are highly interpretable. After training, you can look at the learned embeddings for the rule templates and decode them back into human-readable logic, such as: locatedIn(X, Y) :- neighborOf(X, Z), locatedIn(Z, Y).
  • The Power of Similarity: Because the model operates on embeddings, a single learned rule can generalize. If the model learns a rule for fatherOf, it can automatically apply it to dadOf if their vectors are similar.

Key Results

The authors evaluated their model on four benchmark Knowledge Bases: Countries (designed to test multi-hop reasoning), Kinship, Nations, and UMLS (biomedical concepts).

Performance comparison on benchmark datasets and examples of induced logical rules.
  • Superior Performance: The hybrid model (NTP$\lambda$) outperformed the state-of-the-art ComplEx model on three out of four datasets.
  • Solving Multi-hop Tasks: On the "Countries S3" task, which requires complex three-hop reasoning, NTP$\lambda$ achieved an AUC-PR of 77.26, significantly higher than ComplEx's 48.44.
  • Rule Induction: The model successfully induced complex rules. For example, in the UMLS dataset, it discovered transitivity rules for the interacts_with and isa predicates with high confidence.

Limitations and Future Work

  • Computational Complexity: Constructing a neural network for every possible proof path is computationally expensive. While the authors introduced optimizations like batching and gradient sparsification, scaling NTPs to massive KBs (like Wikidata or Freebase) remains a significant challenge.
  • Function-Free Logic: The current implementation only supports function-free first-order logic. The authors express interest in supporting function terms in the future.
  • Search Heuristics: Future versions could benefit from advanced search techniques, such as Monte Carlo tree search, to navigate the proof space more efficiently without exhaustively building the entire graph.

Summary updated

Abstract

We introduce deep neural networks for end-to-end differentiable theorem proving that operate on dense vector representations of symbols. These neural networks are recursively constructed by following the backward chaining algorithm as used in Prolog. Specifically, we replace symbolic unification with a differentiable computation on vector representations of symbols using a radial basis function kernel, thereby combining symbolic reasoning with learning subsymbolic vector representations. The resulting neural network can be trained to infer facts from a given incomplete knowledge base using gradient descent. By doing so, it learns to (i) place representations of similar symbols in close proximity in a vector space, (ii) make use of such similarities to prove facts, (iii) induce logical rules, and (iv) it can use provided and induced logical rules for complex multi-hop reasoning. On four benchmark knowledge bases we demonstrate that this architecture outperforms ComplEx, a state-of-the-art neural link prediction model, while at the same time inducing interpretable function-free first-order logic rules.
BibTeX
@inproceedings{rocktaschel2017end,
  author = {Tim Rocktäschel and Sebastian Riedel},
  title = {{End-to-end Differentiable Proving}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=SJZQADb_Zr},
}
Figure