# Exact Fractional Inference via Re-Parametrization & Interpolation
between Tree-Re-Weighted- and Belief Propagation- Algorithms

Hamidreza Behjoo  Michael Chertkov

###### Abstract

Inference efforts – required to compute partition function, $Z$, of an Ising
model over a graph of $N$ “spins” – are most likely exponential in $N$.
Efficient variational methods, such as Belief Propagation (BP) and Tree Re-
Weighted (TRW) algorithms, compute $Z$ approximately minimizing respective
(BP- or TRW-) free energy. We generalize the variational scheme building a
$\lambda$\- fractional- homotopy, $Z^{(\lambda)}$, where $\lambda=0$ and
$\lambda=1$ correspond to TRW- and BP-approximations, respectively, and
$Z^{(\lambda)}$ decreases with $\lambda$ monotonically. Moreover, this
fractional scheme guarantees that in the attractive (ferromagnetic) case
$Z^{(TRW)}\geq Z^{(\lambda)}\geq Z^{(BP)}$, and there exists a unique
(“exact”) $\lambda_{*}$ such that, $Z=Z^{(\lambda_{*})}$. Generalizing the re-
parametrization approach of (Wainwright et al., 2001) and the loop series
approach of (Chertkov & Chernyak, 2006a), we show how to express $Z$ as a
product, $\forall\lambda:\ Z=Z^{(\lambda)}{\cal Z}^{(\lambda)}$, where the
multiplicative correction, ${\cal Z}^{(\lambda)}$, is an expectation over a
node-independent probability distribution built from node-wise fractional
marginals. Our theoretical analysis is complemented by extensive experiments
with models from Ising ensembles over planar and random graphs of medium- and
large- sizes. The empirical study yields a number of interesting observations,
such as (a) ability to estimate ${\cal Z}^{(\lambda)}$ with $O(N^{4})$
fractional samples; (b) suppression of $\lambda_{*}$ fluctuations with
increase in $N$ for instances from a particular random Ising ensemble.

Graphical Model, Partition Function, Free Energy, Tree Re-Weighted, Belief
Propagation, Reparametrizations, MCMC, Monotonicity, Convexity

##  1 Introduction

Graphical Models (GM) is a major tool of Machine Learning which allows to
express complex statistical correlations via graphs. Ising models are most
wide-spread GM expressing correlation between binary variables associated with
nodes of a graph where probability is factorized into a product of terms each
associated with an undirected edge of the graph. Many methods of inference and
learning in GM are, first, tested on Ising models and then generalized, e.g.
beyond binary and pair-wise assumptions.

In this manuscript we focus on the most difficult inference problem –
computing the normalization factor, $Z$, – called partition function – over
the Ising models. The problem is known to be of the sharp-P complexity, that
is likely requiring computational efforts which are exponential in the size
(number of nodes, $N$) of the graph (Welsh, 1991; Jerrum & Sinclair, 1993).
There are three general approximate methods to compute $Z$: (a) elimination of
(summation over) the variables one-by-one (Dechter, 1999; Dechter & Rish,
2003; Liu & Ihler, 2011; Ahn et al., 2018); (b) variational approach (Yedidia
et al., 2001, 2005); (c) Monte Carlo (MS) sampling (Andrieu et al., 2003).
(See also reviews (Wainwright & Jordan, 2007; Chertkov, 2023) and references
there in.) In this manuscript we develop the last two of the methods. We also
pay a special attention to providing and tightening approximation guarantees.
We build our novel theory and algorithm on the provable upper bound for $Z$
associated with the so-called Tree Re-Weighted (TRW) variational approximation
(Wainwright, 2002; Wainwright et al., 2003, 2005) and also on the Belief
Propagation (BP) variational approximation (Yedidia et al., 2001, 2005) which
is known to provide low bound on $Z$ in the case of attractive (ferromagnetic)
Ising model (Ruozzi, 2012).

###  1.1 Relation to Prior Work

In addition to the aforementioned relations to foundational work on the
variational approaches (Yedidia et al., 2001, 2005), MCMC approaches (Andrieu
et al., 2003), and lower and upper variational bounds (Ruozzi, 2012;
Wainwright et al., 2003), this manuscript also builds on recent results in
other related areas, in particular:

  * •

We extend the ideas of parameterized homotopy, interpolating between BP
(Yedidia et al., 2001, 2005) and TRW (Wainwright, 2002; Wainwright et al.,
2003, 2005), in the spirit of the fractional BP (Wiegerinck & Heskes, 2002;
Chertkov & Yedidia, 2013), and therefore introducing a broader family of
variational approximations.

  * •

We utilize and generalize re-parametrization (Wainwright et al., 2001), gauge
transformation and loop calculus (Chertkov & Chernyak, 2006a, b; Chertkov et
al., 2020) techniques, as well as the combination of the two (Willsky et al.,
2007).

  * •

Our approach is also related to development of the MCMC techniques with
polynomial guarantees, the so-called Fully Randomized Polynomial Schemes
(FPRS), developed specifically for Ising models of a specialized, e.g.
attractive (Jerrum & Sinclair, 1993) and zero-field, planar (Gómez et al.,
2010; Ahn et al., 2016) types.

###  1.2 This Manuscript Contribution

We introduce fractional variational approximation interpolating between, by
now classical, Tree Re-Weighted (TRW) and Belief Propagation (BP) cases. The
fractional free energy, $\bar{F}^{(\lambda)}=-\log Z^{(\lambda)}$, defined as
minus logarithm of the fractional approximation to the exact partition
function, $Z=\exp(-\bar{F})$, requires solving an optimization problem, which
is achieved practically by running a fractional version of one of the standard
message-passing algorithm. Basic definitions, including problem formulation
for the Ising models and variational formulation in terms of the node and edge
beliefs (proxies for the respective exact marginal probabilities), are given
in Section 2. Assuming that the fractional message-passing algorithm converges
we study dependence of the Bethe Free energy on the fractional parameter,
$\lambda$, and relation between the exact value of the free energy (minus
logarithm of the exact partition function) and the fractional free energy. We
report the following theoretical results:

  * •

We show in Section 3 that $\bar{F}^{(\lambda)}$ is a continuous and monotone
function of $\lambda$ (Theorem 3.1 proved in Appendix B) which is also convex
in $\lambda$ (Theorem 3.2 proved in Appendix C).

  * •

Our main theoretical result, Theorem 4.1, presented in Section 4 and proven in
Appendix D, states that the exact partition function can be expressed as a
product of the variational free energy and of the multiplicative correction,
$Z=Z^{(\lambda)}{\cal Z}^{(\lambda)}$. The latter multiplicative correction
term, ${\cal Z}^{(\lambda)}$, is stated as an explicit expectation of an
expression over a well defined “mean-field” probability distribution, where
both the expression and the “mean-field” probability distribution are stated
explicitly in terms of the fractional node and edge beliefs.

The theory is extended with experiments reported in Section 5. Here we show,
in addition to confirming our theoretical statements (and thus validating our
simulation settings) that:

  * •

Dependence of $\bar{F}^{(\lambda)}$ and $\log{\cal Z}^{(\lambda)}$ on
$\lambda$ is of a phase transition type when we move from the TRW regime at
$\lambda=0$ to the BP regime at $\lambda>\bar{\lambda}$.

  * •

Evaluating $Z^{(\lambda)}{\cal Z}^{(\lambda)}$ at different values of
$\lambda$ and confirming that the result is independent of $\lambda$ suggests
a novel approach to reliable and efficient estimate of the exact $Z$.

  * •

Analyzing ensembles of the attractive Ising Models over graphs of size $N$ we
observe that fluctuations of the value of $\lambda_{*}$ within the ensemble,
where $Z^{(\lambda_{*})}=Z$, decreases dramatically with increase in $N$. This
observation suggest that estimating $\lambda_{*}$ for an instance from the
ensemble allows efficient approximate evaluation of $Z$ for any other
instances from the ensemble.

  * •

Studying the sampling procedure to estimate ${\cal Z}^{(\lambda)}$, we observe
that the number of samples required for the estimate is either independent on
the system size, $N$, or possibly grows relatively weekly with $N$. This
observation confirms that our approach to estimation of $Z$, consisting in
evaluation of $Z^{(\lambda)}$ by a message-passing, then followed by drawing a
small number of samples to estimate the correction, ${\cal Z}^{(\lambda)}$, is
sound.

  * •

Analysis of the mixed Ising ensembles (where attractive and repulsive edges
alternate) suggests that for instances with sufficiently many repulsive edges
finding, $\lambda_{*}\in[0,1]$ may not be feasible.

