Convergence of Generalized Belief Propagation Algorithm on Graphs with Motifs
Authors: Yitao Chen
Deepanshu Vasal
Venue: ICLR 2022 Submitted (2022)
Keywords: Belief Propagation
Bethe energy function

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.

Under review as a conference paper at ICLR 2021
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 run on loopy graphs in most upplications. So, understanding the behavior of belief propagation on loopy graphs has been major topic for researchers in different areas. In this paper, we study the convergence behavior of generalized belief propagation algorithm 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 motif's
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
F(X) = z exp 8 1 h2XX+ E J,,,,,))) (155
(I)
where (X:); E {+1]² are random variables valued in a binary alphabet (also known "spins"), Jij represents the pairwise interactions between spin and spin j. hy represents the external field for spin i, 3 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- Chakov Monte Carlo (MCMC) algorithms. A well-known example is Gibbs sampling, which is special case of the Metropolis-Hastings algorithm. Basically Gibbs sampling samples random variable conditioned the distribution based on the previous samples. It can be shown that Gibbs sampling generates reversible Markov chain of samples. Thus, the stationary distribution of the Markov chain the desired joint distribution over the random variables. and can be reached after the burn-in period. However, it is also well-known that Gibbs sampling will become trapped on multi-moda 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
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 effective numerical method for solving inference problems 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 Frry et al. (1998): ) Richardson

---

Under review as a conference paper at ICLR 2021
and Urbanke 20011, constraint satisfaction problems Achlioptas and Moore 2006), and community detection in the stochastic block model Decelle et al. 2011]. is well-known that belief propagation only exact for model 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 contributions.
Related work and our contribution
In classic work, Yedidia al. (2003) establishes the connection between belief propagation and the Bethe free energy. He shows that there 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 fixed point messages of belief propagation Montanari (2013). In recent work. Kochler (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 model of random graphs with arbitrary distributions of motifs. And Yoon et al. (201T) generalizes the Belief Propagation to graphs with motifs.
Our work builds generalized belief propagation graphs with motifs Yoon et al. (201T) and the convergence belief propagation on ferromagnetic Ising models on loopy graphs with simple edges 2019). In this paper, show for ferromagnetic Ising models 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 Ia] different motif's can be attached to vertex simple edge (i,j), a triangle, square, a pentagon, and other non-clique motifs. Graphs with motifs can be viewed as hyper-graphs where motifs play role of hyper-edges. And the number of specific motifs attached to vertex is equal to hyper-degres with respect to the specific motifs. In this paper, for simplicity, we only consider simple motifs such simple edges, and cliques.
Consider the Ising model with arbitrary order of interactions among vertices in each motif on hyper-graph. Let Mi(i) denote cluster of size I attached to vertex i, where vertices 12. ...,.... ft-1 together with form the motif. And let X denote the random variable of spin configurations, the Hamiltonian of the model
E(X) Σ N
EJx,X (1.5)
Σ JJJXXXXXX
Σ X (F...K.))
(2)
(.j.))
where the first sum corresponds to the external fields at each vertex, the second sum corresponds to the pairwise interactions 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 on. As discussed in the previous section, most previous works focus 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) = E1x Σ Xis
(3)
(f...)
where (i,j. k) is triangle, which can also be denoted as Ma(1), Ma(i), M2(k).
2

---

