SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
Year: 2021

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.

heading: 1 Introduction
text: Reasoning, namely the ability to infer conclusions and draw predictions based on existing knowledge, is a hallmark of human intelligence. Infusing the same ability into machine learning models has been a 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 approaches [43, 42], where neural networks are used to reason over structured knowledge or a text corpus. In this work, we assume that the source of knowledge is a structured knowledge graph (KG) and we tackle the problem of knowledge-based question answering (KBQA), namely finding answers to natural language queries involving multi-hop and logical reasoning over the KG.
Answering queries over a knowledge graph involves many challenges, among which scalability is a major issue. Real-world KGs often contain millions of nodes and even a 2-hop neighborhood of the entities mentioned in the query may comprise tens of thousands of nodes. Many state-of-the-art approaches [41, 42, 39] address the challenge of 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 is 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 a few tens thousands of nodes.
In order to address this issue, we introduce a novel approach called SQALER (Scaling Question Answering by Leveraging Edge Relations). The method first learns a model that generates a 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-level model.
35th Conference on Neural Information Processing Systems (NeurIPS 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 a second-stage edge-level model that recovers the real answers by performing logical reasoning on a subgraph in the vicinity of the candidate solutions. A visual summary of our approach is depicted in Figure 1.
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).
2. 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 of our approach and a theoretical analysis of the expressive power and the computational complexity of SQALER. Our experimental results show that SQALER achieves better reasoning performance than state-of-the-art approaches, generalizes compositionally out of the training distribution, and scales to the size of real-world knowledge graphs with millions of entities.

heading: 2 Scaling KBQA with relation and edge-level reasoning
text: 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
Problem statement. We denote a knowledge graph as G = (V,R, E), where v ∈ V represents an entity or node in G, r ∈ R is a relation type, and we write v r−→ v′ to denote an edge in E labeled with relation type r ∈ R between two entities v, v′ ∈ V . We extend the same notation to sets of nodes by writing Vi r−→ Vj if Vj = {vj ∈ V | vi r−→ vj , vi ∈ Vi}. Given a knowledge graph G = (V,R, E) and a natural language question Q, expressed as a sequence of tokens Q = (q1, q2, . . . , q|Q|), in knowledge-based question answering the objective is to identify a set of nodes AQ ⊆ V representing the correct answers to Q. Following previous work [41, 42, 43], we assume that the set of entities mentioned in the question VQ ⊆ V is given. These nodes are also called the anchor nodes of the question and in practice are commonly obtained using an entity-linking module.
Overview. KBQA can be cast as an entity seeking problem on G by translatingQ into a set of nodes VQ ⊆ V (the starting points of the search) and seeking for nodes that provide an answer [41, 42, 43]. Attempting to find AQ directly on G is prohibitive in practice, as even the most efficient graph-based 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 a set of candidate answers ÃQ, such that AQ ⊆ ÃQ. We refer to ϕ as “relation-level” because, as we will see, 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 a 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 or entities.
(b) The candidate answers are then refined using an edge-level model ψ applied on a subgraph G(ÃQ) of the original knowledge graph in the vicinity of ÃQ. 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-hop question answering [50]. Figure 1 shows an overview of our approach.

