Exact Fractional Inference via Re-Parametrization \& Interpolation between Tree-Re-Weighted- and Belief Propagation- Algorithms
Authors: Hamidreza Behjoo
Michael Chertkov
Venue: Accepted by TMLR ()

Abstract: Computing the partition function, $Z$, of an Ising model over a graph of $N$ \enquote{spins} is most likely exponential in $N$. Efficient variational methods, such as Belief Propagation (BP) and Tree Re-Weighted (TRW) algorithms, compute $Z$ approximately by minimizing the respective (BP- or TRW-) free energy. We generalize the variational scheme by building a $\lambda$-fractional interpolation, $Z^{(\lambda)}$, where $\lambda=0$ and $\lambda=1$ correspond to TRW- and BP-approximations, respectively.  
This fractional scheme -- coined Fractional Belief Propagation (FBP) -- guarantees that in the attractive (ferromagnetic) case $Z^{(TRW)} \geq Z^{(\lambda)} \geq Z^{(BP)}$, and there exists a unique (\enquote{exact}) $\lambda_*$ such that $Z=Z^{(\lambda_*)}$. Generalizing the re-parametrization approach of \citep{wainwright_tree-based_2002} and the loop series approach of \citep{chertkov_loop_2006}, we show how to express $Z$ as a product, $\forall \lambda:\ Z=Z^{(\lambda)}{\tilde Z}^{(\lambda)}$, where the multiplicative correction, ${\tilde Z}^{(\lambda)}$, is an expectation over a node-independent probability distribution built from node-wise fractional marginals. Our theoretical analysis is complemented by extensive experiments with models from Ising ensembles over planar and random graphs of medium and large sizes. Our empirical study yields a number of interesting observations, such as  the ability to estimate ${\tilde Z}^{(\lambda)}$ with  $O(N^{2::4})$ fractional samples and suppression of variation in $\lambda_*$ estimates with an increase in $N$ for instances from a particular random Ising ensemble, where $[2::4]$ indicates a range from $2$ to $4$. We also verify and discuss the applicability of this approach to the problem of image de-noising. Based on these experiments and the theory, we conclude that both the computation of the partition function and the computation of marginals can be efficiently performed via FBP at the optimal value of $\lambda_*$.

Published in Transactions on Machine Learning Research (11/2024)
Fractional Inference via Re- Re-Parametrization & Interpolation between Tree-Re-Weighten and Belief Propagation- Algorithms
Exact
Hamidreza Behjoo University of Arizona
Michael Chertkov University of Arizona
chertkon@urizona..co edu
Reviewed on OpenReview: https: // openreview. net/ pet//frum?? id= SWRpggaffee
Abstract
Computing the partition function, Z, of an Ising model over a graph of "spins" most likely exponential in N. Efficient variational methods, such as Belief Propagation (BP) and Tree Re- Weighted (TRW) algorithms, compute Z approximately by minimizing the respective (BP- or TRW-) free energy. We generalize the variational schemn by building X-fractional interpolation, Z(A), where À = 0 and A = correspond to TRW- and BP- approximations, respectively. This fractional scheme coined Fractional Belief Propagation (FBP) - guarantees that in the attractive (ferromagnetic) case Z(TRW) 2 Z(A) > Z(PP), and there exists a unique ("exact") X, such that Z = z(^-), Generalizing the re-parametrizalle approach (Wainwright et al., 2001) and the loop series approach of (Chertkov & Chernyak, 2006a we show how express Z product, Aa Z Z(A) 2(2), where the multiplicative correction, 2(A), is an expectation over a node-independent probability distribution built from node-wise fractional marginals. Our theoretical analysis is complemented by extensive experiments with models from Ising ensembles planar and random graphs of medium and large sizes. Our empirical study yields number of interesting observations, such as the ability to estimate (()) with O(N2:4) fractional samples and suppression of variation in A_ estimates with an increase
for instances from a particular random Ising ensemble, where [2 :: 4] indicates a range from 2 to We also verify and discuss the applicability of this approach to the problem of image de-noising. Based on these experiments and the theory, conclude that both the computation of the partition function and the computation of marginals be efficiently performed via FBP at the optimal value of X
1 Introduction
Graphical Models (GM) are a major tool of Machine Learning that allow expressing complex statistical correlations via graphs. Ising models are the most widespread GM for expressing correlations between binary variables associated with nodes of a graph, where the probability factorized into product of terms, cach associated with an undirected edge of the graph. Many methods of inference and learning in GM are first tested on Ising models and then generalized, for example, beyond binary and pair-wise assumptions.
In this manuscript, we focus on computing the normalization factor Z (called the partition function), over the Ising models. The problem known to be of sharp-P complexity, likely requiring computational efforts that are exponential in the size (number of nodes, .N) of the graph (Welsh 1991 Jerrum Sinclair 1993
Goldberg & Jerrum 2015 Barahona 1982). There are three general approximate methods to compute Z:
(a) climination of (summation over) the variables one-by-one (Dechter) 1999 Dechter & Rish 2003 Liu &
Thler 2011: Ahn et al. 2018); (b) the variational approach (Yedidia al.] 2001
2005):
(c) Monte Carlo

---

