Year: 2021

Abstract:
Belief propagation is a fundamental message-passing algorithm for numerous applications in machine learning. It is known that belief propagation algorithm is exact on tree graphs. However, belief propagation is run on loopy graphs in most applications. So, understanding the behavior of belief propagation on loopy graphs has been a major topic for researchers in different areas. In this paper, we study the convergence behavior of generalized belief propagation algorithm on graphs with motifs (triangles, loops, etc.) We show under a certain initialization, generalized belief propagation converges to the global optimum of the Bethe free energy for ferromagnetic Ising models on graphs with motifs.

heading: 1 INTRODUCTION
text: Undirected graphical models, also known as Markov Random Fields (MRF), provide a framework for modeling high dimensional distributions with dependent variables. Ising models are a special class of discrete pairwise graphical models originated from statistical physics. Ising models have numerous applications in computer vision Ravikumar et al. (2010), bio-informatics Marbach et al. (2012), and social networks Eagle et al. (2009). Explicitly, the joint distribution of Ising model is given by
P(X) = 1
Z exp ( β( ∑ i hiXi + ∑ (i,j) JijXiXj) ) , (1)
where {Xi}i ∈ {±1}n are random variables valued in a binary alphabet (also known as "spins"), Jij represents the pairwise interactions between spin i and spin j, hi represents the external field for spin i, β = 1/T is the reciprocal temperature, and Z is a normalization constant called partition function.
Historically, Ising models are proposed to study ferromagnetism. However, researchers find the computational complexity is the main challenge of performing sampling and inference on Ising models. In the literature, there are multiple ways to tackle the computational complexity. One of the ways are Markov-Chain Monte Carlo (MCMC) algorithms. A well-known example is Gibbs sampling, which is a special case of the Metropolis–Hastings algorithm. Basically Gibbs sampling samples a random variable conditioned on the distribution based on the previous samples. It can be shown that Gibbs sampling generates a reversible Markov chain of samples. Thus, the stationary distribution of the Markov chain is the desired joint distribution over the random variables, and it can be reached after the burn-in period. However, it is also well-known that Gibbs sampling will become trapped on multi-modal distribution. For example, Smith and Roberts (1993) and Mengersen (1996) show that when the joint distribution is bi-modal, the Gibbs sampling iterations may be trapped in one of the modes, reducing the probability of convergence.
Another popular way to go around the computational complexity is variational methods, which makes some approximation to the joint distribution. These methods usually turn the inference problem with respect to the approximate joint distribution into some non-convex optimization problem, and solve it either by the standard optimization methods, e.g, gradient descent, or by specialized algorithms like belief propagation. However, due to the non-convexity, those methods usually do not have theoretical guarantees that the solution converges to the global optimum.
Belief propagation (BP) is an effective numerical method for solving inference problems on graphical models. It was originally proposed by Pearl (2014) for tree-like graphs. Ever since it plays a fundamental role in numerous applications including coding theory Frey et al. (1998); Richardson
and Urbanke (2001), constraint satisfaction problems Achlioptas and Moore (2006), and community detection in the stochastic block model Decelle et al. (2011). It is well-known that belief propagation is only exact for a model on a graph with locally tree-like structures. The long haunting question is, theoretically how does belief propagation perform on loopy graphs.
We now describe the related work and our contributions.
Related work and our contribution
In a classic work, Yedidia et al. (2003) establishes the connection between belief propagation and the Bethe free energy. He shows that there is one-to-one correspondence between the fixed points of belief propagation and stationary points of the Bethe free energy. Following his work, it is known that the Bethe free energy at the critical points can be represented in terms of fixed point messages of belief propagation Montanari (2013). In a recent work, Koehler (2019) further studies the properties of Bethe free energy at the critical points, and shows for ferromagnetic Ising models, initialized with all one messages, belief propagation converges to the fixed point corresponds to the global maximum of the Bethe free energy. However, those theories consider either asymptotic locally tree-like graphs, or loopy graphs with simple edges. Real technological, social and biological networks have numerous short and large loops and other complex motifs, which lead to non-tree-like structures and essentially loopy graphs with hyper edges. Newman Newman (2009); Karrer and Newman (2010) and Miller (2009) independently propose a model of random graphs with arbitrary distributions of motifs. And Yoon et al. (2011) generalizes the Belief Propagation to graphs with motifs.
Our work builds on generalized belief propagation on graphs with motifs Yoon et al. (2011) and the convergence of belief propagation on ferromagnetic Ising models on loopy graphs with simple edges Koehler (2019). In this paper, we show for ferromagnetic Ising models on graphs with motifs, with all messages initialized to one, generalized belief propagation converges to the fixed point corresponds to the global maximum of the Bethe free energy.