We have a brief discussion of conclusions and path forward in Section 6.

##  2 Technical Preliminaries

###  2.1 Ising Models: the formulation

Graphical Models (GM) are the result of a marriage between probability theory
and graph theory designed to express a class of high-dimensional probability
distribution which factorize in terms of products of lower dimensional
factors. The Ising model is an exemplary GM defined over an undirected graph,
${\cal G}=({\cal V},{\cal E})$. The Ising Model is stated in terms of binary
variables, $x_{a}=\pm 1$, and singleton factors, $h_{a}\in\mathbb{R}$,
associated with nodes of the graph, $a\in{\cal V}$ and pair-wise factors,
$J_{ab}\in\mathbb{R}$, associated with edges of the graph, $(a,b)\in{\cal E}$.
The probability distribution of the Ising model observing a state,
${\bm{x}}=(x_{a}|a\in{\cal V})$ is

$\displaystyle p({\bm{x}}|{\bm{J}},{\bm{h}})$
$\displaystyle=\frac{\exp\left(-E\left({\bm{x}};{\bm{J}},{\bm{h}}\right)\right)}{Z({\bm{J}},{\bm{h}})},$
(1) $\displaystyle Z({\bm{J}},{\bm{h}})$
$\displaystyle\doteq\sum\limits_{{\bm{x}}\in\\{\pm 1\\}^{|{\cal
V}|}}\exp\left(-E\left({\bm{x}};{\bm{J}},{\bm{h}}\right)\right),$ (2)
$\displaystyle E\left({\bm{x}};{\bm{J}},{\bm{h}}\right)$
$\displaystyle\doteq\sum\limits_{(a,b)\in{\cal E}}E_{ab}(x_{a},x_{b}),$ (3)
$\displaystyle\forall(a,b)\in{\cal E}:$ $\displaystyle\
E_{ab}=-J_{ab}x_{a}x_{b}-(h_{a}x_{a}+h_{b}x_{b})/2,$ (4)

where ${\bm{J}}\doteq(J_{ab}|(a,b)\in{\cal E}),\ {\bm{h}}=(h_{a}|a\in{\cal
V})$ are the pair-wise and singleton vectors, assumed given,
$E({\bm{x}};{\bm{J}},{\bm{h}})$ is the energy function and
$Z({\bm{J}},{\bm{h}})$ is the partition function. Solving the Ising model
inference problem means computing $Z$ – which is, generally, requires efforts
which are exponential in $N=|{\cal V}|$.

###  2.2 Exact Variational Formulation

Exact variational approach to computing $Z$ consists in restating Eq. (2) in
terms of the following Kullback-Leibler distance between
$\exp(-E({\bm{x}};{\bm{J}},{\bm{h}}))$ and a probe probability distribution,
${\cal B}({\bm{x}})\in[0,1]^{|{\cal V}|},\ \sum_{\bm{x}}{\cal
B}(({\bm{x}})=1$, called belief:

$\displaystyle\bar{F}\\!=\\!-\\!\log Z\\!=\\!\min\limits_{{\cal
B}({\bm{x}})}\\!\sum\limits_{{\bm{x}}}\left(E({\bm{x}}){\cal
B}({\bm{x}})\\!-\\!{\cal B}({\bm{x}})\log{\cal B}({\bm{x}})\right),$ (5)

where $\bar{F}$ is also called (following widely accepted physics terminology)
the free energy.

The exact variational formulation (5) is the starting point for approximate
variational formulations, such as BP (Yedidia et al., 2005) and TRW
(Wainwright & Jordan, 2007), stated solely in terms of the marginal beliefs
associated with nodes and edges, respectively:

$\displaystyle\forall a\in{\cal V},\ \forall x_{a}:\ {\cal
B}_{a}(x_{a})\doteq\sum\limits_{{\bm{x}}\setminus x_{a}}{\cal B}({\bm{x}}),$
(6) $\displaystyle\forall(a,b)\in{\cal E},\ \forall x_{a},x_{b}:\ {\cal
B}_{ab}(x_{a},x_{b})\doteq\\!\\!\sum\limits_{{\bm{x}}\setminus(x_{a},x_{b})}{\cal
B}({\bm{x}}).$ (7)

Moreover, _fractional_ approach developed in this manuscript provides
variational formulation in terms of the marginal probabilities generalizing
(and, in fact, interpolating between) respective BP and TRW approaches.
Therefore, we now turn to stating the fractional variational formulation.

###  2.3 Fractional Variation Formulation

Let us introduce a fractional-, or $\lambda$\- _reparametrization_ of the
belief (proxy for the probability distribution of ${\bm{x}}$)

$\displaystyle{\cal B}^{(\lambda)}({\bm{x}})=\frac{\prod_{\\{a,b\\}\in{\cal
E}}\left({\cal
B}_{ab}(x_{a},x_{b})\right)^{\rho^{(\lambda)}_{ab}}}{\prod_{a\in{\cal
V}}\left({\cal B}_{a}(x_{a})\right)^{\sum_{b\sim a}\rho^{(\lambda)}_{ab}-1}},$
(8)

where $b\sim a$ is a shortcut notation for $b$ such that, given $a\in{\cal
V}$, $(a,b)\in{\cal E}$. Here in Eq. (8), $\rho^{(\lambda)}_{ab}$ is the
$\lambda$-parameterized edge appearance probability

$\rho^{(\lambda)}_{ab}=\rho_{ab}+\lambda(1-\rho_{ab}),\quad\lambda\in[0,1].$
(9)

which is expressed via the $\lambda=0$ edge appearance probability,
$\rho_{ab}$, dependent on the weighted set of the spanning trees, ${\cal
T}\doteq\\{T\\}$, of the graph according to the following TRW rules
(Wainwright & Jordan, 2007):

$\displaystyle\forall(a,b)\in{\cal V}:\ \rho_{ab}=\\!\\!\\!\sum_{T\in{\cal
T},\text{ s.t. }(a,b)\in T}\\!\\!\\!\rho_{T},\ \sum_{T\in{\cal T}}\rho_{T}=1.$
(10)

A number of remarks are in order. First, $\lambda=1$ corresponds to the case
of BP. Then Eq. (8) is exact in the case of a tree graph, but it can also be
considered as a (loopy) BP approximation in general. Second, and as mentioned
above, $\lambda=0$, corresponds to the case of TRW. Third, the newly
introduced (joint) belief is not globally consistent, i.e.
$\sum_{{\bm{x}}}{\cal B}^{(\lambda)}({\bm{x}})\neq 1$ for any $\lambda$,
including the $\lambda=0$ (TRW) and $\lambda=1$ (BP) cases.

Substituting Eq. (8) into Eq. (5) we arrive at the following fractional
approximation to the exact free energy stated as an optimization over all the
node and edge marginal beliefs, ${\cal\bm{B}}\doteq({\cal
B}_{ab}(x_{a},x_{b})|\forall\\{a,b\\}\in{\cal E},\ x_{a},x_{b}=\pm
1)\cup({\cal B}_{a}(x_{a})|\forall a\in{\cal V},\ x_{a}=\pm 1)$

$\displaystyle\bar{F}^{(\lambda)}\doteq\min\limits_{{\cal\bm{B}}\in{\cal
D}}F^{(\lambda)}({\cal\bm{B}}),\ F^{(\lambda)}({\cal\bm{B}})\doteq
E({\cal\bm{B}})-H^{(\lambda)}({\cal\bm{B}}),$ (11) $\displaystyle
E({\cal\bm{B}})\\!\doteq\\!\sum\limits_{(a,b)\in{\cal
E}}\sum\limits_{x_{a},x_{b}=\pm 1}E_{ab}(x_{a},x_{b}){\cal
B}_{ab}(x_{a},x_{b}),$ (12) $\displaystyle
H^{(\lambda)}({\cal\bm{B}})\doteq-\sum\limits_{(a,b)\in{\cal
E}}\rho^{(\lambda)}_{ab}\sum\limits_{x_{a},x_{b}=\pm 1}{\cal
B}_{ab}(x_{a},x_{b})\log{\cal B}_{ab}(x_{a},x_{b})$
$\displaystyle+\sum\limits_{a\in{\cal V}}\left(\sum_{b\sim
a}\rho^{(\lambda)}_{ab}\\!-\\!1\right)\sum\limits_{x_{a}=\pm 1}{\cal
B}_{a}(x_{a})\log{\cal B}_{a}(x_{a}),$ (13) $\displaystyle{\cal
D}\doteq\left({\cal\bm{B}}\left|\begin{array}[]{lr}{\cal
B}_{a}(x_{a})=\sum_{x_{b}=\pm 1}{\cal B}_{ab}(x_{a},x_{b}),&\\\ \hskip
5.69046pt\forall a\in{\cal V},\ \forall b\sim a,\ \forall x_{a}=\pm 1;&(a)\\\
\sum_{x_{a},x_{b}=\pm 1}{\cal B}_{ab}(x_{a},x_{b})=1,&\\\ \hskip
5.69046pt\forall(a,b)\in{\cal E};&(b)\\\ {\cal B}_{ab}(x_{a},x_{b})\geq 0,&\\\
\hskip 5.69046pt\forall(a,b)\in{\cal E},\ \forall x_{a},x_{b}=\pm
1.&(c)\end{array}\right.\right).$ (20)

The optimization over beliefs in Eq. (11) can be restated in the Lagrangian
form (see Appendix A.1). Fixed points of the Lagrangian (potentially many)
satisfy the so-called message-passing equations (see Appendix A.2). Then, the
fractional free energy (partition function) is given, consistently with all
the formulas from the Appendices A.1,A.2, by

$\displaystyle
Z^{(\lambda)}=\exp\left(-\bar{F}^{(\lambda)}\right)=\exp\left(-F^{(\lambda)}({\cal
B}^{(\lambda)})\right)$ (21) $\displaystyle=\prod\limits_{\\{a,b\\}\in{\cal
E}}\Big{(}\sum\limits_{x_{a},x_{b}}\exp\left(-\frac{E_{ab}(x_{a},x_{b})}{\rho^{(\lambda)}_{ab}}\right)\times$
$\displaystyle\left(\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{\frac{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}{\rho^{(\lambda)}_{ab}}}\left(\mu^{(\lambda)}_{a\to
b}(x_{b})\right)^{\frac{\sum\limits_{c\sim
b}\rho^{(\lambda)}_{bc}-1}{\rho^{(\lambda)}_{ab}}}\Big{)}^{\rho^{(\lambda)}_{ab}}\times$
$\displaystyle\prod\limits_{a\in{\cal
V}}\left(\sum\limits_{x_{a}}\prod\limits_{b\sim a}\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{1-\sum\limits_{c\sim a}\rho^{(\lambda)}_{ac}}.$

##  3 Properties of the Fractional Free Energy

Given construction of the fractional free energy, described above in Section
2.3 and also detailed in Appendix A, we are ready to make the following
statements about the fractional free energy.

######  Theorem 3.1.

[Monotonicity of the Fractional Free Energy] Assuming
${\bm{\rho}}\doteq(\rho_{ab}|(a,b)\in{\cal E})$ is fixed,
$\bar{F}^{(\lambda)}$ is a continuous, monotone function of $\lambda$.

###### Proof.

See Appendix B. ∎

######  Theorem 3.2.

[Convexity of Fractional] Assuming ${\bm{\rho}}\doteq(\rho_{ab}|(a,b)\in{\cal
E})$ is fixed and the model is attractive, $\bar{F}^{(\lambda)}$ is a convex
function of $\lambda$.

###### Proof.

See Appendix C. ∎

Notice that all the statements of this manuscript so far are made for an
arbitrary Ising models, i.e. without any restrictions on the graph and vectors
of the pair-wise interactions, ${\bm{J}}$ and singleton biases, ${\bm{h}}$. It
appears that if the discussion is limited to attractive (ferromagnetic) Ising
models, $\forall(a,b)\in{\cal E}:\ J_{ab}\geq 0$, the following statement
becomes a corollary of the Theorem 3.1

######  Lemma 3.3.

[Exact Fractional] In the case of an attractive Ising model and any fixed
${\bm{\rho}}$ there exists $\lambda_{*}\in[0,1]$ such that,
$Z^{(\lambda_{*})}=Z$.

###### Proof.

Recall that by construction, $Z^{(\lambda=1)}\leq Z$, as proven in (Ruozzi,
2012). In words, the partition function computed within the Bethe (BP)
approximation results in a lower bound to the exact partition function. On the
other hand, we know from (Wainwright & Jordan, 2007), and also by
construction, that $Z^{(\lambda=0)}\geq Z$, i.e. TRW estimate of the partition
function provides an upper bound to the exact partition function. These low
and upper bounds, combined with the monotonicity of $Z^{(\lambda)}$ stated in
Theorem 3.1 results in the desired statement. ∎

##  4 Fractional Re-Parametrization for Exact Inference

######  Theorem 4.1.

[Exact Relation Between $Z$ and $Z^{(\lambda)}$]

$\displaystyle Z$ $\displaystyle=Z^{(\lambda)}{\cal Z}^{(\lambda)},$ (22)
$\displaystyle{\cal Z}^{(\lambda)}$
$\displaystyle\doteq\sum\limits_{{\bm{x}}}\frac{\prod\limits_{\\{a,b\\}\in{\cal
E}}\left({\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b})\right)^{\rho^{(\lambda)}_{ab}}}{\prod\limits_{a\in{\cal
V}}\left({\cal B}^{(\lambda)}_{a}(x_{a})\right)^{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}}$ (23) $\displaystyle=\mathbb{E}_{{\bm{x}}\sim
p^{(\lambda)}_{0}(\cdot)}\left[\frac{\prod\limits_{\\{a,b\\}\in{\cal
E}}\left({\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b})\right)^{\rho^{(\lambda)}_{ab}}}{\prod\limits_{a\in{\cal
V}}\left({\cal B}^{(\lambda)}_{a}(x_{a})\right)^{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}}}\right],$

