Multi-hop Reading Comprehension across Documents with Path-based Graph Convolutional Network

1 Introduction

Machine reading comprehension has been a popular topic in the past years, and a variety of models have been proposed to address this problem, such as BIDAF [Seo et al., 2017], Reinforced mnemonic reader [Hu et al., 2017], and ReasoNet [Shen et al., 2017]. However, most existing works focus on finding evidence and answer in a single document.

In fact, in reality, many questions can only be answered after reasoning across multiple documents. Table 1 shows a multi-choice style reading comprehension example, which is fromWIKIHOP dataset [Welbl et al., 2018]. In the example, we can only answer the question 'what is the place of death of alexander john ellis?' after extracting and integrating the facts 'Alexander John Ellis is buried in Kensal Green Cemetery' and 'Kensal Green Cemetery is located in Kensington' from multiple documents, which is a more challenging task.

The main challenge is that the evidence is distributed in different documents and there is a lot of noise in the documents. We need to extract this evidence from multiple documents, but it is difficult to capture their dependencies for reasoning.

∗ corresponding author

s to the entity graph. And then, we apply a Gated-RGCN to learn the representation of nodes. Compared to GCNs, GatedRGCN utilizes attention and question-aware gating mechanism to regulate the usefulness of information propagating across documents and add question information during reasoning, which is closer to human reasoning processes.

Our contributions can be summarized as follows:

• We propose a path-based reasoning graph, which introduces information about reasoning paths into the graph;
• We propose Gated-RGCN to optimize the convolution formula of RGCN, which is more suitable for multi-hop reading comprehension;
• We evaluated our approach on WIKIHOP dataset [Welbl et al., 2018], and our approach achieves new state-ofthe-art accuracy. Especially, our ensemble model surpasses the human performance by 4.2%.

2 RelatedWork

Recently, there are several categories of approaches that have been proposed to tackle the problem of multi-hop reading comprehension across documents, including GCN-based approaches (Entity-GCN [De Cao et al., 2019], BAG [Cao et al., 2019], HDE [Tu et al., 2019], MHQA-GRN [Song et al., 2018], DFGN [Qiu et al., 2019]), memory based approaches (Coref-GRU [Dhingra et al., 2018], EPAr [Jiang et al., 2019]), path based approaches (PathNet [Kundu et al., 2019]), and attention based approaches (CFC [Zhong et al., 2019], DynSAN [Zhuang and Wang, 2019]).

GCN-based approaches organize supporting documents into a graph, and then employ Graph Neural Networks based message passing algorithms to perform multi-step reasoning. For example, Entity-GCN [De Cao et al., 2019] constructed an entity graph from supporting documents, where nodes are mentions of subject entity and candidates, and edges are relations between mentions. BAG [Cao et al., 2019] applied bi-directional attention between the entity graph and the query after GCN reasoning over the entity graph. HDE [Tu et al., 2019] constructed a heterogeneous graph where nodes correspond to candidates, documents, and entities. MHQAGRN [Song et al., 2018] constructed a graph where each node is either an entity mention or a pronoun representing an entity, and edges fall into three types: same-typed, window-typed and coreference-typed edge. DFGN [Qiu et al., 2019] proposed a dynamic fusion reasoning block based on graph neural networks. Our work proposes Gated-RGCN to optimize the graph convolution operation, it is better for regulating the usefulness of information propagating across documents and add question information during reasoning.

Memory-based approaches try to aggregate evidences for each entity from multiple documents through a memory network. For example, Coref-GRU [Dhingra et al., 2018] aggregated information from multiple mentions of the same entity by incorporating coreference in the GRU layers. EPAr [Jiang et al., 2019] used a hierarchical memory network to construct a 'reasoning tree', which contains a set of root-to-leaf reasoning chains, and then merged evidences from all chains to make the final prediction.

PathNet [Kundu et al., 2019] proposed a typical path-based approach for multi-hop reading comprehension. It extracted paths from documents for each candidate given a question, and then predicted the answer by scoring these paths. Our work introduces the idea of path-based approach on GCNbased approach which is better for multi-hop reasoning.

CFC [Zhong et al., 2019] and DynSAN [Zhuang and Wang, 2019] are two typical attention-based approaches. CFC applied co-attention and self-attention to learn query aware node representations of candidates, documents and entities. While DynSAN proposed a dynamic self-attention architecture to determine what tokens are important for constructing intra-passage or cross-passage token level semantic representations. In our work, we employ an attention mechanism between graphs and the question at each layer of GatedRGCN.

Meanwhile, in order to promote the research on multihop QA, several datasets have been designed, including WikiHop [Welbl et al., 2018], OpenBookQA [Mihaylov et al., 2018], NarrativeQA [Kocisk´y et al., 2017], MultiRC [Khashabi et al., 2018] and HotpotQA [Yang et al., 2018]. For example, WikiHop is a multi-choice style reading comprehension data set, where the task is to select the correct object entity from candidates when given a query 〈s, r, ?〉 and a set of supporting documents. While OpenBookQA focuses on the multi-hop QA which needs a corpus of provided science facts (open book) with external broad common knowledge.

In addition, knowledge completion over knowledge graph (KG) and KG based query answering are also related to our task, since they both need multi-hop reasoning, i.e., finding the reasoning path between two entities in KG. For example, MINERVA [Das et al., 2017] formulates the multi-hop reasoning as a sequential decision problem, and uses the REINFORCE algorithm [Williams, 1992] to train an end-to-end model for multi-hop KG query answering. Meta-KGR [Lv et al., 2019] also used the reinforcement learning method to learn a relation-specific multi-hop reasoning agent to search for reasoning paths and target entities. They further used meta-learning to perform multi-hop reasoning over few-shot relations of knowledge graphs.

3 Approach

In this section, we first formulate the task of multi-hop reading comprehension across documents, and then elaborate our approach in detail.

3.1 Task Formulation

The task of multi-hop reading comprehension across documents can be formally defined as: given a question q = (q1, q2, ..., qM) and a set of supporting documents Sq, the task is to find the correct answer a from a set of answer candidates Cq = (c1, c2, ..., cN), where M is the number of words in the question q and N is the number of candidates in Cq.

In the WIKIHOP dataset [Welbl et al., 2018], the question q is given in the form of a tuple 〈s, r, ?〉, where s represents the subject entity, and r represents the relation between s and the unknown tail entity. In our example, q =

〈alexander john ellis, place of death, ?〉 means where did alexander john ellis die, and the answer candidates is Cq = (college park, france,Kensington, London). When given the supporting documents, e.g., supporting doc1, doc2 in Table 1, we should identify the correct answer a = Kensington from the candidates by reasoning across these documents.

As shown in Figure 1, our approach mainly consists of three components, including graph construction, reasoning with Gated-RGCN, and output layer. In the following sections, we will elaborate on each component in detail.

3.2 Graph Construction

We construct an entity graph based on the EntityGCN [De Cao et al., 2019], which extracts all mentions of entities in Cq∪{s} in Sq as nodes in the graph. Besides, inspired by the human reasoning processing, reasoning paths from the subject entity in question to the candidates could be helpful for reasoning across documents, so we add reasoning entities in the paths into our entity graph. In our example, the path alexander john ellis → Kensal Green Cemetery → Kensington from documents indicate that the candidate Kensington may be the correct answer for the question 〈alexander john ellis, place of death, ? 〉. Thus, we treat Kensal Green Cemetery as a reasoning entity, and add it into the entity graph.

Formally, for a given question q = 〈s, r, ?〉, we would like to extract paths from s to ci ∈ Cq from Sq, e.g., pi = s → e1 → e2 → ... → el → ci, where ei is a reasoning entity. In order to find a path, we first find a document d1 which contains the mention ms of the subject entity s in Sq, and then find all the named entities and noun phrases that appear in the same sentence with ms. In our example, we find Kensal Green Cemetery and alexander john ellis appear in the same sentence in supporting doc1, so we extract Kensal Green Cemetery as one of reasoning entities. Then, we find another document d2 which contains any of the reasoning entities. In our example, supporting doc2 contains the reasoning entity Kensal Green Cemetery. Finally, we check whether the reasoning entity appears with one of the candidates in the same sentence. If so, we would add the path to the entity graph. For example, Kensal Green Cemetery and Kensington appear in the same sentence in supporting doc2. Therefore, the path alexander john ellis → Kensal Green Cemetery →Kensington can be added to the entity graph.

Since each entity in different documents has different contexts, so we use mentions of the subject entity, reasoning entities, and candidate answers as nodes in the entity graph. In our example, Kensal Green Cemetery appears in two different sentences, so we need to add nodes for different positions Figure 2 shows an example of an entity graph, where ms, mc and ma are mentions of the subject entity s, reasoning entities Cc, and candidate answers Cq respectively.

Then, we define the following types of edges between pairs of nodes to encode various structural information in the entity graph.

