Source-linked AI summary
DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning
Wenhan Xiong, Thien Hoang, William Yang Wang
TL;DR
The paper addresses how to learn multi-hop reasoning paths in large knowledge graphs. It trains a reinforcement-learning agent with embedding-based continuous states and a reward balancing accuracy, diversity, and efficiency. The method generally outperforms path-based and embedding baselines on two standard reasoning tasks, while the authors identify sparse reasoning paths as a problematic scenario for future work.
Problem
DeepPath studies how machines can learn to reason over large knowledge graphs and infer unknown answers through multi-hop relational paths.
Method
The method frames path learning as reinforcement learning, using embedding-based continuous states, relation-sampling actions, and rewards that jointly consider accuracy, diversity, and efficiency.
Results
DeepPath generally outperforms two classes of baselines on two standard reasoning tasks using reinforcement-learned paths as reasoning formulas.
Takeaways & Limitations
The learned paths can serve as an alternative to PRA in path-based reasoning methods while allowing control over path properties.
Takeaways & Limitations
The framework faces a problematic scenario when the knowledge graph does not contain enough reasoning paths.
Abstract
from arXiv · showhide
We study the problem of learning to reason in large scale knowledge graphs (KGs). More specifically, we describe a novel reinforcement learning framework for learning multi-hop relational paths: we use a policy-based agent with continuous states based on knowledge graph embeddings, which reasons in a KG vector space by sampling the most promising relation to extend its path. In contrast to prior work, our approach includes a reward function that takes the accuracy, diversity, and efficiency into consideration. Experimentally, we show that our proposed method outperforms a path-ranking based algorithm and knowledge graph embedding methods on Freebase and Never-Ending Language Learning datasets.
1 Introduction
DeepPath frames multi-hop knowledge-graph reasoning as reinforcement learning, using continuous embedding-based states and a reward that balances accuracy, diversity, and efficiency. The method is presented as scalable and outperforming PRA and knowledge-graph embedding methods on two datasets.
- Multi-hop reasoning requires machines to infer unknown answers from existing knowledge-graph resources.
- DeepPath formulates relational-path learning as reinforcement learning for controllable multi-hop reasoning.
- Embedding-based continuous states let the agent reason in the knowledge-graph vector space while sampling relations to extend paths.
- The reward function jointly considers accuracy, efficiency, and path diversity to provide greater control over path finding.
- DeepPath scales to large knowledge graphs and outperforms PRA and knowledge-graph embedding methods on two tasks.
2 Related Work
Prior knowledge-graph reasoning methods use random walks, neural models, or embeddings, but several face discrete-space, parsing, scalability, or search bottlenecks. DeepPath instead reasons in continuous space and uses reinforcement learning to find relational paths with more controllable path selection.
- PRA learns inference paths through random walks with restarts, bounded searches, and supervised path selection.
- Several neural approaches have limitations including parse-error propagation, excessive model training, and reliance on PRA paths.
- DeepPath differs from PRA by reasoning in continuous space and incorporating multiple reward criteria for path-finding control.
- Neural symbolic machine also uses reinforcement learning, but composes token-based programs for question answering rather than finding knowledge-graph reasoning paths.
3 Methodology
DeepPath formulates multi-hop relation reasoning as sequential decision making in an MDP, using a policy-based agent with embedding-based continuous states to select path-extending relations. Training combines supervised paths, policy-gradient updates, and rewards for accuracy, efficiency, and diversity.
- Reinforcement Learning for Relation Reasoning: The KG environment is modeled as an MDP, and the agent learns to select promising relations sequentially until reaching a target entity.The policy network maps states to a stochastic distribution over KG relations, while episodes are bounded by a maximum path length.
- States: Entity and relation symbols are represented with translation-based embeddings, giving the agent continuous states based on the current and target entities.The state uses the current entity embedding and the target entity embedding; the reasoning relation is omitted because its embedding remains constant during path finding.
- Rewards: The reward design jointly considers global accuracy, path efficiency, and path diversity to control the quality and variety of learned reasoning paths.Successful target-reaching sequences receive positive accuracy reward, shorter paths receive higher efficiency reward, and diversity is based on cosine similarity with existing paths.
- Policy Network: A fully connected policy network with ReLU hidden layers and a softmax output maps each state to probabilities over all possible actions.Policy-based reinforcement learning is used because the KG action space can contain hundreds or thousands of relations, creating convergence challenges for direct trial-and-error training.
- Training Pipeline: Training first uses BFS-derived positive paths for supervised policy learning, then retrains the policy with the defined rewards using policy-gradient updates.Random intermediate nodes are introduced during BFS to reduce its short-path bias, and subsequent episodes update the policy from accumulated rewards.
4 Experiments
Experiments evaluate the RL model on two knowledge-graph datasets and two reasoning tasks against path-based and embedding-based baselines. The model achieves stronger overall MAP, extracts compact reasoning paths, and uses supervised training to address the large action space.
- Dataset and Settings: The experiments evaluate link prediction and fact prediction on FB15K-237 and a NELL subset, comparing RL with PRA and several embedding methods.The datasets contain reasoning tasks across domains, with target relations removed from the knowledge graph before train/test construction.
- Baselines and Implementation Details: The RL model uses TransE representations, a 200-dimensional state vector, and a linear-regression-style path reranking procedure.The implementation also trains separate embedding baselines for each reasoning task.
- Qualitative Analysis of Reasoning Paths: The RL model uses fewer reasoning paths than PRA while achieving better MAP, indicating that its reward functions select strong paths and filter similar or irrelevant ones.The analysis links shorter, predictive paths to the effectiveness of the RL model and examines path-length distributions across the datasets.
- Quantitative Results: The RL approach significantly outperforms path-based and embedding methods in overall MAP on both datasets for link prediction.PRA is omitted from the detailed fact-prediction baseline comparison because its implementation ranks target entities rather than all triples.
- Quantitative Results: The RL model performs even better on fact prediction and beats all embedding baselines on most reasoning tasks.The authors report better performance on NELL, where they observe more short paths and synonym-like reasoning relations than in FB15K-237.
- Effect of Supervised Learning: Supervised training is applied before reward retraining to address the large action space, and success ratio within 10 steps is measured across training episodes.Correct paths linking sampled training entity pairs receive a +1 global reward; the confidence band uses 50 runs.
5 Conclusion and Future Work
The paper presents reinforcement learning as a controllable framework for finding reasoning paths in knowledge graphs and reports generally stronger performance than two baseline classes on two standard reasoning tasks. It identifies sparse reasoning paths as a setting motivating future integration of knowledge-graph triples with text mentions.
- The reinforcement learning framework trains an agent to find reasoning paths that can serve as formulas for knowledge-graph reasoning.Unlike random-walk path-finding models, the framework allows control over the properties of the paths it finds.
- Using the learned RL paths as reasoning formulas, the approach generally outperforms two classes of baselines on two standard reasoning tasks.
- Future Work: Future work will investigate adversarially learned rewards instead of the human-defined reward functions used in this study.The proposed direction is intended to provide better rewards than manually designed functions based on path characteristics.
- Future Work: The authors also plan to address cases with insufficient reasoning paths by jointly reasoning over knowledge-graph triples and text mentions.