Message Passing and Combinatorial Optimization
Summary of Message Passing and Combinatorial Optimization
Graphical Models use the intuitive and well-studied methods of graph theory to implicitly represent dependencies between variables in large systems. They can model the global behaviour of a complex system by specifying only local factors. This thesis studies inference in such models from a broad algebraic view and the ways it can be used to express and approximately solve NP-hard combinatorial problems.
The first part of this thesis categorizes these inference problems under a “hierarchy” with increasing levels of complexity. A subset of the problems can be approximately solved using a well-known message passing procedure called Belief Propagation (BP). In this procedure, messages are exchanged between the nodes in the graphical model until reaching convergence. The message update can be seen as a fixed point iteration that finds exact solutions for trees and approximations for graphical models with loops. We study several novel approaches to further improve the approximation obtained by BP in loopy graphs and propose variations on a generalization of BP, called survey propagation.
The second part reviews the existing message passing solutions and provides novel graphical model formulation and inference techniques for more than twenty important combinatorial optimization problems. These are studied under three broad classes: (I) “constraint satisfaction problems” such as satisfiability, coloring, packing; (II) “clustering problems” such as hierarchical clustering, K-median, K-clustering, K-center problem; and (III) “problems over permutations” including assignment problem, graph alignment, isomorphism, graph alignment, finding symmetries and traveling salesman problem. In many cases we show that our message passing procedures are able to find solutions that compare favourably to today’s state-of-the-art approaches, and are often near optimal.
