Many problems in statistics and physics need the partition function: the constant that turns an unnormalized score over all joint configurations of many variables into a probability. Computing it exactly is intractable in general. Neural versions of belief propagation, a classical algorithm that estimates it by passing messages between neighbouring variables, are fast and accurate. The best-known one is trained against exact answers, which can only be computed on small graphs. Graph neural networks (GNNs) pass messages in a similar way, and when they run many rounds they suffer from over-smoothing: every node's representation drifts toward the same value. This note argues that the two phenomena are the same event seen from two sides. In attractive models, where neighbouring variables prefer to agree, the belief-propagation solution that best estimates the partition function is often a homogenized, "everyone aligned" state. That is exactly an over-smoothed state, and it is exactly the state that gives poor per-variable probabilities.
The proposal has two parts. First, train a deep neural belief-propagation operator with no ground-truth labels, by maximizing an estimate that is provably a lower bound on the log partition function for attractive binary models. Second, predict and measure that this objective drives the belief field toward over-smoothed fixed points. We treat the degree of smoothing as an explicit, measured control that trades partition-function accuracy against marginal accuracy. The measurement borrows the careful split between "aligned" collapse and "shrinking" collapse from the over-smoothing literature. We show it maps onto the two classical failure modes of belief propagation: ferromagnetic alignment and paramagnetic collapse, where every variable's belief goes to 50/50.
Core Claim
In attractive pairwise binary models, a learned message-passing operator trained without labels to maximize the Bethe estimate of $\log Z$ will settle on fixed points whose magnetization field has low Dirichlet energy relative to its norm. The Bethe estimate is belief propagation's free-energy formula for the partition function, and "magnetization" here means each variable's belief rewritten as $m_i = 2b_i - 1$. Low relative Dirichlet energy means the magnetizations are nearly constant across the graph. We predict this effect is regime-dependent in a way theory already describes. In the region of patch-potential Ising models where Belief Propagation: Accurate Marginals or Accurate Partition Function - Where is the Difference? proves that the best-$Z$ fixed point differs from the best-marginal fixed point (they coincide only when $2\sqrt{N}J < N\theta$), label-free training should homogenize the beliefs. There, adding a floor on the belief field's relative Dirichlet energy should trade $\log Z$ tightness for marginal accuracy along a smooth curve. Where the condition holds, the floor should cost nothing. If smoothing does not track this boundary, the claim is wrong.
The claim is useful in two ways. It gives a label-free training signal for deep neural belief propagation, which removes the scaling barrier left open by supervised neural estimators. It also gives a physical meaning to "energy" in deep message passing, a question the dynamical-GNN literature explicitly leaves open.
Relation to Prior Work
Two neural belief-propagation systems supply the architecture and motivate the gap. Belief Propagation Neural Networks replaces belief propagation's damping with a learned operator $H$ satisfying $H(0)=0$. This preserves tree fixed points and lower-bound guarantees, converges 1.7x faster than standard belief propagation on Ising grids, and sometimes finds bounds tighter by factors of $e^{22}$. However, both its iterative and Bethe-regression variants are trained against exact $Z$. Neural Enhanced Belief Propagation on Factor Graphs corrects belief-propagation messages with a factor-graph GNN, but it is supervised on marginals and does not address $Z$. We reuse the constrained operator from the first paper. We replace supervision with a bound-maximization objective, and neither paper analyses how the belief field collapses over many iterations.
Two classical-inference papers constrain the design. The patch-potential result above tells us that one objective cannot be optimal for both $Z$ and marginals. Fixing the Bethe approximation shows that pruning weak edges restores convergence and improves marginals on a 10-node complete attractive graph, where dense belief propagation has marginal error near 0.8, but provably degrades $Z$. Our energy floor is a continuous, learned counterpart to that hard pruning step, and it should display the same tension.
The over-smoothing literature supplies the measurement and the control. Dirichlet Energy Constrained Learning for Deep Graph Neural Networks keeps feature Dirichlet energy above a floor to train 64-layer GNNs. We reuse the lower-bound idea, but apply it to beliefs rather than hidden features. Analysis of Dirichlet Energies as Over-smoothing Measures shows two things: an energy must match the operator whose kernel is the collapse target, and alignment must be separated from magnitude shrinkage. For magnetizations the collapse target is the constant field, the kernel of the unnormalized interaction Laplacian. Shrinkage toward $m=0$ is paramagnetic collapse, a separate failure. Graph Neural Dynamics via Learned Energy and Tangential Flows and Implicit Graph Neural Diffusion learn energies that stabilize deep propagation, and the former states that what these energies mean is open. Here the governing energy is the Bethe free energy of a real distribution, which is a concrete answer for this model class.
Other routes to label-free training exist. The $\chi^2$ upper bound of Neural Variational Inference and Learning in Undirected Graphical Models trains a sampler without labels but has high gradient variance. Delta-AI trains with local objectives over neighbourhoods on 1024-variable Ising models. Neither uses deep iterative message passing, and neither studies how the representations collapse. We use the $\chi^2$ bound only as a companion upper bound for sandwiching.
Research Program
The model is a belief-propagation-style operator in which learned residual updates, constrained by $H(0)=0$, act on the messages of a pairwise binary factor graph. It is unrolled for $T$ iterations, with $T$ up to 200. At the final beliefs $b_\phi(G)$ for graph $G$ we compute the Bethe estimate $\log Z_{\text{B}}$, and we train the parameters $\phi$ across a distribution of attractive instances by
$$\max_\phi \; \mathbb{E}_G\big[\log Z_{\text{B}}(b_\phi(G))\big] - \lambda\, \mathbb{E}_G\big[\max(0,\ \tau - D(m_\phi(G)))\big], \qquad D(m) = \frac{m^\top L\, m}{m^\top m}.$$
Here $m_\phi$ is the magnetization field implied by the beliefs, $L$ is the coupling-weighted unnormalized Laplacian of the interaction graph, $\tau$ is the energy floor, and $\lambda$ is a penalty weight. Because the Bethe estimate lower-bounds $\log Z$ for attractive models, a larger first term always means a tighter valid bound. The objective therefore needs no labels. We track $\|m\|$ alongside $D$ so that alignment collapse and paramagnetic shrinkage are reported separately, following the metric split in the Dirichlet-energy analysis paper.
The study has three stages. The first establishes the phenomenon. With $\tau=0$, we measure $D$ and $\|m\|$ at the fixed points reached by label-free training, supervised training, and classical belief propagation across the patch-potential phase diagram. The second sweeps $\tau$ to trace the curve of $\log Z$ bound against marginal error. The third tests whether a model trained on small graphs keeps its bound tightness on graphs too large for exact solvers. On those graphs we compare only bound values, since every method's estimate is a valid lower bound. For non-attractive models the Bethe estimate is no longer a bound. There we report the method only in combination with a $\chi^2$ upper-bound sampler, and we claim no guarantee.
Baselines
The naive reference point is classical loopy belief propagation with scalar damping, run from uniform initial messages and reporting the Bethe estimate at convergence. It needs no training, and Partition Function Estimation: A Quantitative Study found it consistently robust across problem classes. Beating it means a strictly higher (tighter) lower bound on at least 80% of instances at equal or lower per-instance inference time.
The strongest simple competitor is multi-restart belief propagation. It runs damped belief propagation from many random and fully magnetized initializations and keeps the largest Bethe estimate. Maximizing a lower bound is exactly what restarts do, so this is the most dangerous baseline for the label-free objective. It gets the same per-instance wall-clock budget as our inference pass, and we separately report how many instances are needed to recover our training cost.
The strongest existing learned method is the supervised iterative network from Belief Propagation Neural Networks. It is retrained on our instance distribution with the same architecture, iteration count, and tuning budget, and trained against exact $Z$ from the counter Ace on graphs where Ace terminates. That paper reports 1.7x faster convergence than belief propagation and bounds tighter by up to $e^{22}$ on 10x10 and 14x14 Ising grids. No reported RMSE value for it was found on Lacuna. Beating it means matching its $\log Z$ error on small graphs without labels, and exceeding its bound on graphs larger than its training range.
For the full benchmark, the reference is Ace, which solves 611 of 672 instances within a 32-factor accuracy, with an overall TAP score of 2,100 against a virtual-best-solver TAP of 320 (Partition Function Estimation: A Quantitative Study). We do not expect to beat Ace where it terminates. We report TAP on the attractive subset to show where the amortized method adds coverage.
Two ablations isolate the key ingredient. Setting the floor $\tau=0$ removes the smoothing control. Replacing $D$ with a normalized-Laplacian energy tests the metric-matching claim, and we predict it will mis-rank collapse on non-regular interaction graphs.
Why not just…?
Why not just run belief propagation from many restarts and keep the best bound? This is a real threat. On a single instance with ample time, restarts may match us. The proposal's value then rests on two things: amortization, meaning fewer iterations per instance on new graphs, and the diagnostic finding that the winning restarts are the homogenized ones. The equal-budget comparison above settles the first. Measuring $D$ at the winning restart settles the second, and if restarts win outright we will report that.
Why not just keep the supervised network and train on small graphs? Supervision caps training at sizes where exact solvers finish, and the file offers no evidence that a regressor or operator trained there transfers to larger or higher-treewidth graphs. Our large-graph experiment compares bound values directly and shows whether supervised transfer degrades while the label-free version keeps improving its bound.
Why not just use two separate models, one for $Z$ and one for marginals, instead of a smoothing knob? If two independently trained models reproduce the whole curve, the knob adds little as a method. Even so, the claim that the $Z$-optimal model is over-smoothed, and that this switches on only across the $2\sqrt{N}J < N\theta$ boundary, is the scientific result, and the two-model control tests it directly. We will train both and compare them against the $\tau$ sweep.
Why not just use a shallow network or edge dropout? Shallow unrolls cannot carry correlations across a 14x14 or 32x32 lattice. Edge removal is the hard version of our floor and provably degrades $Z$ (Fixing the Bethe approximation). We include a random edge-dropout variant at matched sparsity to test whether a learned, continuous floor does better.
Proposed Experiments
Data comes from five sources. We use patch-potential Ising models on a grid of $(J,\theta)$ that straddles the alignment boundary, the 10x10 and 14x14 attractive grids used for the supervised network, the 10-node complete attractive model from the edge-pruning study, and the attractive pairwise subset of the 672-instance benchmark. For scale, we add 1024-variable and 32x32 attractive grids, where only bound comparisons are made. Ground truth where feasible comes from Ace or junction-tree inference.
We report five metrics: $\log Z$ absolute error, bound value, mean absolute marginal error, the relative energy $D$ and norm $\|m\|$ at the fixed point, and per-instance time.
The decisive check runs on the patch-potential grid with $\tau=0$. The label-free model's fixed-point $D$ should drop sharply as $(J,\theta)$ crosses into the divergence region, marginal error should rise at the same point, and raising $\tau$ should recover marginals at a measurable cost in bound tightness only in that region. If $D$ is unrelated to the boundary, or if the floor costs nothing on either side, the central claim is refuted. A second check is transfer: a model trained on 10x10 grids should produce tighter bounds on 32x32 grids than the supervised network trained on the same sizes, at equal inference budget.
References
- Belief Propagation: Accurate Marginals or Accurate Partition Function - Where is the Difference?
- Belief Propagation Neural Networks
- Neural Enhanced Belief Propagation on Factor Graphs
- Fixing the Bethe approximation: How structural modifications in a graph improve belief propagation
- Dirichlet Energy Constrained Learning for Deep Graph Neural Networks
- Analysis of Dirichlet Energies as Over-smoothing Measures
- Graph Neural Dynamics via Learned Energy and Tangential Flows
- Implicit Graph Neural Diffusion Based on Constrained Dirichlet Energy Minimization
- Neural Variational Inference and Learning in Undirected Graphical Models
- Delta-AI: Local objectives for amortized inference in sparse graphical models
- Partition Function Estimation: A Quantitative Study