Differentiable Reasoning on Large Knowledge Bases and Natural Language

Introduction

The main focus of Artificial Intelligence is building systems that exhibit intelligent behaviour (?). Notably, Natural Language Understanding (NLU) and Machine Reading (MR) aim at building models and systems with the ability to read text, extract meaningful knowledge, and reason with it (?; ?; ?; ?). This ability facilitates both the synthesis of new knowledge and the possibility to verify and update a given assertion.

Traditionally, automated reasoning applied to text requires natural language processing tools that compile it into the structured form of a KB (?). However, the compiled KBs tend to be incomplete, ambiguous, and noisy, impairing the application of standard deductive reasoners (?).

A rich and broad literature in MR has approached this problem within a variety of frameworks, including Natural Logic (?), Semantic Parsing (?), Natural Language Inference and Recognising Textual Entailment (?; ?), and Question Answering (?). Nonetheless, such methods suffer from several limitations. They rely on significant amounts of annotated data to suitably approximate the implicit distribution from which the data is drawn. In practice, this makes them unable to generalise well in the absence of a sufficient quantity of training data or appropriate priors on model parameters (?). Orthogonally, even when accurate, such methods cannot explain given predictions (?).

A promising strategy for overcoming these issues consists of combining neural models and symbolic reasoning, given their complementary strengths and weaknesses (?; ?; ?; ?; ?). While symbolic models can generalise well from a small number of examples, they are brittle and prone to failure when the observations are noisy or ambiguous, or when the properties of the domain are unknown or hard to formalise, all of which being the case for natural language (?; ?). Contrarily, neural models are robust to noise and ambiguity but not easily interpretable, making them unable to provide explanations or incorporating background knowledge (?).

Recent work in neuro-symbolic systems has made progress towards end-to-end differentiable reasoning models that can be trained via backpropagation while maintaining interpretability and generalisation, thereby inheriting the best of both worlds. Among such systems, NTPs (?; ?) are end-to-end differentiable deductive reasoners based on Prolog’s backward chaining algorithm, where discrete unification between atoms is replaced by a differentiable operator computing the similarities between their embedding representations.

NTPs are especially interesting since they allow learning interpretable rules from data, by back-propagating the prediction errors to the rule representations. Furthermore, the proving process in NTPs is explainable – the proof path associated with the largest proof score denotes which rules and facts are used in the reasoning process. However, NTPs have only been successfully applied to learning tasks involving very small datasets, since their computational complexity makes them unusable on larger, real-world KBs. Furthermore, most human knowledge is not available in KBs, but in natural language texts which are difficult to reason over automatically.

In this paper we address these issues by proposing: i) two efficiency improvements for significantly reducing the time and space complexity of NTPs by reducing the number of candidate proof paths and introducing an attention mechanism for rule induction, and ii) an extension of NTPs towards natural language, jointly embedding predicates and textual surface patterns in a shared space by using an end-to-end differentiable reading component.

End-to-end Differentiable Proving

NTPs (?) recursively build a neural network enumerating all the possible proof paths for proving a query (or goal) on a given KB, and aggregate all their proof scores via max pooling. They do so by relying on three modules—a unification module, which compares sub-symbolic representations of logic atoms, and mutually recursive or and and modules, which jointly enumerate all possible proof paths, before the final aggregation selects the highest-scoring one.

In the following, we briefly overview these modules, and the training process used for learning the model parameters from data. We assume the existence of a function-free Datalog KB $\mathfrak{K}$ containing ground facts in the form \bm{[}\verb~p~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{a}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{b}}\bm{]} For consistency, we use the same notation as ? (?)., representing the logical atom \verb~p~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{a}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{b}}) where $\verb~p~$ is a relation type, and {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{a}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{b}} are its arguments. We consider binary predicates, without loss of generality. It also contains rules in the form H :– B such as \bm{[}\verb~p~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}\ \text{:--}\ \bm{[}\bm{[}\verb~q~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}\bm{]},\bm{[}\verb~r~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}\bm{]}, denoting the rule \verb~p~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}})\ \text{:--}\ \verb~q~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}),\verb~r~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}), meaning that \verb~q~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}),\verb~r~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}) implies \verb~p~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}), where {\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}} are universally quantified variables.

