Title: SCALABLE NEURAL THEOREM PROVING ON KNOWLEDGE BASES AND NATURAL LANGUAGE

Abstract: Reasoning over text and Knowledge Bases (KBs) is a major challenge for Artificial Intelligence, with applications in machine reading, dialogue, and question answering. Transducing text to logical forms which can be operated on is a brittle and error-prone process. Operating directly on text by jointly learning representations and transformations thereof by means of neural architectures that lack the ability to learn and exploit general rules can be very data-inefficient and not generalise correctly. These issues are addressed by Neural Theorem Provers (NTPs) (Rocktäschel & Riedel, 2017), neuro-symbolic systems based on a continuous relaxation of Prolog's backward chaining algorithm, where symbolic unification between atoms is replaced by a differentiable operator computing the similarity between their embedding representations. In this paper, we first propose Neighbourhoodapproximated Neural Theorem Provers (NaNTPs) consisting of two extensions to NTPs, namely a) a method for drastically reducing the previously prohibitive time and space complexity during inference and learning, and b) an attention mechanism for improving the rule learning process, deeming them usable on real-world datasets. Then, we propose a novel approach for jointly reasoning over KB facts and textual mentions, by jointly embedding them in a shared embedding space. The proposed method is able to extract rules and provide explanations-involving both textual patterns and KB relations-from large KBs and text corpora. We show that NaNTPs perform on par with NTPs at a fraction of a cost, and can achieve competitive link prediction results on challenging large-scale datasets, including WN18, WN18RR, and FB15k-237 (with and without textual mentions) while being able to provide explanations for each prediction and extract interpretable rules.

1. INTRODUCTION:

The main focus in Artificial Intelligence is building systems that exhibit intelligent behaviour (Levesque, 2014) . In particular, Natural Language Understanding (NLU) and Machine Reading (MR) aim at building models and systems with the ability to read text, extract meaningful knowledge, and actively reason with it (Etzioni et al., 2006; Hermann et al., 2015; Weston et al., 2015; McCallum et al., 2017a) . This ability enables both the synthesis of new knowledge and the possibility to verify and update a given assertion. For example, given the following statement:

The River Thames is in the United Kingdom.

and the following supporting text::

London is the capital and most populous city of England and the United Kingdom. Standing on the River Thames in the south east of the island of Great Britain, London has been a major settlement for two millennia.

a reader can verify that the statement is consistent since London is standing on the River Thames and London is in the United Kingdom. Automated reasoning applied on text requires Natural Language Processing (NLP) tools capable of extracting meaningful knowledge from free-form text and compiling it into KBs (Niklaus et al., 2018) . However, the compiled KBs tend to be incomplete, ambiguous, and noisy, impairing the application of standard deductive reasoners (Huang et al., 2005) .

Rule Group p(X, Y) :-q(Y, X) Rules Rule Group p(X, Y) :-q(X, Z), r(Z, Y) A rich and broad literature in MR has approached this problem within a variety of frameworks, including Natural Logic (MacCartney & Manning, 2007; Angeli & Manning, 2014) and Semantic Parsing (Dong & Lapata, 2016; Bos, 2008) , and by framing the problem as Natural Language Inference-also referred to as Recognising Textual Entailment (Fyodorov et al., 2000; Condoravdi et al., 2003; Dagan et al., 2005; Bowman et al., 2015; Rocktäschel et al., 2015) -and Question Answering (Hermann et al., 2015) . However, such methods suffer from several limitations. For instance, they rely on significant amounts of annotated data to suitably approximate the implicit distribution from which training and test data are drawn, and thus are often unable to generalise correctly in the absence of a sufficient quantity of training data or appropriate priors on model paramaters (e.g. via regularisation). Orthogonally, even if accurate, such methods also cannot provide explanations for a given prediction (Evans & Grefenstette, 2018; Marcus, 2018) .

A promising strategy for overcoming these issues consists of combining neural models and symbolic reasoning, given their complementary strengths and weaknesses (Rocktäschel & Riedel, 2017; Evans & Grefenstette, 2018) . While symbolic models can generalise well from a small number of examples when the problem domain fits the inductive biases presented by the symbolic system at hand, they are brittle and prone to failure when the observations are noisy and ambiguous, or when the domain's properties are not known or formalisable, all of which being the case for natural language (Raedt & Kersting, 2008) . On the other hand, neural models are robust to noise and ambiguity but prone to overfitting (Marcus, 2018) and not easily interpretable (Lipton, 2018) , making them incapable of providing explanations or incorporating background knowledge.

Recent work in neuro-symbolic systems (Garcez et al., 2015) has made progress in learning neural representations that allow for comparison of symbols not on the basis of identity, but of their semantics (as learned in continuous representations of said symbols), while maintaining interpretability and generalisation, thereby inheriting the best of both worlds. Among such systems, NTPs (Rocktäschel & Riedel, 2017) are end-to-end differentiable deductive reasoners based on Prolog's backward chaining algorithm, where unification between atoms is replaced by a differentiable operator computing their similarity between their embedding representations. NTPs are especially interesting since they allow learning interpretable rules from data, by back-propagating a KB reconstruction error to the rule representations. Furthermore, NTPs are explainable: by looking at the proof tree associated with the highest proof score, it is possible to know which rules are activated during the reasoning process-this enables providing explanations for a given reasoning outcome, performing error analysis, and driving modelling choices. So far, due to their computational complexity, NTPs have only been successfully applied to learning tasks involving very small KBs. However, most human knowledge is still stored in large KBs and natural language corpora, which are difficult to reason over automatically.

With this paper we aim at addressing these issues, by proposing:a) An efficient method for significantly reducing the time and space complexity required by NTPs by reducing the number of candidate proof scores and by using an attention mechanism for reducing the number of parameters required for learning new rules (Section 3), and b) An extension of NTPs towards text, by jointly embedding predicates and textual surface patterns in a shared embedding space by means of an efficient reading component (Section 4).

2. NEURAL THEOREM PROVING:

Mimicking backward chaining, NTPs recursively build a neural network enumerating all the possible proof states for proving a goal over the KB. NTPs rely on three modules for building this neural network; the Unification module, which compares subsymbolic representations of symbols, and mutually recursive OR and AND modules, which jointly enumerate all the proof paths, before the final aggregation choses the single, highest scoring state. We briefly overview these modules and the training procedure in the following. AND Module. The and module recursively tries to prove a list of sub-goals for a rule body. Concretely, given the first sub-goal G and the following sub-goals G, the and K θ (G : G, d, S) module will substitute variables in G with constants according to the substitutions in S, and invoke the or module on G. The resulting state be used to prove the atoms in G, by recursively invoking the and module. For example, when invoked on the rule body B mentioned above, the and module will first substitute variables with constants for the sub-goal [locatedIn, X, Z] and invoke the or module, whose resulting state will be the basis of the next invocation of and module on [locatedIn, Z, Y].

Proof Aggregation. After building a neural network that enumerates all the proof paths of the goal G on a KB K, NTPs select the proof path with the maximum proof score:

ntp K θ (G, d) = arg max S ∈ or K θ (G,d,(∅,1)) S =FAIL S ρ

where d is a predefined maximum proof depth. The initial proof state is set to (∅, 1), an empty substitution set, and a proof score of 1.

