Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

By Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, Andrew McCallum. 2017

615 citations recorded by the source corpus.

Knowledge bases (KB), both automatically and manually constructed, are often incomplete --- many valid facts can be inferred from the KB by synthesizing existing information. A popular approach to KB completion is to infer new relations by combinatory reasoning over the information found along other paths connecting a pair of entities. Given the enormous size of KBs and the exponential number of paths, previous path-based models have considered only the problem of predicting a missing relation given two entities or evaluating the truth of a proposed triple. Additionally, these methods have traditionally used random paths between fixed entity pairs or more recently learned to pick paths between them. We propose a new algorithm MINERVA, which addresses the much more difficult and practical task of answering questions where the relation is known, but only one entity. Since random walks are impractical in a setting with combinatorially many destinations from a start node, we present a neural reinforcement learning approach which learns how to navigate the graph conditioned on the input query to find predictive paths. Empirically, this approach obtains state-of-the-art results on several datasets, significantly outperforming prior methods.

Subfields: Artificial Intelligence, Information Retrieval & Search, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Retrieval & Search

In Reinforcement Learning

Citations in the corpus

Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering (2019, background): “, 2016) for question answering in text and knowledge bases (Das et al., 2017; Yang et al., 2017; Das et al., 2018).”
Neural Approaches to Conversational AI (2018, neutral): “, 2017), MINERVA (Das et al., 2017b) and M-Walk (Shen et al.”
NLProlog: Reasoning with Weak Unification for Question Answering in Natural Language (2019, background): “An area in which neural multi-hop reasoning models have been investigated is Knowledge Base Completion (KBC) (Das et al., 2016; Cohen, 2016; Neelakantan et al., 2015; Rocktäschel and Riedel, 2017; Das et al., 2017; Evans and Grefenstette, 2018).”
Multi-hop Reading Comprehension across Documents with Path-based Graph Convolutional Network (2020, methodology): “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.”
Deep Graph Library: Towards Efficient and Scalable Deep Learning on Graphs (2019, background): “…traversal order (Tai et al., 2015; Jin et al., 2018); • random walk (Ying et al., 2018a; Hamilton et al., 2017); • active sets that are generated dynamically, including exploration algorithms on graph navigation (Nogueira & Cho, 2016; Das et al., 2017) and graph generative models (Li et al., 2018).”
Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text (2018, methodology): “We report baselines for future comparison, including Key Value Memory Networks (Miller et al., 2016; Das et al., 2017c), and show that our proposed GRAFT-Nets have superior performance across a wide range of conditions ( § 5).”
WorldTree V2: A Corpus of Science-Domain Structured Explanations and Inference Patterns supporting Multi-Hop Inference (2020, background): “As a result, most multihop inference models are generally unable to demonstrate combining more than 2 or 3 facts to perform an inference (Khashabi et al., 2016; Jansen et al., 2017; Das et al., 2017), and even then only infrequently.”
A Survey on Knowledge Graphs: Representation, Acquisition, and Applications (2020, methodology): “With source, query and current entity denoted as e s , e q and e t , and query relation denoted as r q , the MDP environment and policy networks of these methods are summarized in Table III, where MINERVA, M-Walk and CPL use binary reward.”
Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction (2021, background): “Another stream of works [64, 10, 22] learns an agent to collect useful paths for link prediction.”
Knowledge Aware Conversation Generation with Explainable Reasoning over Augmented Graphs (2019, methodology): “We implement our knowledge selection model based on the code 7 by(Das et al., 2018) and that 4 by (Moghe et al., 2018).”
Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals (2021, positive): “[3, 22] conducted multi-hop reasoning on a graph under the reinforcement learning setting and treated every reasoning step as an edge transition on the graph.”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, background): “While the idea of random walks has been also used for reasoning over KGs [132, 52], the use of random walks for representation learning on KGs has not yet been explored much.”
A Survey of Knowledge-enhanced Text Generation (2020, background): “icable in many real-world QA and dialogue scenarios. Recent RL based knowledge graph reasoning methods have demonstrated appealing performances on non-generative QA scenarios such as answer retrieval [32] and reading comprehension [116]. Leveraging RL based path finding for NLG tasks typically consi”
Embedding Logical Queries on Knowledge Graphs (2018, background): “However, existing work in this area primarily focuses on using logical reasoning to improve edge prediction in knowledge graphs [14, 13, 27], for example, by using logical rules as regularization [15, 20, 35, 37].”
Survey on reinforcement learning for language processing (2021, background): “2017), MINERVA (Das et al.”
On-The-Fly Information Retrieval Augmentation for Language Models (2020, background): “…demonstrated for NLP tasks such as natural language inference (Chen et al., 2018; Yang et al., 2019), language generation (Parthasarathi and Pineau, 2018), knowledge base completion (Toutanova et al., 2015; Das et al., 2017) and question answering (Sun et al., 2019, 2018; Dhingra et al., 2017).”
Deep Learning on Graphs: A Survey (2018, neutral): “DeepPath [120] and MINERVA [121] both adopted RL for knowledge graph (KG) reasoning.”