{'fraction_non_alphanumeric': 0.03562790340538258, 'fraction_numerical': 0.012381464276116251, 'mean_word_length': 4.351859461680707, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning

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.


Introduction
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.
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.

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 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 V i Given a knowledge graph G = (V, R, E) and a natural language question Q, expressed as a sequence of tokens Q = (q 1 , q 2 , . . . , q |Q| ), in knowledge-based question answering the objective is to identify a set of nodes A Q ⊆ V representing the correct answers to Q. Following previous work [41,42,43], we assume that the set of entities mentioned in the question V Q ⊆ 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 translating Q into a set of nodes V Q ⊆ V (the starting points of the search) and seeking for nodes that provide an answer [41,42,43]. Attempting to find A Q 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Ã Q , such that A Q ⊆Ã 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(Ã Q ) of the original knowledge graph in the vicinity ofÃ 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.

Relational coalescing for efficient knowledge seeking
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 ∈Ã Q based on the sequence of relations that connect it with V Q . This can be achieved by using a neural network φ to predict how likely it is that the correct answer is reached from V Q 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 = (r 1 , . . . , r |R| ) be a sequence of relations. We say that That is, we can reach v by starting from a node in V Q and following a sequence of edges with relation types R. We also denote by reach G (V Q , R) the set of nodes that are R-reachable from V Q : Relational coalescing. Given a knowledge graph G, a question Q, and a set of entity mentions V Q , we consider a representation of the graphG Q = (Ṽ Q ,R Q ,Ẽ Q ), which allows us to efficiently compute sets of nodes that are reachable from V Q . 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 ofG Q are sets of nodes of G that are reachable from V Q by following any possible sequence of relations originating from V Q . The graphG Q has an edge V i r − → V j if V j is the set of nodes that are reachable from V i 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 ofG 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 inG 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 inG 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: We can achieve this by using a model φ that only considers relation sequences originating from V Q . The model predicts the likelihood φ :Ẽ Q → [0, 1] of following a certain edge in a relation sequence from V Q toÃ Q . Then, given R = (r 1 , . . . , r |R| ) and a node in the coalesced graph V Q , we can compute the likelihood of R by multiplying the likelihood of all edges traversed by R inG Q : where R 1→i = (r 1 , . . . , r i ) is the subsequence of R up to the i-th relation. We generateÃ Q by selecting the top k relation sequences R i with maximum likelihood P(R i | Q,G Q , V Q ). This can be done by an efficient search algorithm, such as beam search starting from V Q . Then, we computẽ 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.

Refining the solution on the original KG
In certain cases, like multi-hop question answering [50], the set of candidate answersÃ Q may already be a reasonable estimate of A Q . We will substantiate this claim experimentally in Section 4. In general, however, we recover A Q by using an edge-level model ψ applied on a subgraph G(Ã Q ) of G. Specifically, we construct G(Ã Q ) as the subgraph induced by the set of nodes V(Ã 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(Ã 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.

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 φ for all edges iñ 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 ofG 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: 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 A Q from V Q 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: 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 V Q or an existentially quantified bound variable, and V is either an existentially quantified bound variable or the target variable.
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 V Q ⊆ 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:  where

BERT
= 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 A Q . Then, assuming that the edge-level model ψ can recover A Q fromÃ 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.

Architecture of the relation-level model
For the relation-level model φ, we propose an auto-encoder, where the the decoder is constrained to follow sequences of relations in the coalesced representationG 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 A Q . 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 = (q 1 , q 2 , . . . , 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 n l = 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 d model -dimensional encoding of a token in the input question.
Relation encoder. The relation encoder produces a representation r ∈ R dmodel 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 V Q tõ A Q inG Q . At any time step t, it receives as input a sequence of relations R t = (self, r 1 , . . . , r t−1 ) and predicts the next relation r t (self is used as a special token to denote the start of decoding). Note that the input sequence uniquely determines a node V t in the graphG Q , namely the node reachable from V Q by following R t . The decoder thus selects r t by choosing amongst the outgoing edges E t of V t . We use the same number of layers n l both for the question encoder and the decoder. Let ∈ R t×dmodel denote the hidden state of the l-th layer of the decoder preceding time step t. Note that X 0 t is the representation of the sequence R t , 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 l t by computing: 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: . This is done in order to update the current state of the decoder based on the input question. Next, let R t ∈ R |Ẽt|×dmodel denote the encoding of the relations labeling all edges inẼ t . We constrain the decoded sequence to follow the structure of the graph by attending only to valid relations as follows: We get the hidden state of the next layer x l+1 t by processing the result with a feed forward network. The model outputs a categorical distribution φ(e | Q) ∈ [0, 1] over the edges e ∈Ẽ t , by applying a softmax function as follows: , where x n l t is the output of the final layer of the decoder, whereas r and r denote the representations of relations r and r respectively.

Experiments
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.

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 [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.

Main results
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.  [28,44] 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 [36,20] 0.614 ± 0.048 0.301 ± 0.022 0.312 ± 0.057 0.409 ± 0.043 T5-11B-mod [20,22] 0.616 ± 0.124 0.313 ± 0.128 0.333 ± 0.023 0.421 ± 0.091 HPD [23] 0

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 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| = 10 2 to |V| = 10 6 . 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| = 10 3 . 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.

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 [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.

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 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.

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 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.
Time complexity. At time step t, for each triple (V t , R t , w t ) ∈ B t , the algorithm computes φ for all edgesẼ t originating from V t . This means that the relation-level model described in Section 3 is queried |B t | · |Ẽ t | times at iteration t. Note that we do not need to compute the likelihood φ(V i be the maximum outdegree of nodes inG Q . At time step t, the size of the set B t+1 is restricted to β for the next iteration by the operation min(B t+1 , β). Since |B t | is bounded by β and |Ẽ t | is bounded by d + max (G Q ), at any iteration, the relation-level model is queried at most β · d + max (G Q ) times. Each of such queries takes constant time. The function min(B t+1 , β) selects the β tuples in B t+1 with the smallest negative log-likelihood. This can be done on average in O(|B t+1 |) time. At iteration t, the set B t+1 is initialized as the empty set and updated by adding at most β · d + max (G Q ) tuples (one element for each query to the relation-level model). Therefore, the expected time complexity of the function min(B t+1 , β) is O(β · d + max (G Q )). Now, note that by the definition ofG Q , we have d + max (G Q ) ≤ |R Q | = |R| + 1. Hence, the number of queries to the relation-level model is bounded by β · (|R| + 1) and the time complexity of min(B t+1 , β) is also O(β · |R|). The maximum depth reached by the knowledge seeking procedure starting from V Q is bounded by τ max , because Algorithm 1 performs at most τ max iterations of the main outer loop. The final step min(B t , k) selects the k most likely tuples and can be run on average in O(β) time. This yields a final computational complexity of Note that τ max and β are constant parameters of the algorithm and are usually small. In our experiments, we set τ max = 3 for MetaQA 3 and τ max = 2 for MetaQA 2 and WebQSP. We set the beam width β = 10, obtaining only minor improvements with respect to a greedy search with β = 1. Therefore, we obtain that that time complexity of the knowledge seeking procedure scales linearly with the number of relation types and does not depend on the number of nodes or edges in G.

Algorithm 1: Knowledge Seeking
Input :a coalesced knowledge graphG Q ; a set of starting entities V Q ; the beam width β; the maximum number of iterations τ max ; and the number of relation sequences to be returned k ≤ β Output :A set of k tuples of the form (Ã Q , R, w), representing the k most likely candidate answersÃ Q , the sequence of relations R to reachÃ Q , and the negative log-likelihood Space complexity. For each iteration t, Algorithm 1 constructs B t+1 by analyzing all edges originating from each node V t stored in the tuples (V t , R t , w t ) ∈ B t . From the considerations reported above, the size of B t+1 is O(β · |R|). Although for notational convenience we are representing B t as a set of triples, in practice we can avoid storing intermediate nodes V t and construct the set of candidate answers by following R t at the final iteration. Therefore, we only need to store relation sequences R t and their negative log-likelihood w t . Each tuple requires O(τ max ) space, as |R t | is bounded by τ max . The space complexity of the algorithm is thus O(τ max · β · |R|).

C Expressive Power
As mentioned in Section 2.3, the approach described in this paper can be used to answer any valid existential positive first order query on a knowledge graph G. In order to prove this, we first consider the simpler class of conjunctive queries. We will show a result similar to Proposition 1 for conjunctive queries, and then we will extend this result to the wider class of EPFO queries.

C.1 Conjunctive Queries
Given a knowledge graph G = (V, R, E) and a non-empty set of nodes V Q ⊆ V, a conjunctive query on G is a query involving only existential quantification and conjunction: such that each literal e i is an atomic formula of the form In general, for any query Q, we can define its dependency graph as the graph with nodes V Q ∪ {V ? , V 1 , . . . , V m }. The edges of the graph are the literals {e 1 , . . . , e |Q| }, as each literal is of the form r(V, V ) and defines an edge between V and V [25]. Figure 6 shows an example of the dependency graph of a conjunctive query.
We say that a query is valid if its dependency graph is a directed acyclic graph (DAG), with V Q as the source nodes and the target variable V ? as the unique sink node. In the following, we will always consider valid queries, as this ensures that the query has no redundancies or contradictions. Lemma 1. Let G = (V, R, E) be a knowledge graph and Q be a valid conjunctive query on G. Then, there exists a sequence of relations R ∈ R * such that: = True} is the denotation set of Q, namely the entities satisfying Q.
Proof. We proceed by induction on the number of literals |Q|.
Base case. Assume |Q| = 1. Then, since Q is valid, the query is of the form: with {v} = V Q . We have: Hence the sequence with only relation r is sufficient to generate the set of correct answers A Q .
Inductive step. Let Q be a conjunctive query of the form: Assume that there exists a sequence of relations R ∈ R * , such that: Consider a query Q constructed by adding a literal e |Q|+1 to Q, and let A Q be the denotation set of Q , namely the set of nodes satisfying Q . The conjunctive query Q may or may not have the same target variable of Q.
If Q shares the same target variable of Q, then Q is of the form: Note that: Hence, if Q and Q share the same target variable, the same sequence of relations that generates candidate answers for Q can be used to generate candidate answers for Q .
If Q and Q do not have the same target variable, then we can write Q as: Since Q is a valid conjunctive query on G, e |Q+1| is of the form r(V ? , V ? ). Then we have that: Therefore, the sequence (R , r) can be used to generate the answers to Q .

C.2 Existential Positive First-Order Queries
Any EPFO query can be expressed in disjunctive normal form (DNF), namely a disjunction of one or more conjunctions: such that: • each C i is a conjunction of literals of the form C i = e i1 ∧ e i2 ∧ · · · ∧ e i|Ci| • each literal e ij is an atomic formula of the form As above, we assume that the Q is a valid query on G, namely all C i are valid conjunctive queries. As shown in Figure 6, we can represent any EPFO query Q with a computation graph containing the operations that are required to answer Q. Specifically, each atomic formula can be represented as a relation projection, whereas conjunctions and disjunctions can be represented as intersection and union operations respectively.
Proof of Proposition 1. We assume that Q is expressed in disjuctive normal form and we denote with n ∨ the number of disjunction (∨) operators in Q. We proceed by induction on n ∨ .
Base case. Assume n ∨ = 0. Then, Q is a conjunctive query, and by Lemma 1, there exists R ∈ R * such that: Inductive step. Let Q be an EPFO query in DNF: . Note that, for completeness, we represent two paths in the coalesced representation, but only one is sufficient.
Consider the subquery Q consisting of the conjunction terms C 1 ∨ C 2 ∨ · · · ∨ C n∨ and assume that there exist k ≤ n ∨ sequences of relations R i such that: Note that C n∨+1 is a valid conjunctive query and by Lemma 1 there exists R k+1 ∈ R * such that: Then, it holds that:

D Training strategies
In this section we describe the training strategies that we used to optimize the parameters of our relation-level model and improve generalization performance.
Supervision. For the experiments on KBQA, we assume that we only have access to pairs of questions and answers, i.e. the actual inferential chain leading from the question to the answer is latent. Therefore, we resort to weak supervision to train the model. Since at training time the set A Q is known, we can compute all relation sequences R , such thatÃ Q = reach G (V Q , R ) is the smallest reachable superset of V Q . If the smallest reachable superset of A Q is not unique, all relation sequences leading to any superset of A Q of minimum cardinality are considered. Note that the set of all possible relation sequences of a given length originating from V Q inG Q is much smaller than the set of all possible paths starting from nodes in V Q in G, as shown in Appendix E.5. Since the CFQ dataset contains boolean questions (where the answer is not a set of entities), for the experiment on compositional generalization we use the logical parsing provided in the dataset to compute the correct sequences of relations. We assume these sequences of relations are stored in such a way that the set of relations exiting from the a node inG Q can be accessed efficiently in constant time. Then, at any decoding time step t, an edge is labeled as positive if and only if it belongs to a sequence of relations leading toÃ Q . The model is then trained using teacher forcing, namely we feed into the decoder relation sequences leading from V Q toÃ Q . We do not have multiple decoding time steps at training time, as the whole sequence is provided at once, and relation types are appropriately masked so that they cannot attend to items in future positions.
Path dropout. Previous work [41] has shown that randomly removing facts from the knowledge base at training time can be beneficial for generalization. Inspired by such insight, we employ a similar technique to enhance the performance of our model. Specifically, in the first epochs, we randomly remove paths that are not labeled as correct with probability p drop , in order to make the problem easier for the model. This probability is the linearly decreased to 0 during training. We set the initial p drop to 0.5 and we gradually lower it to 0 until half of the training epochs have been run.
Pretraining and fine tuning. For the experiments on WebQuestionsSP and CFQ, we found it beneficial to pretrain our model in order to incorporate knowledge from Freebase into the layers of the decoder. Specifically, we sampled a total of 500k 1-hop or 2-hop paths and we trained the model to predict the sequence of relations connecting two nodes, given the embeddings of the source node and the target node of the path. In order to do this, we replace the encoder with a simple 2-layer feedforward network, with a ReLU non-linearity. This network receives as input two 100-dimensional embeddings for the source and target nodes of the path, and maps them to a d model -dimensional representation. This representation is then fed into the decoder to predict the relations connecting the two nodes. We use a concatenation of 50-dimensional random and 50-dimensional pretrained TransE [8] embeddings [26] to represent the entities in the KG. Moreover, on WebQuestionsSP we observed that it was helpful to fine-tune BERT in order to produce better representations of the relations in the knowledge graph. The same BERT model is still used to encode both the questions and relation types.

E Experimental Details
E.1 Datasets KBQA datasets. We performed our experiments on KBQA on two widely adopted datasets, namely MetaQA [50] and WebQuestionsSP [49]. We provide below a detailed description of each one. • WebQuestionsSP [49] comprises 4737 questions over a subset of Freebase, which is provided under the CC BY 2.5 license 3 . The questions in this dataset are answerable by performing relational following for up to two hops and an optional relational filtering operation on the result. Table 4 shows the number of questions in the training, development and test splits of each dataset. We use the same splits as in [41]. Table 3 reports instead the number of triples (edges), entities (nodes) and relations in the KGs used in our experiments.
Compositional generalization. Our experiments on compositional generalization rely on the Compositional Freebase Questions (CFQ) dataset. It includes a total of 239 357 English question-answer pairs that are answerable using the public Freebase data [21]. CFQ is released under the CC-BY-4.0  The dataset provides three different splits (MCD1, MCD2, MCD3), with maximum compound divergence (MCD) and low atom divergence. For each question, both a logical parsing and the expected answers are included. Hence, CFQ can be used both for semantic parsing and end-to-end question answering.

E.2 Baselines
KBQA Baselines. On WebQuestionsSP and MetaQA, we compared our approach against the following baselines.
• KV-MemNN is a key-value memory network [35] that makes use of a memory of key-value pairs to store the triples from the KG. Keys are joint representation of the subject and relation of each triple, whereas the objects of the triples are used as the corresponding values. • ReifKB [10] uses a compact encoding for representing symbolic KGs, called a sparse-matrix reified KG, which can be distributed across multiple GPUs, allowing efficient symbolic reasoning. • GRAFT-Net [41] is a graph neural network designed to reason over question-specific subgraphs.
The message-passing scheme is conditioned on the input question and takes inspiration from personalized page rank to perform a directed propagation of the messages starting from the entities mentioned in the question. • PullNet [42] builds on top of GRAFT-Net and improves the quality of the question-specific subgraphs with an iterative process based on a learned classifier. This classifier selects which node should be expanded at each iteration and it is a further GNN with the same architecture as GRAFT-Net. • EmbedKGQA [39] uses KG embeddings for multi-hop question answering.
• EmQL [43] relies on a query embedding method that combines a count-min sketch representation for entity sets with logical operations implemented via neural retrieval over embedded KG triples.
CFQ Baselines. For the experiment on compositional generalization, we compare to the bestperforming baselines in CFQ's public leaderboard 5 . These baselines are all designed for semantic parsing and are encoder-decoder architectures trained to output a formal query given a natural language question. Keysers et al. [28] evaluated the compositional generalization capabilities of three sequence-to-sequence models, namely one based on LSTMs [27] equipped with an attention mechanism [5] (LSTM + Attention), a Transformer [44] and a Universal Transformer [17]. Furrer et al. [20] conducted a study that assessed the performance of three more models. The Evolved Transformer [40] is a variation of the Transformer discovered with an evolutionary neural architecture search seeded with the original model of Vaswani et al. [44]. The Text-to-Text Transfer Transformer (T5) [36] is a model pre-trained to treat every task as a text-to-text problem. Furrer et al. [20] fine-tuned all variants, including the largest one with 11 billion parameters (T5-11B). Following the technique introduced by Guo et al. [22], Furrer et al. [20] further implemented the variant T5-11B-mod, which learns to predict an intermediate representation of the SPARQL query which is closer to the formulation of the questions in natural language. Finally, Guo et al. [23] introduced the Hierarchical Poset Decoding (HPD), which enforces partial permutation invariance, thus taking into account semantics and capturing higher-level compositionality.

E.3 Hyperparameters and Reproducibility
We train the relation-level model for 300 epochs on both datasets. We use a mini-batch size of 128 for MetaQA and 32 for WebQuestionsSP. We set the dimension of the embeddings to d model = 768, as we use 12 attention heads applied to tensors of size 64. We optimize the model using the AdamW optimizer [31], with weight decay of 10 −3 . The initial learning rate is set to 10 −4 for MetaQA and 5 · 10 −6 for WebQuestionsSP. We apply dropout regularization, with probability 0.1 on both the encoder and the decoder layers. We use a beam width β = 10 for the knowledge seeking algorithm described in Appendix B.
BERT is fine-tuned for WebQuestionsSP, whereas the weights are kept fixed for MetaQA. For experiments on WebQuestionsSP, we found beneficial to pretrain our model in order to incorporate knowledge from Freebase into the layers of the decoder, as explained in Appendix D. Specifically, we sampled a total of 500k 1-hop or 2-hop paths and we trained the model to predict the sequence of relations connecting two nodes, given the embeddings of the source node and the target node of the path.
For the GCN-based edge-level model, we used the same implementation and hyperparameters of the version publicly available at: https://github.com/OceanskySun/GraftNet. All experiments are performed on a NVIDIA Tesla V100 GPU with 16 GB of memory.

E.4 Discussion and qualitative examples
In our experiments on KBQA, for each model, we selected the entity v ∈ V with the highest likelihood to be a correct answer. The answer to the question is considered correct if v ∈ A Q . For the unrefined SQALER model, we report the expected performance selecting v uniformly at random fromÃ Q .
The high performance of the unrefined model on MetaQA confirms our hypothesis that the relationlevel model applied on the coalesced representation is sufficient for tasks such as multi-hop question answering. On WebQuestionsSP, the edge-level model is needed because relation projection is not sufficient to answer some of the questions in the dataset. Figure 7 shows some examples of the relation sequences predicted by our model on the test set of WebQuestionsSP. For examples (a) and (b), the relation-level model is sufficient, as the set of candidatesÃ Q is the same as the set of the actual answers A Q . However, examples (c) and (d) demonstrate the need for an edge-level model, as following a sequence of relations is not always sufficient to obtain the correct answer. Note that the edge-level model is applied on a 1-hop neighborhood expansion of the graphs depicted in Figure 7 and constrained to select an answer among the candidatesÃ Q . Figure 7 also shows that the answer paths for 2-hop questions in WebQuestionsSP always contain compound value type (CVT) entities in the middle (depicted with cyan nodes in the image). These are special entity types that are used in Freebase to describe n-ary relationships between entities. EmQL uses different encodings for CVT nodes and the real entities, while SQALER does not depend on the KG specifics. In order to answer a question that requires multi-hop reasoning over a KG correctly, one should ideally either consider the full KG or a complete subgraph consisting of all possible multi-hop neighbors of the entities mentioned in the question. However, such subgraphs can be very large, as shown in Table 6. The subgraphs we analyzed include 3-hop neighbors for MetaQA 3 and both 1 and 2-hop neighbors of the entities mentioned in the question for WebQSP. The average number of nodes for MetaQA 3 exceeds 10k and for the larger Freebase KG there are question subgraphs with millions of nodes. This makes impractical to perform KBQA on complete subgraphs with models that scale with the number of edges or nodes in the graph. As a further analysis, we investigate the computational advantage of relational coalescing by computing the number of paths originating from the entities mentioned in the questions both in the original KG and in the coalesced representation. Figure 8 presents the results for both MetaQA and WebQuestionsSP. The experiment shows that relation coalescing allows reducing the number of paths by up to 2 orders of magnitude on both datasets. This directly impacts both the memory requirements and the efficiency of our approach. For MetaQA we analyzed paths of length up to 3, whereas for WebQuestionsSP we consider paths of length 1 or 2, as the dataset does not include 3-hop questions.