Training In NTPs, predicate and constant embeddings are learned by optimising a cross-entropy loss on the final proof score, by iteratively masking facts in the KB and trying to prove them using available facts and rules (Rocktäschel & Riedel, 2017) . Negative examples are sampled from the positive ones by corrupting the entities (Nickel et al., 2016) .

Other than learning embeddings of predicates and constants, NTPs can also learn interpretable rules from data. Rocktäschel & Riedel (2017) show that it is possible to learn rules from data by specifying rule templates H :-B, with H = [θ p: , X, Y] and B = [[θ q: , X, Z], [θ r: , Z, Y]], where θ p: , θ q: , θ r: ∈ R k are free parameters. Note that θ p: , θ q: , θ r: can be learned from data, and decoded by searching the closest representation of known predicates.

3. NEURAL THEOREM PROVING AT SCALE:

Scaling up Inference. The model in Section 2 is capable of deductive reasoning, and the proof paths with the highest score can provide human-readable explanations for a given prediction. However, a significant computational bottleneck lies in the or operator.

For instance, assume a KB K, composed of |K| facts and no rules. The number of facts in a real-world KB can be quite large-for instance, Freebase contains 637 million facts (Dong et al., 2014) , while the Google Knowledge Graph contains 18 billion facts (Nickel et al., 2016) . Given a query G, in the absence of rules, NTP reduces to solving the following optimisation problem:

ntp K θ (G, 1) = arg max F∈K, S =FAIL S ρ with S = unify θ (F, G, (∅, 1)) (1)

that is, it finds the fact F ∈ K in the KB K that, unified with the goal G, yields the maximum unification score. Recall from Section 2 that the unification score between a fact F =

[F p , F s , F o ] and a goal G = [G p , G s , G o ]

is given by the similarity of their representations in a Euclidean space:

EQUATION

where k denotes a RBF kernel, and θ Gp: , θ Gs: , θ Go: ∈ R k (resp. θ Fp: , θ Fs: , θ Fo: ∈ R k ) denote the embedding representation of the predicate, first and second argument of the goal G (resp. fact F).

Given a goal G, the NTPs proposed by (Rocktäschel & Riedel, 2017) will compute the unification score in Eq. 2 between G and every fact F ∈ K in the KB. This is problematic, since computing the similarity between the representations of the goal G and every fact F ∈ K is computationally prohibitive-the number of comparisons is O(|K|n), where n is the number of goals and sub-goals in the proving process. However, ntp K θ (G, d) only returns the single largest proof score, implying that every lower scoring proof is discarded during both inference and training.

One of the core contributions in this paper is to exactly compute ntp K θ (G, m) by only considering a subset of proof scores that contains the largest one. Specifically, we make the following observation: given a goal G, if we know the most similar fact F ∈ K in embedding space as measured by unify θ , the number of comparisons needed for computing the final proof score ntp K θ (G, 1) is reduced from O(|K|) to O(1). The same reasoning can be extended to rules as well.

We argue that, given G, we can restrict the search of the closest fact

F ∈ K to a Euclidean local neighbourhood of size n of G, N K (G) ⊆ K such that |N K (G)| = n, defined as follows: 1 N K (G) = k-arg min F∈K θ F: -θ G: 2 (3)

Then, the matching fact F will be very likely to be contained across the n most similar facts:

ntp K θ (G, 1) ≈ arg max S=unify θ (F,G,(∅,1)) F∈N K (G), S =FAIL S ρ (4)

where the size of the neighbourhood is much lower than the size of the whole KB, i.e., |N K (G)| |K|. The same idea can be extended from facts to rules, by selecting only the rules H :-B ∈ K such that their head H is closer to the goal. However, finding the exact neighbourhood of a point in a Euclidean space is very costly, due to the curse of dimensionality (Indyk & Motwani, 1998) . Experiments showed that methods for identifying the exact neighbourhood can rarely outperform brute-force linear scan methods when dimensionality is high (Weber et al., 1998) .

A practical solution consists in Approximate Nearest Neighbour Search (ANNS) algorithms, which focus on finding an approximate solution to the k-nearest neighbour search problem outlined in Eq. 3 on high dimensional data. Several families of ANNS algorithms exist, such as Locally-Sensitive Hashing (Andoni et al., 2015) , Product Quantisation (Jégou et al., 2011; Johnson et al., 2017) , and Proximity Graphs (Malkov et al., 2014) .

In this work, we use Hierarchical Navigable Small World (HNSW) (Malkov & Yashunin, 2016) , a graph-based incremental ANNS structure which can offer significantly better logarithmic complexity scaling during neighbourhood search than other approaches (Li et al., 2016) . Specifically, given a subset of the KB P ⊆ K-for instance, containing all facts in K-we construct a HNSW graph for all elements in P, which has a O(|P| log |P|) time complexity. Then, given a goal G, the HNSW graph is used for identifying its neighbourhood N P (G) within P, which has a O(log |P|) time complexity. In our implementation, we construct the HNSW graph-based indexing structure when instantiating the model and, during training, we update the index every b batches.

Specifically, in our implementation, we generate a partitioning P ∈ 2 K of the KB K, where each element in P groups all facts and rules in K sharing the same signature. Then, we redefine the or operator as follows:

EQUATION

where, instead of trying to unify a goal or sub-goal G with all facts and rule heads in the KB, we constrain the unification with ANNS to only facts and rule heads in its local neighbourhood N K (G).

Improving Rule Learning via Attention. Although NTPs can be used for learning interpretable rules from data, the solution proposed by Rocktäschel & Riedel (2017) can be quite data-inefficient, as the number of parameters associated to a rule can be quite large. For instance, assume the rule

H :-B, with H = [θ p: , X, Y] and B = [[θ q: , X, Z], [θ r: , Z, Y]

] discussed in Section 2, where θ p: , θ q: , θ r: ∈ R k . Such a rule introduces 3k parameters in the model, and it may be computationally inefficient to learn each of the embedding vectors.

We propose using an attention mechanism (Bahdanau et al., 2015) for attending over known predicates for defining the predicate embeddings θ p: , θ q: , θ r: . Let R be the set of known predicates, and let R ∈ R |R|×k be a matrix representing the embeddings for the predicates in R. We define the θ p: as:

θ p: = softmax(a p: ) R (6)

where a p: ∈ R |R| is a set of trainable attention weights associated with the predicate p. This sensibly improves the parameter efficiency of the model in cases where the number of known predicates is low, i.e. |R| k, by introducing c|R| parameters for each rule rather than ck, where c is the number of trainable predicate embeddings in the rule.

4. JOINTLY REASONING ON KNOWLEDGE BASES AND TEXT:

In this section, we show we can use NaNTPs for jointly reasoning over KBs and natural language corpora. In the following, we assume that our KB K is composed by facts, rules, and mentions. A fact is composed by a predicate symbol and a sequence of arguments, e.g. [locationOf, LONDON, UK]. On the other hand, a mention is a textual pattern between two co-occurring entities in the KB (Gabrilovich et al., 2013; Toutanova et al., 2015) , such as "LONDON is located in the UK".

