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

Yaomin Wang; Chaolong Ying; Xiaodong Luo; Tianshu Yu

cs.LGNov 28, 2024

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

Authors: Yaomin Wang, Chaolong Ying, Xiaodong Luo, Tianshu Yu

Organizations: School of Data Science, The Chinese University of Hong Kong, Shenzhen · Shenzhen Research Institute of Big Data, China

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 $Γ$ makes conditional-expectation rounding exact once the relaxed gap falls below $Γ$ ; 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.

Figures & tables

Panel of Figure 1 — Figure 1: Residual ReMAP is an optimizer for one instance. The factor energy supplies the loss; the free-logit bypass preserves every search direction; the GNN supplies an adaptive graph-structured geometry. Conditional-expectation rounding converts every relaxed iterate into a no-worse discrete incumbent.

Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP
P_potts_1	1k/7591	$-22215.700$	$-21365.800$	$\mathbf{-22646.529}$	$-21451.025$
P_potts_5	50k/249624	$25668.500$	$35389.000$	$12468.172$	$\mathbf{11466.507}$
P_random_1	1k/7540	$\mathbf{-4901.100}$	$-4505.020$	$-4900.759$	$-4564.763$
P_random_5	50k/249374	$12478.300$	$13337.000$	$12835.994$	$\mathbf{11750.969}$

Table 1: Representative pairwise synthetic instances. Discrete energy; lower is better. ReMAP is the best of five seeds. Full best-of-five and mean

\pm

std tables are Table 6 and Table 7 in Appendix F . Best in bold.

Graph	#Nodes/#Cliques	Toulbar2	SRMP	ReMAP
Graph	#Nodes/#Cliques	Toulbar2	SRMP	Energy	Loss
H_Instances_1	500/41253	NA	$-5785.093$	$\mathbf{-7866.214\pm 389.207}$	$-7859.68\pm 393.719$
H_Instances_2	500/57934	NA	$-18504.788$	$\mathbf{-20260.289\pm 143.276}$	$-20286.571\pm 143.624$
H_Instances_3	1000/36993	NA	$-5903.131$	$\mathbf{-7232.648\pm 337.393}$	$-7229.483\pm 336.218$

Table 2: Synthetic high-order MRFs. Energy values; lower is better. “NA”: no solution within the time limit. Best in bold.

Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP
Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	Energy	Loss
PCI_1	30/165	20.344	20.455	$\mathbf{18.134}$	$18.372\pm 0.161$	$18.373\pm 0.160$
PCI_2	40/311	$\mathbf{98.364}$	98.762	$\mathbf{98.364}$	$98.555\pm 0.109$	$98.555\pm 0.109$
PCI_3	80/1522	$\mathbf{1003.640}$	$\mathbf{1003.640}$	$\mathbf{1003.640}$	$\mathbf{1003.640\pm 0.0}$	$1003.639\pm 0.0$
PCI_4	286/10714	585.977	585.977	426.806	$\mathbf{410.945\pm 2.009}$	$410.996\pm 2.014$
PCI_5	929/29009	1591.590	1591.590	1118.097	$\mathbf{1074.617\pm 5.501}$	$1074.676\pm 5.503$

Table 3: Real PCI instances. Energy values; lower is better. Best in bold.

Instance	#Nodes/#Edges	Residual $u+\rho_{v}$	GNN-only $\rho_{v}$	Free logits $u$
PCI_1	30/165	$\mathbf{18.372\pm 0.161}$	$18.399\pm 0.151$	$18.773\pm 0.000$
PCI_2	40/311	$\mathbf{98.555\pm 0.109}$	$98.733\pm 0.159$	$98.874\pm 0.000$
PCI_3	80/1522	$\mathbf{1003.640\pm 0.000}$	$1004.789\pm 1.241$	$\mathbf{1003.640\pm 0.000}$
PCI_4	286/10714	$\mathbf{410.945\pm 2.009}$	$413.458\pm 5.166$	$448.274\pm 0.000$
PCI_5	929/29009	$\mathbf{1074.617\pm 5.501}$	$1092.796\pm 13.663$	$1286.412\pm 0.000$

Table 4: Parameterization ablation on the five real PCI instances. Discrete energy (mean

\pm

std over five seeds); lower is better.

Appendix figures & tables19 assets

Supplementary material from the paper’s appendix.

Appendix

Method	Use	Variables/factors	Search parameterization	Decoding
Nonconvex MAP relaxation ( Lê-Huu and Paragios, 2018 )	Per instance	Categorical; arbitrary order	Free product-simplex variables; multilinear	Guaranteed non-increasing block rounding
PI-GNN ( Schuetz et al., 2022 )	Per instance	Primarily binary QUBO / polynomial	GNN optimizing a relaxed Hamiltonian	Projection to a discrete assignment
SSMP ( Arya et al., 2024b )	Amortized + refinement	General PGM / MPE queries	Neural query predictor with self-supervised refinement	Threshold/argmax-style assignment
SINE ( Arya et al., 2025 )	Amortized inference	MPE queries	Structure- and parameter-aware neural embeddings	Oracle-assisted or neighborhood decoding
Residual ReMAP (this work)	Per instance	Heterogeneous categorical; explicit arbitrary-order factors	Free logits plus a GNN residual on the multilinear energy	Conditional-expectation rounding

Appendix

Table 5: Methodological positioning. “Per instance” means that optimization variables are fitted for the test instance.

Figure 2: This illustrates the padding procedure for unary loss terms $\phi(x)$ and clique loss terms $\psi(x_{i},x_{j},x_{k})$ , with $|\mathcal{X}|=5$ . $x_{max}$ denotes the variable that has the maximum value range. The elements shown in purple represent the energy values in the original $\phi$ and $\psi$ . After padding, the dimension of vector $\phi$ , as well as each dimension of the energy tensor $\psi(x_{i},x_{j},x_{k})$ , will be 5. Orange entries are a layout placeholder (implementation: $\max(\phi)$ or $\max(\psi)$ ); after $-\infty$ masking they do not enter $F(p)$ .

Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP	Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP
P_potts_1	1k/7591	-22215.700	-21365.800	-22646.529	-21451.025	P_random_1	1k/7540	-4901.100	-4505.020	-4900.759	-4564.763
P_potts_2	5k/37439	-111319.000	-105848.000	-110022.248	-105952.531	P_random_2	5k/37488	-24059.900	-22934.000	-24139.194	-21834.693
P_potts_3	10k/75098	-221567.000	-210570.000	-218311.424	-209925.269	P_random_3	10k/74518	-47873.200	-47002.000	-48107.172	-42120.325
P_potts_4	50k/248695	12411.200	13454.600	12955.129	11679.429	P_random_4	50k/249554	12881.500	14342.300	12233.890	11769.934
P_potts_5	50k/249624	25668.500	35389.000	12468.172	11466.507	P_random_5	50k/249374	12478.300	13337.000	12835.994	11750.969
P_potts_6	50k/300181	17609.800	17362.600	17635.791	16756.999	P_random_6	50k/299601	16723.600	16754.500	18031.964	16700.674

Appendix

Table 6: Full pairwise synthetic results. Discrete energy; lower is better. ReMAP is the best energy over five seeds. The four-row excerpt in the main text is Table 1 . Best in bold.

Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP
Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	Energy	Loss
P_potts_1	1k/7591	-22215.700	-21365.800	-22646.529	-21791.868 $\pm$ 218.106	-21799.268 $\pm$ 216.075
P_potts_2	5k/37439	-111319.000	-105848.000	-110022.248	-105762.092 $\pm$ 434.674	-106016.855 $\pm$ 168.861
P_potts_3	10k/75098	-221567.000	-210570.000	-218311.424	-211406.914 $\pm$ 1489.099	-210182.681 $\pm$ 275.164
P_potts_4	50k/248695	12411.200	13454.600	12955.129	12219.817 $\pm$ 538.969	11811.682 $\pm$ 123.877
P_potts_5	50k/249624	25668.500	35389.000	12468.172	12010.036 $\pm$ 266.610	11673.708 $\pm$ 146.513

Appendix

Table 7: Pairwise synthetic instances, same five trials as Table 6 . ReMAP Energy and Loss are mean

\pm

std. Energy is the decoded discrete energy; Loss is the relaxed multilinear objective. Lower is better.

Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP
Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	Energy	Loss
ProteinFolding_11	400/7160	-3106.080	-3079.030	-4461.047	-3976.908 $\pm$ 52.047	-4018.784 $\pm$ 36.491
ProteinFolding_12	250/1848	3570.210	3604.240	3562.387(opt)	16137.682 $\pm$ 16.020	16090.801 $\pm$ 22.869
Grids_19	1600/3200	-2250.440	-2103.610	-2643.107	-2400.251 $\pm$ 20.061	-2398.078 $\pm$ 16.010
Grids_21	1600/3200	-13119.300	-12523.300	-18895.393	-16592.926 $\pm$ 94.368	-16605.564 $\pm$ 113.096
Grids_24	1600/3120	-13210.400	-13260.900	-18274.302	-16323.767 $\pm$ 171.950	-16222.104 $\pm$ 222.593

Appendix

Table 8: Results on the UAI inference competition 2022. Numbers correspond to the obtained energy values. Best in bold.“opt” denotes it is the optimal solution.

Graph	#Nodes/#Cliques	Toulbar2 (1200s)	Toulbar2 (3600s)	ReMAP
Graph	#Nodes/#Cliques	Toulbar2 (1200s)	Toulbar2 (3600s)	Energy	Loss
Maxsat_gss-25-s100	31931/96111	-145969.060	-145969.060	-139904.266 $\pm$ 1717.483	-139914.341 $\pm$ 1710.139
BN-nd-250-5-10	250/250	155.129	154.610	189.395 $\pm$ 5.424	187.729 $\pm$ 4.966
Maxsat_mod4block_2vars_10gates_u2_autoenc	479/123509	-186103.111	-186103.111	-146166.620 $\pm$ 41250.035	-146166.797 $\pm$ 41249.859
Maxsat_mod2c-rand3bip-sat-240-3.shuffled-as.sat05-2520	339/2416	-3734.627	-3737.076	-3511.994 $\pm$ 220.654	-3511.822 $\pm$ 220.471
Maxsat_mod2c-rand3bip-sat-250-3.shuffled-as.sat05-2535	352/2492	-3863.259	-3863.259	-3686.567 $\pm$ 166.998	-3686.085 $\pm$ 166.499

Appendix

Table 9: Results on high-order cases of the UAI inference competition 2022. Numbers correspond to the obtained energy values. Best in bold.

Graph	#Nodes/#Edges	dim=64	dim=512	dim=1024	dim=4096	dim=8192
ProteinFolding_11	400/7160	-3892.949	-3886.701	-3946.168	-4065.294	-4003.323
ProteinFolding_12	250/1848	16064.795	16068.406	16051.798	16088.073	16071.324
Grids_19	1600/3200	-2355.159	-2404.975	-2337.281	-2341.2746	-2373.618
Grids_21	1600/3200	-16478.466	-16169.0320	-16446.410	-16209.017	-16278.668
Grids_24	1600/3120	-16008.008	-15900.249	-15841.799	-15608.162	-15948.219
Grids_25	1600/3120	-2343.547	-2353.223	-2319.899	-2306.686	-2288.182

Appendix

Table 10: Full results on the UAI inference competition 2022 of ReMAP with different feature dimensions. Numbers correspond to the obtained energy values.

Figure 3: The loss curves of the Segmentation_14, P_potts_6 and P_potts_8 from pairwise potts synthetic problems.

	Graph Convolutions	Neighbor Influence
GCN	$h_{i}^{(k)}=\sigma\left(W_{k}\cdot\sum_{j\in\mathcal{N}(i)\cup\{i\}}(\operatorname{deg}(i)\operatorname{deg}(j))^{-1/2}h_{j}^{(k-1)}\right)$	Unequal
GAT	$h_{i}^{(k)}=\sigma\left(\sum_{j\in\mathcal{N}(i)\cup\{i\}}\alpha_{i,j}W_{k}h_{j}^{(k-1)}\right)$	Unequal
GraphSAGE	$h_{i}^{(k)}=\sigma\left(A_{k}h_{i}^{(k-1)}+B_{k}\|\mathcal{N}(i)\|^{-1}\sum_{j\in\mathcal{N}(i)}h_{j}^{(k-1)}+b_{k}\right)$	Equal

Appendix

Table 11: Graph convolutions in typical GNNs

Figure 4: The landscape of instance Segmentation_19. From left to right, the columns correspond to networks with $K\in\{1,2,5,8\}$ layers. The first row is the landscape range from $[-10,+10]$ for both $\delta$ and $\eta$ direction. The second row is the landscape range from $[-1,+1]$ for both $\delta$ and $\eta$ direction.

Figure 5: The average loss curves over UAI inference competition 2022 pairwise cases, PCI instances and synthetic instances using GraphSAGE, GCN and GAT as the GNN backbones.

Figure 6: The average loss curves over UAI inference competition 2022 pairwise cases using different optimizers.

Figure 7: The training loss of instance Segmentation_19 after convergence of using network layer number

\{1,2,5,8\}

Instances	Algorithm/Solver	200s	400s	600s	800s	1000s	1200s
PCI_1	Toulbar2	18.134	-	-	-	-	-
PCI_1	ReMAP	18.211 (10s in total)	-	-	-	-	-
PCI_2	Toulbar2	98.364	-	-	-	-	-
PCI_2	ReMAP	98.446 (16s in total)	-	-	-	-	-
PCI_3	Toulbar2	1003.640	-	-	-	-	-
PCI_3	ReMAP	1003.640 (71s in total)	-	-	-	-	-

Appendix

Table 12: Time comparison between Toulbar2 and ReMAP on PCI instances. “-” if the solving process is already stopped.

Figure 8: Wall-clock convergence time of ReMAP on grid graphs from

5^{2}

50^{2}

nodes. Each size is repeated five times. Convergence is a relative loss change below

10^{-4}

$\displaystyle\min\limits_{z,L}\quad$	$\displaystyle\sum\limits_{(i,j)\in\mathcal{E}}a_{ij}L_{ij}$	(19)
$\displaystyle\mathrm{s.t.}\quad$	$\displaystyle z_{np}\in\{0,1\},\quad\forall n\in N,p\in P$	( 19 a)
	$\displaystyle\sum\limits_{p\in P}z_{np}=1,\quad\forall n\in N.$	( 19 b)
	$\displaystyle\sum\limits_{p\in M_{ih}}z_{n_{i}p}+\sum\limits_{p\in M_{jh}}z_{n_{j}p}-1\leq L_{ij},\forall(i,j)\in\mathcal{E},\forall h\in\{0,1,2\}.$	( 19 c)

Appendix

Table 22

Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	ReMAP
Graph	#Nodes/#Edges	LBP	TRBP	Toulbar2	Energy	Loss
PCI_synthetic_1	280/9678	564198.000	568082.000	522857.923	$\mathbf{496015.5\pm 6307.363}$	$496013.662\pm 6297.169$
PCI_synthetic_2	526/34500	2.092e+06	2.084e+06	2.064e+06	$\mathbf{1.923e+06\pm 9977.015}$	$1.923e+06\pm 10007.739$
PCI_synthetic_3	1000/49950	2.932e+06	2.908e+06	2.856e+06	$\mathbf{2.665e+06\pm 4555.868}$	$2.664e+06\pm 4468.965$
PCI_synthetic_4	1500/78770	4.568e+06	4.532e+06	4.534e+06	$\mathbf{4.215e+06\pm 13500.602}$	$4.214e+06\pm 13252.456$
PCI_synthetic_5	2000/120024	6.807e+06	6.904e+06	7.023e+06	$\mathbf{6.542e+06\pm 19789.758}$	$6.540e+06\pm 19782.638$

Appendix

Table 17: Synthetic PCI instances, same pairwise MRF conversion as Table 3 . Energy values; lower is better. Best in bold.

MAP Estimation

See all 8 papers

A polynomial time algebraic solution to exact marginal inference in Markov Random Field models
Sep 25, 2017Ikhlef BecharEfficient Inference Markov Random Fields
Aix Marseille Univ, Universit´e de Toulon, CNRS, ENSAM, LSIS La Garde 83957, France
Rank Collapse, Fixed Points, and the Renormalization Group Structure of MLP Residual Networks
Jun 9, 2026Parviz Haggi-Mani, Irina RishMultilayer Perceptrons Neural Network Training Dynamics
Universit´e de Montr´eal · Mila - Quebec AI Institute
Fast Graph Laplacian Estimation using Effective Resistance
Sep 20, 2026Christoffer Kjellson, Claudio Altafini, Emma TeglingGraph Structure Learning Probabilistic Graphical Models
Department of Automatic Control, Lund University · ELLIIT Strategic Research Area · Division of Automatic Control, Department of Electrical Engineering, Linköping University

Sep 25, 2017J/K move · Enter open · S save

A polynomial time algebraic solution to exact marginal inference in Markov Random Field models

Ikhlef Bechar

Aix Marseille Univ, Universit´e de Toulon, CNRS, ENSAM, LSIS La Garde 83957, France

Efficient Inference Markov Random Fields Markov Models Probabilistic Graphical Models

Open paper AskPDF arXiv

This paper develops on algebraic grounds a polynomial time exact linear solution to the hard combinatorial problem of marginal inference in Markov random field (MRF) models under general assumptions. To prove our claim, we first implicitly remodel a MRF joint distribution as the unique solution of some linear identity assuming its clique potential functions (equivalently, its individual conditional distributions) to be specified. Then, by assuming an arbitrary point subset, we relax accordingly such a (global) linear identity for deriving a second linear identity, solely, acting on a polynomial time number of entries (e.g.; local marginals or Fourier frequencies) of a solution. Then, we show, only using linear algebraic techniques, that such an identity enables to capture all the entries necessary for the exact reconstruction of an MRF marginal distribution, thus, allowing to solve for the latter, exactly and in polynomial time, using a standard linear solver. Last, but not least, this paper probably solves, once and for all, the P = NP conjecture.

Abstract

MAP Estimation

Explore similar work

A polynomial time algebraic solution to exact marginal inference in Markov Random Field models

Rank Collapse, Fixed Points, and the Renormalization Group Structure of MLP Residual Networks

Fast Graph Laplacian Estimation using Effective Resistance