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 and NELL serve as critical backbones for many AI applications, yet they are inherently incomplete. Multi-hop reasoning—the process of following a chain of links to infer missing facts—is essential for KG completion. Traditional approaches typically bifurcate this task into path-finding (searching for evidence) and path-reasoning (interpreting the evidence). However, these stages are often optimized independently, leading to a disconnect where path-finders generate noise that reasoners cannot handle, or reasoners fail to guide the search toward semantically relevant paths.
The DIVA Framework
To address these limitations, we introduce DIVA (Variational Knowledge Graph Reasoning). DIVA treats multi-hop reasoning as a latent variable model where paths ($L$) are hidden variables connecting a source entity ($e_s$) and a target entity ($e_d$). Because the space of all possible paths is enormous, we employ Variational Inference to maximize the Evidence Lower Bound (ELBO).
The framework is composed of three primary neural modules:
- The Path Finder (Prior): An agent using an LSTM-based Markov Decision Process (MDP) to navigate the KG and discover paths between entities without initial knowledge of the target relation.
- The Path Reasoner (Likelihood): A Convolutional Neural Network (CNN) that processes path sequences to predict the probability of specific relations. The use of a CNN allows for efficient extraction of local features from relatively short reasoning chains.
- The Posterior Approximator: Utilized during training, this module is aware of the target relation and guides the Prior toward "gold" paths that are most relevant to the query, essentially teaching the model what a high-quality path looks like.
Experimental Evaluation
We evaluated DIVA on two benchmark datasets: FB15k-237 (a challenging subset of Freebase with inverse relations removed) and NELL-995. Both datasets include negative samples to rigorously test the model's robustness against noise.
Results and Insights
DIVA achieved state-of-the-art performance on both benchmarks. On FB15k-237, it reached a Mean Averaged Precision (MAP) of 59.8, surpassing previous methods like MML (58.7) and RL-based DeepPath (57.2). On NELL-995, it achieved a MAP of 88.6, significantly outperforming DeepPath (79.6).
Key findings include:
- Posterior Guidance: The KL-divergence loss effectively pulls the Prior toward high-quality paths identified by the posterior during training.
- Model-Based Rewards: Unlike previous Reinforcement Learning methods that use heuristic rewards, DIVA uses the log-likelihood from the Path Reasoner as a reward signal, providing a more nuanced training objective.
- Beam Size Dynamics: Our analysis reveals a "Goldilocks zone" for beam search. As shown in the results, increasing beam size initially improves performance by finding more relevant paths, but excessively large sizes can introduce noise that degrades the reasoner's accuracy.
Conclusion
DIVA provides a unified probabilistic framework for KG reasoning, bridging the gap between search and classification. By jointly optimizing path-finding and reasoning through variational inference, the model demonstrates superior robustness and accuracy. Future work will focus on addressing KG-level noise and exploring more efficient search strategies beyond traditional beam search.
Summary updated