From Fields to Random Trees
Authors: Yaomin Wang
Xiaodong Luo
Tianshu Yu
Venue: ICLR 2026 Poster (2026)
Keywords: MAP estimation
Markov Random Fields
random spanning trees
Primary area: optimization

Abstract: This study introduces a novel method for performing Maximum A Posteriori (MAP) estimation on Markov Random Fields (MRFs) that are defined on locally and sparsely connected graphs, broadly existing in real-world applications. We address this long-standing challenge by sampling uniform random spanning trees(SPT) from the associated graph. Such a sampling procedure effectively breaks the cycles and decomposes the original MAP inference problem into overlapping sub-problems on trees, which can be solved exactly and efficiently. We demonstrate the effectiveness of our approach on various types of graphical models, including grids, cellular/cell networks, and Erdős–Rényi graphs. Our algorithm outperforms various baselines on synthetic, UAI inference competition, and real-world PCI problems, specifically in cases involving locally and sparsely connected graphs. Furthermore, our method achieves comparable results to these methods in other scenarios. The code of our model can be accessed at \url{https://github.com/LOGO-CUHKSZ/From-fields-to-random-trees.git}.

Published as a conference paper at ICLR 2026
FROM FIELDS TO RANDOM TREES
Yaomin Wang 1,2 Xiaodong Luo", Tianshu Yu!
School of Data Science, The Chinese University of Hong Kong, Shenzhen
2 Shenzhen Research Institute of Big Data
edu. yaominwang@l link. cuhk edu..edu... en (xiaodongluo, yutiansho) edu.
ABSTRACT
This study introduces a novel method for performing Maximum A Posteriori (MAP) estimation on Markov Random Fields (MRFs) that are defined on locally and sparsely connected graphs, broadly existing in real-world applications. We address this long- -ttadsiniing challenge by sampling uniform random spanning trees (SPT) from the associated graph. Such sampling procedure effectively breaks the cycles and decomposes the original MAP inference problem into overlapping sub- problems on trees, which can be solved exactly and efficiently. We demonstrate the effectiveness of our approach on various types of graphical models, including grids, cellular/cell networks, and Erdós-Rényí graphs. Our algorithm outperforms various baselines on synthetic, UAI inference competition, and real-world PCI problems, specifically in cases involving locally and sparsely connected graphs. Furthermore, our method achieves comparable results to these methods in other scenarios. The code of our model can be accessed at httph::////// :/gp::::///ie tiggthhub..... com/
LOGO- From fields- to- -tto-rrnnntteeeeee...oe trees.gir
INTRODUCTION
In this paper, we investigate a novel approach to infer on Markov Random Fields defined over sparsely and locally connected graphs via random spanning tree sampling. Formally, an MRF is defined over an undirected graph G = (V, E), where V represents the index set of random variables and È corresponds variable 2; X takes a value from finite alphabet X' (z, can be a vector) with node index V, expressed as a product of potential functions, each associated with
the edge set implying dependencies among these variables. Each random
and the joint distribution subset of variables that forms a clique in G. In this paper, we consider minimizing energy functions with unary terms 0; and pairwise terms Oij. then the MAP estimate is:
min E(X)
min (EE)ViEV
(((x) + Σ 01g(21;zz)) (F.)EE
(I)
where X = Jvev Optimization problem MRFs expressed in equation 1 is prevalent model in the realm of probabilistic graphical modeling (Clifford Hammersley 1971]. Notably, MRF and its counterparts enable the principled and simplified representation of joint probability distributions over a set of variahles, conditioned upon the structure of an undirected graph. The intrinsic capability of MRFs to model contextual relationships in data offers cohesive and efficient framework for addressing inference and estimation chal- lenges across diverse array of scientific and engineering disciplines, including computer vision (Wang et all
[S al. (2021). 5G networks (Kumar al. (2022), pathology image analysis (Li 2020) and other
hields combining the power of GNN (Xu et al. 2021a Wu et al. 2020).
The problem in equation [ is known to be NP-hard in general. Early trials to efficiently and suboptimally solve equation [ dates back to the 80's of the previous century, when Judea Pearl developed the prestigious Belief Propagation (BP) algorithm (Pearl 1988). Motivated by this breakthrough, series of BP variants
were further proposed (Wiegerinck & Heskes 2002) Yedidia et al. 20055 Montanari Rizzo 2005). Other prominent methods include Mean Field Approximation (Saito et al. [0122] Zhang 1993] Zhang & Hanauer 1995), Graph Cuts (Gregg et al. 1989), and Junction Trees (Aji & McEliece 2000), to name few. These methods offer varying trade-offs between accuracy and computational efficiency. To the best of our knowledge,
"oorrespnniigg author.

---

Published as a conference paper at ICLR 2026
no single method stands out Maaeeoffttheaar over all existing problems spanning various scales, topologies, and problem distribution.
In this study, we put our special focus on sparsely and locally connected graphs. In realistic scenarios, such
topologies broadly exist in power grid (Cuffe & Keane (2017). 5G networks (Agiwal et al. [2016] [Liu & Zou
2020). transportation networks (Yunfei Ma & Razavi 2022). and even social networks (Majeed al. 2022).
Efficient MAP inference in the corresponding applications crucial. Beyond our focus, we emphasize that
study can flexibly extended into other types of graphs.
Diverging from existing well-established strategies, our approach leverages the structure of random spanning trees to efficiently infer on MRFs. In a nutshell, our approach consists of "sampling random trees- solving MRFs on trees trerinnerging" steps. Concretely, instead of solving the MRF on the entire graph directly, we sample multiple spanning trees from the original graph and solve the MRF independently on each tree, which exact inference is tractable. The final solution to equation [ is then approximated by merging the solutions from all sampled trees. Our approach thus combines the benefits of exact tree-based inference procedures with the flexibility of sampling methods, creating a balance between computational efficiency and accuracy.
We conduct experiments on synthetic instances, UAT competition instances (uai), and real-world Physical Cell Identity (PCI) instances, covering variety of problem scales. types of topologies. and energy functions. We observe superior performance against several baselines in the sparse and local network setting. and comparable performance in other settings, which strongly pose the promise of the proposed method in various scenarios.
In summary, our contribution through this proposed method introduces a scalable and efficient sampling-hare approach to infer MRFs on locally and sparsely connected graphs, mitigating the drawbacks of existing meth- ods. Superior performance is observed in benchmarks across wide spectrum. By transcending the traditional methodologies and introducing structural simplification via topological sampling over trees, this work posits rich potential to solve intricate MRF problems in the real world.
RELATED WORKS
In MRFs, the energy function is linked to a graph-structured probability distribution. A significant inference challenge in MRFs is determining the MAP configuration. Although minimizing the energy function of MRF models is NP-hard, advances inference techniques have significantly expanded the model's capabilities. The success solving the MAP estimation problem on cycle-free graphs is highly dependent on the graph hss structure. In these graphs, the MAP problem can be effectively tackled using a variant of the min-sum al- gorithm (Clifford & Hammersley 1971 Besag 1974 Kumar al.,20055. which facilitates message passing between nodes and serves graphs. For graphs containing cycles, graph cut methods (Komodakis et al. 2007 Roy & Cox 1998 Boykov eet al. 1998 Ishikawa & Geiger 1998 Szummer et al.] 2208 Ishikawa |003) Schhessnngr & FLACH [2066]
extension of the Viterbi algorithm (Yedidia al. (2003 to arbitrary fyele-free
offer potent solution by employing
cut/max-flow strategics to efficinnlly reduce discrete MRFs energy.
The belief propagation (BP) algorithm, introduced by Pearl (Pearl) 1982 1988) in 1982, is an efficient iterative inference algorithm for Bayesian belief networks, functioning through lixed-point message passing. Its adapt- ability has made a widespread solution for various types of MRFs. Nonetheless, BP encounters difficulties with models containing loops. Loopy belief propagation (LBP) attempts to resolve this by iterating message passing within graphs, even with loop presence (Wciss & Freeman 2001 Felzenszwalb & Huttenlocher] 2004] Frey & Mackay 2002).. While LBP has shown efficacy in several vision tasks (Sun et al. 20022). it does not ensure fixed-point convergence, and its theoretical underpinnings remain elusive. The quest for flexible, convergence-guarantes method persists, yet significant advancements have been made to enhance BP's per- formance. The method proposed by Girm & Felzenszwalb, (2023) enhances BP by adjusting the significance of input messages through discount factor for remote nodes in the message passing chain. Additionally, lever- aging graph topology for decomposition mitigates the impact of loops. In Yan et al. (2023). ) BP's inefficiency large-scale MRFs is addressed by constructing hierarchical framework. lacilitating inference via energy connections between layers. Another strategy, detailed by Hamze & de Freitas (2004). involves partitioning graphs into two segments to serve as mutual evidence for updates, although its applicability is limited to graphs with predefined structures. In KKirkey et al. (202T). they propose graph decomposition using primary circles of specified length from any given node, aiming to cireumvent short loop influences, yet is not effective for large-scale graphs. Integrating tree structures to break loops within the graph, the Junction Tree Algorithm (JTA) (Aji & McEliece) 2000). an exact inference method for arbitrary graphs, entails finding a maximum spanning tree across the largest cliques of a triangulated graph, task known to be NP-hard, thereby limit- ing its practicality. In the realm of pairwise MRFs, problems are formulated as integer linear programming (ILP) (Wainwright et al., 22055] Kolmogorov| (2006), where solutions are derived from a dual problem using a convex combination of trees. This class of algorithms, known as tree-reweighted message passing (TRW) techniques, encompasses edge-based (TRW-E) and tree-based (TRW-T) schemes, both of which lack guaran- teed convergence, potentially looping infinitely. The sequential TRW-S scheme (Kolmogorov] (2066) achieves state of weak tree agreement (WTA), ensuring the lower bound stabilizes, albeit requiring substantial time
2

---

Published as a conference paper at ICLR 2026
reach this stage. TRBP has long been considered the state-of-the-art (SOTA) methodology and has been adapted in Xu al. (2021b) to exploit modern GPUs for accelcrated inference processes.
Several approaches have leveraged tree structures to address graph-related challenges. |Batra et al. (2010) pro- poses a graph decomposition method using outer-planar graphs. However, this approach is restricted to planar MRFs (such as grids or superpixel adjacency graphs), and the computational complexity in determining both the required number and structure of subgraphs limits its applicability general and large-scale graphs. The method in Pletscher al. (2009) employs tree log- likelihood for approximation, while [Skurikhin (2014) com- bines ligeliildoood maximization with gradient descent for inference, specifically on grid structures. Both methodologies rely on voting mechanisms for final predictions. Using trees and Non- parametric Belief Prop- agation (Savic & Zazo 2010) improve the accuracy in solving the localization problem in communication networks under 100 nodes. None of these three methods implement message correction
edges, potentially leading to deviations from original messages, as demonstrated I Lemma [ While Bhidley & Guestrin (2010) addresses structure learning, our work specifically focuses on MAP inference in MRFs and CRFs. Additionally, their approach is limited to graphs exhibiting tree-like structures. Trees could also work on binary inference problems Cesa-Bianchi al. 2010) through graph transformation, converting tree structures into line graphs for prediction purposes. Our work proposes novel methodology that addresses two critical challenges in MRFs: circumventing the computational complexities associated with loop structures while maintaining faith- ful approximations of the original problem formulation. This approach demonstrates particular efficacy in handling large-scale MRF instances and problems that can be formulated within the MRF framework.
PRELIMINARIES
Markov Random Field. MRFs can he used to model probabilistic undirected graphs. We follow the notations in Section. and further suppose [E] M and | N. In this paper, each node i corresponds to a discrete state variable xu E Xx, Vi V, where X is finite alphabet. And there a conditional independence between
variables
((xx)\(=.)))) = P(a.)<z;) for (i. E E).
(2)
where I²(-) is the probability function throughout this paper. Thus, the distribution on the graph g can be factorized into product of local Markow potentials
P(X) = 1/2 E(X)) 1 exp (-Ex Easice (5(
(3)
where Z is the partition function, (.(.) denotes the unary energies, (-)(-) represent the pairwise interaction energies, and E' the energy function. The specific forms of energy functions are determined by the nature of the problems and they are all known most cases. In our study, we aim to maximize the posterior probability by finding the optimal configuration of the hidden variables X == {z,} (assign appropriate values to cach of the random variables). This corresponds to minimizing the energy function:
X
arg max P(X) = arg arg min E(X) XEx
Xex
Sum-Product Belief Propagation. The key subroutine of our Spanning Tree message passing algorithms is sum- com-product belief propagation of Pearl (Peari) 1988). BP is an algorithm for approximate minimization of energy F((x)) as in equation 3 it is exact if the graph does not have loops (e.g., trees and chains). Sum Sum-product BP maintains a directional message Mj from node to node j. The hasic operation of BP is pass the message from node to node j along the edge (1, After receiving all the messages from node i's neighbors, the marginal distribution of node reads:
P(a.[XM(:))) = P(c.) II Mys
(5)
(K,)EE
where P((:;) is the prior marginal of x.. In the absence of specific prior information, we will assume that all priors are uniformly distributed. BP algorithm iteratively passes messages in a specific order until a stopping criterion is met. One numerical method that improves the performance of BP is to stabilize the fixed point iteration scheme with damping (Murphy et al. 2013). which helps prevent oscillations between two steady states. This method involves replacing the term II(..) My in equation 5 received messages:
with a convex combination of the
M (1 - a) aaMl where a E (0. 1) is known as the damping factor and refers to the iteration number.
(6)
Random Spanning Trees. Given graph G = (V,E), we denote T the collection of all the spanning trees T and ((T) some distribution over T. The spanning trees we select from T is {2's TiK E KC), where KC is the index set of the trees. Denote pr the probability of sampling a spanning tree I from T. Throughout the paper, we assume that each distinct tree is sampled with equal probability, i.e., for any two distinct spanning trees T,, T2 STTT), PT, PTz. For each edge (t,j) E E, we denote Più P((i,)) T, T ~ R(T)) the prohability that an edge (i,j) appears in random spanning tree.
3

---

sample candidate tree set Published as a conference paper at ICLR 2026
4 MAP INFERENCE USING TREE SAMPLING
In this section, we present approach and examine the potential benefits of approximating the original prob- lem by combining the results via the analysis random spanning trees original graph. Furthermore, we preseat heuristic that has the potential to improve the approximation outcome by capitalizing on the in- Tormation obtained during the "BP update inference" procedure. Subsequently, we dive into thorough examination of the underlying logic behind algorithm and conduct comprehensive analysis of its plexity.
Algorithm 1: MAP Graph using Spanning Tree Sampling
Input: Graph index of spanning trees number of iterations iter.
Output: overall states X. Tramn + [TT [K]] for T&
while not converge do
for E K do
Apply BP Ta Trand compute ph, (a Va; X:
M = (p(xs E E = (II
(PT (z. (x:))a EX; // update marginals
KEK
X-ibbs = GibbsSampler(MM)
Gresdy = GreedySSlector(MM)
Ebest,t min( ( 1
E(X(mod)))
Update temp according to Ptemp"
pebst.
Ebeat,
// update best x
10 X
X-best,t, tempp
4.1 ALGORITHM
nis %idl+ Σ Sylenig) bolkd
nie Aini+ Σ wuldte s)) bulk
elu
E Root Σ Miliin 2010
Sompling
Approximation
Biile Sumpler
Pir
Original Groph
Random Spanning Trees
Grodd
Tree sampling Bellef propagation
Merging
Figure 1: Pipeline of the proposed approach.
Procedures in the proposed approach are summarized Algorithm I and pipeline diagram is illustrated in Fig. []] While the presence of loops in the original graph renders it analytically intractable, conducting belief propagation cach of the spanning trees efficiently defivers exact solutions. Note spanning tree is a structure that encompass all nodes and capture significant amount of the relationships between nodes without loops, which maximally utilizes original information and avoids oscillations.
By sampling spanning trees from the graph and doing belief propagation on these trees, we are actually trying to formulate series of sub-problems of the original problem and solve the original problem by solving these sub problems. The sub-put problem spanning tree T is shown below:
min F
(X)
min {x:)
Σa (x))+ LEV
Σ 0,g( (FJ)T
To ensure that the combined energy of the spanning trees aligns with energy the original graph, and consequently that the joint distribution over the trees matches the joint distribution the original graph, is crucial to validate the correctness of the belief's propagated within the trees. During the belief propagation procedure, messages passed along edge represent the marginalized joint distribution of that edge, which inherently depends the pairwise energy
4

---

Published as a conference paper at ICLR 2026
To mitigate the bias introduced by the sampling procedure, we adjust the pairwise beliefs each uniformly sampled spanning tree using the probability Py an edge (i, appearing in uniformly sampled spanning tree. The adjustment coefficient for the pairwise energy on edge (i, is given by Wiy = 1/pp.-
To accurately estimate the probability Pij of an edge appearing in a uniformly sampled spanning tree, we utilize
the concept of effective resistance, as detailed in Section 4.3 is formulated as follows:
The adjusted sub-problem on spanning tree T
min E² (X) =
min
Σ ((,))) +
Σ
(8)
iev
(6J)ET
Then we could use the energy of cach sampled tree to approximate the original energy of the graph:
B(X)
Σ PTK KEK
Σ (...)) - KEV
wisls((rsz55) (GJEET&
E
= (i(ss)) + E X)1,
SEV
where PTg is the probability that Tk is sampled and é(X, X) is the pairwise energy term after reweighted. And the second term of the right-hand side is the expectation of the adjustment pairwise term according to the distribution of the random uniform spanning trees. By Lemma [ we could make the merged MAP problem is actually an approximation of the original problem. We use a toy example to show the necessity of weight adjustment in Appendix
After adjustment, the incoming message of vertex from vertex now becomes My. (Ai
Then equation Jon certain tree T now becomes
pd (x) = 77 exp( expppx== (X)) = 7T exp
- NEV
0,(())) -
E (6))TT
(10)
Now we could approximate the joint distribution via:
f(X)= = II Pr. (X) kgk
1 exp Z
Σ
Σ 0((z.) +
Σ mi.00)((nn (6J)
(II)
After applying belief propagation sampled trees, we could obtain the marginals pr, (ax(X²) (xx]) on each tree. They are subsequently merged to approximate the true marginal distribution. For the initial marginals, without any specification, we will assume they are all uniform. To obtain the estimations, we do the follow- ing procedure to merge the marginals of each variables on each trees since the summation in energy is the multiplication when calculating probability:
p(z, (x(x)) & II (PT: (o.)). REA
(12)
We employed two methods, Gibbs sampling (Geman & Geman 1984). and Greedy selection, to assign values to each of the variables based on the estimation of the marginal distributions as in Line 6 and 7 in Algorithm [ These methods are implemented in modules named GibbeSampler and GreedySelector. The GibbsSampler samples a label for each variable based the estimated marginal distribution, this label configuration is called x XCibb while the SelectSSe selects the label with the highest value from the estimated marginal distri- bution, this label configuration is called Greedy. Since the sampling procedure will introduce uncertainty and greedy selection nodes doesn't I mean the combination is the best, we will keep recording the best configura- tion so far X theat, during the itcrations. We will update this configuration if some of the configuration given by the two modules yields the lowest energy so far Fiemp: When the algorithm terminate, the hest configuration that is found would be the final output.
Complexity Analysis can be found in Appendix
Lemma 1. Given a uniform spanning tree distribution Q(T) and the corresponding edge appearance proba- bilities (p.IV((i)) E E), when [X]] = [T), the approximation energy Eq. 9 Hadd the original energy coincide.
Since acquiring the true tree selection probability pr is intractable in practice, we use Monte Carlo Approxi- mation to do the approximation when implementing the algorithm, by Lemma 2 Lemma holds.
you can see the condition in
Lemma 2. By applying the Monte Carlo Approximation, the expectation of the approximation is the original energy.
BTAMN(T)
Σ Σ
wh (inbs,(anne)))
-0(a))) Σ (1)())))))))
(13)
[K]
xex
KEK (NJ)TT,
vex
5

---

Published as a conference paper at ICLR 2026
Theorem 1. Given spanning distribution (2(T) and the corresponding edge appearance probability
(og (i, }.. the following evvor bound of the approximation energy Eq. equation 9 holds with prob- ability at least - 6.
[E(X) E(X)IS
Σ (L,))E
Pg Pis
(14)
K
v8
When
[K]
Σ
(xs,,)))))
1- Pdj -
(15)
8m12
(K.))E
Pij
we have ((|E(X)- - E(X) 2 7) < 8.
The proof of Lemma
1 Lemma and Theorem 1 can be found in Appendix [A]an Appendix C respectively.
is obvious that due to the term graph is sparse.
(--tt) we can achieve good quality results with only a few trees when the Pij
The error bound exhibits an inverse relationship with the edge selection probability Paj. As Pay approaches smaller values, the factor (L=ge) grows significantly, leading to a looser error bound. This relationship pro- vides insight into the performance disparity between sparse and dense graphs. sparse graphs, each edge typically has a higher probability of being included in spanning tree, since fewer alternative paths exist be- tween vertices. Conversely. in dense graphs, the abundance of potential paths results in lower individual edge selection probabilities. Consequently, when Pij is larger (as in spanse graphs), the term (1=P)) remains rela- tively small, yielding tighter error bound and better estimation accuracy. Moreover, this theoretical analysis aligns with our empirical observations of superior performance on sparse graphs. This mathematical relation- ship explains why our method naturally performs better on sparse structures, where the higher edge selection probabilities contribute to more reliable estimates.
4.2 RANDOM UNIFORM SPANNING TREE
The key idea behind our algorithm is utilizing the partial information contained inside the original graphs. To uniformly sample random spanning tree from the given graph, employed the widely used Wilson's algorithm (Wilson 1996). This algorithm. based on random walks and removal, ensures the uniformity of the resulting spanning tree selection. In general, the time complexity of Wilson's 's algorithm is O(N*). ). It could be significant when the size of the graph increases. Using methods such as Depth- First Search (DFS) would be more efficient, given the time complexity of O(M + N). However, these methods make it challenging identify the distribution the trees. As result, we cannot adjust the messages based on the edge selection probabilities. Therefore, one the future trials is to incorporate advanced (approximate) sampling procedures such as Schild (201) to reduce the time complexity.
4.3 EFFECTIVE RESISTANCE
employ algorithms approximating effective resistance obtain Pay. Effective resistance used in electrical network analysis and graph theory to measure the resistance between two vertices in graph (Lyons Peres 2016) how difficult it is for current to flow between two points in network. The terminology of effective resistance originates from the following observation: Given the resistance all edges, if one removes all vertices of G except ts and replaces the whole network with a resistance of resistor Reff(s f) between (s, t). then, the energy (and the potential difference) of all electrical flows between (s, f) remains invariant.
There is strong connection between P.j and the corresponding effective resistance. By applying Kirchhoff's effective resistance formula (Lyons & Peres 2016), we can establish the following lemma.
Lemma 3 ( (Madry et al. 2014 (i,5) E E, Pig j) T.T
Doyle & Snell 2000). For any unweighted graph G (V,E), any edge
= Ref((i.))
As such, we resort efficient alternative algorithm approximating effective resistance (Vos 2016 for pij- In our research, we only need the appearance probabilities of all the edges to calculate the weight the pairwise energies, so we only need to calculate the effective resistance between directly connected nodes instead of do the calculation between all the nodes. Note, the value Reff j) represents the probability of sampling edge (i,5) when reaching node or node in Wilson's 's algorithm. In this sense, it is unnecessary to directly reweight the pairwise terms dy. More details in Appendix

---

Published as a conference paper at ICLR 2026
Patts
Grid
15
385
hapand
ER
Squared
Cellular
Seation
Bender
Foda
Scuardd
Cell
Figure 2: Results Grid, Erdōs-Rényi (ER), Cellular, and Cell graph types (rows) with Potts, Absolute difference (Abs), and Squared difference energies. Each plot shows energy F(x(0) vs. iterations. Blue: LBP, orange: TRBP, green: SPT. The error bars show the standard deviation of each algorithm. Note: LBP and TRBP curves sometimes overlap due to minimal differences.
EXPERIMENTS
We present comprehensive investigation into the performance of the variational inference method Mcan- field and three belief-based inference algorithms: the Loopy Belief Propagation algorithm (LBP), the Tree- reweighted Belief Propagation algorithm (TRBP), and novel sampling algorithm proposed in this study, ferred as SPT. experiments
validate the arguments presented the previous sections lish the superiority of our proposed algorithm over LBP and TRBP. Performance evaluations are conducted on synthetic problems with diverse graph structures, encompassing energy functions such as the square function Ogy = a(x; =²)². absolute difference function Og a i2 zy| and Potts function 0.j- a(æ; 2ạ) + B. and 0.1.
estab-
where and are constant penalty terms. this section, we use
Experiments involve grid-based and cell-based structures, as well as Erdōs-Rémp Rényi (ER) random graphs The LBP algorithm and TRBP algorithm are from Kappes et al. (2015): Andres et al. (2012); Maxwell Forbes (2017). TRBP here is the refined version of TRW-based algorithms. The mean-field algorithm we used is from Wang et al. (2022) and the mapMAP solver is from Thuerck al. (2016). Furthermore, the applicability of algonthm on worldworld MRF inference datascts is demonstrated.
5.1 SYNTHETICC PROBLEMS
We first conduct experiments on synthetic problem instances. To test the applicability of the proposed method in wide spectrum of settings, we test four types of graph topologies: Grid, Erdös-Rényi (ER). Cellular, and Cell. There illustrative figures in Appendix 0.1 visualizing typical layouts of cell graphs (Fig. a)) and cellular graphs (Fig. b)). All the experimental results are in Fig. Concrete settings are as follows.
Grid. We first test these algorithms on 70 70 grids with 4900 nodes, and each random node has 5 possible discrete labels to select. In addition, each label is attached to an explicit energy generated randomly and the energy e (0. 1). For the setting of LBP and TRBP, we set the maximum round of iterations to 40 rounds. The damping factor of both of them is 0.8 since is the hest configuration the experiments. For our SPT, the maximum round of iterations set 20 and the damping factor O. run the experiment for 10 different test cases and the final result is the average result over these cases.
could from the results of
Erdös-Ree Réníi. Random MRF instances under Erdós-Rénn Rényi setting comprise 2,500 nodes, with an average degree of 12. The test cases configured with different energy functions, and all the unary energy terms are generated randomly. order show the inference ability clearly, attach possihle labels for each node
7

---

Published as a conference paper at ICLR 2026
Table I: Results on the UAI dataset. Numbers are the obtained energy values. Best in bold.
#NODES/AEDGES
PROTEINFOLDING..1
400/7160
1.041
7.11675t+07
7,542246=07
8.546200-07
7,496390+07
PROTFINFoi DING_I2
250/1
5852,2148
GRIDS_19
1600/3200
10613.0645
7053.72
60566.45
7523.18
6275.5 56
GRIDS_2
1600/3200
3.
2.5577F+08
2.568528+08
3.33740F-08
3.22289F=005
GRIDS_24
1600/312 120
3.8874E+08
3.06505E+D8
3.01668E=+08
3.53902E-08
3.09172E+08
1600/3120
6113
5476.03
GRIDS_21 _26
400/800
818490.187 187
792987
556629
794293
759351.5
1600/3120
3.892E+06
2.062771=+06
2.14945E+06
3.54505E+06
3.41471E+06
GRIDS 33
400/760
1044407.066
567339
663905
817746
809344
228/624
SEGMENTATION. 12
231/625
805 6727
735.259
735.259
124.025
611.347
13
225/607
785. 7468
726. 144
146.144
7689, 666
596,606
SEGMENTATION.
231/632
803.2781
742.241
742.241
684,055
629.95
229/622
314.47
362.61
362.61
277.087
191.924
SEGMENTATION,
228/610
776.0317
720.009
720.009
647.788
$78.114
17
225/612
166.1681
392.83
370.852
296.107
187.432
SEGMENTATION,
233/647
820.7836
782.282
782.282
662.122
595.11
SEGMENTATION 19
228/624
79% 2877
742.197
742.197
660.399
624.649
SEGMENTATION 20
2321635
578.8339
373.14
371.839
287.187
196.558
this part. The damping factors are set 0 this part of experiment. The maximum iterations, including our SPT algorithm are all set to 40. The number trees used by SPT for the tests is 20.
Cellular & Cell. In addition to these two most common type of networks. We then run the tests on cellular and cell networks which are widely applied in communication networks. Each of the cellular networks has 4,998 nodes and 7,398 edges, the average degree is about 2.96. Each of the cell networks has 4,900 nodes and 14,421 edges, the average degree about 5.89. The other settings are as same we used the experiments on Erdös- Erdös-Rényi
Rényi graphs.
The results are displayed in Fig. These charts show our algorithm effectively handles various energy functions on graphs with specific local structures and randomly generated graphs. For grid, cellular, and cell graphs (all locally and sparsely connected), our algorithm outperforms both LBP, TRBP and mapMAP final energy and iteration efficiency. These structures commonly appear wireless communication and traffic control industries, where strategically placed interconnected devices create potential interference patterns similar to our experimental setup. Our algorithm performs consistently well on completely randomly generated graphs, even when graph density is approximately twice that of cellular networks. In addition, the error hars indicate that these algorithms remain highly stable after convergence, with SPT algorithm exhibiting particularly robust performance. However, it slightly underperforms compared to L.PP and TRBP when using absolute difference as the energy function. This occurs because when different choices have similar costs, the algorithm may converge to sub-optimal positions.
Results Analysis.
5.2 UAI INFERENCE COMPETITION
We extend evaluation to factor graphs from the 2022 UAI Inference Competition's 's MAP tasks"] Table com- pares Mean-field, LBP, TRBP, mapMAP, and SPT method, reporting final energy values. Algorithm settings match those used on synthetic problems, except SPT uses trees for estimation achieves competitive performance comparable to LBP and TRBP, with significant improvements on various segmentation tasks. On segmentation instances, SPT outperforms all other methods. These instances have graph structures similar to those in the synthetic experiments and share the same Potts model characteristies. For ProteinFolding 11 and Grid cases, algorithm's performance matches LBP and TRBP, consistent with findings from Grid graph experiments ProteinFolding. 12, Segmentation. 14 and Grids_30 instances are shown in Appendix 0.2 Segmentation class instance since they all share similar graph structure.
section. Overall, SPT
the synthetic problem set. Graph structures for ProteinFolding, We display only one
5.3 REAL-WORLD PCI PROBLEM OF 5G NETWORKS
PCI (Physical Cell Identity) uniquely identifies cells in LTE and 5G networks. We evaluate using internal PCI data transformed into pairwise MRFs for MAP inference. Appendix details the MIP formulation and transfommtion process. We evaluate our algorithm on four internal real industry-level PC/ instances compared to LBP and TRBP, using final energy (corresponding to the objective function in equation 52) as our comparison standard. Results appear in Table 2 with instance topologics in Appendix 0.3 When MAP estimation is formulated as integer programming, problem size increases significantly, as shown in the table. Both LBP and SPT yield identical results, but algorithm achieves superior performance compare all the baselines, with
https: www. auai wr.. uai 2022 uai 2022__coppppp in
8

---

Published as a conference paper at ICLR 2026
Table 2: Results on real PCI instances. Numbers are obtained energy values. Best in bold.
GRAAPE
PVAR/ACON
#Nooes/AFooss
LRP
TRBP
MAPMAP
PCLINSTANCE.1 955/2496
30/165
3:72662E+08
3.726626+08
101259.1
84382.6 186848 214875
PCLINSTANCE,2
1588/4409
40/31
3.72704m-008
3.72704m-608
PCLINSTANCE.3
60/1522 65713/195287
17684/52673
0.3034688
0.303468
0.295245 0.299465
PCI INSTANCE 4
286/10505
0.251074
0,751074
0.725626
0.552074
Table 3: Inference time results the UAI dataset.
GRAPH
#NODES/HEDGES
Mean field
LBP
TRBP
mupMAP
SPT
SPT Ply Computation Time
ProdeinFolding II
400/7160
0.0343s
0.8802s
0.9671s
0.0400s
13,2087s
1.669s
ProteinFolding.1 12
250/1848
2.2345x
13.4593s
15.4034s
0.1060s
15,9054s
0.4481s
Grids, 19
160033200
0.1503s
3.3206s
3.6675s
0.0930s
112.94,0s
89.1308s
Grids 21
1600/3200
0.1598s
3.3087s
3.6697s
0.1410s
137.6740s
89.1060s
Grids 24
160031200
0.1423s
3,2266s
3,5659%
0.0460x
142.9210s
89,0508s
Grids 25
16003120
0.1337s
3,0990s
3,4754s
0.07 10s
119.1980s
90.8171s
Grids_26
400/800
0.0317s
0.8243s
0.9149%
0.0480s
12.3774s
1.6195s
Grids 27
16003120
0.1375s
3,2234s
3,5731s
0,1050s
132,4540s
89.121
Grids_30
400/700
0.0313s
0.7504s
0.8320s
0.0400s
48677
66666s
Segmentation_11
228/624
0,2086s
24.85 19
29 67.66
0.0240s
12.21924
0,3664s
Segmentation_12
23 1/625
0.0212s
1.8221s
0.8991s
0.0180s
3. 3.7285s
0.3779s
Segmentation_
225/607
0.0208
0.6320s
0.7084s
0.0270x
3. 3.0541s
0.3475x
Segmentation 14
231/632
0.7520%
0,8248s
3.63655
0.3756s
Segmentation 15
229/622
0.1961
24.7640%
29.4172s
0.0230N
9.8776s
0.3650s
Segmentation 16
228/610
0.2110s
0,8860s
0.0260x
3.5368%
Segmentation 17
225/612
0,1895$
25 8389
30.3104b
0,0220x
9.6708s
0,3482s
Segmentation.18
235/647
0.745%
3.6849:
Segmentation 19
228/624
0.2210s
0,7255s
0,8071s
0.0230s
3.3923s
0.3606s
Segmentation_25
232/635
0.3630s
26.8320s
31.4758s
0.0230s
10.7515s
0.3682s
substantial energy reductions for PCLINSTANCE,1 and PCLINSTANCE.2. The inference time are shown in Table. 5 in Appendix.
5.4 MORE ANALYSIS
To investigate the impact of various factors, examine the following aspects: the number of trees used, the number iterations, stopping criteria, other sub-graph structures, and impact of sparsity. "The main part of the result figures in this section is displayed in Fig.
Number of trees. We evaluated our algorithm's 's performance on the PCLINSTANCE model using 1, 5, 20, 80, 160 spanning trees. After 10 iterations per configuration, the final energy values revealed V-shaped curve, with optimal performance at spanning trees (Fig. 3a This suggests that for complex graphs, approximately 5- 10 spanning trees provide sufficient structure representation without redundant information. demonstrated in Appendix H for trivial MRFs with known optimal energies, increasing the number of trees can further minimize the optimality gap.
Number of iterations & Stopping criterion. Fig. 3b shows energy curves for algorithm on the PCI INSTANCE 1 dataset using 20 spanning trees over 40 iterations. The optimal configuration is achieved iteration 19 and persists until the end. Notably, the provisional best configuration remains stahle during several periods within the first 20 iterations. Common early stopping criteria based on monitoring consecutive iterations without improvement (marked by red, green, and yellow dotted lines at thresholds of 3, 5, and 10 iterations) would fail to capture the best solution found at iteration 19. Given algorithm's efficiency, recommend running for the maximum number of iterations in practice.
Inference Time. In Table we show both overall inference time and edge selection probability calculation time. For complex problems like "Segmmenationn 11", all methods require more computation time, but SPT demonstrates more stable performance and faster convergence. Our analysis identifies calculating edge selec- tion probabilities as the main computational bottleneck, especially for larger graphs. Developing more efficient probability estimation methods an important future research direction. The algorithm could be accelerated through parallelization, with details available in Appendix [
Other sub-graph structures. We evaluated several structural alternatives: chains, random trees (covering 75% of nodes), and random walks (1600 steps for greater node coverage). Testing details are in Appendix. G Tests used 1600-node grids with 10-16 possible states per node and square function pairwise energy without unary terms. Unlike our fixed-tree SPT approach, alternative structures were resampled each iteration since they don't 't guarantee full node coverage. Running 20 iterations with SPT using 10 trees, Fig. [3 shows SPT achieved superior results with significantly fewer iterations. Random trees and walks delivered acceptable results but required more iterations to converge. Comparison with the tree-coupling approach from Hamze & de Freitas 2004) appears in Appendix

---

Published as a conference paper at ICLR 2026
390
199
252
Samber of Trens
Therad one
Avenge
(a) Energy v.s. tree num-
(b) Energy v.s. iterations
(c) Performance by differ- (d) SPT-LBP gap vs. spar- sity
bers
ent subgraphs
Figure 3: Part of the results for the analysis in Section. 5.4
Impact of sparsity. From Fig 2] our algorithm outperforms LBP and TRBP on both grid and cell structures, locally and sparsely connected MRFs (Fig Appendix (O) and analyze local structure complexity impact, we tested LBP and SPT on graphs used trees,
with larger performance gap denser cell graphs. To evaluate effectiveness
described Appendix These graphs had average degrees of 3.8, 7.6, 11.3, 18.5, and 22.0. with 10-16 states per random variable and nodes linked to random observations. Pairwise energy used the Potts function. Performance comparison used the relative energy gap (equation T6). averaged over 10 trials.
GAP = (EsrT FLBP)/ / ELBP X 100%
(16)
shows that local structures become denser, SPT inereasingly outperforms LBP. This occurs be- loop impacts become significant, making it crucial balance variable values within local graph structures-a strength of our algorithm. shaded areas indicate modest gap variances.
Fig. 3d
Our algorithm also performs effectively on random graphs, especially when they're not highly dense. We conducted similar experiments on ER graphs with 900 nodes, varying average node degrees from 2 to 12 using squared energy functions (as performance with Potts functions is similar). Results in Fig. 3d (orange line) show algorithm performs effectively algorithm achieves satisfactory results on sparse graphs, but as average node degree increases, the performance gap between our algorithm and I.PP increases linearly. Without local structure to leverage, SPT's performance is reduced.
sparse graphs, even without specific graph topologies. The
CONCLUSION
MAP inference MRFs remains persistent challenge. We propose novel, efficient approach for MAP timation locally and sparsely connected MRFs using spanning tree sampling. Our method works by solving problems on individual sampled trees and merging these solutions into configuration. Experiments demonstrate superior performance against strong baselines across diverse settings, with particularly significant improvements on worldworld PCI instances, indicating broad applicability potential.
ACKNOWLEDGMENT
This work was supported by the National Key R&D Program of China under grant 2002900
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of our research findings. we have taken the following comprehensive measures:
Our implementation code has been made publicly available, with the repository link provided at the end of the abstract. This allows other researchers directly access and utilize our algorithm for their own applications verification purposes.
Detailed instructions for setting up and running our code are included the repository documentation. These instructions cover all necessary steps from environment setup to execution of experiments, enabling smooth replication of work.
In Section we have explicitly documented all algorithm settings used in experiments, including pa- rameter configurations optimization choices, and implementation details. These specifications are critical for reproducing our experimental results.
Access information for the UAI Inference Competition datasets used in our evaluation is clearly provided in Section 5.2 This includes source links and preprocessing steps applied to the data before running experiments.
10

---

Published as a conference paper at ICLR 2026
For synthetic experiments, have thoroughly documented instance generation methodology in Sec- tion 5.4 with additional technical details available Appendix This documentation ensures that synthetic test cases can be precisely recreated.
We provide comprehensive instructions for transforming PCI problems from their original Mixed Integer Pro- gramming (MIP) format into the MRF format required by algorithm. This transformation process is crucial for applying method real-world felecommunication network optimization problems.
Through these measures, have ensured that all aspects of our research be independently verified and built upon by the research community.
ETHICS STATEMENT
During the preparation and submission of this paper, we have strictly adhered to the Code of Ethics in scientific research. We ensured proper citation of all relevant work, maintained integrity in experimental procedures, reported results accurately without manipulation, and respected confidentiality of data sources where applica- blc. All authors have contributed substantially this work and approved the final manuscript, with conflicts interest undisclosed.

---

Published as a conference paper at ICLR 2026
REFERENCES
Uai 2022 competition. http:p//aaaacmmee11toooooooooood
Mamta Agiwal, Abhishek Roy, and Navrati Saxena. Next generation 5g wireless networks: A comprehensive
survey. IEEE Communications Surveys & Tutorials, 1833):1117-1655, 2016. doi: 10.1109/C0MST.2016 2532458.
S.M. Aji and R.J. McEliece. The generalized distributive law. IEEE Transactions Information Theory, 46 (2):325 -33,, 2000, doi: 10.1 10.1109/18.8 122794.
B. Andres, T. Beier, and J.H. Kappes. OpenGM: A C++ library for discrete graphical models. CoRR, abs/1206.0111, 2012. http://///arxi org/ abs http://bb//12111111/ 0111
MOSEK ApS. The MOSEK Python Fusion API manual. Version 2025. 2025. URI httph:t/ttcsscs.... mosee.
com/ Ltttssst//yttooouussoo... index htm.
Dhruv Batra, A. C. Gallagher, Devi Parikh, and Tsuhan Chen. Beyond trees: Mrf inference via outer-planae dccomposition. In 2010 IEEE Computer Society Conference Computer Vision and Pottern Recognition, pp. 2496 2503, 2010. doi: 10.1 1L10//CVR.2200055539953
Julian Besag. Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society, Series B (Methodological), 36(2):192-236, 1974. ISSN 00359246. URL lttp::/ URL /www jstor.
brg/stabbee22848B1
Y. Boykov, O. Vekslen, and R. Zabih. Markov random fields with efficient approximations. In Proceedings. 1998 IEEE Computer Society Conference on Computer Vision Pattern Recognition (Cat. No. No.98CB36231), pp. 648 648-655, 1998. doi: 10.11R// 1998.1999.... 698673.
Joseph Bradley and Carlos Guestrin. Learning tree conditional random fields. Proceedings of 27th International Conference on International Conference on Machine Learning, ICML' 10, pp. 127-134, Madi- son, WI, USA, 2010. Omnipress. ISBN 978 605589077.
Nicolò Cesa-Bianche Bianchi, Claudio Gentile, Fabio Vitale, and Giovanni Zappella, Random spanning trees and the prediction of weighted graphs. pp. 175-182, 01 2010.
Clifford and Hammersley. Markov fields on finite graphs and lattices, 1971.
Paul Cuffe and Andrew Keane. Visualizing the electrical structure of power systems. JEEE Systems Journal, 11(3):1810-181,, 2017.
Peter G. Doyle and J. Laurie Snell. Random walks and electric networks, 2000. URL https://arx:
org/ abs m 0001057
Pedro F. Felzenszwalb and Daniel P. Huttenlocher. Efficient belief propagation for early vision. Interna- tional Journal of Computer Vision, 70:41-54, 2004. URL httptts:::aa..eeaaaaae sttp:///aap..eeettcccccccooosss
Corpus ID: 7024655
Brendan Frey and David Mackay, revolution: Belief propagation in graphs with cycles. 08 2002.
Stuart Geman and Donald Geman. Stochastic relaxation, gibbs distributions, and the bayesian restoration of images. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6(6):721-741, 1984.
D.M. Greig, B.T. Porteous, and Allan Seheult. Exact maximum a posteriori estimation for binary images. Journal of the Royal Statisticul Society, Series B, 51:271-279 01 1989. doi: 10.1111/2551-66611119 tb01764.x.
Anna Grim and Pedro Felzenszwalb. Convex combination belief propagation. Applied Mathematics and Computation, 438: 127572, 2023. ISSN 0096-3003. doi: http:///doi.or/11.00000 ame 2022.12772... URL. https:// sci encedi rect com/ sci wwtp///rticieee/eeccee 1/800 03009066003222088
Firas Hamze and Nando de Freitas. From fields to trees. In Proceedings of the 20th Conference Uncertainty Artificial Intelligence, pp. 243-250, 2004.
H. Ishikawa. Exact optimization for markov random fields with convex priors. IEEE Transactions Patiern Analysis and Machine Intelligence, 23(10):1333-1333 2003. doi: 10.1 109/ 1233308.
H. Ishikawa and D. Geiger. Segmentation by grouping junctions. In Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No. No.98CC336231),, pp. 125-131, 1998. doi: 10.1 109/CVPR. 1998.698988.....
12

---

Published as a conference paper at ICLR 2026
JörgHI Kappes. Bjoern Andres, FredA. Hamprecht, Christoph Schnörr, Sebastian Nowozin, Dhruv Batra, Sung- woong Kim, BerhardX.. Kausler, Thorben Kröger, Jan Lellmann, Nikos Komodakis, Bogdan Savehynskyy, and Carsten Rother. A comparative study of modern inference techniques for structured discrete energy min- imization problems. International Journal of Computer Vision, 115(2):155 1544 2015. ISSN 0920-5691. doi: 10. 1007/s1 120--01-0000
Alec Kirkley, George T. Cantwell, and M. E. J. Newman, Belief propagation for networks with loops. Science Advances, 7(17)cabf1211, 2021. doi: 10.1126/siadvvabf1211. [
doi/abs www.11116/cccccca www.adi.vvaii.......
V. Kolmogorov. Convergent Tree-Reweighted Message Passing for Energy Minimization. IEFF Transac- tions on Pattern Analysis and Machine Intelligence, 28 (6110):168--583, October 2006. ISSN 0162-8828. 2160-9292,
doi: 10.1 10110/9AM...20.200 URL.
16 167755 75157
Nikos Komodakis, Nikos Paragios, and Georgios Tziritas. Mrf optimization via dual decomposition: Message- passing revisited. pp. 1-8, 11 2007. ISBN 978-1-4244-16111 doi: 10.1 1..1100/..2000...... 44088999
Arun Kumar, Aniruddha A. Dutta, Nayan Jain, and Sanjay K. Dhurandher. Mrfbp: Markov random field-driven spatial entropy-based routing protocol in opportunistic networks. International Journal of Communication Systems, 35(1). January 2022. ISSN 1074-5351. doi: 10. 10.1d///ac.50118 Publisher Copyright: @ 2021 John
Wiley & Sons Ltd.
Sanjiv Kumar, Jonas August, and Martial Hebert. Exploiting inference for approximate parameter learning in discriminative fields: An empirical study. In Anand Rangarajan, Baba Vemuri, and Alan L. Yuille (eds.), En- ergy Minimization Methods in Computer Vision and Puttern Recognition, pp. 153-168. Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. ISBN 978-3-540-32098-2
Yixin Li, Chen Li, Xiaoyan Li, Kai Wang, Md Mamunur Rahaman, Changhao Sun, Hao Chen, Xinran Wu, Hong Zhang, and Qian Wang. A comprehensive review of markov random field and conditional random field approaches in pathology image analysis. Archives of Computational Methods in Engineering. 29:609 639, 2020. URLLnEtss: /api. semant lescholase
221995730
Zhiliang Liu and Zengzhi Zou. Analysis of network topology and deployment mode of Sg wireless ac- cess network. Computer Communications, 160:34 42, 2020. ISSN 0140-3664. doi: https://doi.orr// 10.1016/j.comcom. 2020.05 .5.55. URL/tttss://wwe /www. sciencedi wwt.:/o///ccc/e.ec wow////iennc//rrccc......
D11/801403664203065X
Russell Lyons and Yuval Peres. Probability on Trees and Networks, volume 42 of Cambridge Series Statisti- cal and Probabilistic Mathematics. Cambridge University Press, New York, 2016. ISBN 978-1-107-16015. 6.
Aleksander Madry, Damian Straszak, and Jakub Tarnawski. Fast generation of random spanning trees and the effective resistance metric. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Sympo- sium on Discrete Algorithms. Society for Industrial and Applied Mathematics, December 2014. doi: 10. 19117//199711111777700111
URL htRpthtp://dx.... doi. 1137// 9781 973730 134
Sadia Majeed, Muhammad Uzair, Usman Qamar, and Aftab Farooq, Social network analysis visualization tools: comparative review. In 2020 IEEE 23rd International Multitopic Conference (INMIC), pp. 1-6, 2020.
Yan Wong. Maxwell Forbes. factorrorg...h. http://s//ghhh...oo//o/ohhoraaaa 2017.
Andrea Montanari and Tommaso Rizzo. How to compute loop corrections to the bethe approximation. Journal of Statistical Mechanics: Theory and Experiment, 2005:P1001 1 P10011, 2005. URI. https://app..
semant i cscho wtwcchcla.rrrrroooo worg//orruuuaooooooooooooooooroe ID: 1433786
Kevin Murphy, Yair Weiss, and Michael I. Jordan. Loopy belief propagation for approximate inference: An empirical study, 2013.
Judea Pearl. Reverend bayes on inference engines: a distributed hierarchical approach. Proceedings of the Second AAAI Conference on Artificial Intelligence, AAAI'82, pp. 133-136. AAAI Press, 1982.
Judea Pearl. Chapter 4 - belief updating by network propagation. In Judea Pearl (ed.), Probabilistic Reasoning
in Intelligent Systems, pp. 143 237. Morgan Kaufmann, San Francisco (CA), 1988, ISBN 978-0 07788-0088-00 0010080--11100011 051489. 5. doi: https://doi.org/10.. http://wwww.....1...///000000000
https: www aci encedi rect.
com/ i htte///rrricccee/111///890001111
13

---

Published as a conference paper at ICLR 2026
Patrick Pletscher, Cheng Soon Ong, and Joachim Buhmann. Spanning approximations for conditional random fields. David van Dyk and Max Welling (eds.), Proceedings of the Twelfth International Confer- ence on Artificial Intelligence and Statistics, volume 5 of Proceedings of Machine Learning Research, pp. 408 415, Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA. 16-18 Apr 2009. PMLR. URL https: : http:::/prcceeeeeee http///cceeedng...ee. mwr. httppngw.........//ppp. https/////bpeetceeeeeeeee html
S. Roy and IJJ. Cox. A maximum-flow formulation of the n-camera stereo correspondence problem. In Sixth International Conference Computer Vision (IEEE Cat. No.98CH36271), pp. 492 1998. doi: 10. 1109/CCCV 1998. 710763.
Masaki Saito, Takayuki Okatani, and Koichiro Deguchi. Application of the mean field methods mrf opti- mization computer vision. 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1680-1687, 2012. doi: 10. (00///VVR2202.2247775555
Vladimir Savie and Santiago Zazo. Nonparametric belief propagation based on spanning trees cooperative localization in wireless sensor networks. In 2010 IEEE 72nd Vehicular Technology Conference - Fall, pp. 1-5, 2010. doi: 10. 1T.1100/EEEEFF2200005555111
Aaron Schild. An almost-lineat time algorithm for uniform random spanning tree generation. In Proceedings of the 50th Annual ACM SIGACT Sympusium Theory of Computing, STOC 2018, pp. 214-227, New York, NY. USA, 2018. Association for Computing Machinery. ISBN 978 9783450355599 doi: 10.1 10/1145/3188745.
3188852. URL https://doi. 2ttg//...115/313333 1.155318888 3188852
Dmitrij Schlesinger and BORIS FLACH. Transforming arbitrary minsum problem into binary 01 2006.
Alexei N. Skurikhin. Learning tree-structured approximations for conditional random fields. In 2014 IEEE Applied Imagery Pattern Recognition Workshop (AIPR), pp. 1-8, 2014. doi:
Wenkang Su, Jiangqun Ni, Xianglei Hu, and Jessica Fridrich. Image steganography with symmetric embed- ding using gaussian markov random field model. IEFF Transactions on Circuits and Systems for Video Technology, 10011100,,, 2021. doi: 10.1 101100/TTT.222000000000 122.
Jian Sun, Heung- Yeung Shum, and Nan-Ning Zheng. Stereo matching using belief propagation, In Proceedings of the 7th European Conference on Computer Vision-Part II, ECCV '02, 510-524, Berlin, Heidelberg, 2002. Poringer-Verlagg ISBN 3540437444.
Martin Szummer, Pushmeet Kohli, and Derek Hoiem. Learning crfs using graph cuts. volume 5303, 582 595, 10 2008. ISBN 978-3-540 3-540-88668----33- doi: 00.1007/97-3--400 10000-8888-4445
Daniel Thuerck, Michael Waechter, Sven Widmer. Max von Buelow, Patrick Seemann, Mare E. Pfetsch, and Michael Goesele. A fast, massively parallel solver for large. irregular pairwise Markov random fields. In Proceedings of High Performance Graphics 2016, 2016.
Vaya Sapobi Samui Vos. Methods for determining the effective resistance. Master's thesis, Mathematisch Instituut Universiteit Leiden, 2016.
M.J. Wainwright, T.S. Jaakkola, and A.S. Willsky. Map estimation via agreement on trees: message-passing and lincar programming. IEEE Transactions on Information Theory, 51(11):397-3377, 2005. doi: 10.
1109/TIT.2005.8660 8556938.....8.8...
Chaohui Wang, Nikos Komodakis, and Nikos Paragios. Markov random field modeling, inference & learning in computer vision & image understanding: A survey. Computer Vision and Image Understanding. 117
(11):1600-1677, 2013. ISSN 1077-3142. doi: http://bbb.oom//000.0oocc.......
2013.....0000..0.000.0 URI. https:
www. www.wseiiennneee..ccccm.m.. www.e///ccen.eer..ecoommmm htt.://cw........eee......eeeeea
Lihao Wang, Yi Zhou, Yiqun Wang, Xiaoqing Zheng, Xuanjing Huang, and Hao Zhou. Regularized molecular conformation fields. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad-
vances Neural Information Processing Systems, 2022. URL https:://operreview
1d=7XCF XnG8nGS 3d=7XCFxn68nG9
Weiss and W.T. Freeman. On the optimality of solutions the max- propeatpnoo algorithm in arbitrary graphs. IEEE Transactions on Information 472))33677 2001. doi: 10.1 910555.
Wim Wiegerinck and Tom Heskes.
Fractional belief propagation. In S. Becker, S. Thrun, and K. Obermayer (eds.), Advances in Neural Information Processing Systems, volume 15. MIT Press, 2002. htw.:ttttst///eettt htwpopoccpp.//ooooeeeeeee. ngs. neurips.. cc/ wwpppppr_ppppeeeeeeeeeeeeeee f wwtp//appr///aae 2200p/ 1e/ 35536554a37d5330033ae Bdec
14

---

Published as a conference paper at ICLR 2026
David Bruce Wilson. Generating random spanning
quickly than the time. In Symposium on the Theory of Computing, 1996. URL http:///ggp...eet.tt..oooooooooa /tt.
980190080
Yongji Wu, Defu Lian. Yiheng Xu, Le Wu, and Enhong Chen. Graph convolutional networks with markoy random field reasoning for social spammer detection. Proceedings of the AAAI Conference on Artificial Intelligence, 14001):1054-1011, Apr. 2020. doi: 10. 5555
URL httphhttssssssaatt
Bingbing Xu, Huawei Shen, Bingjie Sun, Rong An, Qi Cao, and Xueqi Cheng. Towards consumer loan fraud detection: Graph neural networks with role-constrained conditional random field. Proceedings of the AAAI Conference Artificial Intelligence, 35(5)44537-4545, May 2021a. doi: 10. vttp:/aaii.v3..11.5.. URL
httts://cjs.eet .awpaaio.r/////////eeeeee http://mmee.pppp..///////aaclc//
6582
Zhiwei Xu, Thalaiyasingam Ajanthan, and Richard Hartley. Fast and differentiable message passing pairwise markov random fields. In Hiroshi Ishikawa, Cheng-Lin Liu, Tomas Pajdla, and Jianbo Shi (eds.), Computer Vision - ACCV 2020, pp. 523-540, Cham, 2021b. Springer International Publishing. ISBN 978-3-030- 69535-4.
Tingman Yan, Xilian Yang, Genke Yang, and Qunfei Zhao. Hierarchical belief propagation on image seg- mentation pyramid. IEEE Trunsactions Image Processing. 32:4432-4444 44443224444., 2023, doi: 10.1109/TIP.223. 3299192.
Jonathan S. Yedidia, William I. Freeman, and Yair Weiss. Understanding Belief Propagation and Its Gen- eralizations, pp. 239-269) Morgan Kaufmann Publishers Inc., San Francisco. CA, USA, 2003. ISBN 1558608117.
J.S. Yedidia, W.T. Freeman, and Yair Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. Information Theory, IEEE Transactions on, 51:2282 2312, 2005. doi: 10.1109/ TIT:2005 850085.
Elkafi Hassini Yunfei Ma. Amir Amiri Saiedeh Razavi. Transportation data visualization with a on freight: a literature review. Transportation Planning and Technology, 45(4):358 401, 2022.
Zhang, mean field theory em procedures blind markov random field image restoration. JEEE Transactions on Image Processing, 2(1):27 40, 1993. doi: 10.1109/83.10863.
Zhang G.G. Hanauer. The application mean field theory to image motion estimation. IEEE Trans- actions on Image Processing, 4(1):19-33) 1995, doi: 10.1 109/8833333....6
15

---

Published as a conference paper at ICLR 2026
A PROOF OF LEMMA I
Lemma 1. Given a uniform spanning tree distribution ((T) and the corresponding edge appearance proba-
bilities (P.)lV(L.)) E E), when [C] = [T), the approximation energy Eq. Pand the original energy coincide.
Proof.
When |C| = |T),
É(X) Σ (z(m.)
E
([Tel(i.)) Th, Thi K3H 01
Pig
VEV
(U)EES
(17)
Σ (1r)))
+
Σ (15(:;,
which precisely the original energy.
B PROOF OF LEMMA. 2
Lemma 2. By applying the Monte Carlo Approximation, the expectation of the approximation is original energy.
BIAAR(T) Σ
(1.)))) +
Σ Σ KEK (6:5)ET,
wis ((30,)(21
Σ (xx)) + rex
Σ (1)())))))))
(13)
[C
VeN
Proof. Since the unary term (2:)) included in all spanning trees, we only need to prove the pairwise expectation identical to original pairwise energy term.
[C
Σ
ETTT
Σ
W (r
(18)
((J)ET
(1
Since each tree sampling uniformly and independently
K
R
BI
Σ
wiy0 (ishi)(11,
(19)
(1SD)T
[K]
Br
Σ wisBis(anns)
(20)
K
(L.))TT
Er
(21)
(KO)ET
Here we use Ey to denote Er Introduce indicator variables:
11 edge (I.j) spanning tree Tk
(22)
(c,)
otherwise
We have ((((()) Pij.
16

---

Published as a conference paper at ICLR 2026
Then,
Bx
(23)
(6J)ET
Fr
Σ
Wig Meples)
(24)
(bJ)EE
Σ WiyEr (1,11)0))
(25)
(NJ)E
1 Pij
(26)
(BJEE
Σ
(2((2112g)
(27)
(N.)EE
Therefore, you could see that the expectation of the approximation is the original energy function.
C PROOF OF THEOREM 1
Theorem 1. Given spanning distribution (2(T) and the corresponding edge appearance probability (py (i. 8). the following error bound of the approximation energy Eq. equation 9 holds with prob- ability at least 6.
[F(X) F(X)IS
Σ (FA)EE
03 (x),
Pij
(14)
Pij
When
1 Σ
1 pij )
|C] 2 5n1²
(15)
Pi
(FJ))E
we have P(IE(X)-B(X)) n) 8.
Proof. Given
E(X) Σ ((a)+)++++)))) +
Σ 0lg(21,)))
(28)
(N,E)
B(X) Σ
Σ
(29)
K
IEX
KEK (1,))C
We have
AE(X) = E(X) - E(X)
(30)
= 1 Σ Σ
w))0ts(mi - Σ 25))
(31)
(TJ)EE
(.3)
Introduce indicator variables:
(k) (.,)
if edge (i.j) is in spanning tree Tk
(32)
0
otherwise
Then the error hecomes:
AE =
Σ
( (K) wy f, (x,, z.)).
(33)
|KT
(i,))
Now define the Per-Edge error A E.g. Then
AE(X) Σ AEG
(34)
(6.))
17

