Bounding the Partition Function of Graphical Models

35 concepts16 papers1 proposal

In probabilistic graphical models, calculating the partition function—the normalization constant that scales a set of unnormalized potentials into a valid probability distribution—is a central but computationally intractable challenge. Because exact computation is often impossible in cyclic or densely connected graphs, researchers rely on variational approximations like Mean Field (MF) theory, Tree-Reweighted (TRW) belief propagation, and the Bethe approximation (the mathematical foundation of Loopy Belief Propagation).

Historically, these methods were treated as heuristics. However, a robust body of research has established conditions under which these variational approximations provide mathematically guaranteed upper or lower bounds on the true partition function, transforming heuristics into reliable tools for statistical inference.

The Bethe Approximation as a Guaranteed Lower Bound

A primary focus in this domain is identifying when the Bethe partition function acts as a rigorous lower bound. This guarantee is deeply tied to the concept of log-supermodularity, which mathematically defines "attractive" graphical models where neighboring variables tend to favor similar states (i.e., the product of values at the join and meet of two points is at least the product of the values at the points themselves).

In The Bethe Partition Function of Log-supermodular Graphical Models, Nicholas Ruozzi proved that for any binary graphical model with higher-order log-supermodular potentials, the Bethe partition function consistently provides a lower bound on the true partition function. To preserve these inequalities when summing functions across graph covers, the author utilized a generalized version of the four functions theorem alongside weak majorization.

This lower-bound guarantee is not restricted to discrete systems. In A Lower Bound on the Partition Function of Attractive Graphical Models in the Continuous Case, Nicholas Ruozzi extended this framework to continuous graphical models. By employing a continuous version of log-supermodular correlation inequalities, the author ensured that the model's attractiveness is preserved across graph covers, providing a theoretical safety net that prevents belief propagation from overestimating the normalization constant.

Other foundational work supports this lower-bound behavior from different structural perspectives:

  • Local Dependencies: Erik B. Sudderth et al. demonstrated in Loop Series and Bethe Variational Bounds in Attractive Graphical Models that the Bethe free energy serves as a rigorous lower bound for attractive binary graphical models. By accounting for local dependencies within the graph's cyclic structure, it yields a significantly tighter and more stable approximation than standard mean-field methods as node dependencies increase.
  • Closed-Form Solutions: For associative networks, Soumen Chakrabarti et al. leveraged the properties of loopy belief propagation in attractive models to derive closed-form lower bounds, offering a computationally efficient alternative to iterative approximations in dense graphs.

Extending Bounds Beyond Binary Log-Supermodularity

To broaden the utility of these guarantees, researchers have looked for ways to map non-attractive or non-binary systems into log-supermodular frameworks, or find alternative mathematical properties that yield similar bounds.

Graph Cover Transformations

In Beyond Log-Supermodularity: Lower Bounds and the Bethe Partition Function, Nicholas Ruozzi showed that certain non-log-supermodular models can be transformed into equivalent log-supermodular formulations. By analyzing averages and individual bounds over the graph covers of these transformed models, the author proved that the Bethe partition function serves as a lower bound for widely studied non-binary classes, including the ferromagnetic Potts model and weighted graph homomorphism problems.

Real Stable Polynomials

Taking an algebraic approach, Damian Straszak et al. explored bipartite factor graphs where local interactions are characterized by real stable polynomials in Belief Propagation, Bethe Approximation and Polynomials. They proved that the "Iterated Positive Correlation" property naturally satisfied by these polynomials ensures the Bethe partition function acts as a guaranteed lower bound. This provides a theoretical justification for message-passing heuristics in systems with negative dependence or repulsive interactions, while establishing a worst-case performance guarantee where the approximation error is bounded within a factor of $2^{\#\text{edges}}$.

Tightening Bounds via Clamping and Higher-Order Expansions

Once a baseline lower or upper bound is established, a key practical question is how to systematically tighten it. Two primary mechanisms have emerged: variable clamping and higher-order polynomial expansions.

The Mechanism of Clamping

Clamping involves selecting a variable, fixing it to each of its possible states, running the approximate inference algorithm on each resulting sub-problem, and summing the sub-partition functions.

       [Original Graph] 
        /      |       \
   (Clamp X=0) |   (Clamp X=1)
      /        |        \
[Sub-Approx]   |   [Sub-Approx]
      \        |        /
       [Sum Sub-Approximations] ---> Tighter Bound

In Clamping Variables and Approximate Inference, Adrian Weller et al. demonstrated that in attractive binary pairwise models, the relationship between the Bethe free energy and variable states is characterized by convexity. Because of this convexity, clamping and summing sub-approximations is guaranteed to never decrease the Bethe partition function estimate, systematically driving the lower bound closer to the true partition function.

The authors extended the utility of clamping to other variational methods in Clamping Improves TRW and Mean Field Approximations. They provided a general proof that across any pairwise model, clamping consistently tightens partition function bounds: it monotonically decreases the upper bounds produced by tree-reweighted methods and monotonically increases the lower bounds produced by mean field methods.

Higher-Order Expansions

Rather than using standard first-order mean field approximations, Martijn A. R. Leisink et al. introduced a third-order polynomial bound in A Tighter Bound for Graphical Models. This mathematical framework significantly reduces approximation error—sometimes by factors of up to ten—while maintaining the theoretical safety of a lower bound. The authors generalized this approach in General Lower Bounds based on Computer Generated Higher Order Expansions, presenting an algorithm to generate arbitrary-order lower bounds for Boltzmann machines that remain accurate even outside typical mean-field convergence radii.

Semidefinite Relaxations and Upper Bounds

While much focus centers on lower bounds, obtaining rigorous upper bounds or worst-case guarantees for arbitrary graph topologies requires alternative optimization strategies, such as semidefinite programming (SDP) relaxations.

In Semidefinite Relaxations for Approximate Inference on Graphs with Cycles, Martin J. Wainwright et al. combined Gaussian entropy bounds with semidefinite constraints. This formulation yields a strictly convex optimization problem that provides a guaranteed upper bound on the log partition function, ensuring stability even in regimes where traditional message-passing algorithms fail to converge.

Similarly, Andrej Risteski et al. leveraged SDP relaxations via the Goemans-Williamson rounding technique in Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods. By applying these relaxations to the variational characterization of the log-partition function, the authors achieved the first worst-case approximation guarantees for Ising models regardless of graph structure: a constant-factor approximation for ferromagnetic models and an $O(\log n)$ approximation for models with arbitrary potentials.

Other methods for obtaining upper bounds include:

Key Foundational Work

A New Class of Upper Bounds on the Log Partition Function (2002) — contributed 1 concept elements to this direction.
A Tighter Bound for Graphical Models (2000) — contributed 1 concept elements to this direction.
General Lower Bounds based on Computer Generated Higher Order Expansions (2002) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_generalized_correlation_inequalities_c1c2a943,
  title = {generalized correlation inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-correlation-inequalities/rdr_c1c2a9437c18436dbc98e994b81b8f5d},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_generalized_correlation_inequalities_c1c2a943_v1,
  title = {generalized correlation inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/generalized-correlation-inequalities/rdr_c1c2a9437c18436dbc98e994b81b8f5d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake