OpenNovelty.org

From Fields to Random Trees

ICLR 2026 Conference SubmissionAnonymous Authors
OpenReview Score: 6.7Download Report PDF
MAP estimationMarkov Random Fieldsrandom spanning trees
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://anonymous.4open.science/r/From-fields-to-trees-iclr-EB75}.

Disclaimer
This report is AI-GENERATED using Large Language Models and WisPaper (A scholar search engine). It analyzes academic papers' tasks and contributions against retrieved prior work. While this system identifies POTENTIAL overlaps and novel directions, ITS COVERAGE IS NOT EXHAUSTIVE AND JUDGMENTS ARE APPROXIMATE. These results are intended to assist human reviewers and SHOULD NOT be relied upon as a definitive verdict on novelty.
NOTE that some papers exist in multiple, slightly different versions (e.g., with different titles or URLs). The system may retrieve several versions of the same underlying work. The current automated pipeline does not reliably align or distinguish these cases, so human reviewers will need to disambiguate them manually.
If you have any questions, please contact: mingzhang23@m.fudan.edu.cn

Overview

Taxonomy

Core-task Taxonomy Papers
50
3
Claimed Contributions
26
Contribution Candidate Papers Compared
2
Refutable Paper

Research Landscape Overview

Core task: Maximum A Posteriori estimation on Markov Random Fields. The field centers on finding the most probable configuration of variables in an MRF, a problem fundamental to computer vision, medical imaging, and spatial statistics. The taxonomy reveals four main branches: Core MAP-MRF Inference Algorithms and Optimization Methods, which houses exact solvers like tree-based decompositions (Fields to Trees[0], Nested Recursive MAP[47]) alongside approximate techniques such as belief propagation (Belief Propagation Correctness[22], Fast Belief Propagation[45]) and continuous relaxations (Continuous Relaxations Survey[27], Semidefinite MRF Inference[17]); MRF Model Design and Prior Specification, addressing how to construct potentials and encode domain knowledge (Proper Gaussian MRF[1], Bottleneck Potentials MRF[37]); Application Domains and Problem-Specific Formulations, spanning medical segmentation (MR Brain Segmentation[16], Brain MRI Segmentation[34]), remote sensing (SAR Phase Unwrapping[42], Multimodal Change Detection[7]), and signal processing (MAP Compton Imaging[9], STEM Denoising MRF[18]); and Hybrid and Learning-Based Approaches, which integrate neural networks or data-driven priors (Neural MAP Deblurring[31], Neural MAP Beamforming[24]). Within the exact inference branch, a small cluster of works explores decomposition strategies that exploit graph structure to achieve tractability. Fields to Trees[0] sits squarely in this line, focusing on tree-based methods that transform general MRFs into tractable subproblems, much like Nested Recursive MAP[47] which recursively partitions the graph. In contrast, Proper Gaussian MRF[1] emphasizes closed-form solutions for specific model classes, trading generality for efficiency. Meanwhile, approximate methods like belief propagation remain popular for large-scale problems where exact inference is infeasible, and recent hybrid approaches (Neural MAP Deblurring[31]) blend classical MAP formulations with learned components. The central tension across these branches is the trade-off between solution quality guarantees and computational scalability, with tree-based decompositions offering a middle ground by preserving exactness on carefully chosen substructures while managing complexity through hierarchical partitioning.

Claimed Contributions

Spanning tree sampling method for MAP inference on MRFs

The authors propose a new approach that samples uniform random spanning trees from the graph, breaks cycles, and decomposes the original MAP inference problem into overlapping sub-problems on trees that can be solved exactly and efficiently. The method combines exact tree-based inference with sampling flexibility.

10 retrieved papers
Can Refute
Edge reweighting scheme using effective resistance

The authors introduce a reweighting mechanism that adjusts pairwise energy terms on sampled spanning trees using edge appearance probabilities computed via effective resistance. This ensures the combined energy of spanning trees aligns with the original graph energy.

6 retrieved papers
Theoretical error bound for energy approximation

The authors establish a theoretical error bound (Theorem 1) that relates the approximation quality to the number of sampled trees, edge selection probabilities, and pairwise energy terms. The bound shows the method performs better on sparse graphs where edge selection probabilities are higher.

10 retrieved papers
Can Refute

Core Task Comparisons

Comparisons with papers in the same taxonomy category

Contribution Analysis

Detailed comparisons for each claimed contribution

Contribution

Spanning tree sampling method for MAP inference on MRFs

The authors propose a new approach that samples uniform random spanning trees from the graph, breaks cycles, and decomposes the original MAP inference problem into overlapping sub-problems on trees that can be solved exactly and efficiently. The method combines exact tree-based inference with sampling flexibility.

Contribution

Edge reweighting scheme using effective resistance

The authors introduce a reweighting mechanism that adjusts pairwise energy terms on sampled spanning trees using edge appearance probabilities computed via effective resistance. This ensures the combined energy of spanning trees aligns with the original graph energy.

Contribution

Theoretical error bound for energy approximation

The authors establish a theoretical error bound (Theorem 1) that relates the approximation quality to the number of sampled trees, edge selection probabilities, and pairwise energy terms. The bound shows the method performs better on sparse graphs where edge selection probabilities are higher.

Table of Contents