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