Bayesian Inference with Complex Knowledge Graph Evidence

Armin Toroghi, Scott Sanner

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.

Figure 1: Overview of the BIKG framework, showing the translation of natural language into First-Order Logic (FOL), the construction of a Markov Random Field, and the sequential updating of the user's 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).
Figure 2: Comparison of MPE and Marginalization strategies. Marginalization allows for a broader probabilistic view, which is particularly effective for one-to-many relationships in recommendation tasks.

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

Abstract

Knowledge Graphs (KGs) provide a widely used format for representing entities and their relationships and have found use in diverse applications including question answering and recommendation. A majority of current research on KG inference has focused on reasoning with atomic facts (triples) and has disregarded the possibility of making complex evidential observations involving logical operators (negation, conjunction, disjunction) and quantifiers (existential, universal). Further, while the application of complex evidence has been explored in KG-based query answering (KGQA) research, in many practical online settings, observations are made sequentially. For example, in KGQA, additional context may be incrementally suggested to narrow down the answer. Or in interactive recommendation, user critiques may be expressed sequentially in order to narrow down a set of preferred items. Both settings are indicative of information filtering or tracking tasks that are reminiscent of belief tracking in Bayesian inference. In fact, in this paper, we precisely cast the problem of belief tracking over unknown KG entities given incremental complex KG evidence as a Bayesian filtering problem. Specifically, we leverage Knowledge-based Model Construction (KBMC) over the logical KG evidence to instantiate a Markov Random Field (MRF) likelihood representation to perform closed-form Bayesian inference with complex KG evidence (BIKG). We experimentally evaluate BIKG in incremental KGQA and interactive recommendation tasks demonstrating that it outperforms non-incremental methodologies and leads to better incorporation of conjunctive evidence vs. existing complex KGQA methods like CQD that leverage fuzzy T-norm operators. Overall, this work demonstrates a novel, efficient, and unified perspective of logic, KGs, and online inference through the lens of closed-form BIKG.
BibTeX
@inproceedings{toroghi2024bayesian,
  author = {Armin Toroghi and Scott Sanner},
  title = {{Bayesian Inference with Complex Knowledge Graph Evidence}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i18.30040},
}
Figure