Learning Fast-Inference Bayesian Networks
Year: 2021

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.

heading: 1 Introduction
text: The time complexity of probabilistic reasoning on a Bayesian Network (BN) is 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 al., 2011]; a bag’s state space size is the product of the domain sizes of all the variables it 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-art bounded treewidth BN learning algorithms, on real-world benchmark data sets, with up to over a thousand variables. The results show a clear advantage for new bounded state space (bss) algorithms.
It is common to 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 an 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. [2016, 2018] as well BN-SLIM by Peruvemba Ramaswamy and Szeider [2021a]. The latter is a post-processing algorithm that uses MaxSAT to improve BNs generated by the heuristics. All these algorithms assume a user-specified upper bound k 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 straightforward. The main challenge for extending BN-SLIM to bss learning is to replace BN-SLIM’s simple cardinality constraints with a MaxSAT encoding that bounds the state-space of a bag, i.e., a product of integers. We achieve this by switching to logarithms and bounding the sum of real numbers, utilizing a MaxSAT encoding based on binary decision diagrams (BDDs).
35th Conference on Neural Information Processing Systems (NeurIPS 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).

heading: 1.1 Related Work
text: We discuss related work in terms of Figure 1. In approaches (a) and (b), the BN has already been
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), general-purpose tree decomposition algorithms can be applied, such as the one by Gogate and Dechter [2004]. As the significance of the state space of BNs was recognized [Lauritzen and Spiegelhalter, 1988], the research focused on approach (b) [Kask et al., 2011, Kærulff, 1992, 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 is 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 et 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 et al., 2019]. Recently, Peruvemba Ramaswamy and Szeider [2021a] proposed the hybrid approach BN-SLIM, which improves the score of a heuristically computed BN by multiple applications of a MaxSAT-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.

heading: 2 Preliminaries

heading: 2.1 Graphs and Digraphs
text: We consider both undirected and directed graphs G, where V (G) denotes the set of vertices and E(G) the set of edges of G, respectively. If G is directed, we refer to its edges as arcs. A directed graph is a DAG if it doesn’t contain any directed cycles.

heading: 2.2 Structure Learning
text: Assume we are given a data set of samples D1, . . . , DN over n categorical random variables, each variable v ranging over a 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 f assigns each node v ∈ V (D) and each subset P ⊆ V \ {v} the score fP (v) of P for v. Let
PD(v) = {u ∈ V : (u, v) ∈ E } denote the parent set of v in D. The score f(D) of D is the sum of f(v, PD(v)) over all v ∈ V (D). Score functions defined in such a way (decomposable score functions) accommodate popular scores like AIC, BDeu, and BIC [Akaike, 1974, Heckerman et al., 1995, Schwarz, 1978]. A score function cache is obtained from a score function by disregarding any potential parent set P ′ of a node v if f(v, P ′) ≤ f(v, P ) for another potential parent sets of v with P ( P ′. Consequently, a score function cache does not consider a nonempty potential parent set if its score doesn’t exceed the score of the empty parent set.

heading: 2.3 Tree Decomposition
text: Consider an undirected graph G. A tree decomposition T of G is a pair (T, χ), consisting of a tree T and a mapping χ : V (T )→ 2V (G), where the set χ(t) is called a bag, with the following properties.
1. For every edge e ∈ E(G) there is some t ∈ V (T ) such that e ⊆ χ(t). 2. For every vertex v ∈ V (G), the set { t ∈ V (T ) : v ∈ χ(t) } induces a non-empty subtree
of T .
The moralized graph M(D) of a DAG D is defined by V (M(D)) = V (D) and E(M(D)) = { {u, v} : (u, v) ∈ E(D) } ∪ { {u, v} : (u,w), (v, w) ∈ E(D), u 6= v }. A tree decomposition of a DAG is a tree decomposition of its moralized graph. A tree decomposition of a BN is a tree decomposition of its underlying DAG.

heading: 3 Treewidth and Maximum State Space Size
text: In this section, we discuss the different metrics that can be used to estimate the inference speed of a BN along with some empirical findings.
Consider a tree decomposition T = (T, χ) of a DAG D, where V (D) consists of random variables, each v ∈ V (D) ranging over a set of ds(v) many discrete values. The width of T is
max t∈V (T )
|χ(t)| − 1,
i.e., is the size of a largest bag minus 1. The treewidth tw(D) of D is the minimum width over all tree decompositions of M(D).
The maximum state space size of T is
max t∈V (T ) ∏ v∈χ(t) ds(v),
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) of a D is the minimum msss over all tree decompositions of M(D).
The maximum state space of a binary BN of treewidth t is 2t+1. The bounded treewidth (state space, respectively) BN structure learning problem takes as input a 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 V (D) = V of treewidth (maximum state space size, respectively) at most k, with a maximal score f(D).

