SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
Authors: Mattia Atzeni
Jasmina Bogojeska
Andreas Loukas
Venue: NeurIPS 2021 Poster (2021)
Keywords: knowledge graphs
reasoning
question answering

Abstract: State-of-the-art approaches to reasoning and question answering over knowledge graphs (KGs) usually scale with the number of edges and can only be applied effectively on small instance-dependent subgraphs. In this paper, we address this issue by showing that multi-hop and more complex logical reasoning can be accomplished separately without losing expressive power. Motivated by this insight, we propose an approach to multi-hop reasoning that scales linearly with the number of relation types in the graph, which is usually significantly smaller than the number of edges or nodes. This produces a set of candidate solutions that can be provably refined to recover the solution to the original problem. Our experiments on knowledge-based question answering show that our approach solves the multi-hop MetaQA dataset, achieves a new state-of-the-art on the more challenging WebQuestionsSP, is orders of magnitude more scalable than competitive approaches, and can achieve compositional generalization out of the training distribution.

SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
Mattia Atzeni IBM Research, EPFL
Jasmina Bogojeska
Andreas Loukas EPFL Switzerland andreas. www.as@epklllc..mm
IBM Research Switzerland jbo@zurich. imm com
Switzerland
atz@zurich ibm. com
Abstract
State-of-the-art approaches to reasoning and question answering over knowledge graphs (KGs) usually scale with the number of edges and can only be applied effectively on small instance-dependent subgraphs. In this paper, we address this issue by showing that multi-hop and more complex logical reasoning can be accom- plished separately without losing expressive power. Motivated by this insight, we propose an approach to multi-hop reasoning that scales linearly with the number of relation types in the graph, which is usually significantly smaller than the number edges nodes. This produces set of candidate solutions that can be prov- ably refined to recover the solution to the original problem. Our experiments on knowledge-hasee question answering show that our approach solves the multi-hop MetaQA dataset, achieves new state-of-the-arr on the more challenging WebQues- tionsSP, orders of magnitude more scalable than competitive approaches, and can achieve compositional generalization out of the training distribution.
Introduction
Reasoning, namely the ability to infer conclusions and draw predictions based on existing knowledge, a hallmark of human intelligence. Infusing the same ability into machine learning models has been major challenge 34 29] and has historically required complex systems made of several hand-crafted or learned components [47 19 Recently, the paradigm has shifted to deep learning used to corpus. In this work, we assume that the source of knowledge is a structured knowledge graph (KG) and tackle the problem of knowledge-basee question answering (KBQA), namely finding answers to natural language queries involving multi-hop and logical reasoning over the KG.
approaches [33 42), where neural networks
structured knowledge a text
Answering queries over knowledge graph involves many challenges, among which scalability is a major issue. Real-world KGs often contain millions of nodes and even 2-hop neighborhood of the entities mentioned in the query may comprise tens of thousands of nodes. Many Mlate-of-the-an approaches [1 39] address the challenge scalability by building small query-dependent subgraphs. To this end, they usually use simple heuristics 41 or, in some cases, iterative procedures based on learned classifiers [42]. This preprocessing step usually needed because each forward pass in end-to-end neural networks for KBQA scales at least linearly with the number of edges in the subgraph. Training neural networks involves repeated evaluation, which renders even a linear complexity impractical for graphs of more than few tens thousands of nodes.
In order address this issue, we introduce a novel approach called SQALER (Scaling Question Answering by Leveraging Edge Relations). The method first Iearns model that generates set of candidate answers (entities in the KG) by multi-hop reasoning: the candidate solutions are obtained by starting from the set of entities mentioned in the question and seeking those that provide an answer by chained relational following operations. We refer to this module as the relation-leva model.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We show that this multi-hop reasoning step can be done efficiently and provably generates a set of candidates including all the actual answers to the original question. SQALER then uses second-stage edge-level model that recovers the real answers by performing logical reasoning on subgraph in the vicinity of the candidate solutions. A visual summary of our approach depicted in Figure
The main contributions and takeaway messages of this work are the following:
1. KBQA can be addressed by first performing multi-hop reasoning on the KG and then refining the result with more sophisticated logical reasoning without losing expressive power (we will elaborate this claim in more details in Section 2.3).
Multi-hop reasoning can be accomplished efficiently with a method that scales linearly with the number of relation types in the KG, which are usually significantly fewer than the number of facts or entities.
In the remainder of the paper, we first provide an extensive overview our approach and theoretical analysis of the expressive power and the computational complexity of SQALER. Our experimental results show that SQALER achieves better reasoning performance than statc-of-ther the-thhertt approaches, generalizes compositionally out of the training distribution, and scales to the size of real-world knowledge graphs with millions of entities.
2 Scaling KBQA with relation and edge-level reasoning
This section provides a detailed description of our approach. We start by defining the problem formally and giving an intuitive overview of SQALER. Then, we discuss the approach in more details and we analyze its computational complexity and expressive power
We denote a knowledge graph as g == (V, R) where u E V represents an entity or node in G. r E R is a relation type, and we write v - v to denote an edge in & labeled with relation type/ r R between two entities u, of E We extend the same notation to sets of nodes by writing V; 4 V V; = {u, E E v, 5 v, 02 Vi). Given a knowledge graph G = (V, R, E) and natural language question Q, expressed as sequence of tokens Q (41 92. 90)) ). in knowledge- based question answering the objective is to identify a set of nodes AQ C V representing the correct answers to Q. Following previous work [4]] 42 [3). we assume that the set of entities mentioned in the question Vo S V is given. These nodes are also called the anchor nodes of the question and in practice are commonly obtained using entity-
Problem statement.
module.
Overview. KBQA can be cast as an entity seeking problem on G by translating Q into a set of nodes Vo S V (the starting points of the search) and seeking for nodes that provide an answer [4] 42 43] Attempting to find Aq directly on G is prohibitive in practice, even the most efficient graph-base neural networks generally scale at least linearly with the number of edges. Our approach mitigates this issue by breaking the problem in two subproblems.
(a) We first utilize a relation-level model á to obtain set of candidate answers Āq such that AQ S Aq. We refer to é as "relation-level" because, as will it operates on the coalesced graph, a simplified representation of G, where edges of the same relation type are coalesced. The coalesced graph is constructed before training and incurs one-time linear cost. By exploiting it during training, the relation-level model scales with the number of (distinct) relation types in the KG, which are usually significantly fewer than the number of edges entities.
(b) The candidate answers are then refined using edge-level model t applied on subgraph 9 (AAq of the original knowledge graph in the vicinity of Ag- We should note that the refining step is not always necessary. Indeed, we found that a relation-level model is sufficient to perfectly solve tasks like multi-ho hop question answering [50]. Figure shows overview of our approach.
2.1 Relational coalescing for efficient knowledge seeking
Our approach relies on a relation-level model ø that operates as knowledge seeker in G. The model identifies node v as candidate v E Ag based on the sequence of relations that connect it with Vo-

---

Original KG g
Coalesced Representation 9
Subgraph ((Ao)
seic
The edge-level model to recovers Ag from Ag
B
B
G
G
T4
+I
C
Mention
Eniiyy
D
T4
eatr
F2
7
H
A
22
D
T4
Aq
1
R
Åo
R
T4
J
Answer
Relation sequence generaled by the reiation level model &
Figure I: Overview of our approach. A relation-level model operates on coalesced representation of the original KG to generate set of candidate answers Aq. This approximate solution is then refined by an edge-level model applied on a subgraph of the original KG.
This can be achieved by using a neural network ø to predict how likely it is that the correct answer is reached from Vo by following sequence of relations R.
Reachability. To define how method works, it will help to formalize the concept of reachability. Let Rt = (1))...,T( be sequence of relations. We say that "v is R-reachable from Vo" if there exists a path P
U R), v) in 9 such that:
U1 E Vo and U/ Ji 1s+1 for every
i= i [R).
That is, we can reach by starting from node V2 and following sequence edges with relation types R. We also denote by reachg (Vq, R)) the set of nodes that are R-reachable from Vo:
reachg(Vo. R) {v E V v is R-reachable from Vq).
Relational coalescing. Given a knowledge graph G. question Q, and a set of entity mentions Vo. we consider a representation of the graph Go = (Vo, R2, Eq). which allows us to efficiently compute sets of nodes that are reachable from VQ- We refer to this representation the question- dependent coalesced KG, because edges with the same relation type are coalesced, as shown in Figure
The nodes of Go are sets of nodes of & that are reachable from Vo by following any possible sequence of relations originating from Vo. The graph Go has an edge V; -. V, if V; is the set of nodes that are reachable from V; by following relation r. For convenience, we include a relation type self E Ro to denote self loops. We refer the reader to Appendix A for a formal definition of Sq- The coalesced graph can be precomputed once as a preprocessing step for each question Q and incurs a one-time linear cost. In practice, however, we do not need to compute and store all the nodes in Śo but only edge labels. This makes learning efficient because each forward/backwart pass scales with the number of relation types and does not depend on the number of nodes or edges in the KG.
Knowledge seeking in GΦ. The coalesced graph allows us to provide approximate answers to input questions in an efficient manner. Specifically, seek k > sequences of relations Rt, such that:
Ao C Ao = U reacha R2).
im1
We can achieve this by using a model á that only considers relation sequences originating from Vo- The model predicts the likelihood Φ &g - [0, 1] of following certain edge in relation sequence from VQ to Aq- Then, given R (f1...., )I and node in the coalesced graph Vo, we can compute the likelihood of R by multiplying the likelihood all edges traversed by in Go:
R
P(R| Q,90, Vo) x II
((eeachg(V)) Ri- r,, reache (Vo, R RI-.)) Q),
3

