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

Abstract: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+JJ^{\top}$: the GNN cannot enlarge the feasible set, but it can add dissipation $\|J^{\top}\nabla\ell\|_{2}^{2}$. 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.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2411.18954 [cs.LG]

(or arXiv:2411.18954v5 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2411.18954 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.