Asynchronous Multi-grained Graph Network For Interpretable Multi-hop Reading Comprehension

1 Introduction

Compared with single-hop Machine Reading Comprehension (MRC), where the question can be answered by simply matching a span [Rajpurkar et al., 2016], multi-hop MRC requires models to answer compound questions based on bridging information. Recent datasets such as HotpotQA [ et al., 2018] and QAngaroo [Welbl et al., 2018] have been proposed for studying multi-hop MRC over multiple pieces of evidence. Particularly, HotpotQA also requires models to predict supporting sentences for explainable question answering (QA).

∗Corresponding author

Existing work has proved that Graph Neural Networks (GNN) is useful for multi-hop reasoning because of their natural relationship representation ability and inductive bias [Song et al., 2018; Cao et al., 2019; Ding et al., 2019]. Fine-grained nodes in the entity graph [Qiu et al., 2019] or heterogeneous graph [Tu et al., 2019] pass messages with each other based on defined relationships. Fang et al. [2020] combine the question and different levels of granularity representations (entity, sentence, paragraph) in the document to construct a hierarchical graph for multi-hop reasoning. However, there are still several limitations of the current GNNbased approaches. First, the above methods performmessage passing synchronously at each step of the graph update, ignoring the fact that different-level relationships have different priorities and the reasoning needs to follow an ordered logic. For example, as shown in Figure 1, the same entity-level mentions "Robert W. McElroy" and "McElroy" can locate the third sentence in Paragraph 1 as bridge information, which is further used to infer that "America" is the name of the magazine instead of the American magazine "Texas Monthly". This is sentence-level descriptive information and the model is easily misled by the distractor if the reasoning is not effectively performed in a certain fine-grained logical order, which is ignored by previous work.

Second, existing GNN-based methods either only use the updated entity nodes to reformulate the question embeddings or take the question as a node to update synchronously, which is insufficient since the supporting facts may not be evident in the question. Additionally, the guiding effect of a compound question on the reasoning chain should be reflected in the granularity and sequentiality of supporting fact prediction.

To this end, we propose an Asynchronous Multi-grained Graph Network (AMGN) for multi-hop MRC, which asynchronously updates multi-grained nodes based on different levels of relationships to mimic the logical order of multi-hop reasoning. Specifically, we first use a large-scale pre-trained language model such as Roberta [Liu et al., 2019] to encode the context and the question and then construct a graph with entity and sentence nodes. Particularly, we define relationship groups according to different granularity levels, and each relationship group is represented using independent parameters. We propose an algorithm for asynchronous message propagation according to the relationship levels (e.g., entity-entity

Question: Where is the magazine headquartered that Robert W.

McElroy writes for?

Answer: Manhattan

Figure 1: An illustration of multi-hop MRC with an example from the HotpotQA dataset. The initial entity is marked as red. Bridging information (supporting facts) are marked as blue. The final answer is marked in green. The solid line denotes the correct reasoning chain, and its color represents different granularity levels. Grey dotted lines indicate situations that may be misleading.

→ entity-sentence → sentence-sentence) to update the graph to mimic human multi-hop reading logic. Besides, for the second challenge, a RNN based reformulation mechanism is introduced to iteratively update the latent question representation with sentence nodes. These sentence nodes are directly used for supporting fact prediction. In this way, we have performed asynchronous updates between the question, entities, and sentences to represent the sequential process of multi-hop reasoning.

We evaluate the proposed model on the HotpotQA dataset and achieve top competitive performance in distractor setting compared to other published models. Extensive experiments show that the asynchronous update mechanism can effectively form interpretable reasoning chains at different granularity levels.

2 RelatedWork