We represent mentions jointly with facts and rules in K by considering each textual surface pattern linking two entities as a new predicate, and embedding it in a d-dimensional space by means of an end-to-end differentiable reading component. For instance, the sentence "United Kingdom borders with Ireland" is translated into the following mention in K: [[[arg1], borders, with, [arg2] ], UK, IRELAND] by first identifying sentences or paragraphs containing KB entities, and then considering the textual surface pattern connecting such entities as an extra relation type.

While predicates in R are encoded by a look-up operation to a predicate embedding matrix R ∈ R |R|×k , textual surface patterns are encoded by an encode θ module. The signature of encode θ is V * → R k , where V is the vocabulary of words and symbols occurring in textual surface patterns: it takes a sequence of tokens, and maps it to a k-dimensional embedding space.

More formally, given a textual surface pattern t ∈ V * -for instance, t = [[arg1], borders, with, [arg2]]-the encode θ module first encodes each token w in t by means of a token embedding matrix V ∈ R |V|×k , resulting in a pattern matrix W t ∈ R |t|×k . Then, the module produces a textual surface pattern embedding vector θ t: ∈ R k from W t by means of an end-to-end differentiable encoder. In this paper, we use a simple encode θ module that computes the average of the token embedding vectors composing a textual surface pattern:

encode θ (t ∈ V * ) = 1 |t| w∈t V w• ∈ R k

Albeit the encoder encode can be implemented by using other differentiable architectures, such as Recurrent Neural Networks (RNNs), we opted for a simple averaging model, for the sake of simplicity and efficiency, knowing that such a model performs on par or better than more complex models, thanks to a lower tendency to overfit to training data (White et al., 2015; Arora et al., 2017) .

5. RELATED WORK:

A significant 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 (Sukhbaatar et al., 2015; Graves et al., 2014; Joulin & Mikolov, 2015; Grefenstette et al., 2015; Kaiser & Sutskever, 2016; Miller et al., 2016; Graves et al., 2016) . 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.

Another way of improving the generalisation and extrapolation abilities of neural networks consists of designing architectures capable of learning general, reusable programs-atomic primitives that can be reused across a variety of environments and tasks (Reed & de Freitas, 2016; Neelakantan et al., 2016; Parisotto et al., 2016) . By doing so, it becomes also possible to train such models from enriched supervision signals, such as from program traces rather than simple input-output pairs.

Yet another line of work is differentiable interpreters-program interpreters where declarative or procedural knowledge, e.g., a sorting program, is compiled into a neural network architecture (Bošnjak et al., 2017; Gaunt et al., 2016; Rocktäschel & Riedel, 2017; Evans & Grefenstette, 2018) -NTPs fall in this category. 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 problem with differentiable interpreters, however, is their computational complexity, that so far deemed them unusable except for smaller-scale learning problems.

This work is also related to Rae et al. (2016) , which use an approximate nearest neighbour data structure for sparsifying read operations in memory networks. Furthermore, Riedel et al. (2013) pioneered the idea of jointly embedding KB facts and textual mentions in a shared embedding space, by considering mentions as additional relations in a KB factorisation setting. This idea was later extended to more elaborate mention encoders by McCallum et al. (2017b) . Our work is also related to path encoding models (Das et al., 2016) and random walk approaches (Lao et al., 2011; Gardner et al., 2014) , which both lack rule induction mechanisms. Lastly, our work is related to Yang et al. (2017) which is a scalable rule induction approach for knowledge base completion, but has not been applied to textual surface patterns.

6. EXPERIMENTS 6.1 DATASETS AND EVALUATION PROTOCOLS:

We report the results of experiments on benchmark datasets -Countries (Bouchard et al., 2015) , Nations, UMLS, and Kinship (Kemp et al., 2006) -following the same evaluation protocols as Rocktäschel & Riedel (2017) . Furthermore, since our scalability improvements described in Section 3 allow us to experiment on significantly larger datasets, we also report results on the WN18 (Bordes et al., 2013) , WN18RR (Dettmers et al., 2018) and FB15k-237 (Toutanova et al., 2015) datasetswhose characteristics are outlined in 

Hits:

Hits Hits MRR @10 @3 @1 MRR @10 @3 @1 MRR @10 @3 @1 DistMult (Yang et al., 2015) 0.822 0.936 0.914 0.728 0.430 0.490 0.440 0.390 0.241 0.419 0.263 0.155 ComplEx (Trouillon et al., 2016) Baselines. We compare NaNTPs with NTPs on benchmark datasets, and with DistMult (Yang et al., 2015) and ComplEx (Trouillon et al., 2016) Note that, while the complexity of scoring a triple in DistMult and ComplEx is O(1)-they only need the embeddings of the symbols within a fact for computing the ranking score-instead in our model, it is O(log |K|). For such a reason, instead of performing a full hyperparameter search, we fix some of the hyperparameters-i.e.we fix the embedding size d = 100, and train them for 100 epochs-and report results using these hyperparameters for NaNTPs.

For the sake of comparison, we also train ComplEx and DistMult while fixing d = 100 and the number of training epochs to 100, similarly to NaNTPs. 

6.2. SCALABILITY EXPERIMENTS:

Evaluation Performance Comparison In order to verify the correctness of our approximation, we compare the evaluation performance of NaNTP and NTP on the set of benchmark datasets presented in Rocktäschel & Riedel (2017) . Results, presented in Table 3 show that NaNTP achieves on par or better results than NTP, consistently through benchmark datasets. Please note that results reported in Rocktäschel & Riedel (2017) were calculated with an incorrect ranking function, which caused them to report artificially better ranking results.2 

Run-Time Performance comparison To assess the run-time gains of NaNTP, we compare it to NTP with respect to time and memory performance during training. In our experiments, we vary the n of the ANNS approximation 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 The results, presented in Figure 3 , demonstrate that, compared to NTP, NaNTP is considerably more time and memory efficiency. In particular, we observe that NaNTP 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, NaNTP consistently achieves higher speedups, when compared to NTP. Similarly, NaNTP 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.

6.3. RESULTS ON COUNTRIES, UMLS, AND NATIONS:

Experiments with Generated Mentions. 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-3 datasets with human-generated textual mentions. For instance, the fact neighbourOf(UK, IRELAND) may be replaced by the mention "UK is neighbouring with IRELAND".

Then, we evaluate two ways of integrating textual mentions in NaNTPs, either by i) adding them as facts to the KB, or by ii) parsing the mention by means of an encoder, as described in Section 4. The results, presented in Fig. 2 , testify 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 particularly obvious in cases where the number of held-out facts is higher, implying that the added mentions can replace a large missing number of original facts in the KB.

Explanations Involving Mentions. NaNTPs 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 NaNTPs learn patterns such as:

neighborOf(X, Y) :-neighborOf(Y, X) neighborOf(X, Y) :-"E 1 was a neighbor of E 2 "(Y, X) neighborOf(X, Y) :-"E 1 is a neighboring state to E 2 "(Y, X)

locatedIn(X, Y) :-"E 1 was a neighboring state to E 2 "(X, Z), "E 1 was located in

E 2 "(Z, Y) locatedIn(X, Y) :-"E 1 can be found in E 2 "(X, Z), "E 1 is located in E 2 "(Z, Y)

where E 1 and E 2 denote the position of the entities in the text surface patterns, and leverage them during their reasoning process, providing human-readable explanations for a given prediction.

6.4. RESULTS ON WORDNET AND FREEBASE:

Link prediction results are summarised in Table 1 , while Table 2 shows a sample of explanations for the facts in the validation set of WN18 and WN18RR provided by NaNTPs by analysing the proof paths associated with the largest proof scores. We can see that NaNTPs is capable of learning rules, such as has_part(X, Y) :-part_of(Y, X), and hyponym(X, Y) :hypernym(Y, X).

Interestingly, it is also able to find an alternative, 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 similarity between AFRICA and AFRICAN_ COUNTRY, and the fact that the latter is a hyponym of CONGO. It is also able to explain that CHAPLIN is a FILM_MAKER by leveraging the prior knowledge that CHAPLIN is a COMEDIAN, and the similarity between FILM_MAKER and COMEDIAN.

6.5. THE EFFECT OF ATTENTION:

We analysed the effect of using attention for rule learning, introduced in Section 3, on NaNTP's accuracy, on both the benchmark datasets-outlined in Table 6 -and WordNet-outlined in Table 7 .

Table 6 shows that using attention in NaNTP for learning rule representations yields higher average ranking accuracy and lower variance on Countries S1-3 and Kinship, while yielding comparable results to not using attention on Nations and UMLS. This is consistent with the observation in Fig. 2 , where NaNTPs with attention yield better performance on Countries S1-3.

Results in Table 7 show the results of ablations on two large datasets derived from WordNet, namely WN18 and WN18RR. For these two datasets, attention for learning rules greatly increases the ranking accuracy. For instance Hits@10 increases from 83.2% to 93.7% in the case of WN18, and from 25% to 43.2% in the case of WN18RR. Please note that state-of-the-art Neural Link Predictors such as ComplEx (Trouillon et al., 2016) still yield an Hits@10 lower than 95% on WN18: this shows that WN18 yields results on par with other classes of models, while providing explanations for each prediction (as shown in Section 6.4). Note that Neural Link Predictors are a class of model that was investigated for more than a decade now (Paccanaro & Hinton, 2001; Bordes et al., 2013) .

Similarly, MRR increases from 0.539 to 0.769 in the case of WN18, and from 0.137 to 0.398 in the case of WN18RR. An explanation for this phenomenon is that using attention drastically reduces the number of parameters required to learn each of the rule predicates from 100 to 18 in the case of WN18, and to 11 in the case of WN18RR, introducing an inductive bias that reveals being extremely beneficial in terms of ranking accuracy. We can also note that, for FB15k-237, attention did not improve the ranking accuracy. An explanation is that this dataset is very high relational (237 relation types), and using attention actually increased the number of parameters to be learned.

7. CONCLUSION:

NTPs combine the strengths of rule-based and neural models but, so far, they were unable to reason over large KBs, and therefore over natural language.

In this paper, we proposed NaNTPs that utilise ANNS and attention as a solution to scaling issues of NTP. By efficiently considering only the subset of proof paths associated with the highest proof scores during the construction of a dynamic computation graph, NaNTPs yield drastic speedups and memory efficiency, while yielding the same or a better predictive accuracy than NTPs. This enables application of NaNTPs to mixed KB and natural language data by embedding logic atoms and textual mentions in a joint embedding space.

Albeit results are still slightly lower than those yielded by state-of-the-art Neural Link Predictors on large datasets, NaNTPs is interpretable and is able to provide explanations of its reasoning at scale.

A NEURAL THEOREM PROVING:

In NTPs, the neural network structure is built recursively, and its construction is defined in terms of modules similarly to dynamic neural module networks (Andreas et al., 2016) . Given a goal, a KB, and a current proof state as inputs, each module produces a list of new proof states, i.e., neural networks representing partial proof success scores and variable substitutions. In the following we briefly overview the modules constituting NTPs.

A.1 UNIFICATION MODULE:

In backward chaining, unification between two logic atoms is used for checking whether they can represent the same structure. In discrete unification, non-variable symbols are checked for equality, and the proof fails if two symbols differ. Rather than comparing symbols, NTPs compare their embedding representations by means of an end-to-end differentiable similarity function, such as a RBF kernel. This allows matching different symbols with similar semantics, such as relations like locatedIn and situatedIn.

Unification is carried out by the unify operator, which updates a substitution set S, and creates a neural network for comparing the vector representations of non-variable symbols in two sequences of terms. The signature of unify is L × L × S → S, where L is the domain of lists of terms: it takes two atoms, represented as lists of terms, and an upstream proof state, and returns a new proof state S .

More formally, let H and G denote two lists of terms, each denoting a logical atom, such as [p, A, B] and [q, X, Y] for respectively denoting the atoms p(A, B) and q(X, Y). Given a proof state S = (S ψ , S ρ ), where S ψ and S ρ respectively denote a substitution set and a proof score, unification is computed as follows:

1. unify θ ([ ], [ ], S) = S 2. unify θ ([ ], G, S) = FAIL 3. unify θ (H, [ ], S) = FAIL 4. unify θ (h :: H, g :: G, S) = unify θ (H, G, S )

with S = (S ψ , S ρ ) where:

S ψ =S ψ ∪ {h/g} if h ∈ V {g/h} if g ∈ V, h ∈ V ∅ otherwise , S ρ = min S ρ , k (θ h: , θ g: ) if h ∈ V, g ∈ V 1 otherwise

Here, S refers to the new proof state, V refers to the set of variable symbols, h/g is a substitution from the variable symbol h to the symbol g, and θ g: denotes the embedding look-up of the non-variable symbol with index g.

For example, given two atoms H = [locatedIn, LONDON, UK] and G = [situatedIn, X, Y], the result of unify θ (H, G, (∅, 1)) with S = (∅, 1) will be a new substitution set S = (S ψ , S ρ ) where S ψ = {X/LONDON, Y/UK} and S ρ = min (1, k (θ locatedIn: , θ situatedIn: ))

A.2 OR MODULE:

Given a goal G, the or module unifies G with all facts and rules in a KB: for each rule H :-B ∈ K, after unifying G with the head H, it also attempts to prove the atoms in the body H by invoking the and module. The signature of or is L × N × S → S N , where L is the domain of goal atoms, the second argument specifies the maximum proof depth, and N denotes the number of possible output proof states. This operator is implemented as follows:

EQUATION

where H :-B denotes a rule in a given KB K with a head atom H and a list of body atoms B. a is located in b, a is situated in b, a is placed in b, a is positioned in b, a is sited in b, a is currently in b, a can be found in b, a is still in b, a is localized in b, a is present in b, a is contained in b, a is found in b, a was located in b, a was situated in b, a was placed in b, a was positioned in b, a was sited in b, a was currently in b, a used to be found in b, a was still in b, a was localized in b, a was present in b, a was contained in b, a was found in b neighborOf(a, b)

a is adjacent to b, a borders with b, a is butted against b, a neighbours b, a is a neighbor of b, a is a neighboring country of b, a is a neighboring state to b, a was adjacent to b, a borders b, a was butted against b, a neighbours with b, a was a neighbor of b, a was a neighboring country of b, a was a neighboring state to b  and S3 . For all tasks, the goal is to predict locatedIn(c, r) for every test country c and all five regions r, but the access to training atoms in the KB varies.

S1: All ground atoms 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 locatedIn(X, Y) :-locatedIn(X, Z), locatedIn(Z, Y).

S2::

In addition to S1, all ground atoms 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: locatedIn(X, Y) :-neighborOf(X, Z), locatedIn(Z, Y). 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.

S3::

In addition to S2, also all ground atoms 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 locatedIn(X, Y) :-neighborOf(X, Z), neighborOf(Z, W), locatedIn(W, Y).

B.1.2 COUNTRIES WITH MENTIONS:

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 .

B.1.3 NATIONS AND UMLS:

Furthermore, we consider the Nations, and the Unified Medical Language System (UMLS) datasets (Kok & Domingos, 2007) . 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 Rocktäschel & Riedel (2017) 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.

Note that neither Countries nor UMLS and Nations have mentions. For such a reason, for each of these datasets, we generated one equivalent mention-using a natural language sentence rather than a predicate name-and replaced a varying amount of training set triples with equivalent mentions. (Miller, 1995) , a lexical KB for the English language, where entities correspond to word senses and relationships define lexical relations between them. We also consider WN18RR (Dettmers et al., 2018) , a dataset derived from WN18 where predicting missing links is sensibly harder.

B.3 FREEBASE:

For evaluating the impact of also using mentions, we use the FB15k-237.E dataset (Toutanova & Chen, 2015; Toutanova et al., 2015) , a subset of FB15k (Bordes et al., 2013) that excludes redundant relations and direct training links for held-out triples, with the goal of making the task more realistic.

Textual relations for FB15k-237.E are extracted from 200 million sentences in the ClueWeb12 corpus, coupled with Freebase mention annotations (Gabrilovich et al., 2013) , and include textual links of all co-occurring entities from the KB set. After pruning3 , there are 2.7 million unique textual relations that are added to the KB. The number of relations and triples in the training, validation, and test portions of the data are given in Table 5 . In particular, FB15k-237.E denotes the FB15k-237 dataset augmented with textual relations proposed by Toutanova et al. (2015) .

B.4 WORDNET AND FREEBASE STATISTICS:

In order to grasp the magnitude of WN18, WN18RR and FB15k-237.E datasets, we provide their basic statistics in Table 5 .

C ADDITIONAL EXPERIMENTS C.1 ABLATION STUDIES:

The effect of attention over rules to this framework is quantised by two ablation studies, on benchmark datasets, in Table 6 , and on the large datasets, in Table 7 shows attention achieving higher or on-par performance with NaNTP without attention. In order to analyse the impact of using ANNS as a choice of heuristic, we ran additional experiments on the baseline datasets. In particular, we compared ANNS to exact nearest neighbours search, since ANNS models may not return the exact nearest neighbours. We also compared ANNS to random neighbour selection, for analysing the behaviour of the model with random neighbourhood choices.

Results are outlined in Table 8 : they show that the random neighbour, as expected, yield sensibly worse ranking results in comparison with ANNS.

A surprising exception is Nations, where ranking results were apparently higher in comparison with UMLS and Kinship: a possible explanation is that Nations only contains 14 entities, so the random neighbourhood can sometimes correspond to the exact neighbourhood. 

Hits Hits MRR @10 @3 @1 MRR @10 @3 @1 MRR @10 @3 @1 DistMult (Yang et al., 2015) 0.822 0.936 0.914 0.728 0.430 0.490 0.440 0.390 0.241 0.419 0.263 0.155 ComplEx (Trouillon et al., 2016) We can also observe that ANNS, yield very close ranking results in comparison with Exact NNS, but orders of magnitude faster. This implies that, compared to a costly Exact NNS, ANNS is an optimal choice for a heuristic, since it greatly decreases the computational complexity of the method.

Please note that experiments with Exact NNS were extremely computationally demanding and, for such a reason, we limited the neighbourhood size k to k = 1. 

:

We approximate the neighbourhood with respect to the minimum of component distances with the neighbourhood with respect to a distance of concatenated representations.

In their implementation, if several facts have the same score, the ranking function assigns them the same (best) rank, which artificially inflated their results.

The full set of 37 million textual patterns connecting the entity pairs of interest was pruned based on the count of patterns and their tri-grams, and their precision in indicating that entity pairs have KB relations.

Figures and Tables:

Figure 1: Overall architecture of NaNTPs: the two main contributions consist in a faster inference mechanism (represented by the K-NN OR component, discussed in Section 3) and two dedicated encoders, one for KB facts and rules, and another for text (discussed in Section 4).

Module. The or module unifies the goal with all the facts and rules in a KB. Concretely, for each rule H :-B in KB K, or K θ (G, d, S) unifies the goal G with the rule head H, and invokes the and module to prove atoms in the body B of the rule H, keeping track of the maximum proof depth d. For example, given a goal G = [situatedIn, Q, UK], a rule H :-B with H = [locatedIn, X, Y] and B = [[locatedIn, X, Z], [locatedIn, Z, Y]] , the model would unify the goal G with the head H of the rule, and instantiate and modules, to prove sub-goals in the body G of the rule. Note that each fact F can be represented as a rule F :-[] with no body atoms.

, two state-of-the-art Neural Link Predictors used for identifying missing facts in potentially very large KBs, on WordNet and FreeBase. For computing likelihoods of facts, DistMult and ComplEx embed each entity and relation type in a d-dimensional embedding space and use a differentiable scoring function based on the embeddings corresponding to the entity and relation of a fact. Embedding representations and scoring function parameters are learned jointly by minimising a KB reconstruction error.

Figure 3: Run-time and memory performance of NaNTP in comparison with NTP. Run-time speedup calculated as the ratio of examples per second of NaNTP and NTP. Memory efficiency calculated as a ratio of the memory use of NTP and NaNTP. Dashed line denotes equal performance -above it (green) NaNTP performs better, below it (red) performs worse.

For example, given a goal G = [situatedIn, Q, UK] and a rule H :-B with H = [locatedIn, X, Y] and B = [[locatedIn, X, Z], [locatedIn, Z, Y]], the model would instantiate an and sub-module as follows: or K θ (G, d, S) = [S |S ∈ and K θ (B, d, ({X/Q, Y/UK}, Ŝρ )), . . .]

Unification Module. In backward chaining, unification is the operator that matches two atoms like locatedIn(LONDON, UK) and situatedIn(X, Y). Discrete unification checks for equality between the elements of the atom (e.g. locatedIn = situatedIn) and binds variables to symbols via substitution (e.g. {X/LONDON, Y/UK}). Unification in NTPs matches two atoms by comparing their embedding representations via a differentiable similarity function, which enables matching different symbols with similar semantics, such as locatedIn and situatedIn.

Table content: <table/>



Table content: <table/>

Link prediction results for WN18, WN18RR, and FB15k-237.E. Results for DistMult, ComplEx, ConvE, NeuralLP, and MINERVA are fromDettmers et al. (2018);Das et al. (2017). For the sake of comparison, we also trained ComplEx and DistMult with embedding size d = 100 and for 100 epochs, as NaNTP.

Table content: <table><tr><td>WN18</td><td>WN18RR</td><td>FB15k-237.E</td></tr></table>

Explanations, in terms of rules and supporting facts, for the queries in the validation set of WN18 and WN18RR provided by NaNTPs by looking at the proof paths yielding the largest proof scores.

