Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs. This general result implies the conjecture on the information-theoretic threshold in the disassortative stochastic block model [: Phys. Rev. E (2011)] and allows us to pinpoint the exact condensation phase transition in random constraint satisfaction problems such as random graph coloring, thereby proving a conjecture from [: PNAS (2007)]. As a further application we establish the formula for the mutual information in Low-Density Generator Matrix codes as conjectured in [Montanari: IEEE Transactions on Information Theory (2005)]. The proofs provide a conceptual underpinning of the replica symmetric variant of the cavity method, and we expect that the approach will find many future applications.
Previously the validity of the physics formulas was known in any generality only under the assumption that the factor graph models satisfies the Gibbs uniqueness condition, a very strong spatial mixing assumption @cite_80 @cite_47 @cite_76 @cite_9 . Gibbs uniqueness typically only holds for very small values of @math . Additionally, under weaker spatial mixing conditions it was known that the free energy in random graph models is given by some Belief Propagation fixed point @cite_73 @cite_9 . However, there may be infinitely many fixed points, and it was not generally known that the correct one is the maximizer of the functional @math . In effect, it was not possible to derive the formula for the free energy or, equivalently, the mutual information, from such results. Specifically, in the case of the teacher-student scheme Montanari @cite_74 proved (under certain assumptions) that the Gibbs marginals of @math correspond to a Belief Propagation fixed point as in , whereas identifies the particular fixed point that maximizes the functional @math as the relevant one.
@cite_73 @cite_9 @cite_74 @cite_80 @cite_47 @cite_76
2018836315 2963553740 2161506909 2013024470
We consider homogeneous factor models on uniformly sparse graph sequences converging locally to a (unimodular) random tree T, and study the existence of the free energy density ϕ, the limit of the log-partition function divided by the number of vertices n as n tends to infinity. We provide a new interpolation scheme and use it to prove existence of, and to explicitly compute, the quantity ϕ subject to uniqueness of a relevant Gibbs measure for the factor model on T. By way of example we compute ϕ for the independent set (or hard-core) model at low fugacity, for the ferromagnetic Ising model at all parameter values, and for the ferromagnetic Potts model with both weak enough and strong enough interactions. Even beyond uniqueness regimes our interpolation provides useful explicit bounds on ϕ. In the regimes in which we establish existence of the limit, we show that it coincides with the Bethe free energy functional evaluated at a suitable fixed point of the belief propagation (Bethe) recursions on T. In the special case that T has a Galton–Watson law, this formula coincides with the nonrigorous “Bethe prediction” obtained by statistical physicists using the “replica” or “cavity” methods. Thus our work is a rigorous generalization of these heuristic calculations to the broader class of sparse graph sequences converging locally to trees. We also provide a variational characterization for the Bethe prediction in this general setting, which is of independent interest. According to physics predictions, the free energy of random factor graph models that satisfy a certain "static replica symmetry" condition can be calculated via the Belief Propagation message passing scheme [ PNAS, 2007]. Here we prove this conjecture for a wide class of random factor graph models. Specifically, we show that the messages constructed just as in the case of acyclic factor graphs asymptotically satisfy the Belief Propagation equations and that the free energy density is given by the Bethe free energy formula. In this article we propose new methods for computing the asymptotic value for the logarithm of the partition function (free energy) for certain statistical physics models on certain type of finite graphs, as the size of the underlying graph goes to infinity. The two models considered are the hard-core (independent set) model when the activity parameter λ is small, and also the Potts (q-coloring) model. We only consider the graphs with large girth. In particular, we prove that asymptotically the logarithm of the number of independent sets of any r-regular graph with large girth when rescaled is approximately constant if r ≤ 5. For example, we show that every 4-regular n-node graph with large girth has approximately (1.494…)n-many independent sets, for large n. Further, we prove that for every r-regular graph with r ≥ 2, with n nodes and large girth, the number of proper q ≥ r + 1 colorings is approximately @math n, for large n. We also show that these results hold for random regular graphs with high probability (w.h.p.) as well. As a byproduct of our method we obtain simple algorithms for the problem of computing approximately the logarithm of the number of independent sets and proper colorings, in low degree graphs with large girth. These algorithms are deterministic and use certain correlation decay properties for the corresponding Gibbs measures, and its implications to uniqueness of the Gibbs measures on the infinite trees, as well as some simple cavity trick which is well known in the physics and the Markov chain sampling literature.© 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 Preliminary version of this paper appeared in Proceedings of the Seventeenth ACM-SIAM Symposium on Discrete Algorithms 2006. ArXive version. Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree-like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b-matching in the Erdős–Renyi random graph with fixed average degree and diverging size, for any . To the best of our knowledge, this is the first time that correlation inequalities and unimodularity are combined together to yield a general proof of uniqueness of Gibbs measures on infinite trees. We believe that a similar argument is applicable to other Gibbs measures than those over spanning subgraphs considered here. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013