Abstract
Uncertain Temporal Knowledge Graphs (UTKGs) present a significant challenge for automated reasoning due to the intersection of probabilistic uncertainty and time-varying facts (fluents). This paper proposes a formal framework that extends Markov Logic Networks with numerical constraints to automatically "debug" and clean noisy temporal data. By mapping UTKGs to first-order logic and utilizing Maximum A-Posteriori (MAP) inference, the authors demonstrate a robust method for resolving conflicts in large-scale knowledge bases.
The Challenge of Noisy Fluents
Most modern Knowledge Graphs (KGs) are constructed using "machine reading" or Open Information Extraction (OIE). While powerful, these tools are notoriously noisy, often producing facts with confidence scores but struggling with fluents—facts that are only true for specific periods.
The core difficulty lies in the fact that uncertainty and time are typically treated in isolation. For example, an extraction tool might assign high confidence to a soccer player's birth year and a separate high score to a career event decades later. Individually, these facts appear valid; together, they may be biologically or logically impossible. This research addresses the need for a unified system that employs temporal logic and numerical constraints to "debug" these conflicting probabilistic facts.
Formalizing the Debugging Process
The authors formalize the cleaning process as an optimization problem. Given an uncertain temporal KG, a set of inference rules, and optional constraints, the system must output the most probable conflict-free version of the graph.
Methodology: Numerical MLNs and Constraints
To bridge the gap between KGs and probabilistic logic, the authors utilize several key techniques:
- Numerical Markov Logic Networks (MLNs): MLNs attach weights to first-order logic formulas. The authors extend these with numerical capabilities to handle arithmetic, such as calculating age from birth dates.
- Temporal RDF/S Rules: Standard Semantic Web entailment rules are adapted to include time intervals $[t_1, t_2]$, ensuring that inferred facts respect temporal bounds.
- Datalog-Inspired Constraints: The system uses Inclusion Dependencies (IDIs), (In)equality Generating Dependencies (IGDs), and Disjointness Constraints (DCs) to act as "hard" filters. For instance, a DC might specify that a person cannot be a coach before they are born.
The cleaning process is executed via Maximum A-Posteriori (MAP) inference, which identifies the most probable "world" where no hard constraints are violated.
Conflict Resolution in Practice
A key insight of this work is that probabilistic weights alone are insufficient for cleaning a KG. Domain-specific temporal constraints are required to prune logically impossible errors, even if those errors have high confidence scores.
In the case of Claudio Ranieri, the system can successfully discard a high-weight erroneous fact (such as a wrong birth year) when it conflicts with a set of lower-weight but temporally consistent facts (such as a career timeline). This demonstrates the framework's ability to prioritize logical consistency over raw extraction confidence.
Complexity and Future Directions
The paper provides a rigorous mathematical mapping between temporal KGs and First-Order Logic, proving that KG cleaning can be treated as a standard logical inference problem. However, the authors also characterize the significant computational costs: MAP inference is NP-hard, and calculating exact probabilities is #P-hard.
Future work aims to address these scalability concerns through "lifted inference"—reasoning about groups of objects rather than individuals—and the development of standard "uncertain temporal" benchmarks to facilitate community-wide testing.
Summary updated