# Multi-Hop Knowledge Graph Reasoning with Reward Shaping

arXiv: https://arxiv.org/abs/1808.10568 · HTML: https://mlsanity.com/paper/1808.10568/

## Key facts

- Cited by 102 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Aug 2018.

## Built on by (most cited first, 30 of 102)

- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal](https://mlsanity.com/paper/2212.05767/) (2022)
- [Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals](https://mlsanity.com/paper/2101.03737/) (2021)
- [ConE: Cone Embeddings for Multi-Hop Reasoning over Knowledge Graphs](https://mlsanity.com/paper/2110.13715/) (2021)
- [TimeTraveler: Reinforcement Learning for Temporal Knowledge Graph Forecasting](https://mlsanity.com/paper/2109.04101/) (2021)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Search from History and Reason for Future: Two-stage Reasoning on Temporal Knowledge Graphs](https://mlsanity.com/paper/2106.00327/) (2021)
- [Neural Graph Reasoning: Complex Logical Query Answering Meets Graph Databases](https://mlsanity.com/paper/2303.14617/) (2023)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [Neural Multi-Hop Reasoning With Logical Rules on Biomedical Knowledge Graphs](https://mlsanity.com/paper/2103.10367/) (2021)
- [Query2Particles: Knowledge Graph Reasoning with Particle Embeddings](https://mlsanity.com/paper/2204.12847/) (2022)
- [Advancing Agentic Systems: Dynamic Task Decomposition, Tool Integration and Evaluation using Novel Metrics and Dataset](https://mlsanity.com/paper/2410.22457/) (2024)
- [GammaE: Gamma Embeddings for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2210.15578/) (2022)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [Faithful to the Document or to the World? Mitigating Hallucinations via Entity-linked Knowledge in Abstractive Summarization](https://mlsanity.com/paper/2204.13761/) (2022)
- [Reinforcement Learning from Reformulations in Conversational Question Answering over Knowledge Graphs](https://mlsanity.com/paper/2105.04850/) (2021)
- [Few-shot Relational Reasoning via Connection Subgraph Pretraining](https://mlsanity.com/paper/2210.06722/) (2022)
- [LLM-Based Multi-Hop Question Answering with Knowledge Graph Integration in Evolving Environments](https://mlsanity.com/paper/2408.15903/) (2024)
- [Towards Accurate and Compact Architectures via Neural Architecture Transformer](https://mlsanity.com/paper/2102.10301/) (2021)
- [Learning to Walk with Dual Agents for Knowledge Graph Reasoning](https://mlsanity.com/paper/2112.12876/) (2021)
- [Efficient Non-Sampling Knowledge Graph Embedding](https://mlsanity.com/paper/2104.10796/) (2021)
- [Structure Guided Prompt: Instructing Large Language Model in Multi-Step Reasoning by Exploring Graph Structure of the Text](https://mlsanity.com/paper/2402.13415/) (2024)
- [CAKE: A Scalable Commonsense-Aware Framework For Multi-View Knowledge Graph Completion](https://mlsanity.com/paper/2202.13785/) (2022)
- [MMKGR: Multi-hop Multi-modal Knowledge Graph Reasoning](https://mlsanity.com/paper/2209.01416/) (2022)
- [SMiLE: Schema-augmented Multi-level Contrastive Learning for Knowledge Graph Link Prediction](https://mlsanity.com/paper/2210.04870/) (2022)
- [OCEAN: Offline Chain-of-thought Evaluation and Alignment in Large Language Models](https://mlsanity.com/paper/2410.23703/) (2024)
- [Knowledge Sheaves: A Sheaf-Theoretic Framework for Knowledge Graph Embedding](https://mlsanity.com/paper/2110.03789/) (2021)
- [Is Multi-Hop Reasoning Really Explainable? Towards Benchmarking Reasoning Interpretability](https://mlsanity.com/paper/2104.06751/) (2021)
- [KRACL: Contrastive Learning with Graph Context Modeling for Sparse Knowledge Graph Completion](https://mlsanity.com/paper/2208.07622/) (2022)

## Abstract (arXiv)

Multi-hop reasoning is an effective approach for query answering (QA) over incomplete knowledge graphs (KGs). The problem can be formulated in a reinforcement learning (RL) setup, where a policy-based agent sequentially extends its inference path until it reaches a target. However, in an incomplete KG environment, the agent receives low-quality rewards corrupted by false negatives in the training data, which harms generalization at test time. Furthermore, since no golden action sequence is used for training, the agent can be misled by spurious search trajectories that incidentally lead to the correct answer. We propose two modeling advances to address both issues: (1) we reduce the impact of false negative supervision by adopting a pretrained one-hop embedding model to estimate the reward of unobserved facts; (2) we counter the sensitivity to spurious paths of on-policy RL by forcing the agent to explore a diverse set of paths using randomly generated edge masks. Our approach significantly improves over existing path-based KGQA models on several benchmark datasets and is comparable or better than embedding-based models.