# Exact Inference in High-order Structured Prediction

arXiv: https://arxiv.org/abs/2302.03236 · HTML: https://mlsanity.com/paper/2302.03236/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 29 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Builds on (most cited first, 7 of 7)

- [Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering](https://mlsanity.com/paper/1803.03833/) (2018)
- [Cheeger Inequalities for Submodular Transformations](https://mlsanity.com/paper/1708.08781/) (2017)
- [Information-theoretic Limits for Community Detection in Network Models](https://mlsanity.com/paper/1802.06104/) (2018)
- [Exact inference in structured prediction](https://mlsanity.com/paper/1906.00451/) (2019)
- [Inference in Sparse Graphs with Pairwise Measurements and Side Information](https://mlsanity.com/paper/1703.02728/) (2017)
- [Federated Myopic Community Detection with One-shot Communication](https://mlsanity.com/paper/2106.07255/) (2021)
- [Exact Partitioning of High-order Models with a Novel Convex Tensor Cone Relaxation](https://mlsanity.com/paper/1911.02161/) (2019)

## Built on by (most cited first, 1 of 1)

- [Hyper-STTN: Hypergraph Augmented Spatial-Temporal Transformer Network for Trajectory Prediction](https://mlsanity.com/paper/2401.06344/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of inference in high-order structured prediction tasks. In the context of Markov random fields, the goal of a high-order inference task is to maximize a score function on the space of labels, and the score function can be decomposed into sum of unary and high-order potentials. We apply a generative model approach to study the problem of high-order inference, and provide a two-stage convex optimization algorithm for exact label recovery. We also provide a new class of hypergraph structural properties related to hyperedge expansion that drives the success in general high-order inference problems. Finally, we connect the performance of our algorithm and the hyperedge expansion property using a novel hypergraph Cheeger-type inequality.