In the backward chaining reasoning algorithm, unification is the operator that matches two logic atoms, such as \verb~locatedIn~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{london}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{uk}}) and \verb~situatedIn~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}). Discrete unification checks for equality between the elements composing the two atoms (e.g. $\verb~locatedIn~\neq\verb~situatedIn~$), and binds variables to symbols via substitutions (e.g. \{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}}/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{london}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{uk}}\}). In NTPs, unification matches two atoms by comparing their embedding representations via a differentiable similarity function – a Gaussian kernel – which enables matching different symbols with similar semantics.

More formally, ${\verb~unify~}_{{\bm{\theta}}}(\textsc{H},\textsc{G},\textsc{S})=S^{\prime}$ creates a neural network module that matches two atoms H and G by comparing their embedding vectors. For instance, given a goal \textsc{G}=\bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{London}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{UK}}\bm{]}, a fact \textsc{H}=\bm{[}\verb~situatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}, and a proof state $S=(S_{\psi},S_{\rho})$ consisting of a set of substitutions $S_{\psi}$ and a proof score $S_{\rho}$, the unify module compares the embedding representations of $\verb~locatedIn~$ and $\verb~situatedIn~$ with a Gaussian kernel $k$, updates the variable binding substitution set S^{\prime}_{\psi}=S_{\psi}\cup\{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}}/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{London}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}/{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{UK}}\}, and calculates the new proof score $S^{\prime}_{\rho}=\min\left(S_{\rho},k\left({{\bm{\theta}}}_{\verb~locatedIn~:},{{\bm{\theta}}}_{\verb~situatedIn~:}\right)\right)$ and proof state $S^{\prime}=(S^{\prime}_{\psi},S^{\prime}_{\rho})$.

The or module computes the unification between a goal and all facts and rule heads in a KB, and then recursively invokes the and module on the corresponding rule bodies. Formally, for each rule H :– B Facts are seen as rules with no body and variables, i.e. $\textsc{F}\ \text{:--}\ \bm{[}\bm{]}$. in a KB $\mathfrak{K}$, ${\verb~or~}^{\mathfrak{K}}_{{\bm{\theta}}}(\textsc{G},d,S)$ unifies the goal G with the rule head H, and invokes the and module to prove atoms in the body B, keeping track of the maximum proof depth $d$:

For example, given a goal \textsc{G}=[\verb~situatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Q}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{UK}}] and a rule H :– B with \textsc{H}=\bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]} and \textsc{B}=\bm{[}\bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}\bm{]},\bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}\bm{]}, the model would unify the goal G with the rule head H, and invoke the and modules to prove the sub-goals in the rule body B.

For example, when invoked on the rule body B of the example mentioned above, the and module will substitute variables with constants for the sub-goal \bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}\bm{]} and invoke the or module, whose resulting state will be the basis of the next invocation of and module on \bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}.

After building a neural network that evaluates all the possible proof paths of a goal G on a KB $\mathfrak{K}$, NTPs select the proof path with the largest proof score:

In NTPs, embedding representations are learned by minimising a cross-entropy loss $\mathcal{L}^{\mathfrak{K}}({{\bm{\theta}}})$ on the final proof score, by iteratively masking facts in the KB and trying to prove them using other available facts and rules.

Negative examples are obtained via a corruption process, denoted by $\text{corrupt}(\cdot)$, by modifying the subject and object of triples in the KB (?):

NTPs can also learn interpretable rules. ? (?) show that it is possible to learn rules from data by specifying rule templates, such as H :– B with \textsc{H}=\bm{[}{{\bm{\theta}}}_{p:},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]} and \textsc{B}=\bm{[}\bm{[}{{\bm{\theta}}}_{q:},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}\bm{]},\bm{[}{{\bm{\theta}}}_{r:},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}\bm{]}.

Efficient Differentiable Reasoning on Large-Scale KBs

NTPs are capable of deductive reasoning, and the proof paths with the highest score can provide human-readable explanations for a given prediction. However, enumerating and scoring all bounded-depth proof paths for a given goal, as given in Eq. 3, is computationally intractable. For each goal and sub-goal G, this process requires to unify $G$ with the representations of all rule heads and facts in the KB, which quickly becomes computationally prohibitive even for moderately sized KBs. Furthermore, the expansion of a rule like \verb~p~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}})\ \text{:--}\ \verb~q~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}}),\verb~r~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Z}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}) via backward chaining causes an increase of the sub-goals to prove, both because all atoms in the body need to be proven, and because Z is a free variable with many possible bindings (?). We consider two problems – given a sub-goal G such as \bm{[}\verb~p~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{a}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{b}}\bm{]}, we need to efficiently select i) the $k_{f}$ facts that are most likely to prove a sub-goal G, and ii) the $k_{r}$ rules to expand to reach a high-scoring proof state.

Unifying a sub-goal G with all facts in the KB $\mathfrak{K}$ may not be feasible in practice. The number of facts in a real-world KB can be in the order of millions or billions. For instance, Freebase contains over $637\times 10^{6}$ facts, while the Google Knowledge Graph contains more than $18\times 10^{9}$ facts (?). Identifying the facts $\textsc{F}\in\mathfrak{K}$ that yield the maximum proof score for a sub-goal G reduces to solving the following optimisation problem:

Hence, the fact $\textsc{F}\in\mathfrak{K}$ that yields the maximum proof score for a sub-goal G is the fact F that yields the maximum unification score with G. Recall that the unification score between a fact F and a goal G is given by the similarity of their embedding representations ${{\bm{\theta}}}_{\textsc{F}:}$ and ${{\bm{\theta}}}_{\textsc{G}:}$, computed via a Gaussian kernel $k({{\bm{\theta}}}_{\textsc{F}},{{\bm{\theta}}}_{\textsc{G}})$. Given a goal G, NTPs will compute the unification score between G and every fact $\textsc{F}\in\mathfrak{K}$ in the KB. This is problematic, since computing the similarity between the representations of the goal G and every fact $\textsc{F}\in\mathfrak{K}$ is computationally prohibitive – the number of comparisons is ${\mathcal{O}}(|\mathfrak{K}|n)$, where $n$ is the number of (sub-)goals in the proving process. However, ${\verb~ntp~}^{\mathfrak{K}}_{{\bm{\theta}}}(\textsc{G},d)$ only returns the single largest proof score. This means that, at inference time, we only need the largest proof score for returning the correct output. Similarly, during training, the gradient of the proof score with respect to the parameters ${{\bm{\theta}}}$ can also be calculated exactly by using the single largest proof score:

In this paper, we propose to efficiently compute $S^{\star}$, the highest unification score between a given sub-goal G and a fact $\textsc{F}\in\mathfrak{K}$, by casting it as a Nearest Neighbour Search (NNS) problem. This is feasible since the Gaussian kernel used by NTPs is a monotonic transformation of the negative Euclidean distance.

Identifying $S^{\star}$ permits to reduce the number of neural network sub-structures needed for the comparisons between each sub-goal and facts from ${\mathcal{O}}(|\mathfrak{K}|)$ to ${\mathcal{O}}(1)$. We use the exact and approximate NNS framework proposed by ? (?) for efficiently searching $\mathfrak{K}$ for the best supporting facts for a given sub-goal. Specifically we use the exact L2-nearest neighbour search and, for the sake of efficiency, we update the search index every 10 batches, assuming that the small updates made by stochastic gradient descent do not necessarily invalidate previous search indexes.

We use a similar idea for selecting which rules to activate for proving a given goal G. We empirically notice that unifying G with the closest rule heads, such as \textsc{G}=\bm{[}\verb~locatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{london}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{uk}}\bm{]} and \textsc{H}=\bm{[}\verb~situatedIn~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\bm{]}, is more likely to generate high-scoring proof states. This is a trade-off between symbolic reasoning, where proof paths are expanded only when the heads exactly match with the goals, and differentiable reasoning, where all proof paths are explored.

This prompted us to implement a heuristic that dynamically selects rules among rules sharing the same template during both inference and learning. In our experiments, this heuristic for selecting proof paths was able to recover valid proofs for a goal when they exist, while drastically reducing the computational complexity of the differentiable proving process.

where, instead of unifying a sub-goal G with all rule heads, we constrain the unification to only the rules where heads are in the neighbourhood ${\mathcal{N}}_{{\mathcal{P}}}(\textsc{G})$ of G.

Jointly Reasoning on Knowledge Bases and Natural Language

In this section, we show how GNTPs can jointly reason over KBs and natural language corpora. In the following, we assume that our KB $\mathfrak{K}$ is composed of facts, rules, and textual mentions. A fact is composed of a predicate symbol and a sequence of arguments, e.g. \bm{[}\verb~locationOf~,{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{London}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{UK}}\bm{]}. On the other hand, a mention is a textual pattern between two co-occurring entities in the KB (?), such as “London is located in the UK”.

Related Work