---

Published as a conference paper at ICLR 2026
Define random variable /// (1),)) way (12,, Then,
A
Σ
AZ
(35)
K
kE|K!
Since |11,,11 = Pcs
1 1 (B w.y - 1) 1)0,,
(36)
(piwes (21,
(37)
(38)
Then,
Var Var (wis (ILL, x; ))3 pts p())
(39)
Var 2,5 ( 0ey xz)) pul(1 - pis)
(40)
Pij
Var[AFis] Var (
(41)
[C]]
Var(AF(X)] = E Var(AFig]
(42)
(6,)EE
By Chebyshev's Inequality.
P(IEE(X) 2 1) Var[AE(X)]
(43)
17?
0g (zi, xz) (1 Pis)
Σ (S,)CE
(44)
K
Pij
To ensure that the probability of the exceeding yj. less than equal to 8,
(z), (1- (1-pis)
pis) Pis
Σ
s 6.
(45)
1C|r1 (L.)EE
Solving for [K],
K.
Σ (F.))
2,)
(1- pu)
(46)
bn
Pis
Then, the error bound for the adjusted energy approximation E(X jis,
0Z (2t, m.) (1 - pus)
AF(X) S
Σ
(47)
Pis
48
(E,)EE
This bound holds with probability at least 1
D COMPLEXITY ANALYSIS
The algorithm consists of three parts: calculating the effective resistance, sampling spanning trees, and applying belief propagation on the spanning trees. Generally, O(MNN). ). For sparse graphs, the factor M can be considered negligible coefficient. However, in scenarios involving large and complex graphs, the computational complexity of calculating the probability matrix be- comes dominant relative to other operations. This computational burden represents the primary limitation for the broader application of our proposed method.
complexity of computing the effective resistance
18

