End-to-end Differentiable Proving

Tim Rocktäschel, Sebastian Riedel

Abstract

We introduce neural networks for end-to-end differentiable proving of queries to knowledge bases by operating on dense vector representations of symbols. These neural networks are constructed recursively by taking inspiration from 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. By using gradient descent, the resulting neural network can be trained to infer facts from a given incomplete knowledge base. It learns to (i) place representations of similar symbols in close proximity in a vector space, (ii) make use of such similarities to prove queries, (iii) induce logical rules, and (iv) use provided and induced logical rules for multi-hop reasoning. We demonstrate that this architecture outperforms ComplEx, a state-of-the-art neural link prediction model, on three out of four benchmark knowledge bases while at the same time inducing interpretable function-free first-order logic rules.

Introduction

Knowledge Base (KB) completion—the task of predicting missing links between entities—has traditionally been split between two paradigms: Neural Link Prediction and Symbolic Logic. Neural models like ComplEx excel at capturing subsymbolic similarities through vector embeddings but struggle with multi-step reasoning. Conversely, symbolic systems like Prolog perform robust multi-hop reasoning using hard-coded rules but are brittle and cannot easily learn from raw, noisy data.

Neural Theorem Provers (NTPs) bridge this gap by turning Prolog's backward chaining algorithm into a differentiable neural network. By replacing strict symbolic matching with vector similarity, NTPs can learn to induce interpretable logic rules and perform multi-hop reasoning directly from data using gradient descent.

Methods

The core innovation of the NTP is the reimplementation of the recursive structure of Prolog’s backward chaining (specifically OR and AND operations) as a computation graph.

Differentiable Unification

In standard logic, symbols must be identical to "unify." In an NTP, symbols are represented as vectors, and the model uses a Radial Basis Function (RBF) kernel to calculate a similarity score. This transforms the success of a proof into a continuous value between 0 and 1, allowing gradients to flow back through the proof structure.

A trace of the differentiable proving process showing how queries are recursively decomposed and unified.

Rule Induction and Optimization

Instead of relying solely on human-written rules, the model uses "rule templates" with placeholder predicates (e.g., #1(X, Y) :- #2(X, Z), #3(Z, Y)). During training, the model learns vector embeddings for these placeholders, effectively inducing logic rules like transitivity. To manage the computational complexity of proving, the authors utilize batch proving on GPUs and a K-max heuristic to maintain only the most promising proof paths.

Experimental Results

The model was evaluated on four benchmark Knowledge Bases: Countries, Kinship, Nations, and UMLS. A hybrid training approach, NTPλ, was used where a standard link prediction model (ComplEx) provided an auxiliary loss to accelerate the learning of symbol embeddings.

Performance comparison between ComplEx, NTP, and NTPλ, alongside examples of induced logical rules.

NTPλ outperformed the state-of-the-art ComplEx model on three out of four datasets. Notably, on the "Countries S3" task—which requires a three-hop reasoning chain—NTPλ achieved an AUC-PR of 77.26, significantly higher than ComplEx's 48.44. Beyond raw performance, the model successfully "rediscovered" known logical rules, such as the transitivity of the interacts_with relation in the UMLS dataset.

Conclusion and Future Work

NTPs demonstrate that discrete algorithms can serve as effective templates for neural architectures, providing a built-in inductive bias for reasoning while remaining interpretable. However, scalability remains a challenge as the computation graph grows exponentially with proof depth. Future research may explore Reinforcement Learning or hierarchical attention mechanisms to navigate the proof space more efficiently, as well as extending the framework to support complex function terms.

Summary updated

Abstract

We introduce neural networks for end-to-end differentiable proving of queries to knowledge bases by operating on dense vector representations of symbols. These neural networks are constructed recursively by taking inspiration from 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. By using gradient descent, the resulting neural network can be trained to infer facts from a given incomplete knowledge base. It learns to (i) place representations of similar symbols in close proximity in a vector space, (ii) make use of such similarities to prove queries, (iii) induce logical rules, and (iv) use provided and induced logical rules for multi-hop reasoning. We demonstrate that this architecture outperforms ComplEx, a state-of-the-art neural link prediction model, on three out of four benchmark knowledge bases 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