Inference and mutual information on random factor graphs

Matija Pasch

Random factor graphs provide a powerful framework for the study of inference problems such
as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is
the mutual information between the observed factor graph and the underlying ground truth around which
the factor graph was created; in the stochastic block model, this would be the planted partition. The mutual
information gauges whether and how well the ground truth can be inferred from the observable data. For
a very general model of random factor graphs we verify a formula for the mutual information predicted by
physics techniques. As an application we prove a conjecture about low-density generator matrix codes from
[Montanari: IEEE Transactions on Information Theory 2005]. Further applications include phase transitions
of the stochastic block model and the mixed k-spin model from physics.