R ea R ev: Adaptive Reasoning for Question Answering over Knowledge Graphs (2022)

Abstract: Knowledge Graph Question Answering (KGQA) involves retrieving entities as answers from a Knowledge Graph (KG) using natural language queries. The challenge is to learn to reason over question-relevant KG facts that traverse KG entities and lead to the question answers. To facilitate reasoning, the question is decoded into instructions, which are dense question representations used to guide the KG traversals. However, if the derived instructions do not exactly match the underlying KG information, they may lead to reasoning under irrelevant context.Our method, termed ReaRev, introduces a new way to KGQA reasoning with respectto both instruction decoding and execution. To improve instruction decoding, we perform reasoning in an adaptive manner, where KG-aware information is used to iteratively update the initial instructions. To improve instruction execution, we emulate breadth-first search (BFS) with graph neural networks (GNNs). The BFS strategy treats the instructions as a set and allows our method to decide on their execution order on the fly. Experimental results on three KGQA benchmarks demonstrate the ReaRev’s effectiveness compared with previous state-of-the-art, especially when the KG is incomplete or when we tackle complex questions. Our code is publicly available at https://github.com/cmavro/ReaRev_KGQA.

## introduction a knowledge graph (kg) is a relational graph that contains a set of known facts. these facts are represented as tuples @xcite , where the subject and object are kg entities that link with the given relation. the knowledge graph questionanswering (kgqa) task takes as input a natural language question and returns a set of kg entities as the answer. in the weakly-supervised kgqa setting @xcite , the only available supervisions during learning are question-answer pulp fiction q. tarantino kill bill q: "which year are q.tarantino's movies directed?" a: 2003, 1994 kg links 2003 direct 1963 date date 1994 cast aired on act u.thurman correct kg traversals instruction decoding i (1) , i (2) direct execution i (1) -→ i (2) ✗ : tarantino date --→ ✗ execution i (2) -→ i (1) ✓ : tarantino direct ---→kill bill date --→2003 ✓ decoding ✗: tarantino direct ---→ aired on the kgqa problem involves two modules: (i) retrieving question-relevant kg facts, and (ii) reasoning over them to arrive at the answers. for the reasoning module, a general approach @xcite is to decode the question into dense representations (instructions) that guide the reasoning over the kg. the instructions are matched with one-hop kg facts (or relations) in an iterative manner, which induces kg traversals that lead to the answers. instructions are usually generated by attending to different question's parts, e.g., "...is the director..." @xcite . kg traversals are typically performed by utilizing powerful graph reasoners, such as graph neural networks (gnns) @xcite . the main challenge is that question answering is performed over rich graph structures with possibly complex semantics, and thus, instruction decoding and execution is a key factor for kgqa. figure 1 shows an example where suboptimal initial instructions lead to incorrect kg traversals. while some methods @xcite @xcite attempt to improve the quality of the instructions, they are mainly designed to tackle specific question types, such as 2-hop or 3-hop questions, or show poor performance for complex questions @xcite . our method termed rearev (reason & revise) introduces a new way to kgqa reasoning with respect to both instruction execution and decoding. to improve instruction execution, we do not use instructions in a pre-defined (possibly incorrect) order, but allow our method to decide on the execution order on the fly. we achieve this by emulating breadth-first search (bfs) with gnn reasoners. the bfs strategy treats the instructions as a set and the gnn decides which instructions to accept. to improve instruction decoding, we reason over the kg to obtain kg-aware information and use this information to adapt the initial instructions. then, we restart the reasoning with the new instructions that are conditioned to the underlying kg semantics. to the best of our knowledge, adaptive reasoning with emulating graph search algorithms with gnns has not been previously proposed for kgqa. we empirically show that rearev performs effective reasoning over kgs and outperforms other state-of-the-art. for kgqa with complex questions, rearev achieves improvement for 4.1 percentage points at hits@1 over the best competing approach. our contributions are summarized below: ## related work there are two mainstream approaches to solve kgqa: (i) parsing the question to executable kg queries like sparql, and (ii) grounding question and kg representations to a common space for reasoning. regarding the first case, early methods @xcite @xcite rely on pre-defined question templates to synthesize queries, which requires strong domain knowledge. recent methods @xcite @xcite @xcite @xcite @xcite use deep learning techniques to automatically generate such executable queries. however, they need ground-truth executable queries as supervisions (which are costly to obtain) and their performance is limited when the kg has missing links (nonexecutable queries). methods in the second category alleviate the need for ground-truth queries by learning natural language and kg representations to reason in a common space. these methods match question representations to kg facts @xcite @xcite or to kg structure representations @xcite @xcite . more related to our work, graftnet @xcite , pullnet @xcite , and nsm @xcite enhance the reasoning with graph-based reasoners. our approach aims at improving the graph-based reasoning via adaptive instruction decoding and execution. researchers have also considered the problem of performing kgqa over incomplete graphs @xcite , where important information is missing. these methods either rely on kg embeddings @xcite or on side information, such as text corpus @xcite @xcite , to infer missing information. however, they offer marginal improvement over other methods when the kg is mostly complete. kgqa has also been adapted to specific domains, such as qa over temporal @xcite and commonsense @xcite @xcite @xcite kgs. ## background 3.1 kg a kg g := (v, r, f) contains a set of entities v, a set of relations r, and a set of facts f. each fact (v, r, v ′ ) ∈ f is a tuple where v, v ′ ∈ v denote the subject and object entities, respectively, and @xmath0. a kg is represented as a directed graph with |r| relation types, where nodes v and v ′ connect with a directed relation r if (v, r, v ′ ) ∈ f. nodes and relations are usually initialized with d-dimensional vectors (representations). we denote h @xmath1, respectively. we denote n e (v) and n r (v) the set of node v's neighboring entities and relations (including selflinks), respectively. for example, v ′ ∈ n e (v) and @xmath2, r, v) exists. we use the terms nodes and entities interchangeably. ## rearev approach rearev (reason & revise) enhances instruction decoding and execution for effective kgqa reasoning. our contributions across these two dimensions are described below. question: "which are ...?" k) ... ## experimental setup we experiment with three widely used kgqa benchmarks: webquestionssp (webqsp) @xcite , complex webquestions 1.1 (cwq) @xcite , and metaqa-3 @xcite . we provide the final dataset statistics (see section 5.2) in appendix. ## conclusion our method (rearev) introduces a new way to kgqa reasoning with respect to instruction execution and decoding. we improve instruction decoding via adaptive reasoning, which updates the instructions with kg-aware information. we improve instruction execution by emulating the breadth-first search algorithm, which provides robustness to the initial instruction ordering. experimental results on three kgqa benchmarks demonstrate the rearev 's effectiveness compared with previous state-of-the-art, especially when the kg is incomplete or when we tackle complex questions.