Entropy Homotopy for Loopy Message Passing

Belief propagation is a message-passing algorithm in which each variable in a graphical model repeatedly exchanges local summaries ("messages") with its neighbours. On graphs with cycles it is known to be searching for a stationary point of a non-convex objective, the Bethe free energy. When that objective has several minima, which happens when interactions are strong or conflicting, the algorithm may oscillate forever, or it may settle into a poor minimum that depends on where it started. Convex replacements for the Bethe objective remove the extra minima, but they also shift the answer away from the more accurate Bethe solution. We propose to use the convex objective only as a starting point. Concretely, we interpolate the entropy term continuously from a provably convex reweighted entropy to the exact Bethe entropy, keep the model's energy fixed throughout, and track the solution along the path. Where the tracked minimum becomes a point that ordinary message passing cannot converge to, we hand it to a slower solver that is guaranteed to descend.

The idea in two sentences: existing continuation methods for belief propagation deform the model, by turning couplings up from zero. We instead deform the approximation, by moving the entropy from convex to Bethe. The tracked solution therefore always reflects the real potentials, and the convex end has exactly one answer.

Core Claim

A large share of belief propagation's failures in hard regimes are optimization failures, not approximation failures. The Bethe objective often has a low-energy, accurate minimum that standard updates either cannot reach or actively repel. An entropy-space continuation path, combined with a stability monitor that switches solvers when needed, should reach that minimum far more reliably than coupling-space continuation, damping, restarts, or a single warm start from a convex solution. This should hold most clearly on frustrated models, where couplings mix attractive and repulsive signs.

Background and Positioning

The method rests on the view, formalised by Generalized Belief Propagation, that loopy belief propagation fixed points are stationary points of the constrained Bethe free energy. The messages play the role of Lagrange multipliers. Variational Message Passing and Local Constraint Manipulation in Factor Graphs and Unifying Message Passing Algorithms Under the Framework of Constrained Bethe Free Energy Minimization extend this view to cover variational message passing, belief propagation and expectation propagation as different local constraints on one objective. Senöz et al. state outright that none of these updates is guaranteed to find the global minimum on cyclic graphs. This family of results supplies our method: we stay inside the constrained free-energy family and add a path through it.

Two results constrain the design.

Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy proves that stable belief propagation fixed points are Bethe minima. It also shows that some minima repel the algorithm's descent–ascent dynamics, and that damping cannot fix this. A continuation method that only runs belief propagation along the path will therefore fail exactly where the good minimum is a repeller. This is why our method monitors stability and switches to a double-loop solver.

Convexifying the Bethe Free Energy reweights the entropy with "counting numbers" to obtain a single minimum. It reports that ordinary loopy belief propagation remains more accurate in weak-interaction regimes. This tells us that the convex point should be an entrance to the path, not the destination.

The closest prior method motivates and frames the proposal. Self-Guided Belief Propagation - A Homotopy Continuation Method scales all couplings from zero to their target values and warm-starts belief propagation at each stage. It has guarantees only for attractive models, uses a fixed small number of stages, and does not track bifurcations, which are points where the solution path splits. When coupling-space continuation crosses the point where several solutions appear, it follows whichever branch it is on. That branch is decided by the weak-coupling solution, which carries no information about the target model's strong interactions. Entropy-space continuation differs on three counts. It keeps the full energy term at every stage. Its starting point is the unique minimum of an objective that already "sees" frustration. And its path can be checked for stability with the same Jacobian test Heskes uses.

Other work attacks the same failures differently. $\alpha$ Belief Propagation as Fully Factorized Approximation. softens updates with a divergence parameter that has to be tuned by hand. Local Message Passing on Frustrated Systems learns modified update rules with a small neural network. Both change the update rule. We keep the Bethe objective as the final target and change only the route taken to reach it.

The Method

For a factor graph, write the approximate entropy over node beliefs $q_i$ and factor beliefs $q_\alpha$ as $H_c(q)=\sum_\alpha c_\alpha H(q_\alpha)+\sum_i c_i H(q_i)$, where $c$ is a vector of counting numbers. Bethe corresponds to $c_\alpha=1$ and $c_i=1-d_i$, with $d_i$ the number of factors touching variable $i$. Let $c^{\mathrm{cvx}}$ be a convex choice that satisfies the variable-validity condition of Meshi et al., for example tree-reweighted weights or the projection used in their convexBethe-c method. The path is

