Summary
The paper proposes a new approximate inference method for marginals of probabilistic graphical models (PGMs) based on the incremental build-infer-approximate (IBIA) framework. IBIA was introduced by Bathla & Vasudevan in an arXiv preprint in April 2023 to estimate the partition function (normalizing constant). It achieves this by converting the PGM into a sequence of clique tree forests (SCTFs) with a user-defined clique size bound. The sequence is constructed iteratively: the first step (Build) adds factors of the PGM to the current CTF until the maximum clique size is reached; the second step (Infer) calibrates all clique trees using standard belief propagation; and the final step (Approximate) reduces the clique size to another user-defined bound.
This paper builds upon the previous IBIA work in the following ways: it observes and proves several properties of the SCTF generated by the IBIA framework, which it uses to design an extension of IBIA to approximate marginals (in addition to the partition function). This extension works by introducing links between cliques in subsequent steps of the SCTF based on shared variables, called sequence of linked CTFs (SLCTF). It backpropagates beliefs from the last CTF to previous CTFs via the links and re-calibrates each CTF with one round of message passing. Finally the marginal distribution can be inferred from the CTF containing the desired variable. The paper also describes heuristics for the choice of links and notes that in the directed case (i.e. Bayesian networks), it is advantageous to add variables in topological order during the incremental build step.
The experimental evaluation compares with two existing methods, loopy belief propagation (LBP) and iterative join graph propagation (IJGP), on benchmarks from recent UAI competitions with time limits of 2 min, 20 min, and, for some benchmarks, 1h. They report the number of instances solved within the time limit and the average and maximum Hellinger distance over all non-evidence variables. The new method performs performs better than LBP and IJGP on most examples and is similar on the remaining ones, even though IBIA is implemented in Python whereas the baselines are written in C++.
Strengths
The proposed approximate inference method is interesting and improves the performance compared to existing methods (LBP and IJGP). The extension of the IBIA framework with links is new and useful. The explanation is adequate given the page constraints and the use of a running example is very helpful to understand the algorithm.
Weaknesses
The contribution of this paper (adding links) seems to me to be relatively minor compared to the introduction of IBIA itself in previous work. Extending it in some way to relate successive CTFs (here done via links) seems quite obvious (although that might be the benefit of hindsight).
Regarding the experimental evaluation, I had a look at the recent UAI 2022 competition, since the paper mentions that the same benchmarks were used for recent UAI competitions, if I understand line 14 correctly. It looks like IBIA was a competitor there and while performing well, it did not come in first, as the experimental evaluation of this paper might suggest. For this reason, I'm not convinced that the baselines in the experimental section are representative of the field of PGM inference and whether comparisons with more methods are needed to get an accurate picture of IBIA's performance (see my question to the authors below).
As a minor point: while the presentation is generally fine, I found the notation confusing at times, see below.
Questions
(I will update my rating if the author's answers address my concerns.)
My main question is about the UAI 2022 competition: it seems to me that other submissions there performed better than the baselines in this paper (LBP, IJGP). Is this understanding correct? If so, what is the reason for choosing what seem to be inferior baselines?
I was also confused by line 375, which seems to say that topological ordering gives large errors sometimes. Previously, it sounded like topological ordering was essential for good performance and for the theoretical results in Section 3.1 (line 163). Can you clarify the drawbacks and benefits of topological ordering? Do you know why it causes large errors sometimes?
I also noticed some confusing notation, which I mention here for lack of a better place in the review form:
- equation (1): (i - j) looks like subtraction. In graph theory, an edge is often written as a pair (i, j) instead.
- equation (3): I don't understand the point of the quantifier ($\forall$) in the product notation and have never seen this before.
- line 100: $CTF_{k-1,a}$ first looked like a double-index to me, but I assume the "a" just stands for "approximation".
Typos:
- line 69: I think it should be $Scope(\phi_\alpha)$
- Figure 1, incremental build: I think it should be "while" instead of "until"
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
The authors have adequately discussed the limitations of their work.