Variational Knowledge Graph Reasoning

Wenhu Chen, Wenhan Xiong, Xifeng Yan, William Yang Wang

Abstract

Inferring missing links in knowledge graphs (KG) has attracted a lot of attention from the research community. In this paper, we tackle a practical query answering task involving predicting the relation of a given entity pair. We frame this prediction problem as an inference problem in a probabilistic graphical model and aim at resolving it from a variational inference perspective. In order to model the relation between the query entity pair, we assume that there exists an underlying latent variable (paths connecting two nodes) in the KG, which carries the equivalent semantics of their relations. However, due to the intractability of connections in large KGs, we propose to use variation inference to maximize the evidence lower bound. More specifically, our framework (DIVA) is composed of three modules, i.e. a posterior approximator, a prior (path finder), and a likelihood (path reasoner). By using variational inference, we are able to incorporate them closely into a unified architecture and jointly optimize them to perform KG reasoning. With active interactions among these sub-modules, DIVA is better at handling noise and coping with more complex reasoning scenarios. In order to evaluate our method, we conduct the experiment of the link prediction task on multiple datasets and achieve state-of-the-art performances on both datasets.

Introduction

Knowledge Graphs (KGs) such as Freebase or NELL serve as massive repositories of structured facts, yet they are frequently incomplete. To address this, researchers employ multi-hop reasoning, which involves traversing a chain of existing links to infer missing relationships. For instance, if a KG contains the facts that Michelle is married to Barack and Barack is the president of the USA, one can infer that Michelle resides in the USA.

Historically, multi-hop reasoning has been split into two distinct tasks: Path-Finding, often using Reinforcement Learning (RL) to navigate the graph, and Path-Reasoning, which interprets these paths to predict relations. However, this separation often leads to suboptimal performance, as path-finders rely on heuristic rewards and reasoners are limited by the quality of paths provided. The DIVA framework seeks to unify these components into a single, cohesive probabilistic model.

The DIVA Framework

DIVA (Distributed Variational Analysis) treats the path $L$ between two entities as a latent variable within a probabilistic graphical model. This approach allows the model to jointly optimize path discovery and interpretation.

The framework consists of three primary neural modules:

  1. Path Finder (The Prior): An MDP-based agent utilizing an LSTM to explore the KG and find paths between entity pairs without prior knowledge of the target relation.
  2. Path Reasoner (The Likelihood): A Convolutional Neural Network (CNN) that processes a path and outputs a probability distribution over potential relations.
  3. Posterior Approximator: A critical component during training that is aware of the target relation. It guides the model toward relevant paths, effectively acting as a teacher for the Prior.
Variational framework of DIVA showing the interaction between Prior, Posterior, and Likelihood modules.

The system is trained by maximizing the Evidence Lower Bound (ELBO). This objective ensures the Path Finder learns to emulate the Posterior's high-quality path selection, while the Path Reasoner improves its ability to classify relations based on those paths.

Experimental Evaluation

The authors evaluated DIVA on two standard benchmarks: FB15k-237, a challenging subset of Freebase with inverse relations removed, and NELL-995, derived from the "Never-Ending Language Learning" system.

Key Results

DIVA achieved state-of-the-art results, outperforming both traditional embedding-based methods and previous RL-based approaches:

  • NELL-995: DIVA reached a Mean Average Precision (MAP) of 88.6, a significant improvement over the previous best of 79.6.
  • FB15k-237: DIVA achieved a MAP of 59.8, surpassing existing baselines.
Performance (MAP) of DIVA on NELL-995 and FB15k-237 datasets across different beam sizes.

A key finding was the impact of beam size during testing. As shown in the results, a small beam size (around 5) provides an optimal balance, capturing sufficient paths while minimizing noise from low-quality connections.

Conclusion and Future Work

While DIVA sets a new performance standard, error analysis highlights ongoing challenges. In the NELL dataset, nearly 40% of errors stem from inherent KG noise, such as missing relations. In the more complex FB15k dataset, the Path Reasoner remains a bottleneck, struggling with intricate multi-hop chains. Future research may focus on scaling DIVA to larger graphs or incorporating external textual data to supplement sparse Knowledge Graphs.

Summary updated

Abstract

Inferring missing links in knowledge graphs (KG) has attracted a lot of attention from the research community. In this paper, we tackle a practical query answering task involving predicting the relation of a given entity pair. We frame this prediction problem as an inference problem in a probabilistic graphical model and aim at resolving it from a variational inference perspective. In order to model the relation between the query entity pair, we assume that there exists an underlying latent variable (paths connecting two nodes) in the KG, which carries the equivalent semantics of their relations. However, due to the intractability of connections in large KGs, we propose to use variation inference to maximize the evidence lower bound. More specifically, our framework (\textsc{Diva}) is composed of three modules, i.e. a posterior approximator, a prior (path finder), and a likelihood (path reasoner). By using variational inference, we are able to incorporate them closely into a unified architecture and jointly optimize them to perform KG reasoning. With active interactions among these sub-modules, \textsc{Diva} is better at handling noise and coping with more complex reasoning scenarios. In order to evaluate our method, we conduct the experiment of the link prediction task on multiple datasets and achieve state-of-the-art performances on both datasets.
BibTeX
@inproceedings{chen2018variational,
  author = {Wenhu Chen and Wenhan Xiong and Xifeng Yan and William Yang Wang},
  title = {{Variational Knowledge Graph Reasoning}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2018},
  url = {https://openreview.net/forum?id=rkELwm-uZS},
}
Figure