$$F_t(q)=U(q)-H_{c(t)}(q),\qquad c(t)=(1-t)\,c^{\mathrm{cvx}}+t\,c^{\mathrm{Bethe}},\quad t\in[0,1],$$

where $U(q)$ is the expected energy under the beliefs and is the same at every $t$. Because $c(t)$ is a linear blend of two variable-valid vectors, it remains variable-valid along the whole path.

The algorithm proceeds in four steps. At $t=0$ it runs convex reweighted message passing to the unique fixed point. It then increases $t$ with an adaptive step: the step shrinks when the change in beliefs between stages exceeds a tolerance, which addresses the fixed-stage limitation of self-guided belief propagation. At each stage it warm-starts reweighted message passing from the previous messages. Finally, it estimates the spectral radius of the update Jacobian by power iteration. If the radius exceeds one, the current branch has become a Heskes-type repeller, and the solver switches to a convex–concave double-loop minimiser of $F_t$, warm-started at the tracked beliefs, until the radius drops back below one or $t=1$.

A turning point, where the solution path folds back, shows up as a near-singular Hessian along the path. There we spawn a small number of perturbed continuations and keep the branch with the lowest $F_1$. The bulk of the computation is ordinary message passing, so the per-stage cost matches belief propagation except on the segments that need the double-loop solver.

To connect with the variational message passing side, we also build a variant whose path starts from the best mean-field solution, the fixed point of the coordinate-ascent updates used by Variational Message Passing, instead of from a convex point. Taken literally, the "mean-field to Bethe" homotopy would start from an objective that is itself multimodal on frustrated models. This variant tests whether the convex start is what does the work.

Research Program

The project has three parts.

The first is an analysis of entropy-space paths on small models, complete graphs of 8 to 16 binary variables. On these, every Bethe minimum can be enumerated by running the double-loop solver from many starts, and exact marginals can be computed by summing over all states. The question is how often the $t=0$ minimum lies in the basin that connects continuously to the lowest Bethe minimum, as a function of coupling strength and the fraction of frustrated couplings. We will also try to prove that, for unidirectional models, the entropy path has no turning points, which would match the guarantee Knoll et al. give for coupling paths, and to identify which frustration patterns produce turning points.

The second is a general implementation for discrete factor graphs. It will be written in JAX so that it can be compared under the same parallel execution conditions as the PGMax belief propagation used by Learning Noisy OR Bayesian Networks with Max-Product Belief Propagation.

The third is a separation of two kinds of error. For every method we report how far its final Bethe free energy is from the best known Bethe minimum (optimization error), and separately how far that best Bethe minimum's marginals are from the exact ones (approximation error). This makes it explicit when even a perfect optimizer of the Bethe objective cannot help. Heskes notes an empirical link between non-convergence and poor Bethe quality. If it turns out that hard instances are exactly the ones where the Bethe minimum itself is inaccurate, that is a finding worth reporting, and it would limit the practical value of the method.

Baselines

The naive reference is undamped loopy belief propagation from uniform messages. It shows how often the problem arises at all.

The second baseline is damped belief propagation with damping tuned per regime. It is the standard practical fix, and Heskes argues it cannot help at repelling minima, so it tests whether repellers matter in practice.

The third baseline is multistart double-loop minimisation of the Bethe objective with random initial beliefs. It is matched to our method in total message-update budget. It is the honest "brute-force search" competitor, and on small graphs it also defines the best known minimum.

The fourth baseline is the convex endpoint alone: tree-reweighted message passing and convexBethe-u, following Convexifying the Bethe Free Energy. Our method should match it in hard regimes and beat it in easy ones.

