🤖 AI

Scalable Uncertainty Reasoning in Knowledge Graphs

This thesis proposes a modular framework for scalable uncertainty reasoning in knowledge graphs that addresses imprecise attributes, probabilistic triples, and incomplete schemas through specialized algebraic, logical, and geometric techniques to reconcile semantic precision with computational tractability.

Original authors: Jingcheng Wu

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jingcheng Wu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a massive digital library called a Knowledge Graph. Its job is to organize facts about the world, like "Motor 123 is an electric motor" or "Grinder 07812 has a fault." Currently, this library works like a strict librarian who only accepts facts that are 100% true or 100% false. If a fact isn't written down exactly, the librarian says, "I don't know," even if there's a strong hint or a measurement that's almost certain.

In the real world, however, things are messy. Data is often fuzzy, incomplete, or just a "best guess." This thesis, by Jingcheng Wu, proposes a new way to run this library so it can handle uncertainty without crashing the computer.

The author argues that you can't use one single tool to fix all types of uncertainty. Instead, they break the problem down into three different "rooms" in the library, each requiring a different key:

Room 1: The "Fuzzy Ruler" (Attribute-Level Uncertainty)

The Problem: Sometimes we know a fact exists, but the number attached to it is a guess.

Example: We know a motor has a temperature, but the sensor says it's "around 80°C, give or take 1 degree." The current library treats this as a broken fact because it can't handle the "give or take."
The Solution: The author built a new mathematical ruler (an algebraic framework). Instead of forcing the computer to guess thousands of times (like rolling dice repeatedly to get an average), this new ruler can do the math instantly. It treats the "80 ± 1" as a single, smooth curve (a Gaussian distribution) and allows the computer to combine these curves directly.
The Result: It's like upgrading from a calculator that needs to count every grain of sand to one that can instantly measure the weight of a sandbag. The author's system, called ProbSPARQL, is much faster than the old "dice-rolling" methods while keeping the math precise.

Room 2: The "Detective's Map" (Triple-Level Uncertainty)

The Problem: Sometimes we aren't sure if a fact exists at all.

Example: "There is a 12% chance that Grinder 07812 has an overheating fault." The current library struggles to calculate the odds of complex scenarios involving many such "maybe" facts because the math gets too heavy (a problem known as being "computationally intractable").
The Solution: The author uses a technique called Knowledge Compilation. Imagine a detective trying to solve a case by checking every possible version of reality (a "what-if" scenario). Doing this live is slow. Instead, the author's system does the heavy lifting before the user asks a question. It translates the messy "maybe" facts into a clean, organized flowchart (a probabilistic circuit).
The Result: Once the flowchart is built, answering a question becomes as fast as following a map. The system can instantly tell you the probability of a fault without having to re-simulate the entire universe of possibilities every time.

Room 3: The "Shape-Shifting Box" (Group-Level Uncertainty)

The Problem: Sometimes we have rules about groups of things that are statistical, not absolute.

Example: "85% of angle grinders have a dust cover." This isn't a rule for every single grinder; it's a pattern. The current library tries to fit these patterns into flat, 2D shapes (like boxes on a piece of paper), which gets messy and inaccurate when the data has deep hierarchies (like a family tree).
The Solution: The author suggests using curved space (specifically, hyperbolic geometry) instead of flat space. Think of a flat sheet of paper trying to wrap around a tree trunk—it crumples. But a curved surface (like a saddle or a funnel) fits the tree perfectly.
The Result: By mapping these statistical rules onto a curved surface, the computer can understand the "shape" of the data much better. It can estimate probabilities (like "how likely is this grinder to have a cover?") much more accurately than trying to force everything into a flat box.

The Big Picture

The main idea of this thesis is "Specialization."
Instead of trying to force one giant, clumsy tool to handle all types of uncertainty, the author built three specialized tools:

Algebra for fuzzy numbers.
Logic Circuits for "maybe" facts.
Curved Geometry for statistical rules.

By using the right tool for the right job, the system can handle the messy, uncertain real world while remaining fast and accurate. The author has already tested the first tool (the fuzzy ruler) on a massive dataset of 3 million facts and found it to be significantly faster than existing methods, proving that this "divide and conquer" strategy works.

Technical Summary: Scalable Uncertainty Reasoning in Knowledge Graphs

1. Problem Statement

Knowledge Graphs (KGs) are essential for semantic data integration but frequently model real-world data that is inherently uncertain. Current W3C standards (RDF, SPARQL) operate under a binary truth assumption, lacking native support for probabilistic reasoning. This limitation creates a significant barrier to handling three distinct levels of uncertainty found in KGs:

Attribute-level Uncertainty: Imprecise literal values (e.g., sensor readings with noise) where the triple exists but the value is a continuous random variable. Existing approaches treat these as descriptive metadata or rely on inefficient sampling, lacking a query algebra for operations like convolution or Bayesian fusion.
Triple-level Uncertainty: The probabilistic existence of a triple (e.g., a link prediction with a confidence score). While Tuple-Independent Database (TID) models exist, exact inference for complex, non-monotonic SPARQL queries is often #P-hard. Current provenance engines fail to exploit query structure for "lifted" inference or handle dependencies beyond independence assumptions.
Group-level Uncertainty: Statistical constraints within the KG schema (e.g., "85% of angle grinders have a dust cover"). Exact reasoning in Statistical EL (SEL) is Exptime-complete. Existing geometric approximation methods (e.g., BoxEL) use flat Euclidean spaces that fail to efficiently represent hierarchical ontologies without excessive dimensionality.

The core challenge is that unifying these heterogeneous forms of uncertainty often leads to prohibitive computational complexity (#P-hard or Exptime-complete). The thesis proposes that specialized reasoning mechanisms—algebraic, logical, and geometric—can reconcile semantic precision with computational tractability.

2. Methodology and Approach

The thesis adopts a "decompose-then-specialize" methodology, addressing each uncertainty level with a tailored framework:

2.1 Attribute-level: Algebraic Query Framework

To handle continuous random variables, the research proposes extending the Semantic Web stack with a native datatype for distributions.

Representation: Defines a custom RDF datatype to encode probability distributions (specifically Gaussian Mixture Models or GMMs) as structured literals.
Query Algebra: Extends SPARQL with distribution-aware operators, including probabilistic filtering, Bayesian fusion, and similarity joins.
Mechanism: Utilizes closed-form algebraic operations (e.g., convolution, product) on GMMs to avoid the runtime overhead of Monte Carlo sampling.
Evaluation: Benchmarks against deterministic baselines and sampling strategies (Monte Carlo, stratified sampling) to measure latency and approximation error.

2.2 Triple-level: Logical Compilation Framework

To handle existential probabilities and dependencies, the research leverages Knowledge Compilation (KC).

Mechanism: Shifts complexity from online query evaluation to an offline compilation phase. The system transforms SPARQL provenance lineage into tractable probabilistic circuits, specifically deterministic Decomposable Negation Normal Form (d-DNNF).
Optimization:
- Safe/Unsafe Classification: Identifies "Safe" query patterns (PTIME) to perform lifted inference directly without compilation.
- Non-monotonic Handling: Compiles lineage polynomials defined over spm-semirings (handling OPTIONAL and MINUS) into circuits while preserving probabilistic semantics.
- Dependencies: Integrates probabilistic dependencies (modeled via Bayesian Networks) by encoding them as Conjunctive Normal Form (CNF) constraints within the unified circuit.
Evaluation: Verifies correctness against brute-force enumeration on small graphs and assesses efficiency via compilation time and circuit size.

2.3 Group-level: Geometric Embedding Framework

To handle statistical schema reasoning, the research moves from flat Euclidean space to topology-aware geometric manifolds.

Mechanism: Maps ontological concepts to manifolds that match their structural characteristics. Specifically, it proposes using Hyperbolic space for hierarchical taxonomies, where volume grows exponentially with radius, naturally matching the branching of ontologies.
Inference: Estimates conditional probabilities $P(D|C)$ via volumetric ratios of concept boxes within the embedding space: $P(D|C) \approx \frac{Vol(Box(C) \cap Box(D))}{Vol(Box(C))}$ .
Evaluation: Compares approximation fidelity (Mean Absolute Error) against exact inference on small-scale SEL knowledge bases, varying ontology depth and branching factors.

3. Key Contributions

The thesis contributes three distinct frameworks and a central hypothesis:

ProbSPARQL (Attribute-level): A framework introducing a native RDF datatype for continuous random variables and a corresponding query algebra. It supports closed-form operations on GMMs, enabling efficient probabilistic filtering and similarity joins.
Compilation-based Provenance (Triple-level): A middleware that transforms SPARQL lineage and probabilistic dependencies into d-DNNF circuits. This enables scalable, exact inference for non-monotonic queries and handles tuple dependencies beyond the TID assumption.
Topology-aware Embeddings (Group-level): A geometric neuro-symbolic approach that generalizes box embeddings to non-Euclidean manifolds (e.g., Hyperbolic space) to better preserve hierarchical structures and improve approximation fidelity for statistical axioms.
Central Hypothesis: Specialized reasoning mechanisms (algebraic, logical, geometric) tailored to specific uncertainty types can achieve a balance between semantic precision and computational tractability that unified approaches cannot.

4. Preliminary Results

The paper reports preliminary results specifically for the Attribute-level framework (ProbSPARQL), implemented atop Apache Jena/Fuseki:

Overhead: On synthetic KGs with 3 million triples, the probabilistic framework incurs a constant overhead of 1.25×–2.16× compared to deterministic baselines.
Optimization: Pushing probabilistic filters below joins yields up to a 17.7× speedup.
Similarity Joins: Using a divergence-based SIMJOIN operator with Data Processing Inequality pruning eliminates 90% of candidates, achieving a 178.8× end-to-end speedup compared to naive pipelines.
Efficiency: Histogram-based similarity computation is three orders of magnitude faster than Monte Carlo sampling.
Support: The system supports various distribution families, including histograms and Dirichlet distributions.

Results for Triple-level and Group-level approaches are presented as proposed methodologies and evaluation plans rather than completed empirical benchmarks in this text.

5. Significance and Claims

The paper claims that by decomposing uncertainty into three distinct levels and applying specialized reasoning mechanisms, it is possible to overcome the computational intractability that currently plagues probabilistic reasoning in Knowledge Graphs.

Scalability: The proposed frameworks aim to make probabilistic reasoning feasible for large-scale KGs, moving beyond the limitations of sampling-based approaches and exact inference on complex queries.
Semantic Precision: By using closed-form algebraic operations and exact circuit compilation, the approach maintains rigorous probabilistic semantics rather than relying on fuzzy logic or loose approximations.
Foundational Scope: While the Group-level approach is currently restricted to Statistical EL (limiting expressivity), the thesis notes that EL underpins major ontologies (e.g., SNOMED CT, Gene Ontology), making it a natural and significant starting point. The work establishes a modular foundation for extending these techniques to more expressive logics in the future.

The research is positioned as a step toward a Semantic Web stack that natively supports uncertainty, bridging the gap between the deterministic nature of current standards and the stochastic reality of real-world data.