Introduction

Recently, there has been a rising interest in reasoning problems for Answer Set Programming (ASP) that go beyond the classical consistency problem. For example, LP MLN [2], P-log [3], PrASP [4], PASP [5] and Problog [6] allow for probabilistic reasoning. Weight Constraints and more generally the asprin framework [7] consider preferential reasoning over answer sets. Finally, algebraic Prolog [8] and Weighted LARS [9] capture and generalize both of these ideas in Algebraic Answer Set Counting (AASC), i.e. weighted answer set counting over semirings. While there are many frameworks allowing such specifications, the corresponding choice of solvers is limited: the clingo solver [10] performs answer set counting by enumeration, which becomes infeasible for millions of answer sets. The dynASP2.5 solver [11] focuses on programs of low treewidth. The Problog solver [12] reduces the problem to Algebraic Model Counting (AMC) [13], for which efficient solvers exist [14,15,16]. Other solutions exist for approximate probabilistic queries [17] or most probable answer set inference [18], which are outside of our scope as we aim for exact weighted answer set counting.

While Problog does not accept arbitrary ASP programs as input, we still consider its strategy to be the most promising approach. The basic idea, described in detail in [19], is the following. First one breaks the cyclic dependencies in the input program, obtaining a tight program, where the answer sets are the models of its Clark completion [20]. The Clark completion can then be compiled it into an equivalent d-DNNF/SDD representation, where AMC is possible in linear time [13]. This approach allows for practically relevant instances to be solved [21]. However, the way cycles in the program's positive dependency graph are broken can have a negative effect on the treewidth.

Cycle breaking is well studied in the ASP community. Among others, Hecher's [22] translation from ASP to SAT guarantees that the treewidth of the SAT instance is 𝒪(𝑘 log(𝑙)), where 𝑘 is the original treewidth and 𝑙 is the minimum of 𝑘 and the size of the largest strongly connected component of the dependency graph of the program. Unfortunately, this translation does not preserve models bijectively. In contrast, cycle breaking used in Problog [23,21] and others [24] preserve models without strong treewidth bounds. We address this and provide the following:

• We show that every program of treewidth 𝑘 can be translated into an acyclic program with treewidth at most 𝑘 • cbs(DEP(Π)), where cbs(DEP(Π)), is the component-boosted backdoor size of the dependency graph of Π; notably, cbs(.) is a novel parameter on directed graphs combining backdoor sets and decomposability to measure the cyclicity.

• We provide a prototype implementation aspmc that performs AASC by exploiting the constructive proof of the above result. Our experimental results show that when a program has many answer sets, aspmc outperforms Problog, clingo and lp2sat [24].

Algebraic Answer Set Counting

We assume familiarity with the basics of Answer Set Programming (ASP) [25] and use 𝒜(Π) and 𝒜𝒮(Π) for the atoms and answer sets of a program Π, respectively. We introduce AASC by using the following minimal instantiation Π 𝑠𝑚 of the smokers program, which is a standard example from probabilistic logic programming [6].

{stress(𝑥)} ←

for 𝑥 = 1, 2 smokes(𝑥) ← stress(𝑥)

for 𝑥 = 1, 2 {influences(𝑦, 𝑥)} ← for 𝑥 + 1 = 𝑦 mod 2 smokes(𝑥) ← influences(𝑦, 𝑥), smokes(𝑦)

for 𝑥 + 1 = 𝑦 mod 2

This encodes that for person 1 and 2 it is randomly determined whether they are stressed. If they are, they smoke. Furthermore, if one influences the other, which is again random, and smokes, then they also smoke. In order to introduce probabilities, we use algebraic measures.

𝜇(ℐ).

Measures "measure" values associated with answer set. AASC is then to evaluate 𝜇(𝑎), i.e., to sum up the weights of all answer sets that satisfy 𝑎. We do not focus on any particular application of AASC.

Usually, measures are not necessarily factorized and allow complex terms of sums and products to define the weight of an answer set. Furthermore, they are defined not only for weights over the reals but over any semiring. We stick to the restricted definition above for simplicity.

We can assign probabilities using the measure 𝜇 𝑠𝑚 = ⟨Π 𝑠𝑚 , 𝑓, 𝐹 ⟩, where

𝑓 (stress(𝑖)) = 0.4 𝑓 (¬stress(𝑖)) = 0.6 𝑖 = 1, 2 𝑓 (influences(𝑖, 𝑗)) = 0.3 𝑓 (¬influences(𝑖, 𝑗)) = 0.7 𝑖 + 1 ≡ 𝑗 mod 2

This means that the probability of a person being stressed is 0.4 and the probability that a person influences their friend is 0.3. Therefore, the answer set

ℐ = {stress(1), smokes(1)} has probability 𝜇 𝑠𝑚 (ℐ) = 0.4 • 0.6 • 0.7 2 .

