PaperlayerView exact revision on arXiv

Source-linked AI summary

Differentiable Reasoning on Large Knowledge Bases and Natural Language

Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, Edward Grefenstette

arXiv:1912.10824v1cs.LGcs.CLcs.LO

TL;DR

Reasoning over natural-language knowledge and large KBs is challenging because general neural systems are data-inefficient and difficult to analyze, while NTPs are limited to small symbolic KBs. The paper proposes GNTPs, which dynamically retain the most promising proof paths and jointly embed logic facts with textual mentions. GNTPs achieve similar or better predictive performance than NTPs at several orders of magnitude lower computational cost, while supporting large-scale explanations and interpretable models.

  • Problem

    Reasoning over noisy natural-language knowledge and large KBs remains difficult because neural systems are data-inefficient and hard to analyze, while NTPs do not scale beyond small symbolic KBs.

    Source: Introduction · p. 1, on Large-Scale KBs · p. 3, Conclusions · p. 7

  • Method

    GNTPs dynamically construct NTP computation graphs using only the most promising proof paths and jointly embed logic atoms with textual mentions through a differentiable reading component.

    Source: Introduction · p. 2, and Natural Language · p. 4, Conclusions · p. 7

  • Results

    GNTPs are more computationally efficient by several orders of magnitude while achieving similar or better predictive performance than NTPs and competitive link prediction results on large datasets.

    Source: Conclusions · p. 7, Results on Freebase and WordNet · p. 7

  • Takeaways & Limitations

    GNTPs enable end-to-end differentiable reasoning over large KBs and natural-language texts while providing proof-based explanations and interpretable models.

    Source: Conclusions · pp. 7–8

    The experiments correct previously reported NTP results because the original evaluation function produced artificially better performance.

    Source: Experiments · p. 6

Abstract

from arXiv · show

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.

Introduction

Reasoning over natural-language knowledge is difficult because text-derived KBs are incomplete, ambiguous, and noisy, while neural approaches can be data-inefficient and hard to explain. The paper addresses these limitations with efficient differentiable proving and a shared representation for symbolic facts and textual mentions.

Introduction

  • Text-derived KBs are incomplete, ambiguous, and noisy, while many neural reasoning methods require substantial annotated data and do not explain predictions.These limitations motivate combining neural robustness with symbolic reasoning and interpretability.Source: Introduction · p. 1
  • NTPs perform differentiable deductive reasoning by replacing discrete atom unification with similarity comparisons between embedding representations.They use Prolog-style backward chaining while retaining differentiability and interpretability.Source: Introduction · p. 1
  • GNTPs reduce NTP time and space complexity by pruning candidate proof paths and introducing attention for rule induction.The efficiency improvements target scalability while preserving the differentiable reasoning framework.Source: Introduction · p. 2
  • GNTPs extend differentiable reasoning to natural language by jointly embedding predicates and textual surface patterns with an end-to-end differentiable reading component.Figure 1 identifies the faster inference mechanism and text encoder as the two main architectural contributions.Source: Introduction · p. 2, Figure 1 · p. 2

End-to-end Differentiable Proving

NTPs construct differentiable proof networks by recursively unifying goals with facts and rule heads, proving rule bodies, and selecting the highest-scoring path. Their modules support interpretable rule learning and proof explanations through differentiable substitutions, scoring, and aggregation.

NTP Architecture

  • NTPs recursively enumerate proof paths using unification, mutually recursive OR and AND modules, and maximum-score aggregation.The OR module matches a goal against facts and rule heads, while the AND module proves the resulting rule-body sub-goals.Source: End-to-end Differentiable Proving · pp. 2–3

Unification Module

  • Differentiable unification compares atom embeddings with a Gaussian kernel, updates variable substitutions, and carries forward the minimum proof score.This permits semantically similar symbols such as locatedIn and situatedIn to match without discrete equality.Source: End-to-end Differentiable Proving · p. 2

OR Module

  • The OR module computes unification against all facts and rule heads, then recursively invokes the AND module on corresponding rule bodies.This recursive structure jointly enumerates candidate proof paths for a goal.Source: End-to-end Differentiable Proving · p. 2

AND Module

  • The AND module substitutes variables in each rule-body sub-goal, invokes the OR module, and recursively uses each resulting state to prove remaining sub-goals.The process continues through the rule body while tracking a bounded maximum proof depth.Source: End-to-end Differentiable Proving · p. 3

Training and Rule Learning

  • NTP training minimizes cross-entropy on final proof scores using masked facts and corrupted negative examples.The model learns embeddings and can decode interpretable rules from learned predicate representations.Source: End-to-end Differentiable Proving · p. 3