Table content: <table><tr><td/><td/><td colspan="4">0.941 0.947 0.936 0.936</td><td>0.440 0.510 0.460 0.410</td><td>0.247 0.428 0.275 0.158</td></tr><tr><td colspan="2">ConvE (Dettmers et al., 2018)</td><td colspan="4">0.943 0.956 0.946 0.935</td><td>0.430 0.520 0.440 0.400</td><td>0.325 0.501 0.356 0.237</td></tr><tr><td colspan="2">NeuralLP (Das et al., 2017)</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.463 0.657 0.468 0.376</td><td>0.227 0.348 0.248 0.166</td></tr><tr><td colspan="2">MINERVA (Das et al., 2017)</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.448 0.513 0.456 0.413</td><td>0.293 0.456 0.329 0.217</td></tr><tr><td colspan="2">DistMult (emb. size d = 100)</td><td colspan="4">0.782 0.931 0.910 0.658</td><td>0.411 0.463 0.423 0.382</td><td>0.214 0.402 0.240 0.127</td></tr><tr><td colspan="2">ComplEx (emb. size d = 100)</td><td colspan="4">0.923 0.948 0.941 0.904</td><td>0.420 0.469 0.431 0.395</td><td>0.206 0.373 0.222 0.126</td></tr><tr><td colspan="2">NaNTP NaNTP+Text</td><td colspan="4">0.539 0.832 0.703 0.349</td><td>0.137 0.250 0.148 0.083</td><td>0.197 0.330 0.209 0.131 0.198 0.335 0.210 0.131</td></tr><tr><td colspan="2">NaNTP+Text+Attention</td><td colspan="4">0.769 0.937 0.884 0.649</td><td>0.398 0.432 0.402 0.377</td><td>0.176 0.310 0.185 0.110</td></tr><tr><td/><td/><td/><td/><td colspan="3">Query Score Sρ Proofs / Explanations</td></tr><tr><td/><td colspan="4">part_of(CONGO.N.03, AFRICA.N.01)</td><td>0.995 0.787</td><td colspan="2">part_of(X, Y) :-has_part(Y, X) has_part(AFRICA.N.01, CONGO.N.03) part_of(X, Y) :-instance_hyponym(Y, X) instance_hyponym(AFRICAN_COUNTRY.N.01, CONGO.N.03)</td></tr><tr><td>WN18</td><td colspan="4">hyponym(EXTINGUISH.V.04, DECOUPLE.V.03)</td><td>0.987 0.920</td><td colspan="2">hyponym(X, Y) :-hypernym(Y, X) hypernym(DECOUPLE.V.03, EXTINGUISH.V.04) hypernym(SNUFF_OUT.V.01, EXTINGUISH.V.04)</td></tr><tr><td/><td colspan="4">part_of(PITUITARY.N.01, DIENCEPHALON.N.01)</td><td>0.995</td><td colspan="2">has_part(DIENCEPHALON.N.01, PITUITARY.N.01)</td></tr><tr><td/><td colspan="4">has_part(TEXAS.N.01, ODESSA.N.02)</td><td>0.961</td><td colspan="2">has_part(X, Y) :-part_of(Y, X) part_of(ODESSA.N.02, TEXAS.N.01)</td></tr><tr><td/><td colspan="4">hyponym(SKELETAL_MUSCLE, ARTICULAR_MUSCLE)</td><td>0.987</td><td colspan="2">hypernym(ARTICULAR_MUSCLE, SKELETAL_MUSCLE)</td></tr><tr><td/><td colspan="4">deriv_related_form(REWRITE, REWRITING)</td><td>0.809</td><td colspan="2">deriv_related_form(X, Y) :-hypernym(Y, X) hypernym(REVISE, REWRITE)</td></tr><tr><td>WN18RR</td><td colspan="4">also_see(TRUE.A.01, FAITHFUL.A.01) also_see(GOOD.A.03, VIRTUOUS.A.01)</td><td>0.962 0.590 0.962 0.702</td><td colspan="2">also_see(X, Y) :-also_see(Y, X) also_see(FAITHFUL.A.01, TRUE.A.01) also_see(CONSTANT.A.02, FAITHFUL.A.01) also_see(VIRTUOUS.A.01, GOOD.A.03) also_see(RIGHTEOUS.A.01, VIRTUOUS.A.01)</td></tr><tr><td/><td colspan="4">instance_hypernym(CHAPLIN, FILM_MAKER)</td><td>0.812</td><td colspan="2">instance_hypernym(CHAPLIN, COMEDIAN)</td></tr></table>

Given the Countries dataset, we replaced a varying number of training triples with mentions (see Appendix B.1.2 for details) and integrated the mentions using two different strategies: by encoding the mentions using the encoder introduced in Section 4 (Facts and Mentions) and by simply adding them to the KB (Facts).Experiments were conducted with the attention mechanism proposed in Section 3 (right) and the standard rule-learning procedure (left), each with 10 different random seeds. We can see that, on each of the datasets, using the encoder yields consistently better AUC-PR values than simply adding the mentions to the KB.

Table content: <table><tr><td/><td colspan="5">1.0 Results on Countries with Textual Mentions (without Attention)</td><td/><td/><td>1.0</td><td>Results on Countries with Textual Mentions (with Attention)</td></tr><tr><td/><td>0.8</td><td/><td/><td/><td/><td/><td/><td>0.8</td></tr><tr><td>AUC-PR</td><td colspan="5">100 200 300 400 500 600 700 800 900 Held Out Triples 0.0 0.2 0.4 0.6 Strategy Facts and Mentions Facts Dataset S1 S2 S3</td><td/><td>AUC-PR</td><td colspan="2">Held Out Triples 100 200 300 400 500 600 700 800 900 0.0 0.2 0.4 0.6 Strategy Facts and Mentions Facts Dataset S1 S2 S3</td></tr><tr><td colspan="2">1 1 1 1 1 Figure 2: 1 1 10 100 Performance improvement (x times)</td><td>2 2 2 2 2 2</td><td>5 5 5 5 5 5 NaNTP speedup (relative to NTP) 10 20 10 20 10 20 10 20 10 20 10 20 k (k-NN)</td><td>50 50 50 50 50 50</td><td>100 100 100 100 100 100</td><td>1</td><td colspan="3">2 NaNTP memory efficiency (relative to NTP) 5 10 20 50 k (k-NN)</td><td>100</td><td>Dataset Countries S1 Countries S2 Countries S3 Kinship Nations UMLS</td></tr></table>

Comparison of NaNTPs and NTPs on benchmark datasets. Double asterisk (**) denotes the performance of NTP reevaluated with the correct evaluation function (see the note in Section 6.2). Results for DistMult, ComplEx, ConvE, NeuralLP, and MINERVA are fromDas et al. (2017). 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 ANNS index in NaNTP measures and as a fail-safe, in case the model does not fit on the GPU memory.

