GaussianPath: A Bayesian Multi-Hop Reasoning Framework for Knowledge Graph Reasoning

Guojia Wan, Bo DuAAAI 2021 · DOI

TL;DR

This paper introduces GaussianPath, a novel Bayesian reinforcement learning framework for multi-hop reasoning in knowledge graphs. By modeling entity and relation embeddings as Gaussian distributions, GaussianPath effectively captures uncertainty, leading to more robust and interpretable reasoning, especially in noisy knowledge graphs.

What Problem Does This Paper Address?

Knowledge graphs (KGs) are powerful structured data sources, but they are often incomplete. Answering complex queries requires multi-hop reasoning, which involves traversing multiple relationships to find an answer. Existing reinforcement learning (RL) approaches for this task treat entities and relations as single points in a vector space, failing to account for inherent uncertainties. This can lead to agents getting stuck in suboptimal reasoning paths and premature exploitation of the KG. The paper aims to address this by incorporating uncertainty into the reasoning process.

Methods

GaussianPath frames multi-hop reasoning as a Markov Decision Process (MDP). The core innovation lies in representing entities and relations not as single points but as multi-dimensional Gaussian distributions, denoted as $N(\mu, \Sigma)$. This allows the framework to capture the uncertainty associated with each entity and relation.

Key methodological components include:

  • Bayesian Q-learning: A Bayesian neural network architecture, specifically a Bayesian LSTM, is used to approximate the Q-function. This allows the model to learn the uncertainty in the state-action value function.
  • Thompson Sampling: To balance exploration and exploitation, the paper employs Thompson sampling for action selection. This strategy samples actions based on the posterior distribution of the Q-values, encouraging exploration of uncertain paths.
  • Bayes by Backprop: To train the Bayesian neural network, the authors utilize Bayes by Backprop, a method for learning the probability distribution of network weights.
  • Off-Policy Learning: The framework uses an off-policy approach to optimize the agent's behavior, aiming to mitigate issues like high variance and unstable training often seen with on-policy methods like REINFORCE.

Datasets

The paper evaluates GaussianPath on several standard knowledge graph benchmarks:

  • FB15K-237
  • WN18RR
  • NELL995
  • UMLS
  • Kinship

NELL995 is highlighted as a particularly challenging dataset due to its inherent noise and automatically constructed nature.

Key Insights and Ideas

  • Uncertainty is Key: The most significant insight is that explicitly modeling uncertainty in entity and relation representations is crucial for effective multi-hop reasoning, especially in noisy KGs.
  • Bayesian RL for Robustness: Integrating Bayesian principles into RL provides a principled way to handle the exploration-exploitation dilemma and leads to more robust reasoning agents.
  • Thompson Sampling for Exploration: Thompson sampling proves effective in guiding the agent to explore less certain parts of the KG, preventing it from getting stuck in locally optimal but globally suboptimal paths.
  • Pre-trained Priors Accelerate Training: Using pre-trained Gaussian embeddings as prior distributions for entities and relations can significantly speed up the training process.

Key Results

GaussianPath demonstrates superior performance compared to existing baselines across various knowledge graph reasoning tasks, particularly in entity link prediction.

  • Improved Performance: The framework achieves state-of-the-art results on the NELL995 dataset and shows significant improvements over other methods, especially on automatically extracted KGs.
  • Robustness to Noise: The ability to handle uncertainty makes GaussianPath particularly effective on noisy KGs like NELL995, where it can suppress reasoning paths that lead to unreliable triplets.
  • Faster Convergence: Ablation studies show that GaussianPath converges faster than baseline RL methods, with pre-trained priors offering a slight acceleration.
  • Ablation Studies: Removing the Bayesian approach (resulting in Q-path) or Thompson sampling (resulting in a greedy execution policy) significantly degrades performance, highlighting the importance of these components.

Limitations and Future Work

  • Computational Cost: While effective, Bayesian methods and RL can be computationally intensive. The paper mentions that exactly minimizing the objective naively is computationally extensive, necessitating approximations.
  • Hyperparameter Sensitivity: The performance of RL methods can be sensitive to hyperparameter choices. While the paper provides settings, further exploration might be beneficial.
  • Future Work: The authors suggest that their framework can leverage prior knowledge in the form of pre-trained Gaussian distributions, which slightly accelerates convergence. Future work could explore more sophisticated ways to incorporate prior knowledge and further optimize the Bayesian inference process. The case visualization also suggests that a clear decision boundary exists between positive and negative answers, hinting at potential for improved classification tasks.

Summary updated

BibTeX
@inproceedings{wan2021gaussianpath,
  author = {Guojia Wan and Bo Du},
  title = {{GaussianPath: A Bayesian Multi-Hop Reasoning Framework for Knowledge Graph Reasoning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i5.16565},
}
Figure