heading: 2.1 Relational coalescing for efficient knowledge seeking
text: Our approach relies on a relation-level model ϕ that operates as a knowledge seeker in G. The model identifies a node v as a candidate v ∈ ÃQ based on the sequence of relations that connect it with VQ.
This can be achieved by using a neural network ϕ to predict how likely it is that the correct answer is reached from VQ by following a sequence of relations R.
Reachability. To define how our method works, it will help to formalize the concept of reachability. Let R = (r1, . . . , r|R|) be a sequence of relations. We say that “v is R-reachable from VQ” if there exists a path P = (v1, . . . , v|R|, v) in G such that:
v1 ∈ VQ and vi ri−→ vi+1 for every i = 1, . . . , |R|.
That is, we can reach v by starting from a node in VQ and following a sequence of edges with relation types R. We also denote by reachG(VQ, R) the set of nodes that are R-reachable from VQ:
reachG(VQ, R) = {v ∈ V | v is R-reachable from VQ}.
Relational coalescing. Given a knowledge graph G, a question Q, and a set of entity mentions VQ, we consider a representation of the graph G̃Q = (ṼQ, R̃Q, ẼQ), which allows us to efficiently compute sets of nodes that are reachable from VQ. We refer to this representation as the questiondependent coalesced KG, because edges with the same relation type are coalesced, as shown in Figure 1. The nodes of G̃Q are sets of nodes of G that are reachable from VQ by following any possible sequence of relations originating from VQ. The graph G̃Q has an edge Vi
r−→ Vj if Vj is the set of nodes that are reachable from Vi by following relation r. For convenience, we include a relation type self ∈ R̃Q to denote self loops. We refer the reader to Appendix A for a formal definition of G̃Q. 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 G̃Q but only edge labels. This makes learning efficient because each forward/backward 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̃Q. The coalesced graph allows us to provide approximate answers to input questions in an efficient manner. Specifically, we seek k ≥ 1 sequences of relations R⋆i , such that:
AQ ⊆ ÃQ = k⋃
i=1
reachG(VQ, R⋆i ).
We can achieve this by using a model ϕ that only considers relation sequences originating from VQ. The model predicts the likelihood ϕ : ẼQ → [0, 1] of following a certain edge in a relation sequence from VQ to ÃQ. Then, given R = (r1, . . . , r|R|) and a node in the coalesced graph VQ, we can compute the likelihood of R by multiplying the likelihood of all edges traversed by R in G̃Q:
P(R | Q, G̃Q,VQ) ∝ |R|∏ i=1 ϕ(reachG(VQ, R1→i−1), ri, reachG(VQ, R1→i) | Q),
where R1→i = (r1, . . . , ri) is the subsequence of R up to the i-th relation. We generate ÃQ by selecting the top k relation sequences R⋆i with maximum likelihood P(R ⋆ i | Q, G̃Q,VQ). This can be done by an efficient search algorithm, such as beam search starting from VQ. Then, we compute ÃQ as the union of all target nodes of the selected relation sequences. More details about the knowledge-seeking algorithm are provided in Appendix B.

heading: 2.2 Refining the solution on the original KG
text: In certain cases, like multi-hop question answering [50], the set of candidate answers ÃQ may already be a reasonable estimate of AQ. We will substantiate this claim experimentally in Section 4. In general, however, we recover AQ by using an edge-level model ψ applied on a subgraph G(ÃQ) of G. Specifically, we construct G(ÃQ) as the subgraph induced by the set of nodes V(ÃQ), which includes all nodes visited when following the top-k relation sequences along with their neighbors (see Figure 1 for an example). Any existing method for KBQA can be used to instantiate ψ by running it on G(ÃQ) rather than G. We opted to use a 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.

heading: 2.3 Analysis of scalability and expressive power
text: 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 ϕ for all edges in G̃Q, but we generate the most likely relation sequences using a knowledge-seeking procedure based on the beam search algorithm. At any given time step, only the β most likely relation sequences are retained and further explored at the next iteration. Hence, the time complexity required by our algorithm is O(τmax · β · d+max(G̃Q)), where τmax is the maximum allowed number of decoding time steps and d+max(G̃Q) is the maximum outdegree of G̃Q. Note that d+max(G̃Q) is bounded by the number of relations in the graph, whereas τmax and β are constant parameters of the algorithm and are usually small. This gives a time complexity of:
O(τmax · β · |R|) = O(|R|).
Hence, the knowledge-seeking algorithm scales linearly with the number of relations in the KG. The space complexity is also O(τmax · β · |R|). A more detailed analysis is provided in Appendix B.
Expressive power. Given a natural language question Q, we can represent the inferential chain needed to obtain AQ from VQ as a logical query Q on G. As an example, the question in Figure 2, “Who starred in films directed by George Lucas?”, can be represented by the logical query: Q[V?] = V?.∃V : Directed(George_Lucas,V) ∧ Starred(V,V?). We denote with V? the target variable of the query and we say that v ∈ V satisfies Q if Q[v] = True. A query Q is an existential positive first-order (EPFO) query if it involves the existential quantification (∃), conjunction (∧), and disjunction (∨) [12] of literals corresponding to 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 or the target variable. A literal r(V,V′) is satisfied if V r−→ V′, for r ∈ R. Any EPFO query can be represented in disjunctive normal form (DNF) [15], namely as a disjunction of conjunctions. Note that, we do not consider queries with universal quantification (∀), 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 a knowledge graph and VQ ⊆ V denote a set of entities in G. Let Q be a valid existential positive first-order query on G and let n∨ be the number of disjunction operators in the disjunctive normal form of Q. Then, there exist k ≤ n∨ + 1 sequences of relations R⋆i ∈ R∗ such that:
AQ ⊆ k⋃
i=1
reachG(VQ, R⋆i ),
where AQ = {v ∈ V | Q[v] = True} is the denotation set of Q, namely the entities satisfying Q.
This shows that sampling n∨ + 1 sequences of relations allows generating a set of candidate answers ÃQ that does not miss any of the real answers AQ. Then, assuming that the edge-level model ψ can recover AQ from ÃQ, our approach can be used to answer any EPFO query on G. More details about the expressive power of SQALER and the proof of Proposition 1 are provided in Appendix C.