---

Published as a conference paper at ICLR 2026
For the second step, the time complexity depends the chosen spanning algorithm. In approach. adopt the method proposed in (Wilson 1996), which has a runtime O(N*). discussed in Section. (.2] Depth- First Search (DFS) was proposed as a potential approach to enhance computational efficiency at this stage. However, empirical results indicate that the performance difference between these two sampling methods is relatively modest in practice. This can be attributed to the availability of optimization techniques and the fundamental similarity between random walk-based sampling and DFS-based approaches.
The time complexity of the belief propagation determined by the size the spanning tree, which remains fixed when the graph is constant. Given |Eeee| = N 1, the time complexity becomes O(N). It is worth noting that our algorithm converges rapidly, typically concluding within fewer than 10 iterations in most cases. Assume the average number of dependencies of each node is b, the time complexity of gibbs sampler would he Oiter x Nk). This efficiency allows complexity the algorithm. As a result, the overall time complexity of the algorithm is O(MN3 + N).
disregard the term iter without significantly affecting the
E EFFECTIVE RESISTANCE CALCULATION
The calculation of resistance distance generally follows the procedure outlined in Theorem The main con- tributor to the time complexity of this part is the computation of the Moore-Penross inverse, as we need to the effective resistance on all the edges of the graph.
Theorem 2 (Theorem 2.7 in (Vos 2016). The effective resistance between pair of vertices (i.5) is defined as Reffe., r + 5,, F 3,5, where I = (L | 9)), with 1 denotes the Moore-Penrose inverse, the Laplacian matrix of G. [V] is number of vertices
and the [V] x [V] matrix contain all 1s. Fe. is the (i.j) entry of the Moore-Penrose inverse of the Laplacian matrix.
F COMPARISON TO TREE SAMPLING ALGORITHM
As previously discussed, the Tree Sampling algorithm proposed by |Hamze & de Freitas (2004) is applicable only graphs with specific structures that can be divided into two cycle-free free parts. Under these conditions, the algorithm focuses on solving the MAP estimation problems on grid graphs with observation nodes. The MAP estimate is given by:
min B(X)
min (R..viEv
Σ (2., Σ Oe LEV
(48)
(1))E
here yi is the observation of the node i which is deterministic value and ye, V has the same value range as the 2z, 2 V.
To comprehensively evaluate the performance of our Spanning Tree algorithm and the Tree Sampling algorithm, conducted experiments using grid graphs of varying sizes: 10x10 grids with 100 nodes, 20x20 grids with 400 nodes, and 30x30 grids with 900 nodes. Each node these grids was assigned one of possible labels. The pairwise energy and the energy between variables and their observations were defined using a squared label difference function. Observations were generated randomly for each instances.
For each grid size, repeated the experiment across 10 different random instances to ensure robustness and reliability of the results. Each of these algorithms for 20 iterations. The number of spanning trees used by SPT is 10. As illustrated Fig. 4 our algorithm consistently outperformed Tree Sampling algorithm across all grid sizes. Importantly, the performance gap between the two algorithms remained consistent as the grid size increased.
G GENERATION OF DIFFERENT SUB-GRAPH STRUCTURES
our previous discussions, we proposed using cycle-free structures to decompose the original graph, allowing us to leverage problems that can be solved exactly as approximations for the original problem. In addition to the advantages we outlined earlier, the spanning trees have demonstrated an extraordinary ability to provide more accurate approximations. We have also explored other structural alternatives, including chains, random trees (not necessarily spanning trees), and random structures generated using random walks. To obtain the chains, we used the following procedure: we would start a randomly selected node and then perform a depth-fine first search to traverse the graph and collect the subsequent nodes. When sampling random trees, we would stop the sampling procedure once the number of nodes in the generated tree reached our target threshold. In this process, we allowed an agent to walk along the edges of the graph for certain number of steps. After the agent stopped, the nodes had visited and the edges had traversed were extracted to form the sub-graph.
19

---

Published as a conference paper at ICLR 2026
1700
1600
Energy
SPT
TS
7000
6500
Energy
6000
SPT
5000
4500
16000
15000
Energy
14000
SPT
13000
TS
12000
11000
10000
8
14 18 20
Iteration
Figure 4: Results of SPT and TS synthetic grid problems with squared label difference. The horizontal and vertical axes the figure correspond to #number of iterations and average value of energy E(r v), respectively. From top to bottom, the grid sizes are 10x 10, 20x20, 30x30.
H ERROR GAP ON TRIVIAL MRFs
We conducted additional experiments on MRFs with 64 nodes and increased the number of trees used to 100. We use the optimality gap the evaluation standard. The results are listed in the Table 4 You can see that trees sampled, the inference results converge to point with only occasional fluctuations, and the absolute fluctuation 1. This could be caused by the problem structure where some variable values offer similar energies that are difficult to distinguish, which is characteristic
BP-based methods. Since our method also based on BP, it is inevitable that we encounter the same issue. The calculation of Optimality gap is shown in Eq. 49ich could be found in the user manual of Mosek (ApS) 2025)
Optimality Gap 18(X)- EX)
(49)
I EXAMPLE OF ENERGY WEIGHT ADIUSTMENT
In this section we use toy example to show the importance of weight adjustment when using uniform spanning trees to decompose the original problem. In Fig. [] we show a graph with four nodes and four edges, and we show all of the three spanning of it. Except edge (1, 3), the probabilities of the other edges appear in
20

