📊 statistics

Bayesian Inference for Discrete Markov Random Fields Through Coordinate Rescaling

This paper proposes a scalable coordinate-rescaling sampling method that transforms pseudo-likelihood-based posteriors to enable accurate and efficient Bayesian inference for discrete Markov random fields, effectively overcoming the computational infeasibility of exact likelihood evaluation and the poor uncertainty quantification of existing approximations.

Original authors: Giuseppe Arena, Maarten Marsman

Published 2026-03-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Giuseppe Arena, Maarten Marsman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a complex social network, like a high school where students are either friends or not. You want to map out who influences whom. In the world of statistics, this is called a Markov Random Field (MRF). It's a way to model how different variables (like students' moods or behaviors) depend on each other.

The problem is that calculating the exact truth about these relationships is like trying to count every single possible combination of friendships in a school of 1,000 students. The number of possibilities is so huge (exponential) that even the world's fastest supercomputers would take longer than the age of the universe to do the math. This is the "intractable normalizing constant" problem mentioned in the paper.

Because the exact math is impossible, statisticians usually use a shortcut called Pseudo-Likelihood.

The Analogy: Imagine you want to know the average height of everyone in a city. Instead of measuring everyone (impossible), you measure a few people in each neighborhood and guess the average.
The Flaw: This shortcut is fast, but it's often too confident. It tells you, "I'm 99% sure the average height is 5'10"," when in reality, the data is much more scattered. It underestimates the uncertainty, making the results look more precise than they actually are.

The Solution: Coordinate Rescaling (CoRe)

The authors, Giuseppe Arena and Maarten Marsman, propose a new method called Coordinate Rescaling (CoRe).

The Metaphor: The Distorted Map
Think of the "Pseudo-Likelihood" result as a map of a city that has been stretched and squashed. The streets are in the right places (the average relationships are correct), but the distances between them are wrong. The map makes the city look smaller and more compact than it really is.

The CoRe method is like a smart GPS that takes this distorted map and "rescales" it. It stretches the map back out to its true proportions without having to redraw the whole city from scratch.

Here is how it works in simple steps:

The Fast Guess: First, the computer uses the fast "Pseudo-Likelihood" shortcut to get a rough idea of the relationships. This is quick and easy.
The Stretching Factor: The computer then calculates a "stretching factor" (a mathematical matrix). It looks at how the fast guess differs from what the true math should look like.
The Rescaling: As the computer runs its simulation, it applies this stretching factor. It takes the fast, too-confident results and gently pulls them apart to match the true level of uncertainty.

Why is this better than the old ways?

The paper compares their new method to two other approaches:

The "Double Metropolis-Hastings" (DMH) Method:
- Analogy: This is like trying to fix the map by hiring a team of 100 surveyors to walk every single street and measure it again, just to be sure.
- Pros: It's very accurate.
- Cons: It takes forever. In the paper's example, it took 9 minutes to do what the new method did in 28 seconds. It's too slow for big networks.
The Old "Post-Hoc" Calibration:
- Analogy: This is like drawing the fast map, then waiting until the drawing is finished, and then trying to stretch it with a ruler.
- Cons: It's clunky. You have to finish the whole process before you can fix the errors.

The CoRe Advantage:
The CoRe method does the stretching while it is drawing the map. It keeps the speed of the fast shortcut but fixes the accuracy issues on the fly.

The Results

The authors tested this on simulated data (like creating fake social networks with known rules). They found that:

Accuracy: CoRe gave results almost as accurate as the super-slow "surveyor" method (DMH).
Speed: It was hundreds of times faster than DMH.
Uncertainty: Unlike the old fast method, CoRe correctly showed how uncertain the results were. It stopped pretending to be 100% sure when it wasn't.

The Bottom Line

In the world of data science, there is often a trade-off: you can have speed or accuracy, but rarely both.

Old Fast Methods: Fast but overconfident (wrong).
Old Accurate Methods: Correct but painfully slow.

Coordinate Rescaling (CoRe) is the "Goldilocks" solution. It uses a clever mathematical trick to stretch the fast, rough estimates into the correct shape, giving researchers a tool that is both blazingly fast and statistically reliable. This allows scientists to analyze massive, complex networks (like brain connectivity or genetic interactions) that were previously too difficult to study with such precision.

1. Problem Statement

The paper addresses the challenge of Bayesian inference in discrete Markov Random Fields (MRFs), specifically focusing on doubly intractable posteriors.

The Core Issue: In discrete MRFs, the likelihood function contains an intractable normalizing constant ( $Z(\eta)$ ) that requires summing over an exponentially large state space. Consequently, the posterior distribution is "doubly intractable" because both the likelihood and the marginal likelihood (evidence) involve this constant.
Limitations of Existing Methods:
- Exact Inference (e.g., Double Metropolis-Hastings - DMH): While accurate, these methods require nested MCMC sampling to approximate the ratio of normalizing constants. This results in prohibitive computational costs that do not scale well to large networks.
- Pseudo-Likelihood Approximations: These methods avoid the normalizing constant by approximating the joint likelihood as a product of conditional distributions. They are computationally efficient but systematically underestimate posterior variability (uncertainty), leading to overconfident parameter estimates and poor uncertainty quantification.
- Post Hoc Calibration: Existing methods attempt to correct pseudo-posterior variance after sampling, but they often fail to integrate seamlessly with joint structure learning or require complex iterative estimation.

