Rule-Aware Reinforcement Learning for Knowledge Graph Reasoning

Zhongni Hou, Xiaolong Jin, Zixuan Li, Long BaiACL 2021

TL;DR

This paper introduces RARL, a novel reinforcement learning approach for knowledge graph reasoning that leverages symbolic rules to guide the exploration process. By integrating high-quality rules and a partially random beam search, RARL effectively addresses the sparse reward problem and mitigates the impact of spurious paths, leading to improved accuracy in predicting missing facts.

What Problem Does This Paper Address?

Knowledge Graphs (KGs) are powerful tools for representing information, but they are often incomplete, meaning many facts are missing. KG completion aims to fill these gaps. While embedding-based methods have been successful, they often lack interpretability. Multi-hop reasoning, which finds a path of relations to connect entities, offers better interpretability but faces significant challenges.

The primary challenges in multi-hop reasoning using Reinforcement Learning (RL) are:

  • Sparse Reward Problem: RL agents receive rewards only when they successfully find the correct answer (i.e., the target entity). In large KGs with many possible paths, most paths do not lead to the correct answer, making it difficult for the agent to learn effectively from infrequent rewards.
  • Spurious Paths: The RL agent might accidentally discover paths that, by chance, lead to the correct answer but are semantically inconsistent with the query. The agent can then reinforce these "spurious" paths, leading to biased exploration and poor generalization.

Methods

The proposed method, RARL (Rule-Aware Reinforcement Learning), tackles these challenges by combining symbolic rule-based reasoning with RL and a modified beam search strategy.

  • Rule Integration: RARL injects high-quality symbolic rules (e.g., (x.born_in,y) ^ (v.city_in.z) -> (x.nationality_of.z)) into the reasoning process. These rules act as prior information, guiding the agent towards more semantically relevant actions and increasing the probability of finding correct paths. Rules are mined from the KG using tools like AIME+.
  • Partially Random Beam Search: Instead of strictly selecting the top-K most probable paths at each step (standard beam search), RARL introduces randomness. It randomly samples a fraction of candidate paths and selects the remaining ones based on their scores from the policy network. This encourages exploration of less probable but potentially useful paths and helps to avoid getting stuck on spurious paths that might initially receive high scores.
  • Action Selection Strategy: At each reasoning step, the agent selects actions from three sources: actions matching symbolic rules, actions with high scores from the policy network, and randomly sampled actions. This multi-pronged approach balances guided exploration with the need for diversity.

Datasets

The paper evaluates RARL on three standard link prediction datasets:

  • UMLS: A dataset derived from the Unified Medical Language System.
  • WN18RR: A subset of WordNet, focusing on relation prediction.
  • FB15K-237: A subset of Freebase, specifically focusing on 20 relations within the film domain.

Rules were automatically extracted using AIME+ and limited to a maximum length of 2.

Key Insights and Ideas

  • Symbolic Rules as Guidance: The core insight is that symbolic rules, when of high quality, can significantly improve the efficiency and accuracy of RL-based reasoning by providing strong inductive biases. They act as a form of "curriculum" for the RL agent.
  • Balancing Exploration and Exploitation: The partially random beam search is crucial. It acknowledges that while high-scoring paths are important, completely ignoring lower-scoring paths can be detrimental, especially when dealing with sparse rewards and the risk of spurious paths. Randomness helps break out of local optima.
  • Interpretability through Rules: By explicitly using rules, the reasoning process becomes more transparent. The paths found can be explained by the rules they follow, enhancing the interpretability of the KG completion task.

Key Results

RARL demonstrates strong performance across the evaluated datasets:

  • Superiority over Multi-hop Methods: RARL consistently outperforms existing multi-hop reasoning methods on all three datasets in terms of Hit@1, Hits@10, and MRR.
  • Competitive with Embedding Methods: While embedding-based methods sometimes perform better on datasets like UMLS and FB15K-237 (attributed to their robustness against KG sparsity), RARL achieves competitive results.
  • Ablation Study Highlights Importance: Removing rule information or the random mechanism from RARL leads to a significant performance drop, underscoring the effectiveness of both components. The ablation study also suggests that increasing exploration diversity is key for training.

Limitations and Future Work

  • Rule Quality Dependency: The performance of RARL is dependent on the quality and coverage of the extracted symbolic rules. If rules are noisy or incomplete, their effectiveness might be limited.
  • KG Sparsity: While RARL mitigates sparsity issues, it can still be a challenge, especially for embedding-based methods which might be more resilient.
  • Future Work: The authors suggest further exploring how to improve exploration diversity and potentially combine RARL with other reasoning techniques. The paper also hints at the potential for RARL to be applied to more complex reasoning tasks beyond simple link prediction.

Summary updated

BibTeX
@inproceedings{hou2021rule,
  author = {Zhongni Hou and Xiaolong Jin and Zixuan Li and Long Bai},
  title = {{Rule-Aware Reinforcement Learning for Knowledge Graph Reasoning}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure