Existence alone, however, is not sufficient as we have to rely on some numerical method that obtains all fixed points; if we aim to apply BP for that matter there is the additional requirement for all fixed points to be stable.
Fortunately, it turns out that all fixed points inside $\Region$ are stable indeed.

Let $\ugm$ be a patch potential model with $(\field{}, \coupling{}{}) \in \Region$. Then, every fixed point $\pseudomarginals^m$ is a stable fixed point for BP.

Finally, as an immediate consequence of the limited amount of fixed points (Theorem <ref>), all of which are stable (Theorem <ref>), it follows that the exact solution can be computed according to (<ref>) in practice.
One can for example apply BP repeatedly, possibly in parallel, with random initialization to obtain and combine all fixed points.

Marginal AccuracyaccuracyBP:theory:acccuracy

The MSE of the singleton marginals  $\EMarginal{k}$ of the $k^{th}$ solution $\pseudomarginals^k$ relates to the ratio of the Bethe partition functions according to

\begin{align}
\EMarginal{k} = \frac{2}{N (\sum\limits_m \partitionBethe^m)^2} \sum_{\RV{i}\in\setOfNodes}\! \Big|\! \sum_{m\backslash k} \partitionBethe^m \left(\pmfApprox{\RV{i}}^m - \pmfApprox{\RV{i}}^k\right) \Big|^2 \nonumber.
\end{align}

According to (<ref>) we can express the exact solution by the convex combination of all fixed points.
Consequently, using symmetry properties of the binary random variables,  the error is given by

\begin{align}
\EMarginal{k} &= \frac{2}{N}  \sum_{\RV{i}\in\setOfNodes} \bigg|\frac{\sum\limits_m \partitionBethe^m \pmfApprox{\RV{i}}^m}{\sum\limits_m \partitionBethe^m} - \pmfApprox{\RV{i}}^k\bigg|^2 \nonumber \\
&= \frac{2}{N} \sum_{\RV{i}\in\setOfNodes}  \bigg| \frac{\sum\limits_m \partitionBethe^m \pmfApprox{\RV{i}}^m - \sum\limits_m \partitionBethe^m \pmfApprox{\RV{i}}^k}{\sum\limits_m \partitionBethe^m}\bigg|^2 \nonumber \\
& = \frac{2}{N \big( {\sum\limits_m \partitionBethe^m} \big)^2 }  \sum_{\RV{i}\in\setOfNodes}\Big| \sum_{m\backslash k} \partitionBethe^m \pmfApprox{\RV{i}}^m - \pmfApprox{\RV{i}}^k \Big|^2,
\end{align}

where we first, bring everything  on the same denominator so that the $k^{th}$ contribution cancels out subsequently.

Representing the MSE according to Theorem <ref> is particularly appealing as it omits the need for expressing the exact marginals.
This further provides a way to express the ratio of the marginal error between two fixed points.

The MSE-ratio of two fixed points $k$ and $l$ is a ratio of weighted partition functions according to

\begin{align}
\frac{\EMarginal{k}}{\EMarginal{l} } &= \frac{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{m\backslash k } \partitionBethe^m (\pmfApprox{\RV{i}}^m- \pmfApprox{\RV{i}}^k)|^2}
{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{m\backslash l } \partitionBethe^m (\pmfApprox{\RV{i}}^m- \pmfApprox{\RV{i}}^l)|^2}.
\label{eq:marginal_ratio}
\end{align}

Expressing the ratio of the marginal error according to (<ref>) is advantageous in elaborating on the difference between accuracy of the approximated marginals and the approximated partition function.
We define the mismatch between $\pmfApprox{\RV{i}}^m$ at two fixed points $k$ and $l$ by

\begin{align}
Q_i(k,l) = \pmfApprox{\RV{i}}^k(\RV{i}=1) - \pmfApprox{\RV{i}}^l(\RV{i}=1).
\end{align}

Now, let us denote the error of the state preserving fixed point by $\EMarginal{p}$
and of the fixed point that has all marginals biases towards $\RVval{i}=1$ by $\EMarginal{q}$.
Then – maybe non-surprising as the exact solution is state preserving as well – we show that the state-preserving fixed point has the most accurate marginals.
We first discuss the error-ratio in a general manner in Theorem <ref> before considering the special case of a model with two patches, i.e., for Example <ref>.

Let $\ugm$ be a patch potential model with $(\field{},\coupling{}{}) \in \Region$. The state preserving fixed point $p$ provides more accurate marginals than the fixed point $q$ that has all marginals biased to one state, i.e.,

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q}} < 1.
\end{align}

To show that, irrespective of the value of $\partitionBethe$, $\frac{\EMarginal{p}}{\EMarginal{q}} < 1$ we assume that the state preserving fixed point does not minimize the Bethe free energy, i.e., $\partitionBethe^q > \partitionBethe^p$.

Without loss of generality, we make some prior assumptions on the model:
First, we assume that the overall number of variables with a positive local field equals the number of variables with a negative local field, i.e.,

\begin{align}
|\{\RV{i}\in\setOfNodes: \field{i}=+\field{}\}| = |\{\RV{j}\in\setOfNodes: \field{i}=-\field{}\}|.
\label{eq:symmetry}
\end{align}

Second, we assume that all patches are of equal size.
And finally, we group all possible fixed points according to their marginals and denote them as follows:
the state-preserving fixed point is referred to as $p$;
all fixed points that have more patches biased towards $X_i = +1$ are referred to as $s = 1,\ldots,S$, with $q$ being the fixed point that has all variables biased towards $X_i = +1$;
all fixed points that have more patches biased towards $X_i = -1$ are referred to as $t = 1,\ldots,T$, with $r$ being the fixed point that has all variables biased towards $X_i = -1$.

This has some implications that will ease the subsequent analysis significantly. Specifically, the number of fixed points favoring one state equals the number of fixed points favoring the other state, i.e., $S=T$ by (<ref>) and by Theorem <ref>.

Another important consequence of incorporating the interactions between patches into an effective field is that the number of variables that favor one state has an immediate influence on the value of the singleton marginals. It can be shown that the effective field, if stronger than the local field – note that the effective field is stronger than the local field whenever two neighboring patches are biased towards the same state – increases the bias of the variables. This intuitive statement is a consequence of the Griffiths-Hurst-Sherman inequality [51] that can be extended to specific fixed points by straightforward manipulations (cf. [74]).
In essence this means that for all variables $\RV{i} \in \setOfNodes$ we have

\begin{align}
\pmfApprox{\RV{i}}^q(\RV{i}=1) \geq \pmfApprox{\RV{i}}^s(\RV{i}=1) \geq \pmfApprox{\RV{i}}^p(\RV{i}=1)
\geq \pmfApprox{\RV{i}}^t(\RV{i}=1) \geq \pmfApprox{\RV{i}}^r(\RV{i}=1).
\label{eq:marginal_inequality}
\end{align}

Moreover, as all patches have equal size and because $\coupling{i}{j} = \coupling{}{}$ as well as $\field{i} \in \{-\field{},\field{}\}$ every fixed point $s$ has a symmetric fixed point $t$ that has the same value for the approximate partition function (cf. Proof of Theorem <ref>).
That is, except for the state-preserving fixed point $p$ all fixed points come in couples that satisfy

\begin{align}
\partitionBethe^s = \partitionBethe^t.
\label{eq:partiton_equality}
\end{align}

We will further utilize the properties of the mismatch $\mismatch{k}{l}$; in particular the symmetry property

\begin{align}
\mismatch{k}{l} = - \mismatch{l}{k},
\label{eq:mismatch_symmetry}
\end{align}

and the expansion property

\begin{align}
\mismatch{k}{l} = \mismatch{k}{m} + \mismatch{m}{l}.
\label{eq:mismatch_expansion}
\end{align}

Finally, we express the error ration between the state-preserving fixed point $p$ and the biased fixed point $q$ according to   Corollary <ref> so that

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} }
\frac{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{m\backslash p } \partitionBethe^m \mismatch{m}{p}|^2}
{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{m\backslash q } \partitionBethe^m  \mismatch{m}{q}|^2} \nonumber \\
\frac{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{s } \partitionBethe^s \mismatch{s}{p}
+ \sum\limits_{t } \partitionBethe^t \mismatch{t}{p}|^2}
{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{s\backslash q } \partitionBethe^s \mismatch{s}{q}
+ \sum\limits_{t } \partitionBethe^t \mismatch{t}{q}
+ \partitionBethe^p \mismatch{p}{q}|^2} \nonumber \\
\frac{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{s\backslash q} \partitionBethe^s \big(\mismatch{s}{p} + \mismatch{t}{p}\big)
+ \partitionBethe^q \big(\mismatch{q}{p}+\mismatch{r}{p}\big)|^2}
{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{s\backslash q} \partitionBethe^s \big(\mismatch{s}{q} + \mismatch{t}{q}\big)
+ \partitionBethe^q \mismatch{r}{q}
+ \partitionBethe^p \mismatch{p}{q}|^2},
\end{align}

where (a) follows from splitting the sum into the fixed points $s$ that are more biased towards $\RV{i} = 1$ and into the fixed points $t$ that are more biased towards $\RV{i} = -1$.
Note that the state-preserving fixed point $p$ does not belong to either set and is consequently expressed explicitly in the denominator.
For (b) we make use of (<ref>) and arrange the terms by making the dependence on $q$ and $r$ explicit so that the sum goes over the same terms in the numerator and in the denominator.

We can further express the error ratio and bound it using Jensen's inequality according to

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} }
\stackrel{(a)}{=} &
\frac{ \sum\limits_{\RV{i}\in\setOfNodes}|\sum\limits_{s\backslash q} \partitionBethe^s \big(\mismatch{s}{p} + \mismatch{t}{p}\big)
+ \partitionBethe^q \big(\mismatch{q}{p}+\mismatch{r}{p}\big)|^2}
{ \sum\limits_{\RV{i}\in\setOfNodes}\Big(\sum\limits_{s\backslash q}  \partitionBethe^s \big|\big(\mismatch{s}{q} + \mismatch{t}{q}\big)\big|
+ \partitionBethe^q \big|\mismatch{r}{q}\big|
+ \partitionBethe^p \big|\mismatch{p}{q}\big|\Big)^2} \nonumber \\
\leq &
\frac{\sum\limits_{\RV{i}\in\setOfNodes}\Big(\sum\limits_{s\backslash q} \partitionBethe^s \big|\big(\mismatch{s}{p} + \mismatch{t}{p}\big)\big|
+  \partitionBethe^q\big| \big(\mismatch{q}{p}+\mismatch{r}{p}\big)\big| \Big)^2}
{\sum\limits_{\RV{i}\in\setOfNodes}\Big(\sum\limits_{s\backslash q}  \partitionBethe^s \big|\big(\mismatch{s}{q} + \mismatch{t}{q}\big)\big|
+ \partitionBethe^q \big|\mismatch{r}{q}\big|
+ \partitionBethe^p \big|\mismatch{p}{q}\big|\Big)^2},
\end{align}

where separating the norm does not change the result in (a) because of (<ref>), which implies $\mismatch{m}{q} < 0$ for all fixed points $m\neq q$.

For completing the proof we make use of the symmetry property (<ref>) and the expansion property (<ref>) in order to rearrange the terms; in particular note that
$\mismatch{q}{s}+ \mismatch{q}{t} = \mismatch{q}{s}+\mismatch{q}{s}+\mismatch{s}{p}+\mismatch{p}{t}$, and that
$\mismatch{q}{r} = \mismatch{q}{p} + \mismatch{p}{r} $
so that

\begin{align}
& \frac{\EMarginal{p}}{\EMarginal{q} }\leq \nonumber\\
& \hspace*{-25pt}  \frac{\sum\limits_{\RV{i}\in\setOfNodes}\Big(\sum\limits_{s\backslash q} \partitionBethe^s \big|\big(\mismatch{s}{p} - \mismatch{p}{t}\big)\big|
+  \partitionBethe^q\big| \big(\mismatch{q}{p}-\mismatch{p}{r}\big)\big| \Big)^2}
{\sum\limits_{\RV{i}\in\setOfNodes}\hspace*{-4pt}\Big(\hspace*{-2pt} \sum\limits_{s\backslash q}\hspace*{-2pt}  \partitionBethe^s \big|\big(\mismatch{s}{p}\hspace*{-2pt}+\hspace*{-2pt}\mismatch{p}{t}\hspace*{-2pt}+\hspace*{-2pt}\mismatch{q}{s}\hspace*{-2pt}+\hspace*{-2pt}\mismatch{q}{s}\big)\big| \hspace*{-2pt}
+\hspace*{-2pt}  \partitionBethe^q \big|\mismatch{q}{p} + \mismatch{p}{r} \big| \hspace*{-2pt}
+\hspace*{-2pt} \partitionBethe^p \big|\mismatch{q}{p}\big|\Big)^2}\nonumber.
\end{align}

Note that we have applied (<ref>) so that every mismatch-term is strictly positive.
It is thus straightforward to see, by comparing all terms, that the numerator is strictly smaller than the denominator for every variable $\RV{i} \in \setOfNodes$ so that

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} }  < 1.
\end{align}

In particular for models with two equal-sized patches, we can simplify the error ratio (<ref>) considerably.

Let $d = \mismatch{q}{r}>0$, then

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} } < \frac{ \sum_{\RV{i}\in\setOfNodes}|\partitionBethe^q d|^2}
{ \sum_{\RV{i}\in\setOfNodes}|\partitionBethe^q d + \partitionBethe^p \mismatch{p}{q}|^2} < 1.
\end{align}

Note that Corollary <ref> is an immediate consequence of Theorem <ref>.
Additionally we present an alternative proof that admits some intuitive arguments in Appendix <ref>.

It follows that the state preserving fixed point $p$ minimizes the marginal error inside $\Region$ irrespective of $\FB^p$.
This has drastic implications and forbids any relationship between the fixed point minimizing the marginal error and the one minimizing the partition function error.

Free Energy Minimizing Fixed PointaccuracyBP:theory:minimum
However, despite Theorem <ref>, the question remains where the difference between $\EPartition{m}$ and $\EMarginal{m}$ stems from?

We will now answer this question and provide conditions for $\argmin\EPartition{m} = \argmin\EMarginal{m}$ to be valid.
We further present an approximate condition for the
state-preserving fixed point $p$ to simultaneously provide the most accurate marginals and minimize $\FB$.
Therefore, let us define the following variables (cf. Section <ref> in the appendix for a formal introduction):
$\setOfEdges_P$ is the set of all boundary edges;
$\setOfEdges_C $ is the set of edges between variables that favor different states;
$N_f$ and  $N_c$ are the numbers of flipped and non-flipped variables;
and $\Delta \SB$ is the difference in the entropy between two fixed points.

Let us consider the state-preserving fixed point $p$  with $\FB^p$ and some other fixed point with $\FB^m$.
Then,  $\FB^p < \FB^m$  is the global minimum if

\begin{align}
2J(|\setOfEdges_P|-|\setOfEdges_C |) < \field{}(N-N_c+N_f) + \Delta \SB.
\label{eq:bound_approx}
\end{align}

The proof of Theorem <ref> is deferred to Appendix <ref>.

For models with two equal-sized patches and couplings strong enough for the entropy-term to vanish
we can further simplify (<ref>) significantly and
state that:

The state-preserving fixed point provides the most accurate marginals and the global minimum $\FB^p$ if
$\parameter \in \Region$ and if

\begin{align}
2 \sqrt{N} \coupling{}{} < N\field{}.
\label{eq:bound_approx2}
\end{align}

For the specific case of a grid graph with two equal-sized patches (Example <ref>) we can further simplify the condition from Theorem <ref>.
Therefore, note that for $\FB^p < \FB^q$ to be satisfied, we have $N_c = N_f$ and $|\setOfEdges_P| = \sqrt{N}$ so that (<ref>) reduces to

\begin{align}
2 J\sqrt{N} & \leq \field{}N+\Delta \SB. \label{eq:bound_exact_extreme_ex1}
\end{align}

The definition of $\Region$ requires strong interactions $\coupling{}{}$ so that the entropy terms in the free energy is small. We can consequently approximate (<ref>) by neglecting the entropy terms.

\begin{align}
2 J\sqrt{N} & \leq \field{}N.\label{eq:bound_exact_extreme_ex1_approx}
\end{align}

These sufficient conditions for (<ref>) provide a guideline when it would be safe to select the fixed point according to the partition function value.
This correspondence tends to hold for models with strong local potentials $\field{}$ and with increased model-size $N$ as shown in Corollary <ref>.

In Section <ref> we had relied on the assumption that  finding the global minimum of $\FB$ gives us the most accurate marginals and partition function.
This is a strong assumption that – although never formally verified – was generally believed to be true.

In this chapter we aimed to verify whether such a relationship holds in general.
Therefore, we studied the relationship between the accuracy of the marginals and the partition function at stationary points of the Bethe free energy, with far-reaching implications for approximate inference methods that operate on the Bethe free energy.
To do so, we introduced a new class of models first.
These so-called patch potential models exhibit lots of structure that enabled us to analyze the solution space thoroughly.
Yet, patch potential models proved to be flexible enough to produce some surprising insights.

First, we elaborated on the existence of a well-behaved region in parameter space for which the number of fixed points depends only on the number of patches (instead of the variables).

Second, this well-behaved region allowed us to assess the correspondence between the accuracy of the marginals and the partition function;
we showed that this common assumption is not true in general and explained why – instead of the global minimum – the most accurate marginals may be found at a local minimum of $\FB$.

Finally, we inspected under which conditions this mismatch arises and further introduced guarantees for the global minimum of $\FB$ to remain optimal with respect to marginal accuracy.
Note that the mismatch is effectively attributable to finite-size effects which might explain why this behavior is not known in the physics literature, where the focus lies on infinite-size – or at least very large – models.
Yet, models of relatively small size do play an important role in many applications of BP.

The analysis of patch potential models may serve as a foundation that enables the extension of survey propagation to problems beyond constrained satisfaction problems.
So far this has been limited by the potentially huge amount of fixed point.
Our definition of the well-behaved region and the study of patch potential models as a whole suggests that it may be very much possible to obtain the set of all fixed points efficiently, as long as the model is sufficiently structured.

Moreover, our newly developed understanding of the relationship between the accuracy of the marginals and the partition function has a notable impact on our theoretical analysis of SBP in Section <ref>.
There we have limited our attention to attractive homogeneous models where the accuracy of both quantities can be used in an interchangeable way.
Whether it is the minimum (i.e., the Bethe free energy) or the minimizer (i.e., the pseudomarginals) that is responsible for the optimality of SBP needs to be reassessed.
It is not clear if it is really the global minimum of $\FB$ that originates from the start point.
On the contrary, our minimal patch potential model of Example <ref> shows that the state-preserving fixed point defines the solution path, so that SBP may very well be in favor of obtaining the fixed point with the most accurate marginals.
This could be an explanation for the surprisingly accurate results of SBP for general models and  would immensely strengthen the practical relevance of SBP as no method is known so far that deliberately aims to obtain fixed point with the most accurate marginals.

Discussion and Open Questionsdiscussion
There must be some way out of here,
Said the joker to the thief.Bob Dylan
In this thesis, we performed a systematic analysis of BP's solution space.
Finding all fixed points of BP is a relevant but hard problem, except for a few restricted models.
We took inspiration from a set of diverse scientific fields to tackle this problem:
in particular, we framed BP as dynamical systems and formulated the fixed point equations.
Drawing from computational mathematics, we established a way to solve
the set of fixed point equations and computed all fixed points for a range of problems.

The knowledge of the full solution space then served as a cornerstone for evaluating the accuracy and the convergence properties of BP.
Moreover, we related those performance properties to the parameterization of a given model (i.e., the model size and the specifications of the potentials) and explained how the performance of BP changes if we tune the model.

A detailed summary of our main contributions is presented in each chapter's conclusion.
Here we  summarize our most interesting findings and discuss how we advanced the understanding of BP.
Our findings satisfy a twofold interest:
they advance the theoretical understanding and suggest various possibilities of enhancing BP's performance.

* From a theoretical perspective, we made the influence of the model parameters on the performance of BP explicit.
We sum up our key-insights as follows:

The influence of the model size is hard to pinpoint down.
On the one hand, larger models tend to have a higher average degree, which affects the convergence properties slightly negatively.
On the other hand, we established a positive effect of the model size on the marginal accuracy.

The influence of the potentials is much more apparent.
Strong pairwise potentials influence the performance of BP detrimentally,
whereas strong local potentials increase the accuracy and the convergence properties.

Additionally, we demonstrated a considerable accuracy gap between the best possible and the worst possible fixed point of BP.
This poses a fundamental problem when deriving performance guarantees as is not obvious to which fixed point BP will converge.

* From a practical perspective, we justified the exploration of multiple fixed points, intending to select one with good approximation quality.
We discussed the underlying mechanisms and limitations of established modifications, for example, damping or scheduling.

We further proposed one particular modification that aims to obtain the global minimum of the Bethe free energy. This method, SBP, consistently obtains more accurate marginals than BP and provides accurate marginals for models where BP fails to converge.

Even the minimization of the Bethe free energy, however, has its limitations if one is only interested in the marginals; we exemplified and explained why the most accurate marginals may not be found at the global minimum of the Bethe free energy.

The analysis of BP's solution space addressed some long-standing questions but we are still far away from understanding every aspect of BP.
Below we summarize some intriguing questions that emerged while working on this thesis and that were left unanswered.
We distinguish three different directions that appear to be worth pursuing in particular:

* Structure of the Solution Space:

Although this thesis obtained the full solution space for some models and, in doing so, provided novel insights into the properties of BP, computing the solution space for more complex models remains elusive.
As we have seen in Chapter <ref>, however, it is precisely the consideration of more complex models that can lead to fascinating insights.

The extension of the NPHC method to larger models was primarily hindered by the involved computation of the root count.
So far, we only relied on some meta-heuristics to compute the root count.
Most relevant models, be it grid graphs or models arising in the context of error-correcting codes, however, exhibit a special graph structure that directly determines the structure of the fixed point equations.
A first step towards computing the root count for complex models could be to exploit the graph structure and thus reduce the overall complexity of this crucial step.
Alternatively, it would be relevant (from a mathematical perspective) to reformulate the problem to an equivalent system of equations with fewer complex solutions and a lower BKK bound.
Such problem-tailored approaches would extend the applicability of the NPHC method and, when applied to large models, would have the potential to provide even more insights into the behavior of BP.

Traditionally, one is often interested in specifying regions with a unique fixed point.
We have shown that this seems to be a rather limiting point of view as combinations of multiple fixed points often provide strikingly accurate results.
Although obtaining the set of all fixed points is, in general, a hard problem,  we have seen in Chapter <ref> that certain regions in the parameter space exist for which only a few fixed points are present.
This suddenly opens the door for numerical methods that efficiently obtain all fixed points and enhance the accuracy by combining them.

When defining well-behaved regions of BP we would consequently like to initiate a shift from conditions for uniqueness to conditions for structured, albeit possibly multiple, fixed points.
Fairly substantial work has been conducted in this matter for the special case of optimization problems.
Developing similar results for more general models is a necessary step to assess the relevance of methods that rely on considering multiple fixed points and to elaborate on their capabilities.

* Global Convergence Properties:
We have put a lot of emphasize on the  local stability analysis in Chapter <ref>.
Let us stress the notion of local here again:
we considered a fixed point as stable if the messages will converge to the fixed point inside its neighborhood.
In general, one can, however, not count on bringing the messages close enough to the fixed point and it is not only the local stability that is important for the convergence properties of BP;
even more so it is the region of attraction.
The region of attraction describes the range of message values for which BP will converge to a given fixed point.
This is particularly relevant in practice as BP sometimes fail to converge despite the existence of  stable fixed points (unless initialized very close to the fixed point).

Such a global perspective also highlights the influence of the initial message values on the convergence properties of BP.
Besides being convenient, uniform initialization tends to favor good fixed points; it remains an open problem to answer what is so special about uniform initialization and under which conditions uniform initialization is optimal.
We expect
that extending the local stability analysis and accounting for the regions of attraction as well will provide many answers to those questions.
Besides, this could potentially lead to variants of BP that, even if initialized
far away from any fixed point, explore the parameter space in a way such that the messages enter a region of attraction at some point, ultimately driving the messages into convergence.

* Enhancing BP with Respect to Marginal Accuracy:
The main contribution of Chapter <ref> was to elaborate on the difference between the accuracy of the marginals and the partition function.
Our analysis revealed that the fixed point providing the most accurate marginals may only be a local minimum.
Note that most variants that aim to enhance BP are either heuristics that only aim to enforce convergence or are theoretically well-motivated and focus on the quality of the partition function approximation.

For many applications, we are, however, ultimately interested in enhancing the quality of the marginals (cf. error-correcting codes in Section <ref>).
It would thus be of great relevance to manipulate the update equation in a way that enforces convergence towards a fixed point with accurate marginals.
Enforcing convergence towards one particular fixed point would further enable one to come up with realistic  performance guarantees, even in the presence of multiple fixed points.

We have proposed SBP that is guaranteed to obtain the most accurate marginals for attractive models with unidirectional potentials.
Looking at the evolution of the fixed points on patch-potential models, it seems as if SBP is capable of tracking the state-preserving fixed point as well.
Thus, SBP is already one possible candidate for obtaining accurate marginals.
It would be interesting to elaborate on this observation and substantiate this claim in a more formal way.
Essentially, the advantages of SBP boil down to providing a favorable initialization for BP.
This highlights the importance of the initial messages once more and raises the question if there is a general way of initializing the messages that will lead to accurate marginals.

Besides the role of the initialization, scheduling plays an important role in determining the fixed point of BP.
Again, one would hope that “good” scheduling methods enforce convergence towards an accurate fixed point.
Existing scheduling methods are either adaptive or only take the structure of the model into account.
The performance of BP, however, not only depends on the structure of the model but on the potentials as well.
Therefore, if the aim is to obtain accurate marginals, the value of the potentials should not be neglected and it seems promising to come up with a fixed schedule that takes the values of the potentials into account as well, for example by scheduling the messages in a way that prioritizes regions with strong local potentials.

Proofs from Chapter <ref>selfguided:proofs
This Section contains all the detailed proofs deferred from Section <ref>.

Proof of Lemma <ref>selfguided:proofs:2
Essentially, we first show that $\msg{i}{j}{1}/ \msg{i}{j}{-1}$ increases monotonically with $\coupling{i}{j}$ and then express the pseudomarginals in terms of (<ref>) and (<ref>).

Let us denote the messages on $\ugm[0]$ and on $\ugm[1]$ by $\msg{i}{j}{}_0$ and  $\msg{i}{j}{}_1$ respectively.
Further, let all local potentials be positive, i.e., $\field{i} > 0$, and let all pairwise potentials of $\ugm[1]$ be $\epsilon$-larger than those of $\ugm[0]$, i.e., $0 < \coupling{i}{j}^{0} = \coupling{i}{j}^{1}-\epsilon$. Note that by assumption $\mean{i} \in (0,1]$ so that

\begin{align}
\msg{i}{j}{+1} \geq \msg{i}{j}{-1}. \label{eq:appendix:ratio}
\end{align}

First, we show that for all $\edge{i}{j} \in \setOfEdges$

\begin{align}
\frac{\msg[\circ]{i}{j}{+1}_0}{\msg[\circ]{i}{j}{-1}_0} < \frac{\msg[\circ]{i}{j}{+1}_1}{\msg[\circ]{i}{j}{-1}_1}.
\label{eq:appendix:msgratio1}
\end{align}

Therefore, consider the update rule of (<ref>) for both states