Under review as a conference paper at ICLR 2021
By Boltzmann's law, the joint distribution is defined by
P(X) 7 -B(())
(4)
where Z is the partition functionn.
Throughout this paper, focus on ferromggeticc Ising models, which defined below
Definition 1. An Ising model is ferromagnetic if Jesk 2 0 for all triangle motifs (i, k) and h; 2 0
for all i.
We introduce a intermediate message (Ms(() from motif Ma(i) to spin i.
(M,()(())) 2 cosh (AMa(1))
(5)
In the literature, different works have different definitions of messages. (Ma((0) is not the message definition we eventually work with in this paper, helps to understand the connections between different works. So, abusing the terminology little bit, we call it 'ineermediate message'.
By the definition of generalized Belief Propagation, the probability that spin is state X; is determined by the normalized product of incoming intermediate messages from motifs attached to spin and the external field factor e.
P.(X,)
Sh
II (Ma(1)
(M (X.,,
(6)
where A is a normalization constant. And the belief update rule is given by:
(Ma( (X.) =
Σ
(B(M)(0)
II
II
(X,),
(7)
(X,==I]
(Ma())/Maii)
where (i)) is an energy of the interaction among spins in the triangle Ma(i), and B is normalization constant.
Multiplying Equation 7 by X; and summing over all spin configurations, we obtain an equation for the effective field (M)
tanh (BAMs(t) Z(Ma(1) (x.-511..-11)
Σ
X5e -BE(M((0))
(a) Different motifs attached to vertex i
(b) Tree-like hyper-graph with triangle motifs only
Figure 1: Examples of hyper-graphs

---

Under review as a conference paper at ICLR 2021
where
2
B(M((i) E , Ji
(9)
Ac(5) hi
E AMsG):
(10)
(Ma())
Z(M₂(i)
Σ
DB(Ms(()
(11)
For more detailed explanations of Equations 7 to please refer to Yoon et al. (2011).
Now, define a message from spin i motif Ma (11+ tanh (() More specifically, if the motif (1 is triangle (i.j. k), the message can be alternatively represented as Mz
M4-jk (6)) From on, let the reciprocal temperature & = 1, can further simplify Equation as
V4++j tanh h4 +
tanh Gann-'(tanll (tanh Mn-inn)----nn---
(12)
(m,n)E0i) (J.A)
where di denotes the motifs attached to spin i. Equation 12 is the consistency equation for fixed
point hyper-edge messages vi-33 of the generalized belief propagation. Alternatively, denote Equation
12 as Vi+jjk ((V)s-jk-
BETHE FREE ENERGY OF HIGHER ORDER ISING MODELS
In order get the Bethe free energy of our higher order Ising model
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) (())E(()) Σ
(13)
= -UU(P)+S(2
(14)
where UPP) is called the average energy, and S(P) is the entropy.
We would like derive Gibbs free energy that is function of both the one-node beliefs (x:)) and the three-node beliefs Piya Ty, xx). The beliefs should satisfy the normalization conditions and the marginalization conditions. In other words, lies in the following polytope of locally consistent distributions
Σ Punlln,, (.(2)) for all triangles i, l 24
P((TT)) = for all
(15)
(, (E, .x) 2 for all triangles (i.j, k), and all 2;, Ty,
Because we only consider external fields and higher order interactions with triangles our model, the one-node and three-node belief's actually sufficient to determine the average energy. For our model ( and for any approximate joint probability P such that one-node marginal probabilities are (x(x)) and the three-node marginal probabilities are (I 2j, æk), ) the average energy will have the form
U(P) = Σ
Σ (SJ.R) 24
ΣΣ> Pa(as)afz
(16)
4

---

Under review as a conference paper at ICLR 2021
The average energy computed with the true marginal probabilities (I,) and Pūjx (2i, Ty 24)) will also have this form, so one-node and three-node beliefs are exact, the average energy given by Equation (66 will be exact.
For computing the entropy, we usually need an approximation. We can compute the entropy exactly can explicitly express the joint distribution P(z) in terms of the one-node and three-node beliefs. our graph were tree-like hyper-graph with triangle motifs only (see Fig. [b as an example), we can in fact do that. In that case, we can represent the joint probability distribution in the form
P(x) [L (ay
(17)
I1, P,(2))
where qi is the hyper-degree of node i.
Using Equation
17
get the Bethe approximation the entropy
Reehhe (P)
Σ
Σ
(2 Zy. 2h log Paja D.,
(f...) SK
+ Σ (q: 1) Σ P.(x,) PT(x,)
(18)
Combining Equation 16) and 18) we obtain the Bethe free energy
Bette P) (P() Seathe (P)
(19)
- JiykEp [x Σ h, [X,]
(b.ji))
+
Σ Hpp (X,, - > - (XH
(20)
(3.1.)
Notice when the hyper-graph is tree, the Bethe free energy Beah (P) will have the correct functional dependence on the beliefs. And solving the optimization problem: maximizing GBehe (P) over the polytope of locally consistent distribution (15) will give the true marginals. For loopy hyper-graphs, the Bethe free energy GBehh (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 add Lagrange multipliers to G (P) to form a Lagrangian L. Let λz-ojk (x;) be a multiplier that enforces the marginalization constraint Eny, (eja(T; Tjj xj, P. (x:)). and
A be multiplier that enforces the normalization of (x,)). So, the largrangian corresponding the optimization problem is
C (PP, A) GBethe PP) +
Σ
)z-sg((x) Σ (1s,( - -P((z))
(K..,8).
Σ
A
Pa(x;) 1)
(21)
where we ignore the constraints (x;). Payk Iz, 24) 2 because, given other constraints, those constraints are always satisfied at a critical point.
The equation (Paja() 0 gives:
log Paya 1z. = Jigkt,zz + As-ozk + Ay + Acc-nin (xx) -
(22)
Setting X/ di s1a(1) de s-(-1), find that at critical point of the Lagrangian that
Pinl(T,, Ix) exp Janrazy + de-oa( + dg ) + Ak (2x6)
(23)
exp Janastyn Manzk X1 XI Xk-
(24)
5

---

Under review as a conference paper at ICLR 2021
Al And the equation (*))
0 gives:
(q: 1)(1 + log P.(x)))=
Σ \x-ga((s) - h:w X
(25)
(i.RE
Setting N/ A 1ia(1)-A A x
we find that at critical point of the Lagrangian that
(.(x;)) & exp
Σ
h4
(26)
qi
(iR)E
h4
& exp
Σ
X=
Iz 9:
(27)
(J,))E
Furthermore, by differentiating with respect to X, we see that the marginalization constraints are satisfied. Therefore, for any triangle (i, k). Ex, (a 2f, (z)). Hence,
(1(
II EaE))
E
Pimm (E T.ns F.n.)
(28)
Σ exp
Σ
(Jimn + N + Xm- + X Xn
(29)
(m,n)
exp( Σ
Xmmma zii)
Σ
Σ (m,n)
(JennI + Xm- Im + X Xn-sim Fnn)
exp
{m,n)
(30)
So
exp(X/15a0; harr)) x Σ exp Σ
(Jimn + Xm--snmt X, (nmi
(31)
(m.n)
II
Σ exp (iint + Xm-sin + N An-tim Inn
(m.n)EOi)(A (1.)) 2m
(32)
Define Vi-zzk == tanh tanh(( we have
+ Vi-ajk
(33)
2
No + Vi-aak
Let
f(x;) = hunt
II
Σ
e Jamnthann No #m Nry vim
(34)
(m,m) Tmii
Then we see
Vi-zjk 1(1- ((-1)
(35)
f(-1+
= tanh
h4 +
tanh tanh-"(tanh (Jimn) (imnn)-n-innnniii vn-+im)
(36)
{m.n)e0rM
which is the BP consistency equation 12 derived in Section
Till this point, we represent the Bethe free energy in terms of beliefs corresponds to BP fixed points. In order analyze the behavior of the Bethe free energy at BP fixed points, need to represent the Bethe free energy in terms of the hyper-edge messages Vi-jkk which called dual Bethe free energy in the literature. First, have the following lemma.

---

Under review as a conference paper at ICLR 2021
Lemma 1. The dual Bethe free energy critical point can be defined by
Geethe (N) = Σ E(() E (e5H(A),
(37)
(K...)
where
F((A) = log Σ heae
II
Σ
elonntt th #f An sin Im ty vim
(38)
(m.n) Edi on
(A) log Σ
(39)
Proof. Recall the Bethe free energy
GRethe (P) -U(P) Spethe (P)
(40)
Σ
J [x,X + Σ h.p. [X,]
(41)
(K.ji))
+ Σ
HP Xx, Σ (9: - (X)
(42)
(b..k)
By rearranging terms, we have
Gethe (P) = Bethe (2) = F(()) Σ (b))(A),
(43)
(1.1.)
where
(((A) = B|
Σ
(J + Xm-
Xm +
Xn)]
(44)
(m.n)
Σ
Xmx - (9: (Xi(
(45)
Emi
and
(A) =[,,))),E Xj X₁ + Xy-si X/ Xx] + HX,,, Xx.Xx)
(46)
W.L..g., let us look at the term Fish (A), let f(X) = J it can be rewritten
X X,
X
Xx.
FAjx(A) = B[f(X)] Ellog Piga (Xi, X Xx))
(47)
e(()
Ellog Piya(Xi, (y, X
(48)
From Equation
4 we know
(X,, Xx. 1
(
(49)
Zijk
where Zisk is a normalization constant Zisk = Em, ex(), we have
Substitute it back into Equation
Figu (A) E[log (Z)z)) (og(Zyx)) log(
Σ
e((X))
(50)
llo Σ
(51)
L
we use the definition 1/-zkk := tanh (annh((_gx).. and define 9:ju- = tanhhJesk). we have the following corollary:
7

---

Under review as a conference paper at ICLR 2021
Corollary 1. The dual Bethe free energy in terms of hyper-edge messages is
Beethe (V) = Σ P((U)= Σ
Fegn(u),
(52)
(1...A)
where
F((v) = log
eh II
(1 + Imnn tin e-t (1
Pmmn Cm tin---nnni
(53)
m,n
m,,7
(A) log 1
(54)
4 OPTIMIZATION LANDSCAPE
Now, we can study the behavior of the Bethe free energy at critical points. The following lemma establishes that ((V):=ájk is a concave monotone function for some non-negative v.
Lemma 2. Suppose that f(x) tanh(h (h + E(.,) tanh manh-"(ae (x,22)) for any h 2 0. Then f is concave monotone function the domain [x", 1)".
Proof. Observe that
0f (x) Ox;
1- fx)(²
1 (I),;)² 2 2y 2 0,
(55)
which proves monotonicity, and
j (1) = (1 (z, (2)11))2)
1 1- f(x)²
2f(()))))) 1(k = j. i) + (x)
+ 1(k = i, = 1===;i,_(((__]])) 5)2(xoxr,)
(56)
Note that for any non-negative vector w, we let
v 1- f(x)2
wk / 1--((x) 2188
(z)z,)² Tyw,
(57)
1 (x
Then we have,
2 f
Σ
(58)
1
Σ w
-2((x) + 1[k = j,1 =1:=:] i)( =))-_
+ t2,1,) + 1(k = i, = -])2x,000 wk
(59)
i,k
= 2f(x)( Σ w + Σ
+ I1Rf)) + Σ wo 2004
(60)
(())
Σ (x) I, )w,
Σ
+ 3. - 2)(x))
(61)
11,01
(ij)
1 w!
Σ wkwu
+ x;00 - 25(x)
1 (1
(62)
f(x)
4i w
(1.5)
For any edge (i, let C
wt
+
1 w/
(note C C2 2/ ///9)))))
). and
w
95
((x)
1
2f(x))
1 1 C(1
f(x) )
x
x
(63)
8

---

Under review as a conference paper at ICLR 2021
Due to the fact < f(x), we know ((x) - - 0, and g(1) O. Since g(x) is continuous
over (0, 1), we assume 2;j is the largest root for g(x) (0, 1), we know g(ø) < in (zz 1). Let
x² (1,) z.y. we have
8
Σ
w/ dz,0z
wy S 0,
(64)
for x E [xt, 1)"
We define the set pre pre-fixpoints and post-foxpoinne messages similar as Koehler (2019)
Spre fv=x" S ((v)s-ck S Pi-gkh Spost {V x² S Ve-sh S o(v)-1jk)
(65)
From Lemma we know Spoat is a convex set, while Spre is typically non-convex and even dis- connected. Next, we show the gradient of the dual Bethe free energy is well-behaved on these sets:
Lemma 3. If 1 E Spre then V (V) S 0 and if v E Sport then VG (v) 2 0
Proof. The lemma will follow we compute the gradient of the dual Bethe free energy function Beethe (v).
(GBoahe(y) Öug-ii
(F((v)
(F))(())
diy-vik
dvz-tik
Im.neii((i) (1 mm in e eh -ux- II Immeooi(ii)) Ou mu mn-
eh 1Imm Om Un unmmm) e- h. II (1 Ov (n+im)
Ou 0Vi-skk'k-ár 1 j
(66)
Mj-iik + 1/(0uk ((0nn-iio(u))--:)) Mi-vik 1/(0ve -in vjkk)
Recall (()) updated message from spin to motif [i, k} based on the current messages v. I/ E Spre or Spost, then the signs of the gradient of Bethe free energy are determined by Equation (66)
as claimed.
Based on Lemma
2 andd we can prove our main theorem.
Theorem 1. Suppose that generalized BP is run from initial messages Vi-ijk and there is at least one fixed point in [x", The messages converge to a fixed point v" of the generalized BP equations such that for any other fixed point ph, Pi-tzk S Vi-agk Furthermore
(0)
Gienhe (v")
max Ghenhe
(67)
Proof. If there is least one fixed point (x*,1)) and the initialization is V for all hyper-edges {i, k.j.k].
k}. For each iteration of Belief Propagation, (+))) = ((v(t-1)).
From Lemma 2 we know o is monotonic on [x", 1)". So, p()) (1) (1)) ..... p(t) is a coordinate-wise decreasing sequence, which will converge to some fixed point. By monotonicity, we see that for any fixed point μa E 1)",
S 2-1jk for all Hence, it holds for 1² as well.
Finally, consider any other point v E Spoats by convexity of Spott we know that the line segment from to v" is entirely contained in Spos- By Lemma interpolating line segment that VGBethe())) (v* - v) 2 0, and integrating over this line segment gives GBehhe (v) < (v").
that for any point æ this

---

Under review as a conference paper at ICLR 2021
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 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, 106336)15274-15577, 2009.
B. Frey, J. F. Brendan, and B. 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.
Koehler. Fast convergence of belief propagation to global optima: Beyond correlation decay. arXiv preprint arXiv: 1905:v:9005009900 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. Collins, and G. Stolovitzky. Wisdom of crowds for robust gene network inference. Nature methods, 9())796-804, 2012.
K. L. Mengersen. Testing for mixtures: 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.
Pearl. Probabilistic reasoning intelligent systems: networks of plausible inference. Elsevier, 2014.
P. Ravikumar, M. J. Wainwright, J. D. Lafferty, et al. High-dimensional ising model selection using I1-regularized logistic regression. The Annals of Statistics, 38(3):1287-131,, 2010.
T. J. Richardson and R. L. Urbanke. The capacity of low-density parity-check codes under message- passing decoding. JEEE Transactions on information theory, 47(2):599-611 2001.
A. Smith and 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.
S. Yedidia, W. T. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. Exploring artificial intelligence in the millennium, 8:236-233 2003.
Yoon, A. V. Goltsev, N. Dorogovtsev, and J. Mendes. Belief- propagttonnnntion algorithm and the ising model on networks with arbitrary distributions of motifs. Physical Review E, 84(4):041 1444, 2011.
10


Reviews:
[{"review_id": "kb5ybk76qG2", "reviewer": "Reviewer_PMGJ", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "\nI have a suspicion that the proof of Lemma 2 of this paper is completely wrong.\nI would like the author to clarify the following points.\n\n1. The function $f$ is defined on a domain in n- dimensional space and the value is scalar.\n   Is the sum i is over 1 to n and the sum j is also over 1 to n.\n   Is this correct? (this just a sanity check.)\n\n2. First of all what is your policy on proving concavity?\n   Eq (64) does not imply concavity because w is limited to non-negative elements.\n   (recall that non-negative matrices are not necessarily positive semi-definite)\n\n3. The summation over $j$ is missing in Eq 55, and the summation over $j$ and $l$ are missing in Eq 56.\n    (or do you abbreviate them? if so I recommend not do it because it is confusing.)\n\n4. Again, Eq 57 look strange because the right hand side includes index j (resp. l) \n   but the left hand shows no dependency on j (resp l).\n   If you are omitting the sigma over j, I suggest you not do that because it is just confusing.\n\n5. In Eq 60, the third term has explicit dependency over index j.\n   This look wrong because the first and the second terms and Eq 58 has no dependency on j.   \n\n6. Can you explain how do you obtain Eq 61 from 60?\n\n7. Between Eq 62 and 63, the definition of C depends on indices i and j.\n   I recommended to use the notation $C_{ij}$ instead of $C$.\n   Likewise, I recommended to use the notation $g_{ij}$ instead of $g$.\n\n8. Is x in Eq 63 a scalar or a vector? \n   If it is a vector, how should I understand $1/x$?\n   If it is a scalar, I recommend to use other characters, say $t$, to avoid confusion.\n\n9. I believe the author tries to show each summand of Eq 62 is negative.\n   However I cannot obtain the summand by putting $x$ or $x_i x_j$ into g.\n\n10. Between Eq 63 and 64, what do you mean by $x < f(x)$? Is $x$ a vector or scalar?\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The main result of the paper, Theorem 1, is dependent on Lemma 2. Therefore, I would like to vote for rejection unless every single step of the proof of Lemma 2 is made clear.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "cbIAIKH0s4A", "reviewer": "Reviewer_bjzY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Clarity:  The paper contains a number of typos, but they do not affect understanding.  I found the presentation of the results to be counterintuitive and frustrating, with a number of definitions presented out of order.  Further the notation is incredibly cumbersome in places. e.g., M_3(i), even though there are perfectly good and much more well-established notational conventions that could (and should) be adopted.  Finally, a number of results are presented as if they are novel for this work, e.g., eqns 21-36, which is confusing as they are established results that could simply be included with appropriate citations.\n\nNovelty:  The final theoretical result appears to be novel, but the authors do a poor job of explaining which pieces are novel here or how this work relates to the previously established proof techniques, e.g., is this just a rehashing of the same arguments in a slightly more general case?\n\nSignificance:  While the result may be of interest, the proof techniques may possess only limited novelty and the practical applications are unclear.\n\nSpecific comments:\n\n- The citation style should be fixed.  Use (author year) instead of author (year) for parenthetical citations.\n- The notation in equation 3 is really challenging.  Is the sum over all possible 3 vertex combinations?  How do you distinguish two different triangles containing vertex i with the notation M_3(i)?\n- Why is h_i assumed to be greater than or equal to zero?  This isn't the same as the binary ferromagnetic case?\n- lambda is used in (5) before it is defined.  In fact, (5) is a complete non-sequitur and the presentation of the message passing scheme in general is difficult to follow.\n- I don't understand the notation phi(v_{i\\rightarrow jk).  It seems to be the same as (12) and only creates extra confusion in the discussion as it it several pages before it is used again.\n- Are (21)-(36) and Lemma 1 standard results?  I think this needs a citation at minimum.\n- How does Lemma 2 differ from the approach in previous work?  Indeed, how does anything here differ from the previous approach?", "summary_of_the_paper": "The authors extend a result for BP on ferromagnetic Ising models to BP on higher order Ising models.  This is a purely theoretical result.", "summary_of_the_review": "An interesting result that seems to rehashing a significant amount of existing work without citation, is hampered by a poor presentation, and is not careful to place itself in the context of existing results.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "QDqF_Wouup", "reviewer": "Reviewer_F8Ar", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "Studying the convergence behavior of belief propagation and generalized belief propagation is an ongoing research topic, with many aspects still being not well understood. The paper tackles this important problem and provides a favorable initialization strategy for a special types of models. That being said, the novelty of the current paper is limited and the findings only apply to a restricted setting (more precisely, Theorem 1 is analogous to Lemma 3.3 in [Koehler]. The proofs are also analogous. While the authors claim that the results generalize to a more general case, this seems not to be the case); moreover, the notation and terminology is often imprecise (to the point of being misleading); finally, the paper fails to reference important related work -- both classical papers on belief propagation as well as recent advances. More details are presented below.\n\n## Limitations\nI completely understand that one has to make certain model assumptions to prove something formally. But this paper makes model assumptions for which it has already been established (at least for plain BP) that the most accurate fixed point is the one aligned with the local potentials ([Koehler] and [4]). Since the energy landscape is also well understood in this scenario (see for example [4] and [8]) it comes as no surprise that the convergence results of [Koehler] can be generalized. The result would be stronger if it would hold for any choice of regions (motifs). From the derivations presented, this does not seem to hold. Alternatively, making certain statements about the energy landscape of generalized BP for models with frustrations or arbitrary local potentials and how considering certain motifs might render the originally non-convex free energy convex would be of great interest.\n\n## Notation/Terminology\nThe Bethe free energy is only defined over pairs of random variables. The generalization to larger groups of variables is named Kikuchi free energy.\nIt is repeatedly stated that Ising models with an external field are considered but the equations always consider local fields. The major difference is that local fields are potentially different for every variable, i.e., we have $h_i$, whereas an external field is equivalent over all variables, i.e., we have $h_i=h$\nThe summation indices $(i,j), (i,j,k),...$  are used imprecise. One must ensure that every pair, triplet,... contributes only once to the energy (or normalize the energy accordingly).\nThe ferromagnetic model is not used consistently throughout the literature. Whereas [1] refers to ferromagnetic models whenever $J_{ij}>0$, [6] has the same definition as in this paper.\nEquation 5 uses $\\lambda(\\ldot)$ that has never been introduced.\nI cannot make sense of the double product in Equation 7. I would expect that the first product should go over all neighbors of $i$ (except for $M3(j)$) but not over all variables as stated here.\n\n## Related Work\nThe generalization of the Bethe free energy to higher models in Section 3 is not novel. This is precisely the Kikuchi free energy.\nThe derivations in Section 3 are a straightforward generalization of the classical derivations for the Bethe free energy in [2].\nThe claim that there are not guarantees on how close the beliefs at the \"best\" fixed point is to the exact one are not entirely correct (see [5] and [7]).\nThe accumulation of the effect from multiple variables into one message seems similar to the concept of the effective field in [5].\nMinor Remarks\nThe terms \"variable\" and \"spin\" are used interchangeably. Sticking to one form would improve the clarity.\nIn line 72 $X$ denotes the random variable. In the remaining paper it is always $X_i$\n.\nline 86: Ising models, which is defined -> which are defined\nPlease fix the references. [Koehler] for example has been published at this very conference (NeurIPS) and is not just an arXiv preprint.\n[1] Mooij, Joris, and Hilbert Kappen. \"Sufficient conditions for convergence of loopy belief propagation.\" (2012).\n\n[2] Heskes, Tom. \"On the uniqueness of loopy belief propagation fixed points.\" (2004).\n\n[3] Meltzer, Talya, Amir Globerson, and Yair Weiss. \"Convergent message passing algorithms-a unifying view.\" (2009).\n\n[4] Knoll, Christian, Adrian Weller, and Franz Pernkopf. \"Self-Guided Belief Propagation--A Homotopy Continuation Method.\" (2018).\n\n[5] Knoll, Christian, and Franz Pernkopf. \"Belief Propagation: Accurate Marginals or Accurate Partition Function–Where is the Difference?.\" (2020).\n\n[6] Saade, Alaa, Florent Krzakala, and Lenka Zdeborová. \"Spectral clustering of graphs with the bethe hessian.\" (2014).\n\n[7] Ihler, Alexander, John Fisher, and Alan Willsky. \"Loopy Belief Propagation: Convergence and Effects of Message Errors\"\n\n[8] Zachary Pitkow, Yashar Ahmadian, Ken Miller. \"Learning unbelievable probabilities\"", "summary_of_the_paper": "The paper considers attractive models with unidirectional local potentials and studies a special case of generalized belief propagation, namely over triplets of graphs. For this model class, the paper generalizes the convergence results from [Koehler]. ", "summary_of_the_review": "The paper generalizes the findings of [koehler] to one specific and restricted setting. The technical results are derived analogously to [koehler] and it is not clear how (or if) the findings would generalize; neither to more general potentials nor to more general versions of generalized belief propagation.\nMoreover, the paper has sever issues regarding clarity and deviates from the classical literature in its clarity. Also, the related work is not cited adequately. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "1A6TqfJ09h1", "reviewer": "Reviewer_BLzF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "This paper studies the Ising model, which is perhaps one of the most popular undirected graphical models (also known as Markov Random Fields). The authors study the belief propagation for solving inference problems on graphical models. It is known that BP produces exact solution on trees and locally tree-like graphs. The main contribution of this paper is to study the convergence behavior of BP on loopy graphs.\n\nThe authors study the Ising model on graphs with motifs. For such models, every vertex is associated with motifs that can be edges, triangles, squares, etc. The Hamiltonian is given by summing over all motifs and for each motif taking a product of spins. One can also view such a model as an Ising model on a hypergraph. The authors give detailed proofs to show that the generalized BP run from the initial all one message converges to a fixed point whose Bethe free energy is maximum. In fact, in the proof of this paper the authors only consider triangle motifs, so the Hamiltonian is a sum over all triangles. It is reasonable to infer that the same proof approach works for larger motifs as well.\n\nOne weakness of this paper is that the latter half of the paper is mainly proofs based and it is a little bit hard to follow the intuitions of results. Also, the main convergence result does not seem to say anything about the time it takes for the generalized BP to convergence. This could be disappointing to some people for application reasons as I suspect that the convergence time would increase with the size of the motifs, and that the convergence result might not be so meaningful for motifs with non-constant sizes. In that sense, and also given the known convergence results of BP for Ising (Koehler’19), the main result of this paper is not so impressive.\n", "summary_of_the_paper": "This paper studies the convergence behavior of the generalized belief propagation algorithm on graphs with motifs. The authors show that when initialized as the all one message, the generalized belief propagation will converge to some fixed point that maximizes the Bethe free energy.\n", "summary_of_the_review": "This is an interesting paper but I hope the authors can improve their presentations of their main results by removing some proofs to the supplementary materials and include more intuitions and novelty compared to previous works like Koehler’19. Also it is reasonable to include a study on the convergence rate of generalized BP, either theoretical or experimental. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers are very critical about the submitted paper regarding novelty of results, insufficient placement with respect to existing results, and clarity of presentation. The authors also did not submit a rebuttal. Hence I am recommending rejection of the paper.
Decision: Reject