IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function
Authors: Shivani Bathla
Vinita Vasudevan
Venue: Accepted by TMLR ()

Abstract: Exact computation of the partition function is known to be intractable, necessitating approximate inference techniques. Existing methods for approximate inference are slow to converge for many benchmarks. The control of accuracy-complexity trade-off is also non-trivial in many of these methods. We propose a novel  incremental build-infer-approximate (IBIA) framework for approximate inference that addresses these issues. In this framework, the probabilistic graphical model is converted into a  sequence of clique tree forests (SCTF) with bounded clique sizes.  We show that the SCTF can be used to efficiently compute the partition function. We propose two new algorithms which are used to construct the SCTF  and prove the correctness of both. The first is an algorithm for incremental construction of CTFs that is guaranteed to give a  valid CTF with bounded clique sizes and the second is an approximation algorithm that takes a calibrated CTF as input and yields a valid and calibrated CTF with reduced clique sizes as the output. We have evaluated our method using several benchmark sets from recent UAI competitions and our results show good accuracies with competitive runtimes.

Published in Transactions on Machine Learning Research (09/2023)
IBIA: An Incremental Build-Infer-Approxinee Framework for Approximate Inference of Partition Function
Shivani Bathla
e ee13s064 @ec..itm..c..
Deportment of Electrical Engineering
II Madres
Vinita Vasudevan
vimita@er. hitm.. ac.in
Deportment Electrical Engineering
IIT Madros
Reviewed on OpenReview:
openreviee. net/
net/forum? forum? id= 8L 78N6FIX
Abstract
Exact computation of the partition function is known to be intractable, nccessitating ap- proximate inference techniques. Existing methods for approximate inference are slow to converge for many benchmarks. The control of accuracy-complexity trade-off also non- trivial in many of these methods. We propose novel incremental (IBIA) framework for approximate inference that addresses these issues. In this framework, the probabilistic graphical model is converted into a sequence of clique tree forests (SCTF) with bounded clique sizes. We show that the SCTF can be used to efficiently compute the partition function. We propose two new algorithus which are used to construet the SCTF and prove the correctness both. The first is an algorithm for incremental construction of CTFs that is guarantoed to give valid CTF with bounded clique sizes and the second is an approximation algorithm that takes calibrated CTF as input and yields valid and cali- brated CTF with reduced clique sizes as the output. We have evaluated our method using several benchmark sets from recent UAI competitions and our results show good accuracies with competitive runtimes.
1 Introduction
Discrete probabilistic graphical models including Bayesian networks (BN) and Markov networks (MN) have been used for probabilistic inference in wide variety of applications. A fundamental task in inference the computation of the partition function (PR), which the normalization constant for the overall probability distribution. Exact inference of PR is known to be #P complete (Roth) 1996), necessitating approximations in general. Methods for approximate inference can be broadly classified as methods based on variational optimization and sampling or search based methods.
Variational techniques cast the inference problem as an optimization problem, which is typically solved using iterative message-passinn algorithms. These include loopy belief propagation (I.PP) (Murphy et al. Wainwright et al. 2002 Wiegerinck & Heskes 2003), region-raal based methods like generalized belief
1999
propagation (GBP) and its variants (Yedidia et al. 2000: Heskes 2006 Mooij & Kappen 2007| Sontag al,
2008 Lin et al. 2020 mean-field approximations (Winn et al. 2005 and methods based expectation
propagation (Minka 2001 2004 Vehtari et al. 2020). A combination of mini-bucket heuristics and belief propagation is used in methods like weighted mini-buckel elimination (WMB) (Liu & Ihler] 2011 Forouzan
& Ihler 2015 Lee et al. 2020) and iterative join graph propagation (LJGP) (Mateescu et al. 2010). While the parameter sottings for complexity accuracy trade-off non-trivial many of the GBP based mothods, it is controlled using a single user-defined parameter (ibound) in mini-bucket based methods. More recently, several extensions of mini-bucket. based methods have been proposed. These include bucket re-normalization

---

Published in Transactions on Machine Learning Research (09/2023)
deep-bucket climination (DBE) Razeghi et al. 2021 and NeuroBE (Agarwal et al, 2022). Both DBE and NeuroBE, use neural networks to improve the quality of approximations. Another approach is to bound clique sizes by simplifying the network. In the thin junction tree based methods (Bach & Jordan 2001 Elidan & Gould 2008 Scanagatta et al., 2018), a set of features (nodes and edges) so that the resulting graph has a bounded tree-width. The remaining features are ignored. The edge deletion belief
[Ahn et al. 2018
propagation (EDBP) and the related relax-recover compensate (RRC) methods (Choi et al. 2005 Choi &
Darwiche 2006 2007 2008) perform inference on progressively more complex graphs in which new features
are added, while satistying some consistency conditions.
Sampling algorithms can be classified as methods based on Markov chain Monte Carlo (MCMC) like Gibbs sampling (Gelfand 2000) and methods based on importance and stratified sampling (Bouckaert et al. 1996;
Hernandez et al.) 1998 Moral & Salmerón 2005). The more recent importance sampling based methods
use proposals based on approximate variational methods like WMB and IJGP. In Liu et al. (2015). WMB is used as the proposal for importance sampling (WMB-IS). The dynamic importance sampling (DIS) method proposed in [ou et al. (2017) also uses WMB and has periodic updale of the sampling proposal. The abstraction sampling methods (Broka 2018 Kask et al. 2020 use an abstraction function to merge similar nodes in AND-OR scarch trees to get abstract states. An estimate of the PR is obtained using sampled subtrees, with WMB used in the sampling proposal. Sample search (Gogate & Dechter, 2007) is a variant of importance sampling that deals with the rejection of samples in the presence of zero weights The method proposed in Gogate & Dechter (2011) uses sample search with cutset sampling and an IJGP based proposal. Another approach is to combine sampling techniques with model counting based methods (Chakraborty et al. 2013 2016 Soos& & Meel 2019 Sharma et al., 2019).
Sampling based methods are anytime algorithms where it is possible to improve accuracy by increasing the number of samples, without the associated increase in memory. However, the performance of these methods depends significantly on the proposal distribution used for importance sampling. The results in Gooaat & Dechter (2011); Lou et al. 2017 2019); Kask et al. (2020) also indicate that after an initial rapid increase, the improvement in accuracy slows down significantly with time. Variational techniques typically require increase in both time and memory for better accuracy. LBP works with minimal cluster sizes and is therefore fast and gives solutions for most benchmarks (Agrawal et al. 2021b. However, it results in poor accuracies especially for many of the harder benchmarks. The accuracy of GBP based hods depends on the choice of the outer regions, which is non-trivial. In practice, we have found that these methods are slow to converge for many benchmarks. Methods based on mini- bucket heuristics like WMB, WMB-IS and DIS have casy control of accuracy complexity trado-off but the accuracy obtained is often limited (Broka 2018 Kask el al. 2020: Agarwal et al.] 2022). Neural network basod extensions like NeuroBE and DBE improve the accuracy of estimates, but require several hours of training. Selection of optimum features in the RRC and related methods is compute-intensive since it is based metrics that require several iterations of belief propagation. While weighted model counting based methods work well for many benchmarks, they struggle for benchmarks with large variable domain cardinality (Agrawal et al. 2021).
Limitations of existing methods:
Contributions of this paper: In this paper, we propose a new framework for approximate inference that addresses some of these issues. Our framework, denoted the incremental muild-infer-approziine paradigm, converts cach connected graph in the PGM into a data structure that we call Sequence of Clique Tree Forests (SCTF). We show that the SCTF can be used for elficient computation of the PR. To construct the SCTF, we propose two new algorithms and prove the correctness of both. The first is an algorithm for incremental construction of CTFs that is guaranteed to give a valid CTF with bounded clique sizcs and the second is an approximation algorithm that takes a calibrated CTF as input and yields valid and calibrated CTF with reduced clique sizes as the output.
(IBIA)
Our method has easy control of accuracy-complexity trade-off using two user-defined parameters for clique size bounds, which are similar to the ibound parameter setting in mini-bucket based methods. Since IBIA is based on clique trees and not loopy graphs, the belief propagation step is non-iterative and there are convergence issues. In IBIA, approximations are based on clique beliefs and not the network structure alone, which results in good accuracies. We evaluated our method with 1717 instances belonging to different benchmark sets included in several UAI competitions. Results show that the accuracy of solutions obtained
2

---

Published in Transactions on Machine Learning Research (09/2023)
by IBIA is better than the other variational techniques. It also gives comparable or better accuracies than the state of art sampling methods in much shorter time.
Organization of this paper: The rest of this paper is organized as follows. Section 2 provides background and notation. We present an overview of the IBIA framework in Section 3, the methodology for constructing the SCTF Section 4 and approximate inference of PR in Section 5. We present the complexity analysis in Section 6, results in Section 7 and comparison with related work in Section 8. Finally, we present our conclusions in Section 9. The proofs for all propositions and theorems are included in Appendix A
2 Background
This section has the notation and the definitions used in this paper.
Definition 1. Probabilistic graphical model (PGM): Let x= (X,, X2, ..,.... } be a sot of random variables with associaled domains D (Dx,, Dxy, D- The probabilistic graphical model (PGM) over X' consists of a set of factors, +. Each factor da (Xa) & is defined over subset of variables Scope( = Xa: where denotes the index to the set of factors. The domain Do of X₂ is the Cartesian product of the domains of variables in Na and the factor &a is a map da : Da + R 2 0. The joint probability distribution captured by the model is P(2") = z II &a where the normalizing constant, Z Σ () II da is the partition function (PR).
Each node of the undirected graph corresponding to the PGM is associated with random variable, X, E X. Variables X; and X, are connected via an edge in this graph if there is at least one factor in the PGM (Ø) whose scope contains both variables.
Definition 2. Chordal graph (H): It is an undirected graph with no eycle of length greater than three.
Definition 3. Clique: A subset of nodes in an undirected graph such that all pairs of nodes are adjacent.
Definition Maximal clique: A clique that is not contained within any other clique in the graph.
Definition 5. Junction tree or Join tree or Clique tree (CT) (Koller & Friedman 2009): The CT is hypertree with nodes that are cliques (Ca) in the chordal graph (H) corresponding to the undirected graph of the PGM. An edge between C2 and Cj is associated with a sepset S. = C2 nC,. A valid CT satisfies the following propertics.
(a) All cliques are maximal cliques i.e., there is no Cj such that Cj C Ci.
(b) It satisfics the rumning intersection property (RIP), which states that for all variables X, if X E C, and X E Cj, then X is present in every node in the unique path between C. and Cj-
(c) Each factor da in the PGM is assigned to a single node C, such that Scope(@a) S C..
Note that throughout the paper, use the terms clique tree, join tree and junction tree interchangeably. Also, as is common in the literature, we use the term C2 as a label for the node in the CT as well as to denote the set of variables in the clique.
The initial belief associated with clique C, is the product of all factors assigned to C. Exact inference in a CT is done using the belief propagation (BP) algorithm (Lauritzen & Spiegelhalter 1988 Koller & Friedman 2009) that is equivalent the leaf nodes to the root node) and a downward pass (from the root node to the leaves). Following this, each clique in the CT has an associated joint belief B(C.)) = EDemain(x)))) II &. and each sepset has an associated joint belief ((S;))) = -Doomin(xx) (zz) II &..
two rounds of message passing along the edges of the CT, an upward pass (from
Definition 6. Calibrated CT [Koller & Friedman 2009): Let B(C,) and ((C,) denote the beliefs associated with adjacent cliques O2 and Cj. The cliques said to be calibrated if
Σ
B(Ci)= =
Σ
B(C,)= =
(1)
Domain
Damain(C,
Here, St,, is the sepset corresponding C, and C₁ and p(St.s) is the associated sepset belief. The CT is said to be calibrated if all pairs of adjacent cliques are calibrated. It has the following properties.
3

---

Published in Transactions on Machine Learning Research (09/2023)
(a) All clique and sepset beliefs in the calibrated CT have the same normalization constant (Z) which is equal to the partition function (PR).
(b) The joint probability distribution, P(X), can be re-parameterized in terms of the sepset and clique beliefs follows:
ILe,, 3(C,)
P(X) [[seEe, ((St.)
(2)
where VT and ε are the set of nodes and edges the CT.
3 Overview of the IBIA paradigm
This section has the definitions of terms used in various algorithms and an overview of the IBIA paradigm. We also introduce running example that will be used in various sections of this paper to illustrate the constituent algorithms.
3.1 Definitions
We use the following definitions in the paper.
Definition Clique Tree Forest. (CTF): Set of disjoint CTs.
Definition Valid CTF: CTF is valid if CTs the CTF are valid i.e., they satisfy all properties in Definition Definition Calibrated CTF: A CTF is calibrated if all CTs the CTF are valid and calibrated. Definition 10. Clique size: The clique size cs; of a clique C₁ defined as follows.
= loga ( II (D&I)
(3)
" C.
where |Du] is the cardinality the number of states in the domain of the variable
It can be seen from the definition that the clique size is the effective number of binary variables contained in the clique.
3.2 Motivation
Since the complexity of inference is exponential in the maximum clique size, the key to making the problem tractable is to bound the clique size. Typically, bounding clique sizes leads to loopy graphs and convergence issues. An alternative is to divide the PGM into multiple sections such that each section results in a CTF with smaller clique sizes, thus making amenable to non-iterative belief propagation. Existing approaches are multiply sectioned Bayesian networks (MSBN) (Xiang et al. 1993 Xiang & Lesser 2003), which an exact inference method and the approximate inference method proposed in Bhanja & Ranganathan (2004). The limitations of these methods are discussed in Section X Following
the two main challenges that need to be addressed: (a) How do divide the PGM such that the maximum clique size of cach CTF is less than user-specified bound? (b) How do we exchange beliefs between the CTFs, so that the overall partition function can be inferred?
These two challenges are addressed in this paper.
3.3 Overview
The inputs to the algorithm are the set of initial factors (+) and two user-defined clique size parameters mcs, and mcsim- Let G denote the undirected graph induced by Φ. Figure illustrates the overall methodology used IBIA construct the sequence of CTFs (SCTF) for & and get an estimate of the partition function for the given of factors. The three main steps the method are as follows. Incremental Build: Starting with valid CTF, the algorithm (Algorithm [ builds the CTs in the CTF
4

---

Published in Transactions on Machine Learning Research (09/2023)
Initialize
Incremental Build
Infer
CTFo
Initialize CT using disjoint cliques
Add factors to
CTF
Calibrate using Belief Propagation
CTF CTFo/CTFs.11. until
max-clique-size reaches
mcsp
CTFRR
CTF₁
k
Approximate
Find PR
Reduce max-clique-size CTFF to mc
No
Yes
Φ. e.empty)
Infer partition function from the last CTF
Figure 1: Estimation of partition function using the IBIA framework
by incrementally adding new factors to it long the maximum clique size bound, mcsp, is not violated. We show that the result of Algorithm is guaranteed to be valid CTF. It is assumed that mcsp is large enough to accommodate the maximum domain size of the factors. Infer: This step takes valid CTF as imput and calibrates all the CT&s in the CTF using the standard BP algorithm [Lauritzen Spiegelhalter 1988) for exact inference. After calibration, all clique beliefs in a CT have the same normalization constant. Approximate: The input this algorithm (Algorithm 2) calibrated CTF, CTF,, with maximum clique size mcsp. The result of the algorithm is an approximate CTF, CTF with reduced maximum clique size of mesim. Our approximation algorithm ensures that CTFFka is valid and calibrated so that the CTs need not be re-calibrated using the message-passing algorithm. It also ensures that connected CT in FR remains connected in CTTFka and normalization constants of the CTs in the CTF are unchanged.
Assume that & connected. The construction of the SCTF starts with an initial CTF (CTF)) that contains cliques corresponding factors & with disjoint scopes. As shown in the figure, the three steps incremen- tal build, infer and approximate are used repeatedly to construct the SCTF {CTFi, CTFx). The construction is complete once all factors in + have been added to some CTF in the SCTF. The SCTF is thus sequence of calibrated CTFs, each of which satisfies a property proved in Proposition 9. Based on this property, we show that the last CTF, CTFn, contains single connected CT and the normalization constant of this CT is the estimate of the PR (Theorem 2).
If & has multiple disjoint graphs which happens for example after evidence based simplification, an SCTF is constructed for each connected graph and the estimate of PR the product of the normalization constants of the last. CTF of each SCTF.
3.4 Example
We will use the example shown in Figure 2a as running example to explain the steps used in various algorithms proposed in this work. The figure has the factors and the input graph induced by the factors. All variables are assumed to be binary and mesp and mc8im are set to and respectively. The final result is an SCTF consisting of two CTFss shown in Figure 2b The normalization constant of clique beliefs in CTF2 is the estimated PR for the example.
4 Construction of the SCTF
In this section, describe the three steps that are used to generate the sequence of CTFss namely, incremental build, infer and approximate. We use the following definitions in this section.
Definition 11. MSG[V]: Given subset of variables (V) valid CTF, MSG[V] is used denote the minimal subgraph of the CTF that is needed to compute the joint beliefs of V.
5

---

Published in Transactions on Machine Learning Research (09/2023)
j
h
CTF
abf
chj
il
jh
g
fih
hmn
fgdh
fdhm
hm/
fm
dh
drn
fmn dhk dmo
ho
hk
CTF2 fmoh
ohkl
dhk
(a) Undirected graph induced by input factors c
(b) Corresponding sequence CTFs (SCTF).
Figure 2: Construction of sequence of CTFs (SCTF) for the input set of factors & (o(c, h, o(sggd) o(i, p(a, b, f), o(d, y, h), o(d, k)), @(h,)), o),,o), Φ(j, m), n), ((d, m),), d(k, The maxi- mum clique size constraints, mes, and mcsam are set to 4 and 3 respectively. All variables are assumed to be binary.
It is obtained by first identifying the subgraph of CTF that connects all the cliques that contain variables in the set V. Then, starting from the leaf nodes of the subgraph (nodes with degree equal to 1), cliques that contain the same set (or subset) of variables in V as their neighbors are removed recursively.
Definition 12. Interface variables (IV): Let the initial set of factors in the PGM be ......., 2nh where 4 denotes the set of factors added to CTFF. A variable in CTF: is an interface variable if it is present in the scope of any factor in the set {#*+1...... 2n).
Each CTF in the sequence has different set of interface variables. IVs needed to form the next CTF in the sequence.
4.1 Incremental Build
In this step, new factors from a set are incrementally added an existing valid CTF, which is either CT Fo or the approximate CTF, CTF as long as the maximum clique size bound (mesp) not violated. If the scope of new factor is subset of an existing clique, the factor is simply assigned to the clique. Otherwise, need to modify the CTF to add clique that contains the scope of the new factor while ensuring that the CTF remains valid. We first explain our method of construction of CTFs with the help of the running example. We then formally state the steps and prove the correctness of our algorithm.
4.1.1 Example
Figure g illustrates the construction of CTF, from an initial CTF, CT CTF, is initialized with cliques corresponding to factors with disjoint scopes, chosen as cliques C₁ C3 and Co in the example. These are highlighted in red in the graph. Let V denote the set of variables present in the existing CTF. The first step in the addition of factor ó is the identification of the subgraph SGmin = M SG[[sco n VJ. The method for addition of & to the CTF depends on whether SG is a set of disjoint cliques or it has connected components. The steps involved in the two cases are as follows.
1. SGmin is a set of disjoint cliques: Assume that the factor Φ(h, i) is to be added to CTF. In this case, SGmin MSG i) consists of two disjoint cliques, C3 and Cg. As shown the figure, the new clique corresponding to @(h,i) can simply be connected cliques C3 and Cy via the sepset variables h and i, producing valid CTF. The addition of factor (bd. g, h) is similar. SGmin for the factors <(d, h k), Φ(a, b. f)
6

---

Published in Transactions on Machine Learning Research (09/2023)
Initialize CTF
71
b
C1 fdg
C3 chj
C. il
Add factors @h,, i), (dd, g, h), (dd,h,
Φ b, f), Φ(j,
abf
hi
il
dg
h
fdg
dgh
chj
dh
dhk
jm
k
Add factors &f,, m, n), ((d, m, 0)
abf
chj
hi
il
hj
C
Igah
fdh
fdlmm
hm
hmrr
fm
dh
dm
fmn
dhk
dmo
Figure 3: Construction of the first CTF in the sequence, CTF1, for an example PGM with mesp set to 4. Starting with a set of disjoint cliques, factors are added until the maximum clique size reaches mcsp. Factors 1(,,1,0) and o) are deferred for addition to the next CTF.
and Φ(j, m) are single cliques. As shown in the figure, they can connected to the existing CTF via the corresponding sepsets to produce valid CTF.
2. SGmin has connected components: When try to add factor m(f,m, n). the variables and are present in cliques C3 and C. which are already connccted in the existing CTF. Dircctly connecting these cliques to the new clique containing variables J, and n will generate loop and hence result in an invalid CTF. Figure
4 shows the steps used for addition of this factor. SGmin = M MSGf, m]] is highlighted in red in Figure 4a The goal is to replace SGmin with a subtrec ST that has a clique containing variables f. m and n, while ensuring that the resulting CTF remains valid. As shown in Figure Ib] when the new clique added the chordal graph corresponding
SGmin, chordless loops f-g-h-j-m-J and f-d-h-j-m--f are introduced. Therefore, retriangulation is needed to get back chordal graph. However, only a subgraph of the modified chordal graph needs to be re-triangulated. Using variable climination to form cliques, clique containing variables h and j is obtained after eliminating variable c. This clique is already present in SGmin- We call such cliques as retained cliques. The subgraph GE shown in Figure 4c is obtained after removing the variable e and deleting the corresponding edges. This is the subgraph that needs re-triangulation. We call it the elimination graph and denote the variables in this graph as the elimination set (Sg). Comparing Figures 4a and 4c we see that Sg contains the sepset variables in SGmin and the variables in the new factor. On triangulating GE, we get CT, ST", that contains cliques Ci', C2',, C3' and Ca' as shown in Figure 4d Each retained clique is then connected to clique in ST such that the sepset contains all common variables. In the example, clique C33 gets connected to clique C3' via sepset variables h and which both C3 and ST" The final ST" is highlighted in teal in Figure 4d ST" replaces SGmin in the existing CTF. The connection is done via cliques Cs, C7 and Cs that were adjacent to SGmin with the same sepsets. Since cliques C1, Cz2, C₁ are no longer present the modified CT, the associated factors are re-assigned to corresponding containing cliques in ST'. Accordingly, the factors associated with C₁ and C2 are ro-assigned C₁ and that associated with C4 re-assigned to Cz. The new factor @(f, m, n) is assigned clique C2' that contains all variables in the scope of this factor.
present in

---

Published in Transactions on Machine Learning Research (09/2023)
Cs abf
Cs hi
Cg il
d
f dg
h
h
Ci fdg
C2 dgh
C3 chi
f
9
0
dh
j
C7 : dhk
Ca jm
m
π2
m
(a) Existing CTF. The minimal subgraph cor- responding to variables in the new factor, SG highlighted in red.
(b) Addition of a clique between f. J.m,n to the chordal graph corresponding to SGmin.
(c) The elimination graph, Gg, which is the subgraph of the mod- ified chordal graph that needs re- triangulation.
Cs abf
Cs : hi
Cg :
f
fh
hm
hj
G fgdh
C22 fhm
Cg : hmj
C3 chj
(ih
fm
Or : dhk
fmm
(d) The modified CTF obtained after replacing SOmin with ST (marked in teal). ST contains cliques obtained after triangulating the elimination graph (C''C2', Ca', Ca') and the retained clique Cs.
Figure 4: Addition of factor off, m, n) to existing CTF.
Factor o(d, m. o) is added in a similar manner and the resulting CTF, CTF1, is shown in Figure B Addition of factors off o) and 6(k,(,0) violates the clique size bounds (mcs, 4) and are deferred for addition to the next CTF in the sequence. Note that ST is not unique and depends on the elimination order used for re- re-triangulation. Similarly, the replacement of SGmin by ST can be done in multiple ways. Therefore, the resulting CTF is not unique, but it always a valid CTF.
Often the new factors that need to be added impact overlapping portions of the existing CTF. While they can be added sequentially, adding them together not only reduces the effort required for re-triangulation, but also often results in smaller clique sizes. Therefore, in our algorithm factors having overlapping SGmin are added together group. The procedure to add group of factors is similar.
4.1.2 Algorithm
We first define various terms used in the algorithm. Let V denote the variables in the existing CTF, & denote the set of factors to be added and Scope( (Φ) ScoesSoope(o).
Definition 13. SGmin: It defined as MSG||Scope ( V] (see Definition 11 for MSG).
It is the minimal portion of the existing CTF that is impacted by the addition of new factors.
Definition 14. Elimination set (Sx): It the set containing the variables in the new factors to be added and the variables in the sepsets of SGmin.
Definition 15. Retained cliques: Cliques in SGmin that contain variables that are not contained in the set Sg-
Definition 16. Elimination graph (Gg): The elimination graph is constructed using the following steps:- (a) For each factor é in the set Φ add fully connected component between variables in Scope(o) (b) For each clique C' E SGmin, add a fully connected component corresponding to CNSE.
Algorithm [ shows the formal steps in our algorithm for incremental addition of new factors to an existing CTF such that clique sizes are bounded. The inputs to the algorithm are a valid CTF, the set of factors be added (Ø) and the clique size bound mesp. In each step of this algorithm, we attempt to add group of factors that have overlapping SGmin (.)) (lines 3-15). To do this, first find the SGmin corresponding
8

---

Published in Transactions on Machine Learning Research (09/2023)
to the entire group &g (Definition 13 and construct the modified subtree ST by adding factors in Pg to SGmin (lines 6-7). Tf ST satisfies the clique size bounds, the CTF is modified and the $ is removed from @ (lines 9-11). Otherwise, we remove a subset of factors, & ge., from & and try adding the remaining factors to the CTF. yg is added to la which a list of factors that are deferred for addition to subsequent CTFs
Algorithm BuildCTF(CTEL 2, mcsp))))
Input: CTF: Imput CTF
4: Set of new factors to be added
mcsp: Maximum clique size bound for the modified CTF
Output: CTF: Modified CTF
④: Set remaining factors
Initialize: =)
Set of factors deferred for addition to subsequent CTFs b Loop until further addition not possible
2: while D.is oiisNo)Emp do
V [Variables CTF)
4: For each factor Φ 6 identify the corresponding minimal subgraph SGmin = MSG[Scopee() n V]
P Find group of factors with overlapping minimal subgraphs
6: SGmin + MSG[[Soope(*))) nv]
Find the minimal subgraph corresponding to set 2g
ST' Construct ST (.gr SGmen)
ST": Modified subtree
8:
& Modify CTF if clique size bound is satisfied.
9:
Max-cique-size(ST" I mesp then CTF <- Modily CTF(ST', SSTSS"SGGmann CTF)
10:
D. Replace SGmin with ST" and get modified CTF b Update the set of remaining factors
11:
① + 43
12:
else
13:
g5 + (Subset factors E 2,}
b Choose a subset of factors for addition to subsequent CTFs Remove Pg. from & and add it to the set of deferred factors a
14: ① - + Paoi od.
15: end if
16: end while
17: 4 = 4a
19: procedure CONSTRUCT ( SGmin)
Construct the climination set SE and climination graph GE, as per Definitions 14 and 21: ST" <- Triangulate Gg and find the corresponding clique tree
& Identify the set of retained cliques, C,
23: Veg + (Variables E SGmin]; V, < Veg S5
VA Variables used to identify retained cliques C,: Set retained cliques
24:
C. Cliques SGmin that contain least one variable V,
25:
Connect retained cliques to ST"
26:
for E C, do
Find clique C' E ST such that CnSe CC' if C" CC then Replace C' by C else Connect C' to C' D Check maximality, connect retained clique C' end for 30: b Assign factors to cliques in ST"
28:
Re-assign factors associated with cliques in SGmin containing cliques ST"
32: Assign factors in 4, to containing cliques in ST"
return ST"
34:
end procedure
36:
procedure MODIFY CTF(ST', SSOSSS""'SGGini SSGmin CTF)
37:
D Replace SGmin with ST" CTF
Adj(SGmin) +- List of tuples SC), containing cliques adjacent to SGmin and corresponding sepset variables 39: Remove SG.nn from CTF
for (Ca, S.) E AdG do
Re-connect cliques adjacent to SGmi cliques in ST
41:
Connect C. to clique C' in ST such that S. C C'
end for return CTF
43:
end procedure