Multi-hop MRC task aims to enable models to answer the compound question according to the bridge information scattered in multiple documents. Several multi-hop MRC datasets such as HotpotQA [Yang et al., 2018], QAngaroo [Welbl et al., 2018], and MultiRC [Khashabi et al., 2018] are recently released. In this work, we focus on extractive MRC and choose HotpotQA for experimental analysis. Existing work for multi-hop MRC can be mainly divided into two categories: recurrent reasoning based on memory retrieval and multi-step reasoning based on graph neural networks. The first group focuses on decomposing the question [Min et al., 2019] and updating the latent representations with the interaction of the question and the context in a recurrent network [Das et al., 2019; Jiang et al., 2019; Feldman and El-Yaniv, 2019]. GOLDEN Retriever [Qi et al., 2019] generates intermediate natural language search queries given the question and available context and leverages offthe-shelf information retrieval systems to query for missing entities, which is further enhanced by [Qi et al., 2020] using iterative reranking. Nie et al. [2019] propose a pipeline system specializing in hierarchical semantic retrieval at both paragraph and sentence levels. Jiang et al. [2019] leverage a dynamical RNN to construct a self-assembling neural modular network. Asai et al. [2020] construct an offline Wikipedia graph with hyperlinks and form the reasoning chain by using a beam search over the graph, where a RNN module is responsible for multi-hop retrieval reasoning. More recently, work by [Yadav et al., 2020; Perez et al., 2020] manages to decompose compound questions in an unsupervised fashion to to retrieve useful evidences effectively.

The second group manages to build a document graph for multi-hop MRC and reasoning over the constructed graph using graph neural networks. Considerable studies focus on a single level of granularity representation such as CorefGRN [Dhingra et al., 2018], Entity-GCN [Cao et al., 2019], DFGN [Qiu et al., 2019] and CogQA [Ding et al., 2019]. Tu et al. [2019] construct a heterogeneous graph to enrich the interaction among document nodes, entity nodes, and candidate nodes. SAE [Tu et al., 2020] builds a GNN model over sentence-level embeddings to explicitly facilitate multihop reasoning over all sentences from the predicted gold documents. C2F Reader [Shao et al., 2020] enhances DFGN and argues that graph-attention can be considered as a special case of self-attention, which may not be necessary for multi-hop MRC. HGN [Fang et al., 2020] combines the question and different levels of granularity representations (entity, sentence, paragraph) in the document to construct a hierarchical graph for multi-hop reasoning. DDR [Zhang et al., 2020] employs an entity-linked document graph for multi-document interaction and iteratively retrieves, reranks, and filters documents. Different from the above methods, our work focuses on the asynchronous message propagation and latent question update.

3 Methodology

3.1 Overview

An overview of our model is shown in Figure 2. The model consists of four main components: a paragraph selector for reducing search space, an encoder for encoding the selected context and the given question, a reasoning module for multigrained graph construction and multi-step asynchronous node update, and a multi-task prediction module. Our major contribution is the reasoning module AMGN, which constructs a graph containing multi-grained relationship groups and leverages an asynchronous update mechanism to explicitly consider the logic order at different granularity levels.

Paragraph selector. Similar to DFGN [Qiu et al., 2019], we first pre-train a BERT-based network to retrieve paragraphs relevant to the question. Instead of using a threshold to limit search space in DFGN, we take top-K paragraphs {P1, P2, ...PK} and concatenate them as context C based on the output score. Specifically, we independently encode each candidate paragraph along with the given question Q. The output [CLS] token representation is input to a binary classifier to predict whether the input paragraph contains the ground-truth supporting facts or not.

Context and question encoder. We concatenate the question Q with the context C and feed them to into a pre-trained BERT model to obtain representations Q = {q1, q2, ..., qm} ∈ Rm×d1 and C = {c1, c2, ..., cn} ∈ Rn×d1 , where d1 is the size of hidden states. Following the design of [Qiu et al., 2019], we further feed the representations into a bi-attention [Seo et al., 2017] layer to reduce the dimension of graph update and enhance the interactions of the question and the context, obtaining ˆQ ∈ Rm×d2 and ˆC ∈ Rn×d2 , where d2 < d1.

Multi-step asynchronous reasoning module. First we construct a multi-grained graph G = (V , R) where the node set V = E ∪ S. Entity node representations E ∈ Rne×d2 and sentence node representations S ∈ Rns×d2 are initialized with ˆC and connected by semantic relationships R (see Section 3.2). ne and ns denote the number of the entity and sentence nodes, respectively. Then we perform multi-step asynchronous reasoning on the graph based on AMGN, which can be formally described as:

where T is the number of iterations and q0 = MaxPooling( ˆQ). The details of AMGN will be explained in Section 3.3.

Multi-task prediction. For supporting facts prediction, the final sentence node representations ST after asynchronous propagation are exploited directly:

where Osent ∈ Rns . Following DFGN, we map the logits of the supporting facts Osent ∈ Rns to ˜C ∈ Rn . Then ˜C is concatenated with ˆC and fed into a cascade BiLSTM for answer and type prediction. We jointly train the model in a multi-task way. Please refer to [Qiu et al., 2019] for more details due to space limitation.

3.2 Multi-grained Graph Construction

Given the related paragraphs retrieved by the selector, we focus on entity-level and sentence-level information used to extract a span as the answer. Note that paragraph retrieval also needs multi-hop reasoning in open-domain QA, which beyond the scope of this work. We leave it as future work and provide a retrieval quality analysis in the appendix.

Node representation. We use token representations of the corresponding text spans in ˆC to initialize entity and sentence nodes. Specifically, these representations are fed into a selfattentive pooling layer to calculate the node representations. Given the start and end positions < pstart(vi), pend(vi) > in the text span corresponding to the i-th node vi, the initial node representation v0i is calculated as:

where v0i ∈ Rd2 and w ∈ Rd2 . In practice, we find using the self-attention pooling achieves better performance. We also experiment with other common pooling methods. Please refer to the supplementary materials for more details.

Group-based relationship definition. We define the following six types of edges in the graph to describe the semantic relationship between entities and sentences: (i) edges between entities that appear in the same sentence; (ii) edges between entities that have the same mentions text in C; (iii) edges between entity nodes and the sentence nodes to which they belong; (iv) edges between entity nodes and sentence nodes containing the same mentions; (v) edges between adjacent sentence nodes in the same paragraph; (vi) edges between sentence nodes that contain mentions of the same entity. Obviously, the graph depicts the three levels of relationships of entity-entity Ree (i, ii), entity-sentence Res (iii, iv), and sentence-sentence Rss (v, vi). Different from previous studies, we represent each level of relationships using independent parameters (see Eq. 7). We believe that this has the following advantages: 1) Representing relationship groups based on the granularity level is more scalable for new structured knowledge; 2) It is more interpretable to construct the reasoning chain based on different granularity levels.

3.3 Multi-step Asynchronous Graph Reasoning

AMGN is designed to perform multi-step asynchronous reasoning in a certain logical order and is a core module of our model. At each iteration t ∈ {1, ..., T}, after further interacting with the question, the nodes pass messages to each other asynchronously according to the relationship of different granularities. Then, the question will also be updated through sentence nodes in order to find the next-hop clue.

Question-aware graph. The multi-grained graph needs to highlight the entities and sentences relevant to the question. To this end, we adopt element-wise gate to perform filtering on entity and sentence nodes. Specifically:

where W t ∈ Rd2×2d2 , ⊙ means the element-wise multiplication, and [; ] denotes the concatenation operation. The question-aware nodes ˆ V t-1 will be used to pass message in the next layer.

Asynchronous information propagation. Intuitively, the reasoning chain is formed by the semantic relationship between different levels of granularity representations in a certain logical order. In this paper, we use Graph Attention Network (GAT) to update nodes asynchronously. Formally:

where N r i represents the neighbors of the i-th node through the relation r, W tRee ∈ Rd2 is a parameter representing the entity-entity level relationship group, W tr ∈ R2d2 is the weight vector corresponding to the relation r between i-th and j-th nodes, and f denotes the LeakyRelu activation function. In this way, we calculate the attention weight differentiating each relationship while conduct information propagation at the relationship group level. The uti is then added to ˆvti to update the nodes at the current relationship level:

We denote the above reasoning process (Eq. 7-9) as a single function:

For Res and Rss, we perform the update asynchronously in the same way:

In this way, the module mimics the heuristic of human multihop reasoning: finding the entity related to the question and other relevant entities through Ree → locating the sentence nodes to which these entities belong through Res → comparing the descriptive information in these sentences through Rss to determine the supporting facts. In practical, asynchronous reasoning is essentially regarded as a self-attention calculation across all nodes using different relation group masks, which improves computational efficiency.

Question reformulation. Questions requiring multi-hop reasoning are usually compound, that is, bridge information can answer part of the question. Hence, inspired by [Das et al., 2019], we propose a RNN-based question reformulation mechanism, where the latent representation qt-1 is reformulated with updated sentence nodes. The reformulation mechanism is implemented as follow:

The qt and V t serve as the input of the next-hop reasoning module. We perform T iterations of the reasoning step (Eq. 1) and the output of the last layer V T is obtained for answer and support sentences prediction.

4 Experiments and Analysis

4.1 Experimental Setup

Dataset. We evaluate our method on HotpotQA [Yang et al., 2018], which is a prevalent benchmark for multi-hop MRC. Specifically, HotpotQA has two settings Distractor and Fullwiki. For each question, the Distractor setting contains two gold paragraphs with ground-truth answers and supporting facts and eight negative paragraphs as distractors, while the Fullwiki setting requires to retrieve Wikipedia to obtain relevant paragraphs. We focus on the Distractor setting since retrieval quality is not the focus of this paper. In addition to evaluating answers and supporting facts separately, a joint EM and F1 score are used to measure the final performance, which encourages the model to take both tasks into consideration.

Implementation details. We implement our experiments based on Huggingface 1 and the official open-source implementation of DFGN 2 . We use Roberta-large for paragraph selection and set K = 3. For context encoding, we use another Roberta-large model as the encoder. For graph construction, we employ DFGN pre-trained BERT-based NER model to extract entities including Person, Number, Location and Organization, etc. The numbers of entities and sentences in one graph are limited to 80 and 30, respectively. Since HotpotQA only requires two-hop reasoning, a two-step graph update is conducted thus T is 2. We finetune on the training set for 8 epochs, with batch size as 32. For optimization, We use BERTAdam with an initial learning rate of 2e-5 . Since DFGN uses BERT in the feature-based setting, we leverage the Roberta-large retriever and encoder to re-implemente it in the fine-tuning setting for a fair comparison, which is similar to C2F Reader.

1 https://github.com/huggingface/transformers

2 https://github.com/woshiyyya/DFGN-pytorch

An enhanced variant. Since the definition of relationship group is more scalable for adding new edges, we investigate two new types of edges: 1) We add edges between entities in the question and other entities within the same paragraph to the relation group Ree; 2) We modify (v) to edges between sentence nodes within the same paragraph. This variant is called AMGN+, the same model described in Section 3 except for the above two relations.

4.2 Main Results

Table 1 shows published and unpublished models on both development and blind test set 3 of HotpotQA. Results on the dev set show that our AMGN variants outperform other Reborta-large based methods, indicating the performance gain comes from better relation and model design. Compared with HGN including paragraph nodes, the overall performance of AMGN is modest better. We believe that the asynchronous update sequence design involving more granularity can improve system performance. For AMGN+, we find that all metrics have been improve, which implies the scalability of group-based relationship definition. On the blind test set, our AMGN+ ranks No.1 at the time of submission (Jan 11, 2021).

3 https://hotpotqa.github.io/