heading: 3 Architecture of the relation-level model
text: For the relation-level model ϕ, we propose an auto-encoder, where the the decoder is constrained to follow sequences of relations in the coalesced representation G̃Q. We train the network with weak supervision, assuming that a sequence of relations is correct if it reaches a set of candidate answers ÃQ that is the smallest reachable superset of the AQ. We found it useful to pretrain the model in order to infuse knowledge from the KG. In this case, we train the model to predict a 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 of the model (see Figure 2) includes three main components: a question encoder, a relation encoder and a graph-guided decoder. We explain each one below.
Question encoder. The encoder receives as input a natural language question, which comprises a sequence of tokens Q = (q1, q2, . . . , q|Q|). The question is encoded using a pre-trained BERT [18] model and processed with the same positional encoding technique used in [44]. The resulting embeddings are then fed into nl = 3 transformer encoder layers [44]. This results in a matrix Q ∈ R|Q|+1×dmodel , 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 dmodel-dimensional encoding of a token in the input question.
Relation encoder. The relation encoder produces a representation r ∈ Rdmodel for each relation type r ∈ R. We decided to encode relations based on their surface form, with the same pre-trained BERT model used in the question encoder. In this case, only the embedding of the [CLS] token is used in order to get the final representation r of each relation type r ∈ R. At inference time, or in
case the BERT model is not fine-tuned, the embeddings of the relations can be precomputed as a preprocessing step to improve the efficiency of the approach.
Graph-guided decoder. The decoder’s job is to predict a sequence of relations leading from VQ to ÃQ in G̃Q. At any time step t, it receives as input a sequence of relations Rt = (self, r1, . . . , rt−1) and predicts the next relation rt (self is used as a special token to denote the start of decoding). Note that the input sequence uniquely determines a node Vt in the graph G̃Q, namely the node reachable from VQ by following Rt. The decoder thus selects rt by choosing amongst the outgoing edges Ẽt of Vt. We use the same number of layers nl both for the question encoder and the decoder. Let Xlt = [x l 0, . . . ,x l t−1]
⊤ ∈ Rt×dmodel denote the hidden state of the l-th layer of the decoder preceding time step t. Note that X0t is the representation of the sequence Rt, 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 Xlt by computing:
x̄lt = Attention(x l t,X l t,X l t),
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 t. We then let the result attend to the question as:
x̄Q,lt = Attention(x̄ l t,Q,Q).
This is done in order to update the current state of the decoder based on the input question. Next, let Rt ∈ R|Ẽt|×dmodel denote the encoding of the relations labeling all edges in Ẽt. We constrain the decoded sequence to follow the structure of the graph by attending only to valid relations as follows:
x̄R,lt = Attention(x̄ Q,l t ,Rt,Rt).
We get the hidden state of the next layer xl+1t by processing the result with a feed forward network. The model outputs a categorical distribution ϕ(e | Q) ∈ [0, 1] over the edges e ∈ Ẽt, by applying a softmax function as follows:
ϕ(Vi r−→ Vj | Q) = exp(r⊤xnlt )∑ V′i r′−→V′j∈Ẽt exp(r′⊤xnlt ) ,
where xnlt is the output of the final layer of the decoder, whereas r and r ′ denote the representations of relations r and r′ respectively.

heading: 4 Experiments
text: This section presents an evaluation of 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 E for more details about the experiments.