where the fractional BP expression for the partition function,
$Z^{(\lambda)}$, is defined in Eq. (21);
$p^{(\lambda)}_{0}({\bm{x}})\doteq\prod_{a}{\cal B}^{(\lambda)}_{a}(x_{a})$ is
the component-independent distribution devised from the FBP-optimal node-
marginal probabilities.

###### Proof.

See Appendix D ∎

Notice that ${\cal Z}^{(\lambda)}$, defined in Eq. (23), is the exact
multiplicative correction term, expressed in terms of the FBP solution, which
should be equal to $1$ at the optimal value of $\lambda^{*}(J,H)$, which is
achievable, according to Lemma 3.3, in the case of the attractive Ising model.

##  5 Numerical Experiments

###  5.1 Setting, Use Cases and Methodology

In this Section we present results of our numerical experiments – supporting
and also developing further theoretical results of the preceding Sections.
Specifically, we will describe details of our experiments with the Ising model
in the following “use cases”: (1) Over exemplary planar graph – $N\times N$
square grid, where $N=[3::25]$; (2) Over a fully connected graph, $K_{N}$,
where $N=[3::8^{2}]$. In both cases we consider attractive models and mixed
models – that is the models with some interactions being attractive
(ferromagnetic), $J_{ab}>0$, and some repulsive (antiferromagnetic),
$J_{ab}<0$. We experiment with the zero-field case, ${\bm{h}}=0$, and also
with the general (non-zero field) case. All of our models are “disordered” in
the sense that we have generated samples of random ${\bm{J}}$ and ${\bm{h}}$.
Specifically, in the attractive (mixed) case components of ${\bm{J}}$ are
i.i.d. from the uniform distribution, $\mathcal{U}(0,1)$
($\mathcal{U}(-1,1)$), and components of ${\bm{h}}$ are i.i.d. from
$\mathcal{U}(-1,1)$. In some of our experiments we draw a single instance of
${\bm{J}}$ and ${\bm{h}}$ from the respective ensemble. However, in other
experiments – aimed at analysis of the variability within the respective
ensemble – we show results for a number of instances.

