Abstract-Vi undersöker användningen av message-passing algoritmer för problemet med att hitta maximal vikt oberoende uppsättning (MWIS) i en graf. Först studerar vi prestandan av den klassiska loopy max-produkt tro förökning. Vi visar att varje fast punkt uppskattning av max-produkt kan kartläggas på ett naturligt sätt till en extrem punkt av LP polytope i samband med MWIS-problemet. Men denna extrema punkt kanske inte är den som maximerar värdet av nodvikter; den särskilda extrema punkten vid slutlig konvergens beror på initiering av max-produkt. Vi visar sedan att om max-produkt startas från den naturliga initiering av oinformativa meddelanden, det alltid löser rätt LP - om det konvergerar. Detta resultat erhålls genom en direkt analys av den iterativa algoritmen, och kan inte erhållas genom att endast titta på fasta punkter. Tätheten i LP-avslappningen är därför nödvändig för maximal produkt optimalitet, men det är inte tillräckligt. Motiverade av denna observation, visar vi att en enkel ändring av max-produkt blir lutning nedstigning på (en konvex version av) den dubbla av LP, och konvergerar till den dubbla optimal. Vi utvecklar också en meddelande-passing algoritm som återvinner den primära MWIS-lösningen från utgången av nedstigning algoritmen. Vi visar att MWIS uppskattning som erhållits med hjälp av dessa två algoritmer tillsammans är korrekt när grafen är bipartite och MWIS är unik. Slutligen visar vi att alla problem med MAP-uppskattning för sannolikhetsfördelning över ändliga domäner kan reduceras till ett MWIS-problem. Vi tror att denna minskning kommer att ge nya insikter och algoritmer för MAP uppskattning.
Parallellt arbete REF fastställer denna omgång för det mer allmänna problemet med att hitta den maximala vikten oberoende uppsättningen.
Message-passing for Maximum Weight Independent Set
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}