Graph-Enabled Fast MCMC Sampling with an Unknown High-Dimensional Prior Distribution

Chenyang Zhong, Shijun Ji, Zheng TianarXiv 2024 · DOI · arXiv

TL;DR

This paper introduces graph-enabled MCMC, a novel algorithm for Bayesian inference when the prior distribution is unknown and only available as a set of samples. By constructing a geometric graph over these prior samples to guide Markov chain transitions, the authors achieve massive computational speedups—often an order of magnitude or more—without sacrificing the accuracy of the posterior approximation.

What Problem Does This Paper Address?

In the "ideal" Bayesian world, we have a clean mathematical formula for our prior distribution. In reality, especially in fields like meta-analysis or transfer learning, we often don't. Instead, we might have "prior samples"—for example, posterior draws from a previous, related study that we want to use to inform our current analysis.

The standard way to handle this is to use Kernel Density Estimation (KDE) to turn those samples into a smooth probability surface. However, running a standard Markov chain Monte Carlo (MCMC) algorithm on a KDE-based posterior is computationally brutal. Every single step of the chain requires evaluating the kernel against every prior sample. If you have 20,000 prior samples, your MCMC becomes 20,000 times slower. This "computational tax" makes high-dimensional Bayesian transfer learning nearly impossible for large datasets.

Methods

The authors propose a "graph-enabled" approach to bypass the $O(B)$ (where $B$ is the number of prior samples) evaluation bottleneck.

  1. Graph Construction: They first build an undirected geometric graph (specifically, a $k$-nearest neighbor graph) where each vertex is a prior sample.
  2. Guided Transitions: Instead of proposing a random jump in space (like a standard Metropolis-Hastings walk), the algorithm proposes moves to neighboring nodes in the graph.
  3. The "Secret Sauce": Because the graph structure itself reflects the density of the prior samples, the proposal distribution naturally "knows" about the prior. In the acceptance probability calculation, the complex KDE terms largely cancel out or are replaced by simple graph degrees.
  4. Algorithm Versions:
    • Algorithm I (Discretized): A simpler version that stays on the graph nodes.
  5. Algorithm II (Continuous): A more sophisticated version that allows the chain to move in continuous space while still using the graph to guide its path, providing a more accurate approximation of the true posterior.

Datasets

The authors validated their approach using three distinct setups:

  • Synthetic Multimodal Prior: A Gaussian mixture model used to test if the algorithm can handle complex, "patchy" prior distributions.
  • Synthetic Opioid Use Disorder (OUD) Data: A logistic regression model inspired by real-world efforts to estimate OUD prevalence in New York using historical data from Ohio as a prior.
  • Human Behavior Experimental Study: Real-world data from the Next Generation Social Science (NGS2) program, involving a "public goods game" where researchers integrated findings from an earlier study to inform a newer one.

Key Insights and Ideas

  • The Graph as a Density Proxy: The core "aha" moment is realizing that a geometric graph built on samples is essentially a non-parametric map of the distribution's manifold. Moving along its edges is a computationally cheap way to explore high-probability regions.
  • Breaking the Linear Scaling: In standard KDE-MCMC, the cost per iteration grows linearly with the number of prior samples ($B$). In graph-enabled MCMC, after a one-time setup cost to build the graph, the cost per iteration is constant, regardless of how many thousands of prior samples you have.
  • Mixing Efficiency: Surprisingly, the graph-based proposals often lead to better mixing (lower autocorrelation) than standard Gaussian proposals because the graph "channels" the walker into the relevant parts of the parameter space.

Key Results

  • Massive Speedup: In experiments with 10,000+ prior samples, the graph-enabled MCMC was more than 6 times faster per iteration than the standard Metropolis random walk.
  • Scalability: While the computation time for standard methods exploded as the number of prior samples increased, the graph-enabled method's time remained nearly flat (see Figure 5 in the paper).
  • Accuracy: Using the 2-Wasserstein distance (a measure of how much one distribution must be "warped" to match another), the authors showed that their graph-based approximation is just as accurate as the computationally expensive "gold standard" KDE method and far superior to simple Gaussian approximations.
  • Statistical Efficiency: The algorithm produced a significantly higher Effective Sample Size (ESS), meaning each iteration provided more "useful" information about the posterior than standard methods.

Limitations and Future Work

  • Initial Overhead: Constructing the $k$-NN graph takes $O(B^2)$ time. While this is a one-time cost, it could become a bottleneck if the number of prior samples is in the millions.
  • Prior-Likelihood Gaps: If the prior samples and the new data's likelihood have almost no overlap (disjoint support), the graph-walker might get stuck. The authors propose an "Adaptive" version in Section 6 to handle this by adding a "restart" mechanism to an uninformative prior, but this area warrants more exploration.
  • Transfer Learning Shifts: The authors plan to extend the work to handle more complex "distributional shifts" where the relationship between variables changes between the reference study and the current study.

Summary updated

Abstract

Posterior sampling is a task of central importance in Bayesian inference. For many applications in Bayesian meta-analysis and Bayesian transfer learning, the prior distribution is unknown and needs to be estimated from samples. In practice, the prior distribution can be high-dimensional, adding to the difficulty of efficient posterior inference. In this paper, we propose a novel Markov chain Monte Carlo algorithm, which we term graph-enabled MCMC, for posterior sampling with unknown and potentially high-dimensional prior distributions. The algorithm is based on constructing a geometric graph from prior samples and subsequently uses the graph structure to guide the transition of the Markov chain. Through extensive theoretical and numerical studies, we demonstrate that our graph-enabled MCMC algorithm provides reliable approximation to the posterior distribution and is highly computationally efficient.
BibTeX
@misc{zhong2024graph,
  author = {Chenyang Zhong and Shijun Ji and Zheng Tian},
  title = {{Graph-Enabled Fast MCMC Sampling with an Unknown High-Dimensional Prior Distribution}},
  year = {2024},
  eprint = {2408.02122},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2408.02122},
}
Figure