We know that there is a big freedom in selecting a set of spanning trees and
then re-weighting respective contributions to
${\bm{\rho}}\doteq(\rho_{ab}|(a,b)\in{\cal E})$ according to Eq. (10). (See
some discussion of the experiments with possible ${\bm{\rho}}$ in (Wainwright
et al., 2005). However, we decided not to test the freedom, and instead, in
all of our experiments ${\bm{\rho}}$ is chosen unambiguously for a given graph
uniformly. As shown in (Wainwright, 2002), the edge-uniform re-weighting is
optimal, i.e. it provides the lowest TRW upper-bound, in the case of highly
symmetric graphs, such as fully connected or double-periodic square grid. It
was also assumed in the TRW literature (but to the best of our knowledge never
proven) that the edge-uniform re-weighting is (almost always) possible. We
clarify this point in the following statement.

######  Lemma 5.1.

([Edge-uniform Weights]) For any graph with all nodes of degree two or higher
there exists a subset of spanning trees, such that each edge contributes at
least one spanning tree, and the edge weight is calculated according to the
edge-uniform rule: $\forall(a,b)\in{\cal
V}:\quad\rho_{ab}=(|\mathcal{V}|-1)/|\cal E|$, where $|\cal V|$ is the number
of vertices and $|\cal E|$ is the number of edges 111The “degree two or
higher” constraint on nodes is not restrictive, because we can either
eliminate nodes with degree one (and also tree-like branches associated with
them) by direct summation, or alternatively include the tree like branches in
the appropriate number of spanning trees constructed for the graph ignoring
the tree-like branches..

###### Proof.

See Appendix E for constructive proof. ∎

To compute fractional free energy, $\bar{F}^{(\lambda)}$ (minus log of the
fractional estimate for partition function), we generalize approach of (Bixler
& Huang, 2018) which allows efficient, sparse-matrix based, implementation.
Our code will be made available at github upon acceptance of the paper.

To compare the fractional estimate $\bar{F}^{(\lambda)}=-\log Z^{(\lambda)}$,
with the exact free energy, $\bar{F}=-\log Z$, we either use direct
computations (feasible for the $8\times 8$ grid or smaller and for the fully
connected graph over $64$ nodes or smaller) or in the case of the planar grid
and zero-field, when computation of the partition function is reduced to
computing a determinant, we use the code from (Likhosherstov et al., 2019)
(see also references therein). Our computations are done for the values of
$\lambda$ equally spaced with the increment $0.05$, between $0$ and $1$,
$\lambda\in[0::0.05::1]$. We use Eq. (34) to estimate
$d\bar{F}^{(\lambda)}/d\lambda$, and then use finite difference approximation
for derivative and Eq. (35) to estimate
$d^{2}\bar{F}^{(\lambda)}/d\lambda^{2}$.

The log-correction term, $\log{\cal Z}^{(\lambda)}=\log Z-\log Z^{(\lambda)}$,
is estimated by direct sampling according to Eq. (23). (See Fig. (9) and
respective discussion below for empirical analysis of the number of samples
required to guarantee sufficient accuracy.)

Figure 1: The case of the Ising Model (a) with non-zero field and random
interaction, $h,J\sim\mathcal{U}(0,1)$ over $3\times 3$ planar grid; and (b)
with non-zero field and random interaction, $h,J\sim\mathcal{U}(0,1)$ over
$K_{9}$ complete graph. We show fractional log-parition function (minus
fractional free energy) - on the left- and the respective correction factor
${\cal Z}^{(\lambda)}$ – on the right vs the fractional parameter, $\lambda$.

###  5.2 Properties of the Fractional Free Energy

Our numerical results for the fractional estimate of the log-partition
function (minus fractional free energy), $\log
Z^{(\lambda)}=-\bar{F}^{(\lambda)}$ and the log of the correction term,
$\log{\cal Z}^{(\lambda)}=\log Z-\log
Z^{(\lambda)}=\bar{F}^{(\lambda)}-\bar{F}$, are shown as functions of
$\lambda$ in Fig. (1) for the use cases described above 222See also extended
set of Figs. (4,5, 6,7) in the Appendix F, including dependence of
$d\bar{F}^{(\lambda)}/d\lambda,\ d^{2}\bar{F}^{(\lambda)}/d\lambda^{2}$ on
$\lambda$.. We draw from this set of Figures the following empirical
conclusions:

  * •

The monotonicity and convexity of $\bar{F}^{(\lambda)}$, proven in Theorem 3.1
and Theorem 3.2, respectively, are confirmed.

  * •

Dependence of $\bar{F}^{(\lambda)}$ and $\log{\cal Z}^{(\lambda)}$ on
$\lambda$ is relatively sharp – of a phase transition type at some
$\bar{\lambda}$, when we move from the TRW regime at $\lambda<\bar{\lambda}$
to the BP regime at $\lambda>\bar{\lambda}$. Notice that estimate of the
threshold, $\bar{\lambda}$, decreases with the growth in $N$.

###  5.3 Relation between Exact and Fractional

Figs. (4,5, 6,7), shown in the Appendix F, also give an empirical confirmation
to the Theorem 3.3 statement in the part which concerns independence of,
$Z^{(\lambda)}{\cal Z}^{(\lambda)}$, of $\lambda$. This observation, combined
with the full statement of the Theorem 3.3, suggests that if two or more of
empirical estimates of $Z^{(\lambda)}{\cal Z}^{(\lambda)}$ at different
$\lambda$ are sufficiently close to each other we can use them to bound $Z$
from above and below. Moreover, the full statement of the Theorem 4.1, i.e.
equality between the left- and right- hand sides of Eq. (22), is also
confirmed in all of our simulations with high accuracy (when we can verify it
by computing $Z$ directly).

Figure 2: Planar zero-field Ising models for $n\times n$ grid with
$J\sim\mathcal{U}(0,1)$. For each $n$ four different instances are generated
by sampling uniformly at random from the unit interval and the exact values
are shown by hollow marker on each graph. (a) $10\times 10$ (b) $20\times 20$
(c) $30\times 30$ (d) $40\times 40$. Open symbols show respective values of
$\lambda_{*}$.

###  5.4 Concentration of $\lambda_{*}$ in Large Ensembles

Fig. (8) in the Appendix F shows dependence of $\bar{F}^{(\lambda)}$ on
$\lambda$ for a number of instances drawn from two exemplary attractive use-
case ensembles. We observe that variability in the value of
$\bar{F}^{(\lambda)}$ is sufficiently large. Variability of $\lambda_{*}$,
where $Z^{(\lambda_{*})}=Z$, are also observed, even though it is
significantly smaller.

The last observation suggests that variability of $\lambda_{*}$ within an
attractive ensemble decreases with $N$ when it grows. This guess is confirmed
in our experiments with larger attractive ensembles illustrated in Fig. (2)
for different $N$. For each $N$ in the case over $N\times N$ grid we generate
$4$ different instances. We observe that as $N$ increases variability of
$\lambda_{*}$ within the ensemble decreases dramatically. This observation is
quire remarkable, as it suggests that it is enough to estimate $\lambda_{*}$
for one instance in a large ensemble and then use it for accurate estimation
of $Z$ by simply computing $Z^{(\lambda_{*})}$. Our estimations, based on the
data shown in Fig. (2) and other similar experiments (not shown) suggest that
the width of the probability distribution of $\lambda_{*}$ within the ensemble
scales as $\propto 1/\sqrt{N}$ with increase in $N$.

###  5.5 Convergence of Sampling for ${\cal Z}^{(\lambda)}$

Fig. (9), shown in the Appendix F, reports dependence of the sample-based
estimate of ${\cal Z}^{(\lambda)}$ on the number of samples. Our major
observation here is that the result converges with the number of samples.
Moreover, comparing the speed of convergence (with the number of samples) on
the size of the system, $N$, we estimate that the latter scales with the
former as $\mathcal{O}(N^{[2::4]})$.

###  5.6 Fractional Approach for Mixed (attractive and repulsive) Cases

Fig. (10) of the Appendix F, shows two distinct situations which may be
observed in the mixed case where some of the interactions are attractive but
other are repulsive, then allowing $Z^{(\lambda)}$ to be smaller or larger
than $Z$. The former case is akin to the attractive model and
$\lambda_{*}\in[0,1]$, while in the later case there exists no
$\lambda_{*}\in[0.1]$ such that $Z^{(\lambda_{*})}=Z$.

##  6 Conclusions and Path Forward

This manuscript suggests a new promising approach to evaluating inference in
Ising Models. The approach consists in, first, solving a fractional
variational problem via a distributed message-passing algorithm resulting in
the fractional estimations for the partition function and marginal beliefs. We
then compute multiplicative correction to the fractional partition function by
evaluating a well-defined expectation of the mean-field probability
distribution both constructed explicitly from the marginal beliefs. We showed
that the freedom in the fractional parameter is useful, e.g. for finding
optimal value of the parameter, $\lambda_{*}$, where the multipicative
correction is unity. Our theory validated experiments result in a number of
interesting observations, such as a phase-transition like dependence of the
fractional free-energy on $\lambda$ and strong suppression of fluctuations of
$\lambda_{*}$ in large ensembles.

As a path-forward we envision extending this fractional approach along the
following directions:

  * •

Proving or disproving the concentration conjecture and small number of samples
conjecture, made informally in Section 5.4 and Section 5.5, respectively.

  * •

Generalizing the extrapolation technique, e.g. building a scheme interpolating
between TRW and Mean-Field. This will be of a special interest for the case of
the mixed ensembles which are generally out of reach of the fractional
approach (between TRW and BP) presented in the manuscript.

  * •

Generalizing the extrapolation technique to more general class of Graphical
Models.

  * •

Extending the technique to the setting where $\lambda_{*}$ will be learned
directly from the data.

We also anticipate that all of these developments, presented in this
manuscript and others to follow, will help to make variational GM techniques
competitive with other, and admittedly more popular, methods of Machine
Learning, such as Deep Learning (DL). We envision to see in the future more
examples where the variational GM techniques will be re-enforced with the
automatic differentiation, e.g. in the spirit of (Lucibello et al., 2022), and
also integrated into modern Deep Learning protocols, e.g. as discussed in
(Garcia Satorras & Welling, 2021). This hybrid GM-DL approach is expected to
be especially needed and powerful in the physics problems where we are
interested to learn from data reduced models with graphical structure
prescribed by the underlying physics (or other quantitative disciplines).

## References

  * Ahn et al. (2018) Ahn, S., Chertkov, M., Weller, A., and Shin, J.  Bucket Renormalization for Approximate Inference.  volume 80 of _Proceedings of Machine Learning Research_ , pp. 109–118. PMLR, Jul 2018.
  * Ahn et al. (2016) Ahn, S.-S., Chertkov, M., and Shin, J.  Synthesis of MCMC and belief propagation.  In _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016.
  * Andrieu et al. (2003) Andrieu, C., de Freitas, N., Doucet, A., and Jordan, M. I.  An introduction to MCMC for machine learning.  _Machine Learning_ , 50(1):5–43, Jan 2003.
  * Bixler & Huang (2018) Bixler, R. and Huang, B.  Sparse-Matrix Belief Propagation.  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence_ , 2018.
  * Chertkov (2023) Chertkov, M.  _INFERLO: Inference, Learning and Optimization with Graphical Models_.  Leaving Book (self published for now), 2023.  URL https://t.ly/wkCR.
  * Chertkov & Chernyak (2006a) Chertkov, M. and Chernyak, V. Y.  Loop calculus in statistical physics and information science.  _Phys. Rev. E_ , 73:065102, Jun 2006a.
  * Chertkov & Chernyak (2006b) Chertkov, M. and Chernyak, V. Y.  Loop series for discrete statistical models on graphs.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2006(06):P06009, Jun 2006b.
  * Chertkov & Yedidia (2013) Chertkov, M. and Yedidia, A. B.  Approximating the permanent with fractional belief propagation.  _Journal of Machine Learning Research_ , 14(62):2029–2066, 2013.
  * Chertkov et al. (2020) Chertkov, M., Chernyak, V., and Maximov, Y.  Gauges, loops, and polynomials for partition functions of graphical models.  _Journal of Statistical Mechanics: Theory and Experiment_ , 2020(12):124006, dec 2020.
  * Dechter (1999) Dechter, R.  Bucket elimination: A unifying framework for reasoning.  _Artificial Intelligence_ , 113(1):41–85, 1999\.
  * Dechter & Rish (2003) Dechter, R. and Rish, I.  Mini-buckets: A general scheme for bounded inference.  _J. ACM_ , 50(2):107–153, Mar 2003.  ISSN 0004-5411.
  * Garcia Satorras & Welling (2021) Garcia Satorras, V. and Welling, M.  Neural enhanced belief propagation on factor graphs.  In Banerjee, A. and Fukumizu, K. (eds.), _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics_ , volume 130 of _Proceedings of Machine Learning Research_ , pp. 685–693. PMLR, 13–15 Apr 2021.
  * Gómez et al. (2010) Gómez, V., Kappen, H. J., and Chertkov, M.  Approximate inference on planar graphs using loop calculus and belief propagation.  _Journal of Machine Learning Research_ , 11(42):1273–1296, 2010.
  * Jerrum & Sinclair (1993) Jerrum, M. and Sinclair, A.  Polynomial-time approximation algorithms for the ising model.  _SIAM J. Comput._ , 22(5):1087–1116, oct 1993\.  ISSN 0097-5397.
  * Likhosherstov et al. (2019) Likhosherstov, V., Maximov, Y., and Chertkov, M.  Inference and sampling of $k_{33}$-free ising models.  In Chaudhuri, K. and Salakhutdinov, R. (eds.), _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 3963–3972. PMLR, 09–15 Jun 2019.
  * Liu & Ihler (2011) Liu, Q. and Ihler, A.  Bounding the partition function using hölder’s inequality.  In _Proceedings of the 28th International Conference on International Conference on Machine Learning_ , ICML’11, pp. 849–856, Madison, WI, USA, 2011. Omnipress.  ISBN 9781450306195.
  * Lucibello et al. (2022) Lucibello, C., Pittorino, F., Perugini, G., and Zecchina, R.  Deep learning via message passing algorithms based on belief propagation.  _Machine Learning: Science and Technology_ , 3(3):035005, Jul 2022.
  * Ruozzi (2012) Ruozzi, N.  The bethe partition function of log-supermodular graphical models.  In Pereira, F., Burges, C., Bottou, L., and Weinberger, K. (eds.), _Advances in Neural Information Processing Systems_ , volume 25. Curran Associates, Inc., 2012.
  * Wainwright et al. (2005) Wainwright, M., Jaakkola, T., and Willsky, A.  A new class of upper bounds on the log partition function.  _IEEE Transactions on Information Theory_ , 51(7):2313–2335, 2005.
  * Wainwright (2002) Wainwright, M. J.  _Stochastic processes on graphs with cycles: geometric and variational approaches_.  phd, Massachusetts Institute of Technology, USA, 2002.  AAI0804024.
  * Wainwright & Jordan (2007) Wainwright, M. J. and Jordan, M. I.  Graphical Models, Exponential Families, and Variational Inference.  _Foundations and Trends® in Machine Learning_ , 2007.
  * Wainwright et al. (2001) Wainwright, M. J., Jaakkola, T., and Willsky, A.  Tree-based reparameterization for approximate inference on loopy graphs.  In _Advances in Neural Information Processing Systems_ , volume 14. MIT Press, 2001.
  * Wainwright et al. (2003) Wainwright, M. J., Jaakkola, T. S., and Willsky, A. S.  Tree-reweighted belief propagation algorithms and approximate ML estimation by pseudo-moment matching.  In _In AISTATS_ , 2003.
  * Welsh (1991) Welsh, D.  The Computational Complexity of. Some Classical Problems from. Statistical Physics.  In _Disorder in Physical Systems_ , pp. 307–321. OxfordUniversityPress,, 1991.
  * Wiegerinck & Heskes (2002) Wiegerinck, W. and Heskes, T.  Fractional Belief Propagation.  In Becker, S., Thrun, S., and Obermayer, K. (eds.), _Advances in Neural Information Processing Systems_ , volume 15. MIT Press, 2002.
  * Willsky et al. (2007) Willsky, A., Sudderth, E., and Wainwright, M. J.  Loop series and bethe variational bounds in attractive graphical models.  In Platt, J., Koller, D., Singer, Y., and Roweis, S. (eds.), _Advances in Neural Information Processing Systems_ , volume 20. Curran Associates, Inc., 2007.
  * Yedidia et al. (2005) Yedidia, J., Freeman, W., and Weiss, Y.  Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms.  _IEEE Transactions on Information Theory_ , 51(7):2282–2312, 2005.
  * Yedidia et al. (2001) Yedidia, J. S., Freeman, W. T., and Weiss, Y.  Bethe free energy, Kikuchi approximations, and belief propagation algorithms.  _Advances in neural information processing systems_ , 13, 2001.

##  Appendix A Fractional Variational Formulation: Details

###  A.1 Lagrangian formulation

Introducing Lagrangian multipliers associated with the linear constraints in
Eqs. (20a,20b) we arrive at the following Lagrangian reformulation of Eq. (11)

$\displaystyle\bar{F}^{(\lambda)}$ $\displaystyle=$
$\displaystyle\min\limits_{{\cal\bm{B}}\geq
0}\max\limits_{{\bm{\eta}},{\bm{\psi}}}L^{(\lambda)}({\cal\bm{B}};{\bm{\eta}},{\bm{\psi}}),$
(24) $\displaystyle L^{(\lambda)}$ $\displaystyle\doteq$ $\displaystyle
F^{(\lambda)}({\cal\bm{B}})+\sum\limits_{a\in{\cal V};b\sim
a}\sum\limits_{x_{a}}\eta_{b\to a}(x_{a})\left(\sum\limits_{x_{b}}{\cal
B}_{ab}(x_{a},x_{b})-{\cal B}_{a}(x_{a})\right)+\sum\limits_{\\{a,b\\}\in{\cal
E}}\psi_{ab}\left(1-\sum\limits_{x_{a},x_{b}}{\cal
B}_{ab}(x_{a},x_{b})\right),$ (25)

where $L^{(\lambda)}({\cal\bm{B}};{\bm{\eta}},{\bm{\psi}})$ is the (extended)
Lagrangian dependent on both the primary variables (beliefs, ${\cal\bm{B}}$)
and the newly introduced dual variables, ${\bm{\eta}}\doteq(\eta_{b\to
a}(x_{a})\in\mathbb{R}|\forall a\in{\cal V},\ \forall b\sim a,\ \forall
x_{a}=\pm 1)$ and ${\bm{\psi}}\doteq(\psi_{a}\in\mathbb{R}|\forall a\in{\cal
V})$. Stationary point of the Lagrangian (25), assuming that it is unique, is
defined by the following system of equations

$\displaystyle\forall\\{a,b\\}\in{\cal E},\
\forall{\bm{x}}_{a},{\bm{x}}_{b}=\pm 1:\quad\frac{\delta
L^{(\lambda)}({\cal\bm{B}})}{\delta{\cal B}_{ab}(x_{a},x_{b})}=0\Rightarrow$
(26) $\displaystyle\hskip
142.26378ptE_{ab}(x_{a},x_{b})+\rho^{(\lambda)}_{ab}\left(\log\left({\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b})\right)+1\right)-\psi^{(\lambda)}_{ab}+\eta^{(\lambda)}_{b\to
a}(x_{a})+\eta^{(\lambda)}_{a\to b}(x_{b})=0,$ $\displaystyle\forall a\in{\cal
V},\ \forall x_{a}=\pm 1:\quad\frac{\delta
L^{(\lambda)}({\cal\bm{B}})}{\delta{\cal
B}_{a}(x_{a})}=0\Rightarrow\left(\sum_{b\sim
a}\rho^{(\lambda)}_{ab}-1\right)\left(\log{\cal
B}^{(\lambda)}_{a}(x_{a})+1\right)+\sum\limits_{b\sim a}\eta^{(\lambda)}_{b\to
a}(x_{a})=0,$ (27)

