Conditions beyond treewidth for tightness of higher-order LP relaxations

Mark Rowland, Aldo Pacchiano, Adrian WellerAISTATS 2017 · OpenReview

Abstract: Linear programming (LP) relaxations are a popular method for finding the most likely configuration of a discrete graphical model. While the "tightness" of these relaxations has long been linked to a graph's treewidth, this research demonstrates that for higher-order relaxations, this link breaks down. We explore a new geometric framework that identifies structural conditions beyond treewidth, specifically identifying the "odd-$K_5$" as a unique non-tight structure for fourth-order relaxations.

Introduction

In machine learning, Maximum A Posteriori (MAP) inference is used to find the most likely state of a system, such as identifying objects in an image. For binary pairwise models like Ising models, this task is generally NP-hard. To make it tractable, researchers employ Linear Programming (LP) relaxations. A relaxation is "tight" if its solution is an integer, meaning it has successfully found the exact global optimum of the original problem.

Traditionally, the tightness of these relaxations has been tied to treewidth—a measure of how "tree-like" a graph is. If a graph has low treewidth, a corresponding level of the Sherali-Adams LP hierarchy ($L_r$) is guaranteed to be tight. This paper investigates whether treewidth is the only or even the correct way to characterize when these higher-order relaxations work.

Breaking the Treewidth Paradigm

The most striking insight of this work is that for the 4th order relaxation ($L_4$), treewidth is no longer the definitive metric. The authors show that the set of graphs where $L_4$ is tight is not the same as the set of graphs with treewidth $\le 3$.

To prove this, they utilize Graph Minor Theory, which characterizes graph properties by "forbidden" sub-structures. For treewidth $\le 3$, there are four minimal forbidden minors: $K_5$, the Wagner graph, the octahedron, and the pentagonal prism.

The $K_5$ complete graph is one of the minimal forbidden minors for treewidth $\le 3$. The authors discovered that only a specific "odd" signing of this structure causes $L_4$ to be non-tight.

The authors formally identify the odd-$K_5$ as the unique non-tight signing among these minimal forbidden minors. This means that $L_4$ can be tight on graphs that violate the treewidth-3 condition, provided they do not contain this specific "odd" version of $K_5$.

The Wagner graph, another minimal forbidden minor for treewidth $\le 3$. The paper demonstrates that the clean relationship between treewidth and tightness found in lower-order relaxations vanishes at $L_4$.

Geometric Framework and Efficient Relaxations

The researchers employ a geometric perspective, representing the set of tight potentials as a union of normal cones. This allows them to use polyhedral combinatorics to analyze relaxation exactness. By using "flipping" and "permutation" symmetries, they reduced the complexity of searching for cases where the LP relaxation fails.

One practical outcome is the introduction of a specialized relaxation called $L_3^s$ for "almost balanced" models. While standard $L_3$ relaxations require $O(V^3)$ constraints, $L_3^s$ only requires $O(V^2)$ constraints while maintaining the same guarantee of tightness. Furthermore, they prove the utility of chordal envelopes, showing that triplet constraints only need to be enforced on triplets appearing in a triangulation of the graph, significantly reducing the computational burden for real-world datasets like image segmentation.

Conclusion

This work shifts the focus from purely combinatorial graph properties like treewidth to a more nuanced structural and geometric understanding of LP relaxations. By identifying that $L_4$ tightness is governed by specific "signed" minors rather than just the presence of a minor itself, the authors open new avenues for designing more efficient and powerful inference algorithms. Future work remains to fully map the forbidden minors for higher-order relaxations and extend these insights to multi-label graphical models.

Summary updated

Abstract

Linear programming (LP) relaxations are a popular method to attempt to find a most likely configuration of a discrete graphical model. If a solution to the relaxed problem is obtained at an integra...
BibTeX
@inproceedings{rowland2017conditions,
  author = {Mark Rowland and Aldo Pacchiano and Adrian Weller},
  title = {{Conditions beyond treewidth for tightness of higher-order LP relaxations}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=taf3IR3wrKQ},
}
Figure