Enhancing Multi-Hop Knowledge Graph Reasoning through Reward Shaping Techniques

Chen Li, Haotian Zheng, Yiping Sun, Cangqing Wang, Liqiang Yu, Che Chang, Xinyu Tian, Bo Liu

TL;DR

This paper tackles the challenge of incomplete Knowledge Graphs (KGs) in multi-hop reasoning by using reinforcement learning with a novel "reward shaping" technique. They show that pre-training a reward shaping module using prompt learning on a "rich" KG significantly improves the performance of KG reasoning agents on "sparse" KGs, outperforming BERT-based contextualization.

What Problem Does This Paper Address?

Knowledge Graph Reasoning (KG-R) aims to infer new facts and answer complex queries by navigating relationships within a KG. A common approach uses Reinforcement Learning (RL), where an agent learns to traverse the graph. However, real-world KGs are often incomplete, leading to errors (false positives/negatives) and making it hard for RL agents to learn effectively. Standard RL reward functions, which only give a reward for finding the exact correct answer, are too brittle for these incomplete graphs. This paper addresses how to make KG-R more robust and accurate in the face of KG incompleteness by improving the reward signal.

Methods

The core of this paper is enhancing the reward signal in RL-based KG-R using "reward shaping." The authors propose a method that involves:

  1. Splitting KGs: They create "rich" and "sparse" versions of a KG. The "rich" KG is a more complete version, while the "sparse" KG has missing entities and relations, simulating real-world incompleteness.
  2. Reward Shaper Pre-training: They pre-train a "Reward Shaper" module. This module learns to provide a more nuanced reward signal than a simple binary reward.
  3. Prompt Learning for Reward Shaping: A key innovation is using prompt learning (specifically with the T5 model) to pre-train the Reward Shaper. This involves creating templates like "[head entity] is interconnected with [tail entity] via the relationship of [relation]" and using the model to predict the tail entity, which then informs the reward.
  4. BERT Contextualization (for comparison): They also explore using pre-trained BERT embeddings to contextualize entities and relations for reward shaping, serving as a baseline.
  5. Transfer Learning: The pre-trained Reward Shaper is then applied to the sparse KG during the RL agent's training.

Datasets

  • Unified Medical Language System (UMLS) dataset: This dataset was used to create the "rich" and "sparse" KG subsets for their experiments.

Key Insights and Ideas

  • Reward Shaping is Crucial for Incomplete KGs: Simple binary rewards are insufficient. A more sophisticated reward signal is needed to guide RL agents when the KG is incomplete.
  • Prompt Learning Outperforms BERT for Reward Shaping: The prompt learning approach, when pre-trained on a rich KG, significantly boosted the performance of the RL agent on a sparse KG, outperforming BERT-based contextualization. This suggests that generating explicit relational text and predicting missing links via prompts is more effective for this task.
  • Transfer Learning is Key: Pre-training the reward shaping mechanism on a richer KG and then transferring that knowledge to a sparser KG is a powerful strategy for improving generalization.
  • The "Rich" KG Pre-training Matters: While they initially hypothesized that BERT contextualization would be superior, the results indicate that the method of pre-training (prompt learning vs. BERT) on the rich KG has a more significant impact.

Key Results

The paper presents quantitative results in Table I, evaluating performance using metrics like Hits@k (proportion of correct answers within the top k) and MRR (Mean Reciprocal Rank).

  • Prompt Learning RS trained on Rich KG (ours) achieved the highest performance across most metrics, including Hits@1 (0.877), Hits@3 (0.997), Hits@5 (0.995), and MRR (0.930).
  • BERT Contextualization RS trained on Rich KG (ours) performed well but was generally surpassed by the prompt learning approach, with Hits@1 at 0.810 and MRR at 0.785.
  • Sparse KG Policy Gradient + Rich Reward Shaping also showed strong results, indicating the benefit of a rich reward signal, but was still outperformed by the prompt learning method.

Limitations and Future Work

  • BERT Underperformance: Contrary to their initial hypothesis, BERT contextualization underperformed compared to prompt learning and even a ConvE-based approach. The authors suggest this indicates a complex interplay between embedding techniques and RL training in sparse KGs, warranting further investigation.
  • Overfitting Scenario: They note a potential overfitting scenario when utilizing the multiplicative inverse of the ordinal position within the said enumeration, with performance achieved through training on a sparsely populated KG being surpassed by training on a densely populated KG.
  • Future Work: The paper suggests that their prompt learning-based reward shaping module, pre-trained on densely populated knowledge graphs, offers a promising avenue for wider applications in KG utilization and reward shaping through transfer learning. Further research into the mechanisms underpinning effective reward shaping in sparse KG contexts is also implied.

Summary updated

Abstract

In the realm of computational knowledge representation, Knowledge Graph Reasoning (KG-R) stands at the fore-front of facilitating sophisticated inferential capabilities across multifarious domains. The quintessence of this research elucidates the employment of reinforcement learning (RL) strategies, notably the REINFORCE algorithm, to navigate the intricacies inherent in multi-hop KG-R. This investigation critically addresses the prevalent challenges introduced by the inherent incompleteness of Knowledge Graphs (KGs), which frequently results in erroneous inferential outcomes, manifesting as both false negatives and misleading positives. By partitioning the Unified Medical Language System (UMLS) benchmark dataset into rich and sparse subsets, we investigate the efficacy of pretrained BERT embeddings and Prompt Learning methodologies to refine the reward shaping process. This approach not only enhances the precision of multi-hop KG-R but also sets a new precedent for future research in the field, aiming to improve the robustness and accuracy of knowledge inference within complex KG frameworks. Our work contributes a novel perspective to the discourse on KG reasoning, offering a methodological advancement that aligns with the academic rigor and scholarly aspirations of the Natural journal, promising to invigorate further advancements in the realm of computational knowledge representation.
BibTeX
@misc{li2024enhancing,
  author = {Chen Li and Haotian Zheng and Yiping Sun and Cangqing Wang and Liqiang Yu and Che Chang and Xinyu Tian and Bo Liu},
  title = {{Enhancing Multi-Hop Knowledge Graph Reasoning through Reward Shaping Techniques}},
  year = {2024},
  eprint = {2403.05801},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.05801},
}
Figure