Team for Research in
Ubiquitous Secure Technology

Citation
Sujay Sanghavi, Dmitry Malioutov, Alan S. Willsky. "Linear Programming Analysis of Loopy Belief Propagation for Weighted Matching". submitted to NIPS 2007, December, 2007.

Abstract
Loopy belief propagation has been employed in a wide variety of applications with great empirical success, but it comes with few theoretical guarantees. In this paper we investigate the use of the max-product form of belief propagation for weighted matching problems on general graphs. We show that max-product converges to the correct answer if the linear programming (LP) relaxation of the weighted matching problem is tight and does not converge if the LP relaxation is loose. This provides an exact characterization of max-product performance and reveals connections to the widely used optimization technique of LP relaxation. In addition, we demonstrate that max-product is effective in solving practical weighted matching problems in a distributed fashion by applying it to the problem of self-organization in sensor networks.

Electronic downloads

• HTML

  Sujay Sanghavi, Dmitry Malioutov, Alan S. Willsky. <a
  href="http://www.truststc.org/pubs/265.html"
  >Linear Programming Analysis of Loopy Belief Propagation
  for Weighted Matching</a>, submitted to NIPS 2007,
  December, 2007.

• Plain text

  Sujay Sanghavi, Dmitry Malioutov, Alan S. Willsky.
  "Linear Programming Analysis of Loopy Belief
  Propagation for Weighted Matching". submitted to NIPS
  2007, December, 2007.

• BibTeX

  @inproceedings{SanghaviMalioutovWillsky07_LinearProgrammingAnalysisOfLoopyBeliefPropagationFor,
      author = {Sujay Sanghavi and Dmitry Malioutov and Alan S.
                Willsky},
      title = {Linear Programming Analysis of Loopy Belief
                Propagation for Weighted Matching},
      booktitle = {submitted to NIPS 2007},
      month = {December},
      year = {2007},
      abstract = {Loopy belief propagation has been employed in a
                wide variety of applications with great empirical
                success, but it comes with few theoretical
                guarantees. In this paper we investigate the use
                of the max-product form of belief propagation for
                weighted matching problems on general graphs. We
                show that max-product converges to the correct
                answer if the linear programming (LP) relaxation
                of the weighted matching problem is tight and does
                not converge if the LP relaxation is loose. This
                provides an exact characterization of max-product
                performance and reveals connections to the widely
                used optimization technique of LP relaxation. In
                addition, we demonstrate that max-product is
                effective in solving practical weighted matching
                problems in a distributed fashion by applying it
                to the problem of self-organization in sensor
                networks.},
      URL = {http://www.truststc.org/pubs/265.html}
  }
  

Posted by Dmitry Malioutov on 19 Jul 2007.
For additional information, see the Publications FAQ or contact webmaster at www truststc org.