heading: 2 ISING MODELS ON GRAPHS WITH MOTIFS
text: Let us introduce the concept of graphs with motifs. In graphs with motifs, each vertex belongs to a given set of motifs. As shown in Fig.1a , different motifs can be attached to vertex i: a simple edge (i, j), a triangle, a square, a pentagon, and other non-clique motifs. Graphs with motifs can be viewed as hyper-graphs where motifs play a role of hyper-edges. And the number of specific motifs attached to a vertex is equal to hyper-degree with respect to the specific motifs. In this paper, for simplicity, we only consider simple motifs such as simple edges, and cliques.
Consider the Ising model with arbitrary order of interactions among vertices in each motif on a hyper-graph. Let Ml(i) denote a cluster of size l attached to vertex i, where vertices j1, j2, . . . , jl−1 together with i form the motif. And let X denote the random variable of spin configurations, the Hamiltonian of the model is
E(X) = − ∑ i hiXi − ∑ (i,j) JijXiXj − ∑ (i,j,k) JijkXiXjXk − ∑ (i,j,k,l) JijklXiXjXkXl − · · · (2)
where the first sum corresponds to the external fields at each vertex, the second sum corresponds to the pairwise interactions on simple edges, the third sum corresponds to the higher order interactions among spins in triangles, the fourth sum corresponds to the higher order interactions among spins in squares, and so on. As discussed in the previous section, most previous works focus on Ising models with pairwise interactions. In this paper, we are interested in Ising models with higher order interactions. For simplicity, we consider Ising models with only external fields and higher order interactions in triangles. Our derivation can be extended to more general cases.
Consider Ising models with only external fields and higher order interactions in triangles, the Hamiltonian of the model is
E(X) = − ∑ i hiXi − ∑ (i,j,k) JijkXiXjXk, (3)
where (i, j, k) is a triangle, which can also be denoted as M3(i), M3(j), or M3(k).
By Boltzmann’s law, the joint distribution is defined by
P (X) = 1
Z e−βE(X), (4)
where Z is the partition function.
Throughout this paper, we focus on ferromagnetic Ising models, which is defined below Definition 1. An Ising model is ferromagnetic if Jijk ≥ 0 for all triangle motifs (i, j, k) and hi ≥ 0 for all i.
We introduce a intermediate message µM3(i) from a motif M3(i) to spin i.
µM3(i)(Xi) = eβλM3(i)Xi
2 coshβλM3(i) . (5)
In the literature, different works have different definitions of messages. µM3(i) is not the message definition we eventually work with in this paper, but it helps to understand the connections between different works. So, abusing the terminology a little bit, we call it ‘intermediate message’.
By the definition of generalized Belief Propagation, the probability that spin i is in a state Xi is determined by the normalized product of incoming intermediate messages from motifs attached to spin i and the external field factor eβhiXi ,
Pi(Xi) = 1
A eβhiXi ∏ {M3(i)} µM3(i)(Xi), (6)
where A is a normalization constant. And the belief update rule is given by: µM3(i)(Xi) = B ∑
{Xj=±1}
e−βE(M3(i)) ∏ j ∏ {M3(j) 6=M3(i)} µM3(j)(Xj), (7)
where E(M3(i)) is an energy of the interaction among spins in the triangle M3(i), and B is a normalization constant.
Multiplying Equation (7) by Xi and summing over all spin configurations, we obtain an equation for the effective field λM3(i),
tanh (βλM3(i)) = 1
Z(M3(i)) ∑ {Xi,Xj1 ,...=±1} Xie −βẼ(M3(i)), (8)
where
Ẽ(M3(i)) = − 2∑
n=1
Λt(jn)Xjn − Jij1j2XiXj1Xj2 , (9)
Λt(j) = hj + ∑
{M3(j) 6=M3(i)}
λM3(j), (10)
Z(M3(i)) = ∑
{Xi,Xj1 ,...=±1}
e−βẼ(M3(i)). (11)
For more detailed explanations of Equations (7) to (11), please refer to Yoon et al. (2011).
Now, define a message from a spin i to motif M3(i) as νi→M3(i) = tanh(λM3(i)). More specifically, if the motif M3(i) is a triangle (i, j, k), the message can be alternatively represented as νi→M3(i) = νi→jk = tanh(λM3(i)). From now on, let the reciprocal temperature β = 1, we can further simplify Equation (8) as
νi→jk = tanh ( hi + ∑ {m,n}∈∂i\{j,k} tanh−1(tanh (Jimn)νm→inνn→im) ) , (12)
where ∂i denotes the motifs attached to spin i. Equation (12) is the consistency equation for fixed point hyper-edge messages ν∗i→jk of the generalized belief propagation. Alternatively, we denote Equation (12) as νi→jk = φ(ν)i→jk.

