TransferNet: An Effective and Transparent Framework for Multi-hop Question Answering over Relation Graph

Introduction

Question answering (QA) plays a central role in artificial intelligence. It requires machines to understand the free-form questions and infer the answers by analyzing information from a large corpus Rajpurkar et al. (2016); Joshi et al. (2017); Chen et al. (2017) or structured knowledge base Bordes et al. (2015); Yih et al. (2015); Jiang et al. (2019). Along with the fast development of deep learning, especially the pretraining technology Devlin et al. (2018); Lan et al. (2019), state-of-the-art models have been shown comparative with human performance on simple questions that only need a single hop Petrochuk and Zettlemoyer (2018); Zhang et al. (2020), e.g., Who is the CEO of Microsoft Corporation. However, multi-hop QA, which requires reasoning with the entity relations at multiple steps, is far from resolved Yang et al. (2018); Dua et al. (2019); Zhang et al. (2017); Talmor and Berant (2018).

In this paper, we focus on multi-hop QA based on relation graphs, which consists of entities and their relations. As shown in Figure 1, the relations can be represented by two forms:

Label form, also known as knowledge graph (e.g., Freebase Bollacker et al. (2008), Wikidata Vrandečić and Krötzsch (2014)), whose relations are manually-defined constrained predicates (e.g., Spouse, CEO).

Text form, whose relations are free texts retrieved from textual corpus. We can easily build the graph by extracting the co-occuring sentences of two entities. Since the label form is expensive and usually incomplete, the text form is more economical and practical.

In this paper, we aim to tackle multi-hop questions over these two different forms in a unified framework.

Existing methods for multi-hop QA have two main strands. The first is to predict the sequential relation path in a weakly supervised setting Zhang et al. (2017); Qiu et al. (2020), that is, to learn the intermediate path only based on the final answer. These works suffer from the convergence issues due to the huge search space, which heavily hinders their performance. Besides, they are mostly proposed for the label form. So, it is not clear how to adapt them to the text form, whose search space is even much huger. The second strand is to collect evidences by using graph neural networks Sun et al. (2018, 2019). They can handle both the two relation forms and achieve state-of-the-art performance. Although they prevail over the path-based models in performance, they are weak in interpretability since their intermediate reasoning process is black-box neural network layers.

In this paper, we propose a novel model for multi-hop QA, dubbed TransferNet, which has the following advantages: 1) Generality. It can deal with the label form, the text form, and their combinations in a unified framework. 2) Effectiveness. TransferNet outperforms previous models significantly, achieving 100% accuracy of 2-hop and 3-hop questions in MetaQA dataset. 3) Transparency. TransferNet is fully attention-based, so its intermediate steps can be easily visualized and understood by humans.

Specifically, TransferNet infers the answer by transfering entity scores along relation scores of multiple steps. It starts from the topic entity of the question and maintains an entity score vector, whose elements indicate the probability of an entity being activated. At each step, it attends to some question words (e.g., the wife of) and compute scores for the relations in the graph. Relations relevant to the question words will have high scores (e.g., Spouse). We formulate these relation scores into an adjacent matrix, where each entry indicates the transfer probability of an entity pair. By multiplying the entity score vector with the relation score matrix, we can “hop” along relations in a differentiable manner. After repeating for multiple steps, we can finally arrive at the target entity.

We conduct experiments for the two forms respectively. For the label form, we use MetaQA Zhang et al. (2017), WebQSP Yih et al. (2016) and CompWebQ Talmor and Berant (2018). TransferNet achieves 100% accuracy in the 2-hop and 3-hop questions of MetaQA. On WebQSP and CompWebQ, we also achieve a significant improvement over state-of-the-art models. For the text form, following Sun et al. (2019), we construct the relation graph of MetaQA from the WikiMovies corpus Miller et al. (2016). We demonstrate that TransferNet surpasses previous models by a large margin, especially for the 2-hop and 3-hop questions. When we mix the label form and the text form, TransferNet still keeps its superiority. Moreover, by visualizing the intermediate results, we show its strong interpretability. https://github.com/shijx12/TransferNet

Related Work

In this paper we focus on multi-hop question answering over the graph structure that is either knowledge graph or built from text corpus. In previous works, GraftNet Sun et al. (2018) and PullNet Sun et al. (2019) have a similar setting to ours but they mostly aim at the mixed form, which includes both label relations and text relations. They first retrieve a question-specific subgraph and then use graph convolutional networks Kipf and Welling (2016) to implicitly infer the answer entity. These GCN-based methods are usually weak in interpretability because they cannot produce the intermediate reasoning path, which is necessary in our opinion for the task of multi-hop question answering. Besides, there are many works specifically for only one graph form:

For the label form, which is also known as “KBQA” or “KGQA”, existing methods fall into two categories: information retrieval Miller et al. (2016); Xu et al. (2019); Zhao et al. (2019b); Saxena et al. (2020) and semantic parsing Berant et al. (2013); Yih et al. (2015); Liang et al. (2017); Guo et al. (2018); Saha et al. (2019). The former retrieves answer from KG by learning representations of question and graph, while the latter queries answer by parsing the question into logical form. Among these methods, VRN Zhang et al. (2017) and SRN Qiu et al. (2020) have a good interpretability as they learn an explicit reasoning path with reinforcement learning. However, they suffer from the convergency issue due to the huge search space. IRN Zhou et al. (2018) and ReifKB Cohen et al. (2020) learn a soft distribution for intermediate relations and can be optimized using only the final answer. However, it is not clear how to extend them to the text form.

Question answering over text corpus is also known as “reading comprehension”. For simple questions, whose answer can be retrieved directly from the text, pretrained models Devlin et al. (2018); Lan et al. (2019) have performed better than humans Zhang et al. (2020). For multi-hop questions that are much more challenging, existing works Ding et al. (2019); Fang et al. (2019); Tu et al. (2020); Zhao et al. (2019a) usually convert the text into a rule-based or learning-based entity graph, and then use graph neural networks Kipf and Welling (2016) to perform implicit reasoning. Similar to PullNet, they are weak in interpretability. Besides, most of them build the graph by just connecting relevant entities, missing the important edge textual information.

Methodology

We conduct multi-hop reasoning on a relation graph, which takes entities as nodes and relations between them as edges. The relations can be of different forms, specifically, constrained labels or free texts. The former is also known as structured Knowledge Graph (e.g., Wikidata Vrandečić and Krötzsch (2014)), which predefines a set of predicates to represent the entity relations. The latter can be easily extracted from large-scale document corpora according to the co-occurence of entity pairs. Figure 1 shows examples of these two forms. In this paper we call them label form and text form respectively, and use mixed form to denote a relation graph consisting of both labels and texts.

We denote a relation graph as $\mathcal{G}$, its entities as $\mathcal{E}$ and its edges as $\mathcal{R}$. Let $n$ denote the number of entities, then $\mathcal{R}$ is an $n\times n$ matrix whose element $r_{i,j}$ represents the relations between the head entity $e_{i}$ and the tail entity $e_{j}$. $r_{i,j}$ can be a set of labels (for label form) or texts (for text form) or both (for mixed form). A multi-hop question $q$ usually starts from a topic entity $e_{x}$ and needs to traverse across relations to reach the answer entities $Y=\{e_{y^{1}},\cdots,e_{y^{|Y|}}\}$.

2 TransferNet

To infer the answer of a multi-hop question, TransferNet starts from the topic entity and jumps for $T$ steps. At each step, it attends to different parts of the question to determine the most proper relation. TransferNet maintains a score for each entity to denote their activated probabilities, which are initialized to 1 for the topic entity and 0 for the others. At each step, TransferNet computes a score for each relation to denote their activated probabilities in terms of the current query, and then transfer the entity scores across those activated relations. Figure 2 shows the framework.

Formally, we denote the entity scores of step $t$ as a row vector $\mathbf{a}^{t}\in^{n}$, where $$means a real number between and$1$.$\mathbf{a}^{0}$is the initial scores, i.e., only the topic entity$e_{x}$gets$1$. At step$t$, we attend to part of the question to get the query vector$\mathbf{q}^{t}\in\mathcal{R}^{d}$, where$d$ is the hidden dimension.

$\mathbf{q}$ denotes the question embedding. $f^{t}$ is a projecting function of step $t$, which maps $\mathbf{q}$ to a specific query key $\mathbf{qk}^{t}$. $\mathbf{qk}^{t}$ is the attention key to compute scores for each word based on their hidden vector $\mathbf{h}_{i}$. $\mathbf{q}^{t}$ is the weighted sum of $\mathbf{h}_{i}$.

In terms of $\mathbf{q}^{t}$ TransferNet computes the relation scores $\mathbf{W}^{t}\in^{n\times n}$:

$\theta_{g}$ denotes the learnable parameters. We will have different implementations of $g$ for the label form and the text form, which will be introduced in Sec.3.5.

Then we can simulate the “jumping across edges” as the following formulation:

It means that the production of entity $e_{i}$’s previous score and the edge $r_{i,j}$’s current score will be collected into $e_{j}$’s current score.

