Abstract
Probabilistic Logic Programming (PLP) combines the expressive power of logic with probabilistic reasoning, but its application to large-scale datasets has been limited by the "grounding bottleneck." Traditional PLP systems typically ground a logic program into a massive propositional formula before performing inference, a process that often fails on large knowledge graphs. This paper presents vProbLog, a system that overcomes this limitation by integrating formula construction directly into high-performance Datalog reasoning. By leveraging semi-naive evaluation and optimized magic sets, vProbLog enables efficient probabilistic inference over millions of facts.
Introduction
Probabilistic Logic Programming (PLP) is a cornerstone for reasoning under uncertainty in relational domains. However, state-of-the-art systems like ProbLog often struggle with scalability. The standard approach involves a two-step pipeline: first, grounding the logic program into a propositional formula, and second, performing Weighted Model Counting (WMC) on that formula. In domains like probabilistic Ontology-Based Data Access (pOBDA), the grounding step itself becomes the primary bottleneck, often consuming all available memory or timing out before inference even begins.
Methodology: Integrating Logic and Probability
The core innovation of vProbLog is the integration of formula construction directly into the reasoning process, bypassing the need for an explicit, separate grounding phase. The authors build upon the $T_{cP}$ operator, which tracks the provenance of derived facts as Boolean formulas.
Datalog-Inspired Optimizations
To achieve scalability, vProbLog incorporates three key techniques from the Datalog community:
- Semi-naive Evaluation: This technique avoids redundant computations by only considering new facts derived in the previous iteration. In vProbLog, this is adapted to update the associated Boolean formulas incrementally.
- Magic Sets Transformation: This optimization allows forward-chaining engines to focus only on facts relevant to a specific query, effectively mimicking backward-chaining behavior.
- Optimized Magic Sets ($vProbLog^{opt}$): The authors found that tracking probabilities for "magic" control atoms was unnecessary. By treating these as simple logical triggers, they significantly reduced the complexity of the generated formulas.
The system is implemented using VLog, a high-performance Datalog engine, and utilizes Sentential Decision Diagrams (SDDs) for the final WMC step.
Experimental Evaluation
The authors evaluated vProbLog against ProbLog2 across several benchmarks, most notably the Lehigh University Benchmark (LUBM), which tests scalability on large knowledge graphs.
As shown in the results for LUBM, vProbLog significantly outperforms ProbLog2. On LUBM010 (1 million facts), vProbLog provided exact answers for 10 out of 14 queries in seconds, whereas ProbLog2 failed to ground many of them. On the even larger LUBM100 (12 million facts), vProbLog still managed to solve several queries that were previously considered intractable for PLP systems.
On the WebKB dataset, vProbLog demonstrated its robustness. While ProbLog2's performance degraded as the problem size increased, vProbLog maintained consistent execution times and was able to provide results for larger instances where ProbLog2 could no longer perform exact inference.
Key Insights
- Leveraging Datalog Engines: High-performance Datalog engines are optimized for handling millions of facts. By embedding formula construction within these engines, PLP can inherit their scalability.
- Query-Driven Reasoning: The use of Magic Sets ensures that the system does not waste resources on irrelevant parts of the knowledge graph, which is crucial for large-scale pOBDA.
- Anytime Approximation: For cases where exact inference is too complex, vProbLog can provide lower-bound approximations by limiting the depth of reasoning, offering a flexible trade-off between speed and accuracy.
Conclusion and Future Work
vProbLog represents a significant step forward in scaling probabilistic logic to "big data" scenarios. By solving the grounding bottleneck, it opens the door for PLP in large-scale knowledge graph applications. Future work includes extending the system to support stratified negation and function symbols, as well as further automating anytime approximation strategies.
Summary updated