The strongest existing competitor is self-guided belief propagation from Self-Guided Belief Propagation - A Homotopy Continuation Method. It is the only continuation method aimed at the same failure, and it was shown to beat damped belief propagation in mean squared error on grids, complete graphs and Erdős–Rényi graphs. No reported numerical result for self-guided belief propagation was found on Lacuna, so we will reimplement it. For fairness we will give it the same adaptive step-size rule and the same total update budget as our method, so that the comparison isolates where the path lives rather than how carefully it is stepped.

On frustrated systems we also include the learned updates of Local Message Passing on Frustrated Systems. For its 2×2 fully connected spin glass, it reports a KL divergence to the exact marginals of 0.014 for its learned method against 0.087 for the standard sum-product algorithm. We will reproduce this setting so the numbers are directly comparable. Gibbs sampling run to convergence serves as an accuracy reference, not as a cost competitor.

Three ablations isolate the key ingredients. The first is "warm-start once": jump straight from the convex solution to Bethe belief propagation with no intermediate stages. The second runs continuation without the stability-triggered solver switch. The third is the mean-field-start path.

Our method counts as beating self-guided belief propagation if, on frustrated instances at matched compute, it reaches the best known Bethe minimum on a clearly larger fraction of instances and lowers the median marginal error. A gain only on attractive models would not count, because there self-guided belief propagation already has guarantees.

Why not just…?

Why not just warm-start Bethe belief propagation from the convex solution? This is the most serious threat, because it captures most of the intuition at almost no cost. If the convex solution already lies in the good Bethe basin, intermediate stages add nothing. The warm-start-once ablation settles this directly. We expect warm-starting to fail most often at strong frustration, where a single jump from the convex solution can carry the messages past turning points of the path. If the ablation matches the full method across regimes, we will report that the convex start is the contribution and drop the claim that tracking the path matters.

Why not just use self-guided belief propagation with more stages? More coupling stages make the tracking smoother, but they do not change which branch is followed after the solutions split. The branch is set by the near-independent model, which knows nothing about the target's frustration. Our matched-budget comparison, run on mixed-sign spin glasses where Knoll et al. provide no guarantee, will show whether that branch choice is actually worse.

Why not just damp, or restart many times? Heskes proves that damping cannot stabilise an intrinsically repelling minimum. Restarts do not help either if every start runs belief propagation, because every run is repelled from that same minimum. Multistart double-loop search does avoid this, and on small graphs it is the oracle. The question is cost: we will measure how many restarts it needs to match our method's success rate as graph size grows.

Why not just tune $\alpha$-BP? $\alpha$ Belief Propagation as Fully Factorized Approximation. shows that $\alpha=0.2$ keeps a 9-node pairwise model stable beyond an edge probability of 0.35, where standard belief propagation collapses. However, it changes the objective being solved and needs per-problem tuning. We include it on that same benchmark and on the 8×8 multiple-input multiple-output (MIMO) detection task, where it is reported to beat the linear minimum mean square error (MMSE) estimator at linear rather than cubic cost.

Proposed Experiments

The main suite uses binary pairwise models. These include 10×10 toroidal grids, complete graphs with up to about 20 nodes (still small enough to enumerate exactly), and Erdős–Rényi graphs. Couplings are drawn uniformly from $[-\beta,\beta]$ for spin glasses or from $[0,\beta]$ for attractive models, with weak or strong fields, sweeping $\beta$ through the regime where loopy belief propagation stops converging. Metrics are the marginal KL divergence and mean squared error against exact values, the error in the log partition function, the final Bethe free energy minus the best known minimum, convergence rate, and total message updates. We will also run Heskes's 4-node Boltzmann machine as a unit test. Our method must reach the repelling minimum there and record the solver switch.

The applied check is soft symbol detection on the inter-symbol-interference channel and 8×8 MIMO settings used by Schmid et al. and Liu et al., measured by bit error rate and the error floor at high signal-to-noise ratio. The aim is to see whether reaching a better Bethe minimum removes the error floor without learned updates.

The decisive result is the frustrated-regime success rate against both self-guided belief propagation and the warm-start-once ablation, together with the optimization-versus-approximation split. If entropy continuation reaches better Bethe minima but marginal error does not fall, the proposal's practical claim fails while its optimization claim stands. We will report both outcomes.