# CONVERGENCE OF GENERALIZED BELIEF PROPAGA## TION ALGORITHM ON GRAPHS WITH MOTIFS

**Anonymous authors**
Paper under double-blind review

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.

1 INTRODUCTION

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]



_JijXiXj)_ _,_ (1)
(i,j) 

X


_hiXi +_


where _Xi_ _i_ 1 are random variables valued in a binary alphabet (also known as "spins"), Jij
represents the pairwise interactions between spin { _}_ _∈{±_ _}[n]_ _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.

2 ISING MODELS ON GRAPHS WITH MOTIFS

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


_JijklXiXjXkXl_ (2)
_−· · ·_
(i,j,k,l)

X


_E(X) = −_


_hiXi_
_−_


_JijXiXj_
_−_
(i,j)

X


_JijkXiXjXk_
_−_
(i,j,k)

X


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


_JijkXiXjXk,_ (3)

(i,j,k)

X


_E(X) = −_


_hiXi_
_−_


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) = Z [1] _[e][−][βE][(][X][)][,]_ (4)


where Z is the partition function.

Throughout this paper, we focus on ferromagnetic Ising models, which is defined below
_for allDefinition 1. i._ _An Ising model is ferromagnetic if Jijk ≥_ 0 for all triangle motifs (i, j, k) and hi ≥ 0

We introduce a intermediate message µM3(i) from a motif M3(i) to spin i.

_e[βλ][M][3(][i][)][X][i]_
_µ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[βh][i][X][i],

_Pi(Xi) = A[1]_ _[e][βh][i][X][i]_ _µM3(i)(Xi),_ (6)

_{MY3(i)}_

where A is a normalization constant. And the belief update rule is given by:

_µM3(i)(Xi) = B_ _e[−][βE][(][M][3][(][i][))][ Y]_ _µM3(j)(Xj),_ (7)

_{XXj_ =±1} _j_ _{M3(jY)≠_ _M3(i)}_

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),


_Xie[−][β][ ˜]E(M3(i)),_ (8)
_{Xi,XjX1_ _,...=±1}_


tanh (βλM3(i)) =


_Z(M3(i))_


(a) Different motifs attached to vertex i (b) Tree-like hyper-graph with triangle motifs only

Figure 1: Examples of hyper-graphs


-----

where


Λt(jn)Xjn _Jij1j2_ _XiXj1_ _Xj2_ _,_ (9)
_n=1_ _−_

X


_E˜(M3(i)) =_
_−_


_λM3(j),_ (10)
_{M3(jX)≠_ _M3(i)}_


Λt(j) = hj +


_e[−][β][ ˜]E(M3(i))._ (11)
_{Xi,XjX1_ _,...=±1}_


_Z(M3(i)) =_


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


tanh[−][1](tanh (Jimn)νm→inνn→im) _,_ (12)
_m,n_ _∂i_ _j,k_ 
_{_ _}∈X\{_ _}_


_νi_ _jk = tanh_ _hi +_
_→_



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._
_→_ _→_

3 BETHE FREE ENERGY OF HIGHER ORDER ISING MODELS

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


_P_ (x) log P (x) (13)


_G(P_ ) = −


_P_ (x)E(x) −


= −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

_Pijk(xi, xj, xk) = Pi(xi)_ for all triangles i, j, k
_xj_ _,xk_

X

_Pi(xi) = 1_ for all i (15)
_xi_

X

_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


_Pi(xi)hixi_ (16)
_xi_

X


_U_ (P ) = −


_Pijk(xi, xj, xk)Jijkxixjxk_

(i,j,k) _xi,xj_ _,xk_ _−_

X X


-----