heading: 3.1 Empirical Influence on Inference Speed
text: Complexity results for probabilistic reasoning (inference) suggest that for BNs containing nonbinary variables, maximum state space size provides a 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
between reasoning time and maximum state space size is much stronger than the correlation between reasoning time and treewidth. The number of outliers is much higher in the treewidth plot as compared to 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, as we will lay out in the next sections.

heading: 4 BN Learning of Bounded State Space Size

heading: 4.1 Modified Heuristics
text: We now describe the modifications we made to the k-MAX and k-greedy heuristics to operate with a bound on the state space.
Now, we give a brief outline of the k-greedy algorithm. Let us assume a treewidth bound of k. The algorithm starts from a random ordering of the random variables. Initialization: It then initializes the first bag with the first k+1 variables. It computes the best DAG over these variables either by an exact method or by an approximate method depending on the value of k+ 1. 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 as 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 σ = v1, v2, . . . , vn be the randomly sampled ordering. Instead of simply picking the first k variables, we now pick the first p variables such that p is the largest integer satisfying the condition ∏p i=1 vi ≤ k. In the Addition step, we no longer treat all existing k-cliques as
potential parent sets. Instead, when adding variable v, we only consider those sets S for which∏ u∈S∪{v} ds(u) ≤ k.
The k-MAX algorithm is similar to the k-greedy algorithm but picks the variables based on a 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-greedybss and k-MAXbss refer to the modified versions of k-greedy and k-MAX with the proposed modifications that return bounded state space BNs.
As a side effect, all these algorithms produce a tree decomposition that witnesses the treewidth or state space bound of the obtained BN.