\begin{align}
\msg[n+1]{i}{j}{+1}_1 \propto   e^{\coupling{i}{j} + \field{i} +\epsilon} \!\!\!\!\!\!\!\!\!  \prod \limits_{\RV{k} \in \{\neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\!\! \msg[n]{k}{i}{+1}_1
+ e^{-\coupling{i}{j} - \field{i} -\epsilon} \!\!\!\!\!\!\!\!\! \prod \limits_{\RV{k} \in \{\neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\!\! \msg[n]{k}{i}{-1}_1,
\label{eq:appendix:update_pos}
\end{align}

\begin{align}
\msg[n+1]{i}{j}{-1}_1 \propto   e^{-\coupling{i}{j} + \field{i} -\epsilon} \!\!\!\!\!\!\!\!\! \prod \limits_{\RV{k} \in \{\neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\!\! \msg[n]{k}{i}{+1}_1
+ e^{\coupling{i}{j} - \field{i} +\epsilon} \!\!\!\!\!\!\!\!\! \prod \limits_{\RV{k} \in \{\neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\!\! \msg[n]{k}{i}{-1}_1.
\label{eq:appendix:update_neg}
\end{align}

In (<ref>) the larger product is multiplied by $e^{\epsilon}$ and the smaller product is divided by $e^{\epsilon}$. For (<ref>) it is exactly the other way round so that the ratio between the messages increases which proofs (<ref>).
We shall denote the imposed difference $\delta \in \REALPos$ on the messages by

\begin{align}
\msg[\circ]{i}{j}{+1}_1 = \msg[\circ]{i}{j}{+1}_0+\delta,\label{eq:appendix:msgdiff1}\\
\msg[\circ]{i}{j}{-1}_1 = \msg[\circ]{i}{j}{-1}_0-\delta.\label{eq:appendix:msgdiff2}
\end{align}

Second, we show that $m_{i}^{0} < m_{i}^{1}$ which is an immediate consequence of plugging (<ref>) and (<ref>) into (<ref>).

Finally, it remains to show that $0 \stackrel{(i)}{<} \chi_{ij}^{0} \stackrel{(ii)}{<} \chi_{ij}^{1}$. Without loss of generality we assume that all variables have equal degree $d+1$ and constant coupling strength $\coupling{i}{j}  = \coupling{}{}$.
First we show that (i) holds, i.e., $\chi=\chi_{ij}^{0}$ is positive.
Let us express the marginals by (<ref>) and denote the messages by $\mu = \msg{i}{j}{1}_0$. It follows that $\msg{i}{j}{-1}_0 = (1-\mu)$ and that

\begin{align}
\chi\! &=\! e^{\coupling{}{}+2\field{}} \mu^{2d}\!\! + \!e^{\coupling{}{}-2\field{}} (1\!-\!\mu)^{2d}\!\! - 2 e^{-J} \mu^{d} (1\!-\!\mu)^{d}.
\label{eq:correlation:appdx}
\end{align}

Let us further represent the messages by $\mu = 1/2+x$ with $x \in [0,1/2]$. It follows that

\begin{align}
\chi \stackrel{(a)}{\geq} &\left(\left(1/2+x\right)^{2d}+\left(1/2-x\right)^{2d}\right)
- 2 \left(1/2+x\right)^d\left(1/2-x\right)^d %\label{eq:correlation:positive:2} \nonumber\\
= &\left(\left(1/2-x\right)^d-\left(1/2+x\right)^d\right)^2 \label{eq:correlation:positive:3}\nonumber\\
\stackrel{(b)}{\geq}  & 0,
\end{align}

where $(a)$ follows from neglecting all exponential terms and thus upper bounding the positive term and lower bounding the negative term (with equality if and only if $\coupling{}{} = 0$ and $\field{} = 0$) and
$(b)$ is a direct consequence of the square in (<ref>).
Now let us show that (ii) holds, i.e.,
$\chi$ increases monotonically, by taking the derivative of (<ref>), so that

\begin{align}
\frac{\partial}{\partial \mu}\chi =
& 2d \left(e^{\coupling{}{}+2\field{}} \mu^{2d-1} - e^{\coupling{}{}-2\field{}} \left(1-\mu\right)^{2d-1}\right)
+\!\! 2 d e^{-J}\!\! \left( \mu^{d} (1-\mu)^{d-1} \!\!- \mu^{d-1} (1-\mu)^{d} \right) \label{eq:correlation:monotone:1}\\
\stackrel{(a)}{\geq} &  2 d e^{-J} \left( \mu^{d} (1-\mu)^{d-1} - \mu^{d-1} (1-\mu)^{d} \right) \label{eq:correlation:monotone:2}\nonumber\\
\stackrel{(b)}{\geq} & 0,
\end{align}

where $(a)$ follows from neglecting the, strictly positive, first term in (<ref>), and $(b)$
is a direct consequence from (<ref>).

Proof of Theorem <ref>selfguided:proofs:th9

A unique start point $\pseudomarginalsMinLocal(\scaling=0)$ exists by Theorem <ref> that equals the exact pseudomarginals $\pseudomarginalsExact(\scaling=0)$ and, for $\field{i}> 0$, has positive mean and correlation), i.e., $\meanMinLocal{i}(\scaling=0) > 0$.

Consequently, Lemma <ref> applies, which further implies
that $\meanMinLocal{i}(\scaling)$ and $\chi_{ij}(\scaling) $ are monotonically increasing; moreover, $\meanMinLocal{i}(\scaling)$ and $ \chi_{ij}(\scaling) $ are continuous by Theorem <ref>.

This further implies that the Bethe free energy $\FBLocalMin{m}(\scaling)$ decreases.
Let $\FBLocalMin{m}(\scaling=1)$ correspond to the endpoint of the solution path $c(\scaling)$ that
emerges from the origin; then, it immediately follows that the error with respect to the endpoint $\FBLocalMin{m}(\scaling=1)$ decreases along the solution path: i.e., consider two arbitrary values $m,k \in [0,1]$ such that $k>m$, then
$|\FBLocalMin{m}(\scaling_m)-\FBLocalMin{m}(\scaling=1)| \geq |\FBLocalMin{m}(\scaling_{k})-\FBLocalMin{m}(\scaling = 1)|$.

It remains to show that SBP obtains the fixed point $\FBLocalMin{m}(\scaling=1)$ that minimizes the error with respect to the exact free energy,
i.e., $m = \argmin_{m\in\setOfMinimaSol}\EPartition{m}$ .

Therefore consider the fact, that attractive models with $\field{i} > 0$ have a unique fixed point
that satisfies  $\meanMinLocal{i}(\scaling) \in (0,1]$ [165].
A second minimum with negative means, however, may emerge for sufficiently large values of $\coupling{i}{j}$. We denote this alternative stationary point by $\FBLocalMin{n}$.
This minimum $\FBLocalMin{n}$, if it exists, is close to being symmetric, i.e., $\meanMinLocal{i}^m(\scaling) -\epsilon = - \meanMinLocal{i}^n(\scaling)$ and $\chi_{ij}^m(\scaling) = {\chi}^{n}_{ij}(\scaling) +\epsilon$.

Now let us express the Bethe free energy in (<ref>) of both fixed points $\pseudomarginalsMinLocal$ and $\pseudomarginalsMinLocalNeg$ in terms of their energy and entropy according to $\FB = \EB - \SB$ (cf. Section <ref>). Then, as a consequence of symmetry of the entropy $\SB(\pseudomarginalsMinLocalNeg) \cong \SB(\pseudomarginalsMinLocal)$
and as a consequence of singleton marginals that are not aligned to the local potentials in
(<ref>) $\EB(\pseudomarginalsMinLocalNeg)>\EB(\pseudomarginalsMinLocal)$.
It follows that $ \FB(\pseudomarginalsMinLocalNeg) \geq \FB(\pseudomarginalsMinLocal)$ (cf. [113]).
Consequently, with $\FB(\pseudomarginalsMinLocal)$ being more negative it follows that the fixed point $m$ constitutes the global minimum of the Bethe free energy.

That is, SBP proceeds along a solution path that leads towards the global minimum of the Bethe approximation.
In particular, by considering the fact that the exact free energy is upper bounded by the Bethe approximation for attractive models [123], this implies that the fixed point obtained by SBP indeed minimizes the approximation error, i.e,  $m = \argmin_{m\in\setOfMinimaSol}\EPartition{m}$ holds.

This concurrently implies that $\pseudomarginalsMinLocal(\scaling)$  is optimal with respect to marginal accuracy,
i.e., no stable fixed point – which corresponds to a local minimum of the Bethe free energy – exists that provides more accurate marginals.
Note that attractive models exhibit so-called replica symmetric solutions where the Bethe free energy
has two minima at most.

In particular, this allows one to express
the exact marginals as a convex combination of all fixed points, i.e, $\pseudomarginalsExact =  \frac{1}{\sum\limits_{\partitionBethe \in \setOfMinimaSol} \partitionBethe}
\sum\limits_{(\pseudomarginals,\partitionBethe)\in\setOfMinimaSol}\pseudomarginals\cdot\partitionBethe$ (cf. Section <ref>).

It follows by the existence of at most two solutions that the fixed point that minimizes the Bethe free energy is also more accurate.

Proofs from Chapter <ref>accuracy:proofs
This Section contains all the detailed proofs for Chapter <ref>
Proof of Theorem <ref>accuracy:proofs:effective_field
Here we show how all incoming messages from outside the patch can be subsumed into an effective local field.

First let us revisit the update equation from $\RV{i}$ to $\RV{j}:\RV{j} \in \patchRV{i}$

\begin{align}
\msg[n+1]{i}{j}{} \propto \sum \limits_{x_i \in \sampleSpace{X}}  \pairwiseShort{i}{j}\localShort{i} \!\!\! \!\prod \limits_{\RV{k} \in \{\neighbors{i} \backslash \RV{j}\}} \!\!\!\! \msg[n]{k}{i}{}. \nonumber
\end{align}

Now we group the incoming messages into two groups, i.e., messages coming from outside the patch and messages coming from inside the patch so that

\begin{align}
\msg[n+1]{i}{j}{} \propto \sum \limits_{x_i \in \sampleSpace{X}}  \pairwiseShort{i}{j}\localShort{i}
\prod \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \!\!\!\!\!\!\!\! \msg[n]{k}{i}{}
\prod \limits_{\RV{k} \in \{ \patchRV{i} \cap \neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\! \msg[n]{k}{i}{}. \nonumber
\end{align}

Now we make use of the fact that we are only dealing with binary random variables for which $\msg{i}{j}{-1} = (1-\msg{i}{j}{1})$ and express the message explicitly by

\begin{align}
\msg[n+1]{i}{j}{} \propto& \exp(J\RVval{j}) \exp(\field{i})
\prod \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \!\!\!\!\!\!\!\! \msg[n]{k}{i}{1}
\prod \limits_{\RV{k} \in \{ \patchRV{i} \cap \neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\! \msg[n]{k}{i}{1} \nonumber \\
& + \exp(-J \RVval{j}) \exp(-\field{i})
\prod \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \!\!\!\!\!\!\!\! (1-\msg[n]{k}{i}{1})
\prod \limits_{\RV{k} \in \{ \patchRV{i} \cap \neighbors{i} \backslash \RV{j}\}} \!\!\!\!\!\!\!\! (1-\msg[n]{k}{i}{1}).
\end{align}

We now want to get rid of the first product and absorb the influence of these messages into the local field.
In particular we aim to express it according to

\begin{align}
\exp \big( \effectiveField{i}\RVval{i}) & =  \localShort{i}  \prod \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \!\!\!\!\!\!\!\! \msg[n]{k}{i}{} \label{eq:ef1} \nonumber \\
&= \exp\big((\field{i}+c)\RVval{i}\big)\cdot\exp(g).
\end{align}

In order to do so we take the logarithm of the product over all messages in (<ref>) and put them into the exponent with the local field so that for $\RVval{i}=+1$

\begin{align}
\exp (\effectiveField{i})  &= \exp\bigg(\field{i} +\sum \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \log\big(\msg{k}{i}{1}\big)\bigg) \nonumber\\
& = \exp\big(\field{i} + \sum \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} c_i + \sum \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} g_i\big),
\label{eq:equate1}
\end{align}

and for $\RVval{i}=-1$

\begin{align}
\exp (-\effectiveField{i}) &= \exp\bigg(-\field{i} + \sum \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \log\big(1-(\msg{k}{i}{1}\big)\bigg) \nonumber\\
& = \exp\big(-\field{i} - \sum \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} c_i + \sum\limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}}  g_i\big).
\label{eq:equate2}
\end{align}

Equating the coefficients for $c_i$ and $g_i$ in (<ref>) and (<ref>) gives us the final results:

\begin{align}
c_i &= \frac{1}{2}\bigg( \log \msg{k}{i}{1} -  \log \big(1-\msg{k}{i}{1}\big)\bigg), \nonumber \\
c   &= \sum\limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \arctanh\big(2\msg{k}{i}{1} - 1\big),\\
g   &= \frac{1}{2} \log \prod \limits_{\RV{k} \in \neighbors{i} \backslash \{\RV{j} \cap \patchRV{i}\}} \Big(\msg{k}{i}{1}-\msg{k}{i}{1}^2\Big).
\end{align}

Note that we can further express the message for the second state $\msg{i}{j}{-1}$ in a similar way, with the only difference that the values of the pairwise potentials change. Consequently we get exactly the same result for $g$ again;
this allows us to neglect the influence of $g$ altogether, as it will be canceled out when normalizing the messages so that the sum up to one.

Proof of Corollary <ref>accuracy:proofs:error_ratio_ex1
We want to compare error of the state-preserving fixed point $\EMarginal{p}$ to the error $\EMarginal{q}$ of a fixed point that has all marginals biased towards one state.
We already discussed the error-ratio in a general manner in the proof of Theorem <ref> in Section <ref>;
here we provide a more accessible proof for the special case of a model with two patches, i.e., for Example <ref>.

For a symmetric model with two equal-sized patches we evaluate the error ratio between the state-preserving fixed point $p$ and one of the fixed points that have all marginals biased towards one state, these are $q$ and $r$ and have symmetric marginals.
Further assume that the fixed points $q$ and $r$ minimize the Bethe free energy, i.e.,

\begin{align}
\FB^q = \FB^r &< \FB^p,\\
\partitionBethe^q = \partitionBethe^r &> \partitionBethe^p.\label{eq:bethe_optimal}
\end{align}

Then we want to show that (<ref>) does not imply that $\EMarginal{q} < \EMarginal{p}$, i.e., we want to show that
$\frac{\EMarginal{p}}{\EMarginal{q} } < 1$ despite (<ref>); therefore, we express the ratio of the marginal errors according to

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} } &= \frac{ \sum_{\RV{i}}|\sum_{m\backslash p} \partitionBethe^m \mismatch{m}{p}|^2}
{ \sum_{\RV{i}}|\sum_{m\backslash q } \partitionBethe^m \mismatch{m}{q}|^2} \nonumber \\
&\stackrel{}{=}\frac{ \sum_{\RV{i}}|\partitionBethe^q \mismatch{q}{p}+\partitionBethe^r \mismatch{r}{p}|^2}
{ \sum_{\RV{i}}|\partitionBethe^q \mismatch{r}{q} + \partitionBethe^p \mismatch{p}{q}|^2}.
\label{eq:marginal_ratio2}
\end{align}

Note that because of (<ref>) we have

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} } &\stackrel{}{=} \frac{ \sum_{\RV{i}}|\partitionBethe^q \big( \mismatch{q}{p}+\mismatch{r}{p}\big)|^2}
{ \sum_{\RV{i}}|\partitionBethe^q \mismatch{r}{q} + \partitionBethe^p \mismatch{p}{q}|^2}\nonumber\\
&\stackrel{(a)}{=}\frac{ \sum_{\RV{i}}|\partitionBethe^q \big( \mismatch{q}{p}+\mismatch{r}{p}\big)|^2}
{ \sum_{\RV{i}}\big(\partitionBethe^q \mismatch{q}{r} + \partitionBethe^p \mismatch{q}{p}\big)^2}.
\end{align}

where (a) follows from the fact that $\mismatch{r}{q} < 0$,  $\mismatch{p}{q}<0$, and the symmetry property (<ref>).

We further denote the constant difference between the biased fixed points by

\begin{align}
0<  \mismatch{q}{r} = d < 1\label{eq:mismatch_bound}.
\end{align}

We can use the expansion property (<ref>) to bound the numerator as $|\mismatch{q}{p}+\mismatch{r}{p}|^2 < \mismatch{q}{r}^2 = d^2$ so that

\begin{align}
\frac{\EMarginal{p}}{\EMarginal{q} } < \frac{ \sum_{\RV{i}}\partitionBethe^q d^2}
{ \sum_{\RV{i}}\big(\partitionBethe^q d + \partitionBethe^p \mismatch{q}{p}\big)^2}.
\end{align}

Which completes the proof as $ \mismatch{q}{p} > 0$

Proof of Theorem <ref>accuracy:proofs:marginal_equal_partition

Let us consider three different stationary points $\FB^p$ (state-preserving),
$\FB^q$ (biased to one state), and $\FB^m$ that has some patches flipped.
Note that we consider $\FB^q$ as a limiting case for $\FB^m$.

We will denote the number of variables that are aligned with the local field $N_c$ and the number of flipped variables $N_f$.

The set of boundary edges that connects two patches is denoted by

\begin{align}
\setOfEdges_P = \{\edge{i}{j}\in\setOfEdges : \RV{i} \in \patchRV{i}, \RV{j} \in \patchRV{j} \neq \patchRV{i}\},
\end{align}

and the set of edges that connects two patches that have their variables not aligned is denoted by

\begin{align}
\setOfEdges_C = \{\edge{i}{j} \in \setOfEdges: \RV{i} \in \patchRV{i}, \RV{j} \in \patchRV{j} \neq \patchRV{i}, \sgn \big( \pmfApprox{\RV{i}}(\RV{i}=1)-0.5 \big) \neq \sgn \big( \pmfApprox{\RV{j}}(\RV{j}=1) -0.5\big)\}.
\end{align}

Note that $\setOfEdges_P$ is constant for a specified model, whereas $\setOfEdges_C$ depends on the specific fixed point.
We consequently have $\setOfEdges_C  \leq \setOfEdges_P$ with equality for the state preserving fixed point $p$.

Our analysis is restricted to $\parameter \in \Region$ per definition: one crucial consequence is that $J>J_A(\field{})$ and that most marginals either have $\pmfApprox{\RV{i}}(\RVval{i}) \approx 1$ or $\pmfApprox{\RV{i}}(\RVval{i}) \approx 0$.
We will exploit this fact and express all marginals according to $\pmfApprox{\RV{i}}(\RVval{i}) \in \{0,1\}$ which allows us to simplify $\FB$, as defined in Section <ref>, according to

\begin{align}
\FB^p &= -N\field{}-\big(|\setOfEdges|-2|\setOfEdges_P| \big)\coupling{}{} - \SB^p\\
\FB^m &= -\big(N_c - N_f \big)\field{}-\big(|\setOfEdges|-2|\setOfEdges_C| \big)\coupling{}{} - \SB^m.
\end{align}

Let $\Delta \SB = \SB^p-\SB^m$ be the difference in the entropy, then we can express the conditions for the state-preserving fixed point to have a lower value $\FB^p \leq \FB^m$ according to

\begin{align}
-N\field{}-\big(|\setOfEdges|-2|\setOfEdges_P| \big)\coupling{}{} &\leq -\big(N_c - N_f \big)\field{}-\big(|\setOfEdges|-2|\setOfEdges_C| \big)\coupling{}{} +\Delta \SB \nonumber \\
2 J(-|\setOfEdges_C|+|\setOfEdges_P|) & \leq \field{}(N-N_c+N_f)+\Delta \SB \label{eq:bound_exact}
\end{align}

Now let us express (<ref>) for the fixed points that has all variables biased to one state, i.e., $|\setOfEdges_C|=0$. Then, the state-preserving fixed point has a lower value $\FB^p < \FB^q$ if

\begin{align}
2 J|\setOfEdges_P| & \leq \field{}(N-N_c+N_f)+\Delta \SB \label{eq:bound_exact_extreme}
\end{align}

We present the pseudocode for NIBP and WDBP. Removing the if then else clause in line 8 to 11 of NIBP and substituting it with $\mu_{m}^{n}$ $\leftarrow$ $\mu_{m}^{n+1}$ reduces Algorithm <ref> to RBP. The maximum number of iterations is denoted by $N_{BP} = 2.5 \cdot 10^5$ and $\epsilon = 10^{-3}$. $\text{NrOfMessages} = 2|\setOfEdges|$ denotes the overall number of messages in the graph.

Noise Injection Belief Propagation (NIBP)
Graph $G = (\mathbf{X},\mathbf{E})$
Converged messages $\setOfMessages[n]$
$m \leftarrow 1$

$\mu^{n+1}_{m}$ $\leftarrow$ $\setOfMessages[n]$
$r_m \leftarrow$ $|\mu_m^{n} - \mu_m^{n+1}|$

$n < N_{BP}$ $\max |\setOfMessages[n] - \setOfMessages[n+1]| > \epsilon$

$m \leftarrow \argmax_m \vm{r}^{n}$
$\mu_{m}^{n}$ $\leftarrow$ $\mu_{m}^{n+1} + \mathcal{N}(0,\sigma)$

$\mu_{m}^{n}$ $\leftarrow$ $\mu_{m}^{n+1}$

$j \leftarrow 1$

$\mu_{j}^{n+1} \leftarrow$ $\setOfMessages[n]$
$r_j \leftarrow |\mu_{j}^{n+1} - \mu_{j}^{n}|$

$n = n + 1$

Weight Decay Belief Propagation (WDBP)
Graph $\graph = (\mathbf{X},\mathbf{E})$
Converged messages $\setOfMessages[n]$
$m \leftarrow 1$

$\mu_{m}^{n+1}$ $\leftarrow$ $\setOfMessages[n]$
$r_m \leftarrow$ $|\mu_m^{n} - \mu_m^{n+1}|$
(m) $\leftarrow$ $1$

$n < N_{BP}$ $\max |\setOfMessages[n] - \setOfMessages[n+1]| > \epsilon$

$m \leftarrow \argmax_m \vm{r}^{n}$
$\mu_{m}^{n}$ $\leftarrow$ $\mu_{m}^{n+1}$
(m) $\leftarrow$ (m) + 1
$j \leftarrow 1$

$\mu_{j}^{n+1} \leftarrow$ $\setOfMessages[n]$
$r_j \leftarrow \frac{|\mu_{j}^{n+1} - \mu_{j}^{n}|}{\textnormal{NrUpdates(j)}}$

$n = n + 1$

Guide to Quotesquotes

The attentive reader has probably recognized that this thesis features an opening quote for every chapter.
It was important to me to connect with all the quotes on a personal level (be it by one's art or by a general appreciation of a person's life)
Yet, this was not enough:
every quote must also have a close connection to the respective chapter.
This connection, however, may not always be as obvious to the reader as it was to me.
It is precisely for this reason that I will now reveal the perceived meaning of each quote, and how I see it connect to the content of the chapter.

Chapter <ref>: We quote the commonly used English translation “Uncertainty is an uncomfortable position. But certainty is an absurd one.” of the original line “Le doute n'est pas une état bien agréable, mais l'assurance est un état ridicule” <cit.>.
This statement from Voltaire elegantly connects to the central concept of this thesis, probabilistic graphical model, as it can be interpreted as a praise for probability.

Chapter <ref>:
“A mind is like a parachute. It doesn't work if it is not open.” This quote by Frank Zappa seems to align nicely with a background-chapter that brings different scientific fields together into one powerful concept.
In particular, since it was Frank Zappa's ability to draw inspiration from an unimaginable wide range of musical genres that finally coalesced together and created some stunning albums.

Chapter <ref>: Ludwig Boltzmann played a formative role in the foundational years of statistical physics and laid out the groundwork for many concepts discussed in this chapter.
Beyond that, there is undeniable truth in his statement “The stars bend like slaves to laws not decreed for them by human intelligence, but gleaned from them.” quoted from [50].
One could argue that this whole thesis adheres to this statement as we put considerable effort into  carefully studying the behavior of belief propagation to develop a clearer picture of its underlying working-principles.

Chapter <ref>: “Inside a broken clock; Splashing the wine; With all the rain dogs; Taxi, we'd rather walk...” [142].
The song figuratively refers to the rain dogs as the straying dogs that are seemingly lost after the rain has washed away all their scent.
The underlying meaning is elegantly encompassed by just another quote of Tom Waits that states: “We are buried beneath the weight of information, which is being confused with knowledge; quantity is being confused with abundance and wealth with happiness.”.
Although arguable more general and touching a couple of interesting points of today's society, Tom Waits' statement reflects the experiences one makes when acquainting oneself with the subtleties of a new field.
When embarking into uncharted territory and trying to grasp all impressions one can only sympathize with the rain dogs that must feel similar.

Chapter <ref>:
“Travel makes one modest. You see what a tiny place you occupy in the world.” [44].
Flaubert urges the need for always taking a look at the surrounding to put things into perspective.
BP often behaves like a creature of habit, once it decides for one specific fixed point it neglects all others.
In this chapter we break up with this habit and take a global perspective on the solution space, essentially traveling through the solution space.

Chapter <ref>:
“The most significant dimension of freedom is the freedom from one's own ego - in other words, from the feeling that I am the center of everything.”
Voytek Kurtyka is an outstanding mountaineer that played an important role in bringing the modern alpine-style climbing into the greater ranges.
More importantly, he was always honest about his inner struggle between the desire to nourish one's ego and the awareness that there is no inbred reason to take oneself to serious.
One could argue that our proposed algorithm, self-guided BP, undergoes a similar struggle.
At the beginning, all variables take up a purely ego-centered standpoint and no interactions between them take place.
Only incrementally, as the couplings are incorporate, the variables contribute to the joint assignment of the model and put their own constraints behind.

Chapter <ref>:
“To the wise, life is a problem; to the fool, a solution.”
Wise and fool are maybe strong words;
but one could have been satisfied with the preceding chapters and could have neglected the unanswered questions lingering around instead of being curious and trying to gain some further insights.
On a side-node, Marcus Aurelius was a great proponent of the philosophy of stoicism, a philosophy that is arguable beneficial when working on a thesis for many years.

Chapter <ref>:
“There must be some way out of here; Said the joker to the thief“ [37].
This song puts you in the midst of a discussion, with the joker struggling with his purpose.
Even though it was inevitably to experience some struggles in the process of writing everything up, there is no easy way out and, ultimately, it is just a question of getting things done before one can appreciate the completed task.

[1]
Sungsoo Ahn, Michael Chertkov, Jinwoo Shin, and Adrian Weller.
Gauged mini-bucket elimination for approximate inference.
Proceedings of AISTATS, 2018.

[2]
E. Allgower and K. Georg.
Introduction to Numerical Continuation Methods.
Society for Industrial and Applied Mathematics, 2003.

[3]
Srinivas M Aji and Robert J McEliece.
The generalized distributive law.
IEEE Transactions on Information Theory, 46(2):325–343, 2000.

[4]
Winfried Auzinger and Hans J Stetter.
An elimination algorithm for the computation of all zeros of a system
of multivariate polynomial equations.
In Proceedings of International Conference on Numerical
Mathematics, pages 11–30. Springer, 1988.

[5]
Winfried Auzinger and Hans J Stetter.
A study of numerical elimination for the solution of multivariate
polynomial systems.
Technical report, Institut für Angwandte und Numerische Mathematik,
Vienna University of Technology, 1989.

[6]
David N. Bernstein.
The number of roots of a system of equations.
Functional Analysis and Its Applications, 9:1–4, 1975.

[7]
Hans A Bethe.
Statistical theory of superlattices.
Proceedings of the Royal Society of London. Series
A-Mathematical and Physical Sciences, 150(871):552–575, 1935.

[8]
Richard L Burden and Douglas J Faires.
Numerical Analysis.
Brooks Cole Cengage, 9 edition, 2011.

[9]
Claude Berrou, Alain Glavieux, and Punya Thitimajshima.
Near Shannon limit error-correcting coding and decoding:
Turbo-codes. 1.
In Proceedings of IEEE International Conference on
Communications, volume 2, pages 1064–1070, 1993.

[10]
Andries E Brouwer and Willem H Haemers.
Spectra of Graphs.
Springer, 2011.

[11]
Daniel J. Bates, Jonathan D. Hauenstein, Andrew J. Sommese, and Charles W.
Bertini: Software for numerical algebraic geometry.
Available at bertini.nd.edu with permanent doi:

[12]
K Binder.
Finite size effects on phase transitions.
Ferroelectrics, 73(1):43–67, 1987.

[13]
Christopher Bishop.
Pattern Recognition and Machine Learning.
Springer, 2006.

[14]
Alfredo Braunstein, Farbod Kayhan, Guido Montorsi, and Riccardo Zecchina.
Encoding for the blackwell channel with reinforced belief
In IEEE International Symposium on Information Theory, 2007.

[15]
Hans L Bodlaender, Arie MCA Koster, Frank van den Eijkhof, and Linda C van der
Pre-processing for triangulation of probabilistic networks.
In Proceedings of UAI, pages 32–39, 2001.

[16]
A Braunstein, M Mézard, and R Zecchina.
Survey propagation: An algorithm for satisfiability.
Random Structures & Algorithms, 27(2):201–226, 2005.

[17]
Stephen G Brush.
History of the Lenz-Ising model.
Reviews of Modern Physics, 39(4):883, 1967.

[18]
Bruno Buchberger.
Ein Algorithmus zum Auffinden der Basiselemente des
Restklassenringes nach einem nulldimensionalen Polynomideal.
PhD thesis, University of Innsbruck, 1965.

[19]
Bruno Buchberger.
Bruno buchberger’s phd thesis 1965: An algorithm for finding the
basis elements of the residue class ring of a zero dimensional polynomial
Journal of Symbolic Computation, 41(3-4):475–511, 2006.

[20]
D Batra, P Yadollahpour, A Guzman-Rivera, and G Shakhnarovich.
Diverse m-best solutions in markov random fields.
In Computer Vision–ECCV 2012, pages 1–16. Springer, 2012.

[21]
Michael Chertkov and Vladimir Y Chernyak.
Loop series for discrete statistical models on graphs.
Journal of Statistical Mechanics: Theory and Experiment, (06),

[22]
Venkat Chandrasekaran, Misha Chertkov, David Gamarnik, Devavrat Shah, and
Jinwoo Shin.
Counting independent sets using the Bethe approximation.
SIAM Journal on Discrete Mathematics, 25(2):1012–1034, 2011.

[23]
Michael Chertkov, Vladimir Y Chernyak, and Razvan Teodorescu.
Belief propagation and loop series on planar graphs.
Journal of Statistical Mechanics: Theory and Experiment, (05),

[24]
Tianran Chen and Tien-Yien Li.
Homotopy continuation method for solving systems of nonlinear and
polynomial equations.
Communications in Information and System, 15(2):119–307, 2015.

[25]
Tianran Chen, Tsung-Lin Lee, and Tien-Yien Li.
Hom4ps-3: A parallel numerical solver for systems of polynomial
equations based on polyhedral homotopy continuation methods.
In Proceedings of International Congress on Mathematical
Software, pages 183–190. Springer, 2014.

[26]
D Cox, J Little, and D O'Shea.
Ideals, Varieties, and Algorithms, volume 3.
Springer, 1992.

[27]
D Cox, J Little, and D O'Shea.
Using Algebraic Geometry, volume 185.
Springer, 2005.

[28]
T Chen and D Mehta.
On the network topology dependent solution count of the algebraic
load flow equations.
IEEE Transactions on Power Systems, 2017.

[29]
T Chen, D Mehta, and M Niemerg.
A network topology dependent upper bound on the number of equilibria
of the Kuramoto model.
arXiv preprint arXiv:1603.05905, 2016.

[30]
Gregory F Cooper.
The computational complexity of probabilistic inference using
Bayesian belief networks.
Artificial Intelligence, 42(2-3):393–405, 1990.

[31]
Amin Coja-Oghlan and Will Perkins.
Bethe states of random factor graphs.
Communications in Mathematical Physics, 366(1):173–201, 2019.

[32]
Alicia Dickenstein and Ioannis Z Emiris.
Solving Polynomial Equations.
Springer, 2005.

[33]
Reinhard Diestel.
Graph Theory.
Springer, 2016.

[34]
Paul Dagum and Michael Luby.
Approximating probabilistic inference in Bayesian belief networks
is NP-hard.
Artificial Intelligence, 60(1):141–153, 1993.

[35]
Amir Dembo and Andrea Montanari.
Ising models on locally tree-like graphs.
The Annals of Applied Probability, 20(2):565–592, 2010.

[36]
Rina Dechter and Irina Rish.
Mini-buckets: A general scheme for bounded inference.
Journal of the ACM, 50(2):107–153, 2003.

[37]
Bob Dylan.
All Along The Watchtower.
Columbia Records, 1967.

[38]
Frederik Eaton and Zoubin Ghahramani.
Model reductions for inference: Generality of pairwise, binary, and
planar factor graphs.
Neural Computation, 25(5):1213–1260, 2013.

[39]
Bradley Efron and Trevor Hastie.
Computer Age Statistical Inference.
Cambridge University Press, 2016.

[40]
Gal Elidan, Ian McGraw, and Daphne Koller.
Residual belief propagation: Informed scheduling for asynchronous
message passing.
In Proceedings of UAI, 2006.

[41]
László Erdös.
Universality of wigner random matrices: a survey of recent results.
Russian Mathematical Surveys, 66, 2011.

[42]
Richard P. Feynman.
Statistical Mechanics: A Set Of Lectures.
Benjamin/Cummings, 1972.

[43]
Michael E Fisher.
Critical temperatures of anisotropic ising lattices. ii. general
upper bounds.
Physical Review, 162(2):480, 1967.

[44]
Gustave Flaubert.
Flaubert in Egypt: A Sensibility on Tour: A Narrative Drawn from
Gustave Flaubert's Travel Notes & Letters.
Penguin, 1996.

[45]
Toulouse Gérard.
Theory of the frustration effect in spin glasses.
Communications on Physics, 2:115–119, 1977.

[46]
Robert G Gallager.
Information Theory and Reliable Communication, volume 2.
Springer, 1968.

[47]
Hans O Georgii.
Gibbs Measures and Phase Transitions, volume 9.
Walter de Gruyter, 2011.

[48]
Amir Globerson and Tommi S Jaakkola.
Convergent propagation algorithms via oriented trees.
In Proceedings of UAI, 2007.

[49]
Vicenç Gómez, Joris M Mooij, and Hilbert J Kappen.
Truncating the loop series expansion for belief propagation.
Journal of Machine Learning Research, 8, 2007.

[50]
GEORGE GREENSTEIN.
Science: The bulldog: A profile of ludwig boltzmann.
The American Scholar, 60(1):97–105, 1991.

[51]
Robert B Griffiths.
Correlations in Ising ferromagnets. ii. external magnetic fields.
Journal of Mathematical Physics, 8(3):484–489, 1967.

[52]
David M Grobman.
Homeomorphism of systems of differential equations.
Doklady Akademii Nauk SSSR, 128(5):880–881, 1959.

[53]
Philip Hartman.
A lemma in the theory of structural stability of differential
Proceedings of the American Mathematical Society,
11(4):610–620, 1960.

[54]
John M Hammersley and Peter Clifford.
Markov fields on finite graphs and lattices.
Unpublished manuscript, 1971.

[55]
Tom Heskes.
Stable fixed points of loopy belief propagation are minima of the
Bethe free energy.
In Proceedings of NIPS, volume 15, pages 359–366, 2003.

[56]
Tom Heskes.
On the uniqueness of loopy belief propagation fixed points.
Neural Computation, 16(11), 2004.

[57]
John J Hopfield.
Neural networks and physical systems with emergent collective
computational abilities.
Proceedings of the National Academy of Sciences,
79(8):2554–2558, 1982.

[58]
Geoffrey E Hinton and Terrence J Sejnowski.
Learning and relearning in boltzmann machines.
Parallel Distributed Processing: Explorations in the
Microstructure of Cognition, 1(282-317):2, 1986.

[59]
Birkett Huber and Bernd Sturmfels.
A polyhedral method for solving sparse polynomial systems.
Mathematics of Computation, 64(212):1541–1555, 1995.

[60]
Tamir Hazan and Amnon Shashua.
Convergent message-passing algorithms for inference over general
graphs with convex free energies.
In Proceedings of UAI, 2008.

[61]
Kerson Huang.
Statistical Mechanics.
John Wiley & Sons Inc, 1963.

[62]
Alexander T Ihler, John W Fisher, and Alan S Willsky.
Loopy belief propagation: Convergence and effects of message errors.
In Journal of Machine Learning Research, pages 905–936, 2005.

[63]
Alexander T Ihler.
personal communication, UAI, 2017-08-12.

[64]
Alexander T Ihler.
Inference in Sensor Networks: Graphical Models and Particle
PhD thesis, MIT, 2005.

[65]
Alexander T Ihler.
Accuracy bounds for belief propagation.
In Proceedings of UAI, pages 183–190, July 2007.

[66]
Michael I Jordan, Zoubin Ghahramani, Tommi S Jaakkola, and Lawrence K Saul.
An introduction to variational methods for graphical models.
Machine Learning, 37(2):183–233, 1999.

[67]
Tommi Jaakkola and Michael I Jordan.
Recursive algorithms for approximating probabilities in graphical
In Proceedings of NIPS, pages 487–493, 1997.

[68]
Rudolph E Kalman.
A new approach to linear filtering and prediction problems.
Journal of Basic Engineering, 82(1):35–45, 1960.

[69]
Frank R. Kschischang and Brendan J. Frey.
Iterative decoding of compound codes by probability propagation in
graphical models.
IEEE Journal on Selected Areas in Communications,
16(2):219–230, 1998.

[70]
Daphne Koller and Nir Friedman.
Probabilistic Graphical Models: Principles and Techniques.
MIT press, 2009.

[71]
Daphne Koller, Nir Friedman, Sašo Džeroski, Charles Sutton, Andrew
McCallum, Avi Pfeffer, Pieter Abbeel, Ming-Fai Wong, David Heckerman, Chris
Meek, et al.
Introduction to Statistical Relational Learning.

[72]
Frank R Kschischang, Branden J Frey, and Hans A Loeliger.
Factor graphs and the sum-product algorithm.
IEEE Transactions on Information Theory, 47(2):498–519, 2001.

[73]
Askold G Khovanski.
Newton polyhedra and the genus of complete intersections.
Funkts. Anal. Pril., 12(1):51–61, 1978.

[74]
Christian Knoll, Florian Kulmer, and Franz Pernkopf.
Self-guided belief propagation–a homotopy continuation method.
arXiv preprint arXiv:1812.01339, 2018.

[75]
Achim Kehrein, Martin Kreuzer, and Lorenzo Robbiano.
An algebraist’s view on border bases.
In Solving Polynomial Equations, pages 169–202. Springer,

[76]
Christian Knoll, Dhagash Mehta, Tianran Chen, and Franz Pernkopf.
Fixed points of belief propagation – an analysis via polynomial
homotopy continuation.
IEEE Transactions on Pattern Analysis and Machine Intelligence,

[77]
Vladimir Kolmogorov.
Convergent tree-reweighted message passing for energy minimization.
IEEE transactions on Pattern Analysis and Machine Intelligence,
28(10):1568–1583, 2006.

[78]
Christian Knoll and Franz Pernkopf.
On loopy belief propagation – local stability analysis for
non-vanishing fields.
In Proceedings of UAI, 2017.

[79]
Christian Knoll and Franz Pernkopf.
Belief propagation: Accurate marginals or accurate partition function
– where is the difference?
In Proceedings of UAI, 2019.

[80]
Christian Knoll, Franz Pernkopf, Dhagash Mehta, and Tianran Chen.
Fixed point solutions of belief propagation.
In NIPS-Workshop: Advances in Approximate Bayesian Inference,

[81]
Martin Kreuzer and Lorenzo Robbiano.
Computational Commutative Algebra 1, volume 1.
Springer, 2000.

[82]
Martin Kreuzer and Lorenzo Robbiano.
Computational Commutative Algebra 2, volume 2.
Springer, 2005.

[83]
Christian Knoll, Michael Rath, Sebastian Tschiatschek, and Franz Pernkopf.
Message scheduling methods for belief propagation.
In Proceedings of ECML PKDD, pages 295–310. Springer, 2015.

[84]
AG Kushnirenko.
Newton polytopes and the Bezout theorem.
Funkts. Anal. Pril., 10(3), 1976.

[85]
Bernhard Korte and Jens Vygen.
Combinatorial Optimization, volume 3.
Springer, 2005.

[86]
Alejandro Lage-Castellanos, Roberto Mulet, Federico Ricci-Tersenghi, and
Tommaso Rizzo.
Replica cluster variational method: the replica symmetric solution
for the 2d random bond ising model.
Journal of Physics A: Mathematical and Theoretical, 46, 2013.

[87]
Tien-Yien Li.
Numerical solution of multivariate polynomial systems by homotopy
continuation methods.
Acta numerica, 6:399–436, 1997.

[88]
Tien-Yien Li.
Solving polynomial systems by the homotopy continuation method.
Handbook of Numerical Analysis, 11:209–304, 2003.

[89]
Qiang Liu and Alexander T Ihler.
Bounding the partition function using Hölder's inequality.
In Proceedings of ICML, pages 849–856, 2011.

[90]
Martijn Leisink and Hilbert J Kappen.
Bound propagation.
Journal of Artificial Intelligence Research, 19:139–154, 2003.

[91]
Hans A Loeliger.
An introduction to factor graphs.
IEEE Signal Processing Magazine, 21(1):28–41, 2004.

[92]
Steffen L Lauritzen and David J Spiegelhalter.
Local computations with probabilities on graphical structures and
their application to expert systems.
Journal of the Royal Statistical Society. Series B, pages
157–224, 1988.

[93]
David JC MacKay.
A conversation about the Bethe free energy and sum-product.
Technical Report of MERL., 2001.

[94]
David JC MacKay.
Information Theory, Inference and Learning Algorithms.
Cambridge University Press, 2003.

[95]
Talya Meltzer, Amir Globerson, and Yair Weiss.
Convergent message passing algorithms: a unifying view.
In Proceedings of UAI, pages 393–401, 2009.

[96]
Ofer Meshi, Ariel Jaimovich, Amir Globerson, and Nir Friedman.
Convexifying the Bethe free energy.
In Proceedings of UAI. AUAI Press, 2009.

[97]
Joris M Mooij and Hilbert J Kappen.
On the properties of the Bethe approximation and loopy belief
propagation on binary networks.
Journal of Statistical Mechanics: Theory and Experiment,
2005(11):P11012, 2005.

[98]
Joris M Mooij and Hilbert J Kappen.
Sufficient conditions for convergence of the sum–product algorithm.
IEEE Transactions on Information Theory, 53(12):4422–4437,

[99]
Joris M Mooij and Hilbert J Kappen.
Bounds on marginal probability distributions.
In Proceedings of NIPS, pages 1105–1112, 2009.

[100]
Victorin Martin, Jean-Marc Lasgouttes, and Cyril Furtlehner.
The role of normalization in the belief propagation algorithm.
arXiv preprint arXiv:1101.4170, 2011.

[101]
Ernst W Mayr and Albert R Meyer.
The complexity of the word problems for commutative semigroups and
polynomial ideals.
Advances in Mathematics, 46(3):305–329, 1982.

[102]
H Michael Möller and Ferdinando Mora.
Upper and lower bounds for the degree of Gröbner bases.
EUROSAM 84, pages 172–183, 1984.

[103]
Marc Mezard and Andrea Montanari.
Information, Physics, and Computation.
Oxford University Press, 2009.

[104]
H Michael Möller.
Systems of algebraic equations solved by means of endomorphisms.
In International Symposium on Applied Algebra, Algebraic
Algorithms, and Error-Correcting Codes, pages 43–56. Springer, 1993.

[105]
Joris Marten Mooij.
Understanding and Improving Belief Propagation.
PhD thesis, Radboud University Nijmegen, 2008.

[106]
Bernard Mourrain.
Pythagore’s dilemma, symbolic-numeric computation, and the border
basis method.
In Symbolic-Numeric Computation, pages 223–243. Springer,

[107]
Marc Mezard, Giorgio Parisi, and Miguel Virasoro.
Spin Glass Theory and Beyond: An Introduction to the Replica
Method and Its Applications, volume 9.
World Scientific Publishing Co Inc, 1987.

[108]
H Michael Möller and Hans J Stetter.
Multivariate polynomial equations with multiple zeros solved by
matrix eigenproblems.
Numerische Mathematik, 70(3):311–329, 1995.

[109]
Kevin P Murphy.
Machine Learning: A Probabilistic Perspective.
MIT press, 2012.

[110]
Kevin P Murphy, Yair Weiss, and Michael I Jordan.
Loopy belief propagation for approximate inference: An empirical
In Proceedings of UAI, pages 467–475, 1999.

[111]
Manfred Opper and Ole Winther.
Tractable approximations for probabilistic models: the adaptive
Thouless-Anderson-Palmer mean field approach.
Physical Review Letters, 86(17):3695, 2001.

[112]
Payam Pakzad and Venkat Anantharam.
Belief propagation and statistical physics.
In Proceedings of Conference on Information Sciences and
Systems, 2002.

[113]
Xaq Pitkow, Yashar Ahmadian, and Ken D Miller.
Learning unbelievable probabilities.
In Proceedings of NIPS, pages 738–746, 2011.

[114]
Judea Pearl.
Probabilistic Reasoning in Intelligent Systems: Networks of
Plausible Inference.
Morgan Kaufmann Publishers, 1988.

[115]
R Peierls.
Statistical theory of superlattices with unequal concentrations of
the components.
Proceedings of the Royal Society of London. Series
A-Mathematical and Physical Sciences, 154(881):207–222, 1936.

[116]
Wei Ping and Alexander Ihler.
Belief propagation in conditional rbms for structured prediction.
Proceedings of AISTATS, 2017.

[117]
F Pernkopf, R Peharz, and S Tschiatschek.
Introduction to Probabilistic Graphical Models.
Academic Press’ Library in Signal Processing, 2014.

[118]
Siamak Ravanbakhsh and Russell Greiner.
Revisiting algebra and complexity of inference in graphical models.
arXiv preprint arXiv:1409.7410, 2014.

[119]
Siamak Ravanbakhsh and Russell Greiner.
Perturbed message passing for constraint satisfaction problems.
Journal of Machine Learning Research, 16:1249–1274, 2015.

[120]
Björn S Rüffer, Christopher M Kellett, Peter M Dower, and Steven R
Belief propagation as a dynamical system: The linear case and open
IET Control Theory & Applications, 4(7):1188–1200, 2010.

[121]
Dan Roth.
On the hardness of approximate reasoning.
Artificial Intelligence, 82(1-2):273–302, 1996.

[122]
Nicholas Ruozzi.
The Bethe partition function of log-supermodular graphical models.
In Proceedings of NIPS, pages 117–125, 2012.

[123]
Nicholas Ruozzi.
Beyond log-supermodularity: lower bounds and the Bethe partition
In Proceedings of UAI, pages 546–555, 2013.

[124]
Edward R. Scheinerman.
Invitation to Dynamical Systems.
Prentice Hall, 2000.

[125]
Jinwoo Shin.
Complexity of Bethe approximation.
In Proceedings of AISTATS, pages 1037–1045, 2012.

[126]
David Sontag and Tommi S Jaakkola.
New outer bounds on the marginal polytope.
In Proceedings of NIPS, pages 1393–1400, 2008.

[127]
Alaa Saade, Florent Krzakala, and Lenka Zdeborová.
Spectral clustering of graphs with the Bethe Hessian.
In Proceedings of NIPS, pages 406–414, 2014.

[128]
Alaa Saade, Florent Krzakala, and Lenka Zdeborová.
Spectral bounds for the ising ferromagnet on an arbitrary given
Journal of Statistical Mechanics, 2017(5), 2017.

[129]
Charles Sutton and Andrew McCallum.
Improved dynamic schedules for belief propagation.
In Proceedings of UAI, 2007.

[130]
Christopher Srinivasa, Siamak Ravanbakhsh, and Brendan Frey.
Survey propagation beyond constraint satisfaction problems.
In Proceedings of AISTATS, pages 286–295, 2016.

[131]
Hans J Stetter.
Numerical Polynomial Algebra, volume 85.
SIAM, 2004.

[132]
Gilbert Strang.
Introduction to Linear Algebra.
Wellesley-Cambridge Press, 5 edition, 2016.

[133]
Andrew J Sommese and Charles W Wampler.
The Numerical Solution of Systems of Polynomials Arising in
Engineering and Science, volume 99.
World Scientific, 2005.

[134]
Gerald Teschl.
Ordinary Differential Equations and Dynamical Systems.
American Mathematical Society, 2012.

[135]
Sekhar C Tatikonda and Michael I Jordan.
Loopy belief propagation and Gibbs measures.
In Proceedings of UAI, pages 493–500, 2002.

[136]
Nobuyuki Taga and Shigeru Mase.
Applications of Gibbs measure theory to loopy belief propagation
In Mexican International Conference on Artificial Intelligence,
pages 197–207, 2006.

[137]
Peng Hui Tan and Lars K Rasmussen.
Belief propagation for coded multiuser detection.
In IEEE International Symposium on Information Theory, pages
1919–1923, 2006.

[138]
Jan Verschelde.
Algorithm 795: Phcpack: A general-purpose solver for polynomial
systems by homotopy continuation.
ACM Transactions on Mathematical Software (TOMS),
25(2):251–276, 1999.

[139]
Andrew Viterbi.
Error bounds for convolutional codes and an asymptotically optimum
decoding algorithm.
IEEE Transactions on Information Theory, 13(2):260–269, 1967.

[140]
Oeuvres Complètes.

[141]
Pascal O Vontobel.
Counting in graph covers: A combinatorial characterization of the
bethe entropy function.
IEEE Transactions on Information Theory, 59(9):6018–6048,

[142]
Tom Waits.
Rain Dogs.
Island Records, 1985.

[143]
Martin Wainwright.
Stochastic processes on graphs with cycles: geometric and
variational approaches.
PhD thesis, Massachusetts Institute of Technology, 2002.

[144]
Yusuke Watanabe.
Discrete geometric analysis of message passing algorithm on
PhD thesis, The Graduate University for Advanced Studies, 2010.

[145]
Adrian Weller and Justin Domke.
Clamping improves TRW and mean field approximations.
In Artificial Intelligence and Statistics, pages 38–46, 2016.

[146]
Yair Weiss.
Correctness of local probability propagation in graphical models with
Neural Computation, 12(1), 2000.

[147]
Adrian Weller.
Methods for Inference in Graphical Models.
PhD thesis, Columbia University, 2014.

[148]
Adrian Weller.
Uprooting and rerooting graphical models.
In Proceedings of ICML, pages 21–29, 2016.

[149]
Yusuke Watanabe and Kenji Fukumizu.
Graph zeta function in the Bethe free energy and loopy belief
In Proceedings of NIPS, pages 2017–2025, 2009.

[150]
Eugene P Wigner.
On the distribution of the roots of certain symmetric matrices.
The Annals of Mathematics, 67(2):325–327, 1958.

[151]
Martin J Wainwright and Michael I Jordan.
Graphical models, exponential families, and variational inference.
Foundations and Trends in Machine Learning, 1(1–2):1–305,

[152]
Adrian Weller and Tony Jebara.
Bethe bounds and approximating the global optimum.
In Proceedings of AISTATS, pages 618–631, 2013.

[153]
Adrian Weller and Tony Jebara.
Approximating the Bethe partition function.
In Proceedings of UAI, 2014.

[154]
Adrian Weller and Tony Jebara.
Clamping variables and approximate inference.
In Proceedings of NIPS, pages 909–917, 2014.

[155]
Martin J Wainwright, Tommi Jaakkola, and Alan S Willsky.
Tree-based reparameterization for approximate inference on loopy
In Proceedings of NIPS, pages 1001–1008, 2002.

[156]
Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky.
Tree-based reparameterization framework for analysis of sum-product
and related algorithms.
IEEE Transactions on information theory, 49(5):1120–1146,

[157]
Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky.
Tree-reweighted belief propagation algorithms and approximate ML
estimation by pseudo-moment matching.
In Proceedings of AISTATS, 2003.

[158]
Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky.
A new class of upper bounds on the log partition function.
IEEE Transactions on Information Theory, 51(7):2313–2335,

[159]
Alan S Willsky, Erik B Sudderth, and Martin J Wainwright.
Loop series and Bethe variational bounds in attractive graphical
In Proceedings of NIPS, pages 1425–1432, 2008.

[160]
Max Welling and Yee Whye Teh.
Belief optimization for binary networks: A stable alternative to
loopy belief propagation.
In Proceedings of UAI, pages 554–561, 2001.

[161]
Max Welling and Yee Whye Teh.
Approximate inference in Boltzmann machines.
Artificial Intelligence, 143(1):19–50, 2003.

[162]
Adrian Weller, Kui Tang, Tony Jebara, and David Sontag.
Understanding the Bethe approximation: When and how can it go
In Proceedings of UAI, pages 868–877, 2014.

[163]
Henk Wymeersch.
Iterative Receiver Design, volume 234.
Cambridge University Press Cambridge, 2007.

[164]
Jonathan S Yedidia, William T Freeman, and Yair Weiss.
Generalized belief propagation.
In Proceedings of NIPS, pages 689–695, 2001.

[165]
Jonathan S Yedidia, William T Freeman, and Yair Weiss.
Constructing free-energy approximations and generalized belief
propagation algorithms.
IEEE Transactions on Information Theory, 51(7):2282–2312,

[166]
Allan Peter Young.
Spin Glasses and Random Fields, volume 12.
World Scientific, 1998.

[167]
Alan L Yuille and Anand Rangarajan.
The concave-convex procedure.
Neural Computation, 15(4):915–936, 2003.

[168]
Lenka Zdeborová and Florent Krzakala.
Statistical physics of inference: Thresholds and algorithms.
Advances in Physics, 65(5):453–552, 2016.