Efficient Differentiable Reasoning

GNTPs reduce NTP computation by selecting promising facts and rules instead of expanding every proof path, while preserving high-scoring proof search and improving parameter efficiency.

Problem

  • NTP proof enumeration is intractable because each sub-goal compares against all facts and rule heads, while rule expansion multiplies sub-goals and variable bindings.GNTPs therefore target selection of the k_f most useful facts and k_r most useful rules.Source: on Large-Scale KBs · p. 3

Large-Scale Inference

  • GNTP inference and training retain only the largest proof score, which is sufficient for the output and permits exact gradient calculation.This greedy computation avoids constructing all proof-path substructures.Source: on Large-Scale KBs · p. 3

Fact Selection

  • Nearest-neighbour search reduces fact comparisons from O(|K|) to O(1) by exploiting the Gaussian kernel’s monotonic relation to negative Euclidean distance.The method uses exact or approximate nearest-neighbour search to find supporting facts efficiently.Source: on Large-Scale KBs · p. 4

Rule Selection

  • Dynamic rule selection activates nearby rule heads sharing templates, recovering valid proofs while drastically reducing differentiable proving complexity.The heuristic balances symbolic exact matching against exhaustive differentiable exploration.Source: on Large-Scale KBs · p. 4

Implementation

  • Grouping facts and rules by shared templates enables efficient parallel inference on GPUs.The same grouping optimization was also used in prior NTP work.Source: on Large-Scale KBs · p. 4

Learning to Attend Over Predicates

  • Attention-based predicate embeddings replace k-dimensional rule parameters with c|R| parameters when |R| ≪ k, improving parameter efficiency.The attention mechanism defines rule-predicate embeddings as weighted combinations of known predicate embeddings.Source: on Large-Scale KBs · p. 4

Jointly Reasoning on Knowledge Bases

The model treats textual surface patterns between known entities as predicates and embeds them with logic facts and rules through a differentiable text encoder. A simple mean-pooled bag-of-embeddings encoder already achieves very accurate results.

Representation

  • Textual mentions become predicates linking entities, allowing facts, rules, and natural-language surface patterns to be represented jointly.For example, “United Kingdom borders with Ireland” becomes a relation between UK and IRELAND.Source: and Natural Language · p. 4

Text Encoder

  • A differentiable encoder maps each mention’s token sequence to a predicate embedding, using mean pooling over token embeddings in the reported model.The encoder is a simple Bag of Embeddings architecture, though other differentiable encoders are possible.Source: and Natural Language · p. 4

Results

  • The resulting model achieves very accurate results with the simple text encoder, while Figure 2 measures WN18 training time in seconds per epoch and marks missing entries as out-of-memory errors.The figure uses batches of 1000 examples on a GPU.Source: and Natural Language · p. 5, Figure 2 · p. 5

Related Work

Related work combines neural models with external memory, differentiable interpreters, shared embeddings, and graph-path methods to improve reasoning and generalization. The paper positions GNTPs among approaches addressing interpretability, scalability, and textual integration.

External Memory

  • Differentiable external-memory models represent and manipulate complex data structures, enabling supervision from program traces as well as input-output pairs.This line includes memory-augmented neural architectures such as neural Turing machines and related systems.Source: Related Work · p. 5

Differentiable Interpreters

  • Differentiable interpreters impose inductive biases through partially specified programs, but their computational complexity has limited them to smaller learning problems.Approximate nearest-neighbour structures have also been used to sparsify memory reads.Source: Related Work · p. 5

Knowledge Bases and Text

  • Prior work jointly embedded KB facts and textual mentions, while path and random-walk methods generally lacked rule induction mechanisms or textual surface-pattern integration.The paper distinguishes its approach from shared-embedding, graph-completion, and scalable rule-induction methods.Source: Related Work · p. 5

Experiments

GNTPs make differentiable reasoning substantially more scalable while preserving competitive link prediction, interpretable rules, and proof-based explanations across benchmark and larger knowledge-base settings. They also improve the integration of textual mentions when those mentions are encoded rather than merely added as facts.

Experiments

  • Proof-path pruning lets GNTPs train on large knowledge bases where NTPs quickly run out of memory, with additional experiments showing run-time improvements by several orders of magnitude.NTPs correspond to the unpruned special case of GNTPs, whereas GNTPs dynamically retain a smaller set of promising proof paths.Source: Experiments · p. 5
  • GNTPs achieve better or on-par link prediction results than NTPs, MINERVA, and NeuralLP across benchmark datasets while learning interpretable rules.The comparison covers Countries, Nations, UMLS, and Kinship; the learned rules also reveal domain structure such as transitive relations in UMLS.Source: Experiments · pp. 5–6, Table 1 · p. 6
  • Encoding textual mentions yields consistent ranking-accuracy improvements over simply adding those mentions as facts to the KB.The experiment replaces varying numbers of Countries training triples with generated mentions and compares fact-only integration against an encoder-based approach.Source: Experiments · p. 6, Figure 3 · p. 6

