Belief Propagation and LP Relaxation for Weighted Matching in General Graphs
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 analyze the performance of the max-product form of belief propagation for the weighted matching problem on general graphs. We sho...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/80772 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1811090733516455936 |
|---|---|
| author | Sanghavi, S. Malioutov, Dmitry M. Willsky, Alan S. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Sanghavi, S. Malioutov, Dmitry M. Willsky, Alan S. |
| author_sort | Sanghavi, S. |
| collection | MIT |
| description | 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 analyze the performance of the max-product form of belief propagation for the weighted matching problem on general graphs. We show that the performance of max-product is exactly characterized by the natural linear programming (LP) relaxation of the problem. In particular, we first show that if the LP relaxation has no fractional optima then max-product always converges to the correct answer. This establishes the extension of the recent result by Bayati, Shah and Sharma, which considered bipartite graphs, to general graphs. Perhaps more interestingly, we also establish a tight converse, namely that the presence of any fractional LP optimum implies that max-product will fail to yield useful estimates on some of the edges. We extend our results to the weighted b-matching and r -edge-cover problems. We also demonstrate how to simplify the max-product message-update equations for weighted matching, making it easily deployable in distributed settings like wireless or sensor networks. |
| first_indexed | 2024-09-23T14:51:06Z |
| format | Article |
| id | mit-1721.1/80772 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:51:06Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/807722022-09-29T10:56:49Z Belief Propagation and LP Relaxation for Weighted Matching in General Graphs Sanghavi, S. Malioutov, Dmitry M. Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Willsky, Alan S. 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 analyze the performance of the max-product form of belief propagation for the weighted matching problem on general graphs. We show that the performance of max-product is exactly characterized by the natural linear programming (LP) relaxation of the problem. In particular, we first show that if the LP relaxation has no fractional optima then max-product always converges to the correct answer. This establishes the extension of the recent result by Bayati, Shah and Sharma, which considered bipartite graphs, to general graphs. Perhaps more interestingly, we also establish a tight converse, namely that the presence of any fractional LP optimum implies that max-product will fail to yield useful estimates on some of the edges. We extend our results to the weighted b-matching and r -edge-cover problems. We also demonstrate how to simplify the max-product message-update equations for weighted matching, making it easily deployable in distributed settings like wireless or sensor networks. National Science Foundation (U.S.) (Grant CAREER 0954059) National Science Foundation (U.S.) (Grant 0964391) 2013-09-17T15:09:00Z 2013-09-17T15:09:00Z 2011-04 2010-09 Article http://purl.org/eprint/type/JournalArticle 0018-9448 1557-9654 http://hdl.handle.net/1721.1/80772 Sanghavi, S, D Malioutov, and A Willsky. Belief Propagation and LP Relaxation for Weighted Matching in General Graphs. IEEE Transactions on Information Theory 57, no. 4 (April 2011): 2203-2212. https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/TIT.2011.2110170 IEEE Transactions on Information Theory Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Willsky via Amy Stout |
| spellingShingle | Sanghavi, S. Malioutov, Dmitry M. Willsky, Alan S. Belief Propagation and LP Relaxation for Weighted Matching in General Graphs |
| title | Belief Propagation and LP Relaxation for Weighted Matching in General Graphs |
| title_full | Belief Propagation and LP Relaxation for Weighted Matching in General Graphs |
| title_fullStr | Belief Propagation and LP Relaxation for Weighted Matching in General Graphs |
| title_full_unstemmed | Belief Propagation and LP Relaxation for Weighted Matching in General Graphs |
| title_short | Belief Propagation and LP Relaxation for Weighted Matching in General Graphs |
| title_sort | belief propagation and lp relaxation for weighted matching in general graphs |
| url | http://hdl.handle.net/1721.1/80772 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT sanghavis beliefpropagationandlprelaxationforweightedmatchingingeneralgraphs AT malioutovdmitrym beliefpropagationandlprelaxationforweightedmatchingingeneralgraphs AT willskyalans beliefpropagationandlprelaxationforweightedmatchingingeneralgraphs |