After repeating for $T$ times, we get the entity scores of each step $\mathbf{a}^{1},\mathbf{a}^{2},\cdots,\mathbf{a}^{T}$. Then we compute their weighted sum as the final output:

where $\mathbf{c}\in^{T}$ denotes the probability distribution of the question’s hop, and $c_{t}$ is the probability value of hop $t$. We can answer all questions from $1$-hop to $T$-hop by automatically determine its hop number. The entity with maximum score in $\mathbf{a}^{*}$ is outputed as the answer.

TransferNet is a highly-transparent model. As shown in the example of Figure 2, we can easily track the model behaviour by visualizing the activated words, relations, and entities at each step (see Sec.5.4 for more examples).

3 Training

Given the golden answer set $Y=\{e_{y^{1}},\cdots,e_{y^{|Y|}}\}$, we construct the target score vector $\mathbf{y}\in\{0,1\}^{n}$ by

Then we take the L2 Euclidean distance between $\mathbf{a}^{*}$ and $\mathbf{y}$ as our training objective:

Note that TransferNet is totally differentiable, therefore we can learn all of the intermediate scores (i.e., question attention, relation scores, and entity scores of each step) via this simple objective..

4 Additional Modules

We propose two modules to facilitate the learning of TransferNet.

Score Truncation. According to Equation 4, $a^{t}_{j}$ may exceed $1$ after a transfer step. A too large score will have a bad influence to the gradient computation. Especially when the hop increases, it may lead to gradient explosion. Besides, our loss function, Equation 7, will fail if the final score has an unlimited value. So we need to rectify the entity scores after each transfer step, to ensure the value range is in $$. At the same time, we need to maintain the differentiability of the operation. We propose such a truncation function:

After each transfer step, we truncate $\mathbf{a}^{t}$ by applying this function to each of its elements.

Language Mask. TranferNet does not consider the language bias of the question, which may include some hints for its answer. For example, in the text-formed relation graph we may have (Harry Potter, _{was published in , United Kingdom) and (Harry Potter, was published in , 1997). These two triples depict different aspects (i.e., the publication place and the publication time of Harry Potter) but with the same relation text. As a result, given the question Where was Harry Potter published, TransferNet will produce the same scores for United Kingdom and 1997, and thus use 1997 to wrongly answer the Where-question.}

To solve this issue, we propose a language mask to incorporate the question hints. We predict a mask score for each entity using the question embedding:

where $\mathbf{m}\in^{n}$, $m_{i}$ denotes the mask score of entity $e_{i}$, MLP (short for multi-layer perceptron) projects $d$-dimensional feature to $n$-dimension. We multiply the mask to the final entity scores,

where $\odot$ means element-wise multiplication. The $\mathbf{a}^{*}$ in the objective function Equation 7 should be replaced with $\hat{\mathbf{a}^{*}}$. Note that we need the language mask only in the text form, because the predicates of label form have no ambiguity.

5 Relation Score Computation

Consider Equation 2, $\mathbf{W}^{t}=g(\mathbf{q}^{t};\theta_{g})$, we design different implementations of $g$ for different relation forms.

In the label form, relations are represented with a fixed predicate set $\mathcal{P}$. We first compute probabilities for these predicates in terms of $\mathbf{q}^{t}$, and then collect corresponding probabilities of $r_{i,j}$ as $W^{t}_{i,j}$.

Formally, the predicate distribution is computed by

The Softmax function can be replaced with Sigmoid if predicates are not mutually exclusive, i.e., multiple predicates will be activated meanwhile. Let $b$ denote the maximum number of relations between a pair of entity, then we can denote the relation as $r_{i,j}=\{r_{i,j,1},\cdots,r_{i,j,b}\}$, where $r_{i,j,k}\in\{1,2,\cdots,|\mathcal{P}|\}$. The predicate probabilities are collected in terms of the relation labels:

We gather the probabilities by summing them up. $\max$ is another feasible option, but we find $\sum$ is more efficient and more stable.

5.2 Text Form

In the text form, relations are represented with natural language descriptions. The graph is built by extracting the co-occuring sentence of a pair of entity and replacing the entities with special placeholders. For example, the sentence Bill Gates and Melinda Gates have been married for 26 years contributes an edge from Bill Gates to Melinda Gates, whose relation text is _{and have been married for 26 years, as shown in Figure 2. We can get the reverse relations by exchanging the placeholders of subject and object, but for simplicity, we do not show them in the figure.}

Let $r_{i,j}=\{r_{i,j,1},\cdots,r_{i,j,b}\}$ and $r_{i,j,k}$ denotes the $k$-th relation sentence. We use a relation encoder to obtain the relation embeddings, and then compute the relation score by

where $\odot$ means element-wise product, MLP maps the feature from $d$-dimensional to $1$-dimensional.

Since there are a huge amount of (usually millions of) relation texts in a relation graph, it is impossible to compute the embeddings and scores for all of them. So in practice, we select a subset of relations at each step. Specifically, at step $t$, we select entities whose previous score $a^{t-1}_{i}$ is larger than a predefined threshold $\tau$ and only consider relations that start from these entities. Besides, if there are too many relations meeting this condition, we will only preserve top $\omega$ of them, sorting based on their subject entity score. By doing so, we just need to consider at most $\omega$ relations at each step.

We use the same method to process the mixed form, by simply regarding the label predicates as one-word sentences.

Experiments

MetaQA Zhang et al. (2017) is a large-scale dataset of multi-hop question answering over knowledge graph, which extends WikiMovies Miller et al. (2016) from single-hop to multi-hop. It contains more than 400k questions, which are generated using dozens of templates and have up to 3 hops. Its knowledge graph is from the movie domain, including 43k entities, 9 predicates, and 135k triples.

Besides the label from, we also constructed the text form of MetaQA by extracting the text corpus of WikiMovies Miller et al. (2016), which introduces the information of movies with free text. Following Sun et al. (2019), we used exact match of surface forms for entity recognition and linking. Given an article of a movie, we took the movie as subject and the other relavant entities (e.g., mentioned actor, year, and etc) as objects. The sentence was processed with placeholders, that is, replacing the movie with _{(if it occurs) and the object entity with , and then regarded as the relation texts. An entity pair can have multiple textual relations.}

WebQSP Yih et al. (2016) has a smaller scale of questions but larger scale of knowledge graph. It contains thousands of natural language questions based on Freebase Bollacker et al. (2008), which has millions of entities and triples. Its questions are either 1-hop or 2-hop. Following Saxena et al. (2020), we pruned the knowledge base to contain only mentioned predicates and within 2-hop triples of mentioned entities. As a result, the processed knowledge graph includes 1.8 million entities, 572 predicates, and 5.7 million triples. We only consider the label form of WebQSP due to its huge scale.

CompWebQ Talmor and Berant (2018) is an extended version of WebQSP with more hops and constraints. Following Sun et al. (2019), we retrieved a subgraph for each question using PageRank algorithm. On average, there are 1948 entities in each subgraph and the recall is 64%. Table 1 lists the statistics of these datasets.

2 Baselines

KVMemNN Miller et al. (2016) uses the key-value memory to store knowledge and conducts multi-hop reasoning by iteratively reading the memory.

VRN Zhang et al. (2017) learns the reasoning path via reinforcement learning. Its intermediate results have a good interpretability.

SRN Qiu et al. (2020) improves VRN by beam search and reward shaping strategy, boosting its speed and performance.

GraftNet Sun et al. (2018) extracts a question-specific subgraph from the entire relation graph with heuristics, and then uses graph neural networks to infer the answer.

PullNet Sun et al. (2019) improves GraftNet by learning to retrieve the subgraph with a graph CNN instead of heuristics.

ReifKB Cohen et al. (2020) proposes a scalable implementation of probability transfer over large-scale knowledge graph of label form. It can be regarded as a degenerated case of TransferNet.

EmbedKGQA Saxena et al. (2020) takes KGQA as a link prediction task and incorporates knowledge graph embeddings Bordes et al. (2013); Trouillon et al. (2016) to help predict the answer.

3 Implementations

We added reversed relations into the relation graph, leading to double size of predicates and triples. For the text form, we exchanged the placeholder _{and as the reversed relation, e.g., co-founded the is converted to co-founded the .}

For the experiments of MetaQA, we set the step number $T=3$. We used bi-directional GRU Chung et al. (2014) as the question encoder, and set the hidden dimension as $1024$. The projecting function $f^{t}$ was a stack of linear layer and Tanh layer. The involved MLPs were implemented as simple linear layers. For the text form, we used another bi-directional GRU as the relation encoder. The threshold $\tau$ was set to $0.7$ and $\omega$ was set to $400$. Since the question hop is provided in MetaQA, we used the golden hop number as an auxiliary objective to help learn the hop distribution $\mathbf{c}$. We computed the cross entropy loss and added it into Equation 7 after multiplying a factor of $0.01$. The model was optimized using RAdam Liu et al. (2020) with a learning rate $0.001$ for 20 epochs, which took several hours for the label form and about one day for the text form on a single GPU of NVIDIA 1080Ti.

For the experiments of WebQSP and CompWebQ, we set the step number $T=2$. We used a pretrained BERT Devlin et al. (2018) as the question encoder and finetuned its parameters on our task. There is no hop annotations so we did not use the auxiliary loss. Other settings are the same as MetaQA.

