Abstract
Knowledge Graph (KG) reasoning has traditionally focused on atomic facts. However, real-world applications like conversational recommendation systems require handling complex, sequential logical evidence. This paper introduces BIKG (Bayesian Inference with Complex Knowledge Graph Evidence), a framework that treats KG reasoning as a sequential Bayesian filtering problem. By integrating Markov Random Fields with tensor-factorized embeddings, BIKG allows agents to incrementally update their probabilistic beliefs about unknown entities as complex logical constraints arrive over time.
Introduction
Most research in Knowledge Graphs focuses on simple triples, such as (Inception, directed_by, Christopher Nolan). Yet, user interactions are often more nuanced. For instance, a user might request: "I want a Korean action movie featuring a female actress who practices martial arts." This represents complex evidence involving multiple logical operators (AND, OR, NOT) and existential quantifiers.
Existing methods for Complex Query Answering (CQA) typically treat these queries as static, single-shot blocks. They often rely on fuzzy logic (T-norms), which can struggle to statistically integrate multiple pieces of evidence that arrive sequentially. BIKG addresses this gap by providing a framework for multi-step logical reasoning that maintains a consistent probabilistic "belief" state.
Methodology
BIKG reimagines KG reasoning through the lens of Bayesian filtering, similar to how a robot tracks its position based on sensor data. The framework consists of three core components:
1. Knowledge-based Model Construction (KBMC)
Upon receiving complex evidence, BIKG automatically constructs a Markov Random Field (MRF). In this graphical model, nodes represent entities (both observed and unobserved), and edges represent the relationships defined by the logical query.
2. Tensor-Factorized Likelihoods
To handle the inherent incompleteness of KGs, the model calculates the plausibility of relationships within the MRF using embeddings from SimplE, a state-of-the-art KG embedding method. This allows the system to predict missing links and maintain a robust probabilistic model.
3. Inference Strategies
The authors propose two primary strategies for updating beliefs:
- Most Probable Explanation (MPE): This approach uses a beam search to identify the most likely specific entities that satisfy intermediate steps of a query.
- Marginalization (The "Probabilistic Quantifier"): This key innovation treats unobserved variables as Gaussian distributions and marginalizes them out using the Schur complement. This enables "multi-path" reasoning, which is essential when many different entities might satisfy a constraint (e.g., multiple actresses fitting a "female lead" criteria).
Evaluation and Results
The researchers evaluated BIKG on two distinct tasks across five datasets, including standard KG benchmarks (FB15k, FB15k-237, NELL995) and recommendation datasets (MovieLens 20M, LFM-1b) linked to the Freebase KG.
Key Insights
- Superior Accuracy: BIKG consistently outperformed strong fuzzy-logic baselines like CQD across nearly all datasets and query types, particularly in handling disjunction (OR) and multi-hop chains.
- The Power of Marginalization: In recommendation tasks, the Marginalization approach was significantly more effective than MPE. Maintaining a broad probabilistic view of intermediate variables proved crucial for capturing diverse user tastes.
- Sequential Performance: Using Hit Rate@10 as the primary metric, BIKG demonstrated marked improvements as more evidence was added across sequential interaction steps.
Conclusion and Future Work
BIKG shifts the paradigm of KG reasoning from a search problem to a tracking problem. While the current framework relies on Gaussian assumptions for efficient closed-form marginalization, it provides a robust foundation for sequential Bayesian inference in structured knowledge domains. Future work may explore extending BIKG to non-Gaussian distributions and applying it to domains like medical diagnosis, where evidence naturally arrives in stages.
Summary updated