---

Published in Transactions on Machine Learning Research (09/2023)
(lines 12-15). This process is continued until & becomes empty and no further addition is possible. After the CTF is built, we re-assign & to contain the set of all deferred factors (line 17).
Construct ST (lines 19-34): In this function, we first find the elimination set Sg and the elimination graph GE as per Definitions 14 and 16 The elimination graph is then triangulated and the corresponding clique tree ST is obtained (lines 20-21). We then identify the set of retained cliques (C,.) which contain variables that are not present in Sø (V,) (lines 22-24). For each retained clique C, we find clique C" in ST" that contains the set C CnSP, We show that this is always possible in the proof of Proposition 3 If C' is subset of C, we replace C' with C. Otherwise, connect C' to C" (lines 25- 25-29). Following this, factors associated with cliques in SGmin are reassigned and new factors in & are assigned to corresponding containing cliques in ST (lines 30-33).
Modify CTF (tines 36-44): This function modifies the CTF by replacing SGmin by ST'. We start by finding the set of cliques adjacent to SGmin in the input CTF (Adj(SGmin) and remove SGmin from the CTF. Cliques in Adj(SGmin) are reconnected to eliques in ST that contain the corresponding sepset in the existing CTF. We show that this connection is always possible in the proof of Proposition
4.1.3 Soundness of the algorithm
Let the input to Algorithm [ be a valid CTF. Let CTFm denote the modified CTF obtained after adding a group of factors b to an existing CTF using lines 3-15 of Algorithm T Then the following propositions
hold true. The proofs for these propositions are included in Appendix
Proposition 1. CTFm contains only trees (possibly disjoint) i.e., no loops are introduced by the algorithm. Proposition 2. CT contains only maximal cliques.
Proposition 3. All CTs in CTFm satisfy the running intersection property (RIP).
Proposition 4. If the joint distribution captured by the input CTF with corresponding set of variables X is P.X..), then the joint distribution captured by CTFm is P(X.n) I Φ.
Theorem 1. Let the input CTF to Algorithm | be a valid CTF. Then, the CTF constructed by the algorithm also a valid CTF with maximum clique size of mcsp-
Proof. In Algorithm we start with a valid CTF and sequentially add groups of factor using steps shown in lines 3-15. Based on Propositions [ g if the input is a valid CTF, the modified CTF is also valid CTF since it satisfics all the properties needed to ensure that the CTF contains a set of valid CTss (sce Definition 5) The clique size is bounded since the addition of factors is done only if the clique size bounds are met (line 9).
4.2 Infer clique beliefs
The output of the incremental build step is CTF, CTF₁, where the maximum clique size is at most mesp- In the infer step, CTF2 is calibrated using the standard belief propagation algorithın for exact inference (Lauriteen & Spiegelhalter 1988 Koller & Friedman 2009). This is efficient since message passing is performed over clique trees with bounded clique sizes.
4.3 Approximate CTF
The next step is the approsimate step, in which we reduce elique sizes in CTFF to get an approximate CTF, FTF Based on Definition 12 we identify the interface variables (IV) in CTF., All the other variables in the CTF are referred to as non-interface variables (NTV). Since subsequent CTFs have factors that contain IVs, the accuracy of beliefs in these CTFs will depend on how well the joint beliefs of the IVss is preserved in CTF
Figure 5 shows the steps required to get the approximate CTF (CTF),) for the running example. In the example, mcsjm is set to 3 and IV = k. (marked in red in the figure). CTF1, a is initialized to the minimal subgraph corresponding to IV, MSG k, o)] (highlighted in blue in the figure). The two main
10

---

Published in Transactions on Machine Learning Research (09/2023)
C
Cs abf
Co chj
C4 hi
CTF1
jh
fdh
hmm
Exact Marg.
C1o: : fgdh
C2 fdhmm
C7 hmj
C3
C2 : fdhm
C4's hl
c,
fm
dm
dm
dh
Cn mm
C1 dmo
C3 dhk
C₁ dmo
C3 dhk
Local Marg.
CTF1. 1,a
d
C2's ffm
C4' hl
m
C mo
Cs's : dhk
Figure 5: Approxination of CTF, for the running example with mcsió set to 3. The blue cliques in CTF form the minimal subgraph corresponding to interface variables f. k, and / (marked in red). CTF1. is obtained after exact marginalization of non-interface variables j, and local marginalization of variable d.
steps used to reduce the clique sizes are exact and local marginalization, described below. For clarity, we explain the steps assuming that the clique sizes be reduced exactly to the user-defined parameter mcs3m. In practice, it could be larger or smaller depending on the domain-sizes of the variables that are removed.
Exact marginalization: The goal of this step is to reduce the number of NIVs and the mumber of cliques in the CTF while preserving the joint beliefs over the IVs exactly. This can be done by removing some the NIVs from the CTF as follows. If an NIV is present a single clique, it is removed from the CTF and the correspouding clique belief is marginalized over all states in the domain of this variable. In case the resulting clique is non-maximal, it is removed and its neighbors present in multiple cliques, exact marginalization can only be done after collapsing all the cliques containing the variable into single clique. Let ST. be the subtree of CTFFko that has all the cliques containing a non-interface variable u and C. be the new clique obtained after collapsing cliques in ST, and removing v. The clique belief for Ce is obtained after marginalizing the joint probability distribution of ST. over all states in the domain of variable v, as follows.
connected to the containing clique. If an NIV is
B(C,)= = Σ ICESTT 3(C) D. IISPEST, U(SP)
(4)
where SP denotes sepsets in ST, and D, denotes the domain of variable v. While this exactly preserves the joint distribution, this process becomes expensive or infeasible as the size the collapsed clique increases. Therefore, we perform this step only the size of the collapsed clique less than or equal to mes
In the running example (shown in Figure non-interface variable is present in single clique Co. It is removed from Co and the corresponding belief is marginalized. After this, Ca contains only variables h and j, both of which are also present in C7. Since Co is a non-maximal clique, it is removed and its neighbour Ca is connected to C,. In C7, j is a non-interface variable, present in single clique. We can follow a similar process of marginalization and removal of a non-maximal clique, leaving only C2,C2, C3, C4 and Cs in CTFi,a We can further reduce the mumber non-interface variables. Variable i is present in cliques C₁ and C, which when collapsed give a clique of size 3 (S messm) containing variables i and L. Variable is removed and the beliefs are marginalized to give new clique C.'. Exact marginalization over all other NTVs will increase the clique size beyond mc8im and is therefore not attempted.
11

---

Published in Transactions on Machine Learning Research (09/2023)
Local marginalization: In this step, we reduce clique sizes by removing variables from cliques with size greater than mcsim and locally marginalizing clique beliefs as follows. If a variable v is locally marginalized from two adjacent cliques O and Cj with sepset Si the result is two cliques C; = = \ v and Cjj = C2 \ with sepset و = Sig v and beliefs given by
B(C)) = B(C))
(()T))
D. (S(
(5)
D.
Do
We need to ensure that local marginalization satisfies the following constraints:
(a) Since IVs are present in factors that have not yet been added to a CTF, they must be retained in at least one clique in C.FF...
(b) A connected CT in CT should remain connected in CTP.aa- The reason for this will become apparent in Section 5
Figure 5 illustrates the methodology for local marginalization using the rumning example. CTF,,a obtained after exact marginalization contains a single clique C2, with size greater than mcs5m (set to 3). The variables present in this clique are f.d, and m. Since f is an interface variable that present in a single clique, it is not considered for marginalization. Variable h is also not considered, because removal of h from cliques C2 and C4' will disconnect the clique tree, since the sepset between them contains only h. Tf we remove d from C2, it must also be removed from either Ci or C3 to satisfy RIP. We retain d in C3 and marginalize it from beliefs corresponding to C1 and C2. The resulting approximated CTF, CTFi,a, contains cliques with sizes bounded by mcs.m.
4.3.1 Approximation Algorithm
ApprozimateCTT (Algorithm 2 shows the formal steps in our algorithm used to approximate the CTF. The imputs are FR, the set of factors & that have not been added to any CTF in the set [CTF).... CTFR and the clique size bound for the approximate CTF, mcsim. It returns the approximate CTF, CTFF... We first identify the interface variables (IV) and initialize FTFaaa as the minimal subgraph of CTF2 that is needed to compute the joint beliefs of IV (MSG[IV), Definition [1] (lines 1-3). This is followed by exact marginalization of NIVs which are either present in single clique or wherever the size of the collapsed clique is less than mesim (lines 4-10). Next, we perform local marginalization to reduce clique sizes to mesim, if possible. We first choose variable (v) that is present in large sized cliques and retain it in a connected subtree (ST,) that has clique sizes less than or equal to mc8im (lines 12-16). v is locally marginalized from all other cliques while satisfying the constraints specified for local marginalization (lines 18-24). Any non- maximal clique obtained after exact or local marginalization is removed and its neighbors are reconnected to the containing clique (lines 7,19).
4.3.2 Properties of the approximated CTF
If the input CTF, CTFF to the approximation algorithm is valid and calibrated, then resulting approximate CTF, CTFk.a, satisfies the following properties. The proofs for these properties are included in Appendix A Proposition 5. All CT' in the approximate CTF, FT are valid CTs.
Proposition 6. All CTs in the approximate CTF, CT are calibrated.
Proposition 7. The normalization constant of all CTs in the approximate CTF CTFFa the same as in the input CTF, CTF,.
Proposition 8. If the clique beliefs are uniform, then the beliefs obtained after local marginalization are exact.
4.3.3 Heuristics for choice of variables for local marginalization
Since our aim is to preserve the joint beliefs of the interface variables as much as possible, we would like to choose variables that have the least impact on this joint belief for local marginalization. We need
12

---

Published in Transactions on Machine Learning Research (09/2023)
Algorithm 2 ApproximateCTE (CTFk, @, mcSmm
Input: CTFF:: Input CTF
d: Set remaining factors
mcssm: Maximum clique size limit for the approximated CTF
Output: C.F,ka: Approximated CTF
IV + (Variables e CTFFk (Variables }
Identify interface variables in CT Fi.
2: b Initialize FTF,.a
C.F + Minimal subgraph of CTFFk corresponding to variables in IV, MSG
> See Definition
4: NIV + Variables E CTFkk IV
Identify non-interface variables in CT F
Stepl: Exact marginalization
6: Sum out NIVs present in a single clique in F2F
Remove resultant non-maximal cliques, re-connect neighbors
8: while size of collapsed cliques mcsim do Fxact marginalization over NIVs present in multiple cliques
9: Exact marginalization over NTVs; reconnect neighbors
10: end while
11: & Step 2: Local marginalization
L <- List of variables present in cliques with size mcsim Identify variables present in large-sized cliques
13: b Loop until max-clique size is & mcsim or further reduction is not possible
mesim) && NotsNottmpyyl do 15: U + Choose a variable in L; prioritize NIVs Lremove(u)
while (CTFea.-ma--cliuue
17:
ST. t- Find a connected subtree containing s.t. max-clique-size & mcsam & Subtree in which is retained CTF Locally marginalize v from cliques and sepsets in CTFk.a. ST, Marginalize o from other cliques
19:
Remove resultant non-maximal cliques, reconnect neighbors
20:
(Any CT CTFk,a gets disconnected in CTF(.)) || ((v &V)&&(( & CTF),)) then
21:
continue
P Ignore if CT gets disconnected or if an IV is not retained after local marginalization
22:
else
CT CCT. CTF
Modily the approximate CTF
24:
end if
25:
end while
26:
return CT FR.a
metric that measures this influence and is inexpensive to compute. Towards this end, we propose a heuristic technique based on pairwise mutual information (MI) between variables. The MI between two variables æ and y is defined
p(s,w) w)
M1(x;))-
Σ
p(s, w) log
p(s)p(w)
REDa,wEDy
Computation of MI for variables belonging to different cliques is expensive. Instead, we propose two metrics that are easy to compute, namely, Maximum Local Mutual Information (MLMI) and Mazimum Mutual Information (maxMI) which are defined as follows. Let IVc denote the set of interface variables in a clique C. The MLMI of variable clique is defined as
MLMI
max MI(o;)) V
(6)
The marM1 for a variable is defined as the maximum MLMI over all cliques.
max mar AOECTF s.t. VEC
MLMIICC
(7)
As seen in Equation 6 if v is an interface variable, LLMI is the maximum MI between and the other interface variables in the clique. v a non-interface variable, it the maximum MI between v and all the interface variables in the clique. Since maxMI of the maximum MLMI over all cliques (Equation 7 it is measure of the maximum influence that variable v has on interface variables that are present in cliques that contain A low M means that has low MT with interface variables in all the cliques in
13

---

Published in Transactions on Machine Learning Research (09/2023)
which it is present and is therefore assumed to have lower impact the joint distribution of the interface variables.
We prioritize non-interface variables with the least mazMI for local marginalization. If it is not possible to reduce clique sizes by removing non-interface variables, we locally marginalize over interface variables with least max (line 15, Algorithm| 2 During local marginalization, if we find multiple connected subtrees (ST,) with bounded clique sizes (line 17, Algorithm 2 we retain the variable in the subtree that contains the clique with the maximum MLM..
4.3.4 Re- Re-paramettrrzattonn of approximate CTF
CTFF+1 constructed by adding new factors to the approximate CTF, CTFkka- Before adding new factors, re-assign factors associated with cliques in C such the product of these factors is valid joint distribution. This reparamelerization is needed to use the messag-passing algorithm for calibration of CTF++1- Using Proposition [6] we know that clique and sepset beliefs in CTFkk are calibrated. We re- assign clique factors as follows. For each CT in the CTFika & root node is chosen at random. The factor for the root node is the same as the clique belief. All other nodes are assigned factors by iterating through them pre-order, Le.,, from the root node to the leaf nodes. An un-visited neighbor Cý' of a node C,' Fk assigned the conditional belief ((C,'IC,)) = 3(C)) p(S))) as a factor. Using Equation 2 the product of the re-assigned factors valid joint distribution.
5 Approximate inference of the partition function
The partition function can be inferred using Proposition 9 and Theorem stated below. The proofs for both are included in Appendix A
Proposition 9. Let the undirected graph associated with the PGM be connected and let (CTF1, (CTFI,CTF,. CTF CT CTF.- 1n-1,a CTF,) with the corresponding sets of variables {X1, X2, X2...Nn-1a Xn) denote the sequence of CTFss generated by Algorithms and 2. Then, the normalization constant of the distribution encoded by CTF,, (Zx) is
Σ
11
Φ
for k = 1
Domain(X DE
Zx
HC ((C")
(8)
Σ
④ for k > 1
ISPECTA M(SP')
Domoin (Xx)
where, 1....., 4% are the subsets of initial factors added CTF..... CTF, respectively and
E ICCECTR-1.
ICEECTR,, 3(C)
Σ
(9)
Domain(Xe-1.d IISPECTEELIA ( U(SP') Domain(Xx-.) ISSEECEFL, H(SP)
Theorem 2. Let the undirected graph corresponding to the PGM be connected and let the sequence (CTF,,... ,CTF,)) be the SCTF generated by IBIA. Then, the last CTF, CTF, contains a single CT, denoted as CTT IBIA returns the normalization constant of CT₁ (Zn) as the PR.
The PR returned by IBIA (7n) is an approximation to the exact value. This because Algorithm 2 uses local marginalization, which means,
IoCETA ((C")
HOEETF, ,(())
Σ
IISPECTER ((SP)) Domain(X Xx-1 (1-11.) II ((SP)
Note that, although the overall joint distribution in CT is approximate, the normalization constant is preserved as seen from Equation g
Evidenco-based simplification of the PGM could give set of disjoint graphs. We construct an SCTF corresponding each connected graph. The PR is then estimated the product of the normalization constants of the CT in the last CTF of each SCTF.
14

---

Published in Transactions on Machine Learning Research (09/2023)
6 Complexity analysis and Conditions for exact inference
Let NETF be the number of CTFs in the SCTF and N, be the maximum number of incre- mental steps required to build any CTF. We now discuss the worst-case complexity of three steps used to construct the SCTF.
Complexity:
In each step, we add subset of factors that impact overlapping portions of the CTF. The overall complexity of modification depends on the number of steps and the cost of re-triangulation each step. In the worst case, in each step we get group of factors that impacts all the cliques in the CTF and there are no retained cliques. The cost of re-triangulation (CostR) using any of the greedy search methods is polynomial in the number of variables in CTF (Koller & Friedman 2009 Chap. 9). Hence, the worst-case complexity is upper bounded by O(NeTP N₂ Co Generally, the number of computations roquired much lower since there are many retained eliques and different subsets of factors impact disjoint subgraphs the existing CTs.
Incremental Build:
Inference and Approzimation: Since we use exact inference calibrate the clique-tree, the complexity of inference in each CTF is O(2mcs)). Approximation involves summing out variables from belief table. Once again, this is O(2mc*+). The overall complexity is therefore O(NeTF 2mesp).
Conditions under which IBIA gives exact solution: When the SCTF has a single CTF, the PR obtained is exact. If the SCTF has multiple CTFs, it is still possible to get the exact PR if the approximate step uses only exact marginalization. But this is rare and in most cases, local marginalization required, and the PR obtained approximate.
7 Results
All experiments were carried out on Intel 19-12900 Linux system. IBIA was run using Python v3.10 with Numpy, Scipy and NetworkX libraries. The memory limit was set SGB for all experiments, which is the same that used in the UAI 2022 inference competition UAI 2022
We address the following questions in our evaluation.
How many instances can IBIA solve within different runtime limits?
Are clique sizes generated by the proposed incremental method comparable to those obtained with a non-incremental method?
Is the hcuristic used for approximation useful?
What the impact of clique size constraints on the performance of IBIA?
How does the performance of IBIA compare with the state of art techniques?
Performance measure: The error metric used is the absolute error in partition function (PR) measured as log10 PRIBIA - 1og10 PReefl. PRref is either the exact value or available reference values of PR, discussed in more detail later in the section. Since each tool reports PR using a different number of precision digits, we round off errors to three decimal places and report an error of zero when less than 0.001.
Benchmarks: Table 1 lists the benchmark sots used in this work. These benchmarks have been included in several UAI approximate inference challenges (UAT 2010 2014 2022) and the Probabilistic Inference
Challenge (PIC) 2011). We have categorized an instance 'small' if the exact solution was either available
in the repository [Thler] 2006) or could be computed using Ace (Chavira & Darwiche 2015 2008 tool
based on weighted model counting. All other instances are categorized as 'large'.
Notation: In all tables in this section, we denote the induced width of a specific benchmark as w and the maximum domain-size as dm. We use the following denote the average statistics over all instances each benchmark set (a) va: average number of variables (b) fa: average number of factors (c) wa: average induced width and (d) dm,: average of the maximum domain size.
15

---

Published in Transactions on Machine Learning Research (09/2023)
Choice of parameters: Based on the memory limit of 8GB, we chose mesp of 20 for all experiments unless stated otherwise. Since mC88m determines the extent of approximation, we would like it to be as high as possible for better accuracy. But, we also need a sufficient margin to add variables to the next CTF in the sequence. We have empirically chosen mcsim to be less than mcsp.
7.1 Number of instances solved by IBIA
Table 1: Statistics of benchmark sets used and percentage of total instances solved by IBIA with memory limit set to 8GB and runtime limit set to 20 seconds, 20 minutes, 60 minutes and 100 minutes.
Average stats
Instances solved (%)
Size
Benchmarks
#lust
[uar th dm.,)
20
20 min
60 min
100 min
Segmentation
50
(229 17,2)
100%
100%
100%
100%
Promedas
(619,619,25)
100%
100%
100%
100%
Protein
77
(60,180,6,78
100%
100%
100%
100%
BN
(637.637.22 10)
100%
100%
100%
100%
Object
Detection
79
(60,210,6,
100%
100%
100%
100%
Small
Grida
(250,728 22,2)
100%
100%
100%
100%
CSP
14
(68,345,13,)
100%
100%
100%
100%
DBN
66
(780,154583 29,
100%
100%
100%
100%
Pedigree
(853, 853,
100%
100%
100%
100%
mastermind
128
(2159,2159,
98%
100%
100%
100%
blockmap
240
(24580,24580
5055.55 :2)
78%
100%
100%
100%
Segmentation
50
[229,861,19)
100%
100%
100%
100%
Promedas
173
(1209,1209,72.,
80%
100%
100%
100%
Protein
386
(311,1215,21.8)
75%
100%
100%
100%
BN
22
11272,1272,51.17
73%
100%
100%
100%
Large
Object Detection
(60, 1630,993,,9,177
0%
100%
100%
100%
Grida
19
1121,,102
16%
79%
100%
100%
CSP
52
(304,12168,25) 181,443
23%
77%
77%
77%
DBN
11000,66116,,8,22
0%
63%
63%
100%
Typeáb
82
(0992,,0882,24,5)
0%
99%
100%
100%
Average statistics for instances in each benchmark set, average number of variables, fa: average number of factors, average induced width and dma average of the maximum domain-size.
Table ! shows the percentage of large and small instances in each set that are solved by IBIA within 20 seconds, 20 minutes, 60 minutes and 100 minutes, similar to limits used in the UAI 2022 competition.
Except for a few blockmap and some mastermind instances, IBIA was able to solve all the small benchmarks within 20 seconds. Solutions to the remaining instances were obtained within 20 minutes. For the large instances, we allow for an increase in mes, if needod so that at least one new factor can be added while maintaining the overall memory limit. Except for Grids, CSP, DBN and Type4b, in which some instances take longer, all other large instances could be solved within 20 minutes. All Grids and Type4b instances can be solved within 60 minutes and DBN within 100 minutes. For few DBN instances, the number of factors is very large (greater than 100,000) and the runtime is dominated by the incremental build step where repeated re-triangulations are performed to add factors. In large CSP benchmarks, inference using IBIA runs out of memory in 12 out of 52 instances. For these instances, the maximum domain-size is large (varies from 44 to 200). As a result, the number of variables contained in cliques and sepsets in the CTF is very small. Therefore, the approximation step has a limited choice of variables and it becomes infeasible in these cases. This in turn leads to large-sized cliques in the next CTF, thereby exceeding the set memory limit.
7.2 Evaluation of Algorithms in IBIA
In this section, we evaluate the performance of the proposed method for incremental CT construction and the performance of the metric used for guiding the approximate step in IBIA. We also study the trade-off between runtime and accuracy.
Evaluation of Incremental CT construction: We first evaluated our algorithm for incremental con- struction of the CT in terms of the maximum clique size. We used the following method for evaluation. For given mcsp, we used Algorithm [ to incrementally construct the first CTF the sequence (CTF)). For comparison, we used a CTF obtained using full compilation of all the factors added to CTF, This is done as follows. We first find the undirected graph induced by the factors that were added to CTF. This
16

---

Published in Transactions on Machine Learning Research (09/2023)
graph is then compiled using variable elimination (Zhang & Poole, 1996 Koller & Friedman 2009 The elimination order is found using the 'min-fill' metric, and the metric 'min-neighbors is used in the case of a tie (Koller & Friedman 2009). We choose the min-fill metric since in most cases it has found to give lower clique sizes than other houristics (Gogate & Dechter 2004 Li & Ueno 2017j. Re-computing the number of fill-in edges each lime a variable is eliminated increases the execution time. Therefore, we adopted the methodology suggested in Kask et al. (2011) to compute only the change in the number of fill-in edges.
The difference in maximum clique sizes obtained after incremental construction (mcs;bia) of the first CTF in the sequence; CTF,, and that obtained after full compilation of undirected graph induced by the factors added to CTF (mcs)) for mcsp 20, 25. A mCS mess.
Table 2:
Instt
dm
20
mcsp 25
Avg
Min A
Max
Avg A
Min A
Max A
BN
-0.03
-8.1
3
-9.2
Promedas
238
2
-0.6
-12
4
-0.1
-14
Pedigree
24
Grids
27
2
-0.6
-3
2
-0.2
-6
CSP
66
35
-1.5
-13.3
-2
-14.3
3.6
dinga average of the maximmmn domain-sizee
Table 2 compares the maximum clique size obtained using the incremental (mcsssa) and full compilation (mcsy) approaches for mcsp of 20 and 25. It shows the average, maximum and minimum difference (A mCSahia - mesy) in clique sizes for a few benchmark sets. The results for other benchmarks are similar. The difference, A = mCS;bba - mcsj, is negative when the incremental approach yields a smaller clique size and positive otherwise. On an average, our incremental approach gives similar results as full compilation of the correspouding undirected graph. The average negative, indicating that in many benchmarks, the incremental approach actually resulted in lower clique sizes than full compilation. Since the maximum value of A is positive, it indicates that there are instances for which full compilation is better, which is expected.
Evaluation of heuristic used in the approximate step: To get an approximate CTF with lower clique sizes, we choose variables for local marginalization based on the mar metric (refer Equuatin 7 Table 3 compares the errors obtained using the marM1 metric and errors obtained using a random selection of variables. The minimum error obtained marked in bold. We show results for a subset of hard instances (large width and domain-sizes) in BN, Pedigree, Promedas and DBN benchmarks. In most of the testcases, observe that the errors obtained with the mazMI metric are either lower comparable to that obtained using a random selection. This shows that the metric performs well.
Table 3: Comparison of error obtained using IBIA when the choice of variables for local marginalization is made based on the ma metric versus a random selection of variables. The minimum error obtained is marked bold.
Benchmark
dm)+
Error
Benehmark
(w, dm)*
Error
maz.M
Random
Random
BN 69
(48,36)
1.2
1.3
or chain 155
(31.2)
0.01
0.02
BN 70
(81,36)
2.2
3.1
or_chain _07
(33.2)
0.3
0.3
BN 71
(45,36)
0.8
2.2
or chain 128
(30.2)
0.2
0.6
BN
(58.36)
2.4
or chain 102
(31.2)
BN 73
(75,36)
1.9
2.3
or_chain 106
(31.2)
0.3
0.7
BN
(37.36)
1.7
2.9
or_chain 140
(33.2)
0.1
BN 75
(59,36)
2.1
2.5
or chain 212
(31.2)
0.5
0.1
BN 76
(53,36)
1.7
1.7
or chain 198
(32.2)
1.0
0.01
pedigree13
(32,3)
0.01
chain
(31.2)
pedigreed2
(24.5)
0.05
0.04
rus 20 40
0
(30,2)
0.9
266
pedigree19
(27.5)
0.04
0.3
rus2
40
(30.2)
podigren34
(32.5)
0.2
0.3
rus2
20
40
(30.2)
0.7
1.3
pedigree10
(29.7)
0.1
0.3
rua
40
(30.2)
0.02
pedigree111
(31.5)
0.04
0.5
20
40
8
(30,2)
0.8
0.2
pedigree7
(33,4)
0.01
0.2
rux2
20
40
5
(30.2)
0.7
0.3
induced width, dm maximum domsin-size
1 As shown in Equation our definition clique size is the logarithm (base 2) of the product the domain sizes. Therefore, it. possible to gel decimal values when eliques contain variables with domain size greater than 2.
17

---

Published in Transactions on Machine Learning Research (09/2023)
Impact of mcsp accuracy and runtime: Table shows the error in the estimated PR values for various values of mesp. As mentioned earlier, we have empirically chosen mesim to be 5 less than mCSp. We observe that in most cases the accuracy improves as the clique size bounds are increased. This is expected because increasing the bounds potentially increases the number of factors added in each step, which turn could reduce the number of CTFs and the number of approximate steps. Also, the metrics used for guiding the approximate step are computed using beliefs corresponding to the partial set of factors added up to the current CTF. Therefore, the accuracy of the metrics could improve when a larger set of factors is added, resulting in better estimates.
Table 4: Comparison of error in partition function estimated with IBIA and required runtime (in seconds) for various clique size constraints (mcsp, MC85m)
Benchmark
(we, dm)
Error
Runtime (s)
(10.5)
(15,10)
(20,15)
(25,20)
(10.5)
(15,10)
(20.15)
(25,20)
grid2020r15
(26.2)
9.7
0.5
4x
3
28
grid2020r2
(26,2)
0.1
0.1
3x 10
3x.0
4
3
29
grid2020f5
(26,2)
0.2
0.2
0.003
3x10
4
3
34
rus2
(30,2)
0.1
rus2 20 40 2
(30,2)
1.8
1.7
0.4
0.9
16
12
13
261
rus2
(30,2)
rus2 20 40
(30.2)
6.1
1.0
0.2
17
185
pedigroc1
(27.5)
0.6
0.4
0.04
0.01
3
36
pedigree31
(29.5)
0.01
5
45
pedigree31
(32.5)
0.4
0.2
0.2
0.08
3
A
35
pedigree40
(29.7)
pedigroc422
(24.5)
0.1
0.1
0.04
0.004
1
19
pedigroo44
(27,4)
0.03
0.001
3
19
w: induced width, dm:: maximun domoan-size
The runtime of IBIA includes the time required for the construction of the SCTF and inference of the partition function. We observe that while the required runtime is similar when mcsp is set to 10, 15 and 20, it increases sharply when mcsp is set to 25. This is because the build step dominates the runtime for smaller values of mcs, and the infer step dominates for larger values. As discussed in Section G the time complexity of the build step O(NCTF N, Cost As mesp increases, while the number of CTFs in the sequence (NcTF) expected to reduce, the cost of re-triangulation (CostR) could be potentially larger the number of variables in the CTF is larger. Therefore, we observe that the runtime similar for mesp of 10, 15 and 20. The exponential complexity of inference begins to dominate at mcs, 25.
7.3
Accuracy and runtime comparison with existing inference techniques
7.3.1
Methods used for comparison
As mentioned, we classified the benchmarks as small or large depending on whether exact. PR values can be computed or not. To evaluate the performance of IBIA for the small benchmarks, used the results of recent evaluation of various exact and approximate inference solvers by Agrawal et al. (2021) Based on these results, chose the following methods for comparison. For exact inference, used Ace (Chavira & Darwiche 2015), which is based on weighted model counting. To compare with variational methods, we used LBP (Murphy et al.) 1999) and double-loop GBP (HAK) (Heskes et al.] 2003). Amongst the sampling techniques with a variational proposal, we chose Sample search (Gogate & Dechter 2011). We used the publicly available codes used Agrawal et al. (021 or original implementations by the authors of the method for the comparison. Accordingly, for LBP and HAK, we used the implementations in libDAl (Mooij 2010). For SampleSearch, which performs sample search using JJGP-based proposal and cutset sampling (ISSwe). The runtime switches used are included in Table 5 For IBIA, we have used two sets of clique size bounds. We refer to IBIA with mesp set to 20 as 'IBIA20" and IBIA with mes, of 25 as 'IBIA25'. We report results for ISSwe with two parameter settings. The first variant called as 'ISSwed" uses default values of ibound (effective number of binary variables in a cluster) and w-cutset bound determined by the solver depending on the benchmark and given runtime constraints. For fair comparison with IBIA, we set both bounds to 20 the second variant (referred to 'SSSwc20'). While IBIA is implemented in Python, other tools use C++.
used recent implementation (Gogate 2020 by the authors of the method,
18

---

Published in Transactions on Machine Learning Research (09/2023)
Table 5: Methods used for comparison. For each method, we indicate the class of techniques it falls under, The column marked Publication has the citation to the paper containing the estimates of the PR and the first column has the citation to the original paper of the method. Methods for which we obtained data by
running various tools are shown with the corresponding parameter settings in the last two columns.
Method
Type
Publication
Tool
Parameters
IBIA
IBIA
mcdp
20, mcs.. = 15 (IBIA20)
mesp.
25, mcs cm 20 (IBIA25)
LBP
Variational
LibDAI
10 #lter=
Murphy et al.
1999
HAK
Variational
LibDAI tol = 10
"0"", #lter= 10", clusters=LOOrs
Heskes
2003
158wc
Variational (MB)
Gogate & Dechtter
2011
18Swc
Delault (ISSwed)
Gogate & Dochter
2011
+SSampligg
Ibound= (hound=20ww-coe 20.wtcttset bound=20 (ISSwc20)
Variational
Gogate & Dochter
2011
Choi & Darwiche
2006
W
MB
Variational (MB)
Agarwal et al
2022
1hler
NeuroBE
Variational (MB)
Agarwal ct al.
2022
Agarwal of al.
2022
Neural Networks
DBB
Variational (MB)
Hazeghi et al.
Razeghi et al
2021
+ Neural Networks
115
Variational (MB)
Kask et al.
2020
al.
2017
2019
+Search +Sampling
Variational (MB)
Kask al.
2020
Broka
2018
+ +Search+ SSampling
Amongst the small benchmarks, some of the benchmarks are in general considered "hard" in the literature. These benchmarks have been used extensively for comparison and results for many approximate inference methods are available in the literature. For these benchmarks, we compared our method with published results. Table 5 has the methods used for comparison and the reference to the publication from which the PR estimates were obtained.
For large networks for which the exact PR is not available, we compare our results with published results in Kask et al. )2000), which uses reference values of PR generated using 100 1-hr runs of abstraction sampling.
7.3.2 Performance of IBIA for the small benchmarks
Table 2 compares the average error obtained using IBIA20 and IBIA25 with LBP, HAK, TSSwed and TSSwc20 for all small benchmarks. We use two runtime constraints, 20 seconds and 20 minutes. If all instances in a set could not be solved within the given time and memory limits, we mark the corresponding entry as f and show the number of instances solved in brackets. An entry is marked in bold if it gives the lowest error amongst the methods used for comparison.
Out of 848 instances, TBIA20 solves 792 instances in 20 seconds. In contrast, ISSwc20 that uses the same clique size bounds solves only 659 instances. ISSwed uses smaller clique size constraints and able to solve 838 instances. LBP and HAK solve lesser instances than IBIA20. Note that while other solvers are written in C++, IBIA is implemented using Python3 and is therefore a disadvantage in terms of runtime. That said, the only benchmarks that do not run within 20 seconds with IBTA20 are blockmap and mastermind, for which the maximum runtime is 408 and 35 seconds respectively. In 20 minutes, IBIA20 is able to solve all instances. On the other hand, LBP is unable to solve a few DBN instances, ISSwed is unable to solve a few BN instances and ISSwc20 is unable to solve some Grid, BN and mastermind testcases. IBIA25 also fails to give a solution for some relational (blockmap and mastermind) and DBN benchmarks in 20 minutes with SGB memory limit.
For both time constraints, IBIA20 is definitely better than the two variational methods LBP and HAK for all benchmark sets. In 20 seconds, the errors obtained using IBIA20 are comparable to or better than ISSwed and ISSwc20 for all benchmarks except. CSP. IBIA20 has a significantly lower error for Pedigree and Grids, but higher error than ISSwed for CSP. It is the only solver that solves all BN benchmarks in 20 seconds, with a low error. In 20 minutes, the lowest errors are obtained by either ISSwed or IBIA25 or both. In fact, the accuracy of the PR estimates obtained with IBIA20 in 20 seconds is either comparable to or better than that obtained by ISSwc20 and ISSwed in 20 minutes for many of the benchmark
19

---

Published in Transactions on Machine Learning Research (09/2023)
Table 6: Average error in partition function estimated using IBIA20, IBIA25, LBP, HAK, ISSwod and
ISSwc20 with runtime limit set to 20 scconds and 20 minutes. Entries marked as ' where at least instance could not be solved within the set time limit and the number of instances solved is shown in brackets below. The minimum average error obtained for each set is marked in bold.
Average stats Total
Average Error (20 seconds) #lnst.)
Average Error (20 minutes) (# Inst.))
(Ja, dm.)" " #Inst.
LEP HAK 15Swed ISSwc20
IBIA20
IBIA25
LEP HAK ISSwed ISSwe20
IBIA20
IBIA25
Pedigree
(853,21,4)
1.03
2.48
0.41
0.07
2.60
1.03
0.17
0.20
0.07
0.05
24
(22)
(12)
Grids
(728,22:2)
45.5
113.3
6.1
0.2
45.5
113.3
0.4
0.2
8
(4)
(4)
Promedas
(619,21,2)
0.2
0.2
0.7
0.2
0.2
0.2
0.1
0.1
0.2
0.1
65
(62)
(30)
DBN
(15153,29,2)
0.82
0.57
30.2
0.001
0.02
0.37
66
(57)
(63)
(6)
(6)
(58)
(36)
CSP
(345,13,4)
18.2
12.3
0.68
2.87
18.2
12.5
0.28
0.43
2.87
1.06
14
(11)
(11)
BN
(637,28,10)
0.004
0.27
0.004
0.002
97
(84)
(54)
(91)
(77)
(84)
(78)
(93)
(91)
ObjDetoct (210,6,16)
0.38
0.05
0.01
0.38
6.2
0.01
0.001
0.01
79
(35)
(22)
Procein
(180,6,76)
0.004
0.001
0.003
0
0.004
0.006
0
77
(34)
Segment
(8,1,17,2)
0.62
0.05
0.07
0.001
0.62
0.05
0.005
0.001
50
(46)
Blockmap
(24580,5057,2)
0.009
240
(186)
(75)
(236)
(236)
(187)
(177)
(238)
(152)
(198)
Mastermind
(2139,26,2)
0.13
2.33
2.37
0.04
0.12
128
(112)
(103)
(94)
(125)
(96)
(313)
(119)
Total #Instances solved
848
764
525
838
659
792
026
838
741
844
823
848
767
fat average number of factors, wat average induced width and dm average of the maximum domain-size.
sets. The hardest benchmarks for IBIA are CSP and DBN. In ISSwe, cutset sampling plays crucial role in reduction of errors. Without cutset sampling, we found that errors are significantly larger. This is also seen from the results in Broka (2018).
7.3.3 Comparison with published results
Table 7 compares the error obtained using IBIA (mes, 10, 20, 25) with WMB, DBE, NeuroBE, EDBP and ISSwe for five subsets of benchmarks. The memory limit for IBLA was set to 8GB and time limit to 20 minutes. In the table, we use ISSwc(P) to indicate that the reported results are published results. For fair comparison, we set mcsp to 10 in IBIA for benchmarks where ibound of 10 was used in published results. Entries are marked with 5-' for instances where published results are not available for a particular benchmark. The minimum error obtained for each testcase is marked in magenta color in the table.
For small grid instances, the error obtained using IBIA10 is lower than all other methods. For small DBN instances, the error obtained with IBTA10 is smaller than WMB10, but worse than DBE10. For these instances, IBIA20 has the best accuracy in all testcases, except rbm20 for which WMB20 is better. In the Pedigree and BN instances, IBIA20 gives an error comparable to ISSwe(P). The two exceptions are BN and BN 75 where IBIA20 gives a significantly larger error. For these instances, IBIA25 gives error comparable to ISSwe(P). Exact solutions are not known for large Grid instances. Therefore, we measure the absolute difference from the reference values published in Agarwal et al. (2022): ; Razeghi et al. (2021). The difference obtained with IBIA20 is much smaller than WMB20 and DBE20, and higher than NeuroBE for some instances. That said, the reference values are estimates and not the exact solution, thereby making it difficult to draw any conclusions.
Runtimes for published data cannot be compared due to differences in programming languages and systems used for ovaluation. Therefore, we have only reported runtimes for IBIA. The small instances can be solved in less than 10 seconds by IBIA20. For the larger BNs and Grids, IBIA requires couple of 100s get an error comparable to ISSwe(P) and NeuroBF20 respectively.
20

---

Published in Transactions on Machine Learning Research (09/2023)
Table 7: Comparison of error in PR obtained with IBIA with published results for a subset of benchmarks. The minimum error obtained for each testcase shown magenta. Entries are marked with +.' where published results are not available. wt induced width, dm: maximum domain-size
(a) Grid-small (mc,, 10, abound 10)
(w, dm)
1og10 PR
Error
Runtime
WMBIO
DEEIO
NeuroBE10
IBIATO
IBTATO
1rid
(21,2)
333.3
32
1.8
0.05
0.5
10
(12,2)
303.1
1.6
0.7
1.2
0.2
grid2020f2
(26.2)
291.7
11
2
0.1
0
grid2020F10
(26.2)
2.4
grid2020f5
(26,2)
605 1
39
6
0.8
0.003
grid2020f15
(26.2)
1963.0
123
2.7
0.5
(b) DBN-small (mesp 10, ibound
10 and mcs, 20, ibound 20)
dm)
1og10 PR
Error
Rantime (s)
WMB10
DBE10
NeuroBE10
IBLA10
IBIA10
rbm20
(20,2)
68.5
7.8
0.5
1.4
2.1
rbm21
(21,2)
63.1
15.7
0.7
0.9
1.0
rbm22
(22.2)
66.6
27.5
6.0
WMB20
DBE20
NeuroBE20
IBLA
IBLA20
rbm220
(20,2)
58.5
0.0007
0.2
0.4
0.1
rbm21
(21.2)
63.1
0.6
0.2
rbm22
(22,2)
66.6
8.7
0.5
0.8
0.1
ferro20
(20,2)
rbm-ffrro21
(21,2)
152.6
2.0
1.1
1.8
rbm-ferro22
(22,2)
106.1
4.2
(c) Pedigrou-stall (mcs, 20, ibound = 20)
[w, dr))
lugio PR
Error
Runtime (s)
IS))
WMB20
DBE20
NeuroBE20
IBIA20
IBTA20
1edigree19
(27.5)
-59.0
0.14
2.6
3.7
2.6
0.04
pedigree42
(24.5)
-30.8
0.3
0
0.05
pedigroc44
(27.4)
pedigree41
(31,5)
-76.0
4.1
2.9
0.5
0.04
pedigree31
(29,5)
-69.7
0.02
12.4
5.9
0.1
pedigree13
(32.3)
-31.2
0.11
6.5
3.9
1.1
0.01
pedigres34
(32,5)
-64.2
0.1
0.2
7.1
5.9
0.7
0.2
pedigroe7
(33,4)
-64.8
0.05
6.0
6.0
1.8
0.01
Results sample search with based proposal and cutaet sampling as published in
Gogate Dechter 2011
(d) BN-large (mcsp 20, 25)
(w, dm)
log1o PR
Error
Runtime (s)
EDBP
IP)
IBIA20
IBLA25
IBLA20
IBLA25
BN 69
(18,36)
-53.3
3.3
1.3
1.2
1.2
6
110
BN 70
(81,36)
2.2
BN 71
(45,36)
-110.3
3.7
0.6
0.8
0.8
14
197
BN 72
(58.36)
-149.4
0.1
1.3
0.6
28
261
BN 73
(75,36)
-112.6
2.0
1.9
1.3
233
BN 74
(37,36)
-44.4
2.8
1.3
1.7
1.1
3
68
BN 75
(59,36)
-90.2
0.4
2.4
0.8
360
BN 76
(53,36)
-109.3
4.1
1.4
1.7
1.0
21
268
Fxart values computed using bucket climination with external memory puhlished in Gorate & Dechter
2011
Results for sample search with LJGP-based proposal and cutset sampling as published in Gogate & Dechter
2011
(e) Grid-large (mes 20)
(10, dm)
1og P
Runtime
WMB220
DBE20
NeuroBE20
IBIA20
1BTA20
grid2000012
(54.2)
1220
25
2
0.2
30
grid40.005
(54.2)
grid4040r10
(54,2)
5490
215
97
10
21
30
g01010-
(54.2)
338
18
2ro220-30f2
(113,2)
1231
32
15
6
0.6
144
grid4040f5w
(113.2)
2819
137
10
159
grid4040f Ow
(113,2)
5637
298
140
Reference values computed using 100 x 1hr runs abstraction sampling as published in Agarwal et al. 2022
Razeghi et
2021
21

---

Published in Transactions on Machine Learning Research (09/2023)
Table 8: Comparison of the average difference in PR from the reference values (log PR - log 10 PR for large instances in four benchmark scts. PRref are estimates averaged over 100 1hr simulations of abstraction sampling (AS). Table reports results obtained using IBIA (mes,- = 20) and published results for DIS and single Ihr run of AS, Entries are marked as '22 where at least one instance could not be solved. AS(R): AOAS with randomized context-based abstraction function with 256 levels
AB): Best configuration
Avg. Difference
Avg. (Max.) Runtime (s)
# #Inst.
IBIA20
AS(R)
AS(B)
DIS
IBIA20
Promedas
173
1.0
-3.5
-2.8
-66.6
13 (60)
Grids
19
73.2
-77.5
-49.5
-113.73
16 (26)
Typetb
67
8.6
336 (1226)
DBN
48
-16.2
-2.6
-2.3
-39.5
2000 (5810)
Reference values available only for 67 large instances out of 82.
Table 8 has the results for large benchmarks for which the exact PR is not known. Here, the comparison done with reference values of PR The table reports the average difference over all instances in 4 benchmark sets. It has the results obtained using IBIA as well as published results for dynamic importance sampling (DIS) and abstraction sampling (AS) (Kask et al. 2020). In the (able, the column marked AS(R) shows results obtained using the AOAS algorithm with randomized context-based abstraction function with 256 levels, and the column marked AS(B) shows best-case results. The table also shows the average and maximum runtime required for IBIA20.
IBIA20 could solve all instances within SGB memory. In contrast, both AS and DIS are unable to solve all Type4b benchmarks within 1hr and 24 GB memory (Kask et al. 2020). On average, estimates obtained using IBIA20 are higher than the reference value for all benchmarks except DBN, while those obtained by AS and DIS are lower. While Promedas, Grids and Type4b benchmarks are easy for IBIA, the DBN benchmarks are difficult. Both the difference from the reference and required runtimes are larger for these testcases.
8 Related work
Inference methods that use multiple CTFs: As discussed in Section 3.2 two issues need to be addressed in inference techniques that divide the PGM into multiple sections. The first issue is how to divide the PGM such that the maximum clique size of the CTF corresponding to each section is bounded. Previous attempts at dividing the PGM include the exact inference method, multiply sectioned BN (MSBN) (Xiang et al. 1993 Xiang & Lesser, 2003), and the approximate inference method in Bhanja & Ranganathan (2004). In MSBNs, the network structure is divided into sections. The CTF for each section is built using co-operative triangulation and there is no guarantce that the maximum clique size will be within a specified bound.
Bhanja & Ranganathan (2004) use an ilerative method for partitioning that requires repeated conversion of In contrast, IBIA uses an incremental strategy for sectioning that requires re-triangulation of only a portion of the CTF in each step,
different candidate sections to corresponding CTFs, which is compute-intensse
which reduces the time complexity.
The second issue is how do we exchange beliefs between the CTFs so that the overall partition function can be inferred. In Bhanja & Ranganathan (2004). the information is transmitted from one CTF to the next using approximate Chow-Liu trees, containing variables present in both CTFs. However, this method cannot be used for inference of PR since finding a connected Chow-Liu tree consisting of all interface variables requires exact marginalization which is computationally infeasible. In contrast, information is passed via an approximate CTF in IBIA, which is constructed using a combination of exact and local marginalization A sequence of CTss is also obtained for the 2T-BN model of dynamic BNs in the method proposed in Murphy (2002). Beliefs are transferred from one CT to the next using joint beliefs over subsets of variables present in both CT's (Boyen & Koller 1998) The approximation method used in this technique could disconnect CTs and hence, cannot be used for inference of PR. In contrast, the approximation strategy used in IBIA
Reference values of PR were obtained by Prof. Rina Dechter's group by averaging estimates obtained from 100 one hour runs of ahstraction sampling.
22

---

Published in Transactions on Machine Learning Research (09/2023)
preserves the PR at each step (Proposition in the sequence.
This allows for inference of the overall PR from the last CTF
Incremental construction of CTs:: Incremental methods for CT modification have been explored in some
previous works [Draper 1995 Darwiche 1998 Flores et al. 2002). In Draper (1995). incremental addition of links is performed by first forming a cluster graph using a set of rules and then converting the cluster graph into a junction tree. Although several heuristic- graph transformations are suggested, a difficulty is to choose a set of heuristics so that clique size constraints construct the CT. A preferable method would be to make additions to existing CT. Dynamic reconfigu- ration of CTs is explored (Darwiche) 1998), but it is specific to evidence and query based simplification. A more general approach using the Maximal Prime Subgraph Decomposition (MPD) of the PGM is discussed in Flores et al. (2002). In this method, the CT converted into another graphical representation called the MPD join tree which based on the moralized graph. When factors are added, the minimal subgraph of the moralizod graph that needs re-triangulation is identified using the MPD tree. The identified subgraph is re-triangulated, and both the CT and MPD join trees are updated. In contrast, our method,
met. Also, there is specific algorithm to
Requires a lower effort for re-triangulation. This is because the minimal subgraph that is re- triangulated is not the modified moralized graph, but a portion of the modified chordal graph corresponding to the CT (which we have denoted as the elimination graph). Morcover, as opposed to Flores et al. (2002), the subgraph identified using our method need not always contain all variables present in the impacted cliques of the CT.
Eliminates the memory and runtime requirements for maintaining additional reprosentations like the moralized graph and the MPD join tree. Our method identifies the minimal subgraph to be re-triangulated directly from the CT, triangulates it and updates the CT. No other representation of the PGM is needed.
9 Discussion and Conclusions
We propose a technique for approximate inference of partition function that constructs sequence of CTFs using a series of incremental build, infer and approximate steps. We prove the correctness of our incremental build and approximate algorithms.
IBIA gives better accuracies than several variational methods like LBP, region-graphe based techniques like HAK, methods that simplify network like EDBP and WMB which is a mini- bucket based method. For the same clique size bound, accuracy obtained with IBIA is comparable or better than the noural network basod methods DBE and NeuroBE in many cases, without having the disadvantage of requiring several hours of training. In most instances, the accuracy obtained with IBIA is comparable or better than recent sampling based techniques with much smaller runtimes. The runtimes Python. Within memory limit of 8 GB, IBIA was able to give PR estimates for 1705 of 1717 benchmarks. For large percentage of these benchmarks, solution was obtained within 20 minutes.
very competitive even though it is written in
The main difficulty with predicting the performance of approximate inference algorithms is that besides being dependent on the graph structure of the PGM, it is also strongly dependent on the beliefs encoded by the PGM, which is what the algorithms are trying to estimate. In methods that use "loopy" cluster graphs, we generally expect better accuracies if the cluster(clique) sizes are larger since it accounts for larger number of correlations between variables. However, inference methods that rely solely the network structure to form clusters not always useful. For example, both LBP and HAK are variants of iterative BP. While LBP uses minimum-sized clusters, HAK allows for the use of larger clusters to account for different cycle lengths. However, as seen in Table G the error obtained with HAK is larger than LBP in some cases. In contrast, approximations in IBLA are made based on both structure- based and belief based information, resulting lower errors than that obtained using the graph structure alone. However, as shown in Table 3 while belief- metrics are useful in most cases, there are some cases where the error obtained using random selection is lower.
23

---

Published in Transactions on Machine Learning Research (09/2023)
In IBIA, increasing the clique size bounds gives better accuracies in general. However, this also results in increased runtimes and memory utilization. IBTA constructs clique trees by incrementally adding factors to an existing CT. When the number of factors is large, repeated re-triangulations could increase the runtime. This is particularly seen a few DBN instances where the number of factors is greater than 100,000 and the required runtime is around 100 minutes. Also, for benchmarks that have very large variable domain-sizes, the number of variables cliques and sepsets a CTF small and approximation becomes difficult. This is seen in CSP benchmarks, where we were unable solve 12 instances. Therefore, good strategy needed for the incremental build step that optimizes the runtime and results in reduced clique sizes. Approximation based on the mazMI gives smaller error in most testcases. However, in a few Promedas and DBN testcases smaller errors were obtained with random selection, thus indicating & possibility for further exploration of heuristics.
A possible extension would be combine IBIA and sampling based techniques to get accuracies that improve with time. The proposed IBIA framework can also be extended to handle other inference queries such as computation of the marginals, max-marginals and the most probable explanation. It also has implications in learning, since the tree-width limitations can be relaxed.
Acknowledgements
We thank Prof. Rina Dechter and Bobak Pezeshki for providing reference values of the partition function for the large benchmarks for which exact solutions are not known.
References
Sakshi Agarwal, Kalev Kask, Alex Ihler, and Rina Dechter. NeuroBE: Escalating neural network approxi- mations of bucket elimination. In Uncerlainly in Artificial Intelligence, pp. 11-21, 2022.
Durgesh Agrawal, Yash Pote, and Kuldeep S. Meel. Partition function estimation: A quantitative study, International Joint Conference Artificial Intelligence, pp. 4276-4285, 2021. Survey Track.
Sungsoo Ahn, Michael Chertkov, Adrian Weller, and Jinwoo Shin. Bucket renormalization for approximate inference. In International Conference on Machine Learning, pp. 109-118, 2018.
Francis Bach and Michael Jordan. Thin junction trees. Advances in neural information processing systems, 14, 2001.
Sanjukta Bhanja and Nagarajan Ranganathan. Cascaded Bayesian inferencing for switching activity esti- mation with correlated inputs. IEEE transactions on very large scale integration (VLSI) systems, 12: 1360-1370, 2004.
Remco R Bouckaert, Enrique Castillo, and JoséManuel Gutiérrez. A modified simulation scheme for inference in Bayesian networks. International Journal of Approzimate Reasoning, 14(1):55-8) -0,5,500,550 1996.
Xavier Boyen and Daphne Koller. Tractable inference for complex stochastic processes. In Uncerlainly in Artificial Intelligence, pp. 33 42, 1998.
Filjor Broka. Abstraction sampling in graphical models. In AAAT Conference on Artificial Intelligence, pp- 8010 8011, 2018
Supratik Chakraborty, Kuldeep S Meel, and Moshe Y Vardi. A scalable approximate model counter. Tn Principles and Practice of Constraint Programming, pp. 200 216, 2013.
Supratik Chakraborty, Kuldeep S. Meel, and Moshe Y. Vardi. Algorithmic improvements in approximate counting for probabilistic inference: From linear to logarithmic sat calls. In International Joint Conference on Artificial Intelligence, pp. 3569-3511 3576, 2016.
Mark Chavira and Adnan Darwiche. On probabilistic inference by weighted model counting. Artificial Intelligence, (72 -999, 2008.
24

---

Published in Transactions on Machine Learning Research (09/2023)
Mark Chavira and Adnan Darwiche. Ace version 3.0. http://reassoningco www..s...cc...ooooo.oooooo...ooo iocla.edu/ace) 2013. Ac-
cessed: 2021-10-15.
A. Choi and A. Darwiche. Approximating the partition function by deleting and then correcting for model edges. In Uncertainty in Artificial Intelligence, pp. 79 87, 2007.
A. Choi and A. Darwiche. Many pairs mutual information for adding structure to belief propagation ap- proximations. In Artificial Intelligence, pp. 1031-1036, 2008.
A. Choi, H. Chan, and A. Darwiche. On Bayesian network approximation by edge deletion. In Uncertainty in Artificial Intelligence, pp. 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, pp. 1107 1114, 2006.
Adnan Darwiche. Dynamic jointrees. In Uncertainty in Artificial Intelligence, pp. 97 104, 1998.
Denise I. Draper. Clustering without (thinking about) triangulation. In Uncertainty in Artificial Intelligence, pp. 125-133, 1995.
Gal Elidan and Stephen Gould. Learning bounded treewidth Bayesian networks. Journal of Machine Learning Research, 9(12), 2008.
M. Julia Flores, José A Gámez, and Kristian G Olesen. Incremental compilation of Bayesian networks. Tn Uncertainty in Artificial Intelligence, pp. 233 240, 2002.
Sholeh Forouzan and Alexander Ihler. Incremental region selection for mini-bucket elimination bounds. In Uncertainty in Artificial Intelligence, pp. 1-10, 2015.
Alan E Gelfand. Gibbs sampling. Journal of the American statistical Association, 95 2000.
Vibhav Gogate. JJGP-sampling and samplesearch (PR and MAR tasks).
ijgp- saapaleelesecch 2020. Accessed: 2023-01-15.
Vibhav Gogate and Rina Dechter. A complete anytime algorithm for treewidth. In Uncertainty in Artificial Intelligence, pp. 201-208, 2004.
Vibhav Gogate and Rina Dechter. Samplesearch: scheme that searches for consistent samples. In Artificial Intelligence and Statistics, pp. 147 154, 2007.
Vibhav Gogate and Rina Dechter. Samplesearch: Importance sampling in presence of determinism. Artificial Intelligence, 175(2):694-72)) 2011.
Lais D Hernandez, Serafin Moral, and Antonio Salmeron. A Monte Carlo algorithm for probabilistic propa- gation in belief networks based on importance sampling and stratified simulation techniques. International Journal of Approzimate Reasoning, 18(1-2):53 -0195,9-9911199 1998.
Tom Heskes. Convexity arguments for efficient minimization of the Bethe and Kikuchi free energies. Journal of Artificial Intelligence Research, 26:153 190, 2006.
Tom Heskes, Kees Albers, and Bert Kappen. Approximate inference and constrained optimization. In Uncertainty in Artificial Intelligence, pp.
2003.
Alexander Ihler. UAI model files and solutions. http://ll..cc..dd.ood//hbbeeee cessed: 2021-10-15.
2006. Ac-
Kalev Kask, Andrew Gelfand, Lars Outen, and Rina Dechter. Pushing the power of stochastic greedy ordering schemes for inference in graphical models. In AAAI Conference Artificial Intelligence, 2011.
Kalev Kask, Bobak Pezeshki, Filjor Broka, Alexander Ihler, and Rina Dechter. Scaling up and/or /o abstraction sampling. In International Joint. Conference Artificial Intelligence, pp. 4266-40 4274, 2020.
25

---

Published in Transactions on Machine Learning Research (09/2023)
Daphne Koller and Nir Friedman. Probabilistic graphical models: Principles and techniques. MIT press, 2009.
Steffen I 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 (Methodologieal), 50(2):157 194, 1988.
Junkyu Lee, Radu Marinescu, Alexander Ihler, and Rina Dechter. A weighted mini-bucket bound for solving influence diagram. In Uncertainly in Artificial Intelligence, volune 115, pp. 1159-115 1168, 2020.
Chao Li and Maomi Ueno. An extended depth-first search algorithm for optimal triangulation of Bayesian networks. International Journal of Approzimate Reasoning, 80:294-312 312, 2017.
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 09:231-295, 2020.
Qiang Liu and Alexander Thler. Bounding the partition function using holder's inequality. In International Conference Machine Learning, pp. 849 856, 2011.
Qiang Liu, John W Fisher III, and Alexander Ihler. Probabilistic variational bounds for graphical models. Advances in Neural Information Processing Systems, 28, 2015.
Qi Lou, Rina Dechter, and Alexander T Ihler. Dynamic importance sampling for anytime bounds of the partition function. Advances in Neural Information Processing Systems, 30, 2017.
Qi Lou, Rina Dechter, and Alexander Thler. Interleave variational optimization with Monte Carlo sampling: A tale of two approximate inference paradigms. In AAAI Conference on Artificial Intelligence, volume 33, pp. 7900-7907, 2019.
Robert Mateescu, Kalev Kask, Vibhav Gogate, and Rina Dechter. Join-graph propagation algorithms. Journal of Artificial Intelligence Research, 37:279-324 -28,, 2010.
Thomas P. Minka. Expectation propagation for approximate Bayesian inference. In Uncertainly in Artificial Intelligence, pp.
2001. ISBN 1558608001.
Tom Minka. Power ep. Technical Report MSR-TR-22044149, Microsoft Research Ltd., Jamuary 2004. URL
attps://wwez httt///wwww.cooooooooooooooooot. http:///ww////eeee////////atttta
Joris M. Mooij. libDAl: 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 and Hilbert Kappen. Loop corrections for approximate inference on factor graphs. Journal of Machine Learning Research, :(10)3113, 2007.
Serafin Moral and Antonio Salmerón. Dynamic importance sampling in Bayesian networks based on proba- bility trees. International Journal of Approrimate Reasoning, 38(3):245-22 261, 2005.
Kevin Murphy, Yair Weiss, and Michael T. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artificial Intelligence, pp. 467 475, 1999.
Kevin Patrick Murphy. Dynamic Bayesian networks: Representation, inference and learning, dissortation.
PhD thesis, UC Berkley, Dept. Comp. Sci, 1, 2002.
PIC. The probabilistic inference challenge (pic2011).
httpsr//ww..c.njjj...aa.ppp/p//p
2011.
Yasaman Razeghi, Kalev Kask, Yadong Lu, Pierre Baldi, Sakshi Agarwal, and Rina Dechter. Deep bucket elimination. In International Joint Conference on Artificial Intelligence, pp. 4235 024-,422, 2021.
Dan Roth. On the hardness of approximate reasoning. Artificial Intelligence, (2(1-2):273 302, 1996.
26

---

Published in Transactions on Machine Learning Research (09/2023)
Mauro Scanagatta, Giorgio Corani, Cassio Polpo De Campos, and Marco Zaffalon. Approximate structure learning for large Bayesian networks. Machine Learning, 107(8):1209-15)) 1227, 2018.
Shubham Sharma, Subhajit Roy, Mate Soos, and Kuldeep S Meel. GANAK: A scalable probabilistic exact model counter. In International Joint Conference on Artificial Intelligence, volume 19, pp- 1169-1176, 2019.
David Sontag, Talya Meltzer, Amir Globerson, Tommi Jaakkola, and Yair Weiss. Tightening LP relaxations for MAP using message passing. In Uncertainty in Artificial Intelligence, pp. 503-510, 2008.
Mate Soos and Kuldeep S Meel. BIRD: Engineering an efficient enf-xor sat solver and its applications to approximate model counting. In AAAI Conference on Artificial Intelligence, pp. 1592-1599, 2019.
UAL The 2010 UAI Approximate inference challenge. 2010.
httpe://ww.....uu......p/pp/s/sp
UAL UAI 2014 Probabilistic inference competition.
shtml
2014.
CAL UAI 2022
2022.
Aki Vehtari, Andrew Gelman, Tuomas Sivula, Pasi Jylänki, Dustin Tran, Swupnil Sahai, Paul Blomstedt, John P Cunningham, David Schiminovich, and Christian P Robert. Expectation propagation as a way of life: A framework for Bayesian inference on partitioned data. Journal of Machine Learning Research, 21 (1):577 629, 2020.
Martin J Wainwright, Tommi Jaakkola, and Alan Willsky. Tree-based reparameterization for approximate inference on loopy graphs. In T. Dietterich, S. Becker, and Z. Ghahramani (eds.), Advances in Neural Information. Processing Systems, volume 14, pp. 1001-1008, 2002.
Wim Wiegerinck and Tom Heskes. Fractional belief propagation. In Advances in Neural Information Pro- cessing Systems, volume 15, 2003.
John Winn, Christopher M Bishop, and Tommi Jaakkola. Variational message passing. Journal of Machine Learning Research, 6(4), 2005.
Yang Xiang and Victor Lesser. On the role of multiply sectioned Bayesian networks to cooperative multiagent systems. IEEE Transactions on Systems, Man, and Cabernettis-Part A: Systems and Humans, 33( 4):4 501, 2003.
Yang Xiang, David Poole, and Michael P Beddoes. Multiply sectioned Bayesian networks and junction forests for large knowledge-bart based systems. Computational Intelligence, 9(2):171 220, 1993.
Jonathan S Yedidia, William T Freeman, Yair Weiss, et al. Generalized belief propagation. In Advonces in Newral Information Processing Systems, volume 13, pp. 689-695, 2000.
Nevin Lianwen Zhang and David Poole. Exploiting causal independence in Bayesian network inference. Journal of Artificial Intelligence Research, 5:301-328, 1996.
A Proofs
Propositions based Algorithm 1 Propositions 1 to 4 are based on our algorithm for the incremental addition of a group of factors (b)) to an existing valid CTF using lincs 3-15 of Algorithm [ The modified CTF obtained after addition of factors is denoted as CTFm. SGmin, SE, G and retained cliques are defined in Definitions
16.
All line numbers in these propositions refer to Algorithm
Proposition CTF, contains only trees (possibly disjoint) i.e., no loops are introduced by the algorithm.
27

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. Algorithm | first identifies SGmin for set of factors that have overlapping minimal subgraphs in the input CTF (lines 4-6). SGmin is either single tree a set of disjoint trees, each of which contains variables present in Ly. The algorithm then constructs the elimination graph Gg (refer Definition [6] When SGmin has a single tree, Ge is a connected graph because SE contains all the sepset variables in SGmin and Gg contains a fully connected component between CnSg for each clique C' in SGmin. When SGmin has disjoint trees, GE gets connected when we add fully connected components corresponding to all factors in gg. Therefore, a single CT, ST", is obtained on triangulating GE (line 21). Each retained clique either replaces is re-connected to a single clique in ST (lines 25-29). Hence, the resulting structure ST" continues to be a tree. Next, SGmin is removed from the CTF (line 39). This results in disjoint trees, each containing a single clique in the adjacency list of SGmin- Each adjacent clique is re-connected to a single clique in the modified subtree ST (lines 40-42). Therefore, no loops are introduced and the modified CTF, Fm. continues to have one or more disjoint trees.
Proposition 2 CTFm contains only maximal cliques.
Proof. ST" obtained after triangulating the elimination graph, GF, has only maximal cliques by construction (line 21). The final ST" is obtained after connecting retained cliques (lines 25-29), where there is an additional check for maximality. CTF,, is obtained after replacing SGmin with ST Cliques in the input CTF that are not in SGmin contain at least one variable that is not present in ST thus remain maximal.
Proposition 3 All CTs in CTFm satisfy the running intersection property (RIP).
Proof. In Algorithm [ Veg is the set of variables in SGmin and V, is the set Vag \ (S (line 23). Consider the chordal graph corresponding to SGmin. This chordal graph has a perfect elimination order such that no fill-in edges are introduced on climination. Even after the addition of edges between variables in the new factors, variables in V, can be eliminated in this order without adding any fill-in edges. Therefore, cliques containing these variables are retained as is in the modified CTF, CTFm- Flimination of variables Sy could potentially introduce fill-in edges as they are a part of chordless loops introduced by the addition of the new cliques. Therefore, only the subgraph of the modified chordal graph corresponding to the set of variables in Se needs re-triangulation. Construction of elimination graph Ge using Definition 16 is equivalent to finding this subgraph. ST" obtained after re- te-tranngulatio of Ge is valid by construction and thus satisfies RIP. The modified subtree ST" obtained after adding the retained cliques (lines 25-29) satisfies RIP because each retained clique C is connected such that the sepsets contain all variables in the intersection C n CnSg. This addition is always possible because ST" is obtained from Ge which contains a fully connected component between C' C'SS Sg for all cliques C' in SGmin (see Definition 16
CTF is obtained by removing SGmin and reconnecting cliques adjacent to SGmin in the input CTF (Adj(SGmin)) to the cliques in STT (lines 36-44). Consider clique Co in Adj(SGmmin) that was connected via the set of sepset variables S.- Since the input CTF satisfies RIP, C. V.y = Sa- In addition to Vags the only variables in ST' are variables in the new factors b which are not present in the input CTF. Therefore, Co n STT = Ca n Veg = S.. Thus, RIP is satisfied since each adjacent clique C. is re-connected to a clique C' in ST' that contains the corresponding sepset S. (line 41). This connection is always possible because of the following reasons. If C, was connected to a retained clique, it can simply be re-connected via the same sepsets. Otherwise, if C. was connected to clique C' in SGmin that is not retained clique, by construction every variable in C' must be present in Sg i.e. CUSE C. Since Ge contains fully connected component corresponding to C Sg for all cliques in SGmin (see Definition 16), C' is contained in at least one clique C' in ST obtained after re-triangulation. Therefore, C" also contains the sepset S, and can be connected to C..
Proposition 4 If the joint distribution captured by the input CTF with corresponding set of variables Xin is P(X..), then the joint distribution captured by CTF, is P(X..) II S.
Proof. CTFm obtained after replacing a subgraph of the existing CTF (SGmin) with a modified subtree ST'. We reassign the factors corresponding to each clique in SGmin to cliques in ST" containing their scope
28

---

Published in Transactions on Machine Learning Research (09/2023)
(line 31). This is always possible because a) retained cliques in mmn also present in ST" and (b) cliques in SGmin that are not retained cliques are contained in cliques in ST (as shown in the proof of Proposition 3). No change is made to factors assigned to the remaining cliques. The new factors in 2g are assigned to cliques in the modified CTF, CTFm, containing the scope of these factors (line 32). This is possible because the elimination graph Gg contains a fully connected components corresponding to all new factors (see Definition 16 and hence, these are contained in cliques obtained after re-triangulation. Therefore, if the product of factors in the input CTF is P(Xin), then the product of factors in CTFm is P(X.)) Ho d.
]
Propositions based Algorithm 2 Propositions 5 to 8 are based on the proposed approximation algo- rithm (Algorithm 2) and Equations 4 and We use CTFR to represent the input CTF to the algorithm and CTFR.a to represent the output of the algorithm. CTF, is a valid and calibrated CTF. IV denotes the set of interface variables (refer Definition 12 in CTFR. All line numbers in these propositions refer to Algorithm
Proposition All CTss in the approximate CTF, CTFk,a are valid CTs.
Proof. CT k.a is initialized as MSG MSG is the minimal subgraph corresponding to the IVs (see Definition 11. Since all CTs in CTF& are valid, any connected subtree in CTF: is also valid. We now argue that all CTs in F..F.. obtained after marginalization steps satisfy all properties of valid CT.
It contains only maximal cliques. Any non-maximal clique generated in the exact and local marginalization step is removed (lines 7 and 19).
It contains disjoint trees.
In the exact marginalization step, no loops are introduced since the neighbors of the collapsed and the non-maxinal cliques are reconnected to CTFF.a so that connectivily of the CTs is preserved (lines 7 and 9). The local marginalization step only involves marginalization variables from individual cliques and sepsets (line 18) and therefore does not alter the tree structure of the C''s in the CTF.
It satisfies RIP.
In the exact marginalization step, neighbors of all cliques that are collapsed are connected to the collapsed clique via corrosponding sepsets and thus, RIP is satisfied. In the local marginalization step, variables are retained in single connected subtree of CTF2 (line 17-18). Also, in both steps, neighbors of non-maximal cliques which are removed are connected to the containing cliques with the same sepsets. Therefore, RIP is satisfied.
Proposition 6 All CTs in the approximate CTF, CT are calibrated.
Proof. In calibrated CT, all adjacent cliques agree the marginals over the sepset variables (see Equa- tion D.. CTFkaa is obtained from CTF,, which is calibrated. After exact marginalization, all the clique and sepset beliefs are preserved. Therefore, the resultant CTF is also calibrated. For the local marginalization step, let u be the variable that is locally marginalized from adjacent cliques C, and C2 with sepset S in CTF, After local marginalization variable v, we get the corresponding cliques C₁ and Cý with sepsot S%, in CTFk.a with the following beliefs (see Equation
B(C) = Σ (CC)) B(C)== -E(C) (()))) = Em(Sis)
D.
D.
D.
Here, D,, is the domain of variable Since the result is invariant with respect to the order in which variables are summed out, have
Σ
B(C))
Σ
3(C)))
Σ
Σ
3(C,) = En(Sr,) ((St))
Domain(C."\S)
D.
Domain(C, ((S,)
29

---

Published in Transactions on Machine Learning Research (09/2023)
Similarly, [Demav((, ((C)) ((S),)) Therefore, beliefs of the modified cliques C and Cj' agree the marginals of the sepset variables 5 Since this is true for every pair of adjacent cliques, all CTs in CTFRaa are calibrated.
Proposition 7 The normalization constant of all CTs in the approximate CTF CTFkk is the same as in the imput CTF, CTF2.
Proof. The approximation algorithm (Algorithm 2 has two steps, namely, exact marginalization and local marginalization. Exact marginalization involves collapsing cliques to find joint belief (Equation 4 and then marginalizing a variable by summing over its states. Neither these steps changes the normalization constant. Local marginalization involves marginalizing a variable from individual cliques and sepsets by summing over its states. Once again, it does not alter the normalization constant.
Proposition exact.
8 If the clique beliefs uniform, then the beliefs obtained after local marginalization are
Proof. Let C1 and C2 be two adjacent cliques in CTF, with sepset S1,2. After local marginalization of variable u, get the corresponding cliques Cf and C22 in CTFFk,, with sepset S1,2. Let b1, b2 and by represent the uniform beliefs in C1, C2 and S12. If the domain of variable v (Do) has k states, the beliefs of states in C₁2 C22 and Si,2 are kb,, klz and kbg.
The exact joint belief C₁ and C2 is
U(C)UC2) ((C)) ((S.2)
Each state BCC U C2) has a constant belief 41b2 If exact marginalization is carried out, the stales of ΣD, B(C1 U C2) have constant belief k bib2 ha
With local marginalization, the joint beliefs are
BCCUC (C))
((
The corresponding constant beliefs are (kb)) 1(bb2)
k b1bb
kbb
Propositions based on inference of PR: Proposition and Theorem 2 relate to inference of partition function (PR).
CTFi,a: Proposition 9 Let the undirected graph associated with the PGM be connected and let {CTF,, CCTFF CTF2,..., CT - 1,a CTFF with the corresponding of variables {X1, X2 ......n1.0 Xx) denote the sequence of CTFs generated by Algorithms and 2. Then, the normalization constant of the distribution encoded by CT F5 (7k) is
Σ
II
for k = 1
Domain(X (x)
dE
Ho
B(C")
Σ
II ó for k > 1
ISPEECTRLLLA H(SP')
[omain(Xx)
where, 21. .,...., dh are the subsets of initial factors added to CTF,, CTF: respectively and
ICCECT--1.. 3(C")
HCEECFF 3(C)
Σ
Σ
IISPECTFL 1. U(SP")
M((PP)
ISSPECTF ((SP)
Domain(Xe-1a.
Domain(X, Xt-
30

---

Published in Transactions on Machine Learning Research (09/2023)
Proof. Since the infer step uses the standard belief propagation algorithm for exact inference to calibrate the CTs, the distribution encoded by CTFi is exactly II Φ. Therefore, the normalization constant of CTF, (
(Z1) is the following.
II
Z1
Domain(Xi)
The approximation algorithm (Algorithm 2) enforces the following two constraints (a) no CT in CTF is disconnected (b) all interface variables are retained. These two constraints ensure that the number of CTs in C-Faa1,a the same as that C-F This because the first constraint ensures that the number of CTs C7FR-1,a cannot be higher than that CTF The second constraint along with the assumption that input PGM is a connected graph, ensures that each CT in CTF4-1 has at least one interface variable. If it is not so, it mcans that the PGM has disconnected set of variables, which is contradiction. Since all interface variables are retained, Ca has CT corresponding to each CT in CTFR-1- Using Propositions G and 7 each CT in CTF:-1,- is calibrated and has the same normalization constant (NC) as the corresponding CT in -TP The overall NC of the distribution encoded by CTFx-11. is the product of NCs of all disjoint CTs. Therefore, the NC of CTF is the same as that of CTF i.e.
ICCECTR-1,
1IEECTR_,,(C1)
Σ Domain(XR-1aa IISPEECTELLL ( U(SP')
E
IISPECT ((SP)
(Xmain(Xx-:)
CT is built from CT by adding factors in 4 and then calibrated using belief propagation. Therefore, the NC of CTF& F& (Zx) can be written as follows.
Zz= = E HLEETT (.C)(C)) (Xx) ISSPECTT 1. ((SP))
II Φ
ΦE
Thcorem 2 Let the undirected graph corresponding to the PGM be connected and let the sequence {CTF1,". .CFF,) be the SCTF generated by IBIA. Then, the last CTF, CTF, contains single CT, denoted as CTT, IBTA returns the normalization constant of CT, (7n) as the PR.
Proof. First, we show that Algorithm 1 (BuilCTTF) with mes, set lo oo gives single CT if the graph corresponding to the PGM is connected. Without loss of generality, assume an initial CTF, CTF, and a fixed order in which factors are added. CTF, contains disjoint CTs that have single cliques. Each factor that is added either modifies a CT or connects multiple CTs depending on the scope of the factor. Therefore, the number of CTs either decreases or remains the same as new factors are added. Tf there are disjoint CTss after all factors are added, it means that there is no factor in the PGM whose scope contains variables from each of the disjoint CTs. This means that the set of variables in these CTs present in disjoint graphs of the PGM, which is not possible since the undirected graph corresponding to the PGM is connected by assumption. This is true for any initial set of cliques and any order in which factors are added.
If mcsp set to a finite value, Algorithm 1 stops when this bound is reached. The CTss are then simplified and approximated by Algorithm 2. As argued in the proof of Proposition g CT and CTF, have the same number of CTs. Therefore, each CT in CTFR,a corresponds a single CT in CTF; that has the same set of interface variables. Thus, when subsequent factors are added to the CTF in the same fixed order, the same CTss will get modified or connected. Since this is true of every approximate step, the final CTF will contain single CT, denoted as CT,, By Proposition 9, CT, is calibrated and has the normalization constant given by Zn which is returned by IBIA as the PR of the PGM.
31


Reviews:
[{"review_id": "9S5Tj31KM2", "reviewer": "Reviewer_Tkfo", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\nThe use of a particular example to explain the algorithm is very helpful. \n\nThe empirical results are promising, and exhaustive. \n\nWeaknesses: \n\nThe algorithms are themselves quite simple. This is not necessarily a weakness in itself, especially considering good empirical performance, and the fact that it has not been done before, but the presentation despite the algorithms being simple is severely lacking. The background section, and the algorithm description needs a lot of work. I would not have been able to understand the jargon without reading other papers and the example in section 4.1.1. The theoretical \"contribution\" is too hand wavy.  \n\n\nFig 2: why is mcs_{im} 3? CTK_2 still has cliques of size 4, no ?\n\nProp 5 is redundant, the “validity” as stated follows trivially. \n\nProp 8: isn’t the “uniformity” beliefs a very strong assumption ? why is this not assumption not practically limiting ? \n\nProp 9 and theorem 2 are too hand wavy, there is no concrete approximation. The use of phrases like “estimate of” and “depends on” adds nothing of value to the actual understanding of how good or bad theoretically the proposed algorithm could be. Please remove or make it more concrete. \n\nBackground and clarity in writing: \nThe background section needs some more work. If the authors are drilling into basics (which it seems they are given the attempt to define even what a PGM is), the background could use more clarity. \n\nIn background: please mention \\alpha is a set of indices. \n\nThe construction of graphs and cliques does not become clear till Sec 3.3. Please clarify in the background itself if each node of the graph is a factor or that each node can contain more than just a factor.  The definition of PGM merely says PGM is a collection of factors, the correspondence between factors and nodes is not obvious. This is confusing because of the following clash in the notation: in the RIP property of the CT, it says X \\in C_i (does this mean X is contained in some node of C_i ? or that X itself is a node in the click C_i ?), and then says X is present in every node in the unique path between C_i and C_j. The latter statement seems to imply X \\in C_i overloads the symbol “\\in” to mean that X is in some node in C_i, which probably means each node is a factor.  \n\nEq (1) is ill-formed. It should be \\sum_{x \\in C_i \\S_{I,j}} \\beta (x).\n\nThe belief function \\beta(.) springs out of nowhere for anyone who has no background in PGMs. Please write a couple of sentences writing what it is, and how it relates to \\phi. Otherwise the statement about clique beliefs in calibrated CT having the same Z equal to partition function makes no sense. \n\nIf the authors want to assume background for the reader, please just skip the background entirely. If the authors want to not assume any background, please flush it out well. \n\nThe validity of CTF (definition 8) seems redundant. If CTF is a set of CTs, can you give an example of an invalid CTF ? Isnt a CTF by definition valid? \n\nClique size: again what does it mean variable v \\in Clique ? Does it mean variable in a node in the clique ? what is “state” of a variable (is not mentioned anywhere else)? Are all variables discrete ? \n\nI have no idea what definition 12 means, is there a typo? Intersection of variables in CTK_k and set of variables present in factors that have not been added to CTK_i where i can also be k ?\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes new method(s) to approximate the partition function by recursively constructing clique trees. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have added them in the weakness section.", "broader_impact_concerns": "None. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dcre7lb1GO", "reviewer": "Reviewer_uA1W", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "__Strengths:__\nThe problem the authors consider is an important one, and the proposed algorithm seems quite novel to me. The paper itself is very clearly organized, and despite the complexity of the algorithm, it quite understandable: I especially appreciate the running example provided. The experimental evaluation also seems reasonably thorough.\n\n__Weaknesses:__\nMy biggest concern with the paper is that while the authors do a good job describing their algorithm, I (as a nonexpert in this field) have very little intuition for why this should work well, what limitations of existing methods this addresses, how the parameters of the algorithm affect accuracy, and even why we expect this to be more accurate than other methods. The paper would benefit from a much more thorough intuition of where the ideas presented come from, rather than just describing them.\n\nSimilarly, while the experiments are quite thorough, it might help to study more qualitatively a synthetic experiment where we can look at a particular graphical model(s), and see how its properties interact with the properties of the algorithm. Right now, the benchmarking experiments do not supplement my understanding of the algorithm, they just make the case (convincingly) that the algorithm is useful.\n\nProposition 9 and Theorem 10 say that the normalization constants of the CTF(s) are the \"estimate\" of the true partition function. I am confused by this language. Do the authors actually mean that they are exactly the true partition function? More broadly, it would help to better clarify (at least roughly) when the algorithms output (the estimate) is exact, and when it is approximate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes an sequential approach to approximating the partition function of a graphical model. This involves constructing a sequence of clique tree forests (SCFTs) by incorporating factors while satisfying a maximal clique size constraint (a user parameter). The paper also describes an approximation algorithm that takes in a clique tree forest, and outputs another with a reduced clique size, also a user specified parameter. The partition function of the last clique tree is the estimate of the partition function of the graphical model. The authors prove some properties of their algorithms, discuss complexity and apply it to a number of benchmark datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "While the authors do a good job presenting the details of their algorithm, the paper would be of interest to a larger audience if the authors better motivated how the ideas presented here fit into the existing literature (e.g. are there other CTF methods?), what exactly are the novel ideas here, when and why they might be expected to do well or outperform existing methods. Please see my comment on weaknesses above.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9bdkIKZMt1", "reviewer": "Reviewer_M91U", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Although I have a generally positive view of this work - an effective\nmethod for addressing an important problem is presented - there are\nsome improvments that could be made.\n\nIt is only when we get to the \"Related Work\" section that I got some\nidea of how the authors came up with this method - it's a development\nin the \"incremental construction of CTs\" line of work. I think it\nwould be better if this came earlier and if the reader were given some\nidea of why/how incremental construction of CTs work. At present, the\npaper is addressed at those already working in this area (which will\nindeed by its main audience); I think a bit more explanation would\nenlarge the prospective audience considerably. For example, just\nadding a sentence explicitly stating how a calibrated clique tree\nallows recovery of the partition function would be useful.\n\nThis is a \"present a method and empirically test it\" paper. There is\nlittle theory explaining the impact of the various choices in IBIA;\nthe method has the look of something that was derived by trial and\nerror. A there useful theoretical results available in other work on\nincremental construction of CTs? If so, it would be worth flagging up\nhere. \n\nIt's a pity the authors chose to implement in Python. As they note\nthis makes it harder to do useful empirical comparisons to methods\nimplemented in e.g. C/C++. In actual applications all one cares about\nis performance (accuracy/speed) and less about whether this comes from\nclever method, native code execution or good coding. I know this is\nnot a concern of the current paper, but it may be that gains are\navailaible by sticking with IBIA but working on good implementation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "A new method (IBIA) for approximate computation of the partition\nfunction (for a graphical model) is given. The method is explained in\nsufficient detail using well-chosen examples. Much related work is\ncited and briefly described. The value of the method rests\noverwhelmingly on whether it provides reasonable approximations in a\nreasonable time (as compared to existing methods), so the deciding\nfactor is empirical performance. Empirical comparisons against a\nnumber of reasonable competing approaches are done, and sure enough,\nIBIA does well enough to be considered a SOTA method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The main requested changes I have were mentioned with \"strengths and weaknesses\". Here are some additional small points:\n\np1: #P completeness does not necessitate approximation in all cases,\nonly in general\n\np4: SCTF : perhaps remind reader at this point what \"SCTF\" means.\n\np13: typo \"CT Fk+1 is constructed by adding new factors are added\"\n\nTable 6: \"Entries are marked as '-' where all instances could not\nsolved\". This might confuse the reader since they might (reasonably)\ninterpret this as: \"no instances were solved\". I would rephrase to\n\"where not all instances could be solved\" or \"at least one instance\ncould not be solved\".\n", "broader_impact_concerns": "none", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I suggest that Proposition 9 and Theorem 2's statements be made formal, for example the word "estimate of" doesn't immediately imply a formal meaning. I want to suggest that the statements be made mathematically formal, and the current texts could be tagged as informal statements as the current text is helpful in conveying the intuition but not formal enough to verify the proof precisely. Also, the proofs need to be revised; for example, the proof of Theorem 2 says: "we ensure that CTs
remain connected while approximation" but it's not clear how this implies the previous line. I would suggest that authors expand on the proof.
Decision: Accept (poster)