Differentiable Reasoning on Large Knowledge Bases and Natural Language

Pasquale Minervini, Matko Bosnjak, Tim Rocktäschel, Sebastian Riedel, Edward Grefenstette

Abstract

Reasoning with knowledge expressed in natural language and Knowledge Bases (KBs) is a major challenge for Artificial Intelligence, with applications in machine reading, dialogue, and question answering. General neural architectures that jointly learn representations and transformations of text are very data-inefficient, and it is hard to analyse their reasoning process. These issues are addressed by end-to-end differentiable reasoning systems such as Neural Theorem Provers (NTPs), although they can only be used with small-scale symbolic KBs. In this paper we first propose Greedy NTPs (GNTPs), an extension to NTPs addressing their complexity and scalability limitations, thus making them applicable to real-world datasets. This result is achieved by dynamically constructing the computation graph of NTPs and including only the most promising proof paths during inference, thus obtaining orders of magnitude more efficient models. Then, we propose a novel approach for jointly reasoning over KBs and textual mentions, by embedding logic facts and natural language sentences in a shared embedding space. We show that GNTPs perform on par with NTPs at a fraction of their cost while achieving competitive link prediction results on large datasets, providing explanations for predictions, and inducing interpretable models.

Introduction

Traditional Artificial Intelligence is often divided into symbolic reasoning, which is interpretable but brittle, and neural networks, which are robust but lack transparency. Neural Theorem Provers (NTPs) were developed to combine these paradigms using differentiable unification, allowing models to learn matches between similar concepts (e.g., "is located in" and "is situated in") while following logical rules. However, NTPs suffer from a computational explosion because they explore every possible proof path, limiting their use to small, toy datasets.

Greedy Neural Theorem Provers (GNTPs)

To overcome these scalability limitations, we introduce Greedy NTPs (GNTPs). The core innovation is the use of k-nearest neighbor (k-NN) search to prune the search space during the reasoning process. Instead of exploring all paths, GNTPs identify only the $k$ most promising facts and rules. By framing logical unification as a vector similarity problem, GNTPs can utilize efficient indexing structures to perform inference in sub-linear time.

Architecture of Greedy Neural Theorem Provers (GNTPs) for joint reasoning over KBs and text.

Joint Reasoning over Text and KBs

GNTPs introduce a differentiable text encoder that allows natural language sentences to be treated as logical predicates. By embedding structured KB facts and unstructured text mentions into a shared vector space, the model can reason across both formats seamlessly. This enables the induction of rules that bridge symbolic and textual evidence, such as: locatedIn(X, Y) :- "X is a neighboring state to Z"(X, Z), "Z is located in Y"(Z, Y).

Experimental Results

The authors evaluated GNTPs on various benchmarks, including small reasoning tasks (Kinship, Nations) and large-scale KBs (WN18, FB122).

Efficiency and Scalability

GNTPs are significantly more efficient than standard NTPs, achieving speedups of over 100x on certain datasets. Crucially, GNTPs successfully trained on large-scale datasets like WN18 and FB122, which are impossible for standard NTPs to process due to memory constraints. The model successfully "decoded" learned rules, such as the transitivity of the isa relation in medical datasets.

Performance on Textual Mentions

The model's ability to reason with natural language was tested on a modified "Countries" dataset where some KB facts were replaced with human-generated sentences.

Performance comparison on the Countries dataset with textual mentions (with attention).

As shown in the results with attention, the "Facts and Mentions" strategy consistently outperforms using facts alone, particularly as the number of held-out triples increases. This demonstrates that the model successfully leverages textual information to fill gaps in the symbolic knowledge base.

Conclusion

GNTPs represent a significant advancement in neuro-symbolic AI by making differentiable reasoning scalable to real-world datasets. By integrating k-NN search and joint embeddings for text and KBs, the model achieves high performance while maintaining interpretability through induced logical rules. Future work includes exploring more sophisticated text encoders like Transformers and deeper proof paths.

Summary updated

Abstract

Reasoning with knowledge expressed in natural language and Knowledge Bases (KBs) is a major challenge for Artificial Intelligence, with applications in machine reading, dialogue, and question answering. General neural architectures that jointly learn representations and transformations of text are very data-inefficient, and it is hard to analyse their reasoning process. These issues are addressed by end-to-end differentiable reasoning systems such as Neural Theorem Provers (NTPs), although they can only be used with small-scale symbolic KBs. In this paper we first propose Greedy NTPs (GNTPs), an extension to NTPs addressing their complexity and scalability limitations, thus making them applicable to real-world datasets. This result is achieved by dynamically constructing the computation graph of NTPs and including only the most promising proof paths during inference, thus obtaining orders of magnitude more efficient models. Then, we propose a novel approach for jointly reasoning over KBs and textual mentions, by embedding logic facts and natural language sentences in a shared embedding space. We show that GNTPs perform on par with NTPs at a fraction of their cost while achieving competitive link prediction results on large datasets, providing explanations for predictions, and inducing interpretable models. Source code, datasets, and supplementary material are available online at https://github.com/uclnlp/gntp.
BibTeX
@inproceedings{minervini2020differentiable,
  author = {Pasquale Minervini and Matko Bosnjak and Tim Rocktäschel and Sebastian Riedel and Edward Grefenstette},
  title = {{Differentiable Reasoning on Large Knowledge Bases and Natural Language}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=iAaM5fHi6d},
}
Figure