heading: 4.2 Local Improvement
text: 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 a set V of random variables, a score function f , and a state space bound k. Initialization: We first use a heuristic (such as described in Subsection 4.1) to compute an initial solution D, together with a tree decomposition T = (T, χ) of the moralized graph M(D) with maximum state space size ≤ k. The local improvement step uses the parameter budget B which controls the size of the local instance. Subtree selection: We select a subtree S of T such that VS := ⋃ t∈V (S) χ(t) does not exceed the budget B. Our aim is to compute for each v ∈ VS a new parent set, optimizing the score of the resulting DAG Dnew with V (Dnew) = V . We define DnewS as the DAG induced by VS where E(DnewS ) = { (u, v) ∈ E(Dnew) : {u, v} ⊆ VS }. We distinguish between different kinds of nodes:
• v ∈ VS a boundary vertex if there exists a tree node t ∈ V (T ) \ V (S) such that v ∈ χ(t); • v ∈ VS is an internal vertex if v is not a boundary vertex; • v ∈ V \ VS is an external vertex.
Two boundary vertices v, v′ are adjacent if both occur together in some bag outside S. In that case we call {v, v′} a virtual edge. We let Evirt be the set of all virtual edges. The extended moral graph Mext is obtained from M(DnewS ) by adding all virtual edges. If v, v
′ are two adjacent boundary vertices such that Dnew contains a 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. E→virt denotes the set of all virtual arcs.
We call DnewS a well-behaved DAG with respect to DAG D and its tree decomposition (T, χ) if the following conditions are satisfied:
1. DnewS is acyclic. 2. For each v ∈ V (Mext), if PDnew(v) contains external vertices, then there is some t ∈ V (T ) \ V (S) such that PDnew(v) ∪ {v} ⊆ χ(t). 3. The digraph with vertex set V (Mext) and arc set E(DnewS ) ∪ E→virt) is acyclic.
Let T = (T, χ) be a tree decomposition of DAG D. We call T new = (T new, χnew) a conservative tree decomposition of DAG Dnew with respect to set S ⊆ T if
1. T new is a tree decomposition of DAG Dnew, 2. T new can be partitioned into Snew, T1, . . . , Tr, where T1, . . . , Tr are the connected compo-
nents of T \ V (S), and 3. χnew(t) = χ(t) for t ∈ ⋃r i=1 V (Ti).
Lemma 1. If DnewS is well-behaved, then Dnew is acyclic and f(Dnew) ≥ f(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 of such a DnewS is conservative with respect to S.
Introducing a state space bound to Lemma 1, we obtain the following theorem. Theorem 1. If DnewS is well-behaved and admits a tree decomposition with msss at most k, then
1. Dnew is acyclic,
2. the score of Dnew is at least the score of D, and
3. msss(Dnew) ≤ k.
Proof. The first two properties follow from Lemma 1. Now, let T = (T, χ) be the tree decomposition of DAG D, T new = (T new, χnew) be the tree decomposition of DAG Dnew and Snew = (Snew, χnewS )
be the tree decomposition of DnewS . Since Snew is conservative with respect to S (from Lemma 1), we can express χnew as χnewS (t) if t ∈ S and χ(t) otherwise. In order to prove the third property, we need to bound the state space size of the bags of T new, i.e., we need to bound
max t∈T new ∏ v∈χnew(t) ds(v) = max ( max t∈S ∏ v∈χnewS (t) ds(v), max t∈T\V (S) ∏ v∈χ(t) ds(v) )
≤ max ( k,max
t∈T ∏ v∈χ(t) ds(v) )
[msss(DnewS ) ≤ k]
≤ max (k, k) [msss(D) ≤ k]. Thus, the maximum state space size of Dnew is at most k.

heading: 4.3 MaxSAT Encoding
text: We now describe how we construct the (weighted, partial) MaxSAT instance that encodes the conditions required on the local instance S. The instance is 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 Evirt, the set of virtual arcs E→virt, and the bound k on the maximum state space size and produce a MaxSAT instance ΦS . We reuse parts of the encoding proposed by Peruvemba Ramaswamy and Szeider [2021a] (we will refer to it as the BN-SLIM encoding), extending an encoding proposed by Samer and Veith [2009] for capturing the tree decompositions.
Let n = |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 Φ′S . For an explanation of the semantics of these variables and clauses, we refer to the source [Peruvemba Ramaswamy and Szeider, 2021a].
(acyc∗u,v ∧ acyc∗v,w)→ acyc∗u,w (ord∗u,v ∧ ord∗v,w)→ ord∗u,w
} for distinct u, v, w ∈ S.
¬arcv,v for v ∈ S.∑ P∈Pvpar P v = 1 for v ∈ S.
parPv → acycu,v for v ∈ S, P ∈ Pv, and u ∈ P.
(parPv ∧ ordu,v)→ arcu,v (parPv ∧ ordv,u)→ arcv,u
} for v ∈ S, P ∈ Pv, and u ∈ P.
(parPv ∧ ordu,w)→ arcu,w (parPv ∧ ordw,u)→ arcw,u
} for v ∈ S, P ∈ Pv, and u,w ∈ P.
(arcu,v ∧ arcu,w ∧ ordv,w)→ arcv,w (arcu,v ∧ arcu,w ∧ ordw,v)→ arcw,v
} for u, v, w ∈ S.
¬arcu,v ∨ ¬arcv,u for u, v ∈ S. ord∗u,v → arcu,v ∧ ord∗v,u → arcv,u for {u, v} ∈ Evirt.
parPv → acyc∗u,v for v ∈ S, P ∈ Pv, and (u, v) ∈ A→virt(v, P ).
We also add the following soft clauses to Φ′S , setting f ′ P (v) = fP (v)− f∅(v) as their weight
(parPv ) : weight f ′ P (v) for v ∈ S, P ∈ Pv.
The weight of a solution to Φ′S is given by the sum of weights of the satisfied soft clauses. Let W =∑ v∈S f
′(v, PD(v)) be the core of the unmodified local instance S. Lemma 2. Φ′S admits a solution of weight W new if and only if there exists a well-behaved DAG DnewS with respect to D, such that f(Dnew)− f(D) = W new −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 DnewS . Therefore D new S
is still acyclic. Further, an assignment that corresponds to setting DnewS = SS achieves the lower bound on the score.

heading: 4.4 BDD-based Counter
text: In this section, we elaborate the counting mechanism that we use to encode the condition∑ w∈S,w 6=v,arcv,w log(ds(w)) ≤ log(k) for v ∈ S. The technique we use was first proposed by Eén and Sörensson [2006]. Intuitively speaking, we construct an (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 v ∈ S, and there are two outgoing edges from each node in the BDD corresponding to the existence and absence of arcv,w. More formally, let us assume that the set S consists of the variables v1, . . . , vm, where m := |S|. We construct a BDD, which is a directed graph with nodes of the form (xi, l) where i ∈ {1, d . . .m} is an integer, and l ∈ [0, k] is a real number. Here, xi signifies that we branch on variable vi next, and l denotes the level of the current sum of weights. Additionally, there are two special terminals (sink nodes) – TRUE and FALSE. From each node (xi, l) there are two outgoing arcs – the ‘if’ arc connecting it to the node (xi+1, l+ log(ds(vi))), and the ‘else’ arc connecting it to the node (xi+1, l). In case l + log(ds(vi)) > k, we instead connect it to the FALSE terminal. Finally, for a node of the form (xm, l), we connect it to the TRUE terminal iff l + log(ds(vm)) ≤ k. We denote by if(x, l) and else(x, l), the nodes connected to (x, l) via the ‘if’ and ‘else’ arcs, respectively. We refer to Figure 3 for an example. There are at most 2m + 1 nodes in the BDD.
For each variable v ∈ 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 a CNF formula Bv. We introduce a variable bddvw,l for each w ∈ S \ {v} and each level l in the BDD. We then add the following clauses to Bv
(bddvw,l ∧ arcv,w)→ bddvif(w,l) (bddvw,l ∧ ¬arcv,w)→ bddvelse(w,l)
} for (w, l) ∈ V (Bv).
Next, we add the clause ¬bddvFALSE to Bv that falsifies Bv if the FALSE sink node is reached, i.e., if the outgoing arcs of variable v violate the bound. Finally, we conjoin all the formulas Bv for v ∈ S with the formula Φ′S to obtain our final formula ΦS , giving us the following theorem. Theorem 2. ΦS admits a solution of weightKnew if and only if there exists a well-behaved DAGDnewS with respect to D, such that f(Dnew)− f(D) = Knew −K and msss(DnewS ) ≤ k.
Proof. By construction of the BDD, we see that Bv is falsified if and only if the outgoing arcs from variable v result in the state space size of that bag exceeding k. Thus, ∧ v∈S Bv is satisfiable if and only if msss(DnewS ) ≤ k. Combining this with Lemma 2, 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 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 to the total number of variables, and the runtime has a stronger dependence on the budget.

heading: 5 Experiments

heading: 5.1 Setup
text: We tested the various proposed methods on 4-core Intel Xeon E5540 2.53 GHz CPU (internal cluster), with each process having access to 8GB RAM. The k-greedy and k-MAX algorithms are available as a part of the BLIP package [Scanagatta, 2015] implemented in Java. We modified and extended these to obtain the implementations for k-greedybss and k-MAXbss. We implemented BN-SLIMbssin Python making use of the NetworkX library [Hagberg et al., 2008]. We used UWrMaxSat1 as the MaxSAT-solver, 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 a public github repository [Peruvemba Ramaswamy and Szeider, 2021b].
We tested the algorithms on a subset of the bnlearn repository.3 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 6 to 1041 random variables. Due to the smaller networks’ behavior being susceptible to random noise, we focus more on the larger networks.

heading: 5.2 Method
text: 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-SLIMbss(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 to capture the tradeoff achieved between the two metrics. We set 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.

heading: 5.3 Results
text: 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 BN-SLIMbss(k-MAXbss) as the bss-method. In Figure 4 we see the scatter plots for a 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 BN-SLIMbss(k-MAXbss)’s performance.
In general, from Figure 4, we observe that BN-SLIMbss(k-MAXbss) achieves much faster reasoning times at the expense of slightly worse scores in some cases. Whereas in some cases, BN-SLIMbss(k-MAXbss) manages to match the score while reducing the reasoning time significantly. In most cases, we observe an reduction by an order of magnitude. Another point worth noting is that the clustering of the BNs output by BN-SLIMbss(k-MAXbss) along the reasoning time axis is much tighter than with the tw-methods. This highlights the reliability aspect of the bss-methods.
We also observe that the bss-method BN-SLIMbss(k-MAXbss) allows us to expand the search space much more carefully and predictably. For instance, consider a bound on the maximum state space size of 5× 105. A reasonable equivalent bound on the treewidth would be log2(5× 105) ≈ 19. However, networks with treewidth 19 can be expected to have much worse inference speeds as compared to networks with msss ≤ 5× 105. 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-SLIMbss(k-MAXbss) to learn such fast-inference BNs.
1https://maxsat-evaluations.github.io/2019/descriptions.html 2https://github.com/radum2275/merlin 3https://www.bnlearn.com/bnrepository/

heading: 6 Conclusion
text: We have introduced the concept of bounded state space BN structure learning, devised it theoretically, implemented it, and tested it rigorously on a set of real-world data sets. We compared the new approach with state-of-the-art 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. In some cases, the advantage of bounded state space over bounded treewidth methods is significant.
Ethical Impact BNs are widely used in decision-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 a 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).

Review summaries:
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.   The approach achieves that by a (simple) modification of the algorithms proposed by Scanagatta et al. for bounded treewidth. This 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.

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.  Authors’ 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.

A method for learning BNs where the size of the joint state space of a bag in a tree-decomposition is bounded. It is argued (convincingly) that this is a more useful quantity to bound than simple treewidth, and empirical results produced to back this up. Learning has two phases: an initial heuristic, followed by "local improvement", the latter developed from earlier work. A (weighted partial) MAXSAT encoding is presented for the local improvement phase which is an extension from earlier work. A key contribution is a method for encoding the constraint on the size of the joint state space: move to logs, replace product with sums, and a BDD to encode the necessary summation.