heading: 3 BETHE FREE ENERGY OF HIGHER ORDER ISING MODELS
text: In order to get the Bethe free energy of our higher order Ising model (3), we need to go through the Gibbs variational principle as Yedidia et al. (2003) did for standard Ising models with pairwise interactions. Let P ∗ be a joint distribution defined by our model (4). If we have some approximate joint distribution P , from Gibbs variational principle, we can write Gibbs free energy as
G(P ) = − ∑ x P (x)E(x)− ∑ x P (x) logP (x) (13)
= −U(P ) + S(P ), (14)
where U(P ) is called the average energy, and S(P ) is the entropy.
We would like to derive a Gibbs free energy that is a function of both the one-node beliefs Pi(xi) and the three-node beliefs Pijk(xi, xj , xk). The beliefs should satisfy the normalization conditions and the marginalization conditions. In other words, P lies in the following polytope of locally consistent distributions ∑
xj ,xk Pijk(xi, xj , xk) = Pi(xi) for all triangles i, j, k∑ xi Pi(xi) = 1 for all i (15)
Pi(xi), Pijk(xi, xj , xk) ≥ 0 for all triangles (i, j, k), and all xi, xj , xk Because we only consider external fields and higher order interactions with triangles in our model, the one-node and three-node beliefs are actually sufficient to determine the average energy. For our model (3) and for any approximate joint probability P such that one-node marginal probabilities are Pi(xi) and the three-node marginal probabilities are Pijk(xi, xj , xk), the average energy will have the form
U(P ) = − ∑
(i,j,k) ∑ xi,xj ,xk Pijk(xi, xj , xk)Jijkxixjxk − ∑ i ∑ xi Pi(xi)hixi (16)
The average energy computed with the true marginal probabilities P ∗i (xi) and P ∗ ijk(xi, xj , xk) will also have this form, so if one-node and three-node beliefs are exact, the average energy given by Equation (16) will be exact.
For computing the entropy, we usually need an approximation. We can compute the entropy exactly if we can explicitly express the joint distribution P (x) in terms of the one-node and three-node beliefs. If our graph were tree-like hyper-graph with triangle motifs only (see Fig. 1b as an example), we can in fact do that. In that case, we can represent the joint probability distribution in the form
P (x) = ∏ (i,j,k) Pijk(xi, xj , xk)∏
i Pi(xi) qi−1
, (17)
where qi is the hyper-degree of node i.
Using Equation (17), we get the Bethe approximation to the entropy as SBethe(P ) = − ∑
(i,j,k) ∑ xi,xj ,xk Pijk(xi, xj , xk) logPijk(xi, xj , xk)
+ ∑ i (qi − 1) ∑ xi Pi(xi) logPi(xi) (18)
Combining Equation (16) and (18), we obtain the Bethe free energy
GBethe(P ) = −U(P ) + SBethe(P ) (19) = ∑
(i,j,k) JijkEPijk [XiXjXk] + ∑ i hiEPi [Xi]
+ ∑
(i,j,k) HPijk(Xi, Xj , Xk)− ∑ i (qi − 1)HPi(Xi) (20)
Notice when the hyper-graph is a tree, the Bethe free energyGBethe(P ) will have the correct functional dependence on the beliefs. And solving the optimization problem: maximizing GBethe(P ) over the polytope of locally consistent distribution (15) will give the true marginals. For loopy hyper-graphs, the Bethe free energy GBethe(P ) is only an approximation, which is the essence of the variational methods.
We can derive the BP equations from the first-order optimality conditions for the aforementioned optimization problem. In other words, we can verify that a set of beliefs gives a BP fixed point in any hyper-graph if and only if they are stationary points of the Bethe free energy for the generalized BP. To see this, we need to add Lagrange multipliers to GBethe(P ) to form a Lagrangian L. Let λi→jk(xi) be a multiplier that enforces the marginalization constraint ∑ xj ,xk
Pijk(xi, xj , xk) = Pi(xi), and λi be a multiplier that enforces the normalization of Pi(xi). So, the largrangian corresponding to the optimization problem is
L(P, λ) = GBethe(P ) + ∑
(i,j,k),xi λi→jk(xi)( ∑ xj ,xk Pijk(xi, xj , xk)− Pi(xi))
+ ∑ i λi( ∑ xi Pi(xi)− 1) (21)
where we ignore the constraints Pi(xi), Pijk(xi, xj , xk) ≥ 0 because, given other constraints, those constraints are always satisfied at a critical point.
The equation ∂L∂Pijk(xi,xj ,xk) = 0 gives:
logPijk(xi, xj , xk) = Jijkxixjxk + λi→jk(xi) + λj→ik(xj) + λk→ij(xk)− 1 (22)
Setting λ′i→jk = λi→jk(1)−λi→jk(−1) 2 , we find that at a critical point of the Lagrangian that Pijk(xi, xj , xk) ∝ exp ( Jijkxixjxk + λi→jk(xi) + λj→ik(xj) + λk→ij(xk) ) (23)
∝ exp ( Jijkxixjxk + λ ′ i→jkxi + λ ′ j→ikxj + λ ′ k→ijxk ) (24)
And the equation ∂L∂Pi(xi) = 0 gives:
(qi − 1)(1 + logPi(xi)) = ∑
{j,k}∈∂i
λi→jk(xi)− hixi − λi (25)
Setting λ′i→jk = λi→jk(1)−λi→jk(−1) 2 , we find that at a critical point of the Lagrangian that
Pi(xi) ∝ exp ( 1 qi − 1 ∑
{j,k}∈∂i
λi→jk(xi)− hi
qi − 1 xi
) (26)
∝ exp ( 1 qi − 1 ∑
{j,k}∈∂i
λ′i→jkxi − hi
qi − 1 xi
) (27)
Furthermore, by differentiating with respect to λ, we see that the marginalization constraints are satisfied. Therefore, for any triangle (i, j, k), ∑ xj ,xk Pijk(xi, xj , xk) = Pi(xi). Hence,
Pi(xi) qi−1 ∝ ∏ {m,n}∈∂i\{j,k} ∑ xm,xn Pimn(xi, xm, xn) (28)
∝ ∑
x∂i\{j,k}
exp ( ∑ {m,n} (Jimnxixmxn + λ ′ i→mnxi + λ ′ m→inxm + λ ′ n→imxn) ) (29)
= exp( ∑ {m,n} λ′i→mnxi) ∑ x∂i\{j,k} exp ( ∑ {m,n} (Jimnxixmxn + λ ′ m→inxm + λ ′ n→imxn) ) (30)
So
exp(λ′i→jkxi − hixi) ∝ ∑
x∂i\{j,k}
exp ( ∑ {m,n} (Jimnxixmxn + λ ′ m→inxm + λ ′ n→imxn) ) (31)
∝ ∏
{m,n}∈∂i\{j,k} ∑ xm,xn exp ( Jimnxixmxn + λ ′ m→inxm + λ ′ n→imxn ) (32)
Define νi→jk := tanh(λ′i→jk), we have
1 + νi→jkxi 2 = eλ
′ i→jkxi
eλ ′ i→jk + e−λ ′ i→jk
(33)
Let
f(xi) = e hixi ∏ {m,n} ∑ xm,xn eJimnxixmxneλ ′ m→inxm+λ ′ n→imxn (34)
Then we see
νi→jk = f(1)− f(−1) f(1) + f(−1)
(35)
= tanh ( hi + ∑ {m,n}∈∂i\{j,k} tanh−1(tanh (Jimn)νm→inνn→im) ) (36)
which is the BP consistency equation (12) we derived in Section 2.
Till this point, we represent the Bethe free energy in terms of beliefs corresponds to BP fixed points. In order to analyze the behavior of the Bethe free energy at BP fixed points, we need to represent the Bethe free energy in terms of the hyper-edge messages νi→jk, which is called dual Bethe free energy in the literature. First, we have the following lemma.
Lemma 1. The dual Bethe free energy at a critical point can be defined by G∗Bethe(λ) = ∑ i Fi(λ)− ∑ (i,j,k) Fijk(λ), (37)
where
Fi(λ) = log ∑ xi ehixi ∏ {m,n}∈∂i ∑ xm,xn eJimnxixmxneλ ′ m→inxm+λ ′ n→imxn (38)
Fijk(λ) = log ∑
xi,xj ,xk
eJijkxixjxk+λ ′ i→jkxi+λ ′ j→ikxj+λ ′ k→ijxk (39)
Proof. Recall the Bethe free energy
GBethe(P ) = −U(P ) + SBethe(P ) (40) = ∑
(i,j,k) JijkEPijk [XiXjXk] + ∑ i hiEPi [Xi] (41)
+ ∑
(i,j,k) HPijk(Xi, Xj , Xk)− ∑ i (qi − 1)HPi(Xi) (42)
By rearranging terms, we have
GBethe(P ) = G ∗ Bethe(λ) = ∑ i Fi(λ)− ∑ (i,j,k) Fijk(λ), (43)
where
Fi(λ) = E[hiXi + ∑ {m,n} (JimnXiXmXn + λ ′ m→inXm + λ ′ n→imXn)] (44)
+ ∑
{m,n}∈∂i
H(Xi, Xm, Xn)− (qi − 1)H(Xi) (45)
and
Fijk(λ) = E[JijkXiXjXk + λ′i→jkXi + λ′j→ikXj + λ′k→ijXk] +H(Xi, Xj , Xk) (46)
W.l.o.g., let us look at the term Fijk(λ), let f(X) = JijkXiXjXk+λ′i→jkXi+λ ′ j→ikXj+λ ′ k→ijXk, it can be rewritten as
Fijk(λ) = E[f(X)]− E[logPijk(Xi, Xj , Xk)] (47)
= E[log ef(X)
Pijk(Xi, Xj , Xk) ] (48)
From Equation (4), we know
Pijk(Xi, Xj , Xk) = 1
Zijk ef(X), (49)
where Zijk is a normalization constant Zijk = ∑ xi,xj ,xk
ef(X). Substitute it back into Equation (47), we have
Fijk(λ) = E[log(Zijk)] = log(Zijk) = log( ∑
xi,xj ,xk
ef(X)) (50)
= log ∑
xi,xj ,xk
eJijkxixjxk+λ ′ i→jkxi+λ ′ j→ikxj+λ ′ k→ijxk (51)
If we use the definition νi→jk := tanh(λ′i→jk), and define θijk = tanh(Jijk), we have the following corollary:
Corollary 1. The dual Bethe free energy in terms of hyper-edge messages is G∗Bethe(ν) = ∑ i Fi(ν)− ∑ (i,j,k) Fijk(ν), (52)
where
Fi(ν) = log [ ehi ∏ m,n (1 + θimnvm→inνn→im)− e−hi ∏ m,n (1− θimnvm→inνn→im) ]
(53)
Fijk(λ) = log ( 1 + θijkνi→jkνj→ikνk→ij ) (54)

