2007/05/05 by Sujay Sanghavi, Sanghavi, Sujay
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Artificial Intelligence (cs.AI) #Caching and Content Delivery #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Networking and Internet Architecture (cs.NI) #cs.AI #cs.IT #cs.LG #cs.NI #math.IT
paper · pdf · doi:10.48550/arxiv.0705.0760
6 pages, 2 figures
arxiv created 2007/05/05 · openalex publication_date 2007/05/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Max-product belief propagation is a local, iterative algorithm to find the mode/MAP estimate of a probability distribution. While it has been successfully employed in a wide variety of applications, there are relatively few theoretical guarantees of convergence and correctness for general loopy graphs that may have many short cycles. Of these, even fewer provide exact ``necessary and sufficient'' characterizations. In this paper we investigate the problem of using max-product to find the maximum weight matching in an arbitrary graph with edge weights. This is done by first constructing a probability distribution whose mode corresponds to the optimal matching, and then running max-product. Weighted matching can also be posed as an integer program, for which there is an LP relaxation. This relaxation is not always tight. In this paper we show that \beginenumerate \item If the LP relaxation is tight, then max-product always converges, and that too to the correct answer. \item If the LP relaxation is loose, then max-product does not converge. \endenumerate This provides an exact, data-dependent characterization of max-product performance, and a precise connection to LP relaxation, which is a well-studied optimization technique. Also, since LP relaxation is known to be tight for bipartite graphs, our results generalize other recent results on using max-product to find weighted matchings in bipartite graphs.