Two-Phase Hypergraph Based Reasoning with Dynamic Relations for Multi-Hop KBQA

1 Introduction

Knowledge base question answering (KBQA) is a challenging task and has attracted many researchers to work on it. Previous work [Xu et al., 2016; Huang et al., 2019] mainly focuses on single-hop QA which can be answered by one fact triple in KB. Although the performance has been improved a lot over the last years, these methods lack the ability to reason across multiple triples when one triple is not enough to answer the question. And this type of questions is defined as multi-hop QA, which requires a reasoning path involving multiple triples to obtain the answers (e1 → r1 → e2 → ... → rn-1 → en). As shown in Figure 1, we give a two-hop KBQA example. The reasoning path starts from the entity mentioned in the query and consists of the relations at each hop and the intermediate entities.

In order to solve the multi-hop KBQA, some work has been proposed recently, which can be roughly divided into two research directions. The first one is based on previous neural network models, such as the studies in [Zhou et al., 2018; Xu et al., 2019]. The other direction is based on graph neural networks [Wu et al., 2019] which develops rapidly in recent years, and has achieved desirable performance [Sun et al., 2018; Sun et al., 2019]

Note that when human performs multi-hop reasoning, one starts from the entity mentioned in the query and walks down to the next hop following specific relations at different hops, and repeats this step to form a reasoning path and find the final answers, as shown in Figure 1. We believe that relation information is vital for multi-hop reasoning. However, previous work does not fully utilize the relation information. The work in Schlichtkrull et al. [2018] calculates relation-specific transformation by separating different relations, which does not consider the semantic relation information. And work in Xiong et al. [2019] takes relation information to acquire static graph attention without updating relation information during the multi-hop reasoning process.

Morever, the pairwise connection between nodes based on graph convolutional networks (GCN) may be not sufficient to fully represent the knowledge graph's high-order relationship among entities and relations. And some leading work on hypergraph convolutional networks (HGCN) [Feng et al., 2019; Yadati et al., 2019] has been proposed recently. HGCN leverages hyperedges to connect more than two nodes simultaneously, which is conductive to mimicing human reasoning of pinpointing a group of entities connected by same relation, rather than entity-by-entity reasoning. On the downside, HGCN is for undirected hypergraphs, but knowledge graph is directed which each triple has specific direction meaning. Also HGCN learns the relation representation potentially by gathering from the connected entities, but does not reveal and further utilize it.

This paper firstly proposes the Directed Hypergraph Convolutional Networks (DHGCN) for directed hypergraph to take the direction of information transmission into account. Inspired by human's hop-by-hop reasoning behavior, we further propose a novel and interpretable directed hypergraph convolutional network based model for multi-hop KBQA, namely Two-Phase Hypergraph Based Reasoning with Dynamic Relations (2HR-DR), which explicitly updates the relation information and dynamically focuses on specific relation at different hops. Specifically, we separate the DHGCN into two-phase to let the model firstly learns relation representation explicitly by connected entity feature, and allocates weight dynamically for different relations, then updates the entity states based on dynamic relation weights. Moreover, we predict relations hop-by-hop and form a sequential relation path to make the reasoning interpretable.

The main contributions of this paper can be summarized as follows:

• This paper proposes a directed hypergraph convolutional network that incorporates direction information into HGCN to deal with directed knowledge graph.
• We further propose a two-phase hypergraph based reasoning with dynamic relations which explicitly learns and updates relation information and dynamically concentrates on different relations at different hops.
• Our model is interpretable which predicts relations hopby-hop and form an observable path for reasoning analysis and failure diagnosis.
• We experiment on two widely used multi-hop KBQA datasets and the experimental results demonstrate the effectiveness of our model.

2 RelatedWork

2.1 Multi-hop Question Answering

Multi-hop KBQA models can be roughly divided in two types. The first one is to apply the previous neural networks. These models adapt the previous single-hop QA methods [Bordes et al., 2014; Hao et al., 2017; Min et al., 2018] to multi-hop QA. Xu et al. [2019] improves KVMemNet to achieve better results across multiple triples. Zhong et al. [2019] employs a coarse-grain and a fine-grain module. However, these methods lack of considering graph-structure information. The other is based on graph neural networks. Tu et al. [2019b] employs GCN to reason over heterogeneous graphs. Sun et al. [2019] learns what to retrieve from the KB and corpus and then reasons over the built graph. Xiong et al. [2019] applies graph attention networks to achieve better performance. Cao et al. [2019] proposes a bi-directional attention entity graph convolutional network. These models either use r-GCN [Schlichtkrull et al., 2018] which does not consider the semantic relation information, or use graph attention networks to assign static weights. Different from these models, this paper proposes a dynamic relation strategy, which dynamically updates relation states during the reasoning process and focuses on different relations at different hops.