Results on Freebase and WordNet

  • On FB122, GNTPs outperform neural link predictors without supplied rules and perform on par with methods given all rules, including on the logic-focused Test-II subset.FB122 contains 9,738 entities, 122 relations, and 47 usable rules, but GNTPs must induce those rules from data.Source: Results on Freebase and WordNet · p. 7, Table 2 · p. 7
  • GNTP reaches 94.2 MRR on WN18 with hits@3, 5, 10 of 94.3, 94.4, 94.5, while its WN18RR MRR of 43.4 trails NeuralLP’s 46.3.On WN18RR, GNTP is close to ComplEx at 44.0 MRR; proof paths provide an interpretable account of predictions.Source: Results on Freebase and WordNet · p. 7
  • GNTP explanations expose human-readable rules and supporting facts, including induced relations for FB122 and semantic-similarity explanations such as CONGO being part of AFRICA.WN18 explanations are presented through proof paths with the largest proof scores.Source: Experiments · p. 6, Results on Freebase and WordNet · p. 7

Conclusions

GNTPs overcome NTP limitations by pruning proof paths during dynamic computation-graph construction. They retain predictive performance while enabling scalable, interpretable reasoning over large KBs and natural-language text.

  • GNTPs consider only the highest-scoring proof paths while dynamically constructing the computation graph, overcoming NTP scalability limits.Source: Conclusions · p. 7
  • GNTPs are several orders of magnitude more computationally efficient than NTPs while achieving similar or better predictive performance.Source: Conclusions · p. 7
  • GNTPs jointly embed logic atoms and textual mentions, enabling differentiable reasoning over large KBs and natural-language texts.Source: Conclusions · pp. 7–8
  • The models remain interpretable by providing explanations as logic proofs at scale.Source: Conclusions · p. 8

Datasets

The experiments evaluate GNTPs on benchmark datasets using AUC-PR, MRR, and HITS@m.

  • Experiments report Area Under the Precision-Recall Curve, MRR, and HITS@m as evaluation metrics.Source: Datasets · p. 9
  • The reported metrics assess model performance across the paper’s benchmark datasets.Source: Datasets · p. 9
  • MRR and HITS@m provide ranking-based evaluation alongside AUC-PR.Source: Datasets · p. 9

Countries, UMLS, Nations

The Countries dataset tests neural link-prediction reasoning over geographic facts, while Nations and UMLS provide additional relational benchmarks.

  • Countries contains 244 countries, 5 regions, 23 sub-regions, and 1158 neighborhood and location facts.Source: Countries, UMLS, Nations · p. 9
  • The Countries dataset contains 244 countries and is randomly split into 204 training countries, 20 development (validation) countries, and a test set.Source: Countries, UMLS, Nations · p. 9

20 countries

The experiments cover progressively difficult geographic reasoning tasks, textual-mention variants, relational benchmarks, large knowledge graphs, and computational efficiency. Across these settings, GNTP pruning supports scalable training while preserving competitive reasoning and prediction performance.

20 countries

  • Countries S1 removes test-country region facts and can use transitivity from sub-region information to infer locations.Source: §20 · p. 9
  • S2 additionally removes test-country sub-region facts, requiring inference from neighboring countries and creating a harder task because neighbors may span regions.Source: §20 · p. 9
  • S3 further removes selected training-country region facts, allowing multi-hop inference through neighboring countries and their locations.Source: §20 · p. 9

Countries with Mentions

Nations and UMLS

  • Nations and UMLS contain 2565 and 6529 true facts respectively, and evaluate ranking after corrupting test-fact arguments.Source: Nations and UMLS · p. 10

WordNet and Freebase

  • WordNet contains 40,943 entities and 151,442 triples, while FB122 contains 9,738 entities, 122 relations, and 112,476 triples with rule-based test partitions.Source: WordNet and Freebase · pp. 10–11

Run-Time Performance comparison

  • More than two orders of magnitude speedup is achieved on larger datasets, while memory savings exceed an order of magnitude.Countries S1 and S2 show speedups of an order of magnitude; Kinship and Nations exceed two orders.Source: Figure 4 · p. 10, Run-Time Performance comparison · p. 11
Loading 1912.10824v1…