Belief propagation (BP) is an algorithm that estimates probabilities in a network of interacting variables by having neighbors repeatedly pass messages until those messages stop changing. On networks with cycles ("loopy" BP), the run can settle at one of many stable answers, called fixed points. Each fixed point gives a different estimate of the partition function, the normalizing constant $Z$ needed for likelihoods and model comparison. Which fixed point the run reaches is an accident of initialization and update order, and existing tools for choosing the order are built for speed, not for answer quality. Knoll and Pernkopf show the choice matters. In attractive Ising models split into regions with different local fields, the fixed point with the best marginals and the fixed point with the best $Z$ are different points, and the gap opens once coupling exceeds $2\sqrt{N}J \ge N\theta$. Their analysis gives no algorithm for reaching the better-$Z$ point.
We propose treating loopy BP as a search over fixed points. The run first converges using residual scheduling, which updates first the message that would change most. It then repeatedly proposes flipping a coherent cluster of variables. The priority queue re-converges only the disturbed region, and the move is kept only if the Bethe estimate of $\log Z$ improves. The key point is cost. A move costs roughly the size of the region it disturbs, not the size of the graph. Because Region-II fixed points are combinations of per-region states, a local search can reach configurations that random restarts would hit only with probability exponentially small in the number of regions.
Core Claim
The claim is that, for a fixed budget of message updates, local fixed-point search with residual-confined re-convergence gives more accurate $\log Z$ estimates than three alternatives: a single residual-BP run, best-of-$K$ random restarts, and convexified or tree-reweighted variants. The advantage should be largest in the multi-fixed-point regime that Knoll and Pernkopf identify.
The selection criterion is the Bethe estimate, written in message form as
$$\log Z_{\text{Bethe}}(m) = \sum_\alpha \log Z_\alpha(m) + \sum_i \log Z_i(m) - \sum_{(i,\alpha)} \log Z_{i\alpha}(m).$$
Here $m$ is the full set of messages. $Z_\alpha$, $Z_i$ and $Z_{i\alpha}$ are the local normalizers of the factor beliefs, the variable beliefs, and the edge-wise products of messages. This expression equals the negative Bethe free energy at a fixed point. Its terms are local, so after a region re-converges the change in $\log Z_{\text{Bethe}}$ can be updated incrementally from the touched terms alone.
For attractive models, we hypothesize that the fixed point with the largest $Z_{\text{Bethe}}$ is the most accurate. We test this directly against exact $Z$ rather than assuming it. On frustrated models no such relation is expected, and we measure what happens there too.
Relation to Prior Work
Three papers supply the machinery. Residual Belief Propagation introduced the priority queue keyed on message change. It showed that this schedule converges where synchronous BP and tree reparameterization fail, including 7 of 8 protein-interaction networks. It never measured $Z$ or the Bethe energy, and it explicitly does not improve fixed-point quality. We reuse its queue unchanged as the re-convergence engine.
Residual Splash and Relaxed Scheduling show that bursts of updates confined to a region, and loosely ordered parallel queues, keep convergence while scaling. Their 14x speedup on a $1000\times1000$ Ising grid makes it plausible that region-local re-convergence is cheap. Focused BP computes how strongly one message influences distant beliefs. We borrow that sensitivity score to limit how far a move's re-convergence is allowed to travel.
Two papers motivate the work and also constrain it. Heskes proves that stable BP fixed points are local minima of the Bethe free energy, but some minima repel BP and cause endless oscillation that damping cannot cure. A move can therefore land a region in such an oscillation. In that case we fall back to a double-loop solve restricted to the small region, with boundary messages frozen. This keeps the slowness Heskes notes off the global problem. Knoll and Pernkopf supply the target regime but use plain message passing.
Dynamic Tree Block Coordinate Ascent is the closest scheduling-for-objective work. It ranks updates by local primal-dual gaps, but only for maximum-probability (MAP) inference on a convex dual. There is no basin selection, because a convex dual has only one basin. Our setting is non-convex sum-product inference, where choosing among basins is the whole problem.
Research Program
The algorithm runs in four stages.
- Initial run. Residual BP runs to tolerance.
- Cluster proposal. From the current beliefs we build candidate clusters by joining neighboring variables whose beliefs lean the same way and whose coupling is strong. This mirrors cluster moves in Swendsen-Wang Monte Carlo, but it operates on pseudomarginals instead of samples. Clusters are sampled in proportion to size times boundary weakness.
- Move and re-convergence. A move reinitializes the messages inside the cluster toward the opposite state. It pushes the boundary edges into the residual queue and runs until residuals fall below tolerance or until a move budget is used up. The budget is set from the sensitivity decay along paths leaving the cluster.
- Acceptance. The move is accepted if $\log Z_{\text{Bethe}}$ increases. Otherwise the stored messages are restored. If the region oscillates, we run a local concave-convex procedure (a double-loop method) with boundary messages fixed and then evaluate the result.
On the analysis side, we will characterize when a cluster move's re-convergence stays local. The expected answer is that it does when the cluster boundary is weakly coupled relative to the field, which is the regime with many fixed points. We will also check empirically whether accepted moves correspond to the "biased" fixed points Knoll and Pernkopf identify.
Every cost is reported in message updates and in wall-clock time, including queue overhead.
Baselines
Naive reference. Synchronous BP with damping tuned per model family on held-out instances. This is what most practitioners run, and it shows the cost of ignoring both scheduling and fixed-point choice.
Single residual BP. Residual BP run once from uniform messages, as in McGraw et al. Matching it shows the search adds nothing. Beating it shows the search finds better basins than the default schedule.
Best-of-$K$ restarts. Residual BP from $K$ random initializations, keeping the run with the largest $Z_{\text{Bethe}}$. $K$ is chosen so that total message updates equal those our method spends on the same instance. This is the strongest competitor for the specific question of which fixed point to report, because it uses the same selection rule and differs only in how candidates are generated. Beating it requires a lower median $|\log Z - \log Z_{\text{Bethe}}|$ at equal budget on Region-II instances, with the gap growing with patch count.
Convex and tree-based estimators. The convexified Bethe variant convexBethe-u of Meshi et al. and tree-reweighted BP. Meshi et al. report that convexBethe-u beats standard BP in strong-coupling, weak-field regimes, which is exactly our target. No scalar log-$Z$ error for it was found on Lacuna, so we will rerun it on our instances under the same time limit.
Real-benchmark references. On the 672-instance suite of Agrawal et al., the exact counter Ace is the strongest single solver. It solves 611 of 672 problems within a factor-32 error with a Time Accuracy Penalty (TAP, a score that combines runtime and error) of 2,100, and the virtual best solver reaches 320. On the UAI and probabilistic-inference-challenge instances, IBIA reports solving 1705 of 1717 within 8GB and beating loopy and generalized BP. We do not expect to beat Ace overall. The realistic bar is to improve on loopy BP's per-class accuracy and to lower the virtual best solver's TAP when our method is added to the portfolio.
Ablations. Three ablations isolate the ingredients. The first replaces Bethe-based acceptance with random acceptance. The second replaces confined re-convergence with full-graph re-convergence after each move. The third replaces belief-derived clusters with random connected regions of matched size.
Why not just…?
Why not just damp synchronous BP? Heskes shows that damping fixes oscillations caused by overly large steps but cannot stabilize fixed points that repel BP. More importantly, damping has no mechanism for choosing between several stable fixed points. It is included as the naive baseline, and we expect it to land on whichever basin initialization favors.
Why not just run random restarts and keep the best $Z_{\text{Bethe}}$? This is the real threat, because it shares our acceptance rule. Our argument is combinatorial. If each of $P$ regions must independently fall into the right state, a random restart succeeds with probability that shrinks exponentially in $P$, whereas local moves fix one region at a time. That argument may fail if basins of attraction are lopsided enough that uniform initialization already lands on the good point. The matched-budget comparison, swept over patch count, settles this. If restarts match us, the proposal reduces to "select by $Z_{\text{Bethe}}$," and we will report that result.
Why not just use a convexified Bethe energy or tree-reweighted BP, which have a single answer? A unique minimum removes the selection problem but changes the objective. Meshi et al. find convexBethe-u competitive exactly in hard regimes, so on some families it may win. Density Propagation reports that tree-reweighted upper bounds loosen as coupling grows. Our experiments compare log-$Z$ error at equal time across coupling strengths, and we expect a crossover. Locating that crossover is itself useful.
Proposed Experiments
Controlled study. The first experiment uses patch-potential Ising grids following Knoll and Pernkopf. Grids are small enough for exact $Z$ by variable elimination, about up to $20\times20$, and patch count is varied from 2 to 16. $(J,\theta)$ is swept across Regions I, II and III. Metrics are log-$Z$ error, marginal error, the fraction of instances reaching the best fixed point found by exhaustive enumeration of patch states, and error versus message updates.
First decisive check. In Region II, the fixed point with the largest $Z_{\text{Bethe}}$ must coincide with the most accurate $Z$. If it does not, the selection rule is wrong and the method must change.
Second decisive check. Our advantage over matched-budget restarts must grow with patch count.
Frustrated models. Mixed-sign grids and complete graphs as in Meshi et al. test whether the Bethe acceptance rule still helps when no attractive-model reasoning applies.
Real instances. We then run on the Agrawal 672-instance suite with TAP scoring and on the UAI and challenge instances, reporting per-class accuracy against loopy BP and IBIA and the change in virtual-best-solver TAP.
Escalation rate. Throughout, we log how often moves trigger the local double-loop fallback. This directly measures how often Heskes's repelling minima arise in practice.
References
- Belief Propagation: Accurate Marginals or Accurate Partition Function - Where is the Difference?
- Residual Belief Propagation: Informed Scheduling for Asynchronous Message Passing
- Residual Splash for Optimally Parallelizing Belief Propagation
- Scalable Belief Propagation via Relaxed Scheduling
- Focused Belief Propagation for Query-Specific Inference
- Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy
- Dynamic Tree Block Coordinate Ascent
- Convexifying the Bethe Free Energy
- Partition Function Estimation: A Quantitative Study
- IBIA: An Incremental Build-Infer-Approximate Framework for Approximate Inference of Partition Function
- Density Propagation and Improved Bounds on the Partition Function