augmented with Eqs. (20a,20b). Eqs. (26) and Eqs. (27) results in the
following expressions for the marginals in terms of the Lagrangian multipliers

$\displaystyle\forall a\in{\cal V},\ \forall x_{a}=\pm 1:\quad{\cal
B}^{(\lambda)}_{a}(x_{a})\propto\exp\left(-\frac{\sum\limits_{b\sim
a}\eta^{(\lambda)}_{b\to a}(x_{a})}{\sum\limits_{b\sim
a}\rho^{(\lambda)}_{ab}-1}\right),$ (28)
$\displaystyle\forall\\{a,b\\}\in{\cal E},\ \forall x_{a},x_{b}=\pm
1:\quad{\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b})\propto\exp\left(-\frac{E_{ab}(x_{a},x_{b})+\eta^{(\lambda)}_{b\to
a}(x_{a})+\eta^{(\lambda)}_{a\to b}(x_{b})}{\rho^{(\lambda)}_{ab}}\right).$
(29)

Here in Eqs. (26,27,28,29) and below the upper index $(\lambda)$ in ${\cal
B}^{(\lambda)},\eta^{(\lambda)}$ and $\psi^{(\lambda)}$ variables indicates
that the respective variables are optimal, i.e. argmax and argmin, over
respective optimizations in Eq. (25).