The average energy computed with the true marginal probabilities Pi[∗][(][x][i][)][ and][ P]ijk[ ∗] [(][x][i][, x][j][, x][k][)][ 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


(i,j,k) _[P][ijk][(][x][i][, x][j][, x][k][)]_

_,_ (17)
_i_ _[P][i][(][x][i][)][q][i][−][1]_

Q


_P_ (x) =

where qi is the hyper-degree of node i.


Using Equation (17), we get the Bethe approximation to the entropy as


_SBethe(P_ ) = −


_Pijk(xi, xj, xk) log Pijk(xi, xj, xk)_
_xi,xj_ _,xk_

X


(i,j,k)


_Pi(xi) log Pi(xi)_ (18)
_xi_

X


(qi 1)
_−_


Combining Equation (16) and (18), we obtain the Bethe free energy

_GBethe(P_ ) = −U (P ) + SBethe(P ) (19)

= _JijkEPijk_ [XiXjXk] + _hiEPi_ [Xi]

(i,j,k) _i_

X X


(qi 1)HPi (Xi) (20)
_−_


_HPijk_ (Xi, Xj, Xk)
_−_
(i,j,k)

X


Notice when the hyper-graph is a tree, the Bethe free energy GBethe(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_ _[P][ijk][(][x][i][, x][j][, x][k][) =][ P][i][(][x][i][)][, and]_
_λi be a multiplier that enforces the normalization of Pi(xi). So, the largrangian corresponding to the_
optimization problem is [P]


_L(P, λ) = GBethe(P_ ) +


_λi→jk(xi)(_ _Pijk(xi, xj, xk) −_ _Pi(xi))_
(i,j,k),xi _xj_ _,xk_

X X


_Pi(xi)_ 1) (21)
_−_
_xi_

X


_λi(_


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 _∂Pijk(∂Lxi,xj_ _,xk)_ [= 0][ gives:]


log Pijk(xi, xj, xk) = Jijkxixjxk + λi _jk(xi) + λj_ _ik(xj) + λk_ _ij(xk)_ 1 (22)
_→_ _→_ _→_ _−_

Setting λ[′]i _jk_ [=][ λ][i][→][jk][(1)][−]2[λ][i][→][jk][(][−][1)], 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→jk[x][i]_ [+][ λ][′]j→ik[x][j] [+][ λ][′]k→ij[x][k]



(24)


-----

And the equation _∂P∂Li(xi)_ [= 0][ gives:]

(qi 1)(1 + log Pi(xi)) =
_−_


_λi→jk(xi) −_ _hixi −_ _λi_ (25)
_{j,kX}∈∂i_


Setting λ[′]i _jk_ [=][ λ][i][→][jk][(1)][−]2[λ][i][→][jk][(][−][1)]
_→_

_Pi(xi)_ exp
_∝_

_∝_ exp


, we find that at a critical point of the Lagrangian that


_hi_
_λi→jk(xi) −_ _qi_ 1 _[x][i]_
_j,k_ _∂i_
_{_ X}∈ _−_

_hi_
_λ[′]i→jk[x][i]_ _[−]_ _qi_ 1 _[x][i]_
_{j,kX}∈∂i_ _−_ 


(26)

(27)


_qi_ 1
_−_

1

_qi_ 1
_−_


Furthermore, by differentiating with respect to λ, we see that the marginalization constraints are
satisfied. Therefore, for any triangle (i, j, k), _xj_ _,xk_ _[P][ijk][(][x][i][, x][j][, x][k][) =][ P][i][(][x][i][)][. Hence,]_

_Pi(xi)[q][i][−][1]_ _Pimn(xi, x[P]m, xn)_ (28)
_∝_

_{m,n}∈Y∂i\{j,k}_ _xXm,xn_

_∝_ exp (Jimnxixmxn + λ[′]i→mn[x][i] [+][ λ][′]m→in[x][m] [+][ λ][′]n→im[x][n][)] (29)

_x∂iX\{j,k}_  X{m,n} 

= exp( _λ[′]i→mn[x][i][)]_ exp (Jimnxixmxn + λ[′]m→in[x][m] [+][ λ][′]n→im[x][n][)]

_{Xm,n}_ _x∂iX\{j,k}_  X{m,n}

(30)


So

exp(λ[′]i→jk[x][i] _[−]_ _[h][i][x][i][)][ ∝]_


exp (Jimnxixmxn + λ[′]m→in[x][m] [+][ λ][′]n→im[x][n][)] (31)
_x∂iX\{j,k}_  X{m,n} 


exp _Jimnxixmxn + λ[′]m→in[x][m]_ [+][ λ][′]n→im[x][n]
_xm,xn_ 

X


_{m,n}∈∂i\{j,k}_

Define νi _jk := tanh(λ[′]i_ _jk[)][, we have]_
_→_ _→_


(32)

_e[λ]i[′]→jk[x][i]_

(33)
_e[λ]i[′]→jk + e[−][λ]i[′]→jk_


1 + νi→jkxi


Let

Then we see


_f_ (xi) = e[h][i][x][i][ Y]

_{m,n}_


_m_ _in[x][m][+][λ]n[′]_ _im[x][n]_
_e[J][imn][x][i][x][m][x][n]_ _e[λ][′]_ _→_ _→_ (34)
_xm,xn_

X


_νi_ _jk =_ _[f]_ [(1)][ −] _[f]_ [(][−][1)] (35)
_→_ _f_ (1) + f (−1)


tanh[−][1](tanh (Jimn)νm→inνn→im) (36)
_m,n_ _∂i_ _j,k_ 
_{_ _}∈X\{_ _}_


= tanh _hi +_



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[(][λ][) =]_


_Fi(λ)_ _Fijk(λ),_ (37)
_−_

(i,j,k)

X


_where_


_e[J][imn][x][i][x][m][x][n]_ _e[λ]m[′]_ _→in[x][m][+][λ][′]n→im[x][n]_ (38)
_xm,xn_

X


_e[h][i][x][i]_

_xi_

X


_Fi(λ) = log_

_Fijk(λ) = log_


_xi_ _{m,n}∈∂i_ _xm,xn_

_e[J][ijk][x][i][x][j]_ _[x][k][+][λ]i[′]→jk[x][i][+][λ][′]j→ik[x][j]_ [+][λ][′]k→ij _[x][k]_ (39)
_xi,xj_ _,xk_

X


_Proof. Recall the Bethe free energy_

_GBethe(P_ ) = −U (P ) + SBethe(P ) (40)

= _JijkEPijk_ [XiXjXk] + _hiEPi_ [Xi] (41)

(i,j,k) _i_

X X


(qi 1)HPi (Xi) (42)
_−_

_Fijk(λ),_ (43)

(i,j,k)

X


_HPijk_ (Xi, Xj, Xk)
_−_
(i,j,k)

X


By rearranging terms, we have

_GBethe(P_ ) = G[∗]Bethe[(][λ][) =]

where


_Fi(λ)_
_−_


_Fi(λ) = E[hiXi +_ (JimnXiXmXn + λ[′]m→in[X][m] [+][ λ][′]n→im[X][n][)]] (44)

_{Xm,n}_


+ _H(Xi, Xm, Xn)_ (qi 1)H(Xi) (45)

_−_ _−_
_{m,nX}∈∂i_

_Fijk(λ) = E[JijkXiXjXk + λ[′]i→jk[X][i]_ [+][ λ][′]j→ik[X][j] [+][ λ][′]k→ij[X][k][] +][ H][(][X][i][, X][j][, X][k][)] (46)


and


W.l.o.g., let us look at the term Fijk(λ), let f (X) = JijkXiXjXk+λ[′]i _jk[X][i][+][λ][′]j_ _ik[X][j]_ [+][λ][′]k _ij[X][k][,]_
_→_ _→_ _→_
it can be rewritten as

_Fijk(λ) = E[f_ (X)] − E[log Pijk(Xi, Xj, Xk)] (47)

_e[f]_ [(][X][)]
= E[log (48)

_Pijk(Xi, Xj, Xk)_ []]


From Equation (4), we know


1

_e[f]_ [(][X][)], (49)
_Zijk_


_Pijk(Xi, Xj, Xk) =_


where Zijk is a normalization constant Zijk = _xi,xj_ _,xk_ _[e][f]_ [(][X][)][. Substitute it back into Equation]

(47), we have

[P]

_Fijk(λ) = E[log(Zijk)] = log(Zijk) = log(_ _e[f]_ [(][X][)]) (50)

_xi,xj_ _,xk_

X


= log _e[J][ijk][x][i][x][j]_ _[x][k][+][λ]i[′]→jk[x][i][+][λ][′]j→ik[x][j]_ [+][λ][′]k→ij _[x][k]_ (51)

_xi,xj_ _,xk_

X


If we use the definition νi _jk := tanh(λ[′]i_ _jk[)][, and define][ θ][ijk][ = tanh(][J][ijk][)][, we have the following]_
_→_ _→_
corollary:


-----

**Corollary 1. The dual Bethe free energy in terms of hyper-edge messages is**


_G[∗]Bethe[(][ν][) =]_


_Fijk(ν),_ (52)

(i,j,k)

X


_Fi(ν)_
_−_


_where_

_Fi(ν) = log_ _e[h][i][ Y](1 + θimnvm→inνn→im) −_ _e[−][h][i][ Y](1 −_ _θimnvm→inνn→im)_ (53)
 _m,n_ _m,n_ 

_Fijk(λ) = log_ 1 + θijkνi→jkνj→ikνk→ij (54)
 


4 OPTIMIZATION LANDSCAPE

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][(][x][i][x][j][))][ for any][ h][ ≥] [0][. Then][ f][ is a]

_concave monotone function on the domain [x[∗], 1)[n]._

[P]

_Proof. Observe that_

_∂f_

(x) = [1][ −] _[f]_ [(][x][)][2] (55)
_∂xi_ 1 (xjxi)[2][ x][j][ ≥] [0][,]

_−_

which proves monotonicity, and


_∂[2]f_ 1 _f_ (x)[2]

(x) = _−_
_∂xixk_ (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


1 _f_ (x)[2]
_−_ _wk[′]_ [=]

1 (xjxi)[2][ x][j][w][i][,]

p −


1 − _f_ (x)[2] (57)

1 (xkxl)[2][ x][l][w][k]

p −


_wi[′]_ [=]


Then we have,


_∂[2]f_
_wi_ _wk_ (58)

_∂xixk_

_i,k_

X


_wi[′]_
_i,k_

X


_wk[′]_ (59)


_−_ 2f (x) + 1(k = j, l = i)(


+ xixj) + 1(k = i, l = j)2xixj
_xixj_


_wi[′][)][2][ +]_


2
_wi[′]_ 2xixj (60)


_wi[′][w]j[′]_ [(]
(ij)

X


= − 2f (x)(


+ xixj) +
_xixj_


2
2(f (x) _xixj)wi[′]_ +
_−_ _−_


_wi[′][w]j[′]_ [(]
(ij)

X


1

+ xixj 2f (x)) (61)
_xixj_ _−_


_wj[′]_ ) (62)