heading: 4.1 Experimental setup
text: Datasets. We evaluate the reasoning performance of our approach on MetaQA [50] and WebQuestionsSP [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 [21, 7], a 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 (atoms). 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.1 for an extensive description of the datasets.
Evaluation protocol. In our experiments on MetaQA and WebQuestionsSP, we assess the performance 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) a model that uses a GNN architecture for the refinement step (SQALER – GNN), as explained in Section 2.2. Following previous work [41, 42, 43, 39], we evaluate the models based on the Hits@1 metric. On the CFQ dataset, we evaluate the accuracy of the refined model with the GNN based on whether it predicts exactly the same answers given by the corresponding SPARQL query.

heading: 4.2 Main results
text: KBQA Performance. Table 1 summarizes the results of our experiments on the two benchmark datasets. For the two multi-hop MetaQA datasets, we achieve state-of-the-art performance by only using the relation-level model of SQALER. As shown in Table 1, 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 a custom set of logical operations tailored towards the specifics of the target KG and the kind of questions in the dataset, while our approach is 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.
Compositional generalization. In order to evaluate the compositional generalization ability of SQALER, we performed additional experiments on the CFQ dataset. Table 2 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 a 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 an accuracy comparable to the state-of-the-art 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 to contain the answers to a natural language question. For this purpose, we computed the precision and recall of the set of candidate answers with varying number of relation sequences sampled by the relation-level model. Figure 3 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 4. As expected, on MetaQA the recall is high for all values of k, because selecting the most likely sequence of relations is sufficient to solve the multi-hop question answering task. On WebQuestionsSP, only 3 sequences of relations are sufficient to obtain a recall of 0.91, and we can improve it to 0.95 by generating still small subgraphs consisting of only 10 sequences of relations.

heading: 4.3 Efficiency and scalability
text: We analyze the efficiency of our approach on synthetic KBs (as in [9, 10]) and then compare the scalability of different preprocessing methods on the KGs of MetaQA and WebQuestiontsSP. First, we perform experiments on KBs where the relational coalescing has no effect: the outdegree of each node is equal to the number of relation types and all edges originating from a 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| = 102 to |V| = 106. In the second task (Figure 5b), the number of entities is fixed to |V| = 5000 and the number of relations varies from |R| = 1 to |R| = 103. The single answer node is always two-hops away from the entities mentioned in the question. We compare SQALER (unrefined) against a GNN-based approach (GRAFT-Net [41]) 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 SQALER, whereas GRAFT-Net and the key-value memory network are limited to graphs with less than 10k nodes. This shows that, in 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 the results in 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 to 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) on such graphs. The results are shown in Figure 5c. Note that, at 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 on synthetic KBs with growing number of edges.

heading: 4.4 Incomplete knowledge graphs
text: 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 [41, 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-Net and PullNet, namely the two baselines designed for open-domain question answering with incomplete KGs and text documents.
The results of the experiments are 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, as GRAFT-Net relies on a simple heuristic process to 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 are 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 relation-level model. Similarly to the baselines, we note only a minor gain in performance when using the text documents as an additional source of information.

heading: 5 Related work
text: 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 deep learning approaches [25, 16]. In this context, several KB and query embedding methods have been proposed [45]. Many KB embedding approaches support the same operation performed by our relation-level model, namely relation projection [10, 43, 25, 38]. Some KB embedding methods also explicitly learn to follow chains of relations and traverse KGs [24, 30, 13]. Notably, Query2Box [38] is a query embedding method that represents sets using box embeddings and the more recent beta embeddings [37] extend the framework to support a complete set of first-order logic operators. The main difference with our model is that these methods operate on 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. [43] introduced EmQL, a query embedding method which has also been integrated in a question answering model.
Other lines of research on KBQA have focused on unsupervised semantic parsing [3, 2, 1] or on the introduction of supervised models, like graph neural networks (GNNs) designed for reasoning over knowledge graphs [41, 42, 48]. 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 a 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.
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 [11], which learns to complete natural paths in a graph given a path prefix. Also, our idea of accelerating GNNs by operating on a reduced graph representation has strong connections with graph coarsening and sparsification [32, 33, 6].
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 policybased 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 to navigate the graph conditioned only on an input entity and on a 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.

heading: 6 Conclusion
text: 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 a 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.

Review summaries:
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.  Generally 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?  One 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.  Another 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.  

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.

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.