A notable corpus of literature aims at addressing the limitations of neural architectures in terms of generalisation and reasoning abilities. A line of research consists of enriching neural network architectures with a differentiable external memory (?; ?; ?; ?; ?). The underlying idea is that a neural network can learn to represent and manipulate complex data structures, thus disentangling the algorithmic part of the process from the representation of the inputs. By doing so, it becomes possible to train such models from enriched supervision signals, such as from program traces rather than simple input-output pairs.

A related field is differentiable interpreters—program interpreters where declarative or procedural knowledge is compiled into a neural network architecture (?; ?; ?). This family of models allows imposing strong inductive biases on the models by partially defining the program structure used for constructing the network, e.g., in terms of instruction sets or rules. A major drawback of differentiable interpreters, however, is their computational complexity, so far deeming them unusable except for smaller learning problems. ? (?) use an approximate nearest neighbour data structures for sparsifying read operations in memory networks.

? (?) pioneered the idea of jointly embedding KB facts and textual mentions in shared embedding space, by considering mentions as additional relations in a KB factorisation setting, and more elaborate mention encoders were investigated by ? (?).

Our work is also related to path encoding models (?) and random walk approaches (?; ?), both of which lack a rule induction mechanisms, and to approaches combining observable and latent features of the graph (?; ?). Lastly, our work is related to ? (?), a scalable rule induction approach for KB completion, but has not been applied to textual surface patterns.

Experiments

We report the results of experiments on benchmark datasets — Countries (?), Nations, UMLS, and Kinship (?) — following the same evaluation protocols as ? (?). Furthermore, since GNTPs allows to experiment on significantly larger datasets, we also report results on the WN18 (?), WN18RR (?) and FB122 (?) datasets. Results are reported in terms of the Area Under the Precision-Recall Curve (AUC-PR) (?), Mean Reciprocal Rank (MRR), and HITS@$m$ (?). Datasets and hyperparameters are described in the Appendix. The Appendix can be found at https://github.com/uclnlp/gntp

On benchmark datasets, we compare GNTPs with NTPs and two other neuro-symbolic reasoning systems, MINERVA (?), which employs a reinforcement learning algorithm to reach answers by traversing the KB graph, and NeuralLP (?), which compiles inference tasks in a sequence of differentiable operations. In addition, we consider DistMult (?) and ComplEx (?), two state-of-the-art black-box neural link predictors suited for large datasets.

To assess the benefits of GNTPs in terms of computational complexity and range of applications, we consider the best hyperparameters we found for the WN18 dataset, and measured the time needed for each training epoch varying the number of unified facts and rules during inference. Results, outlined in Fig. 2, show that learning on WN18 quickly becomes infeasible by increasing the number of unified facts and rules. NTPs are a special case of GNTPs where, during the forward pass, there is no pruning of the proof paths.

From Fig. 2 we can see that even for KBs a fraction the size of WordNet and Freebase, NTPs rapidly run out of memory, deeming them inapplicable to reasonably sized KBs. Instead, sensible pruning of proof paths in GNTPs drastically increases the efficiency of both the learning and the inference process, allowing to train on large KBs like WordNet. We refer to the Appendix0 for additional experiments showing run-time improvements by several orders of magnitude.

We compare GNTPs and NTPs on a set of link prediction benchmarks, also used in ? (?). Results, presented in Table 1, show that GNTPs achieves better or on-par results in comparison with NTPs and baselines MINERVA (?) and NeuralLP (?), consistently through all benchmark datasets. We can also see that models learned by GNTPs are interpretable: in Table 1 we show the decoded rules learned by the model, and learn about the domain at hand. For instance, we can see that on UMLS, a biomedical KB, the isa and affects relation are transitive.

For evaluating different strategies of integrating textual surface patterns, in the form of mentions, in NTPs, we proceeded as follows. We replaced a varying number of training set triples from each of the Countries S1-S3 datasets with human-generated textual mentions (for more details, see Appendix).6 For instance, the fact \verb~neighbourOf~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{UK}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Ireland}}) may be replaced by the textual mention “UK is neighbouring with Ireland”. The entities UK and Ireland become the arguments, while the text between them is treated as a new logic predicate, forming a new fact \text{``}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}}\ \text{is neighbouring with }{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}}\text{''}({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{UK}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Ireland}}).

Then, we evaluate two ways of integrating textual mentions in GNTPs: i) adding them as facts to the KB, and ii) parsing the mention by means of an encoder. The results, presented in Fig. 3, show that the proposed encoding module yields consistent improvements of the ranking accuracy in comparison to simply adding the mentions as facts to the KB. This is especially evident in cases where the number of held-out facts is higher, as it is often the case in real-world use cases, where there is an abundance of text but the KBs are sparse and incomplete (?). GNTPs are extremely efficient at learning rules involving both logic atoms and textual mentions.