---

Published as a conference paper at ICLR 2026
Table 4: SPT inference optimality gaps with different number of trees on trivial MRF instances. Numbers are obtained optimality gaps.
GRATH
10 Tanes
mazs
30 mREns
TRGES
50 ranes
60 TRESS
10 TREES
50 TRGES
90 TRESS
100 TAGES
OPT ESERGY
INSTANCE2
64/156
134
INSTANCE_
641124
104
INSTANCE
461116
131
uniform spanning tree are all 5. which means the weights the pairwise energies on these edges are all ş. The probability of cach the being sampled 3. Fig. we using color red denote the edges that have probability of being selected and the color blue to denote the edge that appear in all the uniform spanning
Without loss of generality, we could assume unary energies are all zero. Then we define the pairwise energies as follows. Each random variable has possible states {0, 1}.
1
0
25
1
0
0
0
0
222
333
21
T1
0
4
Now calculate the energy when all the variables at state O. The original energy is E5 0. 142
3 10. If without weight, the energies these would be Fr, (0, 0, 0, 8, (0,0000,,)))) Fry (0, 0, 0) =
Then merging them together by
B(x)
Σ kEK
PTk Σ (1)(2112))
(50)
(i.))TT,
(51)
get the approximation value is which deviates from the original energy.
adjust the pairwise energy using 1/pu- the energies these would be Fr,, (0, 0,0,0
(1 + 3) + = 10, Fr, (0, 0, o, = (1 + 2) + 8.5, Fry (0,0, 0, 0) = )2 + 3) 4 11.5. Then
merging by Eq 2 the approximation is {10 8.5 11.5) 30 which exactly the original energy.
(a) Original Graph
Spanning Tree
(c) Spanning Tree (d) Spanning Tree
Figure 5: Schematic diagrams of spanning trees of graph with cycle.
21

