HOP-MAP: Efficient Message Passing with High Order Potentials

Daniel Tarlow, Inmar E. Givoni, Richard S. ZemelAISTATS 2010 · OpenReview

Abstract

There is a growing interest in building probabilistic models with high order potentials (HOPs), or interactions, among discrete variables. Message passing inference in such models generally takes time exponential in the size of the interaction, but in some cases maximum a posteriori (MAP) inference can be carried out efficiently. We build upon such results, introducing two new classes, including composite HOPs that allow us to flexibly combine tractable HOPs using simple logical switching rules. We present efficient message update algorithms for the new HOPs, and we improve upon the efficiency of message updates for a general class of existing HOPs. Importantly, we present both new and existing HOPs in a common representation; performing inference with any combination of these HOPs requires no change of representations or new derivations.

Introduction

In probabilistic graphical models, finding the most likely configuration of variables—Maximum A Posteriori (MAP) inference—is a fundamental task. Traditional models often rely on pairwise potentials, which capture local interactions between two variables (e.g., ensuring neighboring pixels in an image share similar colors). However, many complex real-world constraints are inherently global or "high-order," involving many variables simultaneously. Examples include enforcing a specific object size (cardinality), ensuring a shape is contiguous (convexity), or maintaining a specific sequence of events (ordering).

The primary challenge with High-Order Potentials (HOPs) is computational complexity. Standard message-passing algorithms scale exponentially ($2^N$) with the number of variables in a potential, making large-scale global constraints intractable. The HOP-MAP framework addresses this by identifying structural properties that allow for efficient, near-linear time inference.

The HOP-MAP Framework

The authors propose a unified approach to handle several classes of tractable HOPs by reducing complex combinatorial problems to efficient dynamic programming tasks.

1. Cardinality-Based Potentials

These potentials depend solely on the number of active variables. By utilizing a clever sorting and dynamic programming approach over cumulative sums, the authors reduced the complexity of computing all outgoing messages from $O(N^2)$ to $O(N \log N)$. This makes global count constraints practical for large variable sets.

2. Order-Based and Convex Potentials

The framework introduces new potentials for sequential data:

  • Convex Set Potentials: These enforce that active variables in a sequence must be contiguous (forming a "convex set" in 1D), solved in $O(N)$ time.
  • Before-After Potentials: These encourage one set of variables to precede another in a sequence, also solved in $O(N)$.

3. Composite HOPs and Unified Representation

A key innovation is the "Composite HOP," a meta-potential that switches between different HOPs based on logical rules. By using a consistent binary representation and message normalization scheme, these diverse HOPs can be mixed and matched in a single factor graph without requiring custom derivations for each new combination.

Experimental Evaluation

Synthetic Image Segmentation

The framework was tested on a $64 \times 64$ grid task aimed at recovering a square foreground from noisy input. Standard pairwise models often fail when local evidence is missing. By incorporating Convexity and Cardinality HOPs, the model can "fill in the gaps" by enforcing global shape and size constraints that local pixels cannot perceive.

Synthetic image segmentation results demonstrating the recovery of a structured foreground from noisy data using high-order priors.

Rank Aggregation

The paper also applies HOP-MAP to document ranking (Kemeny rank aggregation), an NP-hard problem. By treating it as a MAP inference problem with high-order constraints—specifically "Before-After" potentials for user preferences and bipartite matching potentials to ensure each rank is filled exactly once—the framework achieves efficient convergence.

Convergence of dual objectives and resulting permutation matrices for the rank aggregation task across different regularization parameters.

Conclusion

HOP-MAP significantly lowers the barrier to using complex global constraints in graphical models. By reducing the "cost per message" to near-linear time, high-order factors become nearly as computationally cheap as pairwise factors. This modularity allows researchers to move from manual, problem-specific derivations toward a flexible "vocabulary" of global priors for robust inference.

Future work remains in extending these factors to communicate via larger "separator sets" for tighter approximations and integrating a broader range of algebraic or logical constraints into the unified framework.

Summary updated

Abstract

There is a growing interest in building probabilistic models with high order potentials (HOPs), or interactions, among discrete variables. Message passing inference in such models generally takes time exponential in the size of the interaction, but in some cases maximum a posteriori (MAP) inference can be carried out efficiently. We build upon such results, introducing two new classes, including composite HOPs that allow us to flexibly combine tractable HOPs using simple logical switching rules. We present efficient message update algorithms for the new HOPs, and we improve upon the efficiency of message updates for a general class of existing HOPs. Importantly, we present both new and existing HOPs in a common representation; performing inference with any combination of these HOPs requires no change of representations or new derivations.
BibTeX
@inproceedings{tarlow2010hop,
  author = {Daniel Tarlow and Inmar E. Givoni and Richard S. Zemel},
  title = {{HOP-MAP: Efficient Message Passing with High Order Potentials}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=S4ev5U9t6-c},
}

Loading related content...

Figure