Approximate inference of marginals using the IBIA framework
Authors: Shivani Bathla
Vinita Vasudevan
Venue: NeurIPS 2023 poster (2023)
Keywords: Bayesian inference
posterior marginals
probabilistic graphical models
TL;DR: New algorithm for approximate inference of marginals in probabilistic graphical models

Abstract: Exact inference of marginals in probabilistic graphical models (PGM) is known to be intractable, necessitating the use of approximate methods. Most of the existing variational techniques perform iterative message passing in loopy graphs which is slow to converge for many benchmarks. In this paper, we propose a new algorithm for marginal inference that is based on the incremental build-infer-approximate (IBIA) paradigm. Our algorithm converts the PGM into a sequence of linked clique tree forests (SLCTF) with bounded clique sizes, and then uses a heuristic belief update algorithm to infer the marginals. For the special case of Bayesian networks, we show that if the incremental build step in IBIA uses the topological order of variables then (a) the prior marginals are consistent in all CTFs in the SLCTF  and (b) the posterior marginals are consistent once all evidence variables are added to the SLCTF. In our approach, the belief propagation step is non-iterative and the accuracy-complexity trade-off is controlled using user-defined clique size bounds. Results for several benchmark sets from recent UAI competitions show that our method gives either better or comparable accuracy than existing variational and sampling based methods, with smaller runtimes.

Approximate inference of marginals using the IBIA framework
Shivani Bathla
Vinita Vasudevan
Department of Electrical Engineering Indian Institute of Technology Madras India, 600036 ee13s0640ee litmmmm... ac.in
Department of Electrical Engineering Indian Institute of Technology Madras
India, 600036
vinitaβee iitm. ac.
Abstract
Exact inference of marginals in probabilistic graphical models (PGM) is known intractable, necessitating the use approximate methods. Most of the existing variational techniques perform iterative message passing loopy graphs which is slow to converge for many benchmarks. In this paper, we propose a new algorithm for marginal inference that is based the incremental build-infer-approxinai (IBIA) paradigm. Our algorithm converts the PGM into a sequence of linked clique tree forests (SLCTFF) with bounded clique sizes, and then uses heuristic belief update algorithm to infer the marginals. For the special case of Bayesian networks, we show that if the incremental build step in IBIA uses the topological order of variables then (a) the prior marginals are consistent in all CTFs in the SLCTF and (b) the posterior marginals are consistent the SLCTF. In our approach, the belief propagation step is non-iterative and the accuracy-come complexty trade-off is controlled using user-defined clique size bounds. Results for several benchmark sets from recent UAI competitions show that our method gives either better comparable accuracy than existing variational and sampling based methods, with smaller runtimes.
all evidence variables are added
1 Introduction
Discrete probabilistic graphical models (PGM) including Bayesian networks (BN) and Markov networks (MN) used for probabilistic inference in wide variety of applications. An important task in probabilistic reasoning is the computation of posterior marginals of all the variables in the network. Exact inference is known to be #P-complete [Roth] 1996), thus necessitating approximations. Approximate techniques can be broadly classified as sampling based and variational methods.
Sampling based methods include Markov chain Monte Carlo based techniques like Gibbs sam- pling [Gelfand] 2000 Kelly et al. [0099] and importance sampling based methods [Gogate and
Dechter 2011 Friedman and Van den Broeck 2018 Kask et al.) 2020 Broka 2018 Lou al. 2019 7 by Marinescu et al. 2018). An advantage of these methods is that accuracy can be improved with time without increasing the required memory. However, in many benchmarks the improvement becomes slow with time. Moreover, many the recent sampling/search based
techniques Kask al. 2020 Broka 2018 Lou al. [209 2017a(b), Marinescu et al. 2019
2018] have been evaluated either for approximate inference of partition function (PR) or for finding the marginal maximum posteriori assignment (MMAP). Currently, there no published results for posterior marginals (MAR) using these methods, and the publicly available implementations do support the MAR task. Alternatively, variational techniques can be used. These include loopy belief propagation (LBP) Frey and MacKay [9988) region-graph based techniques like generalized
belief propagation (GBP) Yedidia al. 2000) and its variants (Heskes et al., 2003 Mooij and
Kappen 2007 Lin et al. 2020], mini-bucket based schemes like iterative join graph propagation
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(IIPP) Mateescu et al., 2010] and weighted mini- elimination (WMB) Liu and Ihler 2011
and methods that simplity the graph structure like edge deletion belief propagation (EDBP) and the (RCR) techniques [Choi et al.) 2005 Choi and Darwiche, 2006 2010]. While the eecuracy-complexee trade-off can be achieved using single user-defined clique size bound in mini-bucket based methods, it is non-trivial in many of the other region graph based methods. Most of these techniques use iterative message passing to solve an optimization problem. for which convergence is not guaranteed and even if possible, can be slow to achieve. Non-iterative methods like Deep Bucket Elimination (DBE) [Razeghi et al., [02T] and NeuroBE [Agarwal et al.) 2022] are extensions of bucket elimination that approximate messages using neural networks. How- ever, training these networks takes several hours. Moreover, the publicly available implementations of these methods do not support the MAR task.
related eelax-compensate-reeoow
The recently proposed incremental build-infer- muidd-nnfr-approxmmate (IBIA) framework (Bathla and Vasudevan 2023] uses different approach. It converts the PGM into a sequence of calibrated clique tree forests (SCTF) with clique sizes bounded to a user-defined value. [Bathla and Vasudevan [023] show that the normalization constant (NC) of clique beliefs in the last CTF in the sequence is good approximation of the partition function of the overall distribution. This framework has two main advantages. Firstly, since it is based on clique trees and not loopy graphs, the belief propagation step is non-iterative. Therefore, it is fast and has no issues related to convergence. Secondly, it provides an easy control of the accuracy complexity trade-off using two user-defined parameters and hence can be used in anytime manner. However, the framework in Bathla and Vasudevan (2023) cannot be used to infer marginals. This is because only the clique beliets in the last CTF account for all factors in the PGM. Beliefs in all other CTFs account for a subset of factors and thus, cannot be used for inference of marginals.
Contributions of this work: In this paper, we propose a method for marginal inference that uses the IBIA framework. We show that the approximation algorithm used in this framework preserves the within-clique beliefs. Based on this property, we modify the data structure generated by IBIA to add links between adjacent CTFs, We refer to the modified data structure clique tree forests (SLCTF). We propose a heuristic belief update algorithm that back pack-propsgstes beliefs from the last CTF to the previous CTFs via the links and re-calibrates each CTF that the updated beliefs account for all factors in the PGM. We also propose a greedy heuristic for the choice of links used for belief update. Results for several UAI benchmark sets show that our method gives an accuracy that is better than or comparable to the existing variational and sampling based methods, with competitive runtimes.
sequence of linked
For the special case of BNs, we show that if the incremental build step in IBIA is performed in the topological order of variables then (a) the estimated partition function is guaranteed to be one if no evidence variables are present (b) the prior marginals of all variables are consistent across all CTFs in the sequence and (c) once all the evidence variables have been added to the SLCTF, the posterior marginals of variables in subsequent CTFs are consistent. Our results show that using the topological ordering for BNs leads to better estimates of partition function, prior marginals and posterior marginals in most benchmarks.
2 Background
2.1 Discrete Probabilistic Graphical Models
Let X = X2, .x,} be a set of random variables with associated domains D (Dx, Dx.." ... D. The probabilistic graphical model (PGM) over X' consists of a set of factors, L where each factor &a E Φ is defined over a subset of variables, Scope(0x) = Xx. If D. denotes the Cartesian product of the domains of variables in Xx. then &a. D. + R 0. The joint probability distribution captured by the PGM is P(X)= = 1 III Ωa. where Z = Ex II. do is the partition function. PGMs can be broadly classified Markov networks (MN) which are the undirected models and Bayesian networks (BN) which are the directed models.
One method to perform exact inference involves converting the PGM into a clique tree (CT), which a hypertree where each node C, a clique that contains a subset of variables. We use the term C: as a label for the clique as well as to denote the set of variables in the clique. An edge between C, and C2 is associated with a set of sepset variables denoted St,; = C, n,. Hxact inference in a
CT is done using the belief propagation (BP) algorithm [Lauritenn and Spicgelhalter 1988) that is
2

---

Initialize
Incremental Build
CTFo
CTF1
Incremental
Infer
+ Infer
Add factors
Build
CTFR
Calibrate using Beliel Propagation
dmo
jb
frn
hi
it
k
while max-
fm
CTF
clique-size
fdhm
hmnj
< mcCp
dh
Aria
CTF k. k 11
CTF2
dmo
Approximate
Approximato
Reduce elique sizes
No
T eemptyy)
CTF2
Incremental Build
CTF
Infer
hk
mC8i
fmoh
ohkl
dhk
fhm
hl
Yes
m1
Stop
(a)
(b)
Figure 1: Conversion of the PGM, Φ. into sequence of calibrated CTFss (SCTF) using the IBIA frame- work. (a) Overall methodology. (b) Construction of SCTF (CTF1, CTF2) for a PGM, {o(d, m, o), Φ(j, h), @(i,1), 1), øff, , m. n), Φ(h, i), ((d, h, k), Φ d), Φ(j. m), ((k, o(f.o)] o)}: with mesp and mcssm set to 4 and 3 respectively. CT is formed using cliques corresponding to factors oid, m, o), o(j, h), d(i, l). CTFi contains all factors except (,,,,,0) o)s,o). These factors are added to C2
equivalent to two rounds of message passing along the edges of the CT. The algorithm returns a CT with calibrated clique beliefs 3(C;) and sepset beliefs ((S..j) In calibrated CT, all clique beliefs have the same normalization constant (Z) and beliefs of all adjacent cliques agree over the marginals of the sepset variables. The joint probability distribution, P(X), can be rewritten follows.
I,r,, B(C,)
P(X) = Z [I p(St.))
where Vr and e the set of nodes and edges in the CT. The marginal probability distribution of variable X; can be obtained by marginalizing the belief of any clique C' that contains X; as follows.
P(X.)
Σ B(C) CAX.
(2)
We use the following definitions in this paper.
Definition 1. Clique Tree Forest (CTF); Set of disjoint elique trees.
Definition 2. Clique size: The clique size cs of a clique C' the effective number of binary variables contained in C. It computed as follows.
cs
log2
II (Dx.))
(3)
X:
where Dx, the cardinality or the number of states in the domain of the variable X,. Definition 3. Prior marginals (P(X;)): It is the marginal probability of variable X; when the PGM
has no evidence variables.
Definition 4. Posterior marginals (P(X, = e)): It is the conditional probability distribution of
variable X,, given fixed evidence state e.
2.2 Overview of IBIA framework
Methodology: The IBIA framework proposed Bathla and Vasudevan (2023 converts the PGM
into sequence of calibrated CTFs (SCTF) with bounded clique sizes. IBIA starts with an initial

---

CTR, F. that contains cliques corresponding to factors with disjoint scope. Figure la illustrates the overall methodology used in the framework. It uses three main steps as described below.
Incremental Build: In this step, a CTF, CR is constructed by incrementally adding factors in the PGM to an initial CTF (CTFo 1,,)) until the maximum clique size reaches user-specified bound mcs Methods for incremental construction of CTs have been proposed in [atthla and Vasudevan [023] and Flores et al. 2002 Either of the two methods can be used incrementally add new factors.
Infer: In this step, all CTs in CTFF, are calibrated using the standard belief propagation algorithm.
Approximate: In this step, CTF; is approximated to give an approximate CTF, CT Fk,o that has clique sizes reduced to another user-specified bound mcCim.
As shown in Figure Ta IBIA constructs the SCT (CTF CTFF. by repeatedly using the incremental build, infer and approximate steps. This process continues until all factors in the PGM are added to some CTF in the SCTF. Figure [boshows the SCTF generated by IBIA for an example PGM, & (specified in the caption to the figure), with clique size bounds mcsp and mcsim set to 4 and 3 respectively. For the purpose of illustrating all steps, the disjoint cliques corresponding to factors ø(d, m. o), ofi, 1) and Φ h) are chosen as the initial CTF, F.. CTF; is constructed by incrementally adding factors CT All factors except o(k 1) and Φ(f. are added to CT These two factors are deferred since their addition results in clique sizes greater than mcsp = 4. CTF is calibrated using BP and then approximated to give FTF with clique sizes bounded to MC8im = 3. CT F2 is constructed by adding the remaining factors to F1. We will use this example to explain the steps in our method for inference of marginals.
Approximate step: Since our inference algorithm is based on the properties of the approximate CTF, we explain this step in more detail using the running example shown Figure Ib] Variables f, ki l and o in CTF, are also present in the deferred factors o(k, 1, o) and o(f, o). These variables are needed for the construction of subsequent CTFs and are called interface variables (IV). All other variables in CTFF are called non-inter non-interface variables (NIV). CTF1.a is initialized as the minimal subgraph that connects the IVs. This subgraph contains all cliques in CTF, except clique fmn. Approximation involves two main steps to reduce the number of cliques and clique sizes.
Exact marginalization: The goal of this step is to remove as many NIVs as possible while ensuring that the overall joint distribution is preserved. NIV is present in single clique hmj and is marginalized out from by summing over the states of j. The resulting clique hm is a mon-max clique that is contained in clique fdhmn, and is thus removed. NIV is removed after collapsing the two containing cliques hi and il. Exact marginalization of the other NIVs results in collapsed cliques with size greater than mcsim = 3, and is not performed.
2. Local marginalization: In this step, clique sizes are reduced by marginalizing variables from individual cliques with size greater than mcs while ensuring that (a) CTF1a is a valid CTF that satisfics the running intersection property (RIP) (b) a connected CT in CTF, remains connected in CTF,, la and (c) CTFFi, contains all IVs. To reduce the size of the large-sized clique fdhm, NIV is locally marginalized from this clique. In order to satisfy RIP, it needs to be marginalized from either clique dmo dhk as well as the corresponding sepsets. Here, d is locally marginalized from clique dmo and the corresponding sepsets to give CT CTFF,a as shown in the figure. Since all cliques containing are not collapsed before marginalization. this results in an approximate joint distribution. Propositions 5 and 6 in Bathla and Vasudevan (2023) show that all CT's in the approximate CTF obtained after exact and local marginalization are valid and calibrated.
3 Inference of marginals
In this section, we first discuss some of the properties satisfied by the SCTF generated by IBIA. Based on these properties, we then describe the proposed methodology for inference of marginals.
3.1 Properties of SCTF
We show that each CTF, in SCTF and the corresponding approximate CTF, CTFF... satisfy the following properties. The detailed proof' for these properties are included in the supplementary material and the main ideas used in the proofs are discussed here.

---

Proposition 1. The joint belief of variables contained within any clique in the approximate CTF, C. is the same as that C
Proof Sketch. Both exact and local marginalization involve summing clique beliefs over the states of a variable, which does not alter the joint belief of the remaining variables in the clique.
Proposition 2. The clique beliefs in Fg account for all factors added to (CT FI.......... CTFF).
Proof Sketch. CTF, is exact, with clique beliefs corresponding to the partial set of factors used to form CTF, CTFi,, is calibrated CTF that obtained after approximating CTF,, Thus, the joint belief of variables in CTFFi, ia is an approximation of the beliefs encoded by factors added to CTF, C2 is obtained after adding new factors to CT Therefore, after calibration, clique beliefs in CTF2 account for factors added to CTF, and CTF2. The proposition follows. since the same argument holds true for all CTFs in the sequence.
BNs can be handled in similar manner as MNs by using the undirected moralized graph correspond- ing to the BN. Another possibility is to use the directed acyclic graph (DAG) corresponding to the BN to guide the incremental build step. In contrast to MNs where all factors are un-normalized, each factor in a BN is the conditional probability distribution (CPD) of a variable y given the state of its parents in the DAG (Pay). Factors corresponding to the evidence variables are simplified based on the given state and hence become un-normalized.
For BNs, the following properties hold true if each CTF in the SCTF is built by adding factors in the topological order. By this, we mean that the factor corresponding to the variable y added only after the factors corresponding to all its parent variables, Pay, have been added to some CTF in the sequence. Let Y& denote the set of variables whose CPDs are added during construction of CTFF. Fk. eg denote the evidence states of all evidence variables in Y3 and Pay, denote the parents of variables in the set Yn.
Proposition 3. The product of factors added in CTFs, {CTF,..... C1FF) } is valid joint probability distribution whose normalization constant is the probability of evidence states G1, Ck-
Proof. For each variable y [Y,,.... YrJ, the corresponding CPD, P(y) Pay) is added to some CTF in FI. CT CTFFs.. }-). The proposition follows since the CPDs corresponding to parents of
always added CTF before the CPD of y is added.
Proposition 4. The normalization constant of the distribution encoded by the calibrated beliefs in CTF2 is the estimate of probability of evidence states eI...., Ck.
Proof Sketch. Using Proposition 3 the normalization constant (NC) of the distribution encoded by CTF, is P.er). Using Proposition 1 the approximation algorithm preserves the within-clique beliefs and hence the NC. Thus, the NC of CTFF,a is also P(e.). Although the NC is the same, the overall distribution corresponding to CTFi,a la. is approximate due to local marginalization. C2 is constructed by adding CPDs of variables in Y₂ to CTF1.a CPDs of parent variables in Pay, added either in CTFi or C2 Hence, after calibration, we get a valid probability distribution with NC as the estimate of probability of evidence states e1, e2. A similar procedure can be used to show that the property holds for all CTFs.
O
Corollary For a BN with no evidence variables, the normalization constant of any CT in CTF, guaranteed to be one.
Theorem 1. Let Ig denote the index of the last CTF in the sequence where the factor corresponding evidence variable is added. The posterior marginals of variables present in CTFs (CTF& k Ig Y are preserved and can be computed from any of these CTFs.
Proof Sketch. Once all evidence variables added, additional CPDs added in each new CTF in (CTF&, & > Tg correspond to the successors in the BN. Since none of the successors are evidence variables, the corresponding CPDs normalized and hence cannot change the beliefs of the previous variables.
Corollary 2. For a BN with no evidence variables, the estimate of prior marginals obtained from any CTF in the sequence is the same.
5

---

3.2 Proposed algorithm for inference of marginals
We first explain our approach for estimation of marginals with the help of the example shown in Figure Tb Following this, we formally describe the main steps in our algorithm.
The SCTF generated by IBIA for the example in Figure Tb contains two CTFs, CT and CT F2. Using Proposition 2 know that calibrated clique beliefs in CT account for all factors in the PGM, O. Therefore, the marginals of all variables present in it can be inferred using Equation 2 However, clique beliefs in CTF, do not account for factors &f L,,,,, o) and Φ(f, o) which were added during the construction of C2 Therefore, in order to infer the marginals of variables n, that are present only in CTF,, we need to update the beliefs account for these two factors.
Figure shows CTF,, CTF1, and CTF2 for the example. Using Proposition ! we know that the joint belief of variables present within any clique in CT aa is the same that CTF. However, this belief changes when new factors are added during the construction of CTF2. For instance, 3(Cy') = Ey B(C²) + E. B(2)). To reflect the effect of new factors added in CT the joint belief of variables in clique C2 can be updated follows.
B(C2) EBC(2 E0( d
Bupdated
To make sure that CTF; remains calibrated, this must be followed by single round of message passing in CTF: with C2 as the root node. It clear that a sim- ilar belief update is needed for all the variables in CTFi.a However, every up- date and subsequent round of message passing will override the previous updates.
Hence, the beliefs in CTF, will only approximately reflect the effect of ad- ditional factors in C2 To improve accuracy, we propose a heuristic proce- dure for belief update sequence.
CTF:: Co fmm
C2 : fdhm
C. hmj
C2 hi
Cs
fkm
C dma
C3 dhk
mo
dhk
Formally, the steps in our algorithm are as follows. Variables present in Fr... are present in both CTF, and CTF++1 We refer to these variables the link variables. We first find links between corresponding cliques C CTF C' E CTFaa and C E CTF++1- Each link (C, C", C) is associated with a set of link variables Vi C C². For the example, links between CTF,, CT F1,a and F2, and the corresponding link variables are shown magenta in Fig- ure 2 The first part of link contains cliques C' and C. It is obtained as fol- lows.
CTF
G mo
Cy's f
C1' : hl
Ca' : dhk
CTF2:
C fmoh
C. ohkl
Cs dhd
Figure 2: Links between corresponding cliques in CTF, CTFi, and CTF2 for the example shown in Figure Ib
All links (C,C", C) are marked with dashed magenta lines and the link variables corresponding each link are marked in magenta color.
(a) If O' is obtained after collapsing a set of cliques } in CTFF. C' is linked each of [C1.-.. ). For example, C2' is linked to C4 and Cs, which were collapsed during exact marginalization of variable i.
(b) If C' is obtained from C in CT after local marginalization. C' is linked to C. In the example, cliques C₁' and C2' are obtained after local marginalization of variable d from cliques C and C2 respectively. Hence, the corresponding tuples are (C1, C1') and (22,
(c) If C' is same as clique C' in CTFF, C' is linked to C. For example, Cg is linked to Cy'.
The second part links C' to Ö in CTF such that C' Ō. This is always possible since CTFF+1 is obtained after incrementally modifying CTFi, to add new factors. Thus, each clique in CT Fr.o is contained in some clique in CT CTF1 For example, C2' Cg and the link is (C1, Ci's C2).

---

Let L3 denote the set of links between CTFR and CTF++1- We refer to the modified data structure consisting of the sequence of calibrated CTFs, SCTF- (CTFF) and a list of links between all adjacent CTFs, ST. [Tx,), ), as the sequence of linked CTFs (SICTTF). Once the SLCTF is created, starting from the final CTF the SLCTE, we successively back pack-propagate beliefs to the preceding CTFs via links between adjacent CTFs. To back-propagate beliefs from CT to CT Fk. we choose a subset of links in Ly based on heuristics, which will be discussed later. Then, for each selected link (C, C", C),, we update the belief associated with clique C' as follows.
B(C) Σ 3()) CIV
Bupdaten(())
E CWV
B(Ō)
where, = Cn This is followed by one round of message passing from C. to all other cliques in the CT containing C. Once all CTFs are re-calibrated, we infer the marginal distribution of a variable using Equation 2 from the last CTF in which it is present.
For BNs, if incremental build is performed by adding variables in the topological order, then as shown in Theorem T the singleton marginals are consistent in CTFs (C2TFk>)gh where L is the index of the last CTF to which the factor corresponding to an evidence variable is added. Therefore, this case, back-prot prockaprpagttionn of beliefs can be performed starting from FTF,,, instead of starting from the last CTF. This reduces the effort required for belief update.
Heuristics for choice of links: To ensure that beliefs of all CT's in CTF: are updated, at least one link must be chosen for each CT. It is also clear that for any CT in CTF; more than one link may be required since variables that have low correlations in CTF2 could become tightly correlated when new factors are added in CT FTTF++1. However, belief update via all links is expensive since a round of message passing is required for each link. Based on results over many benchmarks, we propose the following greedy heuristic to choose and schedule links for backward belief update.
(a) To minimize the number of selected links, we first choose a subset of link variables for which the difference in posterior marginals in adjacent CTFs, CTFF,, and FTF is greater than a threshold. Next, for belief update, we select minimal set of links that cover these variables.
(b) The updated beliefs depend on the order in which the links are used for update. Based on the difference in marginals, we form priority queue with the cliques containing link variables that have the lowest change in marginals having the highest priority. This is to make sure that large belief updates do not get over-written by smaller ones. This could happen for example, if two variables, vi and u2 that are highly correlated in CTF2 become relatively uncorrelated in CTFF441 due the approximation. Assume that new factors added to CTF affect UJ but not U2. A belief update via the link containing U1 will make sure that its belief consistent in CTFF and CT Later, we perform a belief update using a link containing 22, the previous larger belief update of U1 will be overwritten by something smaller since the belief of 22 is not very different in the two CTFs.
Let NETF be the number of CTFs in the sequence, and N₁ be the maximum number of selected links between any two adjacent CTFs. IBIA requires 2NcTF rounds of message passing for calibrating CTFs and (NCTF- - 1)N, rounds for belief update. Therefore, the runtime complexity of IBIA is D, mccp)). ). To perform backpropagation of beliefs, all CTFs need to be stored and the memory complexity is O O(NeTF2mce;)
Complexity:
4 Results
All experiments were carried out on an Intel 19-12900 Linux system running Ubuntu 22.04.
For each non-evidence variable X,, we measure error terms of Hellinger distance between the exact marginal distribution P(X,) and the approximate marginal distribution Q(X,). It is computed as follows.
Error metrics:
Σ (V) VQ(X=
HD
(5)
V2 (Dmmiin(X.))
We use two metrics namely, the average Hellinger distance (denoted as Davg) and the maximum Hellinger distance (denoted as DD over all non-evidence variables in the network.
7

---

Table I: Comparison of average Havg and average mD (shown in gray background) obtained using various inference methods with two runtime constraints, min and 20 min. The minimum error obtained for each time limit is highlighted in bold. Entries marked as '-' where all instances could not be solved within the set time limit. The total number of instances solved by each method is shown in the last row. eUg: average number of evidence variables, f/ average number of variables, fa: average number of factors, Wa average induced width and dm,: average of the maximum variable domain size.
Total Average stats
min
20 min
#Inst (ella; Na: fa: Wa, dma) LBP WMB IJP ISSwe IBIA20
LBP WMB UJP ISSwe
IBIA23
BN
97
(76.637,637.28.10))
0.037
2E-4
0.023 0.025
6E-5
0.228
9F-3
0.230 0.170
2F-3
GridBN
29
(0,595,595,37,2)
0.075 0.066 0.011 0.003
5E-6
0.075 0.048 0.010 0.001
2F-7
0.478 0.416 0.111 0.051
7E-4
0.478 0,381 0.094 0.015
1E-4
Bulearn
26
(0.256,256,7.16)
0.010 0.005 0.011 0.012
7E-5
0.010 SE-6 0.008 0.006
7E-6
0.089 0,021 0.050 0.064
0.002
0.089 1E-4 0.025 0.028 2E-4
Pedigree
24
(155,853,853324.55)
0.075 0.018 0.035 0.033
0.009
0.075 0.015 0.033 0.021 0.008
0.555 0.253 0.470 0.292 0.204
0.555 0.194 0.446 0.234 0.198
Promedas 64
(7.618,618,21,2)
0.032 0.055 0.124 0.030
0.013
0.032
0.043 O. 120 0.021
0.010
0.168 0.295 0,504 0,139 0.086
0.168
0.245 0,487 0.096
0.072
DBN
36
(653.719.14205.29.2)
0.069 0.081 0.016 0.020
0.018
0.060 2E-6
0.003
0.883 0.919 0.766 0.261
0.544 0.879 2F.4
0.098
ObjDetect 79
(0,60;210,6,16)
0.022 0.001 0.004 0.018
0.002
0.022
2F,4 3R-5 0.009 4F,4
0.130 0.010 0.037 0.189
0.020
0.130
0.003 3E-4 0.061 0.006
Grids
8
(0,250,728,22,2)
0.433 0.146 0.247 -
0.088
0.433 0.089 0.123 0.056 0.002
0.905 0.343 0.713
0.300
0.905 0.221 0.423 0.209 0.099
CSP
12
(0.73,369,12,,)
0.019 0.033 0.026-
0.002
0.019 0.022 0.017 0.054 2E-4
0.066 0.1 0.134 -
0.011
0.066 0.057 0.073 0.093
0.003
Segment 50
(,222,851,17.2).
0.035 1E-4 5E-6 5E-6
6E-5
0.035 5E-6 5E-6 5E-6
1E-7
0,258 0.002 7E-5 7E-5
0.001
0.258 7B-5 7E-5 7E-5
4E-7
Protein
68
(0.59,176,6,,7)
5E-4 0.005
0.003
0.003
6E-4
SE-4
0.003
0.007
0.001
3E-5
0.007 00102
0.094 0.049
0.039
0.007 0.066
0,230
0.015
0.002
#lnst
493
481 493
487
485
493
485
493
491
487
493
Benchmarks: We used the benchmark sets included in UAI repository [Ihler 2006 and the Bayesian network repository [Scutari] 2007). We classify instances for which exact solutions are present the repository as 'small' and others as 'large".
Methods used for comparison: In the UAI 2022 inference competition [UAI 2022 the uail4_nn 4_mo solver had the highest score for the MAR task. It is an amalgam of solvers that dumps solutions with different methods based on the given time and memory constraints. It uses loopy BP (LBP), generalized BP on loopy graphs where outer regions are selected using mini-bucket heuristics, and cutset conditioning of GBP approximations. The implementation of this solver is not publicly available. Therefore, we have compared our results individually with methods that belong to categories of methods used in uai14 mail4_mar. mar. This includes LBP Murphy et al., 1999], IJGP [Mateescu et al.) 2010) and sample search [Gogate and Dechter 2011] which is an importance sampling based technique that uses an IJGP based proposal and cutset sampling (referred to as 'ISSwe' in this paper).
We also compare our results with weighted mini-bucket elimination (WMB) [Liu and Ihler 2011]
Additional results showing a comparison with results published in Kelly et al. 2019 are included in the supplementary material.
Evaluation setup: The implementation of LBP and WMB were taken from LibDAI [Mooi] 2010 2012) and Merlin [Marinescu] 2016) respectively. For UJGP and ISSwc, we used implementa- lions Gogate 2010 2020 provided by the authors of these methods. LBP, IJGP, ISSwe and WMB are implemented in C++ IBIA on the other hand has been implemented in Python3 and is thus, at disadvantage in terms of runtime. We report results with runtime limits of 2 min and 20 min for small instances. In all cases, the memory limit was set to 8GB, which is the same as that used in UAI 2022 competition [UAI, 2022). For IBIA, we set the maximum clique size bound mesp to 20 (referred to as 'BBIA00)) when the time limit is 2 min and we set it to 23 (referred to as '7BIA23") when the time limit is 20 min. mesim is empirically chosen as 5 less than mcsp. The evaluation setup used for other methods is included in the supplementary material.
8

---

Results: Table has the results for the small benchmark sets. It reports the average of H aog and mDmoz over all instaness in each set. We compare results obtained using LBP, WMB, IIP., IBÍA20, IBIA23 and ISSwe for both time constraints. The minimum error obtained for each time limit is marked in bold. IBIA20 and IBIA23 solve all small instances within 2 min and 20 min respectively. In 2 min, the accuracy obtained with IBIA20 is better than all other solvers for most benchmarks. For ObjDetect, Segment and Protein, it is comparable to WMB, WJGP/ISSw and LBP respectively, which give the least errors for these testcases. In 20 min, IBIA23 gives lower or comparable errors in all testcases except DBN and ObjDetect. For DBNs, ISSwe reduces to exact inference in most instances and hence error obtained is close to zero. For ObjDetect, IIGP gives the least error closely followed by IBIA23. Note that for many benchmarks the accuracy obtained with IBIA20 in 2 min is either better than or comparable to the accuracy obtained with other solvers in 20 min.
comparison of IBIA with results published in Kelly et al. (2019] for Gibbs sampling with Rao- blackwellisation (ARB) and IJGP is included in the supplementary material. It is seen that error obtained with IBIA is lower than both methods in majority of the testcases.
For BN instances, Table 2 compares the results obtained using IBIA20 when CTFs are con- structed by adding factors in the topological order (columns marked as 'TP') with that obtained using a non-topological order (columns marked as 'NTP"). We compare the maximum error in partition function (PR) and the average maza over all instances in each benchmark set.
We observe that the topological or- dering gives better accuracy for both PR and marginals in all testcases ex- cept Pedigree. The advantage of this ordering is that once all the evidence variables are added, no belief-update is needed is needed for the subsequent CTFs (using Theorem [.. So, the num- ber of belief update steps is lower, resulting in lower errors. However, drawback of this ordering is that is rigid and it sometimes results in larger number of CTFs in the sequence which could lead to larger errors if all the evidence variables are added in later CTFs. When no evidence variables are present (e.g.
Table 2: Comparison of maximum error in PR and aver- age maa obtained using IBIA20 with CTFs constructed by adding factors in topological order (shown in columns marked 'TP') and that obtained using a non-topological order (shown in columns marked 'NTP"). 6t/: Average number
of evidence variables, APR where PR and PR are estimated and exact values.
1og PR - log PR"
Max ApR
Avg HD mar
#Inst
em
NTP
TP
NTP
TP
Bnlearn GridBN Promedas
26
0
0.02
0
0,023
0.002
29
0.09
0
0.231
0.001
1.5
0.4
0.322
0.086
BN
97
76
0.07
0.02
0.116
0.009
Podigree
24
159
0.4
0.7
0.098
0.204
GridBN, Bnlearn), both runtime and memory complexity is lower with topological ordering since
marginals are consistent in all CTFs (using Corollary ( and belief update not needed. The average
runtime with and without topological ordering was Is and 146s respectively for GridBN instances and 0.3s and 1.3s for Bnlearn testcases.
To evaluate the scalability of the proposed algorithm, we it for large networks where the ex- solutions are not known. Ta- ble the percentage of large instances in each bench- mark set that could be solved us- ing IBIA within min. 20 min and 60 min. For this experiment, we start with mc and al- low it to increase if incremental build results in CTF with larger clique sizes. IBIA could solve all large instances in benchmark sets BN, Promedas, ObjDetect and Segmentation and most in- stances in Protein within 20 min. For other benchmarks, additional
Table 3: Percentage of large instances in each benchmark set solved by IBIA within 2, 20 and 60 minutes. eVa: average num- ber of evidence variables, e,; average number of variables, fa: average number of factors, W, average induced width and dm,:: average of the maximum domain-size.
Total #lnst
Average stats
Instances solved (%)
(ev., Un. Ju, Wa, dm..)
min 20 min 60 min
BN
22
(188,1277,1272.511
64
100
100
Promedas
171
77
100
100
ObjDetect
37
(0.60.8830.99.17
27
100
100
Segment
50
(0,229,85 192
100
100
100
Protein
395
(0.306.1192.21.1)
75
97
98
DBN
78
(784.944,47206.6022
38
77
77
Grids
19
(0.3432.10244,1172,
16
37
58
CSP
54
(0,294,11122,115541
31
54
59
Type4b
82
(4272,
0
9
29

---

instances could be solved when the runtime was increased to 60 min. The memory required for the remaining Grids, DBN, CSP and Protein instances more than GB. The increased m usage is due to the following reasons. Firstly, all calibrated CTFs in the SLCTF need to be stored in order to allow for back-propagant of CTFs. The average number of CTFs in the remaining Grid, DBN and CSP benchmarks is 22, 58 and 80 respectively. Secondly, for benchmarks with large variable domain sizes, the number of variables present in each clique in CTF is small. Therefore, approximation using exact and local marginalization becomes infeasible and the subsequent CTFs have clique sizes greater than mcsp. which results in increased memory usage. This is seen in 9 out of 395 Protein instances and 12 out of 54 CSP instances. In addition to memory, the remaining Type4b instances also require additional runtime. This is because during belief update of each CTF, we perform one round of message passing for each selected link and the number of links is large in these instances.
of beliefs and the memory required increases with the number
5 Discussion
While the belief update algorithm performs well for most benchmarks, it has some limitations. It is sequential and is performed link by link for each CTF that needs to be updated. The time and space complexity depends on the number of CTFs in the sequence and the number of selected links, which large in some testcases. Also, after belief-update of all CTFs completed, beliefs of variables present in multiple CTFs need not be consistent. However, good accuracies obtained when beliefs are inferred from the last CTF containing the variable. For BNs, we found that building CTFs in the topological order gives larger errors in some cases. A possible extension would be to have an efficient build strategy where the ordering is decided dynamically based on the properties of the graph structure.
Limitations:
Comparison with related work: IBIA is similar to mini-bucket schemes in the sense that the accuracy-complexit tradeoff is controlled using user-defined maximum clique size bound. While mini-bucket based schemes like IJGP [Dechter et al., 2002] and join graph linear programming [Thler et al. 2012 use iterative message passing in loopy graphs, others like mini-bucket elimination (MBE), WMB Liu and Ihler [011] and mini-clustering (Matcescu et al., 2010] are non-iterative approaches that approximate the messages by migrating the sum operator inside the product term. In contrast, IBIA constructs a sequence of clique trees. It performs belief propagation on approximate clique trees so that messages are exact and there no issues of convergence.
Unlike sampling based techniques, there no inherent randomness in IBIA that is each run gives the same results. There could be variation if the order in which factors are added is changed. However, this variation is minimal since subsets of factors are added together in the incremental build step. In that sense, it is like mini-bucker based methods where results are the same if the variable elimination order and the partitioning technique used to generate the initial choice of mini-buckets are the same.
In order to construct the sequence, IBIA requires fast and accurate method to approximate clique trees by reducing clique sizes. The aim to preserve as much as possible, the joint distribution of the interface variables. This is achieved by marginalizing out variables from large-sized cliques and a minimal set of neighbors without disconnecting clique trees. IBIA gives good accuracy since variables that are removed are chosen based on a mutual information (MI) based metric and a sufficient number of non-interface variables are retained so that a CT is never disconnected. In contrast, the Boyen Koller (BK) [Boyen and Koller 1998, Murphy| 2002] and factored frontier (FF) approximations, although fast, retain only the interface variables which can disconnect the CT resulting in larger errors due to the underlying independence approximation. The thin junction tree approximation proposed in Kjærulff [1994] and Hutter et al. [2004) split cliques that contain a pair of variables that is not present in any of its sepsets. However, if there are large cliques that have only sepset variables (which is typical in most benchmarks), then the split has to be done iteratively starting from leaf nodes of multiple branches, until the large-sized clique can be split. When such cliques are centrally located in the CT, this process is both conecconu and would result in approximation of a much larger set of cliques. Similar to BK and FF, this method can also disconnect the CT.
The other thin junction tree methods [Bach and Jordan| 2001 Elidan and Gould 2008 Datna and Guestrin 2009 choose an optimum set of features based on either KI. distance or a MI based metric. They cannot be directly used since IBIA requires a good approximation of the joint distribution of only the interface variables. Also, these methods are typically iterative and not very fast.
10

---

References
Sakshi Agarwal, Kalev Kask, Alex Ihler, and Rina Dechter. NeuroBE: Escalating neural network approximations of bucket elimination. In Uncertainty in Artificial Intelligence, pages 1 11-21, 2022.
Francis Bach and Michael Jordan. Thin junction trees. Advances in neural information processing systems, 14, 2001.
Shivani Bathla and Vinita Vasudevan. IBIA: An incremental build-inferr-approxinat framework for approximate inference of partition function. Transactions on Machine Learming Research, 2023, ISSN 2835-8856.
Xavier Boyen and Daphne Koller. Tractable inference for complex stochastic processes. In Uncer- tainty in Artificial Intelligence, pages 33-42, 1998.
Filjor Broka. Abstraction sampling in graphical models. In AAAI Conference on Artificial Intelligence, pages 8010-8011, 2018
A. Choi, H. Chan, and A. Darwiche. On Bayesian network approximation by edge deletion. In Uncertainty in Artificial Intelligence, pages 128-135, 2005.
Arthur Choi and Adnan Darwiche. An edge deletion semantics for belief propagation and its practical impact on approximation quality. In National Conference on Artificial Intelligence and Innovative Applications of Artificial Intelligence Conference, pages 1107-1114, 2006.
Arthur Choi and Adnan Darwiche. Relax, compensate and then recover. In JSAI International Symposium on Artificial Intelligence, pages 167-180, 2010.
Shahaf Dafna and Carlos Guestrin. Learning thin junction trees via graph cuts. In Artificial Intelligence and Statistics, pages 113-120, 2009.
Rina Dechter, Kalev Kask, and Robert Mateescu. Iterative join-graph propagation. In Uncertainty in 2002.
Artificial Intelligence, pages
Gal Elidan and Stephen Gould. Learning bounded treewidth Bayesian networks. Journal of Machine Learning Research, 9(2)), 2008.
M Julia Flores, José A Gámez, and Kristian G Olesen. Incremental compilation of Bayesian networks. In Uncertainty Artificial Intelligence, pages 233-240, 2002.
Brendan J Frey and David MacKay. A revolution: Belief propagation in graphs with cycles. In Advances in Neural Information Processing Systems, volume 10, 1998.
Tal Friedman and Guy Van den Broeck. Approximate knowledge compilation by online collapsed importance sampling. Advances in neural information processing systems, 31, 2018.
Alan E Gelfand. Gibbs sampling. Journal of American Al Association, 95(452):1300-1344 2000.
Vibhav Gogate. Iterative join graph propagation. porrate/ijgp.o html 2010. Accessed: 2023-04-15.
utdallas.
Vibhav Gogate. sampligg and samplesearch (PR and MAR tasks). https://github.cr dechterlab/ijgp samplesearch 2020. Accessed: 2023-01-15.
Vibhav Gogate and Rina Dechter. Samplesearch: Importance sampling in presence of determinism. Artificial Intelligence, 175(2))694-729, 201
Tom Heskes, Kees Albers, and Bert Kappen. Approximate inference and constrained optimization. In Uncertainty in Artificial Intelligence, pages 313-320, 2003.
Frank Hutter, Brenda Ng, and Richard Dearden. Incremental thin junction trees for dynamic Bayesian networks. Darmstadt University of Technology, Tech. Rep, 2004.
Alexander Thler. UAI model files and solutions. http://sli... ics. uci edu/"ihler"""" -aai-dta/ 2006. Accessed: 2021-10-15

---

Alexander T Ihler. Natalia Flerova, Rina Dechter, and Lars Otten. Join-graph based cost-shifting schemes. In Uncertainty Artificial Intelligence. 2012.
Kalev Kask, Bobak Pezeshki, Filjor Broka, Alexander Ihler, and Rina Dechter. Scaling up and/or abstraction sampling. In International Joint Conference Artificial Intelligence, pages 4266-4274, 2020.
Craig Kelly, Somdeb Sarkhel, and Deepak Venugopal. Adaptive Rao- Blackwellisatiion in Gibbs sampling for probabilistic graphical models. In Artificial Intelligence and Statistics, pages 2907- 2915. PMLR, 2019.
Uffe Kjærulff. Reduction of computational complexity in Bayesian networks through removal of weak dependences. In Uncertainty in Artificial Intelligence, page 374-382, San Francisco, CA, USA, 1994.
Steffen L Lauritzen and David Spiegelhalter. Local computations with probabilities on graphical structures and their application to expert systems. Journal of the Royal Statistical Society: Series B (Methodological), 50(2):157-194, 1988.
Peng Lin, Martin Neil, and Norman Fenton. Improved high dimensional discrete Bayesian network inference using triplet region construction. Journal of Artificial Intelligence Research, 69:231-295, 2020.
Qiang Liu and Alexander Ihler. Bounding the partition function using holder's inequality. In International Conference on Machine Learning, pages 849-856, 2011.
Qi Lou, Rina Dechter, and Alexander Ihler. Anytime anyspace and/or search for bounding the partition function. In AAAI Conference on Artificial Intelligence, volume 31, 2017a.
Qi Lou, Rina Dechter, and Alexander T lhler. Dynamic importance sampling for anytime bounds of the partition function. Advances in Neural Information Processing Systems, 30, 2017b.
Qi Lou, Rina Dechter, and Alexander Ihler. Interleave variational optimization with Monte Carlo sampling: A tale of two approximate inference paradigms. In AAAI Conference on Artificial Intelligence, volume 33, pages 7900-7907, 2019.
Radu Marinescu. Merlin. http:://ggaabb.ooo////m///////// 2016. Accessed: 2021- 10-15.
Radu Marinescu, Junkyu Lee, Rina Dechter, and Alexander Ihler. AND/OR search for marginal map. Journal of Artificial Intelligence Research, 63:875-921, 2018.
Radu Marinescu, Akihiro Kishimoto, Adi Botea, Rina Dechter, and Alexander Ihler. Anytime recursive best-first search for bounding marginal map. In Proceedings of the AAAI Conference Artificial Intelligence, pages 7924-7932, 2019.
Robert Mateescu, Kalev Kask, Vibhav Gogate, and Rina Dechter. Join-graph propagation algorithms. Journal of Artificial Intelligence Research, 37:279- -28, 2010.
Joris M. Mooij. libDAI: A free and open source C++ library for discrete approximate inference in graphical models. Journal of Machine Learning Research, 11:2169-2173, August 2010.
Joris M. Mooij. libDAI A free/open source C++ library for discrete approximate inference. https://gitan cww httom///bsssaiiiiDA/... 2012. Accessed: 2021-10-15.
Joris M. Mooij and Hilbert J. Kappen. Loop corrections for approximate inference on factor graphs. Journal of Machine Learning Research, 8(40): 2007.
Kevin P. Murphy, Yair Weiss, and Michael I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artificial Intelligence, pages 467-475, 1999.
Kevin Patrick Murphy. Dynamic Bayesian networks: Representation, inference and learning, disser- tation. PhD thesis. UC Berkley, Dept. Comp. Sci, 1, 2002.
12

---

Yasaman Razeghi, Kalev Kask, Yadong Lu, Pierre Baldi, Sakshi Agarwal, and Rina Dechter. Deep bucket elimination. International Joint Conference on Artificial Intelligence, pages 2021.
Dan Roth. On the hardness of approximate reasoning. Artificial ( 1996.
Marco Scutari. Bayesian network repository. http::///www..nnaaarrr.co/oooppr 2007. Accessed: 2021-10-15.
UAI. UAI 2022 - Competition.
2022.
Jonathan S Yedidia, William T Freeman, Yair Weiss, et al. Generalized belief propagation. In
Advances in Neural Information Processing Systems, volume 13, pages 689-695, 2000.
13


Reviews:
[{"review_id": "uVCz6mHh9q", "reviewer": "Reviewer_vgXS", "summary": "The paper proposes a new approximate inference method for marginals of probabilistic graphical models (PGMs) based on the incremental build-infer-approximate (IBIA) framework. IBIA was introduced by Bathla & Vasudevan in an arXiv preprint in April 2023 to estimate the partition function (normalizing constant). It achieves this by converting the PGM into a sequence of clique tree forests (SCTFs) with a user-defined clique size bound. The sequence is constructed iteratively: the first step (Build) adds factors of the PGM to the current CTF until the maximum clique size is reached; the second step (Infer) calibrates all clique trees using standard belief propagation; and the final step (Approximate) reduces the clique size to another user-defined bound.\n\nThis paper builds upon the previous IBIA work in the following ways: it observes and proves several properties of the SCTF generated by the IBIA framework, which it uses to design an extension of IBIA to approximate marginals (in addition to the partition function). This extension works by introducing links between cliques in subsequent steps of the SCTF based on shared variables, called sequence of linked CTFs (SLCTF). It backpropagates beliefs from the last CTF to previous CTFs via the links and re-calibrates each CTF with one round of message passing. Finally the marginal distribution can be inferred from the CTF containing the desired variable. The paper also describes heuristics for the choice of links and notes that in the directed case (i.e. Bayesian networks), it is advantageous to add variables in topological order during the incremental build step.\n\nThe experimental evaluation compares with two existing methods, loopy belief propagation (LBP) and iterative join graph propagation (IJGP), on benchmarks from recent UAI competitions with time limits of 2 min, 20 min, and, for some benchmarks, 1h. They report the number of instances solved within the time limit and the average and maximum Hellinger distance over all non-evidence variables. The new method performs performs better than LBP and IJGP on most examples and is similar on the remaining ones, even though IBIA is implemented in Python whereas the baselines are written in C++.", "questions": "(I will update my rating if the author's answers address my concerns.)\n\nMy main question is about the UAI 2022 competition: it seems to me that other submissions there performed better than the baselines in this paper (LBP, IJGP). Is this understanding correct? If so, what is the reason for choosing what seem to be inferior baselines?\n\nI was also confused by line 375, which seems to say that topological ordering gives large errors sometimes. Previously, it sounded like topological ordering was essential for good performance and for the theoretical results in Section 3.1 (line 163). Can you clarify the drawbacks and benefits of topological ordering? Do you know why it causes large errors sometimes?\n\nI also noticed some confusing notation, which I mention here for lack of a better place in the review form:\n- equation (1): (i - j) looks like subtraction. In graph theory, an edge is often written as a pair (i, j) instead.\n- equation (3): I don't understand the point of the quantifier ($\\forall$) in the product notation and have never seen this before.\n- line 100: $CTF_{k-1,a}$ first looked like a double-index to me, but I assume the \"a\" just stands for \"approximation\".\n\nTypos:\n- line 69: I think it should be $Scope(\\phi_\\alpha)$\n- Figure 1, incremental build: I think it should be \"while\" instead of \"until\"", "limitations": "The authors have adequately discussed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed approximate inference method is interesting and improves the performance compared to existing methods (LBP and IJGP). The extension of the IBIA framework with links is new and useful. The explanation is adequate given the page constraints and the use of a running example is very helpful to understand the algorithm.", "weaknesses": "The contribution of this paper (adding links) seems to me to be relatively minor compared to the introduction of IBIA itself in previous work. Extending it in some way to relate successive CTFs (here done via links) seems quite obvious (although that might be the benefit of hindsight).\n\nRegarding the experimental evaluation, I had a look at the recent UAI 2022 competition, since the paper mentions that the same benchmarks were used for recent UAI competitions, if I understand line 14 correctly. It looks like IBIA was a competitor there and while performing well, it did not come in first, as the experimental evaluation of this paper might suggest. For this reason, I'm not convinced that the baselines in the experimental section are representative of the field of PGM inference and whether comparisons with more methods are needed to get an accurate picture of IBIA's performance (see my question to the authors below).\n\nAs a minor point: while the presentation is generally fine, I found the notation confusing at times, see below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions. We would also like to thank you for pointing out the typos. We will fix them in the revised version.  Following are our responses to each question.\n\n\n> My main question is about the UAI 2022 competition: it seems to me that other submissions there performed better than the baselines in this paper (LBP, IJGP). Is this understanding correct? If so, what is the reason for choosing what seem to be inferior baselines?\n\nApart from IBIA, there were two other solvers for the MAR task in UAI2022 competition. \n1. $uai14$\\_$mar$: While this solver had the highest score, it is an amalgam of solvers that dumps solutions with different methods based on the available time and memory constraints. As described by the participants, \"they begin by reparameterizing the model using loopy BP, then build a series of generalized BP reparameterizations whose outer regions are selected via mini-bucket, eventually transitioning, when there is much more time than memory to cutset conditioning of GBP approximations.\" \n\n* The implementation of $uai14$\\_$mar$ is not publicly available. Therefore, we have individually compared our results with methods that belong to categories of methods used in $uai14$\\_$mar$, namely, Loopy BP (LBP), IJGP which performs generalized BP on loopy graphs obtained using mini-bucket heuristics and IJGP with cutset sampling (ISSwc).\nFor IJGP and ISSwc, we have used open-source implementations by the authors and for LBP, we have used the LibDAI tool which has been used for comparison in several latest works (Shih, A. \\& Ermon, S., 2020; Agrawal, D.K., Pote, Y., \\& Meel, K.S. (2021)) and was among the winners of UAI2010 competition. We want to point out that as a standalone method, IBIA performs better than each individual solver used in the amalgam.\n\n\n2. $lbp$\\_$mar$: This performs loopy BP and was seen to give much lower scores than IBIA in the 20 min category, which is consistent with our results. \n\nWe would also like to point out that we have compared the average Hellinger distances over all instances in each benchmark set (total of 493 instances). However, in the competition, the reported score (which is not directly Hellinger distance)  is the average score over a subset of 88 instances from different benchmarks in the final set and 123 instances in the tuning set. IBIA had a comparable score as $uai14$\\_$mar$ for the tuning set and lower for the final set. While the overall trend can be compared, a direct one-to-one comparison should not be made.\n\n> Can you clarify the drawbacks and benefits of topological ordering? Do you know why it causes large errors sometimes?\n\nThe advantage of topological ordering is that once all the evidence variables are added,  no belief-update is needed for the subsequent CTFs (using theoretical results discussed in Section 3). So, the number of belief-update steps is lower, resulting in lower errors.\n\nThe drawback of topological ordering is that it is rigid and it sometimes results in a larger number of CTFs in the sequence which could give rise to larger errors if all the evidence variables are added in later CTFs.\n\nWe can add this to the discussion.\n\n> I also noticed some confusing notation, which I mention here for lack of a better place in the review form:\n>* equation (1): (i - j) looks like subtraction. In graph theory, an edge is often written as a pair (i, j) instead.\n>* equation (3): I don't understand the point of the quantifier ($\\forall$) in the product notation and have never seen this before.\n>* line 100: $CTF_{k-1,a}$ first looked like a double-index to me, but I assume the \"a\" just stands for \"approximation\".\n\nWe will fix Equations (1), (3) in the revised version. \n\nYes, \"a\" indeed stands for approximation. $CTF_{k-1,a}$ is the approximate CTF obtained after approximating $CTF_{k-1}$.\n\n\n\nWe hope this addresses all your concerns."}, {"review_id": "ItUwvSzh2o", "reviewer": "Reviewer_SJmy", "summary": "The paper proposes a new approximate inference algorithm for probabilistic graphical models (PGMs). The approach uses a framework called IBIA to perform marginal inference in discrete PGMs. The main idea is to perform Belief Propagation on a sequence of clique trees. In each step the clique tree is approximated such that the number of variables in any factor is less than a bound and BP is performed on this approximate tree. Factors are then added to this tree and the messages are updated using heuristics to get the next clique tree in the sequence.", "questions": "What is the effect of longer vs shorter sequences, how will this affect the experiment results?\nHow is the idea conceptually related to other methods such as mini-buckets, etc.?", "limitations": "Limitations are mentioned.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The approach proposed in the paper seems to work well over a large set of UAI benchmarks in comparison with well-known inference methods. \nThe idea of computing marginals based on a sequence of linked Clique Tree Forests seems novel.\nThe idea of running BP for a single iteration to calibrate and obtaining good experimental results seems interesting since it can reduce computational complexity.", "weaknesses": "The presentation could be improved since it seems a bit hard to understand all the steps. Perhaps a pseudo-code like algorithm might have helped. Also, since there have been a lot of approximate inference algorithms in PGMs, the main motivation for this approach was a bit unclear. For example, if I understand correctly the mini-bucket methods (Dechter 2003) also have a similar idea of approximating factors through mini-buckets. I think in the related work section the significance of the method can be perhaps better motivated in relation to these methods.\n\nOne aspect that was not very clear was when BP converges on the approximate clique tree, if we change the cliques (by adding factors) we cannot just update the beliefs without performing inference again I assumed. In that case, if we use heuristics to update the beliefs (as is mentioned) won’t the errors propagate through the sequence of clique trees? I think there are convergence guarantees on he marginals (e.g. as we add more clique trees in the sequence), that seems like a significant drawback since the scheme will not be any-time (as compared to several other techniques which have this property).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions. Following are our responses to each question.\n\n > What is the effect of longer vs shorter sequences, how will this affect the experiment results? \n \n Error is introduced both in the approximate step during sequence construction and also during heuristic belief update in the backward pass. Since both these steps are performed for each CTF in the sequence, errors for longer sequences are expected to be larger in general. Increasing the maximum clique size bound $mcs_p$ allows for the addition of more factors to a single CTF and thus, leads to shorter sequences and smaller errors in general. \n\nThis is illustrated in Table 1 of the paper (page 8) which shows that IBIA with $mcs_p=23$ gives smaller errors than $mcs_p=20$. We have tabulated the corresponding average sequence length for both these cases in Table 3 in the pdf attached with this rebuttal. As seen from the table, on average, sequence length reduces with an increase in $mcs_p$. \n\n> How is the idea conceptually related to other methods such as mini-buckets, etc.?\n\nPlease refer to the global rebuttal.\n\n> The presentation could be improved since it seems a bit hard to understand all the steps. Perhaps a pseudo-code like algorithm might have helped. \n\nWe have included the pseudo-code in the supplementary material (Page 3).\n\n> One aspect that was not very clear was when BP converges on the approximate clique tree, if we change the cliques (by adding factors) we cannot just update the beliefs without performing inference again I assumed.\n\n That is correct. After adding new factors, we need to perform inference again. This is in the forward pass while constructing the sequence of CTF.\n \n> In that case, if we use heuristics to update the beliefs (as is mentioned) won’t the errors propagate through the sequence of clique trees? \n\nYes. However, our approximation method and the heuristics used for belief update maintain the accuracy. This is demonstrated by our empirical evaluation.\n\n> I think there are convergence guarantees on he marginals (e.g. as we add more clique trees in the sequence), that seems like a significant drawback since the scheme will not be any-time (as compared to several other techniques which have this property).\n\nSimilar to mini-bucket based approaches, IBIA can be run in an anytime manner by changing the maximum clique size bound $mcs_p$. This is illustrated in Table~1 (Page 8). For time limit of 2 min, solutions are obtained with $mcs_p$ set to 20. For time limit of 20 min, solutions with improved accuracies could be obtained by increasing $mcs_p$ to 23.\n\nWe hope this addresses all your concerns."}, {"review_id": "tTPLF3crk6", "reviewer": "Reviewer_QKYy", "summary": "The paper presents a new approximation scheme for computing posterior marginals in graphical models such as Bayesian networks and Markov networks. The proposed approach is based on a previously introduced scheme called IBIA (Incremental Build Infer Approximate) which was initially developed for approximating the partition function. The idea is to construct a sequence of bounded size clique trees (called a clique tree forest) that eventually spans all the input factors and subsequently compute the posterior marginals by carefully selecting the appropriate cliques from the forest. The experimental evaluation is carried out on standard benchmarks for graphical models and the proposed scheme is compared with several state-of-the-art approximation scheme based on message passing. The results demonstrate that the proposed approximation scheme is competitive and some times outperforms existing approaches.\n", "questions": "1. As presented, the performance measure considered assumes that the exact marginals are available. However, many of the problem instances from the experimental section have large induced widths (e.g., 37 for GridBNs) and therefore are difficult to solve exactly, unless a lot of evidence is asserted in the network. Therefore, how many evidence variables are considered for each of the benchmark classes? And also, how do you compute the score when exact inference results are not available?\n\n2. What's the reason for defining the clique size in terms of log instead of just the number of variables in the clique? I found the log based definition confusing.\n\n3. Why do we need to consider two bounds on the clique size? I think the scheme is well defined with only one.\n", "limitations": "The proposed scheme is clearly related to several existing scheme that aim to bound the size of the join-tree. Prominent examples are the mini-bucket scheme for variable elimination, the mini-clustering approach for cluster tree (join tree) elimination, as well as the iterative join-graph propagation scheme (all from Rina Dechter's group). Similarly, the Incremental Thin Junction Tree scheme by Frank Hutter is also looking at bounding the clique size of a join tree by splitting a larger clique into smaller cliques. Therefore, I think a deeper discussion on the connection between these previous schemes and the proposed IBIA based one is clearly called for (it is currently missing from the paper).\n\nThe empirical evaluation only considers a subset of the existing message passing schemes for approximating marginals e.g, LBP, IJGP, and SampleSearch. These methods are more than one decade old (if not more), do not really fall into the more recent category of variational inference methods. I think it would be interesting to compare with more recent methods based on weighted mini-buckets and cost-shifting such as those developed in Alex Ihler's group (including the importance sampling based ones). If you look at the recent UAI-2022 competition results, it looks like these kinds of methods performed best in the MAP (and to some extent in the PR category as well). \n", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is relatively well written and organised. It is also relatively self contained and most of the concepts are discussed in sufficient detail. The empirical evaluation is sound and the results are presented in a relatively clear manner. Some theoretical properties of the proposed method are also discussed.\n", "weaknesses": "Firstly, the contribution presented in this paper appears to be quite incremental over the previous work the IBIA framework. Namely it consists of the message passing scheme over the additional links between adjacent clique trees. The proposed heuristic for choosing links appears to be quite arbitrary. \n\nSecondly, I think the proposed method is highly sensitive to the order in which factors are added to the clique tree forest, as well as the initial collection of factors chosen for initialisation. Therefore, the paper should discuss this aspect in more detail.\n\nThirdly, the paper does not mention anything about the convergence of the scheme nor its time/space complexity.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments and questions. Following are our responses to each question. \n\n>  how many evidence variables in each benchmark class? how do you compute the score when exact results are not available?\n \nWe used evidence sets given in the repository and an average can be added to Table 1. Exact results are either available in UAI repository or could be computed using ACE (performs exact inference using weighted model counting). For other benchmarks, we have only reported the number of instances that are solved by IBIA for various time limits. \n\n> What's the reason for defining the clique size in terms of log instead of number of variables? \n\n We have used $log_2$ because it gives clique sizes as the effective number of binary variables in a clique. The complexity of inference depends on the size of the clique belief table which is directly $O(2^{mcs_p})$. Therefore, it is easy to control the complexity.  Whereas, if we specify the limit as number of variables, and variables have different domain sizes, it could run out of memory. \n\n> Why are there two bounds on clique size? \n \nThe second parameter $mcs_{im}$ controls the extent of approximation in the approximate step (see Figure 1, Page 3). It is possible to make this an internal parameter.\n\n> paper does not mention anything about convergence of scheme nor its time/space complexity.\n\n Our method uses a sequence of clique *trees*, therefore are no issues related to convergence of BP.\n\nComplexity analysis for sequence construction is included in Bathla \\& Vasudevan (2023). For the estimation of marginals, additional time is needed for performing belief-update via the selected links which is  $O(N_{CTF}N_l 2^{mcs_p})$ where, $N_{CTF}$ is sequence length and $N_l$ is the maximum number of selected links between adjacent CTFs. In terms of memory, all CTFs need to be stored to allow for backward belief update, $O(N_{CTF}2^{mcs_p})$. \n\nWe can add this discussion to our paper.\n\n> methods are more than one decade old (if not more), do not really fall into the more recent category of variational inference methods. it would be interesting to compare with more recent methods based on weighted mini-buckets and cost-shifting such as those developed in Alex Ihler's group (including importance sampling based ones). \n \nWe have included a comparison with published results for a recent Gibbs sampling-based technique that uses adaptive Rao-Blackwellisation (ARB) (Kelly, 2019) in the supplementary material (see Table 2, Page 2).  \n\nWhile WMB itself can be used to find MAR (see Table 1 in the pdf attached with the rebuttal), publicly available implementations for extensions such as the cost-shifting scheme JGLP in Merlin, dynamic importance sampling \\& abstraction sampling do not support the MAR task. This is also true for solvers submitted for the MAP and MMAP tasks in UAI2022 like toulbar, daoopt and braobb. It does not seem trivial to extend them to support MAR. If the reviewer can point us to any implementation of other solvers that can find MAR, we would be happy to include it in our comparisons.\n\n\n> proposed heuristic for choosing links appears to be quite arbitrary.\n\n As discussed in Section 3 (Page 7),  the idea is to reduce the number of times BP is performed since it is expensive. The heuristic is not arbitrary, rather it is a greedy approach where we first choose a subset of common variables whose posterior marginals are significantly different in successive CTFs. Next, for belief-update, we select a minimal set of links that cover these variables.\n\n> I think proposed method is highly sensitive to order in which factors are added, as well as initial collection of factors chosen \n \nIBIA uses the following approach:\n\n1. As explained in Bathla \\& Vasudevan (2023), factors are not added one at a time in IBIA. Rather, we group factors that impact overlapping portions of the existing clique tree and add them together. If the addition of a group is not possible, we choose the largest subset that can be added.  \n\n2. The set of disjoint factors used for Bayesian networks is fixed since a topological order is followed. For Markov networks, the number of factors is first reduced by multiplying the factors that are contained in a maximal clique of the MN. Next, factors with large scopes are prioritized while choosing the initial set of disjoint factors.\n\nWe want to emphasize that there is no inherent randomness as in sampling-based methods i.e. every run gives the same results. In that sense, it is like mini-bucket based methods, where results are the same if the variable elimination order and partitioning technique used to generate the initial choice of mini-buckets are the same. \n\nTo answer your question, we introduced a random shuffle before finding the disjoint cliques/subsets of factors added. Table 2 in the pdf attached with the rebuttal has the results for two runs. It can be seen that the difference in average $HD_{avg}$ is less than 0.08 and that in average $HD_{max}$ is less than $0.25$ for all benchmark sets. Maximum variation is seen in Grids and DBN where all initial factors have the same size and no reduction in the number of factors is possible since the size of the maximal cliques is also two.\n\nWe can include this discussion in the revised version. But, unless we know the variability in other methods, it will not be a fair comparison.\n\n>  contribution appears to be quite incremental over previous work on IBIA framework.  \n   \n Please refer to the global rebuttal.\n\n> I think a deeper discussion on the connection between previous schemes and the proposed IBIA based one is clearly called for\n\n Thank you for pointing out Frank Hutter's work on incremental thin JTs. We did not know of this work, mainly because it seems to be unpublished and the authors did not pursue it further.  To understand it,  we hand-worked a few examples and the main problems are summarized in the global rebuttal. \n\nWe hope this addresses all your concerns."}]

Author rebuttal:
We thank all reviewers for their insightful comments and questions. We are encouraged they found our idea to be novel (**vgXS**, **SJmy**), useful (**vgXS**) and interesting (**vgXS**, **SJmy**).  We are glad that the reviewers found our evaluation sound (**QKYy**) and that our method is competitive (**QKYy**) and improves the performance compared to existing methods (**vgXS**, **SJmy**,**QKYy**). We are also pleased that the reviewers found our paper well-written, organized and self-contained with adequate explanations (**QKYy**, **vgXS**). There seem to be two primary concerns, first regarding the contributions of this work and the second regarding comparison with related work. We would like to address these here. Detailed responses to other questions asked by reviewers are included in individual rebuttals.


[**vgXS**, **SJmy**, **QKYy**]  *Regarding the contribution of this paper:*

Although there is a plethora of approximate inference methods in the literature, most of these have been evaluated for the task of finding partition function (PR).  Only a few of these methods have published results for finding posterior marginals (MAR) of all variables which is a key inference task in several applications.  Even in the UAI 2022 competition, while many solvers were submitted for the PR, MPE, MMAP tasks, only a few were submitted for the MAR task.  Publicly available implementations for other submitted solvers like  wmbsearch,  abstraction sampling, toulbar, daoopt and braobb do not support the MAR task. There seems to be no obvious way to extend them for the MAR task. In this context, showing that IBIA can be extended for MAR is a significant contribution.

There is nothing in the base paper (Bathla \& Vasudevan, 2023) to suggest an obvious way to find MAR. It took us a while to figure out that these links can be added and used for belief update. Coming up with reliable algorithms that give good accuracies, understanding differences between topological and non-topological ordering as well as studying the theoretical guarantees for topological ordering is a non-trivial extension. 

[**SJmy**, **QKYy**] *Regarding related work:*

IBIA is similar to mini-bucket schemes in the sense that the accuracy-complexity tradeoff is controlled using a user-defined maximum clique size bound. While mini-bucket based schemes like iterative join graph propagation (IJGP) and join graph linear programming (JGLP) use iterative message passing in loopy cluster graphs,  others like mini-bucket elimination (MBE), weighted MBE (WMB) and mini-clustering are non-iterative approaches that approximate the messages by migrating the sum operator inside the product term. In contrast,  IBIA constructs a sequence of clique *trees*. It performs belief propagation on approximate clique *trees* so that messages are exact and there are no issues of convergence. 

In order to construct the sequence, IBIA requires a fast and accurate method to approximate clique trees by reducing clique sizes.
The aim is to preserve as much as possible, the joint distribution of the subset of variables present in factors that have not yet been added to a clique tree (called interface variables in this work). This is accomplished by marginalizing out variables from large-sized cliques and a minimal set of neighbors without disconnecting clique trees. IBIA gives good accuracy since variables that are removed are chosen based on a mutual information (MI) based metric and a sufficient number of non-interface variables are retained so that a CT is never disconnected. In contrast, the Boyen Koller (BK) (Boyen, 1998) and factored frontier (FF) approximations, although fast, retain only the interface variables which can disconnect the CT resulting in larger errors due to the underlying independence approximation.  The thin junction tree approximations proposed in Frank Hutter et. al (2004) and Kjærulff (1994) split cliques that contain a pair of variables that is not present in any of its sepsets. However, if there are large cliques that have only sepset variables (which is typical in most benchmarks), then the split has to be done iteratively starting from leaf nodes of multiple branches, until the large-sized clique can be split. When such cliques are centrally located in the CT, this process is both time-consuming and would result in approximation of a much larger set of cliques. Similar to BK and FF, this method can also disconnect the CT.

The other thin junction tree methods choose an optimum set of features based on either KL distance or a MI based metric. They cannot be directly used since IBIA requires a good approximation of the joint distribution of only the interface variables. Also, these methods are typically iterative and not very fast.
 
 We can include this in our comparison with related work.


Meta-review: This paper proposes a novel approximation scheme for discrete graphical model marginal inference that proves to be competitive on the standard UAI competition benchmarks. The authors responded very clearly to the questions raised by the reviewers.
Decision: Accept (poster)