Abstract
State-of-the-art inference approaches in probabilistic logic programming typically start by computing the relevant ground program with respect to the queries of interest, and then use this program for probabilistic inference using knowledge compilation and weighted model counting. We propose an alternative approach that uses efficient Datalog techniques to integrate knowledge compilation with forward reasoning with a non-ground program. This effectively eliminates the grounding bottleneck that so far has prohibited the application of probabilistic logic programming in query answering scenarios over knowledge graphs, while also providing fast approximations on classical benchmarks in the field.
Introduction
Probabilistic Logic Programming (PLP) provides a robust framework for reasoning under uncertainty in relational domains, such as social networks and biological pathways. However, the practical application of PLP to large-scale Knowledge Graphs (KGs) has been hindered by the "grounding bottleneck." Traditional PLP systems follow a "ground-then-solve" paradigm: they first generate all possible ground instances of rules and then construct a massive propositional logic formula to compute probabilities. On large KGs, the number of groundings grows exponentially, often exhausting memory and time resources before inference can even begin. This report introduces vProbLog, a system designed to bypass this bottleneck by leveraging high-performance Datalog techniques.
Methodology
The core innovation of vProbLog is the integration of formula construction directly into the reasoning process, treating it as a Datalog materialization problem. This approach utilizes two primary optimization techniques:
1. Semi-naive Evaluation for $T_{c\mathcal{P}}$
The $T_{c\mathcal{P}}$ operator is used to build logic formulas during forward reasoning. By implementing a "semi-naive" version of this operator, vProbLog only computes changes between iterations. This avoids redundant computations and significantly accelerates the fixpoint process.
2. Magic Sets Transformation
To ensure that reasoning remains focused on the query, vProbLog employs the Magic Sets transformation. This technique effectively makes forward reasoning behave like backward reasoning by injecting "magic" predicates that prune the search space to only those paths relevant to the specific query.
The system aims to efficiently construct the propositional formula for a query $q$, which can be represented as a disjunction of conjunctions of probabilistic facts, as shown in the figure above. This formula serves as the basis for weighted model counting.
3. vProbLog Implementation
vProbLog is built upon VLog, a state-of-the-art Datalog engine. It transforms PLP rules into specialized Datalog rules that manage formula identifiers and perform logical equivalence checks using Sentential Decision Diagrams (SDDs). An optimized version, vProbLog-opt, treats "magic" atoms as simple truth values to further reduce overhead.
Experimental Evaluation
The system was evaluated across several benchmarks, demonstrating significant improvements over existing tools like ProbLog2.
- LUBM (Lehigh University Benchmark): In scenarios ranging from 19,000 to 12 million facts, vProbLog successfully answered queries in seconds. Standard systems typically timed out during grounding even on the smallest datasets.
- WebKB, Smokers, and Genes: On these complex benchmarks, vProbLog proved to be orders of magnitude faster for exact inference and provided higher-quality lower-bound approximations for queries where exact inference was intractable.
Discussion and Future Work
While vProbLog successfully addresses the grounding bottleneck, certain challenges remain. The current implementation focuses on programs without negation and does not yet support existential quantifiers common in some ontology languages. Furthermore, while grounding is no longer the primary constraint, the "compilation bottleneck"—where the logic formulas (SDDs) themselves become too large—can still occur for highly complex, cyclic queries.
Future work will focus on extending the system to support stratified negation and developing "anytime" algorithms that can automatically adjust reasoning depth to provide the best possible approximations within a fixed time budget.
Summary updated