1. an edge between a subject node and a reasoning node if they appear in the same sentence in a document, e.g., esc in Figure 2.
2. an edge between two nodes if they are reasoning nodes and are adjacent nodes on the same path, e.g., ecc in Figure 2.
3. an edge between a reasoning node and a candidate node if they appear in the same sentence in a document, e.g., eca in Figure 2.
4. an edge between two nodes if they are mentions of the same candidate, e.g., eaa in Figure 2.
5. an edge between two nodes if they appear in the same document.
6. nodes that do not meet previous conditions are connected.

3.3 Reasoning with Gated-RGCN

We first use pretrained word embeddings GLoVe [Pennington et al., 2014] to represent each node in the entity graph, and then use ELMo [Peters et al., 2018] to model contextual information for each node in different documents. These two vectors are concatenated, and then encoded through 1-layer linear network. Thus, the features for all nodes can be denoted as fn ∈ RT×d , where T is the number of nodes in the graph, and d is the dimension of the node feature.

After graph initialization, we employ a Gated Relational Graph Convolutional Network (Gated-RGCN) to realize multi-hop reasoning. First, we use R-GCN to aggregate messages from its direct neighbors. Specifically, at lth layer, the aggregated message zl i for node i can be obtained via

where Ni is the neighbors of node i, Rij is the set of relations between i and j, W l r ∈ Rd×d is a relation-specific weight matrix, | · | indicates the size of Ni, and hlj is the hidden state of node j at lth layer. Then, the update message uli for node i can be obtained by combining the aggregated message with its original node information:

where W l0 ∈ Rd×d is a general weight.

In Entity-GCN [De Cao et al., 2019], HDE [Tu et al., 2019] and BAG [Cao et al., 2019], a gating mechanism is applied on the update vector uli and the hidden state of node i for updating the hidden state of node i at the next layer.

where σ is the sigmoid function, [uli ; hli ] is the concatenation of uli and hli , fg is implemented with a single-layer multilayer perceptron (MLP), tanh(·) is a non-linear activation function, and ⊙ denotes element-wise multiplication.

This gating mechanism regulates how much of the update message propagates to the next step, so it can prevent overwriting past information. However, the traditional GCN method only updates the central node based on the aggregated information of adjacent nodes, but there is a lot of irrelevant information during information propagating.

When humans do reasoning problems, they always choose the supports information based on the query information. Inspired by human reasoning processing, we add another question-aware gate to optimize graph convolution procedure, which is suitable for multi-hop reading comprehension. This gating mechanism can regulate the aggregated message according to the question, and introduce the question information into the update message simultaneously.

First, we represent the question q using a bidirectional LSTM (BiLSTM) network [Hochreiter and Schmidhuber, 1997], where GLoVe is used as word embeddings.

Then, the final question representation can be obtained by a weighted sum of these vectors.

Finally, uli could be updated via:

With this new uli , we use Equation 1 and 2 to obtain hl+1 i , which is the hidden state of node i at the (l + 1)th layer.

We stack the networks for L layers where all parameters are shared, and finally obtain hL = {hLi }Ti=1 for the entity graph.

3.4 Output Layer

Similar to BAG [Cao et al., 2019], we apply a bi-directional attention between the entity graph and the question. The similarity matrix S ∈ RT×M is first calculated via

where avg-1 is the average operation in last dimension, and fa is a single-layer MLP. Then, the node-to-question attention gn2q and question-to-node attention gq2n are calculated via

where softmaxcol and maxcol denote performing softmax and max function across columns respectively, dup is the function to duplicate the result softmax(maxcol(S)) ∈ R1×M for T times into shape RT×M .

The output of the bi-directional attention layer is [hL; gn2q; hL ⊙ gn2q; hL ⊙ gq2n], which is then fed to a 2layer fully connected feed-forward network with tanh as the activation function in each layer. Finally, the softmax function is applied among the output, which can generate the prediction result for each node in the graph. Each candidate may correspond to several nodes, since it may appear in multiple documents. We use the maximal probability of these nodes as the result of the candidate, and use cross-entropy as the loss function.

4 Experiments

4.1 Dataset and Experimental Settings

We use WIKIHOP [Welbl et al., 2018] to validate the effectiveness of our proposed approach, which is a multi-choice style reading comprehension data set. The dataset contains about 43K/5K/2.5K samples in training, development, and test set respectively. The test set is not public and can only be evaluated online blindly.

In our implementation, we use NLTK [Bird, 2006] to tokenize the supporting documents, question, and candidates into word sequences, and then find mentions of subject entity and candidates in supporting documents through the exact matching strategy. In order to extract reasoning entities, we use Stanford CoreNLP [Manning et al., 2014] to perform entity recognition on the supporting documents.

