|Stochastic Systems Group|
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 firstname.lastname@example.org