Table content: <table><tr><td/><td/><td/><td/><td/><td colspan="2">Models</td><td/><td/></tr><tr><td>Datasets</td><td/><td>Metrics</td><td>NTP **</td><td/><td>NaNTP</td><td/><td>ComplEx</td><td>NeuralLP</td><td>MINERVA</td></tr><tr><td/><td/><td/><td/><td>k=1</td><td>k=2</td><td>k=5</td><td/><td/></tr><tr><td/><td>S1</td><td/><td colspan="7">90.83 ± 15.4 99.20 ± 1.19 97.34 ± 3.86 96.37 ± 4.23 99.37 ± 0.4 100.0 ± 0.0 100.0 ± 0.0</td></tr><tr><td>Countries</td><td>S2</td><td>AUC-PR</td><td colspan="7">87.40 ± 11.7 93.48 ± 3.29 88.48 ± 5.87 83.56 ± 7.78 87.95 ± 2.8 75.1 ± 0.3 92.36 ± 2.41</td></tr><tr><td/><td>S3</td><td/><td colspan="7">56.68 ± 17.6 85.24 ± 5.83 82.18 ± 9.11 72.68 ± 13.4 48.44 ± 6.3 92.2 ± 0.2 95.10 ± 1.20</td></tr><tr><td/><td/><td>MRR</td><td>0.35</td><td>0.51 ± 0.04</td><td>0.66 ± 0.03</td><td>0.67 ± 0.02</td><td>0.838</td><td>0.619</td><td>0.720</td></tr><tr><td>Kinship</td><td/><td>HITS@1 HITS@3</td><td>0.24 0.37</td><td>0.37 ± 0.04 0.57 ± 0.05</td><td>0.51 ± 0.04 0.78 ± 0.03</td><td>0.52 ± 0.02 0.78 ± 0.02</td><td>0.754 0.910</td><td>0.475 0.707</td><td>0.605 0.812</td></tr><tr><td/><td/><td>HITS@10</td><td>0.57</td><td>0.82 ± 0.04</td><td>0.94 ± 0.02</td><td>0.95 ± 0.00</td><td>0.980</td><td>0.912</td><td>0.924</td></tr><tr><td/><td/><td>MRR</td><td>0.61</td><td>0.66 ± 0.03</td><td>0.59 ± 0.02</td><td>0.54 ± 0.05</td><td>-</td><td>-</td><td>-</td></tr><tr><td>Nations</td><td/><td>HITS@1 HITS@3</td><td>0.45 0.73</td><td>0.51 ± 0.05 0.77 ± 0.03</td><td>0.41 ± 0.03 0.71 ± 0.02</td><td>0.36 ± 0.07 0.65 ± 0.06</td><td>--</td><td>--</td><td>--</td></tr><tr><td/><td/><td>HITS@10</td><td>0.87</td><td>0.99 ± 0.00</td><td>0.98 ± 0.01</td><td>0.98 ± 0.01</td><td>-</td><td>-</td><td>-</td></tr><tr><td/><td/><td>MRR</td><td>0.80</td><td>0.63 ± 0.04</td><td>0.80 ± 0.02</td><td>0.80 ± 0.02</td><td>0.894</td><td>0.778</td><td>0.825</td></tr><tr><td>UMLS</td><td/><td>HITS@1 HITS@3</td><td>0.70 0.88</td><td>0.49 ± 0.05 0.73 ± 0.04</td><td>0.68 ± 0.02 0.91 ± 0.01</td><td>0.68 ± 0.03 0.90 ± 0.02</td><td>0.823 0.962</td><td>0.643 0.869</td><td>0.728 0.900</td></tr><tr><td/><td/><td>HITS@10</td><td>0.95</td><td>0.89 ± 0.02</td><td>0.98 ± 0.01</td><td>0.97 ± 0.01</td><td>0.995</td><td>0.962</td><td>0.968</td></tr></table>

Mentions used for replacing a varying number of training triples in the Countries S1, S2, and S3 datasets. 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,

Table content: <table/>

Dataset statistics.

Table content: <table><tr><td>Dataset Name</td><td colspan="6">#Rel. #Entities #Train #Validation #Test #Mentions</td></tr><tr><td>FB15k-237.E (Toutanova et al., 2015)</td><td>237</td><td>27,395</td><td>272,115</td><td>17,535</td><td colspan="2">20,466 3,978,014</td></tr><tr><td>WN18 (Bordes et al., 2013)</td><td>18</td><td>40,943</td><td>141,442</td><td>5,000</td><td>5,000</td><td>-</td></tr><tr><td>WN18RR (Dettmers et al., 2018)</td><td>11</td><td>40,943</td><td>86,835</td><td>3,034</td><td>3,134</td><td>-</td></tr><tr><td>B.2 WORDNET</td><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="3">WN18 (Bordes et al., 2013) is a subset of WordNet</td><td/><td/><td/><td/></tr></table>

Table 6, however, reports that NaNTP with attention significantly outperforms NaNTP without it on WordNet datasets. C.2 ANNS VS. EXACT NNS VS. RANDOM SELECTION

Table content: <table/>

Ablation of attention over relations on NaNTPs, on benchmark datasets. ± 1.19 97.34 ± 3.86 96.37 ± 4.23 S2 90.27 ± 4.53 81.27 ± 14.44 76.9 ± 14.66 93.48 ± 3.29 88.48 ± 5.87 83.56 ± 7.78 S3 84.16 ± 8.31 85.69 ± 9.56 80.9 ± 10.12 85.24 ± 5.83 82.18 ± 9.11 72.68 ± 13.4

Table content: <table><tr><td/><td/><td/><td/><td>NaNTP</td><td/><td/><td/></tr><tr><td>Datasets</td><td>Metrics</td><td/><td>Standard</td><td/><td/><td>Attention</td><td/></tr><tr><td/><td/><td>k=1</td><td>k=2</td><td>k=5</td><td>k=1</td><td>k=2</td><td>k=5</td></tr><tr><td colspan="6">Countries 99.20 Kinship S1 AUC-PR 94.93 ± 7.58 96.58 ± 4.41 94.01 ± 3.6 MRR 0.56 ± 0.03 0.61 ± 0.04 0.57 ± 0.05 0.51 ± 0.04 HITS@1 0.41 ± 0.03 0.45 ± 0.05 0.41 ± 0.05 0.37 ± 0.04 HITS@3 0.64 ± 0.03 0.72 0.04 0.67 ± 0.05 0.57 ± 0.05</td><td>0.66 ± 0.03 0.51 ± 0.04 0.78 ± 0.03</td><td>0.67 ± 0.02 0.52 ± 0.02 0.78 ± 0.02</td></tr><tr><td/><td colspan="2">HITS@10 0.87 ± 0.02</td><td>0.92 ± 0.02</td><td>0.88 ± 0.03</td><td>0.82 ± 0.04</td><td>0.94 ± 0.02</td><td>0.95 ± 0.00</td></tr><tr><td/><td>MRR</td><td>0.63 ± 0.04</td><td>0.65 ± 0.03</td><td>0.60 ± 0.05</td><td>0.66 ± 0.03</td><td>0.59 ± 0.02</td><td>0.54 ± 0.05</td></tr><tr><td>Nations</td><td>HITS@1 HITS@3</td><td>0.46 ± 0.05 0.74 ± 0.04</td><td>0.48 ± 0.03 0.76 ± 0.03</td><td>0.42 ± 0.07 0.72 ± 0.04</td><td>0.51 ± 0.05 0.77 ± 0.03</td><td>0.41 ± 0.03 0.71 ± 0.02</td><td>0.36 ± 0.07 0.65 ± 0.06</td></tr><tr><td/><td colspan="2">HITS@10 0.99 ± 0.01</td><td>0.99 ± 0.00</td><td>0.98 ± 0.01</td><td>0.99 ± 0.00</td><td>0.98 ± 0.01</td><td>0.98 ± 0.01</td></tr><tr><td/><td>MRR</td><td>0.57 ± 0.04</td><td>0.81 ± 0.01</td><td>0.80 ± 0.02</td><td>0.63 ± 0.04</td><td>0.80 ± 0.02</td><td>0.80 ± 0.02</td></tr><tr><td>UMLS</td><td>HITS@1 HITS@3</td><td>0.42 ± 0.04 0.66 ± 0.04</td><td>0.68 ± 0.01 0.92 ± 0.01</td><td>0.68 ± 0.03 0.91 ± 0.01</td><td>0.49 ± 0.05 0.73 ± 0.04</td><td>0.68 ± 0.02 0.91 ± 0.01</td><td>0.68 ± 0.03 0.90 ± 0.02</td></tr><tr><td/><td colspan="2">HITS@10 0.85 ± 0.03</td><td>0.98 ± 0.00</td><td>0.98 ± 0.01</td><td>0.89 ± 0.02</td><td>0.98 ± 0.01</td><td>0.97 ± 0.01</td></tr></table>

