Scalable Uncertainty Reasoning in Knowledge Graphs

Jingcheng Wu · 2026

Read Scalable Uncertainty Reasoning in Knowledge Graphs by Jingcheng Wu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16568.txt.

Introduction

Wu's thesis tackles reasoning under uncertainty in knowledge graphs. Such graphs may carry vague values, uncertain links, and patchy schema knowledge. Current Semantic Web standards offer no native way to reason with such uncertainty. Naive add-ons fail to scale, so the work builds a modular framework across three levels. It defines probabilistic literals with a query algebra for attributes. It compiles SPARQL provenance into usable probabilistic circuits for uncertain triples. It uses topology-aware embeddings for schema reasoning.

Catalog record

CREATORJingcheng Wu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29869
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.16568

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable Uncertainty Reasoning in Knowledge Graphs Jingcheng Wu Abstract Knowledge Graphs are pivotal for semantic data integration. The real-world data they model is often inherently uncertain. Within knowledge graphs, uncertainty manifests in three distinct levels: imprecise attribute values, probabilistic triple existence, and incomplete schema knowledge. However, current Semantic Web standards lack native support for reasoning over such uncertainty, and naïve extensions often incur computational intractability. In this thesis, I aim to develop a modular framework that addresses each level through tailored techniques: (1) defining probabilistic literals and a corresponding query algebra for continuous attributes; (2) a compilation-based framework transforming SPARQL provenance into tractable probabilistic circuits for uncertain triples; and (3) topology-aware geometric embeddings for statistical schema reasoning. The central hypothesis is that specialized reasoning mechanisms, namely algebraic, logical, and geometric approaches, can reconcile semantic precision with computational tractability. 1 Introduction Knowledge Graphs (KGs) [ 27 ] serve as a versatile framework for the semantic integration of heterogeneous data [ 8 , 31 ] , typically relying on W3C standards such as RDF [ 13 ] for data representation and SPARQL [ 23 ] for querying. While these standards excel at retrieving deterministic facts, they operate under an assumption of binary truth [ 33 ] . For instance, the triple (:Motor123, rdf:type, :ElectricMotor) asserts that the entity Motor123 is classified as an electric motor. A standard query for this triple mandates an exact graph match, treating the statement as a binary fact that must explicitly exist in the dataset. In reality, KGs are frequently incomplete and subject to uncertainty, containing missing links and unreliable facts that conflict with the deterministic nature of W3C standards [ 20 , 33 , 52 ] . This pervasive uncertainty is not a monolithic phenomenon but in heterogeneous forms that defy a “one-size-fits-all” treatment. Consider the contrast between a triple representing a confirmed relationship with an uncertain value, such as ( :Motor123 , :hasTemperature , \mathcal{N}(80^{\circ}\text{C},1^{\circ}\text{C}) ), and a triple where the existence of the statement is a probabilistic hypothesis, such as ( :Grinder07812 , :hasFault , :Overheat ) with P=0.12 . The former relies on calculus-based integration to evaluate range-based constraints over infinite continuous domains [ 50 ] . Conversely, the latter employs combinatorial model counting to aggregate the probabilities of discrete possible worlds [ 43 ] . Attempting to unify these heterogeneous forms by coupling discrete structural probabilities with continuous attribute distributions often incurs prohibitive computational complexity, such as #P-hard inference [ 14 ] , because the engine cannot efficiently reconcile discrete counting with infinite continuous domains [ 39 ] . To achieve scalable reasoning without sacrificing semantic precision, we decompose this complexity by distinguishing the nature of the uncertainty. Specifically, following [ 45 , 47 ] , we categorize KG uncertainty into three distinct levels: • Attribute-level Uncertainty refers to the imprecision or inaccuracy of literal values [ 5 , 25 ] . At this level, the existence of the triple is deterministic, but the literal value remains uncertain due to factors such as measurement errors or sensor noise. Recalling the aforementioned Motor123 example, the triple ( :Motor123 , :hasTemperature , l ) is confirmed, but the literal l follows the distribution \mathcal{N}(80^{\circ}\text{C},1^{\circ}\text{C}) rather than a precise scalar. • Triple-level Uncertainty concerns the existential probability of a specific triple between two entities or an entity and a literal [ 20 , 33 ] . This uncertainty is frequently introduced by expert assessment [ 5 ] , link prediction [ 6 , 19 ] , or information extraction [ 20 ] . Recalling the Grinder07812 example, based on domain experts’ observations, there is a 12% probability of an overheat fault. Accordingly, the triple ( :Grinder07812 , :hasFault , :Overheat ) is represented not as a binary fact, but as a probabilistic hypothesis where P(\texttt{:Grinder07812},\texttt{:hasFault},\texttt{:Overheat})=0.12 . • Group-level Uncertainty refers to the probabilistic constraints and statistical regularities residing within the KG schema [ 34 , 51 ] . This level extends the scope of uncertainty from individual facts to terminological axioms regarding entire classes of entities. Instead of focusing on isolated instances, it models general dependencies. For example, regarding the class :AngleGrinder where \texttt{:Grinder07812}\in\texttt{:AngleGrinder} , statistical schema knowledge asserts that 85\% of such devices are equipped with a :DustCover . Formally, this is encoded as the probabilistic inclusion axiom \texttt{:AngleGrinder}\sqsubseteq_{0.85}\exists\texttt{:hasPart}.\texttt{:DustCover} . Despite their differences, these three levels face a common barrier: existing Semantic Web engines lack native support for probabilistic reasoning. Attribute-level handling is currently restricted to descriptive metadata or inefficient sampling; Triple-level inference is #P-hard without structural optimization; and Group-level logical reasoning scales poorly. This thesis addresses these limitations by extending the Semantic Web stack with distinct reasoning mechanisms tailored to each uncertainty type. Specifically, I study: (1) an algebraic query framework for Attribute-level uncertainty, instantiated via closed-form Gaussian Mixture Models (GMMs); (2) a logical compilation framework for Triple-level uncertainty, transforming probabilistic graph patterns into tractable circuits; and (3) a geometric embedding model for Group-level uncertainty, mapping statistical schemas onto topology-aware manifolds. The central hypothesis is that treating these levels through their respective algebraic, logical, and geometric lenses enables the reconciliation of semantic precision with computational tractability. 2 State of the Art We analyze the state of the art based on the three levels. 2.1 Attribute-level Uncertainty Existing standards within the Semantic Web, such as the Semantic Sensor Network (SSN) ontology [ 25 ] and ProbOnto [ 44 ] , have established rich vocabularies for describing probability distributions and sensor observations. Similarly, SCOVO [ 24 ] and the RDF Data Cube [ 12 ] provide ontologies for exchanging statistical data. However, these frameworks function primarily as descriptive metadata schemas . They define how statistical data is structurally represented but lack the underlying query algebra required to execute operations, such as convolution or Bayesian fusion, directly within the database engine. In the RDF stream processing, Keskisärkkä et al. [ 30 , 29 ] introduced a custom literal datatype and SPARQL extensions for probabilistic filtering within the RSP-QL* model. While sharing the high-level idea of embedding distributions in RDF literals, their work targets the transient nature of data streams and differs from our persistent KG framework in three key respects. First, their representation conflates random variables with distributions, whereas our framework separates them to uniformly handle multi-dimensional data. Second, their operations map distributions strictly to scalar probabilities without algebraic closure, precluding chained transformations (e.g., convolution, Bayesian fusion) or distributional comparisons like similarity joins. Third, they support only basic parametric families, whereas our polymorphic support for heterogeneous distribution families (including GMMs, Dirichlet, and histograms) moving beyond basic parametric forms. Beyond the Semantic Web, handling continuous variables in probabilistic databases often incurs prohibitive computational costs. In relational databases, systems like Orion [ 41 ] and MCDB [ 28 ] allow multiple probability distributions as tuple attributes. Orion defines algebraic operations such as floor, marginalize, and product over distributions, whereas MCDB relies on generating thousands of random samples during query evaluation. Although the Monte Carlo approach offers flexibility, it introduces massive runtime overhead, rendering it unsuitable for the interactive querying demands of large-scale knowledge graphs. These limitations reveal a critical research gap: the absence of a query algebra that treats diverse probability distributions (encompassing discrete, continuous, parametric, and non-parametric

Read the complete text