2.2 Explainable Reasoning

Most deep learning models employ end-to-end fashion and lack interpretability. There is some work to try to solve this problem. Zhou et al. [2018] proposes a interpretable reasoning network. Chen et al. [2019] trains a model to extract a reasoning chain and then puts the chain information to a BERT-based QA methods. Tu et al. [2019a] puts forward a RC model which jointly predicts the answer and supporting sentences. Inspired by these work, we put forward an interpretable model based on HGCN to predict relations hop-byhop under the supervision of reasoning path.

2.3 Hypergraph Convolutional Networks

Feng et al. [2019] presents a hypergraph neural networks, which applies hypergraph structure instead of general graph and encodes high order data correlation effectively. Bai et al. [2019] further enhances the ability of representation learning by using attention modules. However, existing HGCN methods are for undirected hypergraph and not suitable for the directed KG which will cause the lack of direction information.

3 Directed Hypergraph Convolutional Networks

In this section, we firstly review the hypergraph analysis theory and HGCN. Following, we introduce the proposed directed HGCN based on directed hypergraph.

3.1 Hypergraph Convolutional Networks Revisited

In Figure 2.(a) and (b), we show the form of general graph and the structure of corresponding hypergraph. Mathematically, given a hypergraph G = (V, E,W), which includes a node set V, a hyperedge set E, and a diagonal matrix W of edge weights. Different from the general graph, the hypergraph defines hyperedge that can connect more than two nodes, and focuses on the connection between nodes and hyperedges indicated by the incidence matrix H ∈ R|V|×|E| ,

learnable parameter. The features of nodes are transformed to the connected hyperedges by multiplying HT, and then aggregated from the hyperedges by multiplying H. However, the form of HGCN is for undirected hypergraph and do not consider direction information, which may lead to noise and redundancy.

3.2 Directed Hypergraph Convolutional Networks

As shown in Figure 2.(c), DHGCN first forms hyperedges feature by aggregating information from nodes that point to hyperedges, and then updates the node states from the hyperedge information that points to nodes.

4 Model

4.1 Task Definition

A knowledge graph is denoted as K = (V, E, T ), where V is the set of entities and E is the set of relations in KB. T consists of a set of triples (eh, r, et) which represent the relation r ∈ E holds between eh ∈ V and et ∈ V. Given a natural language question q = (w1, w2, ..., w|q|), where wi denotes a word in the question, the task aims to pick the answers from V. The overview of the entire model is shown in Figure 3.

4.2 Directed Hypergraph Retrieval and Construction

To retrieve the hypergraph for a L-hop question, we firstly obtain seed entities from the question by entity linking and then traverse the KG to get the entities set e = (e1, e2, ..., en) and relations set r = (r1, r2, ...rm-1) within L hops, where n and m- 1 denote the number of entities and relations. Here we add <STOP> to the relation set as the end mark of relation prediction to let the model learn when to stop reasoning.

Based on these, we figure out two incidence matrices Htail ∈ Rn×m and Hhead ∈ Rn×m. For each triple (ei1, rj , ei2), we put

4.3 Input Encoder

The input encoder encodes a natural language question and all the candidate entities and relations in hypergraph to vector representation, and applies co-attention [Zhong et al., 2019] to learn the correlation between question and entities to further enhance the query-aware entity representation.

Let Xq ∈ R|q|×d , Xe ∈ Rn×d , and Xr ∈ Rm×d be the embedding matrices of question, entities, and relations, where d denotes the embedding dimension. We firstly apply a bi-directional long short-term memory network (bi-LSTM) [Hochreiter and Schmidhuber, 1997] to encode question and obtain question hidden states Hq = biLSTM(Xq) ∈ R|q|×h . h is the hidden dimension of bi-LSTM and here we assume h = d.

Following the work of [Zhong et al., 2019], we employ co-attention to learn query-aware entity representation,

where T denotes matrix transposition, softmax() represents column-wise normalization, [; ] is column-wise concatenation, and fc is a linear network which converts 2h dimension to h dimension.

4.4 Reasoning over Hypergraph

This work proposes an interpretable two-phase hypergraph based reasoning with dynamic relations. We separate the hypergraph convolutional networks into two steps to directly learn the relation representation and further update the entity states. Specifically, the feature of nodes are firstly gathered to the connected hyperedges to learn the representation of the relations explicitly. Then the model dynamically allocates the weight of relations based on the similarity between question and relation representation and predicts the current relation. Finally, we update the node states through the connected relation information. Figure 4 depicts the structure of our proposed two-phase hypergraph based reasoning with dynamic relations.

Learn Relation Representation Explicitly

Formally, at the current hop l, let O(l) e be the input entities representation,

where E(l-1) is the node status obtained by the previous l-1 layer, E(0) = Xe, and fin is a linear network which converts 2h dimension to h dimension. The model firstly explicitly learn the relation representation O(l) r by aggregating the connected entity feature,

where Pr ∈ Rh×h is the relation specific learnable parameter. Then we concatenate R(l-1) and O(l) r and pass through a linear network fr to get representation of relations at hop l.

Allocate Relation Weights Dynamically

Co-attention is employed to learn the correlation between question and relations as the same way before to get the query-aware relation representation Rco attn. Then we apply max pooling to get weights for each relation,

and the diagonal matrix W of edge weights is

Relation weights are dynamically allocated which depend on the relation representation updated hop-by-hop. The model predicts the current relation based on relation weights.

Update Entity Adaptively

Based on dynamic relation weights, the model adaptively updates entity states by accumulating connected relation feature,

where Pe ∈ Rh×h is the entity specific learnable parameter.

4.5 Answer Prediction

For L hop question, we sum the entity representation of each layer to get the final representation and pass through a liner layer fout to predict the answer distribution.

where σ is the sigmoid function, fout converts h dimension to 1 dimension.

4.6 Loss

The training loss consists of two terms, one is binary crossentropy loss of the final answers prediction, the other is the negative log likelihood of the intermediate prediction of relations. Formally,

where y is the golden distribution over entities. r∗ l is the golden relation index at hop l. And λ is a hyper parameter to balance the two terms. Since we add <STOP> mark in, the predicted relation path number is L + 1.

5 Experiment

5.1 Datasets

PQL [Zhou et al., 2018] is a single-answer KBQA dataset, which includes a knowledge base with 5035 entities and 364 relations, and two types of questions. Specifically, PQL-2H consists of 1594 two-hop questions and PQL-3H consists of 1031 three-hop questions. The questions can be answered by walking down a reasoning path consisting of a few relations and the intermediate entities. And the paths are already given. We list two exemplars in dev datasets in Table 1.

MetaQA [Zhang et al., 2018] is a large-scale multi-answer KBQA dataset, with 116045 1-hop questions and 148724 2hop questions. The knowledge base contains 40128 entities and 9 relations. Since the dataset do not give the reasoning path, we apply a heuristic method to traverse through the graph to find the path which starts from the seed entities in question and the length is exactly equal to 2L+ 1. If the answer in it, the path is considered as golden reasoning path. We skip the cases which can not find the path.

5.2 Baselines

We compare our model with the following baselines:

KVMemNet [Miller et al., 2016] is an end-to-end memory network which divides the memory into two parts, the key memory stores the head entity and relation, and the value memory stores the tail entity.

IRN [Zhou et al., 2018] is an interpretable reasoning network that employs a hop-by-hop reasoning process for question answering based on knowledge graph.

VRN [Zhang et al., 2018] proposes an end-to-end variational learning algorithm that can effectively solve the multihop reasoning while deal with the noise in the question.

GraftNet [Sun et al., 2018] introduces text information to construct graph together with entities, and applies GCN to reasoning.

SGReader [Xiong et al., 2019] also combines the unstructured text and knowledge graph to figure out the incompleteness of knowledge graph. The model employs graph attention to reason effectively.

For GraftNet and SGreader, we use full KB setting and no documents here.

5.3 Implementation Details

Throughout our experiments, we apply 768 dimensional BERT embedding [Devlin et al., 2019] for query words and relations, and 400 dimensional TransE embedding [Bordes et al., 2013] for entities. The hidden size of LSTM and directed hypergraph convolutional networks are all set to 400. During training, the Adam optimizer [Kingma and Ba, 2015] is employed to minimize the loss with a learning rate of 1e-4 . λ and dropout are set to 1 and 0.4. We set original relation path with end mark <STOP> as golden relation path. The layer of reasoning is set to L+1. For testing, the hop of question is unknown, the model predicts relation hop-by-hop and stops when the current relation meets end mask.