The query 𝜇(smokes( 1)) corresponds to the probability that person 1 smokes. To evaluate it we need to perform AASC, i.e., sum up the probabilities of all answer sets s.t. smokes(1) holds. Currently, the most promising strategy to perform AASC is the one used by Problog [19]. Here, the general idea is to compile the program Π into an equivalent tractable circuit representation 𝐶, like SDD [26] or sd-DNNF [27]. When this succeeds, AASC is possible in linear time in the size of the circuit 𝐶. However, while there are so called knowledge compilers that perform this task, they can only work on propositional formulas.

Evaluation PipelineGround Break Cycles Clark Completion Knowledge Compilation Evaluation 𝜇 Π Π ′ 𝜑 𝐶 𝑝

The whole pipeline that we and (similarly) Problog use is therefore as in Figure 1. Given an algebraic measure 𝜇, we first ground the logical part of the measure, obtaining a ground program Π. Next, Π is translated into an equivalent program Π ′ , which is acyclic, i.e., which does not contain rules with cyclic positive dependencies. For such programs it is known [20] that the Clark completion of Π ′ results in a propositional formula 𝜑, whose models correspond one-to-one to the answer sets of Π ′ . Thus, by compiling 𝜑 into a tractable circuit representation 𝐶, using a tool like c2d [28], we can obtain the probability 𝑝 as the final result.

Treewidth-Aware Cycle Breaking

Our contribution in [1] focused on the second step in this pipeline, by introducing an algorithm that breaks cycles in a treewidth-aware fashion. Finding an equivalent and acyclic program Π ′ of low treewidth can be beneficial since there are performance guarantees for knowledge compilation based on treewidth [26]. This motivates our main result for cycle-breaking: Theorem 2. For any measure 𝜇 = ⟨Π, 𝑓, 𝐹 ⟩, there exists a measure 𝜇 ′ = ⟨Π ′ , 𝑓, 𝐹 ⟩ with an acyclic program Π ′ s.t.

• for all 𝑎 ∈ 𝒜(Π) it holds that 𝜇(𝑎) = 𝜇 ′ (𝑎),

• the treewidth of Π ′ is bounded by 𝑘 • cbs(DEP(Π)), where 𝑘 is the treewidth of Π.

Here, cbs(DEP(Π)) is a novel parameter, called component-boosted backdoor size, which intuitively measures the cyclicity of the dependency graph of Π. It is defined as follows:

Definition 3. Let 𝐺 be a digraph. Then, the component-boosted backdoor size cbs(𝐺) is • 1, if 𝐺 is acyclic (which includes 𝑉 (𝐺) = ∅)

• 2, if 𝐺 is a polytree, i.e. the undirected version of 𝐺 is connected and acyclic

• max{cbs(𝐶) | 𝐶 ∈ SCC(𝐺)}, if 𝐺 is cyclic but not strongly connected • min{cbs(𝐺 ∖ 𝑆) • (|𝑆| + 1) | 𝑆 ⊆ 𝑉 (𝐺)} otherwise

As the name suggests, 𝑐𝑏𝑠 generalizes the idea of backdoors, which have already been considered in the context of ASP [29]. In our context, a backdoor for a digraph 𝐺 is a vertex set 𝑆, such that 𝐺 ∖ 𝑆 is a polytree, polyforest or dag. The backdoor size of 𝐺 is the minimum size of a backdoor for 𝐺 plus 1. Note that our parameter additionally considers that 𝐺 ∖ 𝑆 may consist of separate SCCs that can be handled recursively and is therefore bounded by backdoor size.

The proof of Theorem 2 is constructive, in the sense that it allows the formulation of an algorithm that computes Π ′ . Broadly speaking, the idea is to gradually introduce copies 𝑎 (1) , . . . , 𝑎 (cbs(DEP(Π))) of each atom 𝑎 that better and better approximate the meaning of 𝑎. For this, we copy all rules 𝑎 ← 𝑏 1 , . . . , 𝑏 𝑛 , not 𝑐 1 , . . . , not 𝑐 𝑚 and replace them by 𝑎 (𝑖) ← 𝑏

(𝑗 1 )

1 , . . . , 𝑏 (𝑗𝑛) 𝑛 , not 𝑐 1 , . . . , not 𝑐 𝑚 , thus expressing the truth of 𝑎 (𝑖)) in terms of already known approximations of 𝑏 1 , . . . , 𝑏 𝑛 . Theorem 2 guarantees that, if we consider the atoms in the correct order, a fixed point can be reached after considering each atom at most cbs(DEP(Π)) times. We cannot go into details here due to lack of space but refer interested readers to the full paper [1]. Nevertheless, we can apply Theorem 2 to our running example and obtain Π ′ 𝑠𝑚 as

{stress(𝑥)} ← for 𝑥 = 1, 2 {influences(𝑦, 𝑥)} ← for 𝑥 + 1 = 𝑦 mod 2 smokes(1) 1 ← stress(1) smokes(1) 1 ← influences(2, 1), ⊥ smokes(2) ← stress(2) smokes(2) ← influences(1, 2), smokes(1) 1 smokes(1) ← stress(1) smokes(1) ← influences(2, 1), smokes(2)

Observe, that Π ′ 𝑠𝑚 has the same answer sets with respect to the original atoms and is acyclic. Also the treewidth of Π ′ 𝑠𝑚 has increased by at most 1, since only the atom smokes(1) 1 was added.

Comparison to other Cycle-Breaking Algorithms

There exists a wide variety of algorithms for cycle-breaking in the ASP literature [24,23,22,30]. However, since most ideas were originally intended for ASP, where it suffices to find one answer set, some of these algorithms do not preserve the original models bijectively [22,30]. The remaining two ideas preserve answer sets bijectively. As such, Janhunen's [24] was considered for the implementation of Problog (cf. [31]) and Mantadeli's and Janssen's [23] is even still part of the standard Problog implementation. While the original papers did not consider the effects that these translations have on treewidth, the strategy to bound treewidth used in [1,22] can be applied to these translation as well. This results in treewidth upper-bounds of 𝑘 log 2 (𝐶 max ) and 𝑘𝑍, respectively, where 𝐶 max is the size of the largest strongly connected component of the dependency graph of Π and 𝑍 is the largest number of simple (directed) cycles that any atom is contained in.

One can show that 𝑐𝑏𝑠(.) is always bounded by 𝑍 and possible exponentially smaller, since on a clique of size 𝑛, we have 𝑍 ≥ 2 𝑛−1 , whereas 𝑐𝑏𝑠(.) of a clique of size 𝑛 is 𝑛. Therefore, Theorem 2 provides strictly better treewidth bounds in general. Observe, however, that for the first translation, the factor grows logarithmically in 𝐶 max . It follows that for a clique of size 𝑛 the upper-bound 𝑘 log 2 (𝑛) of the first translation is exponentially lower than 𝑘𝑛, which is our bound. On the other hand for a polytree 𝑇 with 𝑛 vertices 𝑐𝑏𝑠(𝑇 ) = 2, whereas log 2 (𝑛) is not constant.

Implementation & Experiments

We implemented a system that adheres to the evaluation procedure above, resulting in the prototypical solver aspmc 1 . aspmc is written in Python3 and allows for Problog programs Π as input in order to compute the answers to probabilistic (resp. algebraic) queries in Π.

Benchmark Setting. In order to evaluate the performance of aspmc, we compare the computation of probabilities for atoms of Problog programs. For solvers that are not able to evaluate probabilistic queries we compute the number of answer sets.

Compared Solvers.

In our experiments, we mainly compare against Problog 2.1.0.42 with the arguments "-k sdd", clingo 5.4.0, where we used arguments "-q -n 0" in order to count answer sets, as well as lp2sat+c2d, where instances are translated [32] to CNFs by lp2normal 2.18 in combination with lp2atomic 1.17 and lp2sat 1.24 with answer sets being counted with c2d version 2.2 [28]. Our system is aspmc+c2d, which breaks the cycles and performs AASC on a tractable circuit representation of the constructed CNF, obtained via c2d 2.2.

Benchmark Instances. The instances we used are the benchmarks from [33] and were kindly provided to us by the authors via personal communication. They adhere to typical benchmark domains consisting of 490 instances of the standard smoker's example, 50 instances of the gene's problem [34] and 63 web knowledge base instances [35].

Benchmark Platform. All our solvers ran on a cluster consisting of 12 nodes. Each node of the cluster is equipped with two Intel Xeon E5-2650 CPUs, where each of these Experimental Results & Discussion. In our evaluation, we mainly compare total wall clock time and number of solved instances. Concerning benchmark limits, we consider a timeout of 1800 seconds and an 8 GB RAM limit per instance and solver. Figure 2 (left) shows a plot over all instances, which indicates that aspmc+c2d solves more instances faster than any of the other configurations that we benchmarked. The detailed results in Figure 2 (right) indicate that cycle breaking works well for probabilistic reasoning.

Other experiments [1] showed that clingo is extremely fast at enumerating solutions. Thus, on instances with not that many solutions, clingo is faster than any of the compilation-based approaches we considered. On the other hand, when there are more solutions, considering each of them once as in enumeration, is outperformed by the compilation-based approaches lp2sat+c2d, aspmc+c2d and Problog that solve significantly more instances in this case.

Conclusion and Future Work

For any program Π, there is an equivalent acyclic program, whose treewidth is at most cbs(DEP(Π)) times bigger, where cbs(.) is a novel parameter that measures the cyclicity of directed graphs. The bound on the treewidth provides us with worst case guarantees for the knowledge compilation step in AASC. Our experimental evaluation of the prototype implementation aspmc shows that this idea does not only provide interesting theoretical results but provides a significant speedup on standard Problog benchmarks compared to other solvers.