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

In the quest for Artificial Intelligence, two paradigms often clash: Neural Models, which are robust to noise but operate as "black boxes," and Symbolic Reasoning, which is interpretable and data-efficient but brittle and hard to scale. Neural Theorem Provers (NTPs) were designed to bridge these worlds by turning logical "backward chaining" into a differentiable neural network. However, original NTPs suffered from a combinatorial explosion; to prove a single fact, they attempted to unify a goal with every fact and rule in a Knowledge Base (KB), making them unusable for real-world datasets. Furthermore, much of human knowledge is trapped in natural language text, which traditional symbolic systems cannot process directly.

Methods: Greedy Neural Theorem Provers

To address these scalability and data-source limitations, the authors introduce Greedy NTPs (GNTPs). The architecture relies on three primary innovations:

  1. Fact and Rule Selection via k-NN: Instead of exhaustive comparison, GNTPs treat unification as a Nearest Neighbor Search (NNS). By using efficient L2-distance search, the model only considers the $k_f$ most promising facts and $k_r$ most relevant rules. This transforms the complexity from $O(|KB|)$ to $O(1)$ per proof step.
  2. Attention-Based Rule Induction: To learn rules efficiently, an attention mechanism is used over known predicates. This allows the model to learn which relations (like locatedIn) should fill slots in a rule template (e.g., H(X,Y) :- B1(X,Z), B2(Z,Y)) without a parameter explosion.
  3. The Reading Component: To reason over text, GNTPs treat textual "surface patterns" (e.g., "X is located in the Y") as predicates. A Bag-of-Embeddings encoder maps these patterns into the same vector space as symbolic relations, allowing the model to "read" a sentence and use it as a logical proof step.
Figure 1: The GNTP architecture showing the integration of KB representations, text representations, and rule induction via k-NN selection.

Key Results and Insights

The authors evaluated GNTPs across various benchmarks, including small-scale symbolic datasets (Countries, Kinship) and large-scale KBs (WN18, FB122).

Efficiency and Scalability: GNTPs are orders of magnitude faster than original NTPs. On the WN18 dataset, where original NTPs would run out of memory, GNTPs trained efficiently on a single GPU. On the FB122 dataset, GNTPs achieved an MRR of 0.977, outperforming standard neural link predictors like DistMult (0.874) and ComplEx (0.887).

Text Integration: The "Reading Component" consistently improved performance when relations were replaced by natural language text. By embedding text mentions and symbolic relations in a shared space, the model successfully induced logical rules that bridge language and logic, such as neighborOf(X, Y) :- "Y is a neighboring state to X"(X, Y).

Figure 5: AUC-PR results on the Countries dataset with textual mentions, demonstrating that the 'Facts and Mentions' strategy (blue) maintains higher performance as more triples are held out compared to 'Facts' alone (orange).

Interpretability: Unlike "black box" predictors, GNTPs provide a human-readable proof path. If the model predicts a relationship, it can display the specific rules, facts, or text snippets used to derive that conclusion. Pruning via k-NN was found to not only improve speed but also accuracy by ignoring low-probability, noisy proof paths.

Conclusion

GNTPs represent a significant step toward scalable, interpretable neuro-symbolic reasoning. By combining efficient k-NN search with a differentiable reading component, the model can reason across massive knowledge bases and natural language simultaneously. Future work includes automating the discovery of rule structures to remove dependency on pre-defined templates and utilizing more sophisticated text encoders like Transformers to capture deeper linguistic context.

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 1. 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.
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