# ReMAP: Lossless Residual Neural Lifting for Scalable MAP Inference in Arbitrary-Order Markov Random Fields

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 46 references that are in the map.
- First posted on arXiv 28 Nov 2024.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Loss Surfaces, Mode Connectivity, and Fast Ensembling of DNNs](https://mlsanity.com/paper/1802.10026/) (2018)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [The Loss Surfaces of Multilayer Networks](https://mlsanity.com/paper/1412.0233/) (2014)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [GMNN: Graph Markov Neural Networks](https://mlsanity.com/paper/1905.06214/) (2019)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [Neural Enhanced Belief Propagation on Factor Graphs](https://mlsanity.com/paper/2003.01998/) (2020)
- [Inference in Probabilistic Graphical Models by Graph Neural Networks](https://mlsanity.com/paper/1803.07710/) (2018)
- [Belief Propagation Neural Networks](https://mlsanity.com/paper/2007.00295/) (2020)
- [Factor Graph Neural Networks](https://mlsanity.com/paper/2308.00887/) (2023)
- [A new look at reweighted message passing](https://mlsanity.com/paper/1309.5655/) (2013)
- [Boosting Graph Pooling with Persistent Homology](https://mlsanity.com/paper/2402.16346/) (2024)
- [Conditional Random Field Autoencoders for Unsupervised Structured Prediction](https://mlsanity.com/paper/1411.1147/) (2014)
- [Learning to Solve the Constrained Most Probable Explanation Task in Probabilistic Graphical Models](https://mlsanity.com/paper/2404.11606/) (2024)
- [Neural Network Approximators for Marginal MAP in Probabilistic Circuits](https://mlsanity.com/paper/2402.03621/) (2024)

## Abstract (arXiv)

Maximum a posteriori inference in a finite Markov random field is generally NP-hard. We study an instance-wise optimizer that minimizes the exact multilinear energy under product marginals. The canonical parameterization adds a GNN output to free per-node logits. This residual bypass is a global change of coordinates, so the lifting preserves the infimum, critical points, local extrema (modulo the GNN-parameter fiber), and Hessian inertia of the free-logit problem. Joint gradient flow then induces the preconditioner I+JJtop: the GNN cannot enlarge the feasible set, but it can add dissipation |Jtopnablaℓ|22. For a two-layer branch this extra coupling is four-hop local. We also show that every finite critical point of a nonconstant multilinear objective is a saddle, and that a unique MAP gap Gamma makes conditional-expectation rounding exact once the relaxed gap falls below Gamma; residual gradient flow and joint gradient descent then obey explicit O(1/t) and O(1/k) rates in a small-gap region, with an improved bound under residual alignment. Experiments on synthetic MRFs, UAI 2022 benchmarks, and Physical Cell Identity (PCI) problems evaluate this residual geometry at scale.