Learning Fast-Inference Bayesian Networks
Authors: Vaidyanathan Peruvemba Ramaswamy
Stefan Szeider
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bayesian Network Structure Learning
Exact Probabilistic Reasoning
MaxSAT
Propositional Satisfiability

Abstract: We propose new methods for learning Bayesian networks (BNs) that reliably support fast inference. We utilize maximum state space size as a more fine-grained measure for the BN's reasoning complexity than the standard treewidth measure, thereby accommodating the possibility that variables range over domains of different sizes. Our methods combine heuristic BN structure learning algorithms with the recently introduced MaxSAT-powered local improvement method (Peruvemba Ramaswamy and Szeider, AAAI'21). Our experiments show that our new learning methods produce BNs that support significantly faster exact probabilistic inference than BNs learned with treewidth bounds.

Learning Fast-Inference Bayesian Networks
Vaidyanathan Peruvemba Ramaswamy Algorithms and Complexity Group TU Wien, Vienna, Austria vaidyanathanGac. tuwien. wn...n............
Stefan Szeider Algorithms and Complexity Group TU Wien, Vienna, Austria szfac. twwien. .ct
Abstract
We propose new methods for learning Bayesian networks (BNs) that reliably sup- port fast inference. We utilize maximum state space size as more fine-grained measure for the BN's reasoning complexity than the standard treewidth measure, therehy accommodating the possibility that variables range over domains of differ- ent sizes. Our methods combine heuristic BN structure learning algorithms with the recently introduced MaxS MaxSAT-powered local improvement method (Peruvemba Ramaswamy and Szeider, AAAI'2I), Our experiments show that new learning methods produce BNs that support significantly faster exact probabilistic inference than BNs learned with treewidth bounds.
Introduction
The time complexity of probabilistic reasoning on a Bayesian Network (BN) dominated by the maximum state space size of clusters (i.e., bags of the BN's tree decomposition [Lauritzen and Spiegelhalter, 1988 Dechter 1999 Kask et 2011] a bag's state space size the product of the domain sizes of all the variables contains). We propose algorithms for learning BNs from data, keeping the state space size within a user-specified bound. This results in fast-inference BNs, i.e., BNs reliably admitting fast probabilistic reasoning. We compare our algorithms to the baseline of state-of-the-ar bounded treewidth BN learning algorithms, on real-world benchmark data sets, with up over thousand variables. The results show a clear advantage for new bounded state space (bss) algorithms.
It is common encounter non-binary variables in real-world data. Moreover, during our preliminary analysis, we noticed that even variables with domain sizes as small as 4 were sufficient to impact the reasoning times significantly. This is in agreement with the fact that the reasoning time has exponential dependence on the domain sizes. For instance, consider some of the networks learned for alarm and hepar2 having 37 and 70 variables, respectively. Both these datasets were learned with small values of treewidth, and the maximum domain size of the variables is 4. Despite this, they exhibited reasoning times in the order of magnitude of 2.5 seconds.
For our bss BN structure learning algorithms, we build upon recent work on bounded treewidth BN structure learning, particularly on the heuristic algorithms k-greedy and k-MAX by Scanagatta et al. [016 2018 as well BN-SLIM by Peruvemba Ramaswamy and Szeider 2021a The latter is a post-processing algorithm that uses MaxSAT improve BNs generated by the heuristics. All these algorithms assume a user-specified upper bound & for the treewidth of the learned BN and optimize the BN's score under the given treewidth bound. The learning algorithms are highly optimized for dealing with large instances, and so the generalization of treewidth bounds to state space bounds isn't 't straightforward. The main challenge for extending BN-SLIM bss learning simple cardinality constraints with a MaxSAT encoding that bounds the state-space of a bag, i.e., product of integers. We achieve this by switching to logarithms and bounding the sum of real numbers, utilizing MaxSAT encoding based on binary decision diagrams (BDDs).
replace BN-SLIM's
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

We consider several variants of bss learning algorithms, tested them on 16 real-world benchmark data sets with up to 1041 variables, and compare them with bounded treewidth BN learning algorithms. For the comparison, we put pairs of scatter plots side by side, which show the tradeoff between reasoning speed and data-fitting (score), one for the baseline methods and one for the bounded state space methods. The bounded state space methods show better performance throughout, with significantly higher reliability (small variance).
1.1 Related Work
We discuss related work in terms of Figurel
I In approaches (a) and (b), the BN has already been
bounded treewidth
(a)
Sample Data
BN
Tree Dec
bounded state space
(b) Sample Data
BN
Tree Dec
maximize score, bounded treewidth
(c) Sample Data
BN, Tree Dec
maximize score, bounded state space
(d)
Sample Data
BN, Tree Dec
(new)
Figure 1: Various approaches to BN structure learning
learned by some other method, and one tries to find a tree decomposition that minimizes either the treewidth or the maximum state space size, respectively. For approach (a), -enerrl-purpose tree decomposition algorithms can be applied, such as the one byGGogtte and Dechter [2004). As
the significance of the state space of BNs was recognized [Lauritzen and Spiegelhalter 1988 J the
research focused on approach (b) [Kask et al. 2011 Kærulff |992| Meila and Jordan 1996 Otten and
Dechter 2008a b). However, once the BN has been fixed, the impact of the decomposition method is limited. Therefore, the research in the last decade focused on approach (c), where a treewidth bound already considered during the BN learning; a suitable decomposition is produced simultaneously. On the one hand, exact learning algorithms have been proposed that scale only to small instances but find score-optimal BNs (Korhonen and Parviainen, 2013 Parviainen al.) 2014] Berg et al., 2014). On the other hand, heuristic algorithms have been proposed that scale to large instances but do not guarantee score optimality [Nie et al. 2015 2016 Scanagatta et al. 2016 2018 Benjumeda ct al. 2019]. Recently, |Peruvemba Ramaswamy and Szeider [202 la proposed the hybrid approach ANNSLLM, which improves the score of a heuristically computed BN by multiple applications of a MuxSAT-based exact method.
In this paper, we follow for the first time approach (d) and implement it via various scalable algorithms. Our experiments compare approaches (c) and (d) in terms of the achieved score and inference speed.
2 Preliminaries
2.1 Graphs and Digraphs
We consider both undirected and directed graphs G. where V(G) denotes the set of vertices and E(G) the set of edges G, respectively. If directed, we refer to its edges as arcs. A directed graph is DAG if it doesn't 't contain any directed cycles.
2.2 Structure Learning
Assume we are given a data set of samples Di...., Dry over n categorical random variables, each variable v ranging over domain of ds(v) many discrete values. The goal of the BN structure learning problem is to find a DAG D, whose vertices are the random variables, that fits the data best. The fitting is modeled employing a real-valued score function. The BN is formed by the DAG D and local parameters [Koller and Friedman, 2009]. More precisely, the score function assigns each node V(D) and each subset P C V {v] the score fP(v) of P for v. Let

---

PD(t) (uEV:= (u.z) } denote the parent set of in D. The score f(D) of D is the sum of f(c,Pp(t)) over all v VDD). Score functions defined in such way (decomposable score functions) accommodate popular scores like AIC, BDeu, and BIC [Akaike 1974 Heckerman et al. 1995. Sccwwarz T978]. score function cache is obtained from score function by disregarding any potential parent set P' of node v if f(v, P') S f(, P) for another potential parent sets of with P Ç P. Consequently, a score function cache does not consider a nonempty potential parent set if its score doesn't I exceed the score of the empty parent set.
2.3 Tree Decomposition
Consider an undirected graph G. A Iree decomposition T of G is pair (T,x), x), consisting of a tree T and mapping X (TT) + 2V))), where the set x(t) is called a bag, with the following properties.
1. For every edge e E E(G) there is some t E V(T) such that e S x(t).
2. For every vertex v E V(G), the set {t E V(T) u E x(t) } induces non-empty subtree T.
The moralized graph MD) of DAG D is defined by V(M(D)) V(D) and E(M(D)) {fu, v} (u, v) F(D) U {u, v) : (u, w). (v, w) E E(D), u * v). A tree decomposition of a DAG is tree decomposition of its moralized graph. A tree decomposition of BN is tree decomposition of its underlying DAG.
3 Treewidth and Maximum State Space Size
In this section, we discuss the different metrics that be used estimate the inference speed of BN along with some empirical findings.
Consider tree decomposition T = (T, x) of DAG D, where V(D) consists of random variables, each a E V (D) ranging over a set of ds(v) many discrete values.
The width of T is
The maximum state space size of T is
max Ix(t) 1, (TV(T)
max LEV (T'
II ds(v), eEX(()
ie.. is the size of largest bag minus 1. The treewidth tw(D) of D is the minimum width over all tree decompositions of MDD).
i.e., largest state space size of all bags, where the state space of a bag is the product of the domain sizes of the variables it contains. The maximum state space size msss(D) (D) of a D is the minimum misss over all tree decompositions of M(D).
The maximum state space of binary BN of treewidth f is 21+1 The hounded treewidth (state space, respectively) BN structure learning problem takes input set V of nodes (i.e., random variables), a decomposable score function f on V, and an integer k, and asks to compute a DAG D with (DD) V of treewidth (maximum state space size, respectively) most ks with maximal score f(D).
3.1 Empirical Influence on Inference Speed
Complexity results for probabilistic reasoning (inference) suggest that for BNs containing non- binary variables, maximum state space size provides more accurate prediction for inference speed than treewidth [Lauritzen and Spiegelhalter] 1988 Dechter 1999 Kask et al. 2011). Our initial experiments aimed to verify this theoretical assumption empirically. For this purpose, we generated several BNs with varying treewidth and maximum state space size and analyzed the impact of these two measures on the BN's inference speed. We define a BN's reasoning time as the time required for computing the probability of evidence of 5 random variables set to random states, averaged over 100 runs (same as [Scanagatta et al. 2016)). For more details on the experimental setup, we refer to Section 5
Figure 2 depicts the distribution of the observed reasoning times for different treewidth and maximum state space size ranges utilizing boxplots, with dots signifying outliers. We observe that the correlation
3

---

35
Mean Reasoning Time (in
25
20
15
10
23.44.66.1.488.
(ogz(mess)
Treewidth
Figure 2: Comparison of correlation of treewidth and maximum state space size with reasoning time
between reasoning time and maximum state space size much stronger than the correlation between reasoning time and treewidth. The number of outliers is much higher in the treewidth plot as compared the maximum state space size plot. Furthermore, for gradually increasing reasoning time thresholds, the corresponding maximum state space size, for which none of the BNs exceed the reasoning time, grows much more gradually than the corresponding treewidth.
These results provide a solid basis for our objective to develop algorithms that already bound maximum state space size during BN structure learning, will lay out in the next sections.
BN Learning of Bounded State Space Size
4.1 Modified Heuristics
We now describe the modifications we made to the k-MAX and k-greedy heuristics to operate with bound on the state space.
Now, we give brief outline of the k-greedy algorithm. Let us assume a treewidth bound of k. The algorithm starts from random ordering of the random variables. Initialization: It then initializes the first bag with the first k++ variables. It computes the best DAG over these variables either by an exact method or by approximate method depending on the value of k Addition: Then, the algorithm iteratively adds variables to this DAG with parent sets that maximize local score. While doing so, the algorithm searches through the existing k-cliques potential parent sets. Termination: The iteration continues until there are no variables left to add.
To make the k-greedy algorithm work for bounded state space, we first modify the Initialization step. Let a = 11, ......, Un be the randomly sampled ordering. Instead of simply picking the first le variables, the condition II-=1 2 I k. In the Addition step, we no longer treat all existing k-cliques as potential parent sets. Instead, when adding variable v, only consider those sets S for which Iu ds(u)= < k.
pick the first p variables such that is the largest integer satisfying
The k-MAX algorithm similar to the k-greedy algorithm but picks the variables based on scoring system instead of following a particular variable ordering. The modifications we propose for the k-greedy algorithm can, however, be easily adjusted to work for the k-MAX algorithm by incorporating domain-size checks in place of cardinality checks.
We thus obtain the following algorithms:
k-greedy and k-MAX refer to the original two heuristics proposed by |Scanagatta et al. 2016 2018 that return bounded treewidth BNs.
k-greedy bis and k-MAXbss refer to the modified versions k-greedy and k-MAX with the proposed modifications that return bounded state space BNs.
As side effect, all these algorithms produce a tree decomposition that witnesses the treewidth or state space bound of the obtained BN.

---

4.2 Local Improvement
In this section, we explain how the local improvement framework of Peruvemba Ramaswamy and Szeider [2021a] can be extended and utilized for the bounded state space BN structure learning problem.
Throughout this section, consider an instance of the bounded state space BN structure learning problem, consisting of set V of random variables, score function f, and state space bound k. Initialization: We first use a heuristic (such as described in Subsection [4.]) to compute an initial solution D. together with maximum state space size S k. The local improvement step uses the parameter budget B which controls the size of the local instance. Subtree selection: We select subtree S of T such that Vs := UIEV(S) x(t) does not exceed the budget B. Our aim is to compute for each E Vs new parent set, optimizing the score of the resulting DAG Deww with V (DDew) V. We define D as the DAG induced by Vs where ( = { (u, v) E ((D (u, S Vs }- We distinguish between different kinds of nodes:
decomposition
(I', x) of the moralized graph M (D) with
V E Vs a boundary vertex if there exists a tree node t V(T) \ ((S) such that e E x(t);
v Vg is an internal vertex if is not boundary vertex;
V \ Vs is external vertex.
Two boundary vertices v, vf are adjacent both oceur together in some bag outside S. In that case we call {e, r'} virtual edge. We let Evia be the set of all virtual edges. The extended moral graph Meat obtained from M (Dig)) by adding all virtual edges. If c, v' are two adjacent boundary vertices such that Deew contains directed path from v' to v, where all the vertices on the path, except for v' and v, are external, then (v', v) is a virtual arc. Evi denotes the set of all virtual arcs.
We call n a weel-beeaeedd DAG with respect to DAG D and its tree decomposition (T, if the following conditions are satisfied:
1. D is acyclic.
2. For each v E V(Mex). Prrm (v) contains external vertices, then there is some t e V(T) \ (SS) such that Pa (t) U (v) C (t).
3. The digraph with vertex set V(Mex) and are set E(DS))) U Evin)) is acyelic.
Let T= = =T, be tree decomposition of DAG D. We call Thew (Tnew now) conservative tree decomposition of DAG new with respect to set S T
1. Thew is a tree decomposition of DAG Deew,
2. nnw can be partitioned into Snew .Ti..... ,.....,,,, T,, where Ti...., T2 are the connected compo- nents Tf \ VSS). and
3. X new (t) = (t) for E VTT).
Lemma 1. If Daw is well-behaved then Drew is acyclic and f(D 2 S(D).
Proof. The correctness follows from (Peruvemba Ramaswamy and Szeider, 2021a Theorem 1]. as the statement of the lemma is identical except the treewidth constraints. We note that any tree decomposition such a D is conservative with respect to S.
Introducing a state space bound to Lemma T
we obtain the following theorem.
Theorem 1. If D is well-behaved and admits tree decomposition with msss at most k, then
1. neew is acyclic,
2. the score of Deew is least the score of D. and
3. Duew < k.
Proof. The first two properties follow from Lemma 1 Now, let T (T,x) be the tree decomposition of DAG D. Thew (Trew xx new) be the tree decomposition of DAG Deew and gnew (Stow X
new)
5

---

be the tree decomposition of Se Since Snew is conservative with respect to S (from Lemma D we can express new new (t) if t E S and xt) otherwise. order prove the third property, need to bound the state space size of the bags of Tuo i.e., we need to bound
max 1E7
(1)
ds(v) = max
max rES
(EX
ds(w),
max (ST
II ILxxx ds(r))
< max
k, max tET
II DEX(() ds(v)
[msss( [msss(Dgg)) (5 S k]
x max (k, k)
(msss(D)= S k].
Thus, the maximum state space size of Dnew at most k.
4.3
MaxSAT Encoding
We now describe how we construct the (weighted, partial) MaxSAT instance that encodes the conditions required on the local instance S. The instance a propositional formula in conjunctive normal form (CNF), with hard clauses and soft clauses; each soft clause has a weight. The MaxSAT solver tries to find a truth assignment that satisfies all the hard clauses and maximizes the sum of weights of satisfied soft clauses. We take as input the local instance S, the set of virtual edges Evin- the set of virtual ares E and the bound on the maximum state space size and produce MaxSAT instance &s. We reuse parts of the encoding proposed by |Peruvemba Ramaswamy and Szeider [0211] (we will refer to as the BN-SLIM encoding), extending an encoding proposed by Samer and Veith 2009) for capturing the tree decompositions.
Let |S| denote the size of the subinstance. We now reiterate the hard clauses from the BN-SLIM encoding and refer to the conjunction of these clauses as the formula 4 For an explanation of the semantics of these variables and clauses, we refer the source (Peruvemba Ramaswamy and Szeider 2021a
(acyc", acye + acyc (ord", A ord + ord"
for distinct u, U, S.
arcc,.
for E S.
EPEP, par par + acyc u,o
for E S.
for v E 5, P E Po, and u E P.
(par," A ord,,.) arCu,v
for E S,P E P., and E P.
(par," A orde.u)
+ arC
(par," A ordy,
+ a,
for E S, E Po, and u, w. E P.
(par," A ordw,,)
+ arc
(arc,,, A arc,,w A ord,,w)
+ arC
for u, E S.
(arc,,, arC A ord arc
arc,,, V arC
for u, E S. for {u, v) E Evin-
ord 0,0
arc ord n,u arc
par
acyc
for E S, E Pe, and (u, v) E (u P).
We also add the following soft clauses to D's, setting fiz(v) = fp(v) - fo(v) as their weight (par,") weight (1) for v E S,
The weight of solution to E's is given by the sum of weights of the satisfied soft clauses. Let W Eves (v, PD(v)) be the core of the unmodified local instance S.
Lemma 2. V's admits solution of weight W Wnnew if and only if there exists a well-behaved DAG Deww with respect to D, such that f(Deew) S(D) = Wenew W.
Proof. We can use the proof of [Peruvemba Ramaswamy and Szeider 2021a Theorem 2] to establish the lemma, since the only difference the clauses that upper bound treewidth of DEE Therefore D

---

is still acyclic, Further, an assignment that corresponds to setting D = Sg achieves the lower bound on the score.
4.4 BDD-based Counter
1=0
/= 1
1.6
1= 2.6
Figure 3: Example BDD constructed for three variables 01, 22, vs with domain sizes 2, 2,3, 4, respectively, and with k = 6. The loga- rithms of the domain sizes are 1, 1.6, 2, respectively. The solid and dashed edges represent the 'if" and 'else'
111.0 0)
respectively. The path (x1,0) 0) [22,, 1) - (I3, 2.6) TRUE represents the bag contain- ing i1 and #2 with a state space size of Σ k. hence reaching TRUE. The path (x1, 0) - (22. 1) -- (Zz, 1) - F FALSE represents and 2g with state space size of 8 >> k. hence reaching FALSE. Note that both these bags have cardinality and
(22, 0)
(22
(23.0 0)
(23. 1)
(Cg 1.6)
22. 2.6)
the bag containing
TRUE
FALSE
hence are treated the same when it comes treewidth.
In this section, we elaborate the counting mechanism that we use to encode the condition Em log(ds(w)) S log(k) for e E S. The technique we use was first proposed by Eén and Sörensson 2006). Intuitively speaking, we construct (Ordered) Binary Decision Diagram (BDD), where following a path from an input node to a terminal node corresponds to summing up weights. Each layer of nodes in the BDD is associated with a variable E S, and there two outgoing edges from each node in the BDD corresponding to the existence and absence of arc,, More formally, let assume that the set S consists of the variables U1,.... Um. where m == (S]. We construct a BDD, which is a directed graph with nodes of the form (z; 1) where i E {1, (1,d...m) m) an integer, and E [0, k] a real number. Here, I; signifies that we branch on variable v; next, and denotes the level of the current sum of weights. Additionally, there are two special terminals (sink nodes) TRUE and FALSE. From each node (xii, 1) there are outgoing ares the 'if' are connecting it to the node (I=+1, 1+ log (g(((ss))), and the 'else' arc connecting it to the node (I:+1, (). In case / + log(ds((;)) > we instead connect form (Zm. we connect it to the TRUE terminal iff [ + log (dg((s()m)) < k. We denote by if(r, I) and clse(z,1). the nodes connected to (Ir I) via the 'if' and 'else' ares, respectively. We refer to Figure 3 for an example. There are at most 2m + 1 nodes in the BDD.
the FALSE terminal. Finally, for a node of the
For each variable S, we have one such BDD to ensure that the product of the domain sizes of the endpoints of the outgoing arcs does not exceed the bound k. It is straightforward to express this BDD in the form of CNF formula B,,. We introduce variable bdd for each S {v) and each level / in the BDD. We then add the following clauses to B
(bdd", A arC,, + bdd (bdd",, A -arc,,.)) - bdd
{ for (w, E V(B.).
Next, we add the clause -bddEALsE D that falsifies 8" if the FALSE sink node is reached, i.c., the outgoing arcs of variable e violate the bound. Finally, we conjoin all the formulas 1 for E S with the formula E'g to obtain our final formula $ giving us the following theorem.
Theorem & admits a solution of weight Knnew and only if there exists a well-behaved DAG D with respect to D, such that f(Dne)) - f(D) = Kneww K and msss (Dew) < k.
Proof. By construction of the BDD, we see that 8 is falsified if and only if the outgoing arcs from variable result the state space size of that bag exceeding k: Thus, Aves 8 is satisfiable if and only if mnsss(Deew) < kc Combining this with Lemma we obtain the desired result.
Finally, we would like to draw attention to the fact that since only the local part is encoded into a MaxSAT formula, increasing the total number of variables does not directly affect the solving time for each individual subinstance, and consequently, the time required for each individual improvement. Thus the overhead of the BDDs doesn't 't increase when the total number of variables in the network increases. This is a crucial strength of the SLIM approach in general, i.e., it scales well relative the total number of variables, and the runtime has a stronger dependence the budget.
7

---

5
Experiments
5.1 Setup
We tested the various proposed methods on 4-core Intel Xeon E5540 2.53 GHz CPU (internal cluster), with each process having access 8GB RAM. The k-greedy and k-MAX algorithms are available as part of the BLIP package [Scanagatta] 2015) implemented in Java. We modified and extended these to obtain the implementations for k-greedy has and k-MAX We implemented BN-SLIM Python making use of the NetworkX library (Hagberg et al. 2008]. We used UWrMaxSaf as the MaxSAT-sol because of its reliable response to timeouts. For evaluating the reasoning time we used the Merlin package by Radu Marinescu 2 We provide the source code as public github repository [Peruvemba Ramaswamy and Szeider 2021b].
We tested the algorithms on a subset of the bnlearn repository Fl These networks are commonly used as benchmarks in the literature. Out of the 22 networks available in the repository, we only consider the 16 networks that contain non-binary variables. These networks range in size from to 1041 random variables. Due to the smaller networks' behavior being susceptible to random noise, we focus more on the larger networks.
5.2 Method
Next, we describe the method used to evaluate the performance of the BN structure learning algorithms enumerated in Section [4.1] We run the algorithms for a total time of 90 minutes and record the reasoning time and score at the end. We denote by BN- "IN-SLIMM'CL (X) the algorithm composed of running the heuristic X for 30 minutes and then running the bounded state space local improvement algorithm on top of the heuristic solution for another 60 minutes. We run the algorithms with multiple bounds and multiple random seeds. Finally, for each instance, we visualize the distribution of scores and reasoning times on a scatter plot capture the tradeoff achieved between the two metrics. We set k- k-greedy and k-MAX as the baseline algorithms and always compare the newly proposed algorithms against these baseline algorithms. The baseline algorithms represent the state-of-the-art bounded treewidth BN structure learning methods while the heuristics represent the bounded state space based BN structure learning methods.
5.3 Results
We performed some preliminary tests to determine the most promising bounded state space (bss) methods for comparison against the baseline of tw-methods k-MAX and k-greedy. On the basis of these tests, we choose <K-SLIM as the bss-method. In Figure 4 see the scatter plots for representative subset of instances. We include the complete set of plots in the supplementary material. The plots are presented in pairs with the left subplot depicting the tw-methods" performance and the right subplot depicting RN-SLIM (k-MAX performance.
In general, from Figure we observe that BN-SLIM soning times at the expense of slightly worse scores in some cases. Whereas in some cases, (K-
achieves much faster rea-
manages to match the score while reducing the reasoning time signifi- cantly. In most cases, we observe an reduction by order of magnitude. Another point worth noting that the clustering of the BNs output by (K-SLI much tighter than with the tw-methods. This highlights the reliability aspect of the bss-methods
along the reasoning time axis is
We also observe that the bss-method much more carefully and predictably. For instance, consider bound on the maximum state space size of 10 A reasonable equivalent bound on the treewidth would be logz x 10y) 19. However, networks with treewidth 19 can be expected to have much worse inference speeds as compared to networks with msss < 5 x 105.
allows us to expand the search space
This confirms our hypothesis that maximum state space size is a much better estimator of reasoning time as compared to treewidth, and that one can construct algorithms like BN-SLIMM** to learn such fast-inference BNs.
httpss//aaxstt-eralatttinss htg.::/eeee..a.tnn.........eeeen
https://www www.wrw..eaanccommmmm hta.lerrn..oommbeeppsttttoor
8

---

Starting Heuristic
Width (tw or logs(msss))
k-greedy
K-MAX
2.5
5.0
7.5
10.0
12.5
15.0
17.5
20.0
22.5
Baseline
Instance: munin1 (186 nodes)
Heuristic
Mean Reasoning Time (in
16
X
10'
100
300
288000 -270000 -260000 -250000 -240000
280000
-270000 -260000
-250000 -240000 Score
Score
Baseline
Instance: diabetes (413 nodes)
Heuristic
Mean Reasoning Time (in
100
x
-3.4
-3.2
-3.0
-2.8
-2.6
-2.4
-2.2
-3.4
-3.2
-3.0
-2.8 Score
-2.6
-2.4
2.2
Score
1e6
1e6
Baseline
Instance: pigs (441 nodes)
Heuristic
Mean Reasoning Time (in
10²
10
-1.82
-1.78
-1.76
-1.82
-1.78
-1.76
-1.74
Score
1e6
1e6
Baseline
Instance: link (724 nodes)
Heuristic
Mean Reasoning Time (in
10a
-1.725-1.77 -1775-1770-1675--66500
1.600-
-1.725 17725-1.700 1...0011.665555 -172
1.575
Score
1e6
Score
1e6
Figure 4: Scatter plots

---

Conclusion
We have introduced the concept of bounded state space BN structure learning, devised it theoretically, implemented it, and tested it rigorously on set of real-world data sets. We compared the new ap- proach with state-of-the-an bounded treewidth BN structure learning algorithms on a two-dimensional setting to see the tradeoff between inference speed and data fitting. Our results show that the new approach indeed provides overall better and more reliable results. some cases, the advantage of bounded state space over bounded treewidth methods is significant.
Ethical Impact BNs are widely used in pecision-making loops. We suspect our paper doesn't create any new negative social impacts than those that were already present. However, it could lead to over-dependence on BNs, which has its risks. In its current state, there are many areas where BNs cannot replace domain expert. We propose methods to speed up the inference on BNs, which does not significantly change their use case.
Acknowledgments and Disclosure of Funding
The authors acknowledge the support by the FWF (projects P32441 and W1255) and by the WWTF (project ICT19-065).
References
H. Akaike. A new look at the statistical model identification. IEEE transactions on automatic control, 19(6):716-723, 1974.
M. Benjumeda, C. Bielza, and P. Larrañaga. Learning tractable Bayesian networks in the space of elimination orders. Artificial Intelligence, 274:66-90, 2019.
J. Berg, M. Järvisalo, and B. M. Malone. Learning optimal bounded treewidth Bayesian networks via maximum satisfiability. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 20/4, Reykjavik, Iceland, April 22-25, 2014, volume 33 of JMLR Workshop and Conference Proceedings, pages 86-95. JMLR.org. 2014.
R. Dechter. Bucket elimination: unifying framework for reasoning. Artificial Intelligence, 113(1-2):
41-85, 1999.
N. Eén and N. Sörensson. Translating pseudo-boolean constraints into SAT. J. Satisf. Boolean Model. Comput., 2(1-4):1-26, 2006. doi: 10.3233/sat190014. URL https://doi.org:: 3233/ satt///11
V. Gogate and R. Dechter. A complete anytime algorithm for treewidth. In Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-04), pages 201-208, Arlington, Virginia, 2004. AUAI Press.
A. A. Hagberg. Schult, and Swart. Exploring network structure, dynamics, and function using NetworkX. In Proceedings of the 7th Python in Science Conference (SciPy2008), pages 11-15, Pasadena, CA USA, Aug. 2008
D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Machine Learning, 20(3):197-243, 1995.
U. Kærulff. Optimal decomposition of probabilistic networks by simulated annealing. Statistics and Computing, 2:7-17, 1992.
K. Kask, A. Gelfand, L. Otten, and R. Dechter. Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In W. Burgard and Roth, editors, Proceedings of the Twenty-Fitt -Finth AAAI Conference on Artificial Intelligence (AAAI 2011), page 54-60. AAAI Press, 2011.
D. Koller and N. Friedman. Probabilistic Graphical Models: principles and techniques. MIT press, 2009.
10

---

J. H. Korhonen and P. Parviainen. Exact learning of bounded tree-width Bayesian networks. In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2013, Scottsdale, A7, USA, April 29 May 1, 2013, volume 31 of JMLR Workshop and Conference Proceedings, pages 370-378. Jor.. 2013.
S. L. Lauritzen and D. J. Spiegelhalter. Local computations with probabilitiies on graphical structures and their application to expert systems. J. R. Stat. Soc. Ser. B., 157-224 1988.
M. Meila and M. I. Jordan. Triangulation by continuous embedding. In M. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems 9, NIPS, Denver, CO, USA, December 2-5, 1996, pages 557-563. MIT Press, 1996.
S. Nie, C. P. de Campos, and Q. Ji. Learning bounded tree-width Bayesian networks via sampling. In S. Destercke and Denoeux, editors, Symbolic and Quantitative Approaches to Reasoning with Uncertainty 13th European Conference, ECSQARU 2015, Compiègne, France, July 15-17, 2015. Proceedings, volume 9161 of Lecture Notes in Computer Science, pages 387-396. Springer Verlag. 2015.
S. Nie, C. P. de Campos, and Q. Ji. Learning Bayesian networks with bounded tree-width via guided search. In D. Schuurmans and M. P. Wellman, editors, Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 3294-3300. AAAI Press, 2016.
L.
Otten and R. Dechter. Refined bounds for restance-basele search complexity of counting and other #P problems. In P. J. Stuckey, editor, Principles and Practice of Constraint Programmingg 14th International Conference, CP 2008, Sydney, Australia, September 14-18, 2008. Proceedings, volume 5202 of Lecture Notes in Computer Science, pages 576-581. Springer Verlag, 2008a. doi: 000077978-3-540-85555
L. Otten and R. Dechter. Bounding search space size via (hyper)tree decompositions. In D. A. McAllester and P. Myllymäki, editors, UAI 2008, Proceedings of the 24th Conference in Uncer- tainty in Artificial Intelligence, Helsinki, Finland, July 9-12, 2008, pages 452 459. AUAI Press, 2008b.
Parviainen, H. S. Farahani, and J. Lagergren. Learning bounded tree-width Bayesian networks using Integer Linear Programming. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014, volume 33 of JMLR Workshop and Conference Proceedings, pages 751-759. JMLR.org, 2014.
V. Peruvemba Ramaswamy and S. Szeider. Turbocharging treewidth-bounded Bayesian network structure learning. Proceedings of the AAAI Conference Artificial Intelligence, 355 (5(5) May 2021a. htttstss:://of wwwpi...a....................... ata..aa....aa..eeee.a wwwg//indx..phar http:///anee...ppAAAAA////aaaaaa
www.AAAAaaatitevviiiieaaaaeeeeee 16508
V. Peruvemba Ramaswamy and S. Szeider. aditya955riram/bnnSlim Neurips 2021, Oct. 2021b. URL https://doi.
M. Samer and H. Veith. Encoding treewidth into SAT. Theory and Applications of Satisfibilitt Testing- SAT 2009, 12th International Conference, SAT 2009, Swansea, UK, June 30 - July 3, 2009. Proceedings, volume 5584 of Lecture Notes Computer Science, pages 45-50. Springer Verlag, 2009.
M. Scanagatta. BLIP Bayesian network learning and inference package, 2015. URL https 7/ipg. idsia. ch/ at/software/bipp
M. Scanagatta, G. Corani, C. P. de Campos, and M. Zaffalon. Learning treewidth- Bayesian networks with thousands of variables. In D. D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1462-1470, 2016.
M. Scanagatta, G. Corani, M. Zaffalon, J. Yoo, and U. Kang. Efficient learning of bounded- Bayesian networks from complete and incomplete data sets. Int. J. Approx. Reason, 95:152-1661 2018.
G. Schwarz. Estimating the dimension of model. The Annals of Statistics, 6(2):461-44, 1978.
11

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Experiments highlight benefits and drawbacks
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See
Section 6
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Lemmas 2
and
Theorems 2
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or URL)? [Yes] included in supplementary material
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [N/A] no training phase
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Section 3.1
(b) Did you mention the license the assets? [Yes] all open source. bnlearn: CC-share- alike, blip: LGPL3, merlin: BSD
(c) Did you include any assets either in the supplemental material as URL? [N/A] no new assets
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes] all publicly available assets
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [Yes] personal data
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "ve3eWVVkj7", "reviewer": "Reviewer_9g4D", "summary": "This work combines heuristic Bayesian network structure learning algorithms with a Max-SAT-based local improvement method to provide more responsive than BNs provided by treewidth-based methods. Some efforts are devoted to generate fast methods when learning a Bayesian network from data, but it is also important to provide the ‘best possible structure’. Once the network is created (learned or elicited), the use will imply generally multiple inference operations which is the usual way to reason in BNs. This work aims at generating responsive BNs, that is, able to admit fast probabilistic reasoning. In order to allow tractable inference we need to learn Bayesian networks with a bounded-treewidth structure, being then treewidth value of extreme importance to determine the speeding reasoning. Let us remind that the treewidth of a triangulated graph is the size of its largest clique/bag minus one, so it will determine the largest message to be sent, if probability propagation is used for inference. However, state space is also important, as not all the variables present the same number of states, a binary variable will introduce less potential combinations than one with 5 states for instance. The state space of a clique/bag is the product of the domain sizes of the variables it contains. There exist evidence, supported by the initial experiments, which shows that the largest state space size of all bags can be even more decisive on the reasoning time than the treewidth, which seems natural as it is more informed about the dimension of the bag.\n\nAuthors’ proposal is heavily based on proposed the hybrid approach BN-SLIM, which improves the score of a heuristically computed BN by multiple applications of a MaxSAT-based exact method. They compare their methodology using  bounded state space (bss) with other baseline methods establishing bounded-treewidth strategies, namely k-greedy and k-MAX. Results indicate that bss methods perform better and faster, both BN-SLIMbss and k-MAXbss allows expanding the search space more carefully and predictably.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In my opinion the work is original enough, even though it is greatly based on an existing work, it makes an important contribution when using the bss approach. \n\nThe quality is correct. Some parts may assume too specific knowledge but it is possible to be followed by a familiarised reader.\n\nThere are a few typos (*) but in general the paper is well written. The structure is a little bit unbalanced, as the results are presented too quickly and without a thorough analysis. Even though the supplementary material provides further plots, I would be happy to see in the paper itself a deeper analysis on the results, maybe using some other objective scores to compare the methods.\n\nThe results are of moderate significance, I personally find that exploring the bss alternative is clearly promising.\n\n(*) I will list those detected:\n\n- page 4: consisting pf …\n- page 5: Our aim is compute\n- page 8: networks' behvaior\n\nI like the way in which section 3 presents the two possibilities, and I think section 4 seems correct, although I did not verify every mathematical detail. As indicated before, the experimental side is a little poor, probably due to space restrictions, but I would personally prefer to keep some proofs as supplementary material and find a more in-depth comparison with a broader analysis in the published paper.\n\nIn general I believe it is a paper valuable for discussion and offering helpful and promising ideas.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "It is properly addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "jDKKn7q4Rha", "reviewer": "Reviewer_mMbj", "summary": "A method for learning BNs where the size of the joint state space of a\nbag in a tree-decomposition is bounded. It is argued (convincingly)\nthat this is a more useful quantity to bound than simple treewidth,\nand empirical results produced to back this up. Learning has two\nphases: an initial heuristic, followed by \"local improvement\", the\nlatter developed from earlier work. A (weighted partial) MAXSAT\nencoding is presented for the local improvement phase which is an\nextension from earlier work. A key contribution is a method for\nencoding the constraint on the size of the joint state space: move to\nlogs, replace product with sums, and a BDD to encode the necessary summation.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The methods are mainly not-too-big alterations and additions to\nexisting methods. But I think this is a good thing. The authors know\nthe literature and have thus saved themselves from (re)inventing some\n(possibly inferior) methods.\n\nThis is a clearly written paper. We have some useful theoretical\nresults, but the key issues are: (1) are we using the right measure of\n\"responsiveness\"? and (2) do we learn the \"right\" networks?\n\nRe (1) Section 3.1 provides evidence for a \"yes\" answer. Re (2),\nnaturally there could be a trade-off between fit-to-data and\nresponsiveness. Fig 4 gives us a reasonable idea of when there is such\na trade-off. I think the authors have provided sufficient evidence\nthat that the presented method produces the right sorts of BNs.\n\nNot a big issue, but I don't think \"responsive\" is the right word to\nuse for BNs which admit speedy query answering, since it does not\nconvey that the response (to a query) comes back quickly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors consider this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "dVswWmIGFgi", "reviewer": "Reviewer_tk5p", "summary": "A structure learning method for Bayesian networks. The main contribution is the use of state space to bounds in structure learning rather than the more well established treewidth bounds to improve scalability an speed of inference.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper proposes a new structure learning algorithm for Bayesian nets. The main innovation is to use a bound on the state space as compared to tree width bounds that are typically used in structure learning. In Bayesian nets with non-binary variable domains, the state space bound can be a  much more effective bound for learning compared to tree width. Two known heuristics are augmented with the state space bound. A recently developed approach is adapted to include the state space bound. To guarantee the constraints on the state space, a maxSAT encoding is constructed. A counting method using binary decision diagrams is constructed where a solution ensures that the state space bound can be met.\n\nExperiments are performed on standard benchmarks for structure learning and improvements are shown over tree width based structure learning in terms of mean reasoning time, i.e. using the state space bounds we can learn Bayesian nets where inference is faster.\n\nThe paper has an interesting new approach to use state space bounds quite different from the tree width bounds commonly used. The case for non-binary domains seem relevant since a lot of real world problems have non binary domains and seems like tree width is a worse bound for such cases, so the proposed approach seems significant. One weakness is perhaps the paper builds a lot on recent results by Ramaswamy and Szeider, so the main novel contribution seems to be theorem 1 and the BDD encoding since the maxsat encoding seems to be known already. Maybe explicitly specifying the new contribution will help understand the significance of the proposed method better.\n\nThe experiments do show a consistently significant reduction in reasoning time compared to state of the art implemented in the BLIP package over all the benchmarks, so the experiments do show the benefit of the approach. I am wondering if scalability of structure learning is an issue for large number of variables since there is an overhead of using BDDs for each variable. Overall, the paper though seems to make good contributions with good empirical results to back them up. Some comments about the significance of the contributions beyond the Ramaswamy and Szeider 2021 work will help.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed by the authors. Since the main contribution is improving scalability of existing models, I do not foresee negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "bJKA3InhXXQ", "reviewer": "Reviewer_f3K7", "summary": "This is a paper about the structural learning of Bayesian networks. Analogously to existing methods trying to learning models with bounded treewidth, the authors here are interested in learning models with bounded \"state space\". Of course the two descriptors differ for non-binary models, the second providing a more precise indicator of the time needed for inferences. \n\nThe approach achieves that by a (simple) modification of the algorithms proposed by Scanagatta et al. for bounded treewidth.\nThis is followed by a post-processing step which adapts a similar approach by Ramaswamy and Szeider (AAAI 2021) for bounded treewidth to the bounded state space case by a MaxSAT reduction. Experiments are showing how this approach might give models producing faster inferences, but not necessarily higher scores.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea is clear and reasonable. Yet, I see two critical points:\n\n(i) the reason for focusing on bounded state spaces (and not on bounded treewidth) should be better advocated. I can imagine significant differences for the reasoning time only when variables with a huge number of states are present.\n(ii) compared to Ramaswamy and Szeider (AAAI 2021) the contribution sounds a bit incremental, being basically an adaptation of what has been done in that paper for bounded treewidth to the bounded state space.\n(iii) the experimental results are not well organized, a synthetic (quantitative) description is missing\n\n*** I eventually decided to revise my score after the rebuttal. ***\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Nothing.", "review_text": "", "extra_scores": {"ethical_concerns": "Nothing.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript proposes to use a measure based on the max. "bag" size (product of cardinalities) when learning Bayesian networks, instead of treewidth. From a theoretical perspective, this is unimportant: results of hardness hold when all variables have the same cardinality, and one can easily convert nets if needed to/from that. However, the practical results of using the bag size (which is obviously a better measure than treewidth of the graph, no doubt of that, everybody should know it) can be interesting and useful. The novelty and theoretical contribution are not so significant, but on the other hand it is fair to say that someone needs come forward and argue that we should be using bag size instead of treewidth and make that claim work properly.
Decision: Accept (Poster)