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.
Introduction
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. Examples include constraints like "at least $k$ pixels must be active" or global objectives like minimizing the average cut of a graph. While researchers have developed many ways to perform inference with HOPs, almost all existing approaches are mathematically equivalent to a Unary Consistency LP ($LP_\emptyset$). In this relaxation, the high-order term only communicates with the rest of the model through single variables. This often results in a "loose" relaxation, where the algorithm returns fractional, non-sensical solutions (a high integrality gap) rather than the true optimal assignment.
Methods: From Unary to Edge Consistency
To address the limitations of standard relaxations, this work introduces 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: The authors prove that several popular techniques, such as using auxiliary variables to simplify HOPs, are actually just $LP_\emptyset$ in disguise and suffer from the same weaknesses.
- Tractable Message Passing: Specific classes of HOPs—specifically cardinality-based potentials and Pattern HOPs—allow for efficient message computation even when connected to edges, provided the set of edges $S$ has low tree-width.
- Weak Cycle Agreement (WCA): Since including all edges is computationally expensive, the authors propose WCA, a heuristic that iteratively adds edges to the consistency set $S$ that are most likely to tighten the LP bound.
Key Insights and Ideas
- The Unary Bottleneck: The primary source of error is the "interface" between a high-order potential and the rest of the graph. Even if the HOP itself is easy to compute, if it only communicates via single variables, global structure is lost.
- Tree-width vs. Accuracy: Enforcing consistency on every edge is not always necessary. For many problems, a carefully chosen tree-structured subset of edges (tree-width 1) is sufficient to make the relaxation provably exact.
- Reparameterization: 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.
Experimental Results
The proposed methods were evaluated on synthetic tree models, 4-connected grids, and the Berkeley Segmentation Dataset (BSDS). In Hamming Ball Exclusion experiments, the standard $LP_\emptyset$ failed frequently, while $LP_S$ (using only a tree-width of 1) found the exact solution every time.
On the BSDS image segmentation task, formulated as an NP-hard "average-cut" problem, $LP_S$ with a maximum tree-width of 6 provably found the global optimum for 34 out of 40 images. This outperformed standard spectral clustering solutions in 38 out of 40 cases, with an average objective function improvement of 70%.
Conclusion
While message passing with edge consistency is more computationally expensive than unary consistency, it provides a significant leap in accuracy for challenging graphical models. Future work includes scaling these methods to pixel-level grids using techniques like Fast Fourier Transforms (FFTs) and extending the framework to models with multiple overlapping high-order potentials.
Summary updated