Scalable Neural Methods for Reasoning With a Symbolic Knowledge   Base
Authors: William W. Cohen
Haitian Sun
R. Alex Hofer
Matthew Siegler
Venue:  (2020)
Keywords: question-answering
knowledge base completion
neuro-symbolic reasoning
multihop reasoning

Abstract: We describe a novel way of representing a symbolic knowledge base (KB) called a sparse-matrix reified KB.  This representation enables neural modules that are fully differentiable, faithful to the original semantics of the KB, expressive enough to model multi-hop inferences, and scalable enough to use with realistically large KBs. The sparse-matrix reified KB can be distributed across multiple GPUs, can scale to tens of millions of entities and facts, and is orders of magnitude faster than naive sparse-matrix implementations.  The reified KB enables very simple end-to-end architectures to obtain competitive performance on several benchmarks representing two families of tasks: KB completion, and learning semantic parsers from denotations.

Published as a conference paper at ICLR 2020
SCALABLE NEURAL METHODS FOR REASONING WITH A SYMBOLIC KNOWLEDGE BASE
William W. Cohen & Haitian Sun & R. Alex Hofer & Matthew Siegler
Google, Inc
(wcohen, hat t iasuun,, rofer, ms egl er @googlooog...ooooo com
ABSTRACT
We describe a novel way of representing a symbolic knowledge base (KB) called a sparse-malrix reified KB. This representation enables neural KB inference modules that are fully differentiable, faithful to the original semantics of the KB, expressive enough to model multi-hop inferences, and scalable enough to use with realistically large KBs. The sparse-matris reified KB can be distributed across multiple GPUs, can scale to tens of millions of entities and facts, and is orders of magnitude faster than naive matrix implementations. The reified KB enables very simple end-to-end architectures obtain competitive performance several benchmarks representing two families of tasks: KB completion, and learning semantic parsers from denotations.
INTRODUCTION
There has been much prior work on using neural networks generalize the contents of KB (Xiong eet al. 2017]] Bordes et al. 2013) Dettmers et al.) 2018). typically by constructing low-dimensional embeddings of the entities and relations in the KB, which are then used to score potential triples as plausible or implausible elements of the KB. We consider here the related but different problem of incorporating a symbolic KB into neural system, so as to inject knowledge from an existing KB directly into neural model. More precisely, we consider the problem of designing neural KB inference modules that are (1) fully differentiable, so that any loss based on their outputs can be backpropagated to their inputs; (2) accurate, in that they are faithful to the original semantics of the KB; (3) expressive, so they can perform non-trivial inferences; and (4) scalable, so that realistically large KBs can be incorporated into neural model.
To motivate the goal of incorporating a symbolic KB into a neural network, consider the task of learning neural semantic parsers from denotations. Many questions-e.3 what's 's the most recent movie that Quentin Tarantino directed? or which nearby restaurants have vegetarian entrees and take reservations?- are best answered by knowledge-basen -baed question-answerine where an answer found by accessing a KB. Within KBQA, a common approach is neural semantic parsing-Bi i.e., using neural methods to translate natural- languugg question into structured query against the KB (Zhong et al. 2017 Finegan-Dollak et al., 2018 Shaw et al., 2019). which is subsequently executed with symbolic KB query engine. While this approach can be effective, requires training data pairing natural-languag questions with structured queries, which is difficult to obtain. Hence researchers have also considered learning semantic parsers from denotations (Berant et al. 2013 Yih et al. 2015), where training data consists of pairs (q. A), where is a natural- question and A is the desired answer. Typically a set of KB entities-e.. if is the first sample question above, A would be the singleton set containing Once Upon a Time in Hollywood.
(KBQA) methods,
Learning semantic parsers from denotations is difficult because the end-to-end process to be learned includes a non-differentiable operation-i.e., reasoning with the symbolic KB that contains the answers. To circumvent this difficulty, prior systems have used three different approaches. Some have used heuristic search to infer structured queries from denotations (Pasupat & Liang 2016) Dasigi et al. 2019): this works in some cases but often answer could be associated with many possible structured queries, introducing noise. Others have supplemented gradient approaches with
At the time of this writing.

---

Published as a conference paper at ICLR 2020
an entity
X: weighted set of entities
vector encoding X
Net # entities in KB
Ne: # relations KB Nr: # triples in KB M Maudy, Moty. M the reified KB, encoded as matrices mapping triple id E to subject, object, and relation ids
r: an relation
weighted set relations
r: vector encoding R
My:
matrix for r
Ma: weighted sum of M, 's, see Eq |
follow(x, r): see Eq 2
Table I: Summary of notation used in the paper. (This excludes notation used in defining models for the KB completion and QA tasks of Section 3)
reinforcement learning (e.g., (Misra et al. 20188). Some systems have also "neuralized" KB reasoning. but date only over small KBs this approach natural when answers are naturally constrained to depend on small set of facts (e.g., a single table (Zhong et al. 2017 Gupta & Lewis) 2018)), but more generally requires coupling learner with some moon-differentiable mechanism to retrieve an appropriate small
subset of the KB as in (Sun et al.
In this paper, we introduce a novel scheme for incorporating reasoning on a large question- independent KB into neural network, by representing a symbolic KB with an encoding called a sparse-matrix reified KB. A sparse-matric reified KB is very compact, can be distributed across multiple GPUs necessary, and is well-suited to modern GPU architecture. For KBs with many relations, reified KB can up to four orders of magnitude faster than alternative implementations (even alternatives based on sparse-matri representations), and in our experiments we demonstrate scalability to KB with over 13 million entities and nearly 44 million facts. This new architectural component leads to radically simpler architectures for neural semantic parsing from denotations architectures aarctttioossarcchiteeeuessss based on a single end-to-end differentiable process, rather than cascades of retrieval and neural processes.
We show that very simple instantiations of these architectures are still highly competitive with the state of the art for several benchmark tasks. To our knowledge these models are the first fully end-to-end neural parsers from denotations that have been applied these benchmark lasks. We also demonstrate that these architectures scale to long chains of reasoning on synthetic tasks, and demonstrate similarly simple architectures for a second task, KB completion.
2
NEURAL REASONING WITH A SYMBOLIC KB
2.1 BACKGROUND
KBs, entities, and relations. A KB consists of entities and relations. We use x to denote an entity and to denote relation. Each entity has an integer index between and NE. where NE is the number of entities in the KB, and we write x; for the entity that has index i. A relation is a set of entity pairs, and represents relationship between entities: for instance, if 2; represents "Quentin Tarantino" and 2, represents "Pulp Fiction" then (I). would be an member of the relation director _fo_ A relation r can thus be represented as a subset of [1....,NEe Ne) (l....,NE)) Finally a KB consists set of relations and set of entities.
Weighted sets as "k-hot" vectors. Our differentiable operations are based on weighted sets, where each element z of weighted set X is associated with non-negative real number. It is convenient to define this weight to be zero for all x & X, while for x E X, a weight less than is a confidence that the set contains and weights more than I make X multiset. If all elements of X have weight 1, we say X is a hard set. A weighted set X can be encoded as an entity-set vector x E NR, where the i-th component of x is the weight of x, in X. If X is hard entity set, then this will be "k-hot" vector, for l: = [X] The set of indices of x with non- zero values is called the support of
Sets of relations, and relations as matrices Often we would like to reason about sets of relations so we also assume every relation r in a KB is associated with an entity and hence an integer index. We write r for the relation with index k. and assume that relation entities are listed first in the index of entities, so the index & for r'k is between I and NR. where NR is the number of relations in the KB. We use R for a set of relations, e.g., R- {writer_of director_of] might be such a set, and use r for a vector encoding of a set. A relation r can be encoded as a relation matrix M, E R Ne x Ne. where the value for M, [ j] is (in general) the weight of the assertion r r(z,, 2,) in the KB. In the experiments of this paper, all KB relations are hard sets, so M, [i E {0, 1}.
This is usually called second-order reasoning.
2

---

Published as a conference paper at ICLR 2020
Sparse dense matrices for relations. Scalably representing large KB requires careful consid- eration of the implementation. One important issue is that for all but the smallest KBs, a relation matrix must be implemented using sparse matrix data structure, explicitly storing all N values is impractical. For instance, consider a KB containing 10,000 movie entities and 100,000 person entities. A relationship like writer_of would have only few tens of thousands of facts (since most movies have only one or two writers), but dense matrix would have billion values.
We thus model relations as sparse matrices. Let N, be the number of entity pairs in the relation r: common sparse matrix data structures require space (N,). One common sparse matrix data structure a sparse coordinate pair (COO) encoding: with a COO encoding, each KB fact requires storing only two integers and one float.
Our implementations are based on Tensorflow (Abadi al. 2016). which offers limited support for sparse matrices. In particular, driven by the limitations of GPU architecture, Tensorflow only supports matrix multiplication between a sparse matrix COO and a dense matrix, but not between two sparse matrices, or between sparse higher-rank tensors and dense tensors.
Entity types. It often possible to easily group entities into disjoint sets by some notion "type": for example, in movie domain, all entities might be either of the type "movie", "person", or "movie extend the formalism above to typed sets of entities, and doing this
studio". It straightforward can lead to some useful optimizations. We use these optimizations below where appropriate: in particular, relation-set vectors r are of dimension R, not Ng. in the sections below. The full formal extension to typed entities and relations is given in Appendix A
2.2 REASONING IN KB
The relation-set following operation. Note that relations can also be viewed as labeled edges in a knowledge graph, the vertices of which are entities. Adopting this view, we define the r- neighbors of an entity 2; to be the set of entities 2y that connected to z; by an edge labeled r, i.e. r-neighbors(z) = {zz: (z,, E r). Extending this to relation sets, we define
R-neighbors(X X) = {æz 3r E RG x4 E X so that (I;, Er}
Computing the R-neighbors of an entity is single-step reasoning operation: e.g.. the answer to the question q ='what movies were produced or directed by Quentin Tarantino" precisely the set (R-neighbors(X) for R (producer_ee writer_ef} and X =
"Multi-hop" reasoning operations require nested R-neighborhhodss e.g. if R' = {actor_of) then R² neighiigbosr(Pt neighbors(X)) is the set of actors in movies produced directed by Quentin Tarantino.
We would like to approximate the R--eeighbrr computation with diffcrentiable operations that can be performed on the vectors encoding the sets X and Rt Let x encode weighted set of entities X, and let r encode a weighted set of relations. We first define Mj to be a weighted mixture of the relation matrices for all relations in R i.e.,
Nn rik
MR
M,,)
We then define the relation-set following operation for x and r as:
NR r(k M,.)
follow (x, r) = xM
As we will show below, this differentiable numerical relation-sel following operation can be used as a neural component perform certain types of logical reasoning. In particular, Eq[ corresponns closely to the logical R-neighborhood operation, as shown by the claim below.
Claim The support of follow(x, r) is exactly the set of R-neighbors X).
A proof and the implications of this are discussed in Appendix B
2.3 SCALABLE RELATION-SET FOLLOWING WITH REIFIED KB
Baseline implementations. Suppose the KB contains NR relations, Ng entities, and Ny triples. Typically Nn < NE < Ny & Ng. As noted above, we implement each M, sparse COO matrix,
3

---

Published as a conference paper at ICLR 2020
Strategy
Definition
Batch?
Space complexity
# Operations
sp-dense matmul
dense
sparse
or O
naive mixing
Eq
12 Eq
O(NT NE + NR) O(N + bN + bNR)
0
N R
late mixing reified KB
yes
NR
NR
0
Eq yes
D(bNT+bll
3
1
0
Table 2: Complexity of implementations of relation-ses set following, where Nr is the number of KB triples, NE the number of entities, NR the number of relations, and b is batch size.
so collectively these matrices require space O(Nr). Each triple appears in only one relation, so M in is is also size ((Vr). Since sparse-sparse matrix multiplication is not supported in Tensorflow we implement xMR using dense-sparse multiplication, so x must be a dense vector of size O(Ng), as is the output of relation-sé following. Thus the space complexity of follow(x, r) O + Ne NR). if implemented as suggested by 2
We call this the naive mixing implementation, and its complexity
summarized in T
Because Tensorflow does not support general sparse tensor contractions, it is not always possible to extend mptrie-matrix computations to minibatches. Thus we also consider a variant naive mixing called late mixing, which mixes the output of many single-relation following steps, rather than mixing the KB itself:
NR
follow(x, (x = Σ (r[k) xM,.)
(3)
1=1
Unlike naive mixing, late mixing can be extended easily to a minibatches (see Appendix C). Let be the batch size and X be minibatch of b examples i Xo]: then this approach leads Nn matrices XM, each of size O(NNE). However, they need not all be stored at once, so the space complexity becomes ObbNg + 6NR + NN). An additional cost of late mixing is that we must now sum up NR dense matrices.
reified knowledge base While semantic parses for natural questions often use small sets of relations (often singleton ones), in learning there is substantial uncertainty about what the members of these small sets should be. Furthermore, realistic wide-coverage KBs have many relations typically hundreds or thousands. This leads to situation where, at least during early phases of learning, it necessary to evaluate the result of mixing very large sets of relations. When many relations are mixed, late mixing becomes quite expensive (as experiments below show).
alternative is to represent each KB assertion (I, F3) as a tuple (i,j. where i, are the indices of 24, .Tj, and rık There are Nr such triples, so for l l,..., Nr, let (ie, ke) denote the l-th triple. We define these sparse matrices:
if = else
if m m= clse
{ if m ke { else
M Mauby [e, m] =
Mobj []
Mrd((,
Conceptually, Mauty maps the index & of the E-th triple to its subject entity; Many maps to the object entity; and M, maps to the relation. We can now implement the relation-set following as below, where @ is Hadamard product:
follow(x, r) (XM subj
rM mel
M
(4)
Notice that XM suly the triples with an entity in x their subject, rM are the triples with relation in r, and the Hadamard product is the intersection of these. The final multiplication by Many finds the object entities of the triples in the intersection. These operations naturally extend to minibatches (see Appendix). The reified KB has size O(Ny), the sets of triples that are intersected have size (bbr). and the final result is size O(b giving final size of O(b + bNg). with no dependence on NR.
Table summarizes the complexity of these three mathematically equivalent but computationally different implementions. The analysis suggests that the reified KB is preferable if there are many relations, which is the case for most realistic KB
"The larger benchmark datasets used in this paper have 200 and 616 relations respectively.
4

---

Published as a conference paper at ICLR 2020
Quarlasliac (4 relations)
Quariesisec [10k antitiis)
speedup
refie3
10
122
122
10-
150
nnttedd
late rennn)
19:40
10F
lay-valaz
1074
Num Fullatios
Aum Rolatiens
Figure 1: Left and middle: inference time in queries/sec on a synthetic KB as size and number of relations is varied. Queries/sec given as zero when GPU memory of 12Gb is exceeded. Right: speedups of reified KBs over the baseline implementations.
Distributing a large reified KB. The reified KB representation is quite compact, using only six integers and three floats for each KB triple. However, since GPU memory is often limited, it is important to be able to distribute a KB across multiple GPUs Although to our knowledge prior implementations of distributed matrix operations (e.g.. (Shazeer et al., 2018) do not support sparse matrices, sparse-dense matrix multiplication can be distributed across multiple machines. We thus implemented distributed sparse-matrix implementation of reified KBs. We distibuted the matrices that define a reified KB "horizontally", so that different triple ids are stored on different GPUs. Details are provided in Appendix D
3 EXPERIMENTS
3.1 SCALABILITY
Like prior work (Cohen et al., 2017 De Raedt et al. 2007), we used a synthetic KB based on an n-by-n grid to study scalability of inference. Every grid cell is an entity, related to its immediate neighbors via relations north, south, east, and west. The KB for an n-by-n grid thus has O(n²) entities and (nn²) triples. We measured the time to compute the 2-hop inference follow x, r), r) for minibatches = 128 one-ho hot vectors, and report it as queries per second (qps) on a single GPU (e.g., 1280 would mean single minibatch requires 100ms). We also compare to a key-value memory network (Miller et al. 2016),, using an embedding size of 64 for entities and relations, where there is one memory entry for every triple in the KB. Further details are given in Appendix
The results are shown Figure and middle), on a log-log scale because some differences are very large. With only four relations (the leftmost plot), late mixing is about 3x faster than the reified KB method, and about 250x faster than the naive approach. However, for more than around 20 relations, the reified KB is faster (middle plot). As shown the rightmost plot, the reified KB 50x faster than late mixing with 1000 relations, and nearly 12,000x faster than the naive approach.
With this embedding size, the speed of the key-v network is similar the reified KB for only four relations, however it is about 7x slower for 50 relations and 10k entities. Additionally, the space needed to store triple is much larger in a key-value network than the reified KB, so memory is exhausted when the KB exceeds 200,000 entities (with four relations), or when the KB exceeds 100 relations (with 10,000 entities.) The reified KB scales much better, and can handle 10x as many entities and 20x as many relations.
3.2 MODELS USING REIFIED KBs
As discussed below in Section 4 the reified KB is closely related to key-value memory networks, so it can be viewed as a more efficient implementation of existing neural modules, optimized for reasoning with symbolic KBs. However, being able to include an entire KB into model can lead to a qualitative difference in model complexity, since is not necessary to build machinery to retrieve from the KB. To illustrate this, below we present simple models for several tasks, each using the reified KB in different ways, as appropriate to the task. We consider two families of tasks: learning semantic parsers from denotations over large KB, and learning complete KB.
5

---

Published as a conference paper at ICLR 2020
KBQA for multi-hop questions. MetaQA (Zang al. 2018) consists of 1.2M questions, evenly distributed into one-hop, two-hop, and three-hop questions, (E.g. the question "who acted in a movie directed by Quentin Tarantino?" is two-hop question.) The accompanying KB (Miller al. 2016) contains 43k entities and 186k triples. Past work treated one-hop, two-hop and three-hop questions separately, and the questions labeled with the entity ids for the "seed entities" that begin the reasoning chains (e.g., the question above would be tagged with the id of the entity for Quentin Tarantino).
Using a reified KB for reasoning means the neural model only needs to predict the relations used at each stage the reasoning process. For each step of inference we thus compute relation sets r' using a differentiable function of the question, and then chain them together with relation-set following steps. Letting x be the set of entities associated with q, the model we use is:
for t = 1, = f(()); x = follow(x'
where where follow(x* 1- .'') is implemented with a reified KB as described in Eq.
To predict an answer on a T-hop subtask, we compute the softmax of the appropriate set x²", We used cross entropy loss of this set against the desired answer, represented as a uniform distribution over entities in the target set. Each function f' (q) is a different linear projection of a common encoding for specifically a mnean-pooling of the tokens in q encoded with a pre-trained 128 128-dimensional word2vee model (Mikolov et al., 2013). The full KB was loaded into a single GPU in our experiments.
It is interesting to contrast this simple model with the one proposed by Zhang et al. (2018). The "mod- ule for logic reasoning" they propose in Section 3.4 fairly complex, with description that requires a figure, three equations, and page of text; furthermore, training this model requires constructing an example-dependent subgraph for each training instance. In our model, the "logic reasoning" " (and all interaction with the KB) has been encapsulated completely in the follow(x, r) operation-which, as we will demonstrate below, can be re-used for many other problems. Encapsulating all KB reasoning with single scalable differentiable neural module greatly simplifies modeling: in particular, the problem of learning a structured KB query has been reduced to learning a few differentiable functions of the question, one for each reasoning "hop". The learned functions also interpretable: they mixtures of relation identifiers which correspond to soft weighted sets of relations, which in turn softly specify which KB relation should be used in each stage of the reasoning process. Finally, optimization is simple, as the loss on predicted denotations can be back poo-pprop to the relation pradiictnpreiitiion functions.
A similar modeling strategy is used in all the other models presented below.
KBQA on FreeBase. WebQuestionsSP YYih et al., 2016) contains 4737 natural language questions, all of which are answerable using FreeBase (Bollacker et al. 2008). large open-domain KB. Each question q is again labeled with the entities that appear in it.
FreeBase contains two kinds of nodes: real-world entities, and compound value types (CVTs), which represent non- bonabi relationships or events (e.g., a movie release event, which includes a movie id, a date, and a place.) Real-world entity nodes can be related to each other or to CVT node, but CVT nodes are never directly related to each other. In this dataset, all questions can answered with 1- or 2-hop chains, and all 2-hop reasoning chains pass through CVT entity; however, unlike MetaQA, the number of hops is not known. Our model thus derives from g three relation sets and then uniformly mixes both potential types of inferences:
FE-E = fE-EEQ)); TE-CVT = fE-CCT((); FCVT->E = fevt-se(9) à = follllloofolloooxxrreee--oo rEVTV) follow(x FE-
We again apply softmax to å and use cross entropy loss, and fE-ME SE--CVT, and fcvT--r - are again linear projections of word2vec encoding of q. We used a subset of Freebase with 43.7 million facts and 12.9 million entities, containing all facts in Freebase within 2-hops of entities mentioned in any question, excluding paths through some very common entities. We split the KB across three 12-Gb GPUs, and used a fourth GPU for the rest of the model.
This dataset is a good illustration of the scalability issues associated with prior approaches to including a KB in a model, such as kay-value memory networks. A key-value network can be trained to implement something similar to relation-set following, if it stores all the KB triples in memory. If

---

Published as a conference paper at ICLR 2020
assume 64-float embeddings for the 12.9M entities, the full KB of 43.7M facts would be 67Gb in size. which is impractical. Additionally performing a softmax over the 43.7M keys would be prohibitively expensive, as shown by the experiments of Figure [I This is the reason why in standard practice with key-value memory networks for KBs, the memory is populated with a heuristically subset of the KB, rather than the full KB. We compare experimentally to this approach in Table
Knowledge base completion. Following Yang et al. (2017) we treat KB completion as an inference task, analogous to KBQA: a query q is relation name and a head entity x, and from this we predict set of tail entities. We assume the answers are computed with the disjunction of multiple inference chains of varying length. Each inference chain has a maximum length of T and we build N distinct inference chains in total, using this model (where x = x for every chain i):
for ,,...,,
N and ( 1....,, T: ri (1); x follow (x ..)) + +x
The final output is a softmax of the mix of all the x²" s: i.e., we let å softmax (Eie xf)) The
update x = follow(x r!) + x gives the model access to outputs of all chains of length less than (for more intuition see Appendix E) The encoding of is based on lookup table, and each f is learned linear transformation of g embedding [
An encoder-decoder architecture for varying inferential structures. To explore performance on more complex reasoning tasks, we generated simple artificial natural-language sentences describing longer chains of relationships on 10-by-10 10 grid. For this task used encoder-decoder model which emits chains of relation-set following operations. The question is encoded with the final hidden state of an LSTM, written here h". We then generate a reasoning chain of length up to T using a decoder LSTM. At iteration L, the decoder emits scalar probability of "stopping". p'. and a distribution over relations to follow r', and then, as we did for the KBQA tasks, sets x' ffoloo(x' .')). Finally the decoder updates its hidden state to h' using an LSTM cell that "reads" the "input" r'-1, For each step t. the model thus contains the steps
p' = (p )); r' r'= ft (hh-))); x' = =follow(x' r'): = LSTM(h' h- 1,--1)
The final predicted location is mixture of all the x, 's weighted by the probability of stopping Pa at iteration i.e., å = softmax(> t== x².p" IIe= p² )). The function f, is softmax over linear projection, and fp is a logistic function. In the experiments, we trained on 360,000 sentences requiring between and T hops and tested on additional 12,000 sentences.
Experimental results. We next consider the performance of these models relative to strong baselines for each task. We emphasize our goal here is not to challenge the current state of the on any particular benchmark, and clearly there are many ways the models of this paper could be improved. (For instance, our question encodings are based on word2vec, rather than contextual encodings (Devlin et al. 2018), and likewise relations are predicted with simple linear classifiers, rather than, say, attention queries over some semantically meaningful space, such as might be produced with language models or KB embedding approaches (Bordes et al. 2013)). Rather, our contribution is to present generally useful scheme for including symbolic KB reasoning into a model, and we have thus focused on describing simple, easily understood models that do this for several tasks. However, it is important to confirm experimentally that the reified KB models "work" e.g. that they are amenable to use of standard optimizers, etc.
Performance (using Hits@ 1) of our models on the KBQA tasks is shown in Table 3 For the non- synthetic tasks we also compare to a Key-Value Memory Network (KV-Mem) baseline (Miller et al.) 2016). For the smaller MetaQA dataset, KV-Mem is initialized with all facts within 3 hops of the query entities, and for WebQuestionsSP it is initialized by random-wall process seeded by the query entities (see (Sun et al. 2018 Zhang et al.) 2018) for details). ReifKB consistently outperforms the baseline, dramatically little degradation as chain length increases, with Hits@ I for 10 hops still 89.7%. It also illustrates the ability to predict entities in KB, well relations.
for longer reasoning chains. The synthetic grid task shows that there is very
We also compare these results to two much more complex architectures that perform end-to-end question answering in the same setting used here: VRN (Zhang et al. 2018). GRAFT-Net (Sun et al. 2018). and PullNet (Sun et al. 2 All three systems build question-dependen subgraphs of the
'In the experiments the hyperparameters T E {1,...,6)) 6] and N 21,2,33 dev set.
7

---

Published as a conference paper at ICLR 2020
ReifKB (ours)
ReifKB mask
KV-Mem (haseline)
VRN
GRAFI-
PullNet
non-differentiahe components
Net
of architectures
WebQSP
52.7
46.7
67.8
68.1
KV-Mem
initial memory retrieval
MetaQA
1-hop
96.2
95.8
97.5
97.0
97.0
2-hop
81.1
95.4
25.1
89.9
94.8
99.9
VRN
question-specife
3-hop
72.3
79.7
10.1
62.5
77.2
91.4
GRAFTNG
subgraph retrieval
Grid
PullNet all iterative retrievals
5-hop
98.4
10-hop
89.7
ReifKB(ours)
nome
Table 3: Hits @1 the KBQA datasets. Results for KV-Mem and VRN MetaQA are from (Zhang et al. 2018); results for GRAFT-Net, PullNet and KV-Mem on WebQSP are from (Sun et al. 2018 and (Sun et al. (019)).
KB, and then use graph CNN-like methods (Kipf & Welling 2016) to "reason" with these graphs. Although not superior, ReifKB model is competitive with these approaches, especially on the most difficult 3-hop setting.
A small extension to this model is to mask the seed entities out of the answers (sce Appendix [E) This model (given as ReifKB + mask) has better performance than GRAFT-Net on 2-hop and 3-hop questions.
For KB completion, we evaluated the model on the NELL-995 dataset (Xiong et al. paired with KB with 154k facts, 75k entities, and 200 relations. On the left of Table 4 we compare
2011 which is
our model with three popular embedding approaches (results are from Das et al. (201) )). The reified KB model outperforms DistMult (Yang et al. 2014), is slightly worse than ConvE (Dettmers et al. 2018), and is comparable to ComplEx (Trouillon et al. 2017).
The competitive performance of the ReifKB model is perhaps surprising, since it has many fewer parameters than the baseline models-only one float and two integers per KB triple, plus small number of parameters to define the f functions for each relation. The ability use fewer parameters is directly related to the fact that our model directly uses inference on the existing symbolic KB in its model, rather than having learn embeddings that approximate this inference. Or course, since the KB is incomplete, some learning is still required, but learning is quite different: the system learns logical inference chains the incomplete KB that approximate target relation. this setting for KBC, the ability to perform logical inference "out of the box" appears to be very advantageous.
Another relative disadvantage of KB embedding methods is that KB embeddings are generally transductive they only make predictions for entities seen in training. As non-transductive baseline, we also compared to the MINERVA model, which uses reinforcement learning (RL) methods to learn how to traverse KB to find desired answer. Although RL methods are less suitable "neural modules", MINERVA is arguably a plausible competitor to end-to-end learning with a reified KB.
MINERVA slightly outperforms simple KB completion model on the NELL-995 task. However, unlike our model, MINERVA is trained to find a single answer, rather than trained to infer a ser of answers. To explore this difference, we compared to MINERVA on the grid task under two conditions: (1) the KB relations are the grid directions north, south, east and west, so the output of the target chain is always single grid location, and (2) the KB relations also include a "vertical move" (north or south) and "horizontal move" (east or west), so the result of the target chain can be set of locations. As expected MINERVA's performance drops dramatically in the second case, from 99.3%
NELL
L-995
ReifKB (Ours)
MINERVA
H@1
H@
NELL-995
64.1
66.3
ReifKB (Ours)
64.1
82,4
Grid with seed entity
61.0
79.5
10-hop NSEW
98.9
99.3
ComplEx*
61.2
82.7
10-hop NSEW-VH
73.6
34.4
CouvE*
67.2
86.4
MetaQA 3-hop
72.3
41.7
Starred KB completion Table 4: Left: Hits@1 and Hits 10 for KB completion on NELL 995.
methods are transductive, and do not generalize to entities not seen in training. Right: Comparison to MINERVA on several tasks for 1.
8

---

Published as a conference paper at ICLR 2020
Ruric con IRAFT Pull
NELL-995
MetaQA-3hop
WcbQuestionsSP
130
# Facts
154,213
196,453
43,724,175
# Entities
75,492
43,230
12,942,798
# Relations
200
9
616
Time (scconds) 44.3
72.6
1820
200
350
750
300
126
Table 5: Left, time run 10K examples for KBs of different size. Right, time for 10k examples vs @its@1 I performance for ReifKB compared to three baselines on MetaQA-3hop questions.
@its@1 to 34.4 %, while our model's performance is more robust. MetaQA answers also be sets, so we also modified MetaQA so that MINERVA could be used (by making the non-entity part of the sentence the "relation" input and the seed entity the "start node" input) and noted similarly poor performance for MINERVA. These results are shown on the right of Table 4
we compare the training time of our model with minibatch size of 10 on NELL-995, MetaQA, and WebQuestionsSP. With over 40 million facts and nearly 13 million entities from Freebase, takes less than 10 minutes to run one epoch over WebQuestionSSP (with 3097 training examples) on four PI00 GPUs. In the accompanying plot, we also summarize the tradeoffss between accuracy and training time for our model and three baselines on the MetaQA 3-hop task. (Here ideal performance is toward the upper left of the plot). The state-of- tftte-of-the-art art PullNet [Sun et al. (2019) system, which uses a learned method to incrementally retrieve from the KB, is about 15 times slower than the reified KB system. GRAFT-Net is only slightly less accurate, but also only slightly faster: recall that GRAFT-Net uses a heuristically selected subset (of up to 500 triples) from the KB for each query. while system uses the full KB. Here the full KB is about 400 times large as the question-specific subset used by GRAFT-Net. A key-value memory baseline including the full KB is nearly three times slow as system, while also performing quite poorly.
In Tables 5
4 RELATED WORK
The relation-set following operation using reified KBs is implemented in an open-source pack- age called NQL, for neural query language. NQL implements a broader range of operations for manipulating KBs, which are described in a companion paper (Cohen al., 2019). This paper focuses on implementation and evaluation of the relation-set following operation with different KB representations, issues not covered in the companion paper.
TensorLog (Cohen et al. 2017), a probabilistic logic which also can be compiled to Tensorflow, and hence is another differentiable approach to neuralizing a KB. TensorLog is also based on sparse matrices, but does not support relation sets, making it unnatural to express the models shown in this paper, and does not use the more efficient reified KB representation. The differentiable theorem prover (DTP) is another differentiable logic (Rocktäschel & Riedel 2017), but DPT appears to be much less scalable: it has not been applied to KBs larger than a few thousand triples. The Neural ILP system (Yang et al. 2017) uses approaches related late mixing together with an LSTTM controller to perform KB completion and some simple QA tasks, but it is a monolithic architecture focused on rule-learning, while in contrast we propose a re-usable neural component, which can be used in as a component in many different architectures, and a scalable implementation of this. It has also been reported that neural ILP does not scale the size of the NELL995 task (Das et al. 2017).
The goals of this paper are related to KB embedding methods, but distinct. In KB embedding, models are generally fully differentiable, but is not considered necessary (or even desirable) to accurately match the behavior of inference in the original KB. Being able to construct a learned approximation of a symbolic KB is undeniably useful in some contexts, but embedded KBs also have many disadvantages. In particular, they are much larger than a reified KB, with many more learned parameters- parameters-typicallyy a long dense vector for every KB entity. Embedded models are typically evaluated by their ability to score single triple accurately, and many models are not capable of executing multi-step KB inferences efficiently; further, models that do allow multi-step inference are known to produce cascaded errors on long reasoning chains (Guu al. 2015 Hamilton et al. 2018). In contrast we focus on accurate models of reasoning in a symbolic KB, which requires consideration of novel scalability issues associated with sparse matrice representations.
9

---

Published as a conference paper at ICLR 2020
Mathematically, our definition of relation-set following is much like the bilinear model for path following from Guu et al. (2015); however, we generalize this to path queries that include weighted sets of relations, allowing the relations in paths to be learned. Similar differences apply to the work of Hamilton et al. 2018), which extends the work Guu et (2015) to include intersection operations. The vector representation used here for weighted sets in reified KB makes intersection trivial to implement, as intersection corresponds to Hadamard product. Conveniently set union also corresponds vector sum, and the complement of X is x, which perhaps why only a single additional neural operation is needed to support the KB reasoning tasks needed for the five benchmark tasks considered here.
Neural architectures like memory networks (Weston et al. 2014), or other architectures that use attention over some data structure approximating assertions (Andreas et al., 2016, Cupta & Lewis) 2018) can be used to build soft versions of relation-set following: however, they also do not scale well to large KBs, so they are typically used either with a non-differentiable ad hoc retrieval mechanism, or else in cases where small amount of information is relevant question (Weston al. 2015 Zhong et al. 2017). Similarly graph CNNs (Kipt & Welling 2016) also can be used for reasoning, and often do scaled to tens of millions of triples/edges or millions of entities/graph nodes. Additionally, while graph CNNs have been used for reasoning tasks, the formal connection between them and logical reasoning remains unclear, whereas there is a precise connection between relation-set following and inference.
sparse matrix multiplication, but again existing implementations have not been
Reinforcement learning (RL) methods have been used to learn mappings from natural-languse questions non-differentiable logical representations (Liang et al. 2016 2018) and have also
been applied to KB completion tasks (Das et al. 2017 Xiong et al. 2017). Above we compared experimentally MINERVA, one such method; however, the gradient gradient-based approaches enabled by our methods are generally preferred as being easier to implement and tune on new problems, and easier to combine in a modular way with other architectural elements.
CONCLUSIONS
We introduced here novel way of representing a symbolic knowledge base (KB) called a sparse- matrix reified KB. This representation enables neural modules that are fully differentiable, faithful to the original semantics of the KB, expressive enough to model multi-hop inferences, and scalable enough use with realistically large KBs. In a reified KB, all KB relations are represented with three sparse matrices, which can be distributed across multiple GPUs, and symbolic reasoning on realistic KBs with many relations much faster than with naive implementationss magnitude faster on synthetic-data experiments compared to naive sparse-matrix implementations.
than four orders of
This new architectural component leads to radically simpler architectures for neural semantic parsing from denotations and KB completion-in particular, they make it possible to learn neural KBQA models in a completely end-to-end way, mapping from text to KB entity sets, for KBs with tens of millions of triples and entities and hundreds of relations.
ACKNOWLEDGMENTS
The authors are greatful to comments and suggestions from Fernando Peireira, Bhuwan Dhingra, and many other colleagues on earlier versions of this work.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In 12th {USENIX) Symposium on Operating Systems Design and Implementation ((OSD/) 16), pp. 265 283, 2016.
Jacob Andreas, Mareus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 39-48, 2016.
Jonathan Berant, Andrew Chou, Roy Frostig, and Percy Liang. Semantic parsing on freebase from question-answer pairs. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pp. 1533-1544, 2013.
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: collabora- tively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 1247-1250. AcM, 2008
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, pp. 2787-2795, 2013.
William W Cohen, Fan Yang, and Kathryn Rivard Mazaitis. Tensorlog: Deep learning meets probabilistic DBs. arXiv preprint arXiv: 170.00539., 2017.
William W. Cohen, Matthew Siegler, and R. Alex Hofer Neural query language: A knowledge base query language for Tensorflow. CoRR, abs/ ftss/1905.06200 2019. URL btttp://arxiv.oo
abs/1905. 06209
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishna- murthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. arXiv preprint 1 2017.
Pradeep Dasigi, Matt Gardner, Shikhar Murty, Luke Zettlemoyer, and Eduard Hovy. Iterative search for weakly supervised semantic parsing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 2669-2680, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics. doi: 10. 10.18653/11/119-12777 URL https
www. ac wwt.://www.....r//tttoooo..////.
Luc De Raedt, Angelika Kimmig, and Hannu Toivonen. Problog: A probabilistic Prolog and its application in link discovery. IJCAI, volume 7, pp. 2462-2467. Hyderabad, 2007.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d
knowledge graph embeddings. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Jacob Devlin, Ming-Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 11X.::8800.0480, 2018.
Catherine Finegan-Dollate Jonathan K Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. Improving text-to-SQQ evaluation methodology. arXiv preprint arXiv:/806.09029 2018.
Nitish Gupta and Mike Lewis. Neural compositional denotational semantics for question answering. CoRR, abs/1 09942,99222. 2018. URL /ttp::p//aaxxxw.rrr////////1/11 09942
Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs in vector space. arXiv preprint arXiv:1506 150.000996 2015.
Will Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovec. Embedding logical queries on knowledge graphs. In Advances in Neural Information Processing Systems, pp. 2026- 2037, 2018.
11

---

Published as a conference paper at ICLR 2020
Thomas N Kipf and Max Welling. Semi- eumi-supereised classification with graph convolutional networks. arXiv preprint 1o09:v6609002900000 2016.
Chen Liang, Jonathan Berant, Quoc Le, Kenneth D Forbus, and Ni Lao. Neural symbolic machines: Learning semantic parsers on freebase with weak supervision. arXiv preprint 2016.
Chen Liang, Mohammad Norouzi, Jonathan Berant, Quoe V Le, and Ni Lao. Memory augmented policy optimization for program synthesis and semantic parsing. In Advances in Neural Information Processing Systems, pp. 10994-0006, 2018.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pp. 3111-3119, 2013.
Alexander H. Miller, Adam Fisch, Jesse Dodge, Mosie-Hoseein Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. CoRR, abs/1600.00 12, 2016. http::t////rxx..crtraaaaa///////
wtg. wwwp//////////eeeeeeeee/a/eeeaee 606 C3126
Dipendra Mísra, Ming-Wei Chang, Xiaodong He, and Wen-tau Yih. Policy shaping and generalized update equations for semantic parsing from denotations. In Proceedings of the 2018 Conference on Empirical Methods Natural Language Processing, pp. 2442-2452, 2018.
Panupong Pasupat and Percy Liang. Inferring logical forms from denotations. arXiv preprint arXiv: 1606.06900, 2016.
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. In Advances in Neural Information Processing Systems, pp. 3788-3800, 2017.
Peter Shaw, Philip Massey, Angelica Chen, Francesco Piccinno, and Yasemin Altun. Generating logical forms from graph representations of text and entities. arXiv preprint 1rX.iv:905.08440 2019.
Noam Shazeer, Youlong Cheng, Niki Parmar, Dustin Tran, Ashish Vaswani, Penporn Koanantakool, Peter Hawkins, HyoukJoong Lee, Mingsheng Hong. Cliff Young, Ryan Sepassi, and Blake A. Hechtman. Mesh-tensorfloww Deep learning for supercomputers. CoRR, 0bbs/1811.020S 2018. URL httt::://axxv..o///aa..
02084
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William W Cohen. Open domain question answering using early fusion of knowledge bases and text. EMNLP, 2018.
Haitian Sun, Tania Bedrax-Waar Weiss, and William W Cohen. Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text. arXiv preprint 1904009904 2019.
Théo Trouillon, Christopher Dance, Éric Gaussier, Johannes Welbl, Sebastian Riedel, and Guil- laume Bouchard. Knowledge graph completion via complex tensor factorization. The Journal of Machine Learning Research, 18(1) (14:)44354772 2017.
Jason Weston, Sumit Chopra, and Antoine Bordes. arXiv:1410.3916 2014.
Memory networks.
arXiv preprint
Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart van Merriënboer, Armand Joulin, and Tomas Mikolov. Towards ai-complete question answering: A set of prerequisite toy tasks. arXiv preprint / 2015.
Wenhan Xiong, Thien Hoang, and William Yang Wang. Deeppath: reinforcement learning method for knowledge graph reasoning, arXiv preprint arXiv: 2017.
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. arXiv preprint arXiv:1412.6575, 2014.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In Advances Neural Information Processing Systems, pp. 2319-2328, 2017.
12

---

Ming-Wei Published as a conference paper at ICLR 2020
Wen-tau Yih, Ming- query graph generation: Question answering with knowledge base. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume Long Papers), volume 1, pp. 1321-1331, 2015.
King-Wei Wei Chang, Xiaodong He, and Jianfeng Gao. Semantic parsing via staged
Wen-tau Yih, Matthew Richardson, Chris Meek, Ming- Wei Chang, and Jina Suh. The value of semantic parse labeling for knowledge base question answering. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), volume 2, pp- 201-206, 2016.
Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander J Smola, and Le Song. Variational reasoning for question answering with knowledge graph. In AAAI, 2018.
Victor Zhong, Caiming Xiong, and Richard Socher. Seq2sql: Generating structured queries from natural language using reinforcement learning. arXiv preprint arXiv:1709.00/00 2017.
13

---

Published as a conference paper at ICLR 2020
A ADDITIONAL BACKGROUND AND EXTENSIONS
KBs, entities, and relations, and types. In the more general case, a KB consists of entities, relations, and types. Again use I to denote an entity and r to denote a relation. We also assume each entity has type, written type(z), and let N- denote the number of entities of type т. Each entity x in type r has a unique index index, (x)) which is an integer between and Nz. We write Zr,i for the entity that has index i in type т. x; if the type is clear from context.
Every relation r has a subject type Teubj and an object type Tokj, which constrain the types of x and x' for any pair (2z, x²) r. Hence can be encoded as a subset of (1....,,,, Nr,..; {l..... Na Relations with the same subject and object types are called type-compatibl.
Our differentiable operations are based typed weighted sets, where again each element of weighted set X is associated with a non-negative real number, written w|æ E X]. and we define w[x E X] = 0 for all x & X. A set X has type rype(X) т, and all members of Xmust be entities of type т.
We also assume every relation r in KB is associated with entity Ir, and hence, an index and a type. Sets of relations R are allowed only if all members are type-compatille. For example R = (writer_of, director- might be set of type-compatible relations.
weighted set X of type 7 can be encoded as an entity-ser vector x E RRN, where the i-th component of is the weight of the i-th entity of that type in the set X: e.g., x(inder, (x)] wIx E X]. We also use (xp to denote the type of the set encoded by x.
relation with subject type TI and object type 72 can be encoded relation matrix M, R.N, XNr2.
Background on sparse matrices. A COO encoding consists of N, 2 matrix Ind, containing pairs of entity indices, and a parallel vector w, E IR 8. containing the weights of the corresponding entity pairs. In this encoding, if (i is k of Ind, then [r [k]. and if (i, j) does not appear in Ind,, then M(i j] is zero.
Extension to soft KBs. the paper, we assume the non-zero weights in a relation matrix M, are all equal to 1.0. This can be relaxed: if assertions in KB are associated with confidences, then this confidence can be stored in M,. In this case, the reified KB must be extended to encode the weight for triple: we find it convenient to redefine M, to hold that weight. In particular if the weight for the the l-th triple Th (2, 2zz) is We, then we let
uy if m ke 0 else
M m]
=
B PROOF OF CLAIM 1
Claim The support of follow(x,,) r) is exactly the set of R-neighbors X).
To better understand this claim, let follow(x, r). The claim states z can approximate the R neighborhood of any hard sets R, X by setting to zero the appropriate components of x and r. is also clear that z[j] decreases when one decreases the weights in of the relations that link v, to entities in X, and likewise, zíj] decreases one decreases the weights of the entities in that are linked æ, via relations in R. so there is smooth, differentiable path to reach this approximation.
More formally, consider first a matrix M, encoding a single binary relation r, and consider the vector x' xM, As weighted sets, X and have non-negative entries, so clearly for all i,
x' [ + 0 iff 3j [t + 0 x(]] + O iff Ery E X so that (x,, E
and so if r is one-hot vector for the set {r) then the support of follow(x, r) is exactly the set r-neighbors(()) Finally note that the mixture M has the property that Mg(i(e)), i(e>)] > 0 exactly when éj is related e2 by some relation R.
14

---

Published as a conference paper at ICLR 2020
C MINIBATCHED COMPUTATIONS OF NAIVE AND LATE MIXING
The major problem with naive mixing is that, in the absence general sparse tensor contractions, it is difficult adapt mini-batches-i.ee and R with minibatch size b. An alternative strategy is late mixing, which mixes the output of many single-relation following steps, rather than mixing the KB itself:
setting in which and are replaced with matrices X
NR Σ
follow X.R)
R XM,)
Here R(: k). the k-th column of R. is "broadcast" to element of the matrix XM,. As noted in the body of the text, while there are Nn matrices XM,, each of size ObbNg), they need not be stored at once, so the space complexity becomes ObbN bNn + Nr); however we must now sum up Na dense matrices.
The implementation of relation-set following for the reified KB can be straightforwardedly extended minibatch:
follow X, R)
(XM subj subj
RM
Moby
D DISTRIBUTED MATRIX MULTIPLICATION
Matrix multiplication xM was distributed as follows: can be split into a "horizontal stacking" of m submatrices, which we write as : and M can be similarly partitioned into m² submatrices. We then have the result that
M
M1
M
xM X11 . xm]
x
M
X M
M
Mm.
Mm.m
This can be computed without storing either X M single machine, and mathematically applies to both dense and sparse matrices. In our experiments we distibuted the matrices that define a reified KB "horizontally". , so that different triple ids l are stored different GPUs.
Specifically, we shard the "triple index" dimension Ny of matrices Maunj, Myat and Maty in Eq. to perform distributed relation-set following the reified KB. Let Mautj. be the i'th shard of matrix Maubj. and thus Mauby [M i: M Muttimml 1T R N Mošj and M,et are represented in the similar way. A distributed relation-se set following is computed as a combination of relation-set following results on shards KB.
follow(x (x, r) (XM subj rM Mobi
Mobj.1
[xMT eudy. ....: xM
subj ml 2 [r
ie rM
vet.
(5)
Moti.m
- (xM Subjs @ rM Tel, M
(6)
This method can be easily extended a mini-batch of examples X.
E EXPERIMENTAL DETAILS
Reproducing experiments. To reproduce these experiments, first download and install the Google language packageF Many of the experiments in this paper can be reproduced us- ing scripts stored the some subdirectory of the source directory languagee/nan /nmm///moss: demos: for example, the scalability experiments of Figure [ can be performed using scripts in httpa/////g//eeeeo/o//g///ooooar
"https:// thub. com wwt.:/owwmoooooe.. researhheeeeeeeeeeeeeeee languargch/ag
15

---

Published as a conference paper at ICLR 2020
Grid experiments. In the grid experiments, the entity vector is randomly-chosen singleton set, and the relation vector r weights relations roughly uniformly- moroomly--rree more specifically, each relation has weight 1+c where is drawn uniformly at random between 0 and 0.001 ["] We vary the number of relations by inventing m new relation names and assigning existing grid edges to each new relation. These experiments were conducted on Titan Xp GPU with 12Gb of memory.
For key-value networks, the key is the concatenation of a relation and a subject entity, and the value the object entity. We considered only the run-time for queries on untrained randomly-initialized network (since run-time performance on a trained network would be the same); however, it should be noted that considerable time that might be needed to train the key-value memory approximate the KB. (In fact, it is not obvious under what conditions KB can be approximated well by the key-value memory.)
We do not show results on the grid task for smaller minibatch sizes, but both reified and late mixing are about 40x slower with 1 than with 128.
WebQuestionsSP experiments. For efficiency, on this problem we exploit the type structure of the problem (see Appendix [A.. Our model uses two types of nodes, CVT and entity nodes. The model also uses three types of relations: relations mapping entities to entities, relations mapping entities to CVT nodes; and relations mapping CVT nodes to entity nodes.
MetaQA experiments. An example of a 2-hop question in MetaQA could be "Who co-starred with Robert Downey Jr. in their movies?", and the answer would be a set of actor entities, e.g., "Chris Hemsworth", "Thomas Stanley", etc. Triples in the knowledge base are represented as (subject, relation, object) triples, e.g., ("Robert Downey Jr.", "act in", "Avengers: Endgame"), ("Avengers: Endgame", "stars", "Thomas Stanley"). etc. The quoted strings here all indicate KB entities.
We also observed that in the MetaQA 2-hop and 3-hop questions, the questions often exclude the seed entities (e.g., "other movies with the same director as Pulp Fiction"). This can be modeled by masking out seed entities from the predictions after the second hop (ReifKB + mask in the table).
Timing on MetaQA and other natural problems. The raw data for the bubble plot of Table 5 below.
Time (seconds)
Accuracy (hits@1)
Method Reif KB
72.6
79.7
189.8
10.1
KV-mem
28.9
77.2
GRAFT-Net
1131.0
91.4
PullNet
Discussion of the KB completion model. The KB completion model is
for i I,..., N and / /= 1,..... T: r f(()); x =xollow(x(-1, + +x
It may not be immediately obvious why we used
x (x),,) + x/-
instead of the simpler
x follow(x r!)
In the main text, we say that this "gives the model access to outputs of all chains of length less than f". This statement is probably easiest to understand by considering a concete example. Let simplify notation slightly by dropping the subscripts and writing follow(x rf) as f'(x"-1), Now expand the definition of x for few small values of i, using the linearity of the definition of relation-set
'If the relation weights do not vary from trial to trial, some versions of Tensorflow will optimize computation by precomputing and caching the matrix Mn from Fq. [ which speeds up the naive method considerably. Of course, this optimization is impossible when learning relation sets.
16

---

large extent be controlled by varying the norm of the relation vectors r','..,r', this "kernel- like trick" increases the expressive power of the model without introducing new parameters. Published as a conference paper at ICLR 2020
following where appropriate to simplify:
x
+x
x² = +(x))+xx
= +((()))))+++((())))))))))))))+))
x = -(2)+*2
= +11 (1
=
x2
A pattern is now clear: with this recursive definition x² expands to mixture of many paths, each of which applies a different subset of f'..... f to the initial input x. Since the weights of the mixture
The final mixture of the x seems to provide bias towards accepting the output of shorter paths, which appears to be useful in practice.
17


Reviews:
[{"review_id": "S1xi_7koYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a way to represent symbolic KBs called sparse matrix reified. Relations and entities' types are modelled using sparse matrices. This modelization allows distributing the computation on many GPUs. A neural model is used to manage these matrices. The trained model can be used to perform multi-hop queries. The proposed system has been compared with related systems. The results show that it achieves hits@1 that are comparable with the others.\n\nThe proposed approach seems promising, however, I feel that the paper is not ready for publication. The experiments lack a scalability test with related systems, the scalability test included in the paper only takes into account other definitions of the system. Also, comparison on the run time should be performed to see if the lower performance in terms of hits@1 (which are good anyway) is balanced by a better run time.\n\nTherefore, it is difficult to see whether the proposed system is good or not.\n\nAs for the description of the system, it seems to me to be quite foggy. In my opinion, the neural model should be better described to show how the sparse matrices are mapped into the model.\nAlso, how are the training and testing sentences created? How would the output of a query look?\n\nAfter reading the paper I have the feeling that it was written in a bit of a hurry, without working on the details. There are several typos, parentheses not correctly opened or closed, out of place commas that make some sentences seem unrelated to the rest of the paragraph. However, here last problems are easily fixable.\n\nTo sum up, I am conflicted about the choice of the final score. On the one hand, the approach is interesting, on the other hand the article seems to me not mature enough and strong enough from the point of view of organization, contents and experimental results shown.\n\nMinor problems\nOn page 4, the size of the matrices XM_k uses the factor b that is introduced later.\nIn the introduction, next to footnote 1, I suggest specifying that A is the first query, the one about Tarantino's movies.\nAlso, his surname is misspelt throughout the paper. The correct one is Tarantino.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "S1lWRZMTYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes an efficient sparse-matrix based representation for symbolic knowledge bases. This representation enables fully differentiable neural modules to model multi-hop inferences, which is designed to be scalable to handle realistically large knowledge bases. Experiments using the proposed method with end-to-end architectures on downstream KB tasks demonstrate its effectiveness and efficiency. Overall, this paper makes clear contributions and can inspire other researchers in the community to apply this KB representation for various learning / reasoning tasks on knowledge bases. However, considering the readability, I would like to recommend a weak accept for this paper.\n\nAdvantages of this paper: 1) The proposed method employs three sparse matrices to represent all KB relations, which is more efficient than existing work such as TensorLog and can support relation sets; 2) The reified KB representation is scalable, which can be distributed across multiple GPUs, making it much faster than the naive implementation; 3) The proposed method can be naturally used in end-to-end neural models and efficiently trained with gradient-based approaches.\n\nDisadvantages of this paper: 1) In the introduction part, the authors mention that existing neural KB reasoning methods generally require some non-differentiable mechanism to retrieve small question-dependent subset of the KB, but there exist some existing methods such as memory networks that are fully differentiable for the KBQA task. It would be better to cover and discuss more existing methods when summarizing their properties; 2) In the methodology part (Section 2), the description is clear but lacks some guidance for the readers to understand the motivation behind the scene. For example, it would be helpful to discuss why representing relations as sparse matrices is necessary, whether there is any other choices, and the benefit of making the current choice. This might seem obvious for the authors, but can help readers that are not familiar with the context access the methodology more easily and understand the motivation better.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BklxFnq2YS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes sparse-matrix KB representation for end-to-end KB reasoning tasks. They demonstrate that their algorithm is scalable to large knowledge graphs which is the central contribution of the paper.\nThey apply this to a bunch of tasks such as KB Completion and KBQA. This is done by mapping the query to a set (weights) of relations over which reasoning is performed. \n \nI would first like to comment that I found the paper very hard to read. Thus due to my difficulty in understanding the paper, it is possible that I might have misunderstood parts of the paper. \n \nThe notations are overly complex. In my opinion, the notations can be simplified to a considerable extent. I would suggest a Table of notations or a small figure explaining the model. The paper, in my view, requires  considerable rewriting.\n \nThe paper states that the proposed approach encodes three floating point values and 6 integers for each triple. Is this true for KBC task? Because I am quite surprised that ReifKB approaches SOTA which use hundreds of floats for representing each entity and relation (e.g. DistMult/ComplEx).  \n \nHere are somethings which are not very clear to me KBQA tasks: It is not fully clear how the query is mapped to r. In my understanding r is a set of relations. Is the output of linear function taken as weights? \nKBC Task: How do you ensure that the N chains are distinct? Do you have N different linear functions (f_i)? Also why is x_i^t added to follow in KBC task?\n \nThe paper needs considerable rewriting and therefore I cannot recommend this paper for acceptance at this stage.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an approach to representing a symbolic knowledge base as a sparse matrix, which enables the use of  differentiable neural modules for inference. This approach scales to large knowledge bases and is demonstrated on several tasks.   

Post-discussion and rebuttal, all three reviewers are in agreement that this is an interesting and useful paper. There was intiially some concern about clarity and polish, but these have been resolved upon rebuttal and discussion. Therefore I recommend acceptance. 
Decision: Accept (Poster)