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

Abstract

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.

ICLR 2018

References in corpus (8)

• Adam: A Method for Stochastic Optimization
• End-To-End Memory Networks
• ReasoNet: Learning to Stop Reading in Machine Comprehension
• Probabilistic Similarity Logic
• Reinforcement Learning Neural Turing Machines - Revised
• Learning to Search Better Than Your Teacher
• TensorLog: A Differentiable Deductive Database
• End-to-End Goal-Driven Web Navigation

Cited by in corpus (83)

• A Survey on Knowledge Graphs: Representation, Acquisition and Applications
• Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks
• A Survey of Knowledge-Enhanced Text Generation
• Hypernetwork Knowledge Graph Embeddings
• Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals
• Deep Learning on Graphs: A Survey
• Survey on reinforcement learning for language processing
• Knowledge Graph Reasoning with Relational Digraph
• On the Explainability of Natural Language Processing Deep Models
• Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction
• Probabilistic Logic Neural Networks for Reasoning
• RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs
• Time-aware Path Reasoning on Knowledge Graph for Recommendation
• Representation Learning for Dynamic Graphs: A Survey
• Relation Embedding with Dihedral Group in Knowledge Graph
• Neurosymbolic Reinforcement Learning and Planning: A Survey
• UHop: An Unrestricted-Hop Relation Extraction Framework for Knowledge-Based Question Answering
• Reinforcement Learning from Reformulations in Conversational Question Answering over Knowledge Graphs
• Multi-Hop Knowledge Graph Reasoning with Reward Shaping
• PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text
• Interpretable Graph Convolutional Neural Networks for Inference on Noisy Knowledge Graphs
• Multi-relational Poincaré Graph Embeddings
• Adapting Meta Knowledge Graph Information for Multi-Hop Reasoning over Few-Shot Relations
• Temporal Knowledge Graph Forecasting with Neural ODE
• A Survey on Semantic Parsing
• Iteratively Learning Embeddings and Rules for Knowledge Graph Reasoning
• Variational Knowledge Graph Reasoning
• xERTE: Explainable Reasoning on Temporal Knowledge Graphs for Forecasting Future Links
• Enhancing Text-based Reinforcement Learning Agents with Commonsense Knowledge
• Scalable Neural Methods for Reasoning With a Symbolic Knowledge Base
• One-Shot Relational Learning for Knowledge Graphs
• DOLORES: Deep Contextualized Knowledge Graph Embeddings
• EvoPath: Evolutionary Meta-path Discovery with Large Language Models for Complex Heterogeneous Information Networks
• Learning Representations of Bi-level Knowledge Graphs for Reasoning beyond Link Prediction
• Realistic Re-evaluation of Knowledge Graph Completion Methods: An Experimental Study
• Dynamically Pruned Message Passing Networks for Large-Scale Knowledge Graph Reasoning
• Knowledge Aware Conversation Generation with Explainable Reasoning over Augmented Graphs
• Reasoning over RDF Knowledge Bases using Deep Learning
• Open Domain Question Answering Using Early Fusion of Knowledge Bases and Text
• Learn to Explain Efficiently via Neural Logic Inductive Learning
• Meta Reasoning over Knowledge Graphs
• Logic Embeddings for Complex Query Answering
• Link Prediction using Embedded Knowledge Graphs
• Modeling Attention Flow on Graphs
• Reasoning on Knowledge Graphs with Debate Dynamics
• Dynamic Anticipation and Completion for Multi-Hop Reasoning over Sparse Knowledge Graph
• Learning Collaborative Agents with Rule Guidance for Knowledge Graph Reasoning
• Language Generation with Multi-Hop Reasoning on Commonsense Knowledge Graph
• Collaborative Policy Learning for Open Knowledge Graph Reasoning
• Rethinking Dialogue State Tracking with Reasoning
• Learning to Search in Long Documents Using Document Structure
• Learning Graph Structure With A Finite-State Automaton Layer
• Simple Augmentations of Logical Rules for Neuro-Symbolic Knowledge Graph Completion
• Search from History and Reason for Future: Two-stage Reasoning on Temporal Knowledge Graphs
• Cooperative Reasoning on Knowledge Graph and Corpus: A Multi-agentReinforcement Learning Approach
• Learning to Recover Reasoning Chains for Multi-Hop Question Answering via Cooperative Games
• Multi-hop Reading Comprehension across Documents with Path-based Graph Convolutional Network
• NLProlog: Reasoning with Weak Unification for Question Answering in Natural Language
• Cyberswarm: a novel swarm intelligence algorithm inspired by cyber community dynamics
• Embedding Uncertain Knowledge Graphs
• Neural Consciousness Flow
• Knowledge Efficient Deep Learning for Natural Language Processing
• TimeTraveler: Reinforcement Learning for Temporal Knowledge Graph Forecasting
• Completion Reasoning Emulation for the Description Logic EL+
• Explainable Biomedical Recommendations via Reinforcement Learning Reasoning on Knowledge Graphs
• On-The-Fly Information Retrieval Augmentation for Language Models
• Combining Rules and Embeddings via Neuro-Symbolic AI for Knowledge Base Completion
• MCMH: Learning Multi-Chain Multi-Hop Rules for Knowledge Graph Reasoning
• DyKgChat: Benchmarking Dialogue Generation Grounding on Dynamic Knowledge Graphs
• Reasoning Over Paths via Knowledge Base Completion
• Learning to Order Sub-questions for Complex Question Answering
• Is Multi-Hop Reasoning Really Explainable? Towards Benchmarking Reasoning Interpretability
• SQALER: Scaling Question Answering by Decoupling Multi-Hop and Logical Reasoning
• Differentiable Representations For Multihop Inference Rules
• A Knowledge Enhanced Learning and Semantic Composition Model for Multi-Claim Fact Checking
• Path Ranking with Attention to Type Hierarchies
• Reinforcement Learning based Path Exploration for Sequential Explainable Recommendation
• Are Missing Links Predictable? An Inferential Benchmark for Knowledge Graph Completion
• Navigation-Based Candidate Expansion and Pretrained Language Models for Citation Recommendation
• Knowledge Graph Completion with Text-aided Regularization
• Scalable and interpretable rule-based link prediction for large heterogeneous knowledge graphs
• Learning When Not to Answer: A Ternary Reward Structure for Reinforcement Learning based Question Answering
• EM-RBR: a reinforced framework for knowledge graph completion from reasoning perspective