heading: 4 OPTIMIZATION LANDSCAPE
text: Now, we can study the behavior of the Bethe free energy at critical points. The following lemma establishes that φ(ν)i→jk is a concave monotone function for some non-negative ν.
Lemma 2. Suppose that f(x) = tanh(h + ∑
(i,j) tanh −1(xixj)) for any h ≥ 0. Then f is a
concave monotone function on the domain [x∗, 1)n.
Proof. Observe that
∂f ∂xi (x) =
1− f(x)2
1− (xjxi)2 xj ≥ 0, (55)
which proves monotonicity, and
∂2f
∂xixk (x) =
1− f(x)2
(1− (xjxi)2)(1− (xlxk)2)
[ − 2f(x)xjxl + 1(k = j, l = i)(1 + (xixj)2)
+ 1(k = i, l = j)2(xixj) 2 ] . (56)
Note that for any non-negative vector w, if we let
w′i =
√ 1− f(x)2 1− (xjxi)2 xjwi, w ′ k = √ 1− f(x)2 1− (xkxl)2 xlwk (57)
Then we have,∑ i,k wi ∂2f ∂xixk wk (58)
= ∑ i,k w′i [ − 2f(x) + 1(k = j, l = i)( 1 xixj + xixj) + 1(k = i, l = j)2xixj ] w′k (59)
=− 2f(x)( ∑ i w′i) 2 + ∑ (ij) w′iw ′ j( 1 xixj + xixj) + ∑ i w′i 2 2xixj (60)
≤ ∑ i −2(f(x)− xixj)w′i 2 + ∑ (ij) w′iw ′ j( 1 xixj + xixj − 2f(x)) (61)
= ∑ (i,j) w′iw ′ j [ 1 xixj + xixj − 2f(x) ( 1 + (1− xixj f(x) )( 1 qi w′i w′j + 1 qj w′j w′i ) )] (62)
For any edge (i, j), let C = 1qi w′i w′j + 1qj w′j w′i (note C ≥ 2/√qiqj), and
g(x) = 1
x + x− 2f(x)
( 1 + C(1− x
f(x) )
) . (63)
Due to the fact x < f(x), we know g(x)→∞ as x→ 0, and g(1) < 0. Since g(x) is continuous over (0, 1), if we assume x∗ij is the largest root for g(x) in (0, 1), we know g(x) < 0 in (x ∗ ij , 1). Let x∗ = max(i,j) x ∗ ij , we have ∑
i,k
wi ∂2f
∂xixk wk ≤ 0, (64)
for x ∈ [x∗, 1)n.
We define the set of pre-fixpoints and post-fixpoints messages similar as in Koehler (2019):
Spre = {ν : x∗ ≤ φ(ν)i→jk ≤ νi→jk}, Spost = {ν : x∗ ≤ νi→jk ≤ φ(ν)i→jk} (65)
From Lemma 2, we know Spost is a convex set, while Spre is typically non-convex and even disconnected. Next, we show the gradient of the dual Bethe free energy is well-behaved on these sets:
Lemma 3. If ν ∈ Spre then∇G∗Bethe(ν) ≤ 0 and if ν ∈ Spost then∇G∗Bethe(ν) ≥ 0
Proof. The lemma will follow if we compute the gradient of the dual Bethe free energy function G∗Bethe(ν).
∂G∗Bethe(ν)
∂νj→ik = ∂Fi(ν) ∂νj→ik − ∂Fijk(ν) ∂νj→ik
= ehiθνk→ij
∏ m,n∈∂i\{j,k}(1 + θνm→inνn→im)− e−hiθνk→ij ∏ m,n∈∂i\{j,k}(1− θνm→inνn→im)
ehi ∏ m,n(1 + θvm→inνn→im)− e−hi ∏ m,n(1− θvm→inνn→im)
− θνi→jkνk→ij 1 + θνi→jkνj→ikνk→ij
= 1 νj→ik + 1/(θνk→ijφ(ν)i→jk) − 1 νj→ik + 1/(θνk→ijνi→jk) . (66)
Recall φ(ν)i→jk is the updated message from spin i to motif {j, k} based on the current messages ν. If ν ∈ Spre or Spost, then the signs of the gradient of Bethe free energy are determined by Equation (66) as claimed.
Based on Lemma 2 and 3, we can prove our main theorem.
Theorem 1. Suppose that generalized BP is run from initial messages ν(0)i→jk = 1 and there is at least one fixed point in [x∗, 1)n. The messages converge to a fixed point ν∗ of the generalized BP equations such that for any other fixed point µ, µi→jk ≤ ν∗i→jk. Furthermore
G∗Bethe(ν ∗) = max ν∈Spost G∗Bethe(ν) (67)
Proof. If there is at least one fixed point in [x∗, 1)n, and the initialization is ν(0)i→jk = 1 for all hyper-edges {i, j, k}. For each iteration of Belief Propagation, ν(t) = φ(ν(t−1)).
From Lemma 2, we know φ is monotonic on [x∗, 1)n. So, ν(0), ν(1), . . . , ν(t) is a coordinate-wise decreasing sequence, which will converge to some fixed point. By monotonicity, we see that for any fixed point µ ∈ [x∗, 1)n, µi→jk ≤ ν(t)i→jk for all t. Hence, it holds for ν∗ as well.
Finally, consider any other point ν ∈ Spost, by convexity of Spost, we know that the line segment from ν to ν∗ is entirely contained in Spost. By Lemma 3, we see that for any point x on this interpolating line segment that ∇GBethe(ν) · (ν∗ − ν) ≥ 0, and integrating over this line segment gives us GBethe(ν) ≤ GBethe(ν∗).

Review summaries:
The author considers a special class of attractive models and extends the convergence results of [Koehler]. In general, the convergence behavior of belief propagation algorithm is hard to be understood, however, attractive models are special class of models known to have simple optimization loss landscape. Therefore, the result of the paper is unlikely to be generalized to non-attractive models, limiting the application of the paper.