---

where Ri-1 = (ri....,,ra) is the subsequence of R up to the i-th relation. We generate Aq by selecting the top k relation sequences R with maximum likelihood P(R Q Go, VQ). This can be done by an efficient search algorithm, such as beam search starting from Vq- Then, we compute Aq as the union of all target nodes of the selected relation sequences. More details about the soowledge-seeking algorithm are provided in Appendix B
2.2 Refining the solution on the original KG
In certain cases, like multi-hop question answering [50]. the set of candidate answers Ag may already be a reasonable estimate of Aq- We will substantiate this claim experimentally in Section 4 In general, however, we recover Ag by using an edge-level model &b applied on subgraph ((Aq) of G. Specifically, we construct ((,Ao) as the subgraph induced by the set of nodes V(A)), which includes all nodes visited when following the top-k relation sequences along with their neighbors (see Figure I for an example). Any existing method for KBQA can be used to instantiate v by running it on ((A)) rather than g. We opted to use Graph Convolutional Network (GCN) conditioned on the input question with the same architecture as in [41]. The edge-level model is constrained to predict an answer among the candidates generated by the relation-level model.
2.3 Analysis of scalability and expressive power
This section provides a scalability analysis of our approach and shows that the relation-level model scales linearly with the number of relation types in the graph. Then, we analyse the expressive power of SQALER and we show the class of supported logical queries.
Computational complexity. As mentioned, we do not evaluate the likelihood e for all edges in Gq. but we generate the most likely relation sequences using showledge-seekinn procedure based on the beam search algorithm. At any given time step. only the 3 most likely relation sequences retained and further explored at the next iteration. Hence, the time complexity required by our algorithm is OTmax |3- dt (GQ)), where Tiax is the maximum allowed number of decoding time steps and d (9q) is the maximum outdegree of Gq. Note that dihtce ($q) bounded by the number of relations in the graph, whereas Tmax and /3 are constant parameters of the algorithm and are usually small. This gives a time complexity of: OT B RR)) = O(R))
Hence, the knowledge-seeking algorithm scales linearly with the number of relations in the KG. The space complexity is also O(Tmux B |R.). A more detailed analysis is provided in Appendix B
Expressive power. Given natural language question Q, we can represent the inferential chain needed to obtain Ao from Vo as a logical query Q on G. As an example, the question in Figure "Who starred in films directed by George Lucas?", can be represented by the logical query: V) A Starred (V, Vz). We denote with V? the target variable of the query and we say that E V satisfies Q if Q True. A query Q is existential positive first-order (EPFO) query if it involves the existential quantification (3), conjunction (A), and disjunction (V) 12 of literals corresponding
[ = V/.3V Directed @George_Lucat
relations in the KG. Each literal is of the form r(V, V"), where V is either a node in VQ or an existentially quantified bound variable, and V' is either an existentially quantified bound variable the target variable. A literal r r(V, V') is satisfied if و V", for r E R. Any EPFO query can represented disjunctive normal form (DNF) 15 namely as a disjunction of conjunctions. Note that, we do not consider queries with universal quantification (v), as we assume that in real-world KGs no entity connects to all the others. Then, the following proposition holds for any knowledge graph and EPFO query.
Proposition 1. Let G (V, R. E) be knowledge graph and VQ V denote a set of entities in G. Let be a valid existential positive first-order query on G and let ny be the number of disjunction operators in the disjunctive normal form of Q. Then, there exist k & by + sequences of relations R E R" such that:
k
Ao C
reache (Vo, RT),
4

---

11, ...,... T R sel
Softmax
X
++1
Transformer
Q
FFN
XfI
7; x
Encoder
Dec-Graph Attention
R₂
R
R
m
R
Relation
F
F3
R5
Encoder
Positional Enc.
Enc-Dec Altention
BERT
Self Attention
VQ
Aq
72
Q : 92, qQ
self, , r1, ....... MR
producsdd
Question Encoder
Decoder 1 self, directed, starred
wrote
directed
Blarred
Who starred movies directed by George Lucas?
(Goorge Lucas)
(Liam Neesom,
Natalie Portman,
Figure 2: Architecture of the SQALER relation-level model. A question encoder is used to obtain a representation tokens the input natural language question. Then a graph-guided decoder is applied to obtain the likelihood of output relation sequences. The decoder is constrained to only attend to valid relations according to the structure the coalesced KG.
where Ag - {u V Q [v] True} is the denotation set of Q, namely the entities satisfying Q.
This shows that sampling ny + 1 sequences of relations allows generating a set of candidate answers Aq that does not miss any of the real answers Aq. Then, assuming that the edge-level model eb can recover Aq from ÅQ. approach can be used answer any EPFO query G. More details about the expressive power SQALER and the proof Proposition are provided Appendix C
Architecture of the relation-level model
For the relation-level model o, propose auto-encoder, where the the decoder is constrained to follow sequences of relations in the coalesced representation GQ. We train the network with weak supervision, assuming that sequence of relations is correct if reaches a set of candidate answers Ao that is the smallest reachable superset of the Aq We found useful to pretrain the model in order infuse knowledge from the KG. In this case, train the model to predict path in the KG, given the representations of the source and target nodes. More details about training strategies are given in Appendix D
The architecture the model (see Figure 2 includes three main components: a question encoder, relation encoder and gruph-guided decoder. We explain each one below.
Question encoder. The encoder receives as input natural language question, which comprises sequence of tokens Q (gi, 42.... ... 4[q)). The question is encoded using pre-trained BERT [8] model and processed with same positional encoding technique used [44) The resulting embeddings then fed into n, 3 transformer encoder layers 44). This results in matrix
Q E IR +1+1xd where the first row vector is an overall representation of the whole query Q (derived from the embedding of the [CLS] token introduced by BERT) and each remaining row represents the final dimensional encoding of token in the input question.
Relation encoder. The relation encoder produces representation type R. We decided to encode relations based on their surface form, with the same pre-trained BERT model used the question encoder. In this case, only the embedding of the [CLS] token used in order to get the final representation of each relation type E R. At inference time, in
Rddosi each relation
5

---

case the BERT model is not fine-tuned, the embeddings of the relations can be precomputed as preprocessing step improve the efficiency of the approach.
Graph-guided decoder. The decoder's job is to predict a sequence of relations leading from Va to Aq in Sq. At any time step t, receives as input a sequence of relations RG = (self, "..... Tt-11) and predicts the next relation (self is used as special token to denote the start of decoding). Note that the input sequence uniquely determines a node V. in the graph Qq. namely the node reachable from Va by following Rg. The decoder thus selects ry by choosing amongst the outgoing edges E, of Vg. We use the same number of layers ny both for the question encoder and the decoder. Let X "xu....,>>... -xx,_..,xx(__
IR Rxxdww denote the hidden state of the I-th layer of the decoder preceding time step f. Note that X² is the representation of the sequence RG, obtained by using the relation encoder described above and the same positional encoding technique used in the question encoder. For each decoder layer, we perform self-attention over the target sequence X by computing:
Atlention| x
where Attention is a function that performs multi-head scaled dot-product attention 44 with skip connections and layer normalization [4]. The above step allows each relation in the decoded sequence to attend to all the others predicted up to time step L. We then let the result attend to the question as:
Attention x Q Q).
This is done in order to update the current state of the decoder based on the input question. Next, let R, E X denote the encoding of the relations labeling all edges in E, We constrain the decoded sequence follow the structure of the graph by attending only to valid relations follows:
Attention
Q. R₁, R.).
We get the hidden state of the next layer x by processing the result with a feed forward network. The model outputs categorical distribution de QQ E [0, 1] over the edges E &,, by applying a softmax function follows:
exp(r x;"
6(V. 4 V, (4)
Σ
Sxzee, exp(r' x(")"
where x is the output of the final layer of the decoder, whereas and r' denote the representations of relations and r' respectively.
Experiments
This section presents an evaluation our approach with respect to both reasoning performance and scalability. We first show that SQALER reaches state-of-the-art results on popular KBQA benchmarks and can generalize compositionally out of the training distribution. Then, we demonstrate the scalability of our approach on KGs with millions of nodes. We refer the reader to Appendix for more details about the experiments.
4.1 Experimental setup
Datasets. We evaluate the reasoning performance of our approach on MetaQA (50] and WebQues- tionsSP [49]. MetaQA includes multi-hop questions over the WikiMovies KB (35] and we consider both 2-hop (MetaQA 2) and 3-hop (MetaQA 3) queries. WebQuestionsSP (WebQSP) comprises more complex questions answerable over a subset of Freebase 7. large KG with millions of entities. We further assess the compositional generalization ability of SQALER on the Compositional Freebase Questions (CFQ) dataset [28). Each question in CFQ is obtained by composing primitive elements (aloms). Whereas the training and test distribution of atoms are similar, the test set contains different compounds, namely new ways of composing these atoms. CFQ comprises three dataset splits (MCD1, MCD2, and MCD3), with maximal compound divergence (MCD) between the training and test distributions, We refer the reader to Appendix E. for an extensive description of the datascts.

---

Evaluation protocol. In our experiments on MetaoA and WebQuestionsSP, we assess the per- formance of three variants of our approach: (a) a version that only makes use of the relation-level model without the refinement step (SQALER Unrefined), (b) a model that utilizes a key-value memory network to identify the correct answers from the candidates (SQALER- - KV-MemNN), and (c) model that uses GNN architecture for the refinement step (SQALER GNN), explained in Section 2.2] Following previous work [41 42 43 39), we evaluate the models based on the Hits I metric. On the CFQ dataset, we evaluate the accuracy of the refined model with the GNN based on whether predicts exactly the same answers given by the corresponding SPARQL query.
4.2 Main results
KBQA Performance. Table summarizes the results of our experiments on the two benchmark datasets. For the two multi-hop MetaQA datasets, we achieve state-of-the-ar performance by only using the relation-level model of SQALER. As shown in Table [ SQALER outperforms all the baselines on MetaQA 3, demonstrating the ability of our approach to perform multi-hop reasoning over a KG. For the more complex questions in the WebQuestionsSP dataset, the unrefined SQALER model achieves better performance than all but one (EmQL) of the baselines. To achieve such performance, however, EmQL creates custom set of logical operations tailored towards the specifics of the target KG and the kind of questions in the dataset, while our approach agnostic with respect to such details. Combining the relation and edge-level models improves the performance on WebQSP. In particular, SQALER GNN outperforms all considered baselines on the three datasets.
Table I: Hits on MetaQA and WebQuestionsSP
MetaQA
MetaQA 3
WebQSP
KV-MemNN 35
82.7
48.9
46.7
GRAFT-Net 41
94.8
77.7
70.3
ReifKB mask 110
95.4
79.7
52.7
PulINet 42
99.9
91.4
69.7
EmbedKGQA 39
98.8
94.8
66.6
EmQL 4
98.6
99.1
75.5
SQALER Unrefined
99.9
99.9
70.6
SQALER KV-MemNN
99.9
99.9
72.1
SQALER GNNN
99.9
99.9
76.1
Compositional generalization. In order to evaluate the compositional generalization ability of SQALER, we performed additional experiments on the CFQ dataset. Table shows the accuracy on the three MCD splits and the mean accuracy (MCD-mean) in comparison to the other methods in the leaderboard. Note that the other approaches address semantic parsing task and require additional supervision, as they are trained to predict the target query. On the other hand, we aim to predict directly the set of answers to the input question. The experiment shows that SQALER is able to achieve compositional generalization with accuracy comparable to the state-of-the-arr model on CFQ for semantic parsing.
Subgraph extraction. We analyzed the candidate solutions produced by the relation-level model in order to evaluate the suitability of our approach to building small question subgraphs that are likely contain the answers and recall of the set of candidate answers with varying number of relation sequences sampled by the relation-leve model. Figure shows shows the top relation sequences predicted by the relation-level model on two questions from the test set of WebQuestionsSP. The precision and recall curves are shown in Figure As expected, on MetaQA the recall is high for values of k; because selecting the most likely sequence of relations is sufficient to solve the multi-hop question answering task. On WebQuestionsSP. only sequences relations are sufficient to obtain recall of 0.91, and we can improve it to 0.95 by generating still small subgraphs consisting of only 10 sequences of relations.
natural language question. For this purpose, we computed the precision
7

---

Table 2: Accuracy and 95% confidence interval on the CFQ dataset
MCD1
MCD2
MCD3
MCD-mean
LSTM Attention
28
27
0.289 + 0.018
0,050 + 0.008
0.108 + 0.006
0.149 = 0.011
Transformer
0.349 + 0.011
0.082 = 0.003
0.106 0.011
0.179 = 0.009
Universal Transformer
28
17
0.374 + 0.022
0.081 = 0.016
0.113 0.003
0.189 = 0.014
Evolved Transformer
20
40
0.424 0.010
0.093 + 0.008
0.108 0.002
0.208 0.007
T5-11B B6 20
0.614 0.048
0.301 = 0.022
0.312 0.057
0.409 = 0.043
T5-11B-mod 220
0.616 + 0.124
0.313 = 0.128
0.333 + 0.023
0,421 - 0.091
HPD 23
0.720 + 0.075
0.661 + 0.064
0.639 + 0.057
0.673 - 0.041
SQALER GNN
0.734 0.039
0.653 + 0.040
0.627 0.045
0.671 + 0.041
What town was Martin Luther King assassinated in?
What high school did Harper Lee go to?
self
Aq
Institution
AQ
plase of deam
slate
educaaiin
type
stale
education
YQ
plcce
Va
Influeccdd by
apaiie
worke, writen
location of caremony
Solf
awards wan
Figure 3: Attention weights given by the relation-level model to the edges of the coalesced graph for two questions in WebQuestionsSP. Thicker and darker edges represent higher attention weights.
4.3 Efficiency and scalability
We analyze the efficiency of our approach on synthetic KBs (as in 9 10]) and then compare the scalability of different preprocessing methods the KGs of MetaQA and WebQuestionsSSP. First, we perform experiments on KBs where the relational coaleseing has no effect: the outdegree of each node is equal to the number of relation types and all edges originating from node have different relation labels. We perform two experiments on such KBs. In the first one (Figure 5a). the number of relation types is fixed to R 10 and the number of entities varies from |V] 10 to |V 10 In the second task (Figure 5b). the number of entities is fixed to |V| 5000 and the number of relations varies from [R] 1 [R] 10 The single answer node always two-hops away from the entities mentioned in the question. We compare SQALER (unrefined) against a GNN-based approach (GRAFT-Net (4I) and a key-value memory network (KV-MemNN (35). The approaches are evaluated based on the queries per second at inference time with a mini batch size of 1. The results show that increasing the number of entities has negligible impact on the performance of SQALERR. whereas GRAFT-Net and the key-value memory network are limited to graphs with less than 10k nodes. This shows that, large KGs like Freebase, the baselines would not be able to handle even a 2-hop neighborhood of the entities mentioned in the question (we refer the reader to Appendix E.5 for more details). Finally, from results Figure 5b) we see that the throughput of our approach decreases with the number of relation types. However, in practice, we can leverage the GPU to score the edges of the graph in parallel. This is why we observe only a minor drop in performance when the number of relation types grows from R = 1 to R 100.
In order assess the scalability of the proposed relational coalescing operation, we further compare commonly used preprocessing methods on the KG of WebQuestionsSP. We evaluate the time required to extract complete 2-hop neighborhoods of the entities mentioned in the question and the time to perform Personalized Page Rank (PPR) such graphs. The results are shown in Figure 5c Note that, inference time, we can perform the coalescing only on the portion of the graph explored by the model, which makes SQALER much more efficient. At training time, the preprocessing is comparable to the 2-hop neighborhood extraction. Finally, Figure 5d shows the performance of the models with the respective preprocessing step at inference time synthetic KBs with growing number of edges.
8

---

1.00 1 .00
1.00
1.00
1
1.001.00000
1.03
1.001.00
1.001
1.00
1.00 1.00
1,00
1.30 0.00
10.02.1.000
1.001.00000000
1.00
1.00
1.00
1.001.0011100000
1,0
0.89 0.95 9.94
2.63
71
0.8
79
..8
0.8
0.82
0.71
0.5
51
0.53
0.6
59
0.50
0.6
0.39
0.42
0.34
0.4
031
02
Precision
0.27
0.22
0.2
2.8
23
0.19
0
23
0.18
g.
10.1
10.00000
Racall
2
6
7
10
0.0
2
10
0.0
10
Figure 4: Precision and recall of the top l sequences of relations on MetaQA 2 (left), MetaQA (center) and WebQSP (right)
50
SQUALER GRAFT-NA
40
50
38
GRAFT-NN KHMMmAN
MeNNOA 3 WeoOSP
82
SQUALER
PPR
80
25,9
24-7
22.1
KV-M4mmNN
21,3
20.7
Querfertoe
18
Quariectee
-6
21.4
KX4MMmMM PPR
20
16.8
30
10
7.8
22
0.1
OOM
ODM
10
5.8
COM
OOM
16"
8.7
2
24
CQM
10a
10"
10
10
10
10F
10a
10
10
2hop Contoringg PPR (Pispisessee)
Cookecinn
10
10
10"
10*
Number entiies
Number of reatiions
Number of edges
(a)
(b)
(d)
Figure 5: Inference time in queries/sec on synthetic KBs with increasing number of entities (a) and relation types (b). Time required by different preprocessing steps the KG of WebQuestionsSP and
MetaQA (c). Complete inference and preprocessing time on synthetic KBs with increasing number of
edges (d). We set the queries/sec to O when the model runs out-of-memory (OOM).
4.4 Incomplete knowledge graphs
In order to evaluate the capability of our approach to cope with missing information in the knowledge graph, we performed two additional experiments. In the first experiment, we evaluated our approach (the SQALER GNN variant) on WebQuestionsSP using incomplete knowledge graphs with only 50% of the original edges (50 KG). Then, following previous work [2]42,, we tried to mitigate the missing information using additional sources of external knowledge. In particular, for each question, we used the same text documents extracted from Wikipedia as done by Sun et al. [41] (50% KG + Text). In this experiment, the relation-level model is unaware of the additional source of knowledge, but the information from the text documents is infused into the edge-level GNN with the same strategy used in GRAFT-Net [41] (note that this makes the edge-level GNN-based model essentially equivalent to the full version of GRAFT-Net, with both KG and text support). We compare our approach against GRAFT-Nee and PullNet, namely the baselines designed for open-domain question answering with incomplete KGs and text documents.
The results of the experiments reported in Table 3 We observe that, despite not being designed for incomplete KGs, SQALER outperforms the baselines on both experimental settings. This is not surprising, GRAFT-Net relies simple heuristic process construct question subgraphs and PullNet is constrained to follow the structure of the incomplete graph, because its iterative retrieval process can only expand nodes that reachable from the set of anchor entities. This means that, in principle, any node retrieved by PullNet's iterative process can also be reached by SQALER'S 's relation-level model. Similarly the baselines, note only minor gain in performance when using the text documents as an additional source of information.
Table 3: Hits on WebQuestionnSP with incomplete KGs (50% of the edges) and additional text
50% KG
50% KG
Text
GRAFT-Net 41
48.2
49.9
PullNet 42
50.3
51.9
SQALER GNN
53.5
55.2

---

5
Related work
Several lines of research in the past few years have focused on introducing deep learning approaches aimed at reasoning over structured knowledge. In particular, this paper is closely related to methods for learning to traverse KGs 14 13 24 and recent works on answering conjunctive queries using In this context, several KB and query embedding methods have been proposed [45]. Many KB embedding approaches support the same operation performed by our
deep learning approaches [25] 16.
relation- model, namely relation projection [00 43 25 38) Some KB embedding methods also
13. Notably, Query2Box [38] is query embedding method that represents sets using box embeddings and the more recent beta embeddings (37 extend the framework to support complete set of first-order logic operators. The main difference with our model is that these methods operate vector space, whereas our approach is constrained on the graph structure and learns to traverse the KG while keeping the ability to scale to large graphs. Also, our method answers questions in natural language, while the above methods are primarily designed for query answering. Recently, Sun et al. [33] introduced EmQL, a query embedding method which has also been integrated in question answering model.
explicitly learn to follow chains of relations and traverse KGs
30
Other lines of research on KBQA have focused on unsupervised semantic parsing B or on the introduction of supervised models, like graph neural networks (GNNs) designed for reasoning over These approaches pose the KBQA problem as a node classification task. For this reason, they have been applied succesfully only on small query-dependent graphs. Cohen et al. [10] addressed the problem of creating a representation of symbolic KB that enables building neural KB inference modules that are scalable enough to perform non-trivial inferences with large graphs. Another recent work (39] has explored using KG embeddings for question answering and handle incompleteness in the KG.
knowledge graphs 41 42 48
In our work, we combine relation projection with an edge-level GNN to address the KBQA problem. The same idea of combining GNNs with relational following was introduced in Gretel [II], which learns to complete natural paths in a graph given a path prefix. Also, our idea of accelerating GNNs by operating on reduced graph representation has strong connections with graph coarsening and sparsification [32 33
Methods based on reinforcement learning (RL) have also been proposed to perform multi-hop reasoning over knowledge graphs. Xiong et al. [46) proposed DeepPath, which relies on a policy- based agent that learns to reason over multi-hop paths by sampling relations at each step. Also, Das et al. [14 introduced MINERVA, a RL agent that learns how navigate the graph conditioned only on an input entity and on query. These approaches are designed for simple query answering and KB completion rather than KBQA. A main difference with our work is that SQALER samples multiple paths and employs an edge-level model to reach higher expressivity.
6 Conclusion
This paper introduced SQALER, a scalable approach to reasoning and question answering over KGs. Our method is expressive and can reach state-of-the-art performance on widely used and challenging datasets. Further, SQALER scales with the number of (distinct) relation types in the graph and can effectively handle large-scale knowledge graphs with millions of entities. Our empirical evaluation also showed that our approach can generalize compositionally and that it can be used to generate question-dependent subgraphs that strike good trade-off between precision and recall.
Overall, our work proposes an improvement to existing KBQA technology which carries impact to several practical applications. Nevertheless, we remind that the deployment of such models needs to be done cautiously. KBQA replaces a mature technology (traditional KBs and query languages) with less understood methods. The underlying KB may be incomplete, contain misinformation or biases that could negatively affect the decisions of the learned model. We hope that our work will spur further research in this area and contribute to the development of reliable KBQA systems.
Acknowledgments and Disclosure of Funding
Andreas Loukas would like to thank the Swiss National Science Foundation for supporting him in the context of the project "Deep Learning for Graph Structured Data", grant number PZ00P2 179981.
10

---

References
[1] Mattia Atzeni and Maurizio Atzori. Towards semantic approaches for gencral-purpose end-user development. In Second IEEE International Conference on Robotic Computing, IRC 2018, Laguna Hills, CA, USA, January 31 February 2, 2018, pages 369 --66.. IEEE Computer Society, 2018. doi
URL https: /ttps:///do..oo org/ 10. 1109/IRC 2018.00077
[2] Mattia Atzeni and Maurizio Atzori. Translating natural language to code: An unsupervised ontology-based approach. In First IEEE International Conference on Artificial Intelligence and Knowledge Engineering. AIKE 2018. Laguna Hills, CA, USA, September 26-28, 2018,
pages 1-8. IEEE Computer Society, 2018. doi 10.1109/A1KE.2018.00000
URL https
//doi.org//
1119//IKKE.0 2018. 00009
[3] Mattia Atzeni and Maurizio Atzori. What is the cube root of 27? Question answering over codeontology. In The Semantic ISWC 2018 17th International Semantic Web Conference, volume 11136 of Lecture Notes in Computer Science, pages 285-300. Springer, 2018.
[4] Lei Jimmy Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. CoRR, hass/6607.06455 2016. URL ntt:: http://arxii org/ abs 0tbss/107.0000 06450
[5] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR 2015, 2015.
[6] Joshua D. Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng. Spec- tral sparsification of graphs: theory and algorithms. Commun. ACM, 56(8):87-94, 2013. do: 24920299
httptttts///ot. orgg 1ee...11/229999 2492007 2492029
[7] Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor. Freebase: A collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, SIGMOD '08, page 1247-1250. Association for Computing Machinery, 2008
[8] Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013, pages 2787-2795 2013.
[9] William W. Cohen, Fan Yang, and Kathryn Mazaitis. Tensorl.og: Deep learning meets proba- bilistic dbs. CoRR, abs/1707.0539/ 2017.
http::////axxii.gaaa/a////ss/ 003900 [10] William W. Cohen, Haitian Sun, R. Alex Hofer, and Matthew Siegler. Scalable neural methods for reasoning with symbolic knowledge base. In ICLR 2020, 2020.
[11] -ean-Bap Cordonnier and Andreas Loukas. Extrapolating paths with graph neural networks. In Sarit Kraus, editor, Proceedings of the Twenty-Eighe International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, pages 2187-2194. ijcai.org. 2019. (oi.10024963/jcca.2211/// 2019/303
URL httpp:://dot org/ 24963 /ijai
[12] Nilesh N. Dalvi and Dan Suciu. The dichotomy of probabilistic inference for unions of conjumctive queries. ACM, 59(6):00 2012. doi [0..1145/23911162295111 URL //tp:::///o..../10... 1044 23955119
[13) Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2017, Volume 1: Long Papers, pages 132-141. Association for Computational Linguistics, 2017.
[14] Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR 2018, 2018.
[15] B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, edition, 2002.
[16] Daniel Daza and Michael Cochez. Message passing for query answering over knowledge graphs. CoRR, abs/2002.02406, 2020. URL https: pestps://arrivv wwtp wwwaaa//......... 02406
11

---

[17]
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Uni- versal transformers. In ICLR 2019, 2019.
[18] Jacob Devlin, Ming-Wei Meig-Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In NAACL 20/9, 2019.
[19]
David Ferrucci, Eric Brown, Jennifer Chu-Carroll, James Fan, David Gondek, Aditya Kalyanpur, Adam Lally, J William Murdock, Eric Nyberg. John Prager, Nico Schlaefer, and Christopher Welty. Building Watson: An Overview of the DeepQA Project. Al Magazine, 2010.
[20] Daniel Furrer, Mare van Zee, Nathan Scales, and Nathanael Schärli. Compositional general- ization in semantic parsing: Pre-training vs. specialized architectures. CoRR, abs/2007.088 700
2020. URL hattps://arxiv. www.:/ogg/bb///...oooo 08970
[21] Google. Freebase data dumps. https: httpp:://deeeloperssss google com/freebase//attee..
[22] Jiaqi Guo, Zecheng Zhan, Yan Gao, Yan Xiao, Jian-Guang Lou, Ting Liu, and Dongmei Zhang. Towards complex text-to-sql in cross-domain database with intermediate representation. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019. pages 4524 4535. Association for Computational Linguistics, 2019.
[23] Yinuo Guo, Zeqi Lin, Jian-Guang Lou, and Dongmei Zhang. Hierarchical poset decoding for compositional generalization in language. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[24] Kelvin Guu, John Miller, and Percy Liang. Traversing knowledge graphs in vector space. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, pages 318-327. The Association for Computational Linguistics, 2015.
[25] William L. Hamilton, Payal Bajaj, Marinka Zitnik, Dan Jurafsky, and Jure Leskovee. Embedding logical queries on knowledge graphs. In NeurlPS 2018, 2018.
[26] Xu Han, Shulin Cao, Lv Xin, Yankai Lin, Zhiyuan Liu, Maosong Sun, and Juanzi Li. Openke: An open toolkit for knowledge embedding. In Proceedings of EMNLP, 2018.
[27] Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 98):
1735-1780, 1997.
[28] Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashu- bin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. Measuring compositional generalization: A comprehensive method realistic data. In 8th International Conference Learning Representations, ICLR 2020. OpenReview.net, 2020.
[29] Brenden M. Lake and Marco Baroni. Generalization without systematicity: On the composi- tional skills of sequence-to-sequeene recurrent networks. In ICML, 2018.
[30] Yankai Lin, Zhiyuan Liu, Huan-Bo Luan, Maosong Sun, Siwei Rao, and Song Liu. Modeling relation paths for representation learning of knowledge bases. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, pages 705-714. The Association for Computational Linguistics, 2015.
[31] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR 2019. OpenReview.net, 2019.
[32] Andreas Loukas. Graph reduction with spectral and cut guarantees. J. Mach. Learn. Res., 20:
1 116:1-116:42, 2019. URL URL org/ http:///iiir..rrppppepe///////a/ hhtmm
[33] Andreas Loukas and Pierre Vandergheynst. Spectrally approximating large graphs with smaller graphs. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning. ICML 2018, Stockholmsmässson Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 3243-3252. PMLR, 2018. URL httphc:c/p/rrcceeinggg mlr. wateesssvv//oouaas11// htmml
[34] Gary Marcus. The next decade in ai: Four steps towards robust artificial intelligence, 2020.
[35] Alexander H. Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston. Key-value memory networks for directly reading documents. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, pages 1400-1409 The Association for Computational Linguistics, 2016.
12

---

[36] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. J. Mach. Learn. Res., 21:140:
2020.
[37] Hongyu Ren and Jure Leskovec. Beta embeddings for multi-hop logical reasoning in knowledge graphs. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, 2020.
[38] Hongyu Ren, Weihua Hu, and Jure Leskovec. Query2box: Reasoning over knowledge graphs in vector space using box embeddings. In ICLR, 2020.
[39] Apoorv Saxena, Aditay Tripathi, and Partha P. Talukdar. Improving multi-hop question an- swering over knowledge graphs using knowledge base embeddings. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACI. 2020, pages 4498 4507. Association for Computational Linguistics, 2020.
[40] David R. So, Quoc V. Le, and Chen Liang. The evolved transformer. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, volume 97 of Proceedings of Machine Learning Research, pages 5877-5886. PMLR, 2019.
[41] 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. In EMNLP, 2018.
[42]
Haitian Sun, Tania Bedrax-Weiss and William W. Cohen. Pullnet: Open domain question answering with iterative retrieval on knowledge bases and text. In EMNLP, 2019.
[43] Haitian Sun, Andrew Amold, Tania Bedrax- Weiss, Fernando Pereira, and William W. Cohen. Faithful Embeddings for Knowledge Base Queries. In NeurlPS 2020, 2020.
[44] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Informa- tion Processing Systems 30, NeurIPS 2017, pages 6000-6010, 2017.
[45] Quan Wang. Zhendong Mao, Bin Wang, and Li Guo. Knowledge graph embedding: A survey of approaches and applications. IEEE Trans. Knowl. Data Eng., 29(12):2724 2743, 2017.
[46] Wenhan Xiong, Thien Hoang, and William Yang Wang. DeepPath: A reinforcement learning
method for knowledge graph reasoning. In EMNLP. 2017.
[47] Xuchen Yao and Benjamin Van Durme. Information extraction over structured data: Question answering with freebase. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, Volume 1: Long Papers, pages 956-966. The Association for Computer Linguisties, 2014.
[48] Michihiro Yasunaga, Hongyu Ren, Antoine Bosselut, Percy Liang, and Jure Leskovec. QA- GNN: Reasoning with language models and knowledge graphs for question answering. In North American Chapter of the Association for Computational Linguistics (NAACL), 2021.
[49] Wen-tau Yih, Ming-Wor Chang, Xiaodong He, and Jianfeng Gao. Semantic parsing via staged query graph generation: Question answering with knowledge base. In Proceedings of the 53rd Annual Meeting of the ACL, 2015.
[50] Yuyu Zhang, Hanjun Dai. Zornitsa Kozareva, Alexander J. Smola, and Le Song. Variational reasoning for question answering with knowledge graph. In AAAI, 2018.
13


Reviews:
[{"review_id": "okkzdKnUYP", "reviewer": "Reviewer_Rcue", "summary": "This paper proposes an end-to-end KBQA system that can be directly used on the whole knowledge bases. This is in contrast to existing approaches that need a heuristic subgraph construction stage. More specifically, the proposed method trains a relation-following model to collect a candidate set of entities and the corresponding subgraph, which can then be processed by existing graph models. Empirically, the proposed method achieves state-of-the-art performance on MetaQA and WebQuestionsSP. Overall, this paper presents string empirical results over existing baselines on multi-hop KBQA, however, the main idea is hardly novel and has been applied to similar tasks. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "\n**Originality**: The core idea of the model is not new. The idea of sequentially selecting relation links to extend the reasoning chains has been extensively explored by KB reasoning work (DeepPath) and also semantic parsing methods on Freebase (such as stagg https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/ACL15-STAGG.pdf). The proposed method uses this process as an initial stage to replace pipelines like personalized page rank. \n\n**Quality**: The presentation is clear and the experiments are well designed. It not only shows state-of-the-art performance but also better compositional generalization. \n\n**Clarity**:  The writing is clear and easy to follow. \n\n**Significance**: While similar ideas have been applied to related tasks, this work shows benefits on multi-hop KBQA tasks.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any negative social impact of this work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "lCpq3Jl6x5_", "reviewer": "Reviewer_SVCA", "summary": "This paper proposed a KBQA framework that scales linearly with the number of relation types in a knowledge graph. The framework contains three main components in general. They first adopt relational coalescing to combine the nodes which share the same relation to reduce the number of edges in a graph. Then, they utilized a relation-level model to extract a subgraph that contains a set of answer candidates. Finally, the answer candidates are refined by an edge-level model. Their experiments on knowledge-based question answering show that the proposed framework achieves a new state-of-the-art on the challenging WebQuestionsSP, and is orders of magnitude more scalable than competitive approaches.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Personally, I liked the idea of doing KBQA in a coarse-to-fine way. The proposed relational coalescing is simple and intuitive, yet very effective. The experimental results on the common datasets are quite strong and also show that the proposed method generalizes compositionally. These are all good merits that could spur further researches of KBQA in this coarse-to-fine fashion. Also, the paper is well-presented and I enjoyed the reading. \n\nHere are several questions I have:\n1. What is the average length of the relational chains for WebQSP?\n2. Could the proposed framework generalize to the question that contains several entities?\n3. Are there some typical cases where the relational-level model fails to retrieve the correct chain?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors sufficiently addressed the limitations of their work and I don't think there are potential negative societal impacts.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5"}, "extra_text": {}}, {"review_id": "29fVRN4hzhv", "reviewer": "Reviewer_aN8i", "summary": "The paper focuses on the task of knowledge graph question answering. It specifically aims to address the challenge of scalability issue of the current KGQA methods. The overall idea is to first obtain a question-specific coalesced subgraph out of the knowledge graph, which “merges” entities of the same type (connected by the same relation types). Then the method locates a subset of answer candidates on the subgraph by traversing on this coalesced subgraph with some relation sequences derived from the mentioned entities in the question. Then they run a GNN model to select the final answer to the question from the answer candidates.\n\nGenerally I feel the paper writing can be refactored and improved. I suggest the authors list all the model components at the beginning of Section 2. Currently they only introduce a relation-level model and the edge-level model in Section 2, then out of nowhere, they mention they further propose an autoencoder in Section 3. They also say that “the architecture of the model includes three main components: a question encoder, a relation encoder, and a graph-guided decoder” in line 163. Where is relation-level model and edge-level model?\n\nOne key assumption (or limitation) in the paper is that the graph is complete, which renders the proposed method weaker than the baselines, e.g., all Pullnet, embedkgqa, EmQL can deal with missing edges. Although the authors mention in line 147-154 that “it may still be able to retrieve alternative sequences of relations, provided that the training data are representative enough”, can you run experiments on incomplete MovieGraph for MetaQA? I assume the training questions in MetaQA are much more than that in WebQSP and should also be very “representative” since the questions in the dataset are generated using some templates.\n\nAnother general comment is that since the paper focuses on QA in the complete graph setting and aims to obtain a relation sequence as the “parsed representation” of the question. Can you also compare your method with the series of (unsupervised) semantic parsing methods? These methods aim to parse the input questions to some logic form and then execute the logical queries on KG for answers.\n\n", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "1. I am confused by line 28-31, what exactly do you mean by “each forward pass scales at least linearly with the number of facts in the KG”? What is a forward pass? If you mean obtaining the subgraph for the question, I think in Pullnet obtaining the subgraph is not running a classifier on all the facts (edges) on the KG, but rather an iterative process, where at each step the classifier only needs to classify a small set of edges that are connected to the current retrieved subgraph. This is not linear to the number of facts on the KG and actually it is much less.\n2. It seems that the paper misses one important section, which is the detailed architecture of the edge-level model.\n3. Do you assume $\\mathcal{V}_Q$ are given? The authors should make it clear what is given and what is not.\n4. In line 83-93, the authors talk about how to obtain the coalesced graph. The term “Reachability” is conditioned on a sequence of relations as defined in the Reachability paragraph. However, in line 87, the authors only say “The nodes of $\\tilde{\\mathcal{G}_Q}$ are a set of nodes of $\\mathcal{G}$ that are reachable from $\\mathcal{V}_Q$” Then what is the relation sequence here? Do different questions have different relation sequences? How do you obtain the relation sequences? Significant amount of details are missing here and I could not find that in Appendix A. \n5. The notation is confusing for the equation after line 97. As in the definition, $\\phi: \\tilde{\\mathcal{E}_Q} \\to [0,1]$ really maps an edge in $\\tilde{\\mathcal{G}_Q}$ to a value between 0 and 1, but in the equation after line 97, for the argument of the function $\\phi$, I do not think $reach_\\mathcal{G}(\\mathcal{V}_Q,R_{1\\to i-1})$ represents a node on the KG but rather it represents **a set of nodes** on the KG as in the definition above line 83. Can you clarify the equation?\n6. Also, how long is the $R_i*$? Do you allow different lengths for $R_i*, i=1,\\dots,k$?\n7. I am also confused by the motivation of the knowledge seeking process. It seems that $\\tilde{\\mathcal{A}_Q}$ is obtained using $R_i*$, which is obtained by maximum likelihood $p(R_i*|\\tilde{\\mathcal{G}_Q},\\mathcal{V}_Q)$. This is saying that the answer candidates in the coalesced subgraph are only conditioned on the original KG and the question entities, but not conditioned on the original question. This is rather counterintuitive since there exist many questions with drastically different answers but with the same starting entities.\n8. Besides, how would you train the network $\\phi$?\n9. What is $\\mathcal{G}(\\tilde{\\mathcal{A}_Q})$ and $\\mathcal{V}(\\tilde{\\mathcal{A}_Q})$ in line 106-107? $\\mathcal{G}$ and $\\mathcal{V}$ are not functions.\n\nminor:\n1. I would suggest using different notations for natural language question and logical query. Currently both are denoted as Q in different fonts. \n2. line 159: “We found useful” -> “We found it useful”\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please check the section above, I do not think it has potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a substantially more scalable approach to KBQA that scales with the number of relation types (rather than the number of edges) in a KG, and operates in a coarse-to-fine manner.  The overall idea of working first at relation types, and later refining to individual edges, is interesting, and the results in the setting considered are strong.

The detailed discussion during the reviewing + author response period clarified some aspects (e.g., that the main contribution is not traversing a KG for multi-hop reasoning but identifying in a coarse-to-fine and scalable way to identify subgraphs that contain the answer), and also included additional positive results such as improved performance even on incomplete KGs, which is what the PullNet and GraftNet baselines were originally designed for.

The paper is close to the fence, with several strengths and some weaknesses:

**Strengths**: Strong empirical performance, intuitive overall idea, and authors' active effort in addressing (and, I assume, incorporating in the revised draft) detailed feedback from the reviewers.

**Weaknesses**: Limited novelty (as many pieces of the overall idea exist), room for clarity of presentation of both technical details (some of which are in the appendix) and broad statements like existing methods scaling linearly in the size of the entire KG (whereas they scale linearly in the size of the *retrieved* subgraph, which is often much smaller for 2-4 hop questions).
Decision: Accept (Poster)