We use the standard 1024-dimension ELMo and 300dimension pre-trained GLoVe (trained from 840B Web crawl data) as word embeddings. The dimensions of hidden states in BiLSTM and GCN are set as d = 256, and the number of nodes and the query length is truncated as 600 and 25 respectively. We stack L = 4 layers of the Gated-RGCN blocks. During training, we set the mini-batch size as 16, and use Adam [Kingma and Ba, 2015] with learning rate 0.0002 for learning the parameters.

4.2 Main Results

We compare our approach with several previously published models, and present our results in Table 2. The performance of multiple choice QA is evaluated by the accuracy of choosing the correct answer. Table 2 shows the performance of approaches both on development and test set respectively. As shown in the table, we can see that our approach achieves the state-of-the-art accuracy on both development and test set against all types of approaches, including GCN-based approaches (Entity-GCN [De Cao et al., 2019], BAG [Cao et al., 2019], HDE [Tu et al., 2019], MHQA-GRN [Song et al., 2018]), memory-based approaches (Coref-GRU [Dhingra et al., 2018], EPAr [Jiang et al., 2019]), path-based approaches (PathNet [Kundu et al., 2019]), and attention-based approaches (CFC [Zhong et al., 2019], DynSAN [Zhuang and Wang, 2019]).

For ensemble models, our approach also achieves state-ofthe-art performance, which surpasses the reported human performance [Welbl et al., 2018] by about 4.2%.

4.3 Ablations Studies

We conduct an ablation study to evaluate the contribution of each model component, and show the results in Table 3.

In (a), we delete all reasoning entities, so our graph degenerates to the entity graph in [De Cao et al., 2019]. The accuracy on the development set drops to 69.1%, but it is still higher than the accuracy of Entity-GCN [De Cao et al., 2019]. This proves the effectiveness of reasoning entities and the Gated-RGCN mechanism. In (b), we do not bring in the question in the reasoning. While in (c), we only use BiLSTM to encode the question, but do not adopt the attention mechanism in BiLSTM. From (b) and (c), we can see that question is useful for reasoning. In (d), we treat all edge types equally, so Gated-RGCN is replaced by Gated-GCN in reasoning, which reduces 1.8% accuracy absolutely. In (e), we only define the edge types as in BAG [Cao et al., 2019], and the accuracy drops to 69.5%. From (d) and (e), we learn that different types of edges is also critical in the reasoning.

4.4 Analysis

In this section, we conduct a series of experiments with different setting in our approach.

Different number of Gated-RGCN Layers. We evaluate our approach with different number of GCN layers (L), and the result is shown in Figure 3(a). From the figure, we can see that the accuracy increases gradually and then drops finally, which proves the effectivity of Gated-RGCN. It is expected that the accuracy drops finally, because more hops would bring in noise. As for why 4-hops is the best, this may be because many samples are 1-hop problems, and the length of path in these samples is exactly 4.

Different number of supporting documents. We split the development set into subsets according to the number of supporting documents, and then evaluate our approach on each subset. The results are shown in Figure 3(b). From the figure, we can see that more documents may bring in more irrelevant information, which is harmful to the multi-hop QA. However, even on a number greater than 16, our model achieved an accuracy of 69.5%, which is better than the overall effect of most models.

Different word embeddings. Table 4 shows the results of our approach when using different word embeddings. From the table, we can see that only using ELMo or GLoVe in our approach will cause a severe drop, and replacing ELMo with BERT [Devlin et al., 2019] delivers a competitive result. Meanwhile, we can see that for the GCN-based approach, the initialization of nodes is extremely critical, because this type of approach has greatly compressed the information when constructing the graph.

5 Conclusion

In this paper, we propose a novel approach for multi-hop reading comprehension across documents. Our approach extends the entity graph by introducing reasoning entities, which can form the reasoning path from question to candidates. In addition, our approach incorporates the question in the multi-hop reasoning through a new gate mechanism to regulate how much useful information propagating from neighbors to the node. Experiments show that our approach achieves state-of-the-art accuracy both for single and ensemble models.

Our future work would focus on the interpretability of the multi-hop reading comprehension across documents. In addition, we would like to build the entity graph with reasoning entities dynamically during the reasoning, and apply our model on other datasets.

Acknowledgments

This work is supported by the National Key Research and Development Project of China (No. 2018AAA0101900), the Fundamental Research Funds for the Central Universities (No. 2019FZA5013), the Zhejiang Provincial Natural Science Foundation of China (No. LY17F020015), the Chinese Knowledge Center of Engineering Science and Technology (CKCEST) and MOE Engineering Research Center of Digital Library.