Loopy belief propagation estimates marginal probabilities in graphs with cycles by passing messages between neighboring variables. When it works, it is often very accurate. The trouble is that it often fails to converge in exactly the regimes where it would be most accurate. The known fixes each give something up. Convexified approximations always converge, but they are blurrier. Guaranteed-descent solvers for the Bethe free energy (the objective whose stationary points are belief propagation's fixed points) always converge, but only to whichever local minimum lies downhill from the starting point. We propose to start where a unique answer is guaranteed and move continuously to the objective we actually want. Concretely, we solve a provably convex surrogate of the Bethe free energy, then slide its entropy weights toward the true Bethe weights in small steps. At each step we re-solve from the previous answer. We watch the curvature of the objective to detect the points where the tracked minimum splits into several, and we branch there.
The claim is specific and testable. This path-following procedure should reach Bethe minima that belief propagation provably cannot reach. It should also reach lower-energy and more accurate minima than random restarts of a guaranteed-descent solver given the same compute. The benefit should concentrate in the strong-coupling, weak-field regime, where the tension between accuracy and convergence is worst.
Background and the gap
Three results frame the problem. Heskes shows that belief propagation behaves like gradient descent-ascent on a saddle-point form of the Bethe free energy. Every stable fixed point is therefore a local minimum, but some local minima repel the dynamics, and damping cannot rescue them. His 4-node Boltzmann machine is the canonical case: belief propagation cycles while a double-loop concave-convex procedure (CCCP) reaches the minimum. This result motivates our work.
On the convex side, Loh and Wibisono characterize exactly when a reweighted Bethe objective is concave: the counting weights must lie in the convex hull of single-cycle forests. Meshi et al. construct convex surrogates close to Bethe. One of them, convexBethe-c, projects the Bethe counting numbers onto the convex region. They also show that convexity costs accuracy relative to Bethe. Both papers supply our starting point, and both constrain us: whatever we end with must beat these surrogates, or the procedure has no purpose.
Stable Bethe solvers supply the inner machinery and define the limitation we attack. These include:
- CCCP for collective graphical models, from Nguyen et al., which converges in 100% of runs where nonlinear belief propagation fails 20–60% of the time.
- Sequential single-variable minimization for Ising models, from Tonosaki and Kabashima.
- Projected gradient descent with polynomial-time guarantees for bounded-degree binary models, from Shin.
All of them guarantee a stationary point or local minimum and say nothing about which one they reach. Meshi et al. explicitly do not adapt counting numbers during inference. Loh and Wibisono give no rule for choosing weights beyond the concavity boundary. Neither paper uses the convex solution as anything but a final answer. We use it as the first point on a path.
Core Claim
Write the free energy with counting numbers $c=(c_i,c_\alpha)$ as
$$F_c(b) = U(b) - \sum_\alpha c_\alpha H(b_\alpha) - \sum_i c_i H(b_i),$$
where:
- $b$ are pseudo-marginals on the local polytope (node and factor beliefs that agree on shared variables);
- $U$ is the expected energy;
- $H$ is Shannon entropy.
Bethe corresponds to $c^B$, with $c_\alpha=1$ and $c_i = 1-\deg(i)$. Let $c^0$ be the Meshi-style projection of $c^B$ into the Loh–Wibisono concavity region. Along the path
$$c(s) = (1-s)\,c^0 + s\,c^B, \qquad s\in[0,1],$$
the constraint $\sum_{\alpha\ni i}c_\alpha + c_i = 1$ (which Meshi et al. found important for accuracy) holds throughout, because it is affine.
At $s=0$ the objective has a unique minimizer. As $s$ grows, the tracked minimizer $b^\star(s)$ moves smoothly until the smallest eigenvalue of the Hessian of $F_{c(s)}$ reaches zero. The Hessian is taken restricted to the tangent space of the local polytope. That zero crossing is a bifurcation: new minima appear, and the global minimum can jump to a different branch.
Our algorithm does three things:
- It tracks $b^\star(s)$ with warm-started, budget-capped inner solves.
- It monitors the smallest curvature with a few Lanczos iterations on Hessian-vector products.
- At each zero crossing, it perturbs along the negative-curvature direction in both signs, follows each branch, and keeps the one with lower $F_{c(s)}$.
The endpoint at $s=1$ is a genuine Bethe local minimum. It is not a convexified surrogate. Nothing restricts it to minima that belief propagation finds stable.
The curvature trace has a second use. It gives an empirical, potential-dependent measure of how far past the topological concavity boundary a given model stays effectively convex along the path. This is the blind spot noted in Loh and Wibisono, whose conditions ignore interaction strengths. We treat this as a diagnostic, not a theorem. Positive local curvature certifies only a local minimum.
Research Program
The first component is the tracker, for pairwise models with binary and small categorical variables. The inner solver is CCCP with a hard cap of a few inner sweeps per step. Warm starts should make each solve cheap, since the answer moves little between steps. The step size in $s$ adapts to how far $b^\star$ moved on the previous step. For binary Ising models, we also implement a sequential-minimization inner solver, following Tonosaki and Kabashima, to check that the gains come from the path and not from the solver.
The second component is the bifurcation handler. It uses curvature estimates from automatic differentiation, projected onto the null space of the consistency constraints, and deflation to find the escape direction. Branching is capped at a small number of simultaneous branches, so that compute stays within a declared multiple of a single CCCP run.
The third component is analysis. On small models we enumerate all Bethe minima by dense multi-start. We then record which minimum the path selects, whether that minimum is stable under belief propagation (spectral radius of the linearized message map below one), and whether lower Bethe energy actually means lower marginal error. That last question is not guaranteed: Bethe is not a bound, and its lowest minimum need not be the most accurate. We will report the answer either way.
A secondary probe returns to the "unlearnable" regime of Heinemann and Globerson. We run the tracker on $3\times3$ toroidal models whose parameters are chosen to target marginals in that regime. The question is whether the tracker reaches a minimum that belief propagation cannot, and whether that minimum's marginals move closer to the target. This is the open question those authors leave.
Baselines
The naive reference point is undamped and damped belief propagation. We sweep the damping factor over a fixed grid, allow a generous iteration cap, and report both convergence rate and the error of the last iterate. Beating it means converging where it fails and matching or improving accuracy where it succeeds.
The first convex competitor is convexBethe-u from Meshi et al., together with tree-reweighted belief propagation. Meshi et al. report that convexBethe-u beats TRW-opt and matches or exceeds belief propagation in strong-interaction, weak-field regimes. No reported numerical result for marginal error on toroidal grids was found on Lacuna for this method, so we will rerun it ourselves on identical models. Beating it means lower marginal $L_1$ error at comparable wall-clock time.
The strongest competitor for our specific claim is multi-start CCCP on the true Bethe objective, following Nguyen et al.. It converges reliably, and restarts address the choice of minimum directly. The closest reported figure for a stable solver is not directly comparable. On $20\times20$ Ising grids, Ibrahim et al. report that GEM-MP converged in 97% of cases, versus 82% for $L_2$-convex methods. We include GEM-MP as a convergence reference on those grids. Our fair-comparison rule is to give multi-start CCCP exactly the total inner-solver sweeps and wall-clock time that the tracker consumes, including its branches. Initializations are uniform, random, and the belief propagation last iterate. Beating it means reaching the lowest known Bethe minimum more often, and achieving lower marginal error, at equal compute.
We also run two ablations that isolate the key ingredient:
- Tracking without branching (always follow the current branch). This tests whether bifurcation detection matters.
- Direct gradient descent on the Bethe objective, initialized at the $s=0$ convex solution. This tests whether the path matters or only the starting point does.
Why not just…?
Why not just damp belief propagation? Heskes proves that damping stabilizes only instabilities caused by step size. It cannot turn a repelling minimum into an attracting one. The nonlinear belief propagation failure rates in Nguyen et al. show that the problem arises in practice. Our 4-node Boltzmann machine experiment checks the claim directly: we sweep damping on that model and show whether damped belief propagation still oscillates while the tracker lands on the minimum.
Why not just use the convex surrogate and stop? It always converges, but Meshi et al. document an accuracy loss relative to Bethe. The Loh–Wibisono region is purely topological, so strong multi-cycle couplings are over-smoothed. If the endpoint at $s=1$ were no more accurate than the point at $s=0$, the path would add nothing. The $s=0$ versus $s=1$ comparison is therefore built into every experiment, and it is where the proposal most plausibly fails.
Why not just restart CCCP from many random points? This is the real threat. On small graphs with few minima, a handful of restarts may find the best one as cheaply as tracking does. Our bet is that in hard regimes the basin of the good minimum shrinks as coupling grows, so random starts rarely land in it, while continuation reaches it by construction. The equal-compute comparison settles this. We will report the coupling strength and graph size at which each method wins. If restarts match the tracker everywhere, we will say so.
Why not anneal temperature instead of counting numbers? Deterministic annealing — scaling potentials from weak to full strength — is another natural continuation. It could work as well. We run it as a variant of the tracker with identical branching logic. Counting-number continuation has a principled advantage: its start point is certified unique for any potentials, whereas weak-coupling uniqueness holds only near zero coupling. Whether that advantage matters is an empirical question the ablation answers.
Proposed Experiments
Model classes. Binary Ising models on $n\times n$ toroidal grids for $n$ up to 16, where exact marginals come from transfer-matrix variable elimination, and on complete graphs $K_n$ for $n\le 18$, where exact marginals come from enumeration. These are the settings of Meshi et al. and Loh–Wibisono. Couplings are attractive and mixed, swept from weak to strong under weak fields.
Additional settings. - Heskes's 4-node Boltzmann machine, as a minimal existence check. - $20\times20$ Ising grids, to compare convergence against the GEM-MP figures. Here exact marginals are unavailable, so we compare Bethe energy and agreement with long-run Gibbs sampling. - The Heinemann–Globerson $3\times3$ probe.
Metrics. Mean and max marginal $L_1$ error, $\log Z$ error, Bethe energy attained, fraction of runs reaching the lowest enumerated minimum, fraction of final minima that are unstable under belief propagation, and wall-clock time.
Decisive checks.
1. On the 4-node model, the tracker must reach the minimum that belief propagation cannot. If it fails there, the design is wrong.
2. Across the coupling sweep, the tracker must beat equal-compute multi-start CCCP on the frequency of finding the lowest minimum in the strong-coupling regime.
3. Lower Bethe energy must translate into lower marginal error than convexBethe-u. If the lowest Bethe minimum turns out to be less accurate than the convex surrogate, that is a publishable negative finding about the accuracy-convergence paradox.
4. The no-branching ablation must lose in the regimes where the curvature trace shows zero crossings. This shows that bifurcation detection, not just warm starting, carries the gain.
References
- Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy
- Concavity of reweighted Kikuchi approximation
- Convexifying the Bethe Free Energy
- Approximate Inference Using DC Programming For Collective Graphical Models.
- Sequential Minimization of the Bethe Free Energy of Ising Spin Systems
- Complexity of Bethe Approximation
- What Cannot be Learned with Bethe Approximations
- Improving probabilistic inference in graphical models with determinism and cycles