4.3 Ablation Study

Table 2 summarizes the contributions of components of our model. We notice that removing the SS subgraph and removing the EE subgraph have a significant impact on supporting fact prediction and answer prediction, respectively. One possible reason is that most of the answers in HotpotQA are based on entities. Without the Rse, the joint F1 drops by 1.31 points, showing that the cross-granular relationship contributes to the model performance. Leveraging a multigrained graph improves the joint F1 score over the vanilla RoBERTa by 5.36%. Either using global parameters or without parameters results in performance degradation, showing the effectiveness of group-based relation definition. We further provide an analysis of group-based representation in the supplementary materials. Besides, our question reformulation mechanism also provides around 2% performance improvement and it mainly affects supporting factual predictions, which is reasonable because we use sentence representations to update the question.

4.4 Effectiveness of Asynchronous Update

To analyze the effectiveness of the asynchronous update, we experiment with different update orders. Table 3 indicates that the best results are obtained by updating the nodes with different granularities in the graph through the logical sequence closest to the human heuristic (finding related entities, reading the sentences where the entities are, judging which sentences are supporting facts, and obtaining the bridge information or final answer). We also find that not all asynchronous update variants perform better than the synchronous update (e.g., Simultaneous Update vs. Rss->Ree->Res). It is worth mentioning that the synchronous update mainly causes a decline in support F1 (88.69% to 87.51%). We argue that preferentially updating some nodes will progressively affect the representation of subsequent nodes, causing different effects on the final answer prediction and the evidence prediction.

4.5 Result Analysis

We provide result analysis based on the reasoning types officially annotated by HotpotQA to illustrate which reasoning is affected by our methods. HotpotQA provides two reasoning types: "bridge" and "comparison". The former requires the model to find bridge information before reaching the final answer, while the latter requires the model to compare the attributes of two entities and then give the answer. For a fair comparison, we mainly focus on published Roberta-large based HGN. As shown in Table 4, our AMGN achieves better results on the "bridge" reasoning type and is fairly competitive on the "comparison" reasoning type. Interestingly, the performance of two variants on the "bridge" type is higher than HGN. We hypothesize that our methods mainly work on sequential reasoning as both asynchronous update and question reformulation have obvious sequential logic. For the "comparison" task, there is still room for further improvement.

4.6 Case Study

We further provide a case study to illustrate the specific reasoning chain in AMGN. We visualize the row-wise correlation αi,j in Eq. 8 between part of entity and sentence nodes after Updateee ,Updatees and Updatess . The results are shown in Figure 3, where the same y-axis labels of the 2-hop EE and ES heatmaps as 1-hop are omitted. We can observe that the cross-granularity attention weights explicitly emphasize the formation process of the reasoning chain in the asynchronous update phase. For example, in the 1-hop reasoning stage, more attention focuses on between "Big Stone Gap" in sent 1 and "Adriana Trigiani" in sent 1, "Adriana Trigiani" in sent 1 and "Adriana Trigiani" in sent 4, "Adriana Trigiani" in sent 4 and sent 1, and sent 1 and sent 4. Note that the confusing clues such as "Virginia" in sent 2 are also considered in multi-hop reasoning, which shows that AMGN compares the sentence information and makes a correct prediction.

5 Conclusion

In this paper, we present AMGN for multi-hop reading comprehension. We introduce an asynchronous update mechanism of the multi-grained graph to mimic the logic of human multi-hop reading. Additionally, a RNN-based question reformulation method is proposed to update the hidden representation of compound questions. Experimental results and analysis show that asynchronously updating the graph in accordance with the sequence of human logic can boost the performance of the model by a significant margin under the premise of the reasonable use of node representations. As for future work, both paragraph-level and document-level representations can be considered as more complex composition elements, and the calculation order of logical relationships also needs to be designed adaptively. Besides, we would like to evaluate our model on other multi-hop MRC datasets.