On MAP Inference by MWSS on Perfect Graphs

Adrian Weller, Tony Jebara
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:242-251, 2013.

Abstract

Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a max- imum weight stable set (MWSS) on a de- rived weighted graph, which if perfect, al- lows inference in polynomial time. We de- rive new results for this approach, including a general decomposition theorem for MRFs of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and an exact characterization of which bi- nary pairwise MRFs can be efficiently solved with this method. This defines the power of the approach on this class of models, im- proves our toolbox and expands the range of tractable models.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-weller13a, title = {On {MAP} Inference by {MWSS} on Perfect Graphs}, author = {Weller, Adrian and Jebara, Tony}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {242--251}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/weller13a/weller13a.pdf}, url = {https://proceedings.mlr.press/r11/weller13a.html}, abstract = {Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a max- imum weight stable set (MWSS) on a de- rived weighted graph, which if perfect, al- lows inference in polynomial time. We de- rive new results for this approach, including a general decomposition theorem for MRFs of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and an exact characterization of which bi- nary pairwise MRFs can be efficiently solved with this method. This defines the power of the approach on this class of models, im- proves our toolbox and expands the range of tractable models.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T On MAP Inference by MWSS on Perfect Graphs %A Adrian Weller %A Tony Jebara %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-weller13a %I PMLR %P 242--251 %U https://proceedings.mlr.press/r11/weller13a.html %V R11 %X Finding the most likely (MAP) configuration of a Markov random field (MRF) is NP-hard in general. A promising, recent technique is to reduce the problem to finding a max- imum weight stable set (MWSS) on a de- rived weighted graph, which if perfect, al- lows inference in polynomial time. We de- rive new results for this approach, including a general decomposition theorem for MRFs of any order and number of labels, extensions of results for binary pairwise models with submodular cost functions to higher order, and an exact characterization of which bi- nary pairwise MRFs can be efficiently solved with this method. This defines the power of the approach on this class of models, im- proves our toolbox and expands the range of tractable models. %Z Reissued by PMLR on 04 October 2026.
APA
Weller, A. & Jebara, T.. (2013). On MAP Inference by MWSS on Perfect Graphs. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:242-251 Available from https://proceedings.mlr.press/r11/weller13a.html. Reissued by PMLR on 04 October 2026.

Related Material