# Exact and Approximate MCMC for Doubly-intractable Probabilistic Graphical Models Leveraging the Underlying Independence Model

arXiv: https://arxiv.org/abs/2510.03587 · HTML: https://mlsanity.com/paper/2510.03587/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 39 references that are in the map.
- First posted on arXiv 4 Oct 2025.

## Builds on (most cited first, 4 of 4)

- [On Russian Roulette Estimates for Bayesian Inference with Doubly-Intractable Likelihoods](https://mlsanity.com/paper/1306.4032/) (2013)
- [Noisy Monte Carlo: Convergence of Markov chains with approximate transition kernels](https://mlsanity.com/paper/1403.5496/) (2014)
- [Towards a turnkey approach to unbiased Monte Carlo estimation of smooth functions of expectations](https://mlsanity.com/paper/2403.20313/) (2024)
- [Likelihood Based Inference in Fully and Partially Observed Exponential Family Graphical Models with Intractable Normalizing Constants](https://mlsanity.com/paper/2404.17763/) (2024)

## Abstract (arXiv)

Bayesian inference for doubly-intractable pairwise exponential graphical models typically involves variations of the exchange algorithm or approximate Markov chain Monte Carlo (MCMC) samplers. However, existing methods for both classes of algorithms require either perfect samplers or sequential samplers for complex models, which are often either not available, or suffer from poor mixing, especially in high dimensions. We develop a method that does not require perfect or sequential sampling, and can be applied to both classes of methods: exact and approximate MCMC. The key to our approach is to utilize the tractable independence model underlying the intractable probabilistic graphical model for the purpose of constructing a finite sample unbiased Monte Carlo (and not MCMC) estimate of the Metropolis--Hastings ratio. This innovation turns out to be crucial for scalability in high dimensions. The method is demonstrated on the Ising model. Gradient-based alternatives to construct a proposal, such as Langevin and Hamiltonian Monte Carlo approaches, also arise as a natural corollary to our general procedure, and are demonstrated as well.