arXiv：cs.AI· Yaomin Wang, Chaolong Ying, Xiaodong Luo, Tianshu Yu·· 5 小时前
ReMAP：面向任意阶马尔可夫随机场可扩展 MAP 推理的无损残差神经提升
ReMAP: Lossless Residual Neural Lifting for Scalable MAP Inference in Arbitrary-Order Markov Random Fields
AI 导读
ReMAP 提出一种实例级优化器，通过将 GNN 输出作为残差旁路叠加到自由节点 logits 上，在乘积边缘分布下最小化精确多线性能量。该残差参数化是全局坐标变换，可保持下确界、临界点、局部极值与 Hessian 惯性不变。实验在合成 MRF、UAI 2022 基准和 PCI 问题上验证了该残差几何的可扩展性。
正文
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.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2411.18954 [cs.LG] |
| (or arXiv:2411.18954v5 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2411.18954 arXiv-issued DOI via DataCite |
Submission history
From: Yaomin Wang [view email]
[v1]
Thu, 28 Nov 2024 06:50:47 UTC (859 KB)
[v2]
Fri, 16 May 2025 08:18:23 UTC (649 KB)
[v3]
Tue, 17 Feb 2026 09:27:26 UTC (402 KB)
[v4]
Thu, 7 May 2026 12:50:20 UTC (392 KB)
[v5]
Sun, 11 Oct 2026 03:56:15 UTC (394 KB)
来源：arXiv：cs.AI · arxiv.org