Recently Graph Neural Network (GNN) has been used as a promising tool in multi-hop question answering task. However, the unnecessary updations and simple edge constructions prevent an accurate answer span extraction in a more direct and interpretable way. In this paper, we propose a novel model of Breadth First Reasoning Graph (BFR-Graph), which presents a new message passing way that better conforms to the reasoning process. In BFR-Graph, the reasoning message is required to start from the question node and pass to the next sentences node hop by hop until all the edges have been passed, which can effectively prevent each node from over-smoothing or being updated multiple times unnecessarily. To introduce more semantics, we also define the reasoning graph as a weighted graph with considering the number of co-occurrence entities and the distance between sentences. Then we present a more direct and interpretable way to aggregate scores from different levels of granularity based on the GNN. On HotpotQA leaderboard, the proposed BFR-Graph achieves state-of-the-art on answer span prediction. Typical Question Answering (QA) or Reading Comprehension (RC) task aims at exploring a desired answer through a single evidence document or paragraph. Recently, a more challenging multi-hop QA task, where we need to reason over multiple paragraphs to find the answer, is gradually catching attention. One example from HotpotQA dataset (Yang et al., 2018) is shown in Fig. 1. One method for achieving multi-hop QA is to concatenate all the paragraphs together and treat it as a typical single-hop QA task (Yang et al., 2018), then existing QA techniques can be applied. Although multi-hop QA can be solved to some extent, * Corresponding author. Graph Neural Networks (GNN) is a natural way to represent the solving procedure of multi-hop QA. For instance, nodes in GNN represent sen-tences/entities in the paragraphs, and from the up-dation through edges we can get interactive message between them, which is similar to the process of reasoning. Thus, a more reasonable method is to construct GNN to simulate the reasoning process among multiple paragraphs (Ding et al., 2019; Qiu et al., 2019; Tu et al., 2020). Promising performance has been reported in methods that designed different type of nodes or edges for GNN(De Cao et al., 2019; Tu et al., 2019, 2020; Fang et al., 2020) and the features generated from GNN has also been combined with those from the context encoder in a latent way (Qiu et al., 2019; Fang et al., 2020). Despite of the success that GNN achieves in multi-hop QA, new problems associated to GNN arise. Firstly, current approaches update all the nodes, including some unnecessary ones, together within each layer, which may lead the nodes to converge to similar values and lose the discriminating ability for GNN with more layers (Kipf and Welling, 2017). Secondly, although different types of edges have been designed for GNN, there is no more fine-grained distinction between edges of the same type, without considering the other relational information between sentences. Thirdly, existing methods only latently fuse the hidden representations of GNN and context encoder, without contributing to the answer span extraction in a direct and interpretable way. To solve the aforementioned issues, we proposed a novel model of Breadth First Reasoning Graph (BFR-Graph) to effectively adapt GNN to multihop QA. The proposed BFR-Graph is a weighted graph in which the weight of an edge is computed based on other relational information (e.g., co-occurrence entities and distance) of the connected sentences. Inspired by the Human reasoning mechanism and the Breadth First Search algorithm, in BFR-Graph the reasoning message starts from the question and passes to the next sentence nodes hop by hop until all the edges have been passed, effectively preventing each node from updating multiple times or being updated unnecessarily. Then the reasoning result from BFR-Graph is converted to the sentence scores and paragraph scores, contributing to the answer span extraction. Specifically, the final answer span probability is the sum of the score of answer span, the sentence and the paragraph, in both of which the answer is located. Experiment results shows that our methods make GNN more powerful in multi-hop QA and achieves state-of-the-art on answer span prediction of HotpotQA. The contributions of this paper are summarized as follows:  We propose BFR-Graph for multi-hop QA, which is more in line with reasoning process than existing GNNs. The reasoning message starts at the question and then reasons to the next sentences hop by hop. Our BFR-Graph is a weighted graph, considering the number of co-occurrence entities and the distance between sentences. BFR-Graph, multi-score mechanism is used for answer span extraction in a more direct and interpretable way. Serval multi-hop QA datasets have been proposed such as WikiHop (Welbl et al., 2018) and HotpotQA (Yang et al., 2018). WikiHop provides candidate answers for selection while HotpotQA needs to find an answer span over all paragraphs. Based on these datasets, several categories of multi-hop QA approaches were proposed. Yang et al. (2018) proposed a baseline method based on RNNs and Min et al. (2019) decomposed the multi-hop question into simpler single-hop subquestion that can be answered by existing single-hop RC models. To better utilize multiple paragraphs, Nishida et al. (2019) proposed Query Focused Extractor to sequentially summarize the context and Asai et al. (2020) used a recurrent retrieval approach that learns to sequentially retrieve evidence paragraphs. Moreover, reasoning has also been conducted in multi-hop QA. Jiang and Bansal (2019) designed a neural modular network to perform unique types of reasoning; Chen et al. (2020) presented extra hop attention that can naturally hops across the connected text sequences. Qiu et al. (2019) regards the task as a two-stage task including paragraph selection and downstream model. and Tu et al. (2020) further proposed a pairwise learning-to-rank loss for better interaction between paragraphs. Although the aforementioned methods are specifically designed for multi-hop QA with different structures, they lack an explicit scheme to show the reasoning process. Recently GNNs such as Graph Convolution Networks (Kipf and Welling, 2017) and Graph Attention Networks (Velickovic et al., 2018) show enhancement in multi-hop QA because the GNN-based methods are more intuitive and explicit. Entity-GCN (De Cao et al., 2019) considered different type of edges and Tu et al. (2019) further built a heterogeneous graph with multiple types of nodes and edges for different granularity levels of information. Besides, Ding et al. (2019) coordinated implicit extraction and explicit reasoning through a GNN inspired by the dual process theory in cognitive science, and Tu et al. (2020) built a Figure 2: Diagram of our system. GNN model for reasoning over sentence, which is summarized over token representations based on a mixed attentive pooling mechanism. Furthermore, more complex graphs is also designed. Qiu et al. (2019) proposed a Dynamically Fused Graph Network to explore along the entity graph dynamically and finds supporting entities from the context. Fang et al. (2020) created a hierarchical graph for different levels of granularity to aggregate clues from scattered texts across multiple paragraphs. However, GNNs in these methods update all the nodes together, including some unnecessary ones. To solve the aforementioned issues, we propose a novel model of Breadth First Reasoning Graph (BFR-Graph) for multi-hop QA. Different from existing GNN-based methods, BFR-Graph introduces new restrictions on the message passing: the message only starts from the question and then passes to the latter sentence nodes hop by hop. Besides, our graph is constructed as a weighted graph considering the co-occurrence entities and distance between sentences. Moreover, multi-score answer prediction is designed to take advantage of the reasoning result from BFR-Graph. In short, we propose breadth first reasoning on the weighted graph and then combine multi-level scores for answer prediction in the framework of multi-task joint training. The diagram of our system is shown in Fig. 2. Given multiple paragraphs, we first filter out irrelevant paragraph with paragraph selection (Sec. 3.1) and then use a BERT for context encoding (Sec. 3.2). A weighted graph is constructed (Sec. 3.3) to reason over sentences (Sec. 3.4) and calculate the sentence score and paragraph score. Finally, we use multi-score mechanism to predict the answer span (Sec. 3.5). Although multiple candidate paragraphs are given for answering the question, not all of them are useful (i.e., relevant to the question). Following Qiu et al. (2019), we retrieve N useful paragraphs for each question through a straightforward way. Each candidate paragraph is concatenated with the question ([CLS] + question + [SEP] + paragraph + [SEP]) and fed into a BERT (Devlin et al., 2019) for binary classification. After training procedure, we select paragraphs with topN score as the useful paragraphs, which are then concatenated together as context C . Following Qiu et al. (2019), we concatenate each question Q and its corresponding context C , and feed them into a BERT followed by a bi-attention layer (Seo et al., 2017) to obtain the encoded representations of question and context. The output is denoted as: H = { h 0 ,    , h L  1 }  RL  d , (1) where L is the length of the input sequence (con-catenating question and context), and d is the output dimension of bi-attention layer (also the dimension of BERT). sen-Figure 3: Message passing procedure of BFR-Graph and typical GNN. Active node is the node that is reachable for its neighbors while the quiet one is on the contrary. Active edge is the passable edge while the quiet one is on the contrary. where s starti , s endi are the start and end position of the sentence i respectively, L s i is the length of sentence i . Note that the question is also a sentence. Then using the method in Rei and Sgaard (2019), we get sentence representation: s i = L s (cid:88) k =0  ik S seqi [ k, :]  R d , (3) where  ik is the weight on the k -th token of sentence i , obtained from a two-layer MLP (Multi-Layer Perceptron) with output size = 1. 3.3 Weighted Graph Construction The nodes in our weighted graph represent question Q and sentences in context C . To better exploit complex relational information between sentences, two types of correlation are defined: positive correlation and negative correlation. Although they can be designed in many ways, now we illustrate our design: (1) Positive correlation: an edge is added if the nodes representing the sentences i and j have n ( n  1) of the same named entities, and the weight of the edge is: w ij = 1 1 + e  n + K 1 . (2) Negative correlation: otherwise, an edge is added if the two nodes are originally from the same paragraph, and the weight of the edge is: w ij = 1 1 + e d + K 2 , (5) where d is the distance of the two sentences (e.g., d = 1 if the sentence is immediately followed by the other sentence in a paragraph, d = 2 if there is a sentence between them, etc.). K 1 and K 2 are hyperparameters. To simplify our design, we treat our graph as a homogeneous graph, which contains single type of nodes and edges. When we reason over paragraphs to answer a question, we start from the question and find the next sentence hop by hop. For a GNN where nodes represent sentences, the following message passing is unnecessary and may suppress the disturbance from useless nodes: (1) from the latter node to the former node, (2) a node haven't received the message from question but it updates other nodes. To prevent each node from being updated multiple times unnecessarily, the reasoning message in our BFR-Graph starts from the question node and passes to the next nodes hop by hop until all the edges have been passed. Note that a node is allowed to update multiple times, depending on whether the connected edges have all been passed. Fig. 3 visually shows the difference between BFR-Graph and typical GNN. Specifically, a node i is updated by node j when the following conditions are met simultaneously: (1) node i and node j are neighbors, (2) node j is active, i.e., it is updated last layer, (3) the edge between node i and node j haven't been passed previously. The overall message passing procedure of BFR-Graph is illustrated in Algorithm 1. Inspired by Graph Attention Networks (Velickovic et al., 2018), the updating function (or message passing function) is defined as: s (cid:48) i = LeakyRelu( (cid:88) j N (cid:48) i  ij s j W ) , (6)  ij = exp( f ( s i , s j ))  w ij (cid:80) k N (cid:48) i exp( f ( s i , s k ))  w ik , (7) Figure 4: Multi-score answer prediction. where N (cid:48) i is the set of reachable neighbors for node i , calculated with Algorithm 1. f ( s i , s j ) = s i W 1 W 2 s j is for calculating the attention score between node i and j . W , W 1 and W 2 are learnable parametres. w ij is the weight of the edge ( i, j ) , described in the Sec. 3.3. For clarity, s (cid:48) is written as s in following contents. The answer in HotpotQA dataset is a span from the context. Existing works only calculate the span probability on the output of encoder (e.g., BERT) or additionally concatenate the GNN's hidden output. Differently, we use a more interpretable method by calculating the sentence score and paragraph score obtained from the GNN. An example is shown in Fig. 4. 1 to obtain the score value. Then, we calculate the sentence score corresponding to each node in GNN:  sent ( s i ) = MLP 3 ( s i ) . where s p j i is the representation of the i -th sentence in paragraph p j , L p j is the number of sentences in paragraph p j . Max(  ) is a max-pooling layer with pooling size = L p j  1 , which can also be done by taking the maximum hidden value on each dimension over all the sentence nodes. Finally, the probability of y -th word in context being the start of the answer span is determined by: p start ( y ) = softmax(  (cid:48) start ( y )) , (12)  (cid:48) start ( y ) =  start ( y ) +  sent ( s i ) +  para ( p j ) , (13) where the y -th word is located in sentence s i and paragraph p j . And the probability of y -th word in context being the end of the answer span can be calculated similarly. In addition to the answer span prediction, there are other two training tasks in HotpotQA. One is the answer type prediction task: some answers cannot be retrieved from the context, but are Yes or No, so finally there are three type of answers (e.g., span, Yes and No). We use a global-max-pooling similar with Eq.(11) to compress all the nodes in the GNN and predict the answer type through a two-layer MLP. The other task is to predict whether a sentence in the context is a support sentence (or called supporting fact in some papers) that is an evidence to the answer. Following previous works (Tu et al., 2020), we use the output of the GNN to predict the supporting sentences with a two-layer MLP. The tasks in HotpotQA are jointly performed through multi-task learning, and the loss function is: L = LCE ( y start , y start ) + LCE ( y end , y end )+  1  LCE ( y type , y type ) +  2  LBCE ( y sp , y sp ) , (14) where LCE and LBCE denote the cross entropy and binary cross entropy loss respectively. y start denotes the logits of start position from Eq.(12) and y start is the label. Similarly,  y type and  y sp are the logits of answer type prediction and supporting sentence prediction respectively. The HotpotQA dataset (Yang et al., 2018) is the first explainable multi-hop QA dataset with sentence-level evidence supervision. Each sample in the dataset contains 2 gold paragraphs and 8 distracting paragraphs. Three tasks are included for evaluation: (1) answer span prediction (denoted as Ans) that extracts a span in the paragraphs or generate Yes/No; (2) supporting sentences prediction (denoted as Sup) that determines which sentences are evidences to the answer; (3) joint prediction (denoted as Joint). We submit our model to HotpotQA official leaderboard 1 and carry out ablation studies on the dev-set. We also apply the main idea of BFR-Graph to the WikiHop dataset (Welbl et al., 2018), which provides candidate answers for selection while HotpotQA dataset needs to find an answer span over all paragraphs. Implementation details can be found in Appendix A. 4.2 Results The experimental result on HotpotQA dataset is shown in Table 1. As a reading comprehension task, the performance of answer prediction should be emphasized. Our model improves 0.84% Ans-EM (Exact Match) than HGN-large, becoming the first model to break through 70% and achieving state-of-the-art on answer span prediction. On supporting sentence prediction and joint prediction, our model shows a close performances to HGN-large, possibly because this paper is based on the standard GNN (homogeneous graph) for simple clarifica-tion, and we just plan to prove that our algorithm can improve the performance of GNN. Existing GNN methods mostly constructed elaborate graphs for more granular expression of nodes, while our BFR-Graph solve the problem from another novel perspective. Thus, BFR-Graph is universal and can be easily applied to existing promising models (e.g., HGN) to get better results, which provides a promising direction for future research. We also compare our model with two state-of-the-art GNN models (i.e., SAE and HGN), shown in Table 2. Both of them need to set the number of GNN layers manually while BFR-Graph can pass through all the connected nodes automatically with 1 https://hotpotqa.github.io/ Model Ans Sup Joint EM F1 EM F1 EM F1 Official baseline (Yang et al., 2018) 45.60 59.02 20.32 64.49 10.83 40.16 QFE (Nishida et al., 2019) 53.86 68.06 57.75 84.49 34.63 59.61 DFGN (Qiu et al., 2019) 56.31 69.69 51.50 81.62 33.62 59.82 LQR-Net (Grail et al., 2020) 60.20 73.78 56.21 84.09 36.56 63.68 SAE-large (Tu et al., 2020) 66.92 79.62 61.53 86.86 45.36 71.45 C2F-reader (Shao et al., 2020) 67.98 81.24 60.81 87.63 44.67 72.73 HGN-large (Fang et al., 2020) 69.22 82.19 62.76 88.47 47.11 74.21 BFR-Graph 70.06 82.20 61.33 88.41 45.92 74.13 Table 1: Results on HotpotQA leaderboard. an extremely low risk of over-smoothing (Kipf and Welling, 2017). SAE and HGN set a fixed types of edges, which is still not fine-grained enough, while BFR-Graph define different weights (can up to  different weights depends on the dataset) to distinguish nodes in a finer granularity. Furthermore, we can easily observe scores from GNN in an intuitive way in BFR-Graph. Besides, Table 3 shows the results on WikiHop dev-set. When we add the breadth first reasoning graph and weights to Longformer (Beltagy et al., 2020), the performance is slightly improved, showing that our method have the ability for better reasoning. In this section, we carry out ablation studies on HotpotQA dev-set. Table 4 shows the results of our full model and that without breadth first reasoning, weights, and multi-score. It indicates that our methods obviously improve the performance of GNN. Table 5 shows the result by gradually replace the BFR-Graph layers with standard GNN layers. In detail, r/p 1 layer denotes replacing the first layer with a standard GNN layer, r/p 2 layers denotes the same operation for the first and second layers, etc.. We observe that the more layers to be replaced, the more severely the result drops. And when we replace 4 layers, the joint F1 drops at about 6%, meaning that it causes over-smoothing. It also re-flects the severe problem of typical GNN: if it have more layers, over-smoothing is caused; if it have less layers, it cannot achieve long-path reasoning. To further analyze why this particular approach of message passing in a breadth first reasoning fashion should result in better reasoning, we propose to calculate how many useful messages the answer sentence node received from supporting senteences: precision = N sp & rcv N rcv , recall = N sp & rcv N sp , where N rcv denotes how many nodes' massages the answer sentence node received, N sp denotes the number of supporting sentence (containing the question sentence here), and N sp & rcv denotes how many supporting nodes' massages the answer sentence node received. The above-mentioned precision, recall and corresponding F1 on dev-set is shown in Table 6, where the typical GNN is a 2-layer GNN following previous works. With breadth first reasoning, the answer Ans F1 Sup F1 Joint F1 full model 81.82 88.80 73.98 bfr&ws&ms 80.72 87.77 72.20 Table 4: General ablation study for our full model. sentence could receive messages from supporting sentences with a higher precision, meaning that it can focus on useful sentences and eliminate invalid distractions. Since the restrictions on message passing in breadth first reasoning, it leads to a decrease in recall. However, it is hard to draw a PR curve or get different precision-recall results because this is not a binary classification task as we generally understand. But fortunately, BFR-Graph shows a higher F1 than the typical GNN. Table 7 (top) presents the results with and without the weights in the GNN. -ent denotes removing the weights (we set the weights = 0.5 rather than simply remove them) and dist denotes removing the distance weights. When we remove the weights, although the answer F1 rises slightly, the supporting F1 falls to a greater extent. This shows that the proposed weights is beneficial to the supporting sentences prediction, which is directly predicted from the GNN nodes. To our understanding, our model enhances the discrimination of edges by setting weights for them, and inevitably reduces the robustness of model. Fortunately, by designing Eqs.(4) and (5), the quantitative error will not cause the weight to increase or decrease sharply, and is still able to distinguish Precision Recall F1 typical GNN 37.62 95.61 52.89 BFR-Graph 59.44 83.49 63.08 Table 6: Message passing in different style. For multi-score, we evaluate how the result changes if this particular way of exploiting GNN's output is replaced by traditional way. In Table 7 (bottom), -sent and -para denote removing multi-score for sentence and paragraph respectively. It indicates that both the addition of sentence scores and paragraph scores are beneficial to the performance. We also analyze the complexities of BFR-Graph and typical GNN, which is simply shown in Table 8. Firstly, in each layer of our BFR-Graph, only several nodes are updated by active nodes, so the number of nodes to be updated in a BFR-Graph layer is less than or equal to that in a typical GNN ( N update  N ). Secondly, for a node in a layer of BFR-Graph, it is only updated by its reachable nodes (i.e., active neighbors), so the number of reachable nodes for a node in a BFR-Graph layer is also less than or equal to that in typical GNN ( M reach  M ). Therefore, breadth first reasoning leads to lower complexity. For GPU parallel training, we also show the actual cost of time per epoch. BFR-Graph cost 158.6 minutes per epoch, while a 2-layer and 3-layer typical GNN costs 157.5 and 165.6 minutes respectively. We find that BFR-Graph is always 4 layers in HotpotQA dataset, and it can even cost less time than a 3-layer typical GNN and is close to a 2-layer typical GNN. In this paper, we proposed a novel GNN model of BFR-Graph. Specifically, the reasoning message starts from the question node and passes to the next sentences node hop by hop until all the edges have been passed. We also construct the reasoning graph as a weighted graph and present a more interpretable way to aggregate scores of different levels from GNN. On HotpotQA leaderboard, BFR-Graph achieved state-of-the-art on answer span prediction. This work is partially supported by National Natural Science Foundation of China (Grants no. 61772568), Guangdong Basic and Applied Basic Research Foundation (Grant no. 2019A1515012029), and Youth science and technology innovation talent of Guangdong Special Support Program.
abstain abstain objective abstain method method abstain abstain result abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain method method abstain method abstain other other other other other other other other other other other other method other other other other other abstain abstain method abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method other abstain abstain abstain abstain method abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain method abstain abstain method other abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain result abstain abstain result other abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain method abstain other abstain abstain abstain abstain abstain abstain abstain method method abstain method abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain objective abstain method abstain other