Revisiting the Limits of MAP Inference by MWSS on Perfect Graphs

A recent, promising approach to identifying a configuration of a discrete graphical model with highest probability (termed MAP inference) is to reduce the problem to finding a maximum weight stable set (MWSS) in a derived weighted graph, which, if perfect, allows a solution to be found in polynomial time. Weller and Jebara (2013) investigated the class of binary pairwise mod-els where this method may be applied. How-ever, their analysis made a seemingly innocuous assumption which simplifies analysis but led to only a subset of possible reparameterizations be-ing considered. Here we introduce novel tech-niques and consider all cases, demonstrating that this greatly expands the set of tractable models. We provide a simple, exact characterization of the new, enlarged set and show how such mod-els may be efficiently identified, thus settling the power of the approach on this class.