Probability distributions defined by graphs arise in a variety of fields, including statistical signal and image processing, statistical physics, machine learning, and communication theory. Graphical models provide a principled framework in which to combine local constraints so as to construct a global model. Important practical problems in applications of graphical models include computing marginal distributions or modes, and the log partition function. Although these problems can be solved efficiently in tree-structured models, these same tasks are intractable for general large-scale graphs with cycles.

In recent years, local message-passing algorithms (i.e., belief propagation, max-product) have been widely used to compute approximate solutions in graphs with cycles. We describe a class of reweighted message-passing algorithms, and illustrate how they can be understood as methods for solving graph-structured optimization problems. These modified algorithms have advantages over standard methods, including unique fixed points and guaranteed upper bounds (reweighted belief propagation), and performance guarantees (reweighted max-product). We discuss applications of graphical models and message-passing to statistical image processing and error-control coding.