Many systems that predict missing facts in a knowledge graph work the same way. They find several chains of known facts, called paths, that each suggest a conclusion, score each path, and then combine the scores with a Noisy-OR. A Noisy-OR is the rule "the conclusion fails only if every path fails," so the combined score is $1-\prod_i(1-p_i)$. The combination assumes the paths are independent, and they usually are not. Two learned rules can both pass through the same observed fact, and one rule can fire many times through different intermediate entities. When a single noisy fact supports ten paths, the Noisy-OR counts it ten times. The predictions then come out overconfident, and candidates backed by many redundant paths are ranked above candidates backed by fewer paths that are genuinely independent.
Probabilistic databases already have the correct way to count shared evidence once. A probabilistic database stores each fact with the probability that it is true. The probability of a query answer is the total weight of the "possible worlds," meaning the random subsets of facts, in which the query holds. The research file shows that, for a large class of queries, this probability can be computed as ordinary relational operations: joins multiply probabilities, and projections combine them as a Noisy-OR over genuinely independent branches. We propose to rewrite a learned temporal rule set as a union of database queries and evaluate it under this possible-worlds semantics. Where the query structure allows, evaluation is exact SQL. Where it does not, we use sampling. The parameters that turn path scores into fact and rule probabilities are fit by likelihood under that same semantics. The claim is that this "factorized Noisy-OR" matches or improves ranking on temporal link forecasting and substantially improves calibration, with the largest gains on queries whose supporting paths overlap heavily.
Core Claim and What Is Actually New
The research file frames the gap as the absence of any lifted Noisy-OR. That framing is partly wrong, and the proposal starts by saying so. In the safe plans that underlie the tractability dichotomy adapted by Jung and Lutz (Ontology-Based Access to Probabilistic Data with OWL QL), existential projection over independent tuples already is a Noisy-OR. For example, the probability of $\exists b.\, r_1(a,b)\wedge r_2(b,c)$ is $1-\prod_b\bigl(1-p(r_1(a,b))\,p(r_2(b,c))\bigr)$. The work of Jermaine and Ramakrishnan on the equivalence between lifted inference and SQL aggregation ( Letter from the Special Issue Editor, Optimizing mpf queries: decision support and probabilistic inference; Optimizing mpf queries: decision support and probabilistic inference) supplies the compilation machinery. What has not been done is to treat a learned, weighted, temporal rule set as the query and data of such a system. That means deciding how uncertain rules become random events, fitting those probabilities, and measuring whether correcting double-counting changes predictions on a real benchmark.
The central construction handles the fact that rules themselves are uncertain. Jung and Lutz list uncertain TBoxes as open: their Lifting Theorem assumes deterministic ontological rules (in their setting, the TBox is the set of ontology axioms). We sidestep the problem by reification. Each learned rule $\rho$ becomes a probabilistic tuple $E_\rho$ with probability $\pi_\rho$, and $E_\rho$ is conjoined to its rule body. A candidate answer $c$ for the query $(a, r, ?, t)$ then receives
$$P(c)=P\Big(\bigvee_{\rho}\big(E_\rho\wedge\exists \bar b.\ \mathrm{body}_\rho(a,\bar b,c,t)\big)\Big),$$
where the probability is taken over independent tuples. Each historical fact $f$ has probability $p_\theta(f)$, a learned function of its recency, and $\theta$ collects those parameters together with the rule probabilities $\pi_\rho$.
Because $E_\rho$ is shared across all groundings of rule $\rho$, the formula does not reward a rule for firing through many intermediates in the way per-path Noisy-OR does. Because rule bodies that share an atom such as $r_1(a,b)$ factor that atom out, the shared fact is counted once. After the rewriting, the formula is a union of conjunctive queries with temporal selection predicates. Deterministic ontology axioms, when available, can be folded in by standard rewriting, which the Lifting Theorem shows remains sound for probabilities.
The closest existing work is Calì and Lukasiewicz's probabilistic data integration (An Approach to Probabilistic Data Integration for the Semantic Web) and its dl-program follow-ups ( Representing Ontology Mappings with Probabilistic Description Logics Programs). These attach probabilities to mapping rules via Independent Choice Logic and combine redundant sources. Our proposal differs in three ways. Those papers use hand-set reliabilities where we learn them. They reason with answer-set solvers where we compile to relational plans. And they report no experiments, whereas we evaluate on a standard benchmark.
Research Program
The first component is a compiler from TLogic-style temporal rules to probabilistic relational plans. TLogic (TLogic: Temporal Logical Rules for Explainable Link Forecasting) learns rules by random walks backward in time, scores path instantiations by rule confidence times an exponential recency decay, and combines paths with Noisy-OR. We keep its rule learner unchanged and replace only the scoring and aggregation.
For each query, the compiler builds the union from the formula above and checks it for safety using the Dalvi–Suciu-style criteria that Jung and Lutz adapt. For a safe union it emits a SQL plan built only from joins, products, and grouped Noisy-OR aggregation. An unsafe union remains solvable, only more slowly. For these we extract the lineage formula, which is a Boolean formula over the relevant tuples. We estimate its probability by Monte Carlo when it is large and compute it exactly by knowledge compilation when it is small.
An early empirical question is what fraction of ICEWS queries turn out safe. With both query endpoints fixed, rules of length two or less always produce safe unions. Longer rules that mix shared atoms may not. If most queries are unsafe, the method degrades to lineage sampling, and we will report that outcome as it is.
The second component is learning. On safe plans, $P(c)$ is a closed-form, differentiable composition of products and $1-\prod(1-\cdot)$, so we fit $\theta$ by maximizing the log-likelihood of observed training links against sampled negatives. On unsafe plans we use a straight-through sampling estimator. This addresses the "ad-hoc score grounding" problem from the file directly: the probabilities are fitted under the same semantics that uses them.
The third component is verification. Imprialou, Stoilos and Cuenca Grau (Benchmarking Ontology-Based Query Rewriting Systems) found that every rewriting system they tested was unsound or incomplete on some benchmark. For that reason, every compiled plan is checked on small subsampled instances against brute-force enumeration of possible worlds before any large-scale number is reported.
Baselines
The naive reference point is TLogic itself, run with its published rules and heuristic Noisy-OR. The file reports an ICEWS14 mean reciprocal rank (MRR) of 0.4304 for TLogic ( TLogic: Temporal Logical Rules for Explainable Link Forecasting on Temporal Knowledge Graphs). We will reproduce it on the same splits and filtering before comparing anything. TLogic is the strongest competitor because it is the same rule learner with the independence assumption left in. Any gain we show is therefore attributable to aggregation rather than to better rules.
The strongest neural reference is xERTE, which the file reports at MRR 0.4079 on ICEWS14 (from the TLogic paper). It is included to place the numbers in context rather than as the main target.
The truncation baseline follows the "Panel of Experts" heuristic of ExDB (Structured Querying of Web Text Data). It combines only the top five paths per candidate, and we also sweep $k$. The single-best-path, or max, aggregator is its limiting case.
All systems receive the same rule set, the same training window, and the same hyperparameter search budget. That budget covers the recency parameterization and the negative-sampling rate, and it is equalized across systems. Wall-clock time is reported on the same 8-CPU class of machine that the TLogic paper uses.
Two ablations isolate the key ingredient. The first, "exact semantics, heuristic probabilities," feeds TLogic's original path scores into the possible-worlds evaluation without refitting, so it measures the effect of deduplication alone. The second, "fitted probabilities, naive Noisy-OR," fits $\theta$ by likelihood but keeps per-path Noisy-OR, so it measures the effect of calibration alone. A third ablation replaces the shared rule event $E_\rho$ with per-grounding rule events, which tests which semantic choice matters.
On ranking, beating TLogic means a statistically significant MRR improvement over the reproduced TLogic across seeds on ICEWS14, ICEWS18 and ICEWS0515. For ICEWS18 and ICEWS0515 there is no reported result found on Lacuna for TLogic, so the reproductions there serve as the reference. On calibration, beating it means a lower Brier score and lower expected calibration error than every baseline, including post-hoc recalibrated ones. No reported calibration result for any of these systems was found on Lacuna.
Why not just…?
Why not just recalibrate TLogic's Noisy-OR output with temperature or isotonic scaling? This is the most serious threat. A single monotone map fitted on validation data may recover most of the calibration gain. It cannot, however, change the order of candidates within a query, because it applies the same monotone transformation to every score. Double-counting harms ranking specifically when one candidate has many overlapping paths and another has fewer independent ones. We will therefore apply isotonic recalibration to all baselines. We will also report MRR and calibration stratified by an overlap statistic, the ratio of distinct supporting tuples to supporting paths. If our gains vanish after recalibration and show no dependence on overlap, the core claim is falsified.
Why not just learn a discount on path count, such as Noisy-OR with a learned exponent? A global discount corrects the average amount of redundancy but not which paths are redundant. Two candidates with five paths each may share one tuple or none. The overlap-stratified analysis tests this directly, and we include a learned-exponent Noisy-OR as an additional baseline under the same tuning budget.
Why not just materialize every derived fact forward, then query? Ahmetaj et al. ( Ontology-Enriched Query Answering on Relational Databases) show that forward materialization is fast in deterministic settings. Materializing derived probabilities, though, bakes in exactly the independence error we are trying to remove, because a materialized derived tuple forgets which base facts it came from. Keeping the lineage is the fix, and it is what our compiler already does per query. Felix (Scaling Inference for Markov Logic via Dual Decomposition) additionally found that eager materialization of probabilistic intermediates is expensive.
Why not just use an end-to-end neural forecaster? Within this file, symbolic rule aggregation already outperforms xERTE on ICEWS14 at a small fraction of the training time. The question here is how to aggregate given rules, and a neural model does not answer it. Our method also keeps each prediction explainable as a set of supporting facts and rules.
Proposed Experiments and Decisive Checks
The main experiment compares all systems on ICEWS14, ICEWS18 and ICEWS0515, reporting MRR, Hits@k, Brier score, and expected calibration error. Every metric is also broken down by overlap stratum and by query safety.
A controlled synthetic study plants a known generative process. In it, a small set of noisy "hub" facts supports many paths, and we vary the degree of sharing. The study checks that our estimates track the true answer probabilities while Noisy-OR diverges as sharing grows.
A cost study reports the fraction of queries that are safe, the latency of SQL plans against lineage sampling, and the verification pass rate against enumeration of possible worlds.
A secondary transfer check applies the same aggregation to PathNet-style two-hop chains on WikiHop. The file reports an accuracy of 69.6% for PathNet ( Exploiting Explicit Paths for Multi-hop Reading Comprehension.). The check asks whether deduplicating shared intermediate passages helps a different aggregator: PathNet uses normalized sums rather than Noisy-OR.
The decisive result is the overlap-stratified comparison against recalibrated TLogic. If exact semantics wins mainly in high-overlap strata and the gap survives recalibration, counting shared evidence once is shown to matter for ranking and not only for calibration. If it does not, the contribution reduces to a calibration technique, and we will report it as that.
References
- Ontology-Based Access to Probabilistic Data with OWL QL
- Letter from the Special Issue Editor
- Letter from the Special Issue Editor
- Optimizing mpf queries: decision support and probabilistic inference
- Optimizing mpf queries: decision support and probabilistic inference
- An Approach to Probabilistic Data Integration for the Semantic Web
- Representing Ontology Mappings with Probabilistic Description Logics Programs
- TLogic: Temporal Logical Rules for Explainable Link Forecasting on Temporal Knowledge Graphs
- Benchmarking Ontology-Based Query Rewriting Systems
- Structured Querying of Web Text Data: A Technical Challenge
- Ontology-Enriched Query Answering on Relational Databases
- Ontology-Enriched Query Answering on Relational Databases
- Scaling Inference for Markov Logic via Dual Decomposition
- Exploiting Explicit Paths for Multi-hop Reading Comprehension.