contrast to the ProbLog implementation presented here, Poole’s AILog2, an implementation of ICL, uses a meta-interpreter and is not tightly integrated with Prolog.

We contribute exact and approximate inference algorithms for ProbLog. We present algorithms for computing the success and explanation probabilities of a query, and show how they can be efficiently implemented combining Prolog inference with Binary Decision Diagrams (BDDs) [@Bryant86]. In addition to an iterative deepening algorithm that computes an approximation along the lines of [@Poole93:jrnl], we further adapt the Monte Carlo approach used by [@Sevon06] in the context of biological network inference. These two approximation algorithms compute an upper and a lower bound on the success probability. We also contribute an additional approximation algorithm that computes a lower bound using only the $k$ most likely proofs.

The key contribution of this paper is the tight integration of these algorithms in the state-of-the-art YAP-Prolog system. This integration includes several improvements over the initial implementation used in [@DeRaedt07], which are needed to use ProbLog to effectively query Sevon’s Biomine network [@Sevon06] containing about 1,000,000 nodes and 6,000,000 edges, as will be shown in the experiments.

This paper is organised as follows. After introducing ProbLog and its semantics in Section 