Published in Transactions on Machine Learning Research (11/2024)
(MS) sampling (Andrieu et al. 2003 (See also reviews (Wainwright & Jordan 2008 Chertkov 2023 and references therein.) In this manuscript, we develop the latter two methods. We also pay special attention to providing and tightening approximation guarantees. We base our novel theory and algorithm on the provable upper bound for Z associated with the so-called Tree Re- Re-Weighted (TRW) variational approximation (Wainwright al. 2003 2005) and on the Belief Propagation (BP) variational approximation (Vedidia al. 2001 2005), which is known to provide a lower bound on Z in the case of an attractive (ferromagnetic) Ising model [Ruozzi p012). Note that there are also additional upper bounds derived from log-determinant relaxations, wherein binary graphical models are relaxed to Gaussian graphical models on the same graph Wainwright & Jordan, 2006; Ghaoui & Gueye, 2008). However, these bounds are generally considered to be loose, and to the best of our knowledge, there is no known method to effectively narrow the gap between these upper bounds and the exact partition function.
1.1 Relation to Prior Work
In addition to the aforementioned relations to foundational work on the variational approaches Yedidia
ct al.
2001 2005). MCMC approaches (Andrieu et al., 2003). and lower and upper variational bounds
Ruozzi 2012 Wainwright et al. 2003), this manuscript also builds on recent results in other related areas,
in particular:
2005 and TRW (Wainwright et al.) 2003 2005), in the spirit of fractional BP (Wiegerinck & Heskes 2002 Chertkov & Yedidia 2013 thus introducing a broader family of variational approximations.
We extend the ideas of parameterized interpolation between BP Yedidia et al. 2001
Expanding on the previous point, since our approach can be considered as an interpolation bridging the TRW and BP approximat for the GM's partition function, it seems appropriate to cite (Knoll al. 2023 where another interpolation approach was unveiled. The interpolation discussed in (Knoll et al. 2023 is of an anncaling type it starts with the trivial (iighttemperature) model where all components are independent, and then the potentials of the pair-wise model are luned gradually, adjusting the scaling parameter from 0 to 1. At every incremental step, a BP algorithm is employed to track the fixed point, ensuring the method's precision and reliability. The primary objective of this approach was to surpass the conventional BP in both accuracy and convergence rates. contrast, our approach is designed to ascertain the exact value of the partition function and marginals, thus setting a new standard for precision in the analysis of complex systems.
We utilize and generalize re- re-paraamerizaation Wainwright et al. 2001 loop calculus (Chertkov & Chernyak]
gauge transformation, and 2020 techniques, as well as the
2006a b Chertkov et al.
combination of the two @Willsky et al. 2007)-
Our approach is also related to the development of MCMC techniques with polynomial guarantees, the so-called Fully Randomized Polynomial Schemes (FPRS), developed specifically for Ising models of specialized types, e.g., attractive (Jerrum & Sinclair 1993) and zero-field, planar (Gómez et al.
2010: Ahn et al. 2016.
1.2 This Manuscript's Contribution
We introduce a fractional variational approximation that interpolates between the classical Tree Re- Weighted (TRW) and Belief Propagation (BP) cases. The fractional free energy, ((A) llgg (A)), defined as the negative logarithm of the fractional approximation to the exact partition function, Z = exp(-F), requires solving optimization problem, which is achieved practically by running a fractional version of one of the standard pussage-passing algorithms. The parameter À E [0, 1] interpolates between the X = 1 and X = 0 cases, corresponding to BP and TRW, respectively. The interpolation technique, particularly our focus on Xe, which lies somewhere between x = 0 and À = 1 and for which ( Z, is novel - to the best of our knowledge, this is the first manuscript where the interpolation technique is discussed. Basic definitions, including problem formulation for the Ising models and variational formulation in terms of the node and edge beliefs (proxies for the respective exact marginal probabilities) are given in Section 2 Assuming that
2

---

Published in Transactions on Machine Learning Research (11/2024)
the fractional message-passien algorithm converges, we study the dependence of the fractional free energy the parameter À and the relationship between the exact value of the free energy (the negative logarithm of the exact partition function) and the fractional free energy. We report the following theoretical results:
We show in Section of x (Theorem 3.1 proved in Appendix Bi, which is also concave in X (Theorem 3.2.
3 that under some mild asumptions F(A) is contimuous and monotone function
Our main thcoretical result, Theorem 4.1 presented in Section ! and proven in Appendix C states that the exact partition function can be expressed as a product of the variational free energy and a multiplicative correction, Z = z 2(A) The latter multiplicative correction term, 2(A), is stated as an explicit expectation of an expression over a well-defined "mean-field" probability distribution, where both the expression and the "mean-field" probability distribution are stated explicitly in terms of the fractional node and edge beliefs. We note that such bridge between the exact partition function and the approximate partition function, known as the Loop Scries/ Calculus, was introduced in Chertkov & Chernyak (2006a bj and elaborated upon in Willsky et al. (2007) for the case of the Bethe (Belief Propagation), where À = 1. However, to the best of our knowledge, it has not been reported in the literature for any other values of À E [0, interpolating between BP and TRW, particularly for À = corresponding to TRW.
The theory is extended with experiments reported in Section 5 Here we show, in addition to confirming our theoretical statements (and thus validating our simulation settings), that:
Evaluating Z (A) at different values of À and confirming that the result is independent of À suggests novel approach to reliable and efficient estimate of the exact Z - the Fractional Message
Passing Algorithm [
Analyzing ensembles of the attractive Ising models over graphs of size N,, we observe that fluctuations of the value of X, within the ensemble, where Z(^.) = Z, decrease dramatically with an increase in N. This observation suggests that estimating A. for an instance from the ensemble allows efficient approximate evaluation of Z for any other instance from the ensemble.
Studying the importance-sampling procedure based on TRW BP, we empirically estimate (A) and observe convergence with the number of samples. Analyzing the speed of convergence with the number of nodes, N, in the Ising model, our experiments show that the correct mean of Z(A)), evaluated at A = A., is recovered with N2 samples. Additionally, the variance of the respective importance sampling is reduced beyond a pre-fixed ((1) tolerance with A samples.
Analysis of mixed Ising ensembles (where attractive and repulsive edges alternate) suggests that for instances with sufficiently many repulsive edges, finding, X. E [0, 1] may not be feasible.
We demonstrate the effectiveness of our approach in the context of image denoising, as detailed Section 5.7 This application highlights the practical utility of our theoretical developments in a real-world machine learning task. Furthermore, the denoising experiments support the conjecture that the optimal X, is special not only because the Fractional Belief Propagation (FBP) at this value yields the exact partition function, but also because estimating marginal probabilities at X. is significantly more accurate. The error in these estimates decreases as the size of the problem increases, underscoring the robustness and scalability of our method.
We have brief discussion of conclusions and paths forward in Section 6
2 Technical Preliminaries
2.1 Ising Models: the formulation
Graphical Models (GM) are the result of a marriage between probability thcory and graph theory designed to express a class of high-dimensional probability distributions that factorize in terms of products of lower- dimensional factors. The Ising model is an exemplary GM defined over undirected graph, G = (V,E). The
3

---

Published in Transactions on Machine Learning Research (11/2024)
Ising Model is stated in terms of binary variables, 2a =1, and singleton factors, ha E R, associated with nodes of the graph, E V, and pair-wise factors, Jah E IR, associated with edges of the graph, {a, b} E &. The probability distribution of the Ising model observing a state, I = (Iala E V) is
p(z|J.h)) exp (- J.) Z(J,h)
Σ #E{+1HIVI
exp(-E (-
(1)
h(J,
E Ex; J.).
E Eab(Fa; 0b), V(a,b) E Eub(Fa, - Jab hata da h6 do-
(2)
fa.JEE
where da is the degrec of node a in 9 and J == (Jas E E), h (Mala E V) are the pair-wise and singleton vectors, assumed given. E(x; J, h) is the energy function and Z(J,h) is the partition function. Solving the Ising model inference problem means computing which generally requires an effort that is exponential in N Vl.
2.2 Exact Variational Formulation
Exact variational approach to compute Z consists in restating Eq. 1 terms of the following Kullback- Leibler distance between exp(-E(ax;J] J. h)) and probability distribution, B 1-1, + [0, 1], E. B(x=) 1, called belief:
F log Z min
E (E())B(()) - ((x) log B(x)),
(3)
[(())
where is also called the free energy (following widely accepted physics terminology).
The exact variational formulation 3 is the starting point for approximate variational formulations, such BP (Yeiidia et al., 2005) and TRW (Wainwright & Jordan 2008), stated solely in terms of the marginal beliefs associated with nodes and edges, respectively:
Va V, Vxa. Bo(xa) = Σ B(x), V(a,b) E E, Vra.zs: Bas(Fa, =
Σ
B(x).
(4)
a/,
Moreover, the fractional approach developed in this manuscript provides a variational formulation terms of the marginal probabilities, generalizing (and, in fact, interpolating between) the respective BP and TRW approaches. Therefore, we turn to stating the fractional variational formulation.
2.3 Fractional Variation Formulation
Let us introduce a fractional-, or A- reporamctrization of the belief (proxy for the probability distribution of x>)
(x) Iaa (Babl r6)) (A)
(5)
IL (Ba (xaa) En. 11
where b bw shorthand notation for b such that, given a E V, (a.b) EE Here in Eq. >-parameterized edge appearance probability
5
Pab the
(A) Pab Pab + X(1 Pab), (A:0-1))
(6)
which is expressed via the edge appearance probability, Pab, dependent on the weighted set of spanning trees, T : {T), of the graph according to the following TRW rules (Wainwright 2002 Wainwright & Jordan 2008
b( E V: Pab
Σ
Ep-=1 PT,
(7)
TET, at. (a.)eT
TET
4

---

Published in Transactions on Machine Learning Research (11/2024)
Several remarks in order. First, À 1 corresponds the case of BP. Then Eq. is exact in the case of tree graph, but it can also be considered as (loopy) BP approximation in general. Second, and mentioned above, X = 0, corresponds to the case of TRW. Third, the newly introduced (joint) beliefs are not globally consistent, i.c. Ex (x) # for any X, including the À ==0 (TRW) and X == (BP) cases.
Substituting Eq- 5 into Fq. 3 we arrive at the following fractional approximation the exact free energy stated as an optimization over all the node and edge marginal beliefs, B =
63 E, Ta
=1) U (z, E V. 2a =1):
F(A) = ( (B(N)), B(A)= == arg min F(A) (B),, BED
(8)
(B) = E(B)- (B), B(B)
Σ
Σ
EablEas I6 (an (Ta)
(a.b]EE #e
(B) = E pas Σ
BablFar Hb) log Bab Ib) +
Σ
(2)
-1
Σ
Ba (2a log (xaa)
Pab
fa.lEE En.ta=t1
b
z,=t1
(a( = Ex Bas(Fa;
Ya E V, vbn a, Vxa = +1;
(a)
Eem0m, (as vb)) = 1,
D: B
(9)
b(a,b] EE;
(b)
Bab Ib) 2 0,
v(a,b) b} E,, Yæa, Tb = #1.
(c)
As discussed in Section 3 in detail, X 0 results in Z(A) which upper bounds the exact Z, and À = 1 results in lower bound if the model is attractive.
The optimization over beliefs in Eq. (8) can be restated in the Lagrangian form (see Appendix A.1 p. Fixed points of the Lagrangian (potentially many) satisfy the so-called mnssage-passiingg equations (see Appendix A.2h. We will refer the iterative algorithm that finds marginal probabilities and respective message variables y by solving these equations the basic Fractional Belief Propagation (FBP) algorithm. Consistent with the equations from Appendices A and A.2 the resulting messages can then be used to find the FBP approximation, Z(A), for the partition function Z as follows:
2(1) = exp (-F(A) = exp (B(N)))))))
eexp
II ta.bLEE
Σ Hart
exp
Eas(Do: 1b)
(10)
(12)
Σ (2)
Σ (2)
(A)
1-Σ
( (Ira)
(A)
Pah
II
EII p p (Ira)
(2)
ona
aEv
bwa
where ((A) is defined in Eq.
18 and its components are expressed via (A and pa according to Eqs.
17 18
3 Properties of the Fractional Free Energy
Given the construction of the fractional free energy, described above in Section 2.3 and also detailed Appendix A we are ready make the following statements. Theorem 3.1. [Monotonicity of the Fractional Free Energy] Assuming p == (patl (a (a,b) E E) is fixed, and ((A) is differentiable in X, F(A is a continuous, monotone function of X.
Proof. See Appendix
Remark. The continuity of (A) in À is a technical condition that almost always holds. This condition may break, albeit in some rare cases, when at a particular value X, two (or more) distinct local minima of the fractional free energy (()(B)) (considered as function of B) yield the same value. In such instances, as we vary À and pass through this special value of X, the absolute minimum can jump from one local minimum to another.
5

---

Published in Transactions on Machine Learning Research (11/2024)
Theorem 3.2. [Concavity of the Fractional Free Energy] Assuming p (Pas [a, E) is fixed, F(A) is concave function of X.
(A) Proof. Since Pab is linear in X, from Eq. Ag )1, have
(B) also linear in A. Therefore, for any A, do, A with \ A 11 (B) +
X do H (B), dι 2o
(B)
\ A0
and consequently,
(B)- =
\1 x
(B) +
X A0 p()n) (B).
\ 0 A
\1 Ao
Thus, we have
A1 A ((A))(BA))
X Ao ((Ai)(B(A))
F(A) (B(A)
+
\1 Ao
\1 Ao
2 \1 - X
A - Ao ((A)(((A:))
+
\ Ao
d1 do
\1 X (((a))
x - do FT(I))
21 d0
where we used the fact that (BAA((())) = ming (B) S (B(A)) at the incquality step. This proves the concavity of ((A) in X.
Note that all the statements in this manuscript far are made for arbitrary Ising models, i.e., without any restrictions on the graph and vectors of the pair-wise interactions, J, and singleton biases, h. If the discussion is limited to altractive ((erromagnetcc Ising models, V(a, b} E E Jas 2 0, the following statement becomes a corollary of Theorem 3.1
Lemma 3.3. [Exact Fractional] In the case of an attractive Ising model, any fixed p, and also assuming that (AA) is differentiable in A, there exists X, E [0, 1] such that Z = Z.
Proof. In the case of attractive Ising model, BP provides lower bound the exact partition function, z(A=1) < Z, proven in (Ruozzi, 2012). On the other hand, know from (Wainwright & Jordan 2008). and also by construction, that Z(==)) > Z, i.e., the TRW estimate of the partition function provides an upper bound to the exact partition function. These lower and upper bounds, combined with the monotonicity of z(A) stated in Theorem 3.1 result in the desired statement.
4 Fractional Re- Re-Parametrization for Exact Inference
Theorem 4.1. [Exact Relation Between Z and (A) for any X [0,1]] ),
Z = 2(1) (()),
(11)
poa)
(2)
II
(B()) ab
(Iar (Far x66
II (x (Iar xx))
()) Σ
ta,blEs
E ca = E
Bapp ()
fabbeE
(12)
E
(2) Pac
21
II VEV
(Ba))(xa)
[B(a) (Ix)
II aEV
BB( (Ia)
where Po
(2)
(x) I1, B
(A) (I.) is the component-indeeenneen distribution devised from the FBP-optimal
mode-marginal probabilities.
Proof. See Appendix

---

Published in Transactions on Machine Learning Research (11/2024)
Algorithm 1: A-optimal Fractional Belief Propagation
Input: -= (V, graph.
Initialize: Pab = (1) 1)
For: À 0: 0.05 1,
1. Compute (A)
Pab Pab X(1 Pab))
2. Use Eq. 100 (and formulas from Appendix A.2 to find z B( (xa). Bid (xx))
(Ia: xbb)
3. Compute (A) utilizing Eq. 12
End
1. Find Aa where ((A)
2. Return Z = Z(a.)
Notice that Z(2), defined in Eq. 12 is the exact multiplicative correction term expressed in terms of the FBP solution. This term should equal 1 the optimal value of (J, h). According to Lemma 3.3 this optimal value is achievable in the case of the attractive Ising model.
Theorem 4.1 suggests using A presented as pseudo-algorithm, which refer to the X-optimal (or simply optimal) Fractional Belief Propagation Algorithm (O-FBP), to approximate the exact partition function Z.
We will also explore an alternative method for transforming the main theoretical result of this paper, Theorem into a practical computational tool in the next subsection.
4.1
4.1
Optimal X from Z
Algorithm 2: Optimal À from Z
Input: (V,E), graph. Exact value of Z. Initialize: V(a, 6) E Pab (IVI- 1)
For: X = 0: 0.05 1,
(2) 1. Compute bf E E Pab
Pab X(1 Pab).
Use Eq.
10 (and formulas from Appendix A.2 to find Z()
End
1. Find Xa where Z(2)
2. Return Z = z(aa)
Suppose we have access to the exact value of the partition funct ion Z. Then, Theorem suggests Al Algorithm 2 which allows us to identify the optimal Xe, that is, the value of À for which FBP (which can be evaluated efficiently, typically in linear time with respect to the problem size) outputs the exact result for the partition function. The exact value of Z, required as an input for Algorithm can be determined via the following TRW- (or BP-) based computations:
1. Compute ( (or ())).
2. Compute Z (or ()) by sampling according to Eq. 10 (and the formulas in Appendix A.2
3. Use the identity 7 2(1 Z(1 (or 7 =7 ((0))

---

Published in Transactions on Machine Learning Research (11/2024)
As we will see in the next section, where turn to the empirical exploration of the approach presented in this paper, Algorithm 2 proves to be useful for making efficient computations of marginals in high-dimensional case.
5 Numerical Experiments
5.1 Setting, Use Cases and Methodology
In this section, present the results of our numerical experiments, supporting and also further developing the theoretical results of the preceding sections. Specifically, we will describe the details of our experiments with the Ising model in the following "use cases:" (1) Over an exemplary planar graph N x N square grid, where N = [3 :: 5]: (2) Over a fully connected graph, KN, where N = [9 :: 5*]. The notation [a :: bj indicates a range from a to b.
In both cases, we consider attractive models and mixed models that is, models with some interactions being attractive (ferromagnctic), Jab > 0, and some repulsive (antiferromaanetic)) Jab 0. We experiment with the zero-field case, h = 0, and also with the general (non-zero field) case. All of our models are "disordered" in the sense that we have generated samples of random J and h. Specifically, in the attractive (mixed) case, components of J are i..d. from the uniform distribution, (40, 1) (M(-1, 1)), and components of h are iidd. from 1(- In some of our experiments, we draw a single instance of J and h from the respective ensemble. However, in other experiments - aimed at analyzing the variability within the respective ensemble we show results for a number of instances.
We acknowledge that there is significant flexibility in selecting a set of spanning trees and then re-weighting respective contributions to p : (Pab {a, b} E E) according to Eq. 77). (See some discussion of experiments with possible p in (Wainwright et al. 2005).) However, we chose not to test this flexibility. Instead, in all of our experiments, P is chosen uniformly for a given graph. A direct corollary of Lemma 7.3.2 from Wainwright] 2002) is that if the edge-uniform re-weighting is feasible, the following relation holds for all a, E: Pas = (IV in the TRW rules of Eq. (7) solely in terms of the it shown in (Wainwrihht, 2002) that the edge-uniform re-weighting is feasible and optimal, providing the lowest TRW upper-bound in the case of highly symmetric graphs, such as fully connected or double-perion square grids. Our experiments are conducted on graphs where identifying the feasibility of edge-uniform re-weighting is straightforward. However, we also note, consistently with a remark in (Wainwright) 2002 that there exist some exotic graphs for which edge-uniform assignment is infcasible.
1)) ())
This lemma allows us to restate the set of linear constraints defining the polytope Pab: thereby excluding tree- tree- weights. Moreover,
We introduced the X-optimal FBP Algorithm 1 which approximately calculates the partition function for a specified Ising model on graph g (V,E). This algorithm generalized traditional message- passing methods by interpolating between the Tree- Free-Reweighted case (A 0) and the Belief Propagation case (A 1) for any x E 10. Utilizing Theorem 4.1 the algorithm identifies a particular value, denoted as X.; where the fractional partition function (A is approximately equal to the exact partition function Z. The algorithm employs Eq. 12 to determine the correction factor ((A) utilizing fractional node and edge beliefs. Additionally, we initialize the edge appearance probabilities Pas uniformly.
message-passing
To compute the fractional free energy, F(A) (minus the log of the fractional estimate for the partition function), we generalize the approach of (Biller & Huang 2018), which allows efficient, sparse-matrix based implementation. Our code is available on https: /ttp//tttttttt/tt//// com homm/hamdrra feaaidreeabehjaeeo www.o//aaanonaaaaaeeeeeoooaaaaae TRW
To compare the fractional estimate ((A) - log (A) with the exact free energy. F = log Z, we either use direct computations (feasible for the 8 x 8 grid or smaller and for the fully connected graph over 64 nodes or smaller) or, in the case of the planar grid and zero-field, when computation of the partition function is roduced to computing determinant, we use the code from (Likhosherstov et al. 2019) (soc also references therein). Our computations are done for values of À equally spaced with the increment 0.05, between 0 and l.
8

---

Published in Transactions on Machine Learning Research (11/2024)
25.7
33.0
0.0
0.2
25.6
32.8
0.1
0.0
log Z
log Z
log 2(1)
25.5
N
32.6
0.2
log
0.2
25.4
32.4
0.3
0.4
25.3
32.2
00.4
0.6
0.0
0.5
1.0
0.0
0.5
1.0
À
(a)
(b)
0.0
70
6
66.8
00.
68
Z
0.2
66.6
1092
log
0.3
66
2
66.4
004
64
005
66.2
0.0
0.5
1.0
0.00
0.25
0.50
0.75
1.00
À
À
(c)
(d)
Figure 1: The case the attractive Ising Model (a) with non-zero field and random interaction, h, J U(00 1)
on a 3 planar grid; and (b) with zero field and random interaction, ~ ~0, 1) on 3 3 planar grid; (c) with non-zero field and random interaction, h, J ((0 1) on a Kg complete graph and (d) with zero field and random interaction, J ~ U(O, fractional free energy) the left and the respective correction factor Z(A) the right the fractional parameter, A. We observe monotonicity and concavity of F(A) on X.
K₂ complete graph. We show fractional log-partition function (minus
The log-correction term, log (() log Z - log Z(A), is estimated by direct sampling according to Eq. 12 (See Fig. 3 and the respective discussion below for empirical analysis of the number of samples required to guarantec sufficient accuracy.)
It is important to stress that, even though the A-optimal FBP Algorithm [ is a direct extension of what was discussed in the literature in the past for the TRW = and BP = 1 cases, extending the algorithm to the interpolating À E [0, 1] values is novel. In this regard, the and À versions of the X-optimal FBP Algorithm should be considered as providing baselines baselines/benchhmatt benchmarks for its performance at the interpolating values of X.
5.2 Properties of the Fractional Free Energy
We use Algorithm for the fractional estimate of the log-partition function (minus fractional free energy), log ((A) (1)), and the log of the correction term, log ((A) log 7 log ( F()) F. The results are

---

Published in Transactions on Machine Learning Research (11/2024)
shown as functions of À in Fig. | where the monotonicity and concavity of F(A), proven in Theorem 3.1 and respectively, are confirmed.
Theorem 3.2
5.3 Relation between Exact and Fractional
Figs. D also provide empirical confirmation of Lemma 3.3 on existence of in the case of attractive Ising model for which Z = Z. Morcover, the full statement of Theorem 4.1 i.c., the equality between the left- and right-hand sides of Eq. [1 is also confirmed in all of our sinulations (over Ising models, attraclive not) with high accuracy (when we can verify it by computing Z directly).
4.40
4.45
4.35
4.30
4.40
logz
log Z
4.225
4.35
4.20
4.30
4.15
4.25
4.10
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
A
(b)
4.55
4.55
4.50
4.50
log Zg
4.45
log ZM
4.45
4.40
4.40
4.35
4.35
4.30
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
A
(d)
Figure 2: Planar zero-field Ising models for x n grid with J (4( 1). For each n, four different instances are generated by sampling uniformly random from the unit interval and the exact values, A., are shown by open symbols on each graph. (a) 10 x 10 (b) 20 20 (c) 30 x 30 (d) 40 x 40.
5.4 Concentration of the Fractional Parameter in Large Ensembles
Fig. 5 in Appendix shows the dependence of F(A) on the fractional parameter, X, for number of instances drawn from two exemplary attractive use-case ensembles. We observe that the variability in the value of F(A)
is significant. Variability in A,, where (().) Z, is also observed, even though it significantly smaller.
This observation suggests that the variability of X within an attractive ensemble decreases as N grows.
This hepothesis is confirmed in experiments with larger attractive ensembles, illustrated in Fig. 2 for
10

---

Published in Transactions on Machine Learning Research (11/2024)
different N. For each N in the case of an N x N grid, we generate 4 different instances. We observe that as N increases, the variability of Å. within the ensemble decreases dramatically. This observation is quite
remarkable, as it suggests that it is sufficient to estimate X for one instance in large ensemble and then use for accurate estimation of by simply computing Z(^-), This is also indicated in Algorithm 3 Our
estimations, based on the data shown in Fig. 2 suggest that the width of the probability distribution of X within the ensemble scales as x 1/vN with an increase N.
Algorithm 3: Fractional Belief Propagation for Large Ensembles
Input: Ensemble G of similar graphical models, number of samples M, new instance Gnew Output: Estimated partition function 2 and marginals {B;}. [B:r} for Gnew Function PrecomputeLambddsttan (G, M):
A 0;
for i to M do
G G;
// Sample graphical model from the ensemble // Using Algorithn
X Fin(OptimllLammda((i A - AU
end return M ExEAd:
// Average X*
Function o (Grews X²):
(X))
Compute edge appearance probabilities Pig using Eq. (6)
(X*)
Run TRW algorithm with Pig on Gnewi
Obtain z(A") using Eq.
10 and marginals (8.), (Bi));
return z(8), (B. }.
5.5
Convergence of Sampling for Fractional Partition Function
54.0
85.0
53.0
84.0
2
log2
logZ
52.0
83.0
51.0
82.0
λ=0
50.0
81.0
1
3
4
1
2
3
i
(b)
Figure 3: Dependence of the sample-basod estimate of Z on the number of samples in the case of attractive Ising model for two different values of À in the case of (a) 4 x and (b) grids, where elements of J and h are drawn i.i.d. from 4(0, 1]. The number of samples are N where 1,2,3, 4 and N |V] (that is N 16 in (a) and N = 25 in (b).
Fig. shows the dependence of the importance sampling- estimate of Z on the number of samples and where the experiment was performed 100 times, and we report the mean and variance. Our major observation here that the result converges with an increase in the number of samples. Moreover, comparing
11

---

Published in Transactions on Machine Learning Research (11/2024)
the speed of convergence with the size of the system, N, conjecture that the number of samples needed for the convergence of the mean scales as O(N)) in the case of generic A. However, the scaling becomes much better, ((N2), at the optimal X Another empirical conclusion extracted from Fig. 3 is that the variance of the importance sampling for estimating (()) at A = X2 reaches an O(1) (predefined) tolerance with the N samples.
5.6 Fractional Approach for Mixed (Attractive and Repulsive) Cases
Fig. in Appendix D shows two distinct situations which may be observed in the mixed case where some of the interactions are attractive but others are repulsive, allowing z be smaller or larger than Z. The former case is akin the attractive model and [0, 1], while in the latter case there exists no X2 [0, [] such that Z(..) Z.
5.7 Application in Machine Learning Image De-Noising
Consider a black-and-white image represented as a binary vector, (z, =1|a E V), where V is the set of nodes in two-dimensional
square grid. For example, the cameraman image shown in Fig. 4 is 256 x 256 65536 pixel image, which is represented as binary vector, E {+1) ] 165536
The de-noising problem is set up as follows Koller & Friedman (209)): assume that an image is sent through a noisy Bernoulli channel, where each pixel is flipped independently with a probability e. The noisy version of the image y received, and the task is to recover the original image æ.
We also make the plausible assumption that images are constructed in such a way that the probability for two neighboring pixcls and b to have the same values Fa and Fb; (xp(J)/ccshh(()) probability exp(-J))(cosh(() that they have opposite values, where J J> 0.
is higher than the
Then, the probability for the image æ to be reconstrueted from the observed noisy image is given by
Ia + E IoYla h = log p( y) exp ()
E
1
E
(13)
fa.bEEE
aEV
where G = (V,E) is the graph of the two-dinensional grid, and E is the set of edges of the grid. Clearly, Eq. 13 shows the probability distribution of the ferromagnetic Ising model.
The basic FBP algorithm solving Eq. [ well its BP and TRW versions, with x 1 and A 0 respectively, can all be utilized to solve the de-noising problem.
Results of experiments de-noising an image with different algorithms are shown in Fig. 4 where pixels are flipped with the noise level corresponding to = 1.1. We then optimize the J parameter in each algorithm to obtain the best performance, evaluated according to the following error function:
Error Number of pixels different in true image and denoised version
Total number of pixels
We find that in the BP and TRW cases, the optimal J values (minimizing the error) are 0.28 and 0.32 respectively. In the case of the basic FBP, we optimize not only over J but also over X, resulting in optimal values of = 0.3 and X = 0.1. We observe that the basic FBP algorithm demonstrates improved performance compared to both BP and TRW algorithms.
Note that this example is too large to reliably evaluate our X-optimal FBP algorithm However, we conjecture that the value of X obtained by minimizing the error will converge, in the thermodynamic limit of large graph, to the value of X which is optimal within Algorithm I This conjecture is intuitively based on two facts. First, the error is expressed in terms of pixel marginals. Second, the À that oplimizes the pixel marginals should be close to the X that optimizes the partition function. This because, in the thermodynamic limit, the marginals can be reformulated terms of the partition functions of the graphical models, which differ from the original one only by fixing the respective x, variable (to =1) at single pixel among many.
12

---

Published in Transactions on Machine Learning Research (11/2024)
Image
Noisy Image
BP
TRW
FBP
3.56%
3.48%
3.23%
Figure 4: Different algorithms and their correspouding errors (listed below each image) for image de-noising.
It is also important to emphasize that even though the optimal X was defined for Z the partition function inspired by results reported in Section 5.5 we have used it in this section to compute marginals. Indeed, major empirical observation made in Section 5.5 suggests that computing the multiplicative correction Z by sampling at the optimal value, X,, requires significantly fewer samples. In other words, the variance of sampling is minimal at the optimal value. This suggests that evaluating other expectations, particularly those corresponding to marginals, will also require fewer samples. Moreover, we also observed that the variance decreases with the model size. Based on all these observations, as well as the empirical advantage of evaluating marginals via FBP at X. illustrated in Fig. | we hypothesize that ovaluating FBP at the optimal X, will provide exact results not only for the partition function but also asymptotically (when the problem size increases) for marginals.
Adding to this discussion, observations reported in Section 5.4 on the concentration of X in large ensembles provide further support for the hypothesis that it is sufficient to estimate X- for only one (representative) GM from the ensemble. This result can then be used not only to estimate the partition function in other GM models of the ensemble but also to compute marginals via FBP efficiently. Note that this hypothesis also emphasizes the utility of Algorithm g which allows us to estimate X, from the exact Z.
6 Conclusions and Path Forward
This manuscript suggests new promising approach to evaluating inference in Ising Models. The approach consists in, first, solving fractional variational problem via a distributed algorithm resulting in the fractional estimations for the partition function and marginal beliefs. We then compute multiplicative correction to the fractional partition function by evaluating a well-defined expectation of the mean-field probability distribution both constructed explicitly from the marginal beliefs. We showed that the freedom in the fractional parameter is useful, c.g. for finding optimal value of the paramcter, X., where the multipicative correction is unity. Our theory-validated experiments result in a number of interesting observation, such strong suppression of fluctuations of X, in large ensembles. We also demonstrate how the FBP approach can efficiently and more accurately solve the de-noising problem in machine learning compared to BP and TRW approaches. Finally, the combination of theoretical and empirical observations led us to hypothesize that the optimal value of X,, computed for a single graphical model within an ensemble, provides asymptotically exact values (in the limit of large and increasing system size) not only for the partition function but also for the marginals.
As path forward, envision extending this fractional approach along the following directions:
Proving or disproving the concentration conjecture and small number of samples conjecture, made informally in Section 5.4 and Section 5.5
respectively.
Generalizing the interpolation technique, c.g. building a schome interpolating between TRW and Mean-Field (see e.g. Chapter of Wainwright & Jordan (2008)). This will be of special interest. for the case of the mixed ensembles which are generally out of reach of the fractional approach (between TRW and BP) presented in the manuscript.
Generalizing the interpolation technique to a more general class of Graphical Models.
13

---

Published in Transactions on Machine Learning Research (11/2024)
We also anticipate that all of these developments, presented in this manuscript and others to follow, will help to make variational GM techniques competitive with other, and admittedly more popular, methods of Machine Learning, such as Deep Learning (DL). We foresee that in the future, there will be more ex- amples where variational GM techniques will be enhanced with automatic diffcrentiation, e.g. in the spirit of (Lucibello et al. 2022), and also integrated into modern Deep Learning protocols, e-g. as discussed inn Garcia Satorras & Welling, 2021). This hybrid GM-DL approach is expected to be particularly beneficial and powerful in physies problems where we aim to learn reduced models with graphical structures prescribed by the underlying physics from data.
14

---

Published in Transactions on Machine Learning Research (11/2024)
References
Sung-Soo Ahn, Michael Chertkov, and Jinwoo Shin. Synthesis of MCMC and belief propagation. In Advances in Newral Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
Sungsoo Ahn, Michael Chertkov, Adrian Weller, and Jinwoo Shin. Bucket Renormalization for Approximate Inference. volume 80 of Proceedings of Machine Learning Research, pp. 109-118. PMLR, Jul 2018.
Christophe Andrieu, Nando de Freitas, Arnaud Doucet, and Michael Jordan. An introduction to MCMC for machine learning. Machine Learning, 50(1):5 43, Jan 2003.
F Barahona, On the computational complexity of ising spin glass models. Journal of Physics A: Mathematical and General, 15(10):3241, oct 1982. doi: 10.1088/ 10.1088/0305-4477 (4705-4470/15/ 14170011110022/ 15/10/02..
Reid Bixler and Bert Huang. Sparse-Matrix Belief Propagation. In Proceedings of the Conference on Un- cerlainly in Artificial Intelligence, 2018.
Michael Chertkov. INFERLO: Inference, Learning and Optimization with Graphicol Models. Leaving Book (sclf published for now), 2023. URL https://t.ly////e
Michael Chertkov and Vladimir Y. Chernyak. Loop calculus in statistical physics and information science. Phys. Rev. E, 73:065102, Jun 2006a.
Michael Chertkov and Vladimir Y Chernyak. Loop series for discrete statistical models on graphs. Journal of Statistical Mechanics: Theory and Experiment, 2006(06):P06009, Jun 2006b.
Michael Chertkov and Adam B. Yedidia. Approximating the permanent with fractional belief propagation. Journal of Machine Learning Research, 14(62):2025 2066, 2013.
Michael Chertkov, Vladimir Chernyak, and Yury Maximov. Gauges, loops, and polynomials for partition fonctions of graphical models. Journal of Statistical Mechanics: Theory and Experiment, 2020(12):124006,
dec 2020.
Rina Dechter. Bucket elimination: A unifying framework for reasoning. Artificial Intelligence, 113(1):41 85, 1999.
Rina Dechter and Irina Rish. Mini-buckets: A general scheme for bounded inference. J. ACM, 50(2):107-153, Mar 2003. ISSN 0004-5411.
Victor Garcia Satorras and Max Welling, Neural enhanced belief propagation on factor graphs. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial In- telligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 685 693. PMLR, 13-15 Apr 2021.
Laurent Ghaoui and Assane Gueye. A convex upper bound on the log-partition function for binary distri- butions. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou (eds.), Advances in Neurol Information Processing Systems, volume 21. Curran Associates, Inc., 2008
Leslic Ann Goldberg and Mark Jerrum. A complexity classification of spin systems with an external field. Pro- ceedings of the National Academy of Sciences, 112(43)::3161111316) 2015. doi: 10. /...0///s..... http//aaa..... 1505664112.
Vicenç Gómez, Hilberrt J. Kappen, and Michael Chertkov. Approximate inference on planar graphs using loop calculus and belief propagation. Journal of Machine Learning Research, 11442):1273-122) 1296, 2010.
Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the ising model. SIAM Comput., 22(5):1087 1116, oct 1993. ISSN 0097-5397.
Christian Knoll, Adrian Weller, and Franz Pernkopf. Self-guided belief propagation homotopy continu- ation method. IEF. Trans. Pollern Anal. Mach. Intell. 45(4):5139 5157, Apr 2023. ISSN 0162-8828.
15

---

Published in Transactions on Machine Learning Research (11/2024)
Daphne Koller and Nir Friedman. Probabilistic Graphical Models:
Principles and Techniques. Adaptive computation and machine learning. MIT Press, Cambridge, MA, USA, 2009.
Valerii Likhosherstor, Yury Maximov, and Misha Chertkov. Inference and sampling of kys-free ising models. Tn Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 3963-3972. PMLR, 09 15 Jun 2019.
Qiang Liu and Alexander Ihler. Bounding the partition function using hölder's inequality. In Proceedings of the 28th International Conference on International Conference on Machine Learning, ICML'11, pp. 849 849-856, Madison, WT, USA, 2011. Omnipress. ISBN 9781450306195.
Carlo Lucibello, Fabrizio Pittorino, Gabriele Perugini, and Riccardo Zecchina. Deep learning via message passing algorithms basod on belief propagation. Machine Learning: Science and Technology. 3(3):035005, Jul 2022.
Nicholas Ruozzi. The bethe partition function of log-supermodular graphical models. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), Advances in Newral Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Martin J. Wainwright, Stochastic processes on graphs with cycles: geometric and variational approaches. phd, Massachusetts Institute of Technology, USA, 2002. AA10804024.
Martin J. Wainwright and Michael I. Jordan. Graphical Models, Exponential Families, and Variational Inference. Foundations and Trendso in Machine Learning, 2008.
Martin Wainwright, Tommi Jaakkola, and Alan Willsky, Tree- based reparameterization for approximate inference on loopy graphs. In Advances in Neurol Information Processing Systems, volume 14. MIT Press, 2001.
Martin J. Wainwright, Tommi S. Jaakkola, and Alan S. Willsky, Tree-reweighted belief propagation algo- rithms and approximate MT. estimation by pseudo-moment matching. In In ATSTATS, 2003.
M.J. Wainwright and M.I. Jordan. Tog-determinant relaxation for approximate inference in discrete markov random fields. IEEE Transactions on Signal Processing, 54(6):2099 2109, 2006. doi: 10.1109/TSP:200. 874409.
M.J. Wainwright, T.S. Jaakkola, and A.S. Willsky. A new class of upper bounds the log partition function. IEEE Transactions on Information Theory, 51 (7):22331 2335, 2005.
D.J.A. Welsh. The Computational Complexity of. Some Classical Problems from. Statistical Physics. In Disorder in Physical Systems, pp- 307-321 OxfordUniiverittyPres 1991.
Wim Wiegerinck and Tom Heskes. Fractional Belief Propagation. In S. Becker, S. Thrun, and K. Obermayer (eds.), Advances in Neural Information Processing Systems, volume 15. MIT Press, 2002.
Alan Willsky, Erik Sudderth, and Martin J Wainwright. Loop series and bethe variational bounds in at- tractive graphical models. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2007.
Jonathan S Yedidia, William T Freeman, and Yair Weiss. Bethe free energy, Kikuchi approximations, and belief propagation algorithms. Advances in newral information processing syslems, 13, 2001.
J.S. Yedidia, W.T. Freeman, and Y. Weiss. Constructing Pree-Energy Approximations and Generalized Belief Propagation Algorithms. JEEE Tronsactions on Information Theory, 51(():2282-220 2312, 2005.
16

---

Published in Transactions on Machine Learning Research (11/2024)
A Fractional Variational Formulation: Details
A.1 Lagrangian Formulation
Introducing Lagrangian multipliers associated with the linear constraints in Eqs. following Lagrangian reformulation of Eq.
9
9
we arrive at the
F(A) = min max (B: 17 1)) [(A) = (B)+
(14)
B20 n.
Σ Σ (2a)
Σ 26
Bab(Za, 26) Balta))
+
Σ {a,b)E
Vab
1-
Σ Furtth
Bab(Ea: (z))
AE V:Vbb Re
where (B: 77 bb) the (extended) Lagrangian dependent on both the primary variables (belicfs, B) and the newly introduced dual variables, 7 (o E R|Vaa V, vb ~ a, Vx, = =1) and up (va E R Va V). The stationary point of the Lagrangian 14 assuming that it is unique, is defined by the following system of equations
(B)
Vfa,b) E, Vz,, 26 = #1:
=0 + (b6,
(15)
SBab ( (b))
(log (B/d) (Rar +1) -100 + mo-0 (#a) ) + (o0)( = 0.
Pab
( 0
Va E V, Vr, =1
SB.
Σ
Pab
(A)
((a + + Σ (xa) 0, -1
(16)
howa
bwaa.
augmented with Eqs. 9p). Eqs. 15 and Eqs.
16 result in the following expressions for the marginals
in terms of the Lagrangian multipliers
Σ (A)
Mo (Fa)
Va V, Vr, #1: (x)) exp
bwaa
(17)
Σ bnve
(2) Pab
Eas(Ear I6)
+m +m)
(2)
(ma)) m
Via, b) E, Vr,, =l: B(2) (xay xxxx
(18)
(A)
Pab
Here in Eqs. 15 16 17 18
and below, the upper index (A) B(A), (A and ((A) variables indicates that the respective variables optimal, i.e. argmax and argmin, over respective optimizations in Eq. 114.
17

---

Published in Transactions on Machine Learning Research (11/2024)
A.2 Message Passing
We may also rewrite Eqs. 17 18 in terms of the so-called message (from node node) variables. Then the marginal beliefs are expressed via the ((A) -msssggs according to
Th mh- (FO)
(A)
Va E,V, V. Ab ~a a:: Pooa (Io) = exp
(A)
(19)
Σ Pab
Mo (vaa
(A)
VaEV, V. Vr, = =1; Bi
(20)
Σ II
1 b- (x'a)
x'a bwa
V(a,b) E E, Vo vb = +1 BaA) (Ia, 1bb)
(21)
Σ
(2 -1
Σ
(A)
cnub
exp
Futlltgitto) Pab
(Jaa
Fab
1 (16)
(2)
"ab
[(A]
Σ (2)
Σ (A)_1
Down
Eutla' wa'e)
(nl (a'a)
(p (m
(2)
Σ exp a'a
Pab
and the Fractional Belief Propagation (FBP) equations, expressing relations between pairwise and singleton marginals become:
Va V, vb a, Vaa +1: (xa) x II (A) (Fa)
(22)
bna
Σ -
Σ EN
Eub( 260 ) (mbiba (2roo) Pab
x
Σ exp
Pab
( (2s))
(A)
Pab
Σ
Blai ab (Ia,
Note (on a tangent), that the p (A) (messsas) variables introduced here are related but not equivalent to the messsssss which can also be used in the BP-literature, see e.g. Section 4.1.3 of (Wainwright & Jordan 2008). Specifically in the case of BP, i.e. when Pab is follows, (1 (xa))da-1= Iovaaccs M(A)a(xo))
(A) = 1, relation between ((() and M variables
B Proof of Theorem 3.1
Let evaluate the derivative of the fractional free energy
over À explicitly
OF(2) (B(A)
dBL (Ia. 26)
((A)
(B(A)) = Σ F()
dx
d)
( (Izz
dA
(0,b) Fa.
aF(A) (B(A)) dBB( (xEa)
(H(A)
dp
(2)
aB(2) (IOO)
(p(2)
dA
22
{a.b}
18

---

Published in Transactions on Machine Learning Research (11/2024)
Taking into account the conditions of stationarity of the fractional free energy, tracking explicit dependencies of the fractional entropy on Pab and thus on X, we arrive at
(A)
OF(A) (B(A))
a (B(A)) 0:
6]
0; Va
aB (Fa: 2bb
aB
21) (Ia)
(B(A)
Σ
BlN ( Lb) log ((d) (Fa; vbb +
Σ
B (Ia log ( (3a)
0p
#a-b==11
+ B (xx) log Bi (xt) = ab
-
2
where the newly introduced ((2) is nothing but the pairwise mutual information defined according to BiA).
ah
Notice that I (A)
ab 2 Since, according to the theorem's assumption (xA) differentiable in x; dp /dA Pab 2 O, and then summarizing all of the above we derive
- 00
F(A)
(23)
{a.b}
thus concluding the proof of both continuity (the derivative is bounded) and monotonicity (the derivative is negative).
C Proof of Theorem 4.1
Consistently with Eq. 15. Eqs. 21 21
allow us to rewrite the joint probability distribution in terms of the
optimal beliefs which solve the fractional Eqg.
22
Σ
Σ (A)
(A)
p(x)=2-1 fa,btEE
II
Σ exp sa
Fras mb)) (2)
ong
(2)
Bmcb
(2)
Pab
x
Pab
(())
(B(a) (Ia, (b))
1- E-Σ p(A)
II NEV
ΣI (A) Po (Ia)
oova
{a.bEEg
(24)
E (())
B
(Ma))
cmc
NEV
Normalization condition requires the sum on the right hand side of Eq. 24 to return 1, results in the desired statement, i.c. Eqs.
11 12
D More Figures from Numerical Experiments
Fig. 5 mentioned in Section 5.4 shows X, for a number of instances drawn from the respective ensembles of the Ising model (over planar and complete graphs). We observe that in the planar case, X. E [0.75, 0.95]. while in the case of the complete graph, X, [0.05, 0.15].
Fig. mentioned in Section 5.6 shows results for the mixed case when the pair-wise interaction can vary in sign from edge to edge. In this mixed case, as seen in the presented examples, we can not guarantee that BP provides a lower bound on the partition function, and thus X, may or may be identified within the [0, 1] interval.
19

---

Published in Transactions on Machine Learning Research (11/2024)
30
70
29
69
28
68
log 7
N 27
67
10
26
66
25
65
20.0
64
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
A
A
(a)
(b)
Figure 5: ((A) vs À for number of instances (shown in different colors) drawn for the Ising model ensembles over, (a) 3 x 3 grid, and (b) K2 graph, where elements of J and h are iidd from u((0, 1). Circles mark respective exact values, A..
60.5
47.0
46.5
60.0
100) ((2)
log Z (M)
46.0
59.5
45.5
59.0
45.0
58.5
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
(a)
(b)
Figure 6: Two different random instance of 4 x 4 Isisng Model with (a) J ~ 1) and h ~ u(-1,1) (b)
J J~ h = Dashed line shows exact value of partition functions for the corresponding curve.
20


Reviews:
[{"review_id": "pyMKACqwet", "reviewer": "Reviewer_Nu2b", "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": "I think that the proposal of extending the Bethe and TRW approximations\nis itself not novel (see [C1] below) but interesting, although one should note \nthat there are several errors and flaws even in the theoretical part\nof this paper (see [C3], [C6], [C7], [C9]-[C11]).\nI do not precisely understand the proposed algorithm for evaluating $Z$,\nbecause of the unclear description in this paper (see [C4]),\nbut if my understanding is appropriate,\nthen one can question the efficiency of the algorithm (see [C5]).\nOne can furthermore raise several criticisms on\nthe experimental part of this paper (see [C12]-[C16]).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 paper proposes a one-parameter extension,\nwith parameter $\\lambda\\in[0,1]$, of the Bethe \nand the tree reweighted (TRW) approximations\nof the free energy,\ncontaining the latter two as special cases ($\\lambda=1$ and 0, respectively).\nThe extension of the Bethe free energy,\nwhich is called the fractional free energy\nand denoted by $\\bar{F}^{(\\lambda)}(\\mathcal{B})$\nwith a test pseudomarginal $\\mathcal{B}$, \nis formulated in equations (11)-(14),\nand the corresponding extension of the belief propagation (BP) algorithm,\nwhich is called the fractional belief propagation, \nis derived as equation (26) in Appendix A.2,\nvia the Lagrangian formulation in Appendix A.1.\nAs theoretical contributions,\nthis paper claims to have proven continuity and monotonicity (Theorem 3.1),\nas well as concavity (Theorem 3.2), \nof the (optimized) fractional free energy\n$\\bar{F}^{(\\lambda)}:=\\min_{\\mathcal{B}}\\bar{F}^{(\\lambda)}(\\mathcal{B})$\nas a function of the parameter $\\lambda$.\nIt also claims to have shown that the reparametrization properties\nof the Bethe approximation (namely, the fact that the original distribution is\nrepresented, or ``reparametrized,'' in terms of any fixed point\nof the Bethe free energy, see Proposition 4.3 in Wainwright and Jordan (2007))\nalso holds for their extension (Theorem 4.1).\n\nAs a possible application of their extension,\nthe authors consider the problem of estimating the partition function $Z$\nof Ising models with ``attractive'' two-spin interactions (i.e.,\nall the interactions $J_{ab}$ are nonnegative),\non the basis of the known observations, summarized in Lemma 3.3, \nthat the TRW estimate $Z^{(0)}$ and the BP estimate $Z^{(1)}$ \nsatisfy $Z^{(0)}\\ge Z$ and $Z^{(1)}\\le Z$, respectively, \nthe latter of which has been proven to hold in Ruozzi (2012)\nonly for attractive Ising models.\nAlthough the proposed algorithm for approximately evaluating $Z$ (Algorithm 1),\ncalled the fractional message passing algorithm,\nis not described clearly enough,\nresults of numerical experiments seem to suggest validity\nof the theoretical development in this paper.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "All the comments listed in \"Strengths and weaknesses\" above are critical to securing my recommendation for acceptance.\n\n### [C1] Novelty\nThe proposed formulation of the fractional free energy\n(equations (11)-(14)) is not entirely new:\nThe same form of an approximate free energy has been studied in\nWainwright, Jaakkola, and Willsky (2005) (see equation (25)) \nand Wainwright and Jordan (2008) (see, e.g., Theorem 7.2)\nunder the TRW rules, \nas well as in Wiegerinck and Heskes (2003) (see equation (14))\nwhere $\\{\\rho_{ab}\\}$ are no longer assumed to follow the TRW rules.\nThe proposed formulation in this paper\nis therefore regarded as a one-parameter subclass of\nthose general formulations, the former being defined by linearly interpolating\n$\\{\\rho_{ab}\\}$ satisfying the TRW rules and $\\rho_{ab}=1$ which\ncorresponds to the Bethe free energy.\nThe associated belief propagation formulae and/or\nfixed-point equations have been derived there as well.\nThese facts, as well as the relationship between\nthese arguments and those in this paper,\nhave not been stated clearly in this paper.\n\n### [C2] Further possible extension\nIn view of the argument given in [C1],\none might be able to consider the following further extension.\nLet $\\rho:=\\\\\\{\\rho_{ab}\\in[0,1]\\\\\\}$ be completely tunable parameters,\nas in Wiegerinck and Heskes (2003), \nand define $\\bar{F}^{(\\rho)}$ and $F^{(\\rho)}(\\mathcal{B})$\nanalogously as in equations (11)-(14).\nThis setting corresponds to the TRW if $\\rho$ satisfies\nthe TRW rules, to the BP if $\\rho_{ab}=1$ for all $(a,b)\\in\\mathcal{E}$,\nand to what is called the naive mean field if $\\rho=\\mathbf{0}$.\nThis extension should be feasible beyond the Ising models. \nFurthermore, the following extended theorems might be expected to hold,\nif the arguments in this paper be valid: \n\n**Theorem R3.1:**\n$\\partial\\bar{F}^{(\\rho)}/\\partial\\rho_{ab}=-I_{ab}^{(\\rho)}\\le 0$,\nprovided that the required differentiability is satisfied\n(see, however, [C3] below).\n\n**Theorem R3.2:**\n$\\bar{F}^{(\\rho)}$ is concave in $\\rho$\n(see also [C8]).\n\n**Theorem R4.1:**\nThe reparametrization properties hold\nfor any fixed point of the fractional belief propagation algorithm. \n\nTheorems 3.1, 3.2, and 4.1 will then be obtained\nas corollaries of these theorems,\nby restricting $\\rho$ to be on a line segment connecting\na TRW weight (i.e., $\\exists\\mathcal{T};\\rho_{ab}=\\sum_{T\\in\\mathcal{T},(a,b)\\in T}\\rho_T,\\sum_{T\\in\\mathcal{T}}\\rho_T=1$) \nand the BP weight (i.e., $\\rho_{ab}=1$ for all $(a,b)\\in\\mathcal{E}$). \n\n### [C3] Validity of Theorem 3.1 and Lemma 3.3\nOne may alternatively raise a question about the validity\nof Theorem 3.1 in this paper. \nFirst of all, one can regard that Theorem 3.1\nis a restatement of Lemma 2 in Wainwright, Jaakkola, and Willsky (2005)\n(note that the proof of Lemma 2 does not rely directly on\nthe assumption that $\\rho$ satisfies the TRW rules):\nOne can then find in the latter that the existence and uniqueness\nof $\\mathcal{B}^{(\\lambda)}$ play an important role\nin guaranteeing the required differentiability,\nand that the required existence and uniqueness are ensured by the tree subgraph\nassumption. \nIf one brings the argument in the latter to that in this paper, however,\none may question the required differentiability\nsince it is known that the uniqueness of $\\mathcal{B}^{(\\lambda)}$\ndoes not hold in general (consider the BP case $\\lambda=1$ as an example),\nwhich may cause violation of the differentiability\nof $\\mathcal{B}^{(\\lambda)}$ with respect to $\\lambda$\nat some values of $\\lambda$. \nOne can consequently raise the following criticism:\nHow can one guarantee the differentiability\nrequired for the manipulation done in Appendix B to prove Theorem 3.1\nto be valid, without the existence and uniqueness assumptions on $\\mathcal{B}^{(\\lambda)}$?\nA more detailed proof which takes this point into account\nwould be appreciated.\nAs the proof of Lemma 3.3 relies on the intermediate value theorem,\nwhich requires continuity of $Z^{(\\lambda)}$ on $\\lambda\\in[0,1]$,\nthe above point should also affect the validity of Lemma 3.3. \n\n### [C4] Fractional message passing algorithm\nI do not understand several aspects of\nthe proposed fractional message passing algorithm (Algorithm 1):\n- Line 2 in the For block:\n  The authors write \"Use TRW-BP\", but what is TRW-BP?\n  Although it is not explained explicitly in this paper at all,\n  my guess is that it is nothing other than the fractional belief propagation\n  algorithm described in equation (26), but then why do the authors\n  use the different names?\n- Line 1 in the End block:\n  The authors write \"Find $\\lambda_*$ where $\\mathcal{Z}^{(\\lambda)}=1$\", \n  but how? According to Algorithm 1, one estimates the values of\n  $\\mathcal{Z}^{(\\lambda)}$ via random sampling\n  for 21 equispaced values of $\\lambda$ from $\\lambda=0.01$ to $\\lambda=1$.\n  Among the resulting 21 estimates $\\{Z^{(\\lambda=0.01)},\\ldots,Z^{(\\lambda=1)}\\}$,\n  it is quite unlikely that there exists a value of $\\lambda$ with\n  which the value of $\\mathcal{Z}^{(\\lambda)}$ is estimated\n  to be exactly 1.\n  One should also take care of the statistical fluctuations\n  of these estimates arising from the random sampling. \n\n### [C5] Possible alternatives\nSince the proposed fractional message passing algorithm\ninvolves random sampling in evaluating $\\mathcal{Z}^{(\\lambda)}$,\none might think about sevaral alternative approaches\nwhich make use of similar random sampling schemes.\nFor example: \n- **Direct sampling:**\n  Let $q(x)$ be a tractable probability distribution\n  on $\\\\\\{-1,1\\\\\\}^N$, and approximate $Z$ as\n  \\begin{equation}\n    Z=\\sum_{x\\in\\{-1,1\\}^N}q(x)\\frac{\\exp(-E(x))}{q(x)}\n      \\approx\\frac{1}{M}\n      \\sum_{i=1}^M\\frac{\\exp(-E(x_i))}{q(x_i)},\n  \\end{equation}\n  where $\\\\\\{x_1,x_2,\\ldots\\\\\\}$ is a sequence of random samples\n  drawn from the distribution $q$.\n  If $q$ is simple enough, then one can use iid sampling.\n  One may alternatively use Markov-Chain Monte-Carlo (MCMC) sampling \n  when $q$ is not simple but has a structure suitable for MCMC sampling. \n  The computational complexity of the above scheme\n  is at most the same as that of evaluating $\\mathcal{Z}^{(\\lambda)}$\n  in the proposed algorithm. \n- **TRW+Sampling:**\n  Perform TRW to obtain $\\mathcal{B}^{(0)}$ and $Z^{(0)}$,\n  and then evaluate $\\mathcal{Z}^{(0)}$\n  via the same random sampling procedure as that of the proposed algorithm.\n  Return $Z^{(0)}\\mathcal{Z}^{(0)}$ as an estimate of $Z$.\n  An obvious advantage of this approach is\n  that the TRW is guaranteed to converge in finite time\n  and yields a unique solution. \n- **BP+Sampling:**\n  Perform BP to obtain $\\mathcal{B}^{(1)}$ and $Z^{(1)}$,\n  and then evaluate $\\mathcal{Z}^{(1)}$ \n  via the same random sampling procedure as that of the proposed algorithm.\n  Return $Z^{(1)}\\mathcal{Z}^{(1)}$ as an estimate of $Z$.\n- **FBP+Sampling:**\n  Choose a value of $\\lambda\\in[0,1]$ according to\n  some criterion. \n  Perform fractional belief propagation with the chosen value of $\\lambda$ \n  to obtain $\\mathcal{B}^{(\\lambda)}$ and $Z^{(\\lambda)}$,\n  and then evaluate $\\mathcal{Z}^{(\\lambda)}$ \n  via the same random sampling procedure as that of the proposed algorithm.\n  Return $Z^{(\\lambda)}\\mathcal{Z}^{(\\lambda)}$ as an estimate of $Z$.\n  This reduces to TRW+Sampling and BP+Sampling\n  if one lets $\\lambda=0$ and 1, respectively. \n\nAn apparent disadvantage of the proposed fractional message passing\nalgorithm (Algorithm 1) compared with the above competitors\nis that the proposed algorithm requires several runs\nof fractional belief propagation with several different values of $\\lambda$,\nwhich makes the computational complexity larger.\nIn order for the proposed algorithm to be significant,\none would have to demonstrate its superiority\ncompared with competitors such as those listed above. \nIt would be nice if the proposed algorithm\ngives good results compared with those competitors,\nwith a similar amount of computational resources.\n\nI am also concerned about absence of results which directly show\nhow good the estimates of the partition function $Z$\nwith the proposed approach were. \n\n### [C6] Equation (5)\nEquation (5) seems incorrect. \nConsider the KL divergence $D(\\mathcal{B}\\|p(x|J,h))$ \nof a test distribution $\\mathcal{B}(x)$\nfrom the true distribution $p(x|J,h)$:\n\\begin{equation}\n  D(\\mathcal{B}\\|p(x|J,h))\n  =\\sum_{x}\\mathcal{B}(x)\n  \\log\\frac{\\mathcal{B}(x)}{p(x|J,h)}\n  =\\sum_{x}\\mathcal{B}(x)\\log\\mathcal{B}(x)\n  +\\sum_{x}\\mathcal{B}(x)E(x)+\\log Z,\n\\end{equation}\nwhere $Z=Z(J,h)$ is the partition function\nof the true distribution as defined in equation (2). \nOne then has \n\\begin{equation}\n  D(\\mathcal{B}\\|p(x|J,h))-\\log Z\n  =\\sum_{x}(E(x)\\mathcal{B}(x)\n  +\\mathcal{B}(x)\\log\\mathcal{B}(x)),\n\\end{equation}\nand thus, noting the nonnegativity of the KL divergence, \n\\begin{equation}\n  F:=-\\log Z\n  =\\sum_{x}(E(x)\\mathcal{B}(x)\n  +\\mathcal{B}(x)\\log\\mathcal{B}(x))\n  -D(\\mathcal{B}\\|p(x|J,h))\n  =\\min_{\\mathcal{B}(x)}\n  \\sum_{x}(E(x)\\mathcal{B}(x)\n  \\mathrel{\\color{red}+}\\mathcal{B}(x)\\log\\mathcal{B}(x)),\n\\end{equation}\nwhere the minimum with respect to $\\mathcal{B}(x)$\nis achieved at $\\mathcal{B}(x)=p(x|J,h)$.\nThe sign just before the term $\\mathcal{B}(x)\\log\\mathcal{B}(x)$\nis not the minus $-$ as in equation (5)\nbut the plus $+$ as shown above.\n\nThe authors also wrote just above equation (5) that\nthey consider the Kullback-Leibler distance between\n$\\exp(-E(x;J,h))$ and $\\mathcal{B}(x)$.\nAlthough $\\mathcal{B}(x)$ is a proper probability distribution,\n$\\exp(-E(x;J,h))$ is not in general,\nso that one cannot consider the Kullback-Leibler divergence\nwith it. \n\n### [C7] Derivation of fractional free energy\nSubstituting equation (8) into equation (5) does not yield equations (11)-(14).\nIt is obvious from the fact that\n$\\mathcal{B}(x)$ as defined in equation (8)\nis not in general a proper probability distribution,\nas mentioned by the authors themselves in page 5, lines 3--4.\nAlso, the argument $\\mathcal{B}$ of $F^{(\\lambda)}$ defined in equation (11)\nis not the function $\\mathcal{B}(x)$ defined in equation (8)\nbut the collection of single- and two-body marginals $\\\\\\{ℬ_a(x_a)\\\\\\}$\nand $\\\\\\{ℬ_{ab}(x_a,x_b)\\\\\\}$.\nIt is therefore appropriate to define $\\mathcal{B}$ not as in equation (8)\nbut rather as a pseudomarginal\n$ℬ=\\\\\\{ℬ_a(x_a),ℬ_{ab}(x_a,x_b)\\\\\\}$\nas discussed by, e.g., Wainwright's papers.\nAt least one has to distinguish the test distribution $\\mathcal{B}(x)$\nin Section 2.2, which is a proper probability distribution,\nand the pseudomarginal $\\mathcal{B}$ in Section 2.3.\n(Note: I occasionally used ℬ in place of $\\mathcal{B}$ in the above, in order to avoid MarkDown formatting problems.)\n\nThere is notational inconsistency:\n- Later the authors\nuse the expression $\\mathcal{B}^{(\\lambda)}$ to denote\nthe pseudomarginal optimizing $\\bar{F}^{(\\lambda)}(\\mathcal{B})$,\nas mentioned in page 13, lines 19--20, \nthat is, $\\mathcal{B}^{(\\lambda)}:=\\min\\bar{F}^{(\\lambda)}(\\mathcal{B})$,\nwhereas in equation (8) they use the same expression to denote\na generic pseudomarginal,\nirrespectively of being optimized or not.\n- An edge is represented in two different ways: $(a,b)$ and $\\\\\\{a,b\\\\\\}$.\n  The same notation should be used throughout the paper. \n\n### [C8] Theorem 3.2\nSince the proof is straightforward, I think it better\nto write it down much more concretely, as:\n> As $\\rho_{ab}^{(\\lambda)}$ is linear in $\\lambda$,\nfrom Eq. (13) $H^{(\\lambda)}(\\mathcal{B})$ is also linear in $\\lambda$,\nso that one has, for any $\\lambda,\\lambda_0,\\lambda_1$ with \n$\\lambda_0<\\lambda_1$, \n\\begin{equation}\n  H^{(\\lambda)}(\\mathcal{B})\n  =\\frac{\\lambda_1-\\lambda}{\\lambda_1-\\lambda_0}H^{(\\lambda_0)}(\\mathcal{B})\n    +\\frac{\\lambda-\\lambda_0}{\\lambda_1-\\lambda_0}H^{(\\lambda_1)}(\\mathcal{B}),\n\\end{equation}\nand therefore\n\\begin{equation}\n  F^{(\\lambda)}(\\mathcal{B})\n  =\\frac{\\lambda_1-\\lambda}{\\lambda_1-\\lambda_0}F^{(\\lambda_0)}(\\mathcal{B})\n    +\\frac{\\lambda-\\lambda_0}{\\lambda_1-\\lambda_0}F^{(\\lambda_1)}(\\mathcal{B}).\n\\end{equation}\nOne consequently has\n\\begin{equation}\n  \\bar{F}^{(\\lambda)}\n  =F^{(\\lambda)}(\\mathcal{B}^{(\\lambda)})\n  =\\frac{\\lambda_1-\\lambda}{\\lambda_1-\\lambda_0}\n  F^{(\\lambda_0)}(\\mathcal{B}^{(\\lambda)})\n  +\\frac{\\lambda-\\lambda_0}{\\lambda_1-\\lambda_0}\n  F^{(\\lambda_1)}(\\mathcal{B}^{(\\lambda)})\n  \\ge\\frac{\\lambda_1-\\lambda}{\\lambda_1-\\lambda_0}\n  F^{(\\lambda_0)}(\\mathcal{B}^{(\\lambda_0)})\n  +\\frac{\\lambda-\\lambda_0}{\\lambda_1-\\lambda_0}\n  F^{(\\lambda_1)}(\\mathcal{B}^{(\\lambda_1)})\n  =\\frac{\\lambda_1-\\lambda}{\\lambda_1-\\lambda_0}\n  \\bar{F}^{(\\lambda_0)}\n  +\\frac{\\lambda-\\lambda_0}{\\lambda_1-\\lambda_0}\n  \\bar{F}^{(\\lambda_1)},\n\\end{equation}\nwhere at the inequality sign we used the fact\n$F^{(\\lambda)}(\\mathcal{B}^{(\\lambda)})\n=\\min_{\\mathcal{B}}F^{(\\lambda)}(\\mathcal{B})\\le F^{(\\lambda)}(\\mathcal{B}^{(\\lambda')})$. \nIt proves the concavity of $\\bar{F}^{(\\lambda)}$ in $\\lambda$.\n\n### [C9] Lemma 3.3\nHow the attractiveness condition is used is not clear.\nI guess that the condition is used in Ruozzi (2012) to\nprove $Z^{(1)}\\le Z$, which should be explicitly stated. \n\n### [C10] Theorem 4.1\nIt should be mentioned that Theorem 4.1 is an extension\nof the known result of the reparametrization properties\nof Bethe approximation (e.g. Proposition 4.3 of Wainwright and Jordan, 2007).\n\nI think that equation (28) in Appendix C containing the proof\nof Theorem 4.1 has the following error: The factor\n\\begin{equation}\n  \\prod_{a\\in\\mathcal{V}}\\left(\\sum_{x_a}\\prod_{b\\sim a}\\mu_{b\\to a}^{(\\lambda)}(x_a)\n  \\right)^{\\sum_{c\\sim a}\\rho_{ac}^{(\\lambda)}-1}\n\\end{equation}\nappearing on the right-hand side should be \n\\begin{equation}\n  \\prod_{a\\in\\mathcal{V}}\\left(\\sum_{x_a}\\prod_{b\\sim a}\\mu_{b\\to a}^{(\\lambda)}(x_a)\n  \\right)^{\\color{red}1-\\sum_{c\\sim a}\\rho_{ac}^{(\\lambda)}}.\n\\end{equation}\n\n### [C11] Lemma 5.1\nI think that the proof of Lemma 5.1 in Appendix D is \nseverely flawed in several respects.\nAs demonstrated by the example shown in Figure 3,\nthe authors first consider the $N$-node complete graph $K_N$,\nand initialize $\\mathcal{T}$ as the set of all linear spanning trees\nof $K_N$.\nSince any permutation $(\\sigma(1),\\sigma(2),\\ldots,\\sigma(N))$\nof $(1,2,\\ldots,N)$ corresponds to a linear spanning tree of $K_N$,\nand since each linear spanning tree of $K_N$ corresponds to\ntwo such permutations $(\\sigma(1),\\sigma(2),\\ldots,\\sigma(N))$\nand $(\\sigma(N),\\sigma(N-1),\\ldots,\\sigma(1))$,\nthe total number $|\\mathcal{T}|$ of the linear spanning trees\nof $K_N$ is $N!/2$.\nFor $N=4$, it is equal to 12 (see a separate [figure](https://figshare.com/s/ae3c257ed285496a5946),\nwhich shows all the linear spanning trees of $K_4$: the left six drawn in black are in Figure 3 (a), \nwhereas the right six drawn in red are absent).\nOn the other hand, in Figure 3 (a) only six of them are shown,\nso that it would be inappropriate as an illustration of Algorithm 2.\nFurthermore, the edge counts in those six spanning trees\nare not uniform across the six edges of $K_4$:\nAlthough two edges have edge counts of 3,\ntwo others have 2, and the remaining two have 4.\nIt is inconsistent with the description in the figure caption,\nas they do not yield $\\rho$ satisfying the edge-uniform rule. \nIf instead one considers all the 12 linear spanning trees\nshown in the figure,\nthen the edge counts are 6 for all the six edges of $K_4$. \n\nAlso, the figure caption itself contains several errors:\n$|V|$ should read $|{\\color{red}\\mathcal{V}}|$.\nThe formula $\\rho_{ab}=|\\mathcal{V}|-1/|\\mathcal{E}|$ should read\n$\\rho_{ab}={\\color{red}(}|\\mathcal{V}|-1{\\color{red})}/|\\mathcal{E}|$.\n(b) $|V|=5$ should be $|{\\color{red}\\mathcal{V}}|={\\color{red}4}$.\n\nIn line 2 of Algorithm 2,\nthe authors let $\\rho_T=1/|\\mathcal{E}|$.\nThis assertion is in general invalid, as it may violate the TRW rules:\n\\begin{equation}\n  \\sum_{T\\in\\mathcal{T}}\\rho_T\n  =\\sum_{T\\in\\mathcal{T}}\\frac{1}{|\\mathcal{E}|}\n  =\\frac{|\\mathcal{T}|}{|\\mathcal{E}|}\n  \\stackrel{?}{=}1.\n\\end{equation}\nTake $\\mathcal{G}=K_{|\\mathcal{V}|}$ as an example.\nIn view of the argument shown above, one has $|\\mathcal{T}|=|\\mathcal{V}|!/2$,\nwhereas the total number of edges in $K_{|\\mathcal{V}|}$ is given by \n$|\\mathcal{E}|=|\\mathcal{V}|(|\\mathcal{V}|-1)/2$.\nThey are equal only when $|\\mathcal{V}|=2$ or $|\\mathcal{V}|=3$.\nIn general, one should let $\\rho_T={\\color{red}1/|\\mathcal{T}|}$. \n\nI think that the most serious problem with the proof of Lemma 5.1\nis that it is not clear at all whether the procedure described\nin Algorithm 2 is always feasible: For example, in line 6,\none has to \"modify $\\mathcal{T}$ by adding an extra edge to each spanning tree of $\\mathcal{T}$'' in such a way that one ``guarantees that each edge enters\nexactly $N-1$ resulting spanning trees.\"\nThere would be several possibilities of adding an edge,\nsome of which might result in the same spanning tree already in $\\mathcal{T}$.\nI do not understand either why the authors can guarantee\n\"that each edge enters exactly $N-1$ resulting spanning trees,\"\nas they did not provide any concrete proof for that.\n\nI even think that Algorithm 2 *cannot* guarantee existence\nof a subset of spanning trees with the desired properties,\nas opposed to the authors' claim.\nConsider a graph $\\mathcal{G}=(\\mathcal{V},\\mathcal{E})$,\nwhere $\\mathcal{E}$ is equal to the edge set of\nthe complete graph $K_{|\\mathcal{V}|}$ *minus*\nthe single edge $(N-1,N)$, where $N=|\\mathcal{V}|$.\nRecalling that the number of linear spanning trees of $K_N$ is $N!/2$,\nafter removing from $\\mathcal{T}$ one linear spanning tree which becomes\ndisconnected by the edge removal, and then adding an extra edge\nto each of the remaining linear spanning trees which have become\ndisconnected by the edge removal,\nthe total number of spanning trees in $\\mathcal{T}$\nshould be $N!/2-1$, each with $(N-1)$ edges. \nIt implies that now $\\mathcal{T}$ contains\n$(N-1)(N!/2-1)$ edges in total.\nIn order to achieve the edge-uniform rule\n(i.e., $\\rho_{ab}$ are independent of edge $(a,b)$)\nwith equal-weight trees, \nthese edges should be distributed equally to\nthe $|\\mathcal{E}|=N(N-1)/2-1$ edges of $\\mathcal{G}$,\nresulting in the average edge count of\n\\begin{equation}\n  \\frac{(N-1)(N!/2-1)}{N(N-1)/2-1}\n  =\\frac{(N-1)(N!-2)}{(N+1)(N-2)}\\quad (*)\n\\end{equation}\nper edge.\nIn order for Lemma 5.1 to be valid,\nthis quantity should be an integer.\nAs shown in the following table, however, \nthis quantity can be non-integer. (I numerically confirmed that\nthis quantity is non-integer for all $N\\in\\{4,5,\\ldots,10000\\}$.)\nThis fact demonstrates that Algorithm 2 does not work as expected,\ntherefore disproving Lemma 5.1.\n\n|$N$|$3$|$4$|$5$|$6$|$7$|\n|----|----|----|----|----|----|\n|average edge count (*)|2|$\\frac{33}{5}$ | $\\frac{236}{9}$ | $\\frac{1795}{14}$ | $\\frac{7557}{10}$ |\n\n### [C12] Graphs of $\\log Z^{(\\lambda)}$\nIn figure 1 (a), the third black marker\nfor the value of $\\log Z^{(\\lambda)}$ seems to be violating\nthe concavity of $\\log Z^{(\\lambda)}$ in $\\lambda$\nassured by Theorem 3.2,\nas it seems to be slightly above the line segment\nconnecting the two adjacent markers,\nas can be confirmed by magnifying the figure and applying a ruler.\nThe same applies to figure 4 (a), figure 5 (a) and figure 7 (a) as well.\n\n### [C13] Section 5.2\nThe claim that dependence of $\\bar{F}^{(\\lambda)}$ and $\\log Z^{(\\lambda)}$\non $\\lambda$ is \"of a phase transition type\" is inappropriate.\nAlthough I know that in some engineering papers the term \"phase transition\"\nis used to merely refer to a rather rapid change of something,\na common convention in statistical mechanics is such that\nthere should be a definite phase-transition point\nwhere a certain symmetry of the system changes\nand/or thermodynamical functions, such as the free energy,\nexhibit anomaly/singularity, in the thermodynamic limit.\nI could not find any clue for such anomaly in Figures 4-7.\nOne should not use the term \"phase transition\"\nwhen what one observes is merely a rapid change.\n\n### [C14] Section 5.3\nI do not understand what the authors mean\nby the claim \"if two or more of empirical estimates\nof $Z^{(\\lambda)}\\mathcal{Z}^{(\\lambda)}$ at different $\\lambda$ are\nsufficiently close to each other we can use them to bound $Z$\nfrom above and below.\"\nAs Theorem 4.1 states, $Z^{(\\lambda)}\\mathcal{Z}^{(\\lambda)}$\nshould be equal to $Z$ irrespectively of the value of $\\lambda$,\nfor $\\lambda_1\\not=\\lambda_2$ one ideally has \n$Z^{(\\lambda_1)}\\mathcal{Z}^{(\\lambda_1)}=Z^{(\\lambda_2)}\\mathcal{Z}^{(\\lambda_2)}=Z$.\nThus, if $Z^{(\\lambda_1)}\\mathcal{Z}^{(\\lambda_1)}$\nand $Z^{(\\lambda_2)}\\mathcal{Z}^{(\\lambda_2)}$ are sufficiently close\nto each other, it might only imply that our optimization\nof $\\mathcal{B}$ and numerical estimation of $\\mathcal{Z}^{(\\lambda)}$\nare going well.\nHow can one obtain the claimed bounds of $Z$?\n\n### [C15] Section 5.4\nI think that the concentration claim here \"the width of the probability\ndistribution of $\\lambda_*$ within the ensemble scales as $\\propto1/\\sqrt{N}$\"\nlacks empirical justification.\nIn Figure 2, only four instances are compared,\nand if one compares Figure 2 (b) $20\\times20$ and (c) $30\\times30$\nor (d) $40\\times40$,\none can observe that (b) exhibits stronger concentration of $\\lambda_*$\n(shown by hollow markers) \nthan (c) or (d), which is in conflict with the authors' concentration claim. \n\n### [C16] Section 5.5\nThe proposal of the sampling-based\nevaluation of $\\mathcal{Z}^{(\\lambda)}$ was experimented,\nand the results were shown in Figure 9 in Appendix E.\nThey have the following problems:\n- Since the results are obtained from random sampling,\n  they should have statistical fluctuations.\n  Error bars should then be shown to demonstrate\n  how large the fluctuations are. \n- Figure 9 (a) shows the results\n  for the model on the $3\\times 3$ grids.\n  As the model contains $3\\times 3$ binary variables,\n  the direct calculation of the partition function $Z$\n  will only require $2^{3\\times 3}=512$ evaluations\n  of the Boltzmann factor and summation of them.\n  Therefore, in this particular setting one should say that\n  the proposed method is far less efficient than the direct evaluation of $Z$. \n- For the setting in Figure 9 (b), direct calculation \n  of $Z$ would require $2^{36}\\sim 6.9\\times 10^{10}$,\n  so that the proposed method might seem efficient in terms of\n  the number of samples needed. One could however argue that\n  alternative sampling-based approaches, such as those\n  mentioned in [C5], can be exploited in estimating the partition function $Z$.\n  Comparison of the proposed method with such naive approaches\n  is needed in order to demonstrate efficiency of the proposal. \n- As in [C15], the authors' claim \"number of samples needed for\n  convergence scales as $\\mathcal{O}(N^{[2::4]})$\" lacks justification.\n  In Figure 9 in Appendix E, the authors show how\n  the sampling-based estimates of $\\mathcal{Z}^{(\\lambda)}$ behave\n  as the number $M$ of samples changes.\n  They only experimented two cases, $N=3$ and $6$.\n  One cannot figure out how the \"sufficient number of samples,\"\n  denoted by $M_c$, behaves as a function of $N$\n  on the basis of the results of only two values of $N$.\n  Indeed, the following formulas reproduce\n  the values of $M_c(N)$ at $N=3,6$, and yet\n  they exhibit different dependence on $N$:\n  The former is polynomial in $N$ since $M_c(N)=\\mathcal{O}(N^\\alpha)$,\n  whereas the latter is exponential in $N$ since $M_c(N)=\\mathcal{O}(e^{cN})$.\n  \\begin{equation}\n    M_c(N)\n    \\approx(M_c(6)-M_c(3))\\left(\\frac{N-3}{3}\\right)^\\alpha+M_c(3),\n    \\quad\\alpha>0,\n\\end{equation}\n\\begin{equation}\n    M_c(N)\\approx M_c(3)\\left(\\frac{M_c(6)}{M_c(3)}\\right)^{(N-3)/3}.\n  \\end{equation}\n  As we do not have any preference among the two candidates as well as\n  several other ones, we cannot decide which functional form\n  is appropriate for $M_c$.\n  The expression $[2::4]$ in the exponent is also ambiguous.\n  One may alternatively write something like\n  $\\mathcal{O}(N^\\alpha)$ with $\\alpha\\in[2,4]$\n  if it is a valid statement. \n- In page 3, lines 23-24, the authors claim that ``the number of\n  samples required for the estimate is either independent on (→ of)\n  the system size, $N$, or ...''. I do not find, however, any\n  experimental results supporting this claim either in Section 5.5\n  or in Appendix E.\n\n### [C16] Minor points\n- Page 1, lines 7 and 13; page 3, lines 4 and 5; page 6, line 31; page 7, line 2 and footnote 1: Closing double quotes are typeset differently from opening double quotes.\n- Page 1, line 37: there( )in.\n- Page 3, line 15: The symbol $\\bar{\\lambda}$ has not been defined yet.\n- Page 3, line 21: suggest(s)\n- Page 3, line 24: we(e → a)kly\n- Page 3, line 29: finding(,) $\\lambda_*\\in[0,1]$\n- Page 3, line 34: high-dimensional probability distribution(s)\n- Page 4, equation (4): $E_{ab}$ → $E_{ab}(x_a,x_b)$ / I feel that the factor $(1/2)$ of the terms\n  $h_ax_a+h_bx_b$ is somehow strange, since these terms are to be summed up\n  in equation (3) to yield $(1/2)\\sum_{a\\in\\mathcal{V}}d_ah_ax_x$,\n  where $d_a$ is the degree of the node $a$ in the graph,\n  which may be different from 2.\n- Page 4, line 8: which (is), generally, requires\n- Page 4, line 11: $\\mathcal{B}(x)\\in\\\\\\{-1,1\\\\\\}^{|\\mathcal{V}|}$\n  → $\\mathcal{B}:\\\\\\{-1,1\\\\\\}^{|\\mathcal{V}|}\\to[0,1]$\n- Page 4, line 29, equation (9): $\\lambda\\in[0,1](.\\ \\to\\ ,)$\n- Page 5, line 14: in (the → a) lower bound\n- Page 6, line 1: line(a)r; ther(e)fore\n- Page 6, line 33: from a to b → from $a$ to $b$\n- Page 8, lines 5-6: \"equally spaaced with the increment 0.05,\n  between 0.01 and 1\" In order to divide the interval $[0.01,1]$\n  evenly, the increment should not be 0.05 but $0.99/20=0.0495$.\n- Page 10, line 12: in the lat(t)er case\n- Page 12, line 20: The publication year of Wainweight and Jordan is not 2007 but 2008.\n- Page 13, line 15: result(s) in\n- Page 13, line 18, equation (22): $\\eta_{b\\to a}^{(\\lambda)}(x_a)$\n  and $\\eta_{a\\to b}^{(\\lambda)}(x_b)$ on the right-hand side are overlapped. \n- Page 14, line 2: from node-to-node → from node to node\n- Page 14, equations (24) and (25): Avoid use of the same symbols\n  as the independent variables $x_a$ and $x_b$ in the normalization\n  coefficients.\n- Figure numbers should not be enclosed in pairs of parentheses.", "broader_impact_concerns": "I do not see any concerns on the ethical implications of this work, as it is of theoretical nature.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "n4B0A1k0Bp", "reviewer": "Reviewer_gKSN", "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": "strength:\n* the paper deals with an interesting problem concerning the inference of Ising models.\n* the mathematical results obtained in the paper seem to provide a nice complement and extension to existing results.\n* discussion of related work is comprehensive.\n\nweakness:\n* Although understandable, experiments are conducted on synthetic data only.\n* presentation can be improved.", "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 a new inference algorithm for Ising models that interpolates between two classical inference algorithms: the tree-reweighted algorithm and the belief propagation algorithm. The inference algorithm is concerned with calculating the partition function of the Ising model. Theoretical justification and empirical evaluation are provided to validate the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* the title of section 1.2 suggests that it is concerned with the major contribution of the paper. However, a lot of background-related descriptions are also included. This makes it hard to parse the key contribution of the paper.\n* The last sentence of section 4 can be broken down into multiple sentences.\n* The graphs in the experiments can use some legends. The curves in figure 2 are getting too close to each other.", "broader_impact_concerns": "no ethical implication.s", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "20eyQqfRqr", "reviewer": "Reviewer_NNDJ", "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": "Starting with the strengths, the idea behind the new algorithm is pleasantly elegant. The proofs seem mostly similarly elegant. For the ferromagnetic case Theorem 4.1 + Lemma 3.3 provide quite a nice theoretical guarantee (which however does not address convergence of the message passing algorithm to the optimum for each $\\lambda$, but rather assumes it). As far as I can tell the idea is novel (though I am not an expert in the area of applying message passing to graphical models - for “calibration” I might mention that I was quite familiar with the BP algorithm before reading this work, but not had not heard of the TRWBP algorithm). From a theoretical stand-point I certainly find the work interesting.\n\nA major weakness is the quality of the write-up and presentation. There are many language errors, and suboptimally presented graphs.\n\nAnother weakness is that the performance of the algorithm is not really clearly compared to other algorithms.\n\nA further weakness is that practical applicability for actual machine learning is not made plausible. The experiments are all “toy” instances of the Ising model with no clear machine learning application. My positive answer to the \"audience\" question below is made with low confidence.", "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 paper introduces a new message passing algorithm for computing the partition function of Ising models, understood here as graphical models on an arbitrary finite graph with pairwise and one-vertex interactions, which may be edge resp. vertex dependent. In the most general setting the edge interactions can be ferromagnetic, anti-ferromagnetic or discorded.\n\nThe algorithm arises by interpolating between two previously known message passing algorithms: Belief Propagation (BP) and Tree Re-Weighted BP (TRWBP). In the presentation of the paper both of these algorithms correspond to different ways to parameterize a class of \"trial measures\" to approximate the Gibbs measure. A trial measure is found using BP message passing, and then plugged into the Gibbs variational principle to estimate the partition function. The authors write the trial measure parameterization of BP and TRWBP in the unified formula (8), which depends on an interpolation parameter lambda. The values $\\lambda=1$ and $\\lambda=0$ correspond to the parameterization of BP and TRWBP respectively. They then consider this formula for $\\lambda$ between $0$ and $1$, and note that for each $\\lambda \\in [0,1]$ one obtains a different trial measure parameterization, and therefore a different message passing algorithm.\n\nIn the ferromagnetic case they make the interesting observation that the true partition function $Z$ is equal to $Z^{(\\lambda)}$ for some lambda in $[0,1]$, where $Z^{(\\lambda)}$ denotes the estimate of the partition function with the optimal parameters (=optimal messages) for the corresponding trial measure parameterization. [Lemma 3.3]\n\nFurthermore, they obtain a kind of factorization formula for $Z$ that holds for any $\\lambda$. It says that for all lambda, $Z = Z^{(\\lambda)} \\times \\mathcal{Z}^{(\\lambda)}$, where $\\mathcal{Z}^{(\\lambda)}$ is a quantity that can be computed from the optimal parameters/messages for that $\\lambda$. [Theorem 4.1].\n\nBased on this they formulate their new algorithm for estimating the parition function $Z$ which they name the Fractional Message Passing Algorithm (FBP): [Algorithm 1]\n\nFor a range of $\\lambda \\in [0,1]$:\n- Use message passing to estimate the optimal parameters/messages for $\\lambda$.\n- Compute estimates of $Z^{(\\lambda)}$ and $\\mathcal{Z}^{(\\lambda)}$ using these.\n\nAt the end, for $\\lambda$ such that the estimate of $\\mathcal{Z}^{(\\lambda)}$ is closest to one, output the estimate of $Z^{(\\lambda)}$.\n\nThe success of the algorithm is contingent on the convergence of the message passing algorithm for each $\\lambda$.\n\nAs far as I can tell, for the ferromagnetic case, in an idealized setting where an oracle gives exact optimal parameters/messages for each $\\lambda$, and using the oracle is used for every value of $\\lambda$ in $[0,1]$, this algorithm is guaranteed to return the true value of the partition function $Z$.\n\nBeyond the ferromagnetic case, there is no guaranteed that $Z = Z^{(\\lambda)}$ for some $\\lambda \\in [0,1]$, so the algorithm may fail, but it may also plausibly produce good estimates in some cases.\n\nThe authors present numerical experiments for different \"toy\" instances of the Ising model. These \"toy\" instances seem to be more the spirit of theoretical physics than machine learning.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please improve presentation.\n* There are a few places in the text where I cannot figure out exactly\nwhat is meant. Please improve the corresponding formulations.\n   - In step 2 of the for loop of Algorithm 1 it says: use TRWBP to find\n$Z^{(\\lambda)},\\ldots$'. Is this a separate use of TRW, distinct\nfrom formulating eq. (8)? So that there is a kind of ``TRW on top\nof TRW'' in the algorithm? Also, why not use simply BP in this step?\n        - **[Edit]** In fact, to make the algorithm fully unambiguous also for readers who are not so used to thinking about message passing algorithms, it would be helpful if step 2 is fleshed out and written more explicitly. If the authors don't want to put such detail in algorithm 1, they could write a detailed \"subalgorithm\" in the appendix that the pseudocode in algorithm 1 can \"call\".\n   - In Section 6 in the second bullet point it says ``building a scheme\ninterpolating between TRW and Mean-Field''. What is meant by mean\nfield here?\n   - The abbreviation FBP is used on p6 before it has been introduced.\n\nPlease improve organization.\n* Algorithm 1 should come before Section 5 on \"numerical experiments\". After all, it is needed to fully specify what \"FBP\" is.\n\nPlease improve readability of the graphs.\n* One has to really look closely to see the difference between $\\log Z^{(\\lambda)}$\nand $\\log\\mathcal{Z}^{(\\lambda)}$ on two sides of e.g. Figure 1 (a)\n(b). Before that the reader is quite puzzled by what they are supposed\nto be showing. Please find a solution for this!\n * In Figure 2 I don't understand what is mean by \"hollow markers''\nand \"open symbols''. I see the hollow small shapes on the curves,\nbut if they are \"hollow markers'', what are the \"open symbols''?\nFurthermore these hollow/open symbols are much too small and difficult\nto make out. Here again the reader will likely spend some time puzzling\nover how exactly the \"exact values'' are \"values of lambda''\nare supposed to be expressed.\n\n\nPlease improve the English of the manuscript.\n\n\n* Several times terms that seem unidiomatic are used.\n   - For instance I've never seen \"inference efforts'' used. \"Computational\ncomplexity of inference'' or similar would make more sense to me.\n   - Is it really meaningful to use the word \"homotopy'' here? Maybe\nthere is some use of this word in a similar setting that I am not\naware of, but if not it seems like a stretch.\n\n* Grammar: Lots of grammar mistakes.\n  - In particular, often a definitive article is missing. For instance\non p. 4 it says \"Moreover, fractional approach developed in this\nmanuscript'' instead of \"Moreover, *the* fractional approach\ndeveloped in this manuscript''. \n   - Sometimes there is a superfluous definitive article, like in p. 10\nwhere it says \"We envision seeing in the future more examples where\n*the* variational GM techniques will be reinforced with *the*\nautomatic differentiation, e.g. in the spirit of (Lucibello et al.,\n2022), and also integrated into modern Deep Learning protocols..''.\nBoth of these \"the'' should be removed.\n - Ideally the manuscript should be proofread by a native speaker. If this is not possible then then please use the grammar checking features of e.g. Word to find the errors.\n\nPlease provide a comparison to other algorithms.\n* Is there some benchmark problem in this area that could be used to\ncompare the performance of this algorithm to other algorithms? If\nso please provide an experimental comparison.\n\n\nPlease make an application to machine learning more plausible.\n* Please come up with some simple experiment that you can add that illustrates\nhow the algorithm might be used in a machine learning setting. As\nthis is a fairly theoretical work, a \"toy'' example would be fine.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: After careful review of the author’s responses and revisions, I recommend accepting the paper. The submission introduces a valuable interpolation approach between BP and TRW, offering new insights into inference for structured models. Reviewer concerns on theoretical assumptions and algorithmic clarity were addressed, and additional empirical validation has strengthened the submission. Although some empirical claims remain conjectural, the core contributions are well-supported.
Decision: Accept (poster)