---

Published as a conference paper at ICLR 2026
Table 5: Inference time on PCI instances.
GRAPH
RVAR/ACDS
#Noors/FForrs
SPT
P
955/2496
30/165
0.3592835
0.4417035
0.4055725
PCL 2CCINSTANCE.2
1588/4309
40/311
0.392266
0.6521745
0.434375
PCLINSTANCE.J
17684/52673
80/1522
0. 0.8522678
0.918235
0.7708435
PCI INS INSTANCE
65713/195277
286/10565
2.14094s
6.2118
3.009s
INFERENCE TIME ON PCT INSTANCES
In Table 5 we present the inference times of LBP, TRBP, and our SPT algorithm on the real PCI instances used in Section 5.3 Notably, despite SPT's O(N") time complexity, its inference times these instances fall between those of LBP and TRBP.
K TRANSFORMING MIP PROBLEMS OF PCI INTO MRF PROBLEMS
The Mixed Integer Programming(MIP) format of PCI problems is follows:
min
Σ TiyTui
(52)
(FJ)EE
s.l.
Zmp
(0,1), Vn N
(53)
Σ Zup =
VnEN.
(54)
PEP
Σ
Znpp +
E Zmzp -5 EV E 1,2). PEМ;,
(55)
where is the index for devices, and N is the of these indices. / stands for the possible states of each device. Ma. stands for the possible states set for node nı Leş the cost when given a certain choices of states of device and device j. a.y is the coefficient of the cost in the objective function. There is an (i,j) E means there exists interference between these two devices. In the MIP formulation of the PCI problems, there are three types of constraints. Combining equation 53 and equation [4gtthhe implies that each device must select one state, and only one state can be chosen a given time. The constraint equation 55 indicates that interference occurs between two devices only if they choose specific states. The impact on the entire system determined by the corresponding value of Lij and its coefficient. Since interference always exists, the objective is to minimize its degree.
To transform these problems into MRF problems, equation 53 corresponds to the diserete states of given node. Since only one state can be chosen a time, the constraints equation [53 and equation[54]]a are naturally satisfied. By processing equation [55] we identify edges and their associated energies. If we find Zn,p and Zn,p in the same constraint from equation (3)) we can formulate an edge (i. j). By selecting different values for Zn,p and En,p, can determine the minimum value of Lij that satisfies the constraint. The product of Lig and dg represents the energy for the edge (i,j) under the combination
use equation 54
represent nodes, where each
these two states. When all the states the nodes are fixed, the values become fixed as well. This implies that the objective function is the summation of all the edge energies. Since the PCI problems do not include unary terms, we will neglect them during the transformation process.
edge costs
Example
The original problem is
min I.
Ta,2 2T2.3
s.t.
2np -10,1] 1):
Vn E (1,2,3), p E (1,2,3) Vn (1,2,3)
Σ Znp 1,
F11 221 S L122
213 + 222 < L1,2
812 + 223 S L1,2
221 + 231 < T,2,3
+ 222 1 < L2,3
223 233 S L2,3
(56)
22

