Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Belief Propagation for Weighted Matching and Independent Set

Sujay R. Sanghavi

The analysis of loopy BP, especially for arbitrary graphs with small cycles, lags far behind its empirical success. In this talk we investigate the performance of Max-product - a variant of loopy BP - in solving two canonical combinatorial problems: weighted matching and independent set. The special structure of these problems allows an exact and detailed characterization of when the BP estimates are accurate.

Both problems can be naturally formulated as integer programs (IP). We show that the success of loopy BP is closely related to the LP relaxation of these IPs. For weighted matching, and related problems, loopy BP turns out to be EXACTLY as powerful as LP relaxation (ie works/fails on the same problem instances) while for independent set it turns out to be STRICTLY inferior. We then devise a simple "two-sided" modification of max-product, which we show to be exactly as powerful as LP relaxation.

We note that our results pertain to classical BP, and not to the more recent "tree-reparametrized" or "convexified" algorithms.

(Work is joint with Dmitry Malioutov, Devavrat Shah and Alan Willsky)

Problems with this site should be emailed to