Ablation of attention over relations on NaNTPs, on WN18, WN18RR and FB15k-237.E

Table content: <table><tr><td>WN18</td><td>WN18RR</td><td>FB15k-237.E</td></tr></table>

Performance of NaNTPs with attention (Attention) and without it (Standard) when using the random nearest neighbour, ANNS and exact NNS for k = 1, on benchmark datasets.

Table content: <table><tr><td/><td/><td/><td/><td/><td colspan="2">NaNTP</td><td/></tr><tr><td>Datasets</td><td/><td>Metrics</td><td colspan="2">Random</td><td colspan="2">ANNS</td><td colspan="2">Exact NNS</td></tr><tr><td/><td/><td/><td>Standard</td><td>Attention</td><td>Standard</td><td>Attention</td><td>Standard</td><td>Attention</td></tr><tr><td/><td>S1</td><td/><td colspan="2">40.54 ± 4.85 42.88 ± 3.5</td><td colspan="2">94.93 ± 7.58 99.20 ± 1.19</td><td colspan="2">96.65 ± 3.01 98.14 ± 3.31</td></tr><tr><td>Countries</td><td>S2</td><td>AUC-PR</td><td colspan="2">36.02 ± 5.56 39.32 ± 4.21</td><td colspan="2">90.27 ± 4.53 93.48 ± 3.29</td><td colspan="2">92.72 ± 4.47 91.25 ± 2.18</td></tr><tr><td/><td>S3</td><td/><td colspan="2">28.73 ± 2.82 38.46 ± 5.81</td><td colspan="2">84.16 ± 8.31 85.24 ± 5.83</td><td colspan="2">85.68 ± 5.46 89.12 ± 9.17</td></tr><tr><td/><td/><td>MRR</td><td>0.05 ± 0.00</td><td>0.06 ± 0.00</td><td>0.56 ± 0.03</td><td>0.51 ± 0.04</td><td>0.58 ± 0.02</td><td>0.52 ± 0.04</td></tr><tr><td>Kinship</td><td/><td>HITS@1 HITS@3</td><td>0.01 ± 0.00 0.03 ± 0.00</td><td>0.01 ± 0.00 0.03 ± 0.00</td><td>0.41 ± 0.03 0.64 ± 0.03</td><td>0.37 ± 0.04 0.57 ± 0.05</td><td>0.43 ± 0.02 0.66 ± 0.03</td><td>0.38 ± 0.04 0.58 ± 0.05</td></tr><tr><td/><td/><td colspan="2">HITS@10 0.11 ± 0.00</td><td>0.11 ± 0.01</td><td>0.87 ± 0.02</td><td>0.82 ± 0.04</td><td>0.89 ± 0.02</td><td>0.81 ± 0.05</td></tr><tr><td/><td/><td>MRR</td><td>0.42 ± 0.01</td><td>0.42 ± 0.01</td><td>0.63 ± 0.04</td><td>0.66 ± 0.03</td><td>0.70 ± 0.04</td><td>0.63 ± 0.02</td></tr><tr><td>Nations</td><td/><td>HITS@1 HITS@3</td><td>0.19 ± 0.02 0.54 ± 0.02</td><td>0.19 ± 0.02 0.54 ± 0.01</td><td>0.46 ± 0.05 0.74 ± 0.04</td><td>0.51 ± 0.05 0.77 ± 0.03</td><td>0.56 ± 0.05 0.81 ± 0.03</td><td>0.46 ± 0.03 0.74 ± 0.02</td></tr><tr><td/><td/><td colspan="2">HITS@10 0.96 ± 0.01</td><td>0.96 ± 0.01</td><td>0.99 ± 0.01</td><td>0.99 ± 0.00</td><td>0.99 ± 0.00</td><td>0.99 ± 0.01</td></tr><tr><td/><td/><td>MRR</td><td>0.13 ± 0.00</td><td>0.14 ± 0.01</td><td>0.57 ± 0.04</td><td>0.63 ± 0.04</td><td>0.59 ± 0.05</td><td>0.61 ± 0.05</td></tr><tr><td>UMLS</td><td/><td>HITS@1 HITS@3</td><td>0.05 ± 0.00 0.12 ± 0.01</td><td>0.06 ± 0.01 0.13 ± 0.01</td><td>0.42 ± 0.04 0.66 ± 0.04</td><td>0.49 ± 0.05 0.73 ± 0.04</td><td>0.43 ± 0.05 0.68 ± 0.05</td><td>0.46 ± 0.06 0.70 ± 0.05</td></tr><tr><td/><td/><td colspan="2">HITS@10 0.27 ± 0.01</td><td>0.28 ± 0.01</td><td>0.85 ± 0.03</td><td>0.89 ± 0.02</td><td>0.88 ± 0.03</td><td>0.86 ± 0.04</td></tr></table>

Peer review (iclr2019):
 The authors propose several techniques to speed up the previously proposed Neural Theorem Prover approach. The techniques are evaluated via empirical results on several benchmark datasets. Learning interpretable models is an important topic and the results here are interesting and valuable to the community. However, I feel that the paper in its current form is not yet ready for publication in ICLR, for the following reasons: 1) The authors propose three improvements. The first is a speed-up through nearest neighbor search instead of a brute-force search. This is the most elaborated section out of the three, yet seems like the most trivial -- unless the authors can provide an analytical bound on the loss in ntp score w.r.t the neighborhood size. It is a standard and well-known technique to restrict the search to a neighborhood, widely used in any applications of word embedding (e.g. in Khot et el*s Markov Logic Networks for Natural Language Question Answering). The attention mechanism (essentially reducing the model capacity) is also well-known but its effect in this particular framework is not properly elaborated. The same can be said for the use of mentions. 2) The section on experiment results seems a bit rushed -- the authors did mention some last-minute discovery that may affect some of the presented results. The section can be a little hard to parse. In particular, it would be useful for the authors to focus on providing more insights on how the proposed techniques improve the results, and in what ways. 3) Section 2 on the NTP framework is not very helpful for a reader that has not read the previous paper on NTP (in particular, the part on training and rule learning). For a reader that has done so, the section feels redundant.