5.4 Results

Main Results and Analysis

We employ Hits@1 and F1 to measure the performance of the models. For PQL dataset, there is one answer for each question, so we only adopt Hits@1 for evaluation. As shown in Table 2, our method achieves best Hits@1 compared with the baseline models on PQL dataset. Specifically, 2HRDR achieves a great improvement on PQL-2H, which is 3% higher than the second best model. It also obtains good result on PQL-3H, 1.1% higher than the second best one. Table 3 demonstrates the performance of the baseline methods and our model on the metaQA dataset. Our model outperforms all the baselines on metaQA1-Hop, improving Hits@1 and F1 by 1.8% and 1.3% respectively. And for metaQA2Hop, we obtain competitive Hits@1 and improve F1 from 79.8% to 81.4%. The reasons why our method performs well include: 1) The model reconstructs the knowledge graph to hypergraph structure and applies directed hypergraph convolutional networks to reason over it, which fully consider the high-order data correlation. 2) We dynamically concentrate on relation information at different hops to guide the model to follow the golden relation path and select the final answers. 3) The information of intermediate reasoning path is introduced into our model to supervise the model focus on the dynamic relations at different hops.

To illustrate the model's ability to predict relational path, we also define the relational EM. If the output relation path and the golden relation path are completely identical, this case is counted as an exact match, and the relation EM is set to 1. Otherwise, the relation EM is 0. We average all cases to obtain the final value. AvgRelation denotes the average number of relations in the subgraph of each question. The experimental results are shown in Table 5 which achieve a promising performance on sequential relation prediction even we adopt a strict metric.

Ablation Study on Model Components

We compare our model with a few variants. As shown in the first three rows of Table 4, the first model r-GCN only applies r-GCN [Schlichtkrull et al., 2018] to reason over knowledge graph, where adding skip connection and gate mechanism. The second model HGCN and the third DirectedHGCN apply HGCN and DHGN with the same setting. HGCN outperforms the r-GCN which shows the superiority of HGCN to represent high-order relation among data. Moreover, HGCN requires less parameters than r-GCN. DirectedHGCN achieves higher performance than HGCN, illustrating the effectiveness of our proposed DHGCN in reducing the effects of noise by direction information.

To evaluate the performance of different components in our model, we also perform ablation study. 2HR-DR w/o sequential relation prediction predicts all relations by the final relations states which do not consider the sequential order. 2HR-DR w/o relation prediction does not consider the relation loss part. 2HR-DR w/o dynamic relations assigns static relation weights according to the similarity between relations and query. And 2HR-DR w/o relation weights represents our proposed two phase reasoning network without relation weights. The above two methods do not consider relation prediction. The experimental results prove the validity of each component. Shown in Table 4, compared 2HR-DR w/o relation weights with 2HR-DR w/o dynamic relations, we can see relation information is vital for reasoning and our proposed dynamic relation significantly improves performance by focusing different relations at different hops. By comparing 2HR-DR w/o relation prediction and 2HR-DR w/o sequential relation prediction, the results illustrate the significance of relation path to guide the model to reason hop-by-hop.

Case Study on Interpretibility

As Figure 5 shows, we give an exemplar question from PQL3H and its corresponding reasoning path and triples in KB, and plot the attention heatmap of relations' probability distribution at each hop to illustrate dynamic relations of our model. It is clear that 2HR-DR has the ability to predict relations hop-by-hop and stop reasoning automatically. For question "what is the release of recording of amsterdam's artist?", the model firstly detects relation "Artist", then "Recording" and "Release" successively, finally meets <STOP> to end the reasoning process. From the visualization of heatmap, we can observe our model's predicted relation path (Artist → Recording → Release → <STOP>).

6 Conclusion

This paper proposes a QA model based on hypergraph convolutional networks. We expand the HGCN to directed hypergraph and propose the directed-HGCN. In order to imitate humans' hop-by-hop reasoning, we further propose the twophase hypergraph based reasoning with dynamic relations to firstly update the relation states and assign dynamic weights for relations, then learn the node representation adaptively. Meantime, we predict the relation at each hop and form a sequential relation path to make the model interpretable. Experimental results prove the effectiveness of the model.

Acknowledgements

This work is supported by the National Key Research and Development Program of China under grant 2018YFB1003804, in part by the National Natural Science Foundation of China under grant 61921003, 61972043. Bo Cheng is the corresponding author.