###  A.2 Message Passing

We may also rewrite Eqs. (28,29) in terms of the so-called message (from node-
to-node) variables. Then the marginal beliefs are expressed via the
$\mu^{(\lambda)}$-messages according to

$\displaystyle\forall a\in{\cal V},\ \forall b\sim a:\ \mu^{(\lambda)}_{b\to
a}(x_{a})\doteq\exp\left(-\frac{\eta^{(\lambda)}_{b\to
a}(x_{a})}{\sum\limits_{b\sim a}\rho^{(\lambda)}_{ab}-1}\right),$ (30)
$\displaystyle\forall a\in{\cal V},\ \forall x_{a}=\pm 1:\quad{\cal
B}^{(\lambda)}_{a}(x_{a})=\frac{\prod\limits_{b\sim a}\mu^{(\lambda)}_{b\to
a}(x_{a})}{\sum\limits_{x_{a}}\prod\limits_{b\sim a}\mu^{(\lambda)}_{b\to
a}(x_{a})},$ (31) $\displaystyle\forall\\{a,b\\}\in{\cal E},\ \forall
x_{a},x_{b}=\pm 1:\quad{\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b})=\frac{\exp\left(-\frac{E_{ab}(x_{a},x_{b})}{\rho^{(\lambda)}_{ab}}\right)\left(\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{\frac{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}{\rho^{(\lambda)}_{ab}}}\left(\mu^{(\lambda)}_{a\to
b}(x_{b})\right)^{\frac{\sum\limits_{c\sim
b}\rho^{(\lambda)}_{bc}-1}{\rho^{(\lambda)}_{ab}}}}{\sum\limits_{x_{a},x_{b}}\exp\left(-\frac{E_{ab}(x_{a},x_{b})}{\rho^{(\lambda)}_{ab}}\right)\left(\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{\frac{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}{\rho^{(\lambda)}_{ab}}}\left(\mu^{(\lambda)}_{a\to
b}(x_{b})\right)^{\frac{\sum\limits_{c\sim
b}\rho^{(\lambda)}_{bc}-1}{\rho^{(\lambda)}_{ab}}}},$ (32)

and the Fractional Belief Propagation (FBP) equations, expressing relations
between pairwise and singleton marginals become:

$\displaystyle\forall a\in{\cal V},\ \forall b\sim a,\ \forall x_{a}=\pm 1:$
(33) $\displaystyle{\cal B}^{(\lambda)}_{a}(x_{a})\propto\prod\limits_{b\sim
a}\mu^{(\lambda)}_{b\to
a}(x_{a})\propto\sum\limits_{x_{b}}\exp\left(-\frac{E_{ab}(x_{a},x_{b})}{\rho^{(\lambda)}_{ab}}\right)\left(\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{\frac{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}{\rho^{(\lambda)}_{ab}}}\left(\mu^{(\lambda)}_{a\to
b}(x_{b})\right)^{\frac{\sum\limits_{c\sim
b}\rho^{(\lambda)}_{bc}-1}{\rho^{(\lambda)}_{ab}}}\propto\sum\limits_{x_{b}}{\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b}).$

Note (on a tangent), that the $\mu^{(\lambda)}$-(message) variables introduced
here are related but not equivalent to the $M^{(\lambda)}$-messages which can
also be seen used in the BP-literature, see e.g. Section 4.1.3 of (Wainwright
& Jordan, 2007). Specifically in the case of BP, i.e. when
$\rho^{(\lambda)}_{ab}=1$, relation between $\mu^{(\lambda)}$ and
$M^{(\lambda)}$ variables is as follows, $(\mu^{(\lambda)}_{b\to
a}(x_{a}))^{d_{a}-1}=\prod_{c\sim a;c\neq b}M^{(\lambda)}_{c\to a}(x_{a})$.

##  Appendix B Proof of Theorem 3.1

Let us evaluate derivative of the fractional free energy (11) over $\lambda$
explicitly

$\displaystyle\frac{d}{d\lambda}\bar{F}^{(\lambda)}$
$\displaystyle=\frac{d}{d\lambda}F^{(\lambda)}\left({\cal\bm{B}}^{(\lambda)}\right)=\sum\limits_{\\{a,b\\}}\sum\limits_{x_{a},x_{b}}\frac{\partial
F^{(\lambda)}\left({\cal\bm{B}}^{(\lambda)}\right)}{\partial\mathcal{B}_{ab}^{(\lambda)}(x_{a},x_{b})}\frac{d\mathcal{B}_{ab}^{(\lambda)}(x_{a},x_{b})}{d\lambda}+\sum\limits_{a}\sum\limits_{x_{a}}\frac{\partial
F^{(\lambda)}\left({\cal\bm{B}}^{(\lambda)}\right)}{\partial\mathcal{B}_{a}^{(\lambda)}(x_{a})}\frac{d\mathcal{B}_{a}^{(\lambda)}(x_{a})}{d\lambda}$
$\displaystyle-\sum\limits_{\\{a,b\\}}\frac{\partial
H^{(\lambda)}({\cal\bm{B}}^{(\lambda)})}{\partial\rho^{(\lambda)}_{ab}}\frac{d\rho^{(\lambda)}_{ab}}{d\lambda}.$

Taking into account for the conditions of stationarity of the fractional free
energy, tracking explicit dependencies of the fractional entropy on
$\rho^{(\lambda)}_{ab}$, and thus on $\lambda$, we arrive at

$\displaystyle\forall\\{a,b\\}:\quad$ $\displaystyle\frac{\partial
F^{(\lambda)}\left({\cal\bm{B}}^{(\lambda)}\right)}{\partial\mathcal{B}_{ab}^{(\lambda)}(x_{a},x_{b})}=0;\quad\forall
a:\quad\frac{\partial
F^{(\lambda)}\left({\cal\bm{B}}^{(\lambda)}\right)}{\partial\mathcal{B}_{a}^{(\lambda)}(x_{a})}=0;$
$\displaystyle\frac{\partial
H^{(\lambda)}({\cal\bm{B}}^{(\lambda)})}{\partial\rho^{(\lambda)}_{ab}}$
$\displaystyle=-\sum\limits_{x_{a},x_{b}=\pm 1}{\cal
B}_{ab}^{(\lambda)}(x_{a},x_{b})\log{\cal
B}_{ab}^{(\lambda)}(x_{a},x_{b})+\sum\limits_{x_{a}=\pm 1}{\cal
B}_{a}^{(\lambda)}(x_{a})\log{\cal
B}_{a}^{(\lambda)}(x_{a})+\sum\limits_{x_{b}=\pm 1}{\cal
B}_{b}^{(\lambda)}(x_{b})\log{\cal B}_{b}^{(\lambda)}(x_{b})$
$\displaystyle=-I^{(\lambda)}_{ab},$

where the newly introduced $I^{(\lambda)}_{ab}$ is nothing but the pairwise
mutual information defined according to ${\cal\bm{B}}^{(\lambda)}$. Notice
that $I^{(\lambda)}_{ab}\geq 0$. Since,
$d\rho^{(\lambda)}_{ab}/d\lambda=1-\rho_{ab}\geq 0$, and summarizing all of
the above we derive

$\displaystyle\frac{d}{d\lambda}\bar{F}^{(\lambda)}=-\sum_{\\{a,b\\}}(1-\rho_{ab})I^{(\lambda)}_{ab}\leq
0,$ (34)

therefore concluding proof of both continuity (the derivative is bounded) and
monotonicity (the derivative is negative).

##  Appendix C Proof of Theorem 3.2

Let us express the second derivative of the fractional free energy over
$\lambda$ explicitly using Eq. (34),

$\frac{d^{2}}{d\lambda^{2}}\bar{F}^{(\lambda)}=-\sum_{\\{a,b\\}}(1-\rho_{ab})\
\frac{d}{d\lambda}I^{(\lambda)}_{ab}.$ (35)

To show that the second derivative is positive (convexity claim), it is
sufficient to prove the following lemma.

######  Lemma C.1.

Assuming ${\bm{\rho}}\doteq(\rho_{ab}|(a,b)\in{\cal E})$ is fixed,
$I_{ab}^{(\lambda)}$ is monotone decreasing in $\lambda$.

###### Proof.

Consider, first, the case of the Ising model in zero field, where the minimum
of the fractional free energy is achieved at a highly symmetric beliefs

$\displaystyle\forall a\in{\cal V}:\quad{\cal
B}_{a}(x_{a})=1/2,\quad\forall(a,b)\in{\cal E}:\quad{\cal
B}_{ab}(x_{a},x_{b})=\begin{pmatrix}\beta_{ab}^{(\lambda)}&1/2-\beta_{ab}^{(\lambda)}\\\
1/2-\beta_{ab}^{(\lambda)}&\beta_{ab}^{(\lambda)}\end{pmatrix}.$

It allows the following simplification of the mutual information in terms of
the marginal beliefs

$\displaystyle I_{ab}^{(\lambda)}(x_{a},x_{b})$
$\displaystyle=\sum\limits_{x_{a},x_{b}=\pm 1}{\cal
B}_{ab}^{(\lambda)}(x_{a},x_{b})\log{\cal
B}_{ab}^{(\lambda)}(x_{a},x_{b})-\sum\limits_{x_{a}=\pm 1}{\cal
B}_{a}^{(\lambda)}(x_{a})\log{\cal
B}_{a}^{(\lambda)}(x_{a})-\sum\limits_{x_{b}=\pm 1}{\cal
B}_{b}^{(\lambda)}(x_{b})\log{\cal B}_{b}^{(\lambda)}(x_{b})$
$\displaystyle=2\left(\beta_{ab}^{(\lambda)}\log\beta_{ab}^{(\lambda)}+(1/2-\beta_{ab}^{(\lambda)})\log(1/2-\beta_{ab}^{(\lambda)})\right)+\log
2+\log 2$
$\displaystyle=2\left(\beta_{ab}^{(\lambda)}\log\beta_{ab}^{(\lambda)}+(1/2-\beta_{ab}^{(\lambda)})\log(1/2-\beta_{ab}^{(\lambda)})+1\right).$

Then evaluating derivative of the mutual information over $\lambda$ we arrive
at

$\frac{dI_{ab}^{(\lambda)}}{d\lambda}=\frac{dI_{ab}^{(\lambda)}}{d\beta_{ab}^{(\lambda)}}\frac{d\beta_{ab}^{(\lambda)}}{d\lambda}=\log\left(\frac{\beta_{ab}^{(\lambda)}}{1/2-\beta_{ab}^{(\lambda)}}\right)^{2}\frac{d\beta_{ab}^{(\lambda)}}{d\lambda}\leq
0,$

The first term in the expression is always positive because,

$1/4={\cal B}_{a}{\cal B}_{b}<\beta_{ab}^{(\lambda)}<\min\\{{\cal B}_{a},{\cal
B}_{b}\\}=1/2,$

where $\beta_{ab}^{(\lambda)}$ is a decreasing function of $\lambda$ (since
the model is attractive).

To extend this derivation to the general case of ${\bm{h}}\neq 0$ we follow
the (standard) transformation from the general Ising model to its zero-field
equivalent by introducing an extra node connected to all other nodes:

$\displaystyle p(\mathbf{x})\propto\exp\left(\sum_{a\in
V}h_{a}x_{a}+\sum_{(a,b)\in\mathcal{E}}J_{ab}\ x_{a}x_{b}\right)\propto
p(\mathbf{x},x_{*})\propto\exp\left(\sum_{a\in V}J_{a*}\
x_{a}x_{*}+\sum_{(a,b)\in\mathcal{E}}J_{ab}\ x_{a}x_{b}\right),$

where $x_{*}$ is the newly introduced node connected to all original nodes and
$J_{a*}=h_{*}$. It is easy to see that
$Z(\bm{J},\bm{h})=Z^{*}(\bm{J}^{*},\bm{0})/2$ where $Z^{*}$ is the partition
function on the modified graph with new interaction $\bm{J}^{*}$.

∎

##  Appendix D Proof of Theorem 4.1

Consistently with Eq. (8), Eqs. (31,32) allow us to rewrite the joint
probability distribution in terms of the optimal beliefs which solve the
fractional Eqs. (33)

$\displaystyle p({\bm{x}})$
$\displaystyle=Z^{-1}\prod\limits_{\\{a,b\\}\in{\cal
E}}\Bigg{(}\sum\limits_{x_{a},x_{b}}\exp\left(-\frac{E_{ab}(x_{a},x_{b})}{\rho^{(\lambda)}_{ab}}\right)\left(\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{\frac{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}{\rho^{(\lambda)}_{ab}}}\left(\mu^{(\lambda)}_{a\to
b}(x_{b})\right)^{\frac{\sum\limits_{c\sim
b}\rho^{(\lambda)}_{bc}-1}{\rho^{(\lambda)}_{ab}}}\Bigg{)}^{\rho^{(\lambda)}_{ab}}\times$
$\displaystyle\prod\limits_{a\in{\cal
V}}\left(\sum\limits_{x_{a}}\prod\limits_{b\sim a}\mu^{(\lambda)}_{b\to
a}(x_{a})\right)^{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}\frac{\prod\limits_{\\{a,b\\}\in{\cal E}}\left({\cal
B}^{(\lambda)}_{ab}(x_{a},x_{b})\right)^{\rho^{(\lambda)}_{ab}}}{\prod\limits_{a\in{\cal
V}}\left({\cal B}^{(\lambda)}_{a}(x_{a})\right)^{\sum\limits_{c\sim
a}\rho^{(\lambda)}_{ac}-1}}.$ (36)

Normalization condition, that is the requirement for the sum on the right hand
side of Eq. (36) to return $1$, results in the desired statement, i.e. Eqs.
(22,23).

##  Appendix E Proof of Lemma 5.1

Figure 3: Construction of the set of spanning trees for a sequence of graphs
built from the $K_{4}$ graph (sub-figure (a)) in two steps, from (a) to (b)
and from (b) to (c), each time eliminating an edge. At each step we remove one
edge (shown dashed green), remove one spanning tree (shown circled and crossed
red), and add a new edge (shown solid green) to all the remaining spanning
trees which lost an edge such that they stay spanning trees and the resulting
$\rho_{ab}$ edges are uniform among the remaining spanning trees. The
resulting number of spanning trees and the uni-form edge weights are (a)
$|V|=4$ and $\forall(a,b)\in{\cal V},\ \rho_{ab}=|{\cal V}|-1/|{\cal
E}|=(4-1)/6=3/6=1/2$; (b) $|V|=5$ and $\forall(a,b)\in{\cal V},\ |{\cal
V}|-1/|{\cal E}|=(4-1)/5=3/5$; (c) $|V|=4$ and $\forall(a,b)\in{\cal V},\
|{\cal V}|-1/|{\cal E}|=(4-1)/4=3/4$.

Our proof of the statement is constructive and it is thus formalized in the
Algorithm 1. The Algorithm follows induction, starting from a complete graph
and then progressing by removing edges (and therefore loops) sequentially,
such that at any step all nodes continue to be of degree two or larger. The
induction terminates when the resulting graph is a single loop. See Fig. (3)
for illustration on the example of $N=4$, thus $K_{4}$.

The proof allows to construct the required set of spanning trees for any graph
(with all nodes of degree two or larger) because by selecting a sequence of
edges in the Algorithm 1 proper we can arrive at the given graph starting from
the complete graph containing as many nodes as the given graph and eliminating
edges according to the Algorithm 1.

Algorithm 1 Edge-Uniform Set of Spanning Trees

Input: $K_{N}$, graph. Sequence of edges, $\\{e_{1},\cdots,e_{N-2}\\}$ of
$K_{N}$ and respective sequence of graphs, $\\{{\cal G}_{1},\cdots,{\cal
G}_{N-2}\\}$, such that, ${\cal G}_{1}=K_{N}\setminus e_{1}$, $\forall
n=1,\cdots,N-3:\ {\cal G}_{n+1}\doteq{\cal G}_{n}\setminus e_{n+1}$, and
${\cal G}_{N-2}$ is a single loop

Initialize: ${\cal T}$\- set of all linear spanning trees of ${\cal G}$. (A
spanning tree is linear if all nodes is of degree two or one.)

Repeat: $n=1,\cdots$

  1. 1.

${\cal G}=({\cal V},{\cal E})={\cal G}_{n}$

  2. 2.

$\forall T\in{\cal T}:\ \rho_{T}=1/|{\cal E}|$ and thus $\forall(a,b)\in{\cal
E}:\rho_{ab}=(|{\cal V}|-1)/|{\cal E}|$.

  3. 3.

Exit if $n=N-2$.

  4. 4.

Remove edge $e_{n}$ from all spanning trees in ${\cal T}$

  5. 5.

${\cal T}\leftarrow{\cal T}\setminus(\text{element of ${\cal T}$ which becomes
disconnected})$

  6. 6.

Modify ${\cal T}$ by adding an extra edge to each spanning tree of ${\cal T}$
having $(N-n-1)$ edges. These added edges should keep each element of ${\cal
T}$ a spanning tree of ${\cal G}$ and also guarantee that each edge enters
exactly $N-1$ resulting spanning trees. (It is straightforward to check that
such a construction is unique and unambiguous. See Fig. (3) for illustration.)

##  Appendix F More Figures from Numerical Experiments

We show in this Appendix an extended set of Figures for the experiments
discussed in the Section 5.3 of the main text. Specifically, results of our
experiment for the case of the Ising model over planar graphs and complete
graphs of various sizes in the settings of zero- and non-zero- fields are
illustrated in Figs. (4,5, 6,7). We show in this set of figures dependence of
$\log Z^{(\lambda)}=-\bar{F}^{(\lambda)}$ and $\log{\cal Z}^{(\lambda)}$, as
well as $d\bar{F}^{(\lambda)}/d\lambda$ and
$d^{2}\bar{F}^{(\lambda)}/d\lambda^{2}$, on $\lambda$. Observing dependence of
the first and second derivatives of the fractional free energy on $\lambda$
allows us to conclude (confirm) that the log fractional partition function is
monotone decreasing and also convex in $\lambda$. We also observe that when
$\lambda$ is sufficiently large, $\log Z^{(\lambda)}$ is independent of
$\lambda$. We also track in these figures the value of $\lambda_{*}$,
correspondent to ${\cal Z}^{(\lambda_{*})}=1$, and thus $Z=Z^{(\lambda_{*})}$.

Fig. (8), mentioned in Section 5.4 shows $\lambda_{*}$ for a number of
instances drawn from the respective ensembles of the Ising model (over planar
and complete graphs). We observe that in the planar case,
$\lambda_{*}\in[0.25,0.45]$, while in the case of the complete graph,
$\lambda_{*}\in[0.05,0.15]$.

Fig. (9), mentioned in Section 5.5, shows results for the experiments with the
Ising model of two different sizes. We see here estimation of the correction
factor, $\log\cal Z^{(\lambda)}$, evaluated at different $\lambda$ for a
varying number of samples (drawn i.i.d. from the mean-field distribution built
based of the fractional nodal beliefs). We observe that the estimate stops to
change with increase in the number of samples, once a sufficient number of
samples, $M_{c}$, is drawn. We estimate that $M_{c}$ grows with $N$ as
$\mathcal{O}(N^{4})$ or slower.

Fig. (10), mentioned in Section 5.6, shows results for the mix case when the
pair-wise interaction can vary in sign from edge to edge. In this mixed case,
as seen in the presented examples, we can not guarantee that BP provides a
lower bound on the partition function, and thus $\lambda_{*}$ may or may not
be identified within the $[0,1]$ interval.

Figure 4: The case of the Ising Model with non-zero magnetic field and random
interaction, $h,J\sim\mathcal{U}(0,1)$ over $3\times 3$ planar grid. We show
(a) fractional log-parition function (minus fractional free energy) - on the
left- and the respective correction factor ${\cal Z}^{(\lambda)}$ – on the
right vs the fractional parameter, $\lambda$; (b) the first order derivative –
on the left – and second order derivative – on the right – vs $\lambda$.

Figure 5: The case of the Ising Model with zero magnetic field and random
interaction, $J\sim\mathcal{U}(0,1)$ over $3\times 3$ planar grid. Further
details are identical to used in Fig. (4).

Figure 6: The case of the Ising Model with non-zero magnetic field and random
interaction, $h,J\sim\mathcal{U}(0,1)$ over $K_{9}$ complete graph. Further
details are identical to used in Fig. (4).

Figure 7: The case of the Ising Model with zero magnetic field and random
interaction, $J\sim\mathcal{U}(0,1)$ over $K_{9}$ complete graph. Further
details are identical to used in Fig. (4).

Figure 8: $F^{(\lambda)}$ vs $\lambda$ for a number of instances (shown in
different colors) drawn for the Ising model ensembles over, (a) $3\times 3$
grid, and (b) $K_{9}$ graph, where elements of ${\bm{J}}$ and ${\bm{h}}$ are
i.i.d. from $\mathcal{U}(0,1)$. Circles mark respective exact values,
$\lambda_{*}$.

Figure 9: Dependence of the sample-based estimate of $\mathcal{Z}^{(\lambda)}$
on the number of samples in the case of attractive Ising model over (a)
$3\times 3$, and (b) $6\times 6$ grids, where elements of ${\bm{J}}.^{2}$ and
${\bm{h}}$ are drawn i.i.d. from $\mathcal{U}[0,1]$. Different colors
correspond to different values of $\lambda$.

Figure 10:  Two different random instance of $4\times 4$ Isisng Model with (a)
$J\sim\mathcal{U}(-1,1)$ and $h\sim\mathcal{U}(-1,1)$ (b)
$J\sim\mathcal{U}(-1,1)$, $h=0$. Dashed line show exact value of partition
functions for the corresponding curve.