# IBIA: Bayesian Inference via Incremental Build-Infer-Approximate operations on Clique Trees

arXiv: https://arxiv.org/abs/2202.12003 · HTML: https://mlsanity.com/paper/2202.12003/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 86 references that are in the map.
- First posted on arXiv 24 Feb 2022.

## Builds on (most cited first, 13 of 13)

- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [Inference in Probabilistic Graphical Models by Graph Neural Networks](https://mlsanity.com/paper/1803.07710/) (2018)
- [Belief Propagation Neural Networks](https://mlsanity.com/paper/2007.00295/) (2020)
- [Tractable Inference for Complex Stochastic Processes](https://mlsanity.com/paper/1301.7362/) (2013)
- [Join-Graph Propagation Algorithms](https://mlsanity.com/paper/1401.3489/) (2014)
- [Deeply Learning the Messages in Message Passing Inference](https://mlsanity.com/paper/1506.02108/) (2015)
- [Partition Function Estimation: A Quantitative Study](https://mlsanity.com/paper/2105.11132/) (2021)
- [Computational Advantages of Relevance Reasoning in Bayesian Belief Networks](https://mlsanity.com/paper/1302.1558/) (2013)
- [The Factored Frontier Algorithm for Approximate Inference in DBNs](https://mlsanity.com/paper/1301.2296/) (2013)
- [Dynamic Jointrees](https://mlsanity.com/paper/1301.7369/) (2013)
- [Clustering Without (Thinking About) Triangulation](https://mlsanity.com/paper/1302.4941/) (2013)
- [A Scheme for Approximating Probabilistic Inference](https://mlsanity.com/paper/1302.1534/) (2013)

## Built on by (most cited first, 1 of 1)

- [MPE inference using an Incremental Build-Infer-Approximate Paradigm](https://mlsanity.com/paper/2206.01954/) (2022)

## Abstract (arXiv)

Exact inference in Bayesian networks is intractable and has an exponential dependence on the size of the largest clique in the corresponding clique tree (CT), necessitating approximations. Factor based methods to bound clique sizes are more accurate than structure based methods, but expensive since they involve inference of beliefs in a large number of candidate structure or region graphs. We propose an alternative approach for approximate inference based on an incremental build-infer-approximate (IBIA) paradigm, which converts the Bayesian network into a data structure containing a sequence of linked clique tree forests (SLCTF), with clique sizes bounded by a user-specified value. In the incremental build stage of this approach, CTFs are constructed incrementally by adding variables to the CTFs as long as clique sizes are within the specified bound. Once the clique size constraint is reached, the CTs in the CTF are calibrated in the infer stage of IBIA. The resulting clique beliefs are used in the approximate phase to get an approximate CTF with reduced clique sizes. The approximate CTF forms the starting point for the next CTF in the sequence. These steps are repeated until all variables are added to a CTF in the sequence. We prove that our algorithm for incremental construction of clique trees always generates a valid CT and our approximation technique preserves the joint beliefs of the variables within a clique. Based on this, we show that the SLCTF data structure can be used for efficient approximate inference of partition function and prior and posterior marginals. More than 500 benchmarks were used to test the method and the results show a significant reduction in error when compared to other approximate methods, with competitive runtimes.