_wi[′]_



_wi[′]_

+ [1]
_wj[′]_ _qj_


1

+ xixj 2f (x) 1 + (1
_xixj_ _−_ _−_ _f[x][i]([x]x[j])_ [)( 1]qi



_wi[′][w]j[′]_
(i,j)

X


_wj[′]_

_wi[′]_ [(note][ C][ ≥] [2][/][√][q][i][q][j][), and]


For any edge (i, j), let C = _q[1]i_ _wwj[′]i[′]_ [+][ 1]qj


_g(x) = [1]_ 1 + C(1

_x_ [+][ x][ −] [2][f] [(][x][)] _−_



_x_

_._ (63)
_f_ (x) [)]



-----

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]

_∂[2]f_
_wi_ _wk_ 0, (64)
_i,k_ _∂xixk_ _≤_

X


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][ ν][ ∈] _[S][post][ 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[(][ν][)]_

= _[∂F][i][(][ν][)]_
_∂νj→ik_ _∂νj→ik_ _−_ _[∂F]∂ν[ijk]j→[(]ik[ν][)]_

= _e[h][i]_ _θνk→ij_ _m,n∈∂i\{j,k}[(1 +][ θν][m][→][in][ν][n][→][im][)][ −]_ _[e][−][h][i]_ _[θν][k][→][ij]_ _m,n∈∂i\{j,k}[(1][ −]_ _[θν][m][→][in][ν][n][→][im][)]_
Q _e[h][i][ Q]m,n[(1 +][ θv][m][→][in][ν][n][→][im][)][ −]_ _[e][−][h][i][ Q]m,n[(1]Q[ −]_ _[θv][m][→][in][ν][n][→][im][)]_

_θνi→jkνk→ij_
_−_ 1 + θνi→jkνj→ikνk→ij


1

(66)
_νj_ _ik + 1/(θνk_ _ijνi_ _jk)_ _[.]_
_→_ _→_ _→_


_νj_ _ik + 1/(θνk_ _ijφ(ν)i_ _jk)_
_→_ _→_ _→_ _[−]_


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 νi[(0)]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]_ _Bethe[(][ν][)]_ (67)
_ν_ _Spost_ _[G][∗]_
_∈_

