Fact-Tree Reasoning for N-ary Question Answering over Knowledge Graphs (2022)

Abstract: Current Question Answering over Knowledge Graphs (KGQA) task mainly focuses on performing answer reasoning upon KGs with binary facts. However, it neglects the n-ary facts, which contain more than two entities. In this work, we highlight a more challenging but under-explored task: n-ary KGQA, i.e., answering n-ary facts questions upon n-ary KGs. Nevertheless, the multi-hop reasoning framework popular in binary KGQA task is not directly applicable on n-ary KGQA. We propose two feasible improvements: 1) upgrade the basic reasoning unit from entity or relation to fact, and 2) upgrade the reasoning structure from chain to tree. Therefore, we propose a novel fact-tree reasoning framework, FacTree, which integrates the above two upgrades. FacTree transforms the question into a fact tree and performs iterative fact reasoning on the fact tree to infer the correct answer. Experimental results on the n-ary KGQA dataset we constructed and two binary KGQA benchmarks demonstrate the effectiveness of FacTree compared with state-of-the-art methods.

## introduction the task of question answering over knowledge graphs (kgqa) has provided new avenues to the recent development of qa systems by utilizing the advantages of kgs @xcite @xcite . current kgqa studies mainly consider performing answer reasoning upon kgs with binary facts, which encode binary relations between pairs of entities, e.g., golden state warriors' arena is chase center 1 . however, n-ary facts that involve more than two entities are also ubiquitous in reality @xcite @xcite , e.g., the ternary fact golden state warriors won the nba championship in 2018. compared to binary facts, n-ary facts have more information content. this makes the answer reasoning for questions involving n-ary facts more intractable, exposing open challenges in kgqa. in this work, we aim to study the under-explored n-ary kgqa task, i.e., answering n-ary facts questions upon n-ary kgs. the multi-hop reasoning kgqa method @xcite @xcite has become popular for its high efficiency and interpretability. specifically, the reasoning process can be expressed as a chain, starting from an entity extracted from the question and then walking on the kg by connected relations and entities until arriving at the answer entity. see figure 1 (b) for an example, to answer the question, what is the address of the arena of the golden state warriors, the reasoning chain starts from golden state warriors, to walk through "@xmath0, and it ends at 1 warriors way, i.e., the answer. multi-hop reasoning has been studied widely on the binary kgqa task. here, we first try to execute it on the n-ary kgqa task. however, we find that multi-hop reasoning is not directly applicable on n-ary kgqa. we take the n-ary facts question in figure 1 (c) as an example to explain. first, the essence of multi-hop reasoning is to construct a reasoning chain by treating the relation as the translation between two entities @xcite , naturally in a linear structure. however, the transition from binary to n-ary facts is similar to the transition from a line to a plane. for a single n-ary fact (e.g., golden state warriors won the nba championship in 2018), the reasoning chain could only include two entities golden state warriors and nba championship and a relation win involving them, leading to the possible loss of important information 2018. to overcome where the correct answer is marked by a star. the multi-hop reasoning method can be used to answer q1, and the reasoning process can be visualized as a chain (b). however, for the more complex q2, the multi-hop reasoning method is not applicable. we use fact as the basic reasoning unit to construct the reasoning process. as shown in (c), the reasoning process can be visualized as a fact tree: fact 2 and fact 3 are leaf nodes need to be inferred first, and then the two inferred entities (los angeles lakers and 2018) are transmitted to the root node (fact 1). finally the root node infers the answer entity (lebron james). nevertheless, multi-hop reasoning would still be less capable in more complex reasoning scenarios where a question involves multiple n-ary facts. for example, the question in figure 1 (c ) is composed of three facts. when using fact as the basic reasoning unit, the whole reasoning process can be represented as a tree structure, where nodes represent facts and edges reflect the reasoning order. specifically, in the fact tree, the entities (los angeles lakers and 2018) which are missing in the two leaf nodes (fact 2 and fact 3) are first inferred and then passed to the root node (fact 1). the root node can then finally infer the correct answer entity lebron james. obviously, the chain structure used in the multi-hop reasoning framework is evidently insufficient to cope with the tree structure. therefore, to improve the ability to cope with more complex reasoning scenarios, we propose that upgrading the reasoning structure from chian to tree. in this work, we propose a novel fact-tree reasoning framework, namely, factree, which integrates the above two upgrades and pipelines the answer reasoning process into three steps: 1) fact tree construction, which transforms an input natural language (nl) question into an nl fact tree; 2) fact location, which locates the nl fact onto the kg; and 3) fact reasoning, which iterates intra-fact and inter-fact reasoning to infer the answer. during the intra-fact reasoning, the n-ary kg embedding model @xcite is plugged in to alleviate the deficiency of kg incompleteness. the explicit tree reasoning structure makes the results strongly interpretable. furthermore, we develop a new dataset called wikipeopleqa to foster research on n-ary kgqa. we then conduct comprehensive experiments on wikipeopleqa dataset to show that factree has the desired ability to perform effective reasoning on n-ary fact questions. besides, on two binary kgqa datasets, factree also indicates a strong ability to infer answers compared with state-of-the-art methods accurately. our study fundamentally contributes to bridging the gap between binary kgqa and n-ary kgqa. the proposed factree can serve as a preliminary foundation for the n-ary kgqa. to summarize, our contributions are: ## related work the previous series of kgqa models @xcite @xcite @xcite synthesize a structured query graph from the question and then match the query with kg to get the answer. this type of model has high interpretability but is challenged by the incomplete nature of kgs. then another series models compute the semantic similarity of the question and each candidate answer directly in the latent space @xcite @xcite . this type of model overcomes the limitation of incomplete kg, but lacks sufficient interpretability. factree uses facts as the basic reasoning unit to alleviate the deficiency of kg incompleteness and the explicit tree reasoning structure to realize strongly interpretable. multi-hop reasoning framework has attracted widespread attention due to its high flexibility and high interpretability in recent years @xcite . current efforts build an explicit reasoning chain through training a reinforcement learning agent to walk on the kg @xcite @xcite , or construct implicit reasoning chains through memory network @xcite @xcite or in the latent space @xcite @xcite @xcite . this kind of method performs well on binary fact questions but has difficulties in dealing with n-ary fact questions. of course, one could construct and synthesize multiple reasoning chains to tackle n-ary kgqa. but this would inevitably lead to an exponential increase in the reasoning difficulty and computational complexity, which in turn affects the reasoning performance. our work first highlights the n-ary kgqa task. the research of n-ary kg provides a feasible research foundation for n-ary kgqa. kg embedding learning on n-ary facts @xcite @xcite @xcite has grown considerably in recent years. the n-ary kg embedding model @xcite is plugged in factree to alleviate the reasoning difficulties caused by the kg incompleteness. ## fact-tree reasoning we illustrate the fact-tree reasoning framework for n-ary kgqa in figure 2 . it takes the question (q) as an input, passes through a three-stage pipeline processing, and finally gets the answer entity (a). in the first fact tree construction stage, we construct the nl fact tree from the nl question (sec. 3.1). in the second fact location stage, we locate the nl fact onto the kg to obtain the kg fact tree (sec. 3.2). this helps to bridge the semantic and structure gap between the unstructured nl and the structured kg. in the last fact reasoning stage, we perform intra-fact and inter-fact reasoning iteratively on the kg fact tree to infer the answer entity (sec. 3.3). we use fact as the basic reasoning unit in the fact-tree reasoning framework. in the nl fact tree, the fact is represented as a sequence of words and placeholders, where the words are taken from the nl question, and the placeholders refer to the missing entities to be inferred, e.g., the fact (2 joined 2 in the year 2). in the kg fact tree, following @xcite , we represent the n-ary fact as ## conclusion this work highlights a more challenging task: nary kgqa, and it advocates that the multi-hop reasoning framework popular in binary kgqa is no longer applicable to n-ary kgqa. a novel fact-tree reasoning framework factree is proposed, which pipelines the n-ary kgqa into three steps: fact tree construction, fact location, and fact reasoning to infer the correct answer. the quantitative and qualitative experimental results have demonstrated that factree has superior reasoning ability on n-ary and binary fact questions. elimination process does not involve the leaf nodes and their parents nodes (line 6-10).