For instance, by analysing the learned models and their explanations, we can see that GNTPs learn rules such as

and leverage them during their reasoning process, providing human-readable explanations for a given prediction.

Results on Freebase and WordNet

Link prediction results for FB122 are summarised in Table 2. The FB122 dataset proposed by ? (?) is fairly large scale: it comprises 91,638 triples, 9,738 entities, and 122 relations, as well as 47 rules that can be leveraged by models for link prediction tasks. For such a reason, we consider a series of models that can leverage the presence of such rules, namely KALE (?), DistMult and ComplEx using Adversarial Sets (ASR) (?)—a method for incorporating rules in neural link predictors via adversarial training—and the recently proposed KBlr (?). Note that, unlike these methods, GNTPs do not have access to such rules and need to learn them from data.

Table 2 shows that GNTP, whilst not having access to rules, performs significantly better than neural link predictors, and on-par with methods that have access to all rules. In particular, we can see that on Test-II, a subset of FB122 directly related to logic rules, GNTP yields competitive results. GNTP is able to induce rules relevant for accurate predictions, such as:

We also evaluate GNTP on WN18 (?) and WN18RR (?). In terms of ranking accuracy, GNTPs is comparable to state-of-the-art models, such as ComplEx and KBlr. In ? (?) authors report a $94.2$ MRR for ComplEx and $93.6$ MRR for KBlr, while NeuralLP (?) achieves $94.0$, with hits@10 equal to $94.5$. GNTP achieves $94.2$ MRR and $94.31$, $94.41$, $94.51$ hits@3, 5, 10, which is on par with state-of-the-art neural link prediction models, while being interpretable via proof paths. Table 3 shows an excerpt of validation triples together with their GNTP proof scores and associated proof paths for WN18. On WN18RR, GNTP with MRR of $43.4$ performs close to ComplEx (?) ($44.0$ MRR) but lags behind NeuralLP ($46.3$ MRR).

We can see that GNTPs is capable of learning and utilising rules, such as {\verb~has\_part~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}})}\ \text{:--}\ \verb~part\_of~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}}), and \verb~hyponym~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}})\ \text{:--}\ \verb~hypernym~({\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{Y}},{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\textsc{X}}). Interestingly, GNTP is able to find non-trivial explanations for a given fact, based on the similarity between entity representations. For instance, it can explain that congo is part of africa by leveraging the semantic similarity with african_country.

Conclusions

NTPs combine the strengths of rule-based and neural models but, so far, they were unable to reason over large KBs and natural language. In this paper, we overcome such limitations by considering only the subset of proof paths associated with the largest proof scores during the construction of a dynamic computation graph.

The proposed model, GNTP, is more computationally efficient by several orders of magnitude, while achieving similar or better predictive performance than NTPs. GNTPs enable end-to-end differentiable reasoning on large KBs and natural language texts, by embedding logic atoms and textual mentions in the same embedding space. Furthermore, GNTPs are interpretable and can provide explanations in terms of logic proofs at scale.

References

Appendix

We run experiments on the following datasets, and report results in terms of Area Under the Precision-Recall Curve (?) (AUC-PR), MRR, and HITS@$m$ (?).

Countries is a dataset introduced by ? (?) for testing reasoning capabilities of neural link prediction models. It consists of $244$ countries, $5$ regions (e.g. Europe), $23$ sub-regions (e.g. Western Europe, North America), and $1158$ facts about the neighbourhood of countries, and the location of countries and sub-regions. As in ? (?), we randomly split countries into a training set of $204$ countries (train), a development set of $20$ countries (validation), and a test set of $20$ countries (test), such that every validation and test country has at least one neighbour in the training set. Subsequently, three different task datasets are created, namely S1, S2, and S3. For all tasks, the goal is to predict $\verb~locatedIn~(c,r)$ for every test country $c$ and all five regions $r$, but the access to training atoms in the KB varies.

All ground atoms $\verb~locatedIn~(c,r)$, where $c$ is a test country and $r$ is a region, are removed from the KB. Since information about the sub-region of test countries is still contained in the KB, this task can be solved by using the transitivity rule:

In addition to S1, all ground atoms $\verb~locatedIn~(c,s)$ are removed where $c$ is a test country and $s$ is a sub-region. The location of countries in the test set needs to be inferred from the location of its neighbouring countries:

This task is more difficult than S1, as neighbouring countries might not be in the same region, so the rule above will not always hold.

In addition to S2, also all ground atoms $\verb~locatedIn~(c,r)$ are removed where $r$ is a region and $c$ is a country from the training set training that has a country from the validation or test sets as a neighbour. The location of test countries can for instance be inferred using the rule:

We generated a set of variants of Countries S1, S2, and S3, by randomly replacing a varying number of training set triples with mentions. The employed mentions are outlined in Table 4.

Furthermore, we consider the Nations, and the Unified Medical Language System (UMLS) datasets (?). UMLS contains $49$ predicates, $135$ constants and $6529$ true facts, while Nations contains $56$ binary predicates, $111$ unary predicates, $14$ constants and $2565$ true facts. We follow the protocol used by ? (?) and split every dataset into training, development, and test facts, with a $80\%/10\%/10\%$ ratio. For evaluation, we take a test fact and corrupt its first and second argument in all possible ways such that the corrupted fact is not in the original KB. Subsequently, we predict a ranking of the test fact and its corruptions to calculate MRR and HITS@$m$.

WordNet and Freebase

We also evaluate the proposed method on WordNet (WN18) and Freebase (FB122) jointly with the set of rules released by ? (?). WordNet (?) is a lexical knowledge base for the English language, where entities correspond to word senses, and relationships define lexical relations between them. The WN18 dataset consists of a subset of WordNet, containing 40,943 entities, 18 relation types, and 151,442 triples.

We also consider WN18RR (?), a dataset derived from WN18 where predicting missing links is sensibly harder.

Freebase (?) is a large knowledge graph that stores general facts about the world. The FB122 dataset is a subset of Freebase regarding the topics of people, location and sports, and contains 9,738 entities, 122 relation types, and 112,476 triples.

For both data sets, we used the fixed training, validation, test sets and rules provided by ? (?); a subset of the rules is shown in Table 5. Note that a subset of the test triples can be inferred by deductive logic inference.

For such a reason, following ? (?), we also partition the test set in two subsets, namely Test-I and Test-II: Test-I contains triples that cannot be inferred by deductive logic inference, while Test-II contains all remaining test triples.

Appendix B Run-Time Performance comparison

To assess the run-time gains of GNTP, we compare it to NTP with respect to time and memory performance during training. In our experiments, we vary the $n$ of the NNS to assess the computational demands by increasing $n$. First, we compare the average number of examples (queries) per second by running 10 training batches with a maximum batch to fit the memory of NVIDIA GeForce GTX 1080 Ti, for all models. Second, we compare the maximum memory usage of both models on a CPU, over 10 training batches with same batch sizes. The comparison is done on a CPU to ensure that we include the size of the NNS index in GNTP measures and as a fail-safe, in case the model does not fit on the GPU memory.

The results, presented in Figure 4, demonstrate that, compared to NTP, GNTP is considerably more time and memory efficiency. In particular, we observe that GNTP yields significant speedups of an order of magnitude for smaller datasets (Countries S1 and S2), and more than two orders of magnitude for larger datasets (Kinship and Nations). Interestingly, with the increased size of the dataset, GNTP consistently achieves higher speedups, when compared to NTP. Similarly, GNTP is more memory efficient, with savings bigger than an order of magnitude, making them readily applicable to larger datasets, even when augmented with textual surface forms.

Appendix C Hyper-parameters

For each experiment, the best hyperparameters were selected via cross-validation. We use Adam (?) for minimising the loss function in Eq. 4. We searched for the best learning rates in $\{0.001,0.005,0.01,0.05,0.1\}$, for the best L2 regularisation weights in $\{0.001,0.0001\}$. For Freebase and WordNet, we fixed the batch size to 1000, while for Countries, UMLS, Kinship, and Nations we searched the best batch size in $\{10,20,50,100\}$. About GNTPs-specific hyperparameters, we searched for the best number of rules $k_{r}$ and facts $k_{f}$ to unify with in $\{1,3,5\}$.

Due to time and computational constraints, the embedding size of entities and relation types was set to 100, the number of epochs was also set to 100, while the maximum proof depth $d$ was fixed to 2.

In all experiments, we observed a quick convergence of the model already in the first 20-30 epochs. On FB122, we found it useful to pre-train rules first (95 epochs), without updating any entity or relation embeddings, and then training the entity embeddings jointly with the rules (5 epochs). This forces GNTPs to learn a good rule-based model of the domain before fine-tuning its representations.