---

Published as a conference paper at ICLR 2026
Then the corresponding MRF problem is
min min (1111 + 02,3 25))
(57)
the energy on edge (21, 22) and edge (22,, mz) are as follows:
T2
2's
221
2:2
2/3
231
A32
2:53
211
0
221
212
0
0
1
222
0
0
213
0
0
222
0
L GENERATION OF LOCALLY AND SPARSELY CONNECTED MRFs
We begin by uniformly placing the nodes in 2-dimensional space. Next, we iteratively traverse all the nodes an arbitrary order. each node visited, we identify its k-ncarest neighbors and create edges between them until the required average degree achieved. Once nodes have been visited, the graph construction complete.
M PARALLELIZAATIN
When the size of the graph increases, algorithms still function, but they become time-consuming. This is because the time complexity, we have just analyzed, highly dependent on both N and M (where M related to the number of states n in the Markov chain). Evidently, acquiring comprchensive information about the entire graph would require more than one tree. Such a requirement could result in notable slowdown of our algorithm due the necessity of performing belief propagation on each tree. Nonetheless, the algorithm have introduced have been calculated, both the spanning tree sampling process and the subsequent helief propagation on each sampled tree can be performed independently and in parallel. This adaptability enables us to significantly improve efficiency.
be seamlessly modified for parallel processing. Once the edge selection probabilities
N ITERATION WITH DIFFERENT BATCHES OF SPANNING TREES
Besides using fixed trees perform the estimation, could also generate another batch of conduct the estimation in a new iteration, similar what was done when using different subgraph structures estimation. However, this could be an expensive strategy to adopt. Note the analysis in Appendix [D] where the time complexity of sampling spanning tree is O + N). which could incur significant computational cost as the graph size increases.
To get comprehensive understanding of whether could gain more by spending more time sampling trees and how two strategies would perform with similar time budget, we experimented on 40x40 grid graphs with 1600 nodes. Each random node has 10 to 16 possible states to chaose from, the pairwise energy is determined by square function, and the unary energy is set to zero. For the SPT method using fixed trees, the number of trees is set 20. For the SPT with tree resampling, the number of trees is varied 20). SPT variants are run for 20 iterations.
5, 10, 15,
As shown Fig. energy curves for each setting the SPT methods reveal both the SPT variants with 20 trees achieve the hest and identical results. As the number of trees used per iteration increases, the gain on the final energy decreases, and the improvement rate diminishes quickly. However, the actual time cost of the SPT with fixed trees lies between the SPT with tree resampling using tree and trees and far less than re-sampling 20 trees each iteration. This suggests that, although we could resample trees during iterative process, the additional time spent on this may not be worthwhile.
O INSTANCE TOPOLOGY
0.1 SYNTHETIC PROBLEMS
Fig. 7 illustrates schematic diagrams of cellular ,cell graph and Erdós-Rémy graph structures. And in Fig. illustrates two schematic diagrams of the locally and sparsely connected graphs we generated. Note they do not correspond to any testing instances.
23

---

Published as a conference paper at ICLR 2026
1e4
2.2
SPT
2.1
SPT_ SPT_CT((tree//ter)
Energy
SPT [PT_CT(Strees/iter)
2.0
SPT_CT(10trees//ie
1.9
SPT_CT([SSreessiter)
SPT_CT(20trees/iter)
1.8
Iterations
Figure Energy curves of SPT using fixed trees or resample spanning trees at each iteration.
(a) Cell graph
(b) Cellular graph
(c) Erdös-Rényi graph
Figure Schematic diagrams of cell graph, cellular graph and Erdōs-Rényi graph.
O.2 UAI INFERENCE COMPETITION
We visualize the topology of four instances from UAT competition in Fig. 9
(a) Average degree
(b) Average degree 24
Figure 8: Schematic diagrams of locally and sparsely connected graphs
24

---

Published as a conference paper at ICLR 2026
(a) Segmentation.
(b) ProteinFolding.1
(c) ProteinFolding.I1
(d) Grids_30
Figure 9: Schematic diagrams of some UAI inference competition instances. Zoom in for better view.
O.3 PCI INSTANCES
topologies the PCI instances are Fig. 10
(a) ICLINSTANCE. (b) 2CLINSTANCE.2 (c) 3 (d) PCLINSTANCE.
Figure 10: Schematic diagrams of PCI instances. Zoom for better view.
P LLM STATEMENT
In our research process, utilized large language models primarily to support technical writing aspects rather than for generating research content. These tools were employed specifically for grammar checking, spell correction, improving sentence structure, enhancing overall readability of manuscript. scientific contributions, technical analyses, experimental designs, and conclusions presented in this paper are the original work of the authors, with language models serving only as writing assistance tools.
25


Reviews:
[{"review_id": "xAeL35QElV", "reviewer": "Reviewer_14zd", "summary": "The paper studied the problem of finding the minimum energy state in a Markov random field (MRF). The problem is NP-hard in general because it can in-code the max-cut problem. The Belief Propagation (BP) is a famous algorithm for computing marginal distributions (inference) of MRFs. The algorithm can solve the inference problem exactly if the graph is a tree. The main contribution of this paper is a heuristic algorithm for finding the minimum energy state of a MRF. \n- The algorithm generate some i.i.d. samples of uniform random spanning trees.\n- For each tree (re-weight the edge according to the marginal of random spanning trees), run BP to compute marginals of every nodes. \n- Merge the results of all trees by taking the product in (12) line 237.\n- Given the marginals, using a greedy algorithm and a simple sampling (sample each marginal independently) algorithm to find a state. Update the current best answer.\n\nThe paper gives theoretical analysis on some step of the algorithm. The paper then did a lot of experiment on both synthetic data and real-world data.\n\nTo summarize, I think the theory part is of this paper is simple. The idea share some similarity with graph sparsification algorithm, which also use the random tree to sparsify the graph and change the edge weight (you may add some discussion). Some main theoretical results is the correctness of expectation and a concentration bound. However, it is interesting to see a simple algorithm works in many real application.", "questions": "Consider a Markov Random Field (MRF) defined on a general graph, inducing a Gibbs distribution $\\mu$ over $\\mathcal{X}^V$ (assume $\\mathcal{X} =$ {0,1}). Although computing marginals is generally intractable, suppose we have access to an oracle that provides the marginal distribution for each node. For any $v \\in V$, the oracle returns $p_v = \\text{Pr}_{X \\sim \\mu}[X_v = 0]$. With this information, we can directly run the GibbsSampler and GreedySelector as described in Algorithm 1. The question is: does the algorithm find a good state with low energy?\n\nHere is a simple example. Consider the energy function defined in (1), with $\\mathcal{X}$ = {0,1} and $\\theta_i(x_i) = 0$ for all $i$ and $x_i$. For the pairwise interaction term $\\theta_{ij}$, define:\n- $\\theta_{ij}(x_i, x_j) = 1$ if $x_i \\neq x_j$\n- $\\theta_{ij}(x_i, x_j) = 0$ if $x_i = x_j$\n\nClearly, the minimum energy configuration corresponds to the MAX-CUT of the graph, which is NP-hard. In this case, due to the symmetry between values $0$ and $1$, the marginal distribution for each node is uniform over {0,1}. This suggests that marginals alone may not help in finding the minimum energy state.\n\n**Question:** In general, what is the relationship between computing marginals and finding the minimum energy state? Since the problem itself is NP-hard, we cannot expect the algorithm work for all cases. It is better to give some intuition and explanation on which situation this idea could provide a good solution. \n\n---\n\n**Lemma 1** relies on an unrealistic assumption. The set $\\mathcal{K}$ is a randomly sampled set in the algorithm and may contain duplicate elements. The lemma assumes $\\mathcal{K} = \\mathcal{T}$, but this assumption is problematic for two reasons:\n1. Let $N = |\\mathcal{T}|$ be the number of spanning trees. Since $N$ can be exponential in $n$, i.e., $N = \\exp(O(n))$, it is infeasible to generate that many samples.\n2. Even if it were feasible, the condition $\\mathcal{K} = \\mathcal{T}$ implies no duplicates in $\\mathcal{K}$ (otherwise, equation (17) in the proof of Lemma 1 fails). However, the algorithm samples with replacement, making this event extremely unlikely.\n\n---\n\n**Lemma 2** is more reasonable. It states that the expected energy is correct. Some notational improvements can be made in equation (13):\n- You can remove the factor $\\frac{1}{|\\mathcal{K}|}$ and the summation over $T_k \\in \\mathcal{K}$, and simply replace $T_k$ with $T$. It suffices to show that the expectation over a single random spanning tree $T\\sim \\Omega(\\mathcal{T})$ is correct. Since $\\mathcal{K}$ consists of i.i.d. samples, the expectation of their average is also correct.\n- If you prefer to keep the set $\\mathcal{K}$, then the expectation should be taken over the randomness of all i.i.d. samples in $\\mathcal{K}$, where each $T_k \\sim \\Omega(\\mathcal{T})$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper proposed to use random trees to approximate the MRF, which connects the concept of graph sparsification with the MAP (Maximum A Posteriori) inference problem in probabilistic graphical models. Intuitively, by constructing a collection of randomly sampled tree structures, one can run existing algorithms on trees while random trees preserves some information of the original MRF.\n\n- The experimental evaluation on synthetic data and real-world data is comprehensive and well-structured. Detailed tables and visualizations are provided to illustrate the results, including comparisons with baseline methods. The findings shows that their algorithm can achieve a good performance in many situations.", "weaknesses": "- The MAP problem is trivial in trees because one can use a dynamic programming (the algorithm called max-product or min-sum algorithm). In this paper, the authors use BP to compute marginal distributions on trees and use marginal on trees to approximate marginal on MRFs.  The connection between computing marginal distributions and identifying the minimum energy configuration is not stated in the paper.  Even if this is a heuristic, it would be good to explain some intuition here. (See more detailed questions in the next section)\n\n- Some statement in the theorems and lemmas and some proofs look confusing.  (See more detailed questions in the next section)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CJWR27hQJr", "reviewer": "Reviewer_inkb", "summary": "The paper explores sparsity and local connectedness in MAP estimation of Markov Random Fields (MRFs) proposing to combine multiple (spanning) subtrees learned exactly by sampling multiple spanning trees from the original graph and applying conventional belief propagation (BP). These exactly solved spanning subtrees are combined through an inverse weighting function accounting for the probability of sampling given edges to provide aggregated approximate solutions to the entire MRF. The approach is simple and straightforward to implement and appears to work well in practice as highlighted in the papers experimental section.", "questions": "Consider include scalable approaches based on approximate spanning tree estimation procedures and compare how the exact to such scalable approaches compare.\n\nPlease provide error bars in Figure 1 and the Tables across multiple runs. As the procedure is non-deterministic it will be good to see how much variability this induces on the results.\n\nMRF estimation has been demonstrated to benefit from massively parallelization – how does the proposed approach compare to such parallelized implementations as in:\n\nhttps://download.mmag.hrz.tu-darmstadt.de/media/FB20/GCC/paper/Thuerck-2016-HPG.pdf\n\nFurthermore, how does the procedure compare to other methods covered in the related works section such as \n\nH. Ishikawa, Exact Optimization for Markov Random Fields with Convex Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) 25 (10) (2003) 1333-1336.\n\nD. Schlesinger, B. Flach, Transforming an Arbitrary Minsum Problem into a Binary One, Tech. Rep. TUD-FI06-01, Dresden University of Technology (2006)\n\nIn equation 12 the product does not produce as I understand it a valid conditional distribution \\tilde{p}(x_i|X\\{x_i}). Please clarify how samples are drawn from the distribution, is it simply renormalized by \\tilde{p}(x_i|X\\{x_i})/(\\sum_{x_i} \\tilde{p}(x_i|X\\{x_i})) and shouldn’t \"=\" then be \"\\propto\" (if it is not a normalized distribution)?\n\nIn summary, I consider this a borderline leaning accept paper but with room for improvements in particular in terms of establishing their approach to more alternatives by providing a wider comparison and include error bars for the assessments of results.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "•\tThe approach is well related to the existing literature in the literature review.\n\n•\tThe approach appears to work well in practice and is simple to implement.\n\n•\tThe weighting scheme to correct for how edges in the spanning tree are sampled compared to uniform sampling appears as a simple, elegant, and valid practical approach to correct for biases by the sampling procedure.\n\nOriginality:\nThe approach combining multiple spanning subtrees appears new and original.\n\nQuality:\nThe paper is generally clear and easy to follow. The experimentation considers comparison to a limited number of baselines which can be improved.\n\nClarity:\nThe paper can be improved in its writing - please also see the minor comments under Weaknesses, however, the developed methodology is clear. \n\nSignificance:\nMinimizing pairwise MRFs are an extensively studied field with many contributions and approaches developed over the years. The paper here develops an interesting new approach which could warrant publication, but the significance of the results are unclear as no error bars are reported and the paper only compared to a limited number of alternatives.", "weaknesses": "The present procedure relies on estimating the spanning three exactly requiring O(N^3) which limits the approach to small graphs and subtrees. While scalable approaches are discussed it is unclear how well they perform in practice.\n\nWhereas applications where the methodology is important is discussed in the motivation it is unclear how the solutions benefit practical applications. It would strengthen the paper to consider the solutions for at least one of the given problem domains highlighted in the motivation (introduction) and the practical implications.\n\nThe method is compared to very few competing methods, whereas the literature and approaches minimizing the energy of MRF including for the considered pairwise MRFs is vast as also highlighted in the rather old survey:\n\nWang, Chaohui, Nikos Komodakis, and Nikos Paragios. \"Markov random field modeling, inference & learning in computer vision & image understanding: A survey.\" Computer Vision and Image Understanding 117.11 (2013): 1610-1627.\n\nWhere submodular random fields have also been considered for pairwise random fields such as the papers cited in the related works section:\n\nH. Ishikawa, Exact Optimization for Markov Random Fields with Convex Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) 25 (10) (2003) 1333-1336.\n\nD. Schlesinger, B. Flach, Transforming an Arbitrary Minsum Problem into a Binary One, Tech. Rep. TUD-FI06-01, Dresden University of Technology (2006)\n\nFurthermore MRF estimation has been scaled using massively parallelized implementations as in:\nhttps://download.mmag.hrz.tu-darmstadt.de/media/FB20/GCC/paper/Thuerck-2016-HPG.pdf\n\nIn this context, I find the experimentation to only include a very limited  number of comparisons to existing methods, i.e. Mean field, LBP, and TRBP whereas the literature is vast with many proposed methods. \n\nMinor issues of the paper needing some proof-reading:\nProblem equation 1 is known NP-hard in general -> The problem in equation 1 is known to be NP-hard in general\n\nsolve equation 1 can date back 80’s of the previous century -> solve equation 1 dates back  to the 80’s of the previous century\napproach to infer on MRFs  -> approach to infer MRFs \n\nStrange use of past tense of “could” in the Methods section which should be “can” throughout please check. \n\nSince Acquire the true tree -> Since Acquiring the true tree", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fNVEVMDsDl", "reviewer": "Reviewer_Vpu6", "summary": "This paper proposes a spanning-tree–based MAP inference algorithm (called SPT) for Markov Random Fields (MRFs) on locally and sparsely connected graphs, which is a regime common in power grids, communication networks, and transportation networks. The key idea is to sample uniform random spanning trees (RSTs) from the original graph; then run exact BP on each sampled tree (cycle-free so inference is tractable). Experiments on both synthetic an real datasets show the better performance of the proposal.", "questions": "- In Theorem 1, the error bound decreases as the number of spanning trees $\\mathcal{K}$ increases. The proposed algorithm is taliored for sparse graphs. However, a sparse graph should have less spanning trees compared to a dense graph, which leads to a worse error bound. How do we understand this?\n- In the experiment of Figure 1, where we compare energy against number of iteration, I wonder if this is a fair comparison. As these methods can be doing very different things and computation in each iteration step.\n- Maybe a better comparison is to look at the wall clock time needed for each baseline to reach a certain energy accuracy.\n- Why is the proposed algorithm inconsistent on ER graph?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper has clear motivation and introdution for the problem setup and the proposal.\n- The complexity analysis and convergence guarantee is given and offer insights into the dependence on the problem parameters.\n- The proposed algorithm is scalable thus supports inference for large graphs.\n- The empirical validation on synthetic + UAI + real PCI datasets shows promising gains of the proposed approach.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)