2. Methodology: Coordinate Rescaling (CoRe)

The authors propose a new class of sampling methods called Coordinate Rescaling (CoRe). This approach embeds a linear transformation directly into the MCMC sampling process to correct the geometry of the pseudo-posterior.

A. Theoretical Foundation

The method operates on the observation that while pseudo-likelihood estimates are consistent in location (mean), they suffer from a scale error (underestimated variance). CoRe transforms the parameter space to align the pseudo-posterior with the target posterior.

Transformation: Let $\eta$ be parameters on the pseudo-posterior scale and $\beta$ be parameters on the transformed scale. The linear transformation is defined as:
$\beta = A(\eta - \eta^*) + \eta^*$
where $\eta^*$ is a point estimate (e.g., MAP or MPLE) and $A$ is a rescaling matrix.
The Rescaling Matrix ( $A$ ): The matrix $A$ $A$ is constructed to approximate the covariance structure of the target posterior. It is defined as $A = \Gamma L^\top$ $A = Γ L^{⊤}$ , where:
- $L^\top$ is the Cholesky factor of the negative Hessian of the pseudo-likelihood (local curvature).
- $\Gamma$ is the Cholesky factor of a robust covariance estimator (Godambe-Huber-White) that captures the target posterior's variability.
Sampling Scheme: The sampler targets the transformed posterior $\pi(\beta | X)$ . The Metropolis-Hastings acceptance ratio is calculated using the pseudo-likelihood (which is tractable) but applied to the transformed parameters. The Jacobian of the transformation is constant and cancels out in the ratio, preserving the Markov property.

B. Adaptive Variant (AdaCoRe)

To avoid the need for pre-specifying the rescaling matrix, the authors introduce AdaCoRe.

During the warm-up phase, the rescaling matrix $A^{-1}$ is updated iteratively based on the running mean of the parameters.
Updates are triggered only when the relative change in local curvature exceeds a specific threshold ( $3/\sqrt{n}$ ), ensuring stability against Monte Carlo noise.
This allows the sampler to adaptively learn the correct covariance structure without external calibration steps.

3. Key Contributions

Novel Sampling Framework: Introduction of CoRe, a method that integrates coordinate rescaling within the MCMC algorithm rather than as a post-processing step. This allows for joint estimation of parameters and network structure on a correctly calibrated scale.
Adaptive Implementation: Development of AdaCoRe, which removes the need for manual specification of the rescaling matrix by learning it during the burn-in phase.
Theoretical Justification: Demonstration that the transformation preserves detailed balance and converges to the target posterior while retaining the computational efficiency of the pseudo-likelihood.
Comprehensive Benchmarking: A rigorous simulation study comparing CoRe/AdaCoRe against:
- Recalibration methods: Post Hoc calibration (Robbins-Monro, GHW, Monte Carlo Hessian).
- Likelihood approximations: Empirical Likelihood.
- Transition kernel approximations: Double Metropolis-Hastings (DMH) and Adaptive DMH (AdaDMH).

4. Simulation Results

The authors evaluated methods on ordinal MRFs with network sizes $p=6$ and $p=9$ , and sample sizes ranging from 500 to 3000, across small-world, random, and fully connected graph structures.

Posterior Overlap: CoRe and AdaCoRe achieved median overlap indices with the exact posterior between 90% and 95%, significantly outperforming the raw pseudo-posterior (~65-70%) and matching the accuracy of the computationally expensive DMH.
Uncertainty Quantification:
- Pseudo-likelihood consistently underestimated standard deviations by 30-35%.
- CoRe and AdaCoRe corrected this, producing posterior standard deviation ratios ( $\sigma_{method}/\sigma_{exact}$ ) close to 1.0 across all conditions.
- DMH also performed well on this metric but with higher variance in larger networks.
Conditional Independence (Savage-Dickey Ratio): CoRe methods accurately reproduced the Bayes factors for testing absent edges, whereas pseudo-likelihoods showed systematic distortion (overestimating evidence for zero effects).
Computational Efficiency:
- Runtime: CoRe methods were roughly 2x slower than pseudo-likelihood/post-hoc methods but orders of magnitude faster than DMH.
  - Example: For $p=9$ , CoRe took ~370 seconds, while DMH took ~3,800 seconds (approx. 1 hour).
- Effective Sample Size (ESS): CoRe maintained stable and high ESS values as network complexity increased. In contrast, DMH and AdaDMH showed significant declines in ESS as $p$ increased, indicating poor mixing due to the nested sampling burden.

5. Significance and Implications

Scalability: CoRe provides a scalable solution for Bayesian inference in discrete MRFs, bridging the gap between the speed of pseudo-likelihood and the accuracy of exact inference.
Reliable Uncertainty: By correcting the posterior scale, CoRe enables reliable hypothesis testing (e.g., edge selection) and credible interval estimation, which are critical for applications in psychology (symptom networks) and genetics.
Integration: Unlike post-hoc calibration, CoRe operates during sampling, making it suitable for frameworks that require simultaneous estimation of network structure and parameters.
Future Directions: The authors suggest extending the geometric rescaling principle to other composite likelihoods (e.g., ERGMs, Potts models) and developing component-wise update mechanisms for even higher-dimensional systems.

In conclusion, the paper establishes Coordinate Rescaling as a superior alternative for discrete MRF inference, offering a "best of both worlds" scenario: the computational tractability of pseudo-likelihood with the statistical fidelity of exact Bayesian inference.