_Proof. If there is at least one fixed point in [x[∗], 1)[n], and the initialization is νi[(0)]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 ≤ _νi[(]→[t][)]_ _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(ν[∗])._


-----

REFERENCES

D. Achlioptas and C. Moore. Random k-sat: Two moments suffice to cross a sharp threshold. SIAM
_Journal on Computing, 36(3):740–762, 2006._

A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block
model for modular networks and its algorithmic applications. Physical Review E, 84(6):066106,
2011.

N. Eagle, A. S. Pentland, and D. Lazer. Inferring friendship network structure by using mobile phone
data. Proceedings of the national academy of sciences, 106(36):15274–15278, 2009.

B. J. Frey, J. F. Brendan, and B. J. Frey. Graphical models for machine learning and digital
_communication. MIT press, 1998._

B. Karrer and M. E. Newman. Random graphs containing arbitrary distributions of subgraphs.
_Physical Review E, 82(6):066118, 2010._

F. Koehler. Fast convergence of belief propagation to global optima: Beyond correlation decay. arXiv
_preprint arXiv:1905.09992, 2019._

D. Marbach, J. C. Costello, R. Küffner, N. M. Vega, R. J. Prill, D. M. Camacho, K. R. Allison,
M. Kellis, J. J. Collins, and G. Stolovitzky. Wisdom of crowds for robust gene network inference.
_Nature methods, 9(8):796–804, 2012._

K. L. Mengersen. Testing for mixtures: a bayesian entropic approach. Bayesian statistics, pages
255–276, 1996.

J. C. Miller. Percolation and epidemics in random clustered networks. Physical Review E, 80(2):
020901, 2009.

A. Montanari. Statistical mechanics and algorithms on sparse and random graphs. Lectures on
_Probability Theory and Statistics. Saint-Flour, 2013._

M. E. Newman. Random graphs with clustering. Physical review letters, 103(5):058701, 2009.

J. Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier,
2014.

P. Ravikumar, M. J. Wainwright, J. D. Lafferty, et al. High-dimensional ising model selection using
l1-regularized logistic regression. The Annals of Statistics, 38(3):1287–1319, 2010.

T. J. Richardson and R. L. Urbanke. The capacity of low-density parity-check codes under messagepassing decoding. IEEE Transactions on information theory, 47(2):599–618, 2001.

A. F. Smith and G. O. Roberts. Bayesian computation via the gibbs sampler and related markov chain
monte carlo methods. Journal of the Royal Statistical Society: Series B (Methodological), 55(1):
3–23, 1993.

J. S. Yedidia, W. T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations.
_Exploring artificial intelligence in the new millennium, 8:236–239, 2003._

S. Yoon, A. V. Goltsev, S. N. Dorogovtsev, and J. Mendes. Belief-propagation algorithm and the ising
model on networks with arbitrary distributions of motifs. Physical Review E, 84(4):041144, 2011.


-----