Results

Table 2 compares different models on label-formed datasets. TransferNet performs perfectly in the 2-hop and 3-hop questions of MetaQA, that is, achieving 100% accuracy. As for the 1-hop questions of MetaQA, TransferNet achieves 97.5%, on a par with previous models like VRN and EmbedKGQA. We analyze the wrong cases of 1-hop and find that the errors are caused by the ambiguity of entities. For example, the question who acted in The Last of the Mohicans asks the actors of the movie The Last of the Mohicans. In the knowledge graph there are two movies with this name, one released in 1936 and the other released in 1920. Our model outputs the actors of both movies, whereas the MetaQA dataset only considers the actors of the 1920 one as golden answer, causing an inevitable mismatch. Previous work’s performance should also suffer from this dataset fault. In the questions of 2-hop and 3-hop, the ambiguity is mostly eliminated by the relation restrictions. Therefore, TransferNet can achieve 100% accuracy. We can say that the label-formed MetaQA dataset has been nearly solved by our TransferNet.

WebQSP is more challenging than MetaQA, because it has a much more predicates and triples yet much less training examples. TransferNet achieves 71.4% accuracy, beating previous state-of-the-art models (68.1%) by a large margin, implying that it is well qualified for large-scale knowledge base.

On the CompWebQ dataset, we compare the results with Sun et al. (2019) on the dev set. TransferNet achieves 48.6% accuracy, still better than PullNet (47.2%).

2 Results on Text-Formed Graph

In Table 2 we compare TransferNet with state-of-the-art models that are able to handle text-formed relations. We can see that TransferNet significantly outperforms previous models. Especially for questions of 2-hop and 3-hop, we improve the accuracy from 81.0% to 98.1% and from 78.2% to 94.3% respectively. PullNet and GraftNet both infer the answer by aggregating the graph features implicitly, and thus cannot provide the intermediate relation path. Compared with them, TransferNet not only has a superior performance, but also has a better interpretability (see Sec.5.4).

Besides the pure text form, we also compare the mixed form following Sun et al. (2018, 2019). That is, randomly selecting 50% of the label-formed triples and add them into the text-formed relation graph. In this setting, we simply consider the predicates as sentences containing just one word, and use the relation encoder (see Sec.3.5.2) to process them. These 50% labels slightly improve the performance of TransferNet over the pure text form (about 0.4%), because some relations are missing in the text corpus. Compared with PullNet, TransferNet is still in the lead by a large gap (85.2% v.s. 94.7%).

3 Ablation Study

Table 4 shows results of ablation study. We can see that the score truncation and language mask are both important, especially for the text form. As stated in Sec. 3.4, the language mask is not needed in the label form. The auxiliary loss (see Sec. 4.3) slightly improves the performance because it helps the learning of hop attention.

4 Interpretability

We visualize the intermediate results of TransferNet for two 3-hop questions in Figure 3. The entities and relations whose score is larger than $0.8$ are highlighted in red. The top question is aimed at the label-formed relation graph. The activated predicates for three hops are directed_by, directed_by_rev, and starred_actors respectively, where the suffix _rev means reverse relation. The bottom question is aimed at the text form. At step 1, TransferNet tries to find the screenwriter of the topic movie, and activates the relation whose textual description is “based on the novel of the same name by ”. At step 2, the movie written by Harold Bell Wright is found. At step 3, we aim to find the movie’s release year. But since the text descriptions of Western (which is the movie’s genre) and 1926 are very similar, both of these two entities are activated. Here the proposed language mask successfully filters the wrong answers out.

5 Model Efficiency

Figure 4 shows the average hits@1 on the label form of MetaQA when the models are trained with partial training examples (left) and at different epochs (right). We can see that TransferNet is very data-efficient and converges very fast. With only 10% training data, it still achieves the same performance as the entire training set. And it only needs two epochs to reach the optimal results.

Conclusions

We proposed TransferNet, an effective and transparent framework for multi-hop QA over knowledge graph or text-formed relation graph. It achieved 100% accuracy on 2-hop and 3-hop questions of label-formed MetaQA, nearly solving the dataset. On the more challenging WebQSP, CompWebQ and text-formed MetaQA, it also outperforms other state-of-the-art models significantly. Qualitative analysis shows the good interpretability of TransferNet.

Acknowledgments

This work is supported by the NSFC Key Project (U1736204), grants from the Institute for Guo Qiang, Tsinghua University (2019GQB0003), Beijing Academy of Artificial Intelligence, Huawei Inc, and MOE AcRF Tier 2.

References