Tighter Linear Program Relaxations for High Order Graphical Models

Elad Mezuman, Daniel Tarlow, Amir Globerson, Yair Weiss

TL;DR

This paper demonstrates that standard methods for handling High Order Potentials (HOPs) in graphical models often rely on a "weak" linear program (LP) relaxation that only enforces consistency between the HOP and individual variables. The authors propose a family of tighter relaxations that enforce consistency between the HOP and pairs of variables (edges), providing efficient message-passing algorithms and a heuristic for selecting which edges to include to maximize accuracy without sacrificing tractability.

What Problem Does This Paper Address?

Graphical models are powerful tools for representing dependencies between variables, but many real-world problems require "High Order Potentials" (HOPs)—functions that depend on a large set of variables simultaneously (e.g., "at least $k$ pixels must be active" or "the average cut of this graph should be minimized").

While researchers have developed many ways to perform inference with HOPs, the authors point out a hidden flaw: almost all existing approaches are mathematically equivalent to a Unary Consistency LP ($LP_\emptyset$). In this relaxation, the high-order term only "talks" to the rest of the model through single variables. This often results in a "loose" relaxation, where the algorithm returns fractional, non-sensical solutions (the "integrality gap") rather than the true optimal assignment.

Methods

The authors introduce Partial Edge Consistency LPs ($LP_S$). Instead of just ensuring the HOP agrees with each variable's marginal distribution, $LP_S$ forces the HOP to agree with the joint distribution of pairs of variables (edges) for a chosen subset of edges $S$.

Key technical contributions include:

  • Proof of Equivalence: They prove that several popular techniques (like using auxiliary variables to simplify HOPs) are actually just $LP_\emptyset$ in disguise and suffer from the same weaknesses.
  • Tractable Message Passing: They identify specific classes of HOPs—specifically cardinality-based potentials and Pattern HOPs—where messages can still be computed efficiently even when the HOP is connected to edges, provided the set of edges $S$ has low tree-width.
  • Weak Cycle Agreement (WCA): Since including all edges is computationally impossible for complex graphs, they propose a heuristic called WCA. This method iteratively adds edges to the consistency set $S$ that are most likely to tighten the LP bound.

Datasets

The paper evaluates the proposed methods on:

  1. Synthetic Tree Models: Used to test "Hamming Ball Exclusion" (finding the M-best assignments).
  2. 4-connected 7x7 Grids: Used to evaluate the edge selection heuristics.
  3. Berkeley Segmentation Dataset (BSDS): 40 images from this standard benchmark were used for an image segmentation task formulated as an "average-cut" problem.

Key Insights and Ideas

  • The "Unary" Bottleneck: The most striking insight is that the "interface" between a high-order potential and the rest of the graph is the primary source of error. Even if the HOP itself is easy to compute, if it only communicates via single variables, the global structure is lost.
  • Tree-width vs. Accuracy: You don't need to enforce consistency on every edge to get a perfect result. For many problems, enforcing consistency on a carefully chosen tree-structured subset of edges (tree-width 1) is enough to make the relaxation provably exact.
  • Reparameterization is Key: The authors leverage the dual form of the LP to show that "tightening" the relaxation is equivalent to finding a better reparameterization of the energy function, where the HOP and the local edges "agree" on the best local assignments.

Key Results

  • Exactness on Hard Problems: In the Hamming Ball Exclusion experiments, the standard $LP_\emptyset$ failed frequently, while the proposed $LP_S$ (using only a tree-width of 1) found the exact solution every time.
  • Image Segmentation: On the Berkeley dataset, the authors attempted to solve the NP-hard "average-cut" problem. Using $LP_S$ with a maximum tree-width of 6, they provably found the global optimum for 34 out of 40 images.
  • Performance Gain: Their method improved upon standard spectral clustering solutions in 38 out of 40 cases, with an average objective function improvement of 70%.

Limitations and Future Work

  • Computational Complexity: Even with efficient routines, message passing with edge consistency is more expensive than unary consistency. Specifically, the message computation can become quadratic in the number of variables for certain HOPs.
  • Scaling to Large Images: While successful on super-pixels (approx. 100 nodes), scaling the method to pixel-level grids (thousands of nodes) remains a challenge. The authors suggest investigating Fast Fourier Transforms (FFTs) to speed up these computations.
  • Multiple HOPs: The current work focuses primarily on models with a single large HOP. The authors note that extending this to models with multiple overlapping HOPs is an open question, particularly regarding how to coordinate edge selection across different potentials.

Summary updated

Abstract

Graphical models with High Order Potentials (HOPs) have received considerable interest in recent years. While there are a variety of approaches to inference in these models, nearly all of them amount to solving a linear program (LP) relaxation with unary consistency constraints between the HOP and the individual variables. In many cases, the resulting relaxations are loose, and in these cases the results of inference can be poor. It is thus desirable to look for more accurate ways of performing inference in these models. In this work, we study the LP relaxations that result from enforcing additional consistency constraints between the HOP and the rest of the model. We address theoretical questions about the strength of the resulting relaxations compared to the relaxations that arise in standard approaches, and we develop practical and efficient message passing algorithms for optimizing the LPs. Empirically, we show that the LPs with additional consistency constraints lead to more accurate inference on some challenging problems that include a combination of low order and high order terms.
BibTeX
@inproceedings{mezuman2013tighter,
  author = {Elad Mezuman and Daniel Tarlow and Amir Globerson and Yair Weiss},
  title = {{Tighter Linear Program Relaxations for High Order Graphical Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=BO-V9U5Ka-q},
}

Loading related content...

Figure