Research map / Probabilistic and scientific modeling / Variational and generative sampling
Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a history-driven target (HDT) framework that replaces the target in any MCMC graph sampler with a visit-count-dependent target, giving unbiased sampling with O(1/alpha) variance reduction, compatibility with non-reversible samplers, and lower per-sample cost than SRRW.
Problem
Self-repellent random walks (SRRW) on graphs need the normalizing constant over all neighbors per step, require time-reversible base chains, and store full visit counts, limiting efficiency and scalability for graph sampling.
Approach
Instead of modifying the transition kernel, embed the self-repellent mechanism in a history-dependent target pi[x] proportional to mu_i (x_i/mu_i)^(-alpha); any MH-style base sampler then uses only local unnormalized visit counts and target values in its acceptance ratio, so it works with reversible and non-reversible chains.
Key results
- HDT-MTM and HDT-MHDA attain lower TVD and NRMSE than their base samplers on Facebook graph with alpha=5 (1000 runs, 15,000 steps).
- Under the same computational budget, HDT-MHRW consistently achieves lower TVD and NRMSE than SRRW, with the gap larger on the denser Facebook graph.
- LRU cache with 10% capacity yields about 10% smaller TVD than MHRW while reducing memory by over 90%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add the HDT target (α = 5) to the base sampler | MHRW, MTM, and MHDA · Graph sampling on Facebook and other evaluated graphs | TVD | Helped |
| Add the HDT target (α = 5) to the base sampler | MTM and MHDA · Graph sampling on evaluated graphs | NRMSE | Helped |
| Use HDT-MHRW instead of SRRW under the same computational budget | MHRW-based graph sampling · Facebook and p2p-Gnutella04 | TVD | Helped |
| Use HDT-MHRW instead of SRRW under the same computational budget | MHRW-based graph sampling · Facebook and p2p-Gnutella04 | NRMSE | Helped |
| Add HDT to the base MCMC sampler | HDT-MCMC · Empirical-measure variance relative to the base sampler | limiting covariance: 1/(2α+1) | Helped |
| Add an LRU cache tracking only part of the visit counts | HDT-MHRW · Real-world graph sampling with over 90% memory reduction | TVD: 10% smaller TVD | Helped |
| Increase the self-repulsion parameter α | HDT-MHRW · Graph sampling | TVD | Helped |
| Vary the initial state between low-degree and high-degree nodes | HDT-MHRW, HDT-MTM, and HDT-MHDA · Facebook | TVD | No clear effect |
| Vary the fake visit-count initialization (degree, non-uniform, or uniform) | HDT-MHRW, HDT-MTM, and HDT-MHDA · Facebook | TVD | No clear effect |
Surprising findings
- SRRW achieves the lowest TVD per step, but its per-step cost makes it worse than HDT under a fixed budget.
Limitations
- Theory covers only the discrete graph setting with finite state spaces; high-dimensional applications deferred to future work.
- LRU cache scheme is a heuristic approximation without theoretical guarantees.
- Requires assumption that the empirical measure stays in the interior of the simplex, enforced by truncation in practice.
Experimental setup
Datasets: facebook (SNAP) p2p-Gnutella04 (SNAP) WikiVote (SNAP) p2p-Gnutella08 (SNAP)
Benchmarks: facebook graph p2p-Gnutella04
Metrics: total variation distance NRMSE variance under fixed budget
Baselines: MHRW MTM MHDA SRRW
Builds on: SRRW Metropolis-Hastings multiple-try Metropolis MHDA stochastic approximation
Closest papers by meaning
- Repelling Random Walks (ICLR 2024 · similarity 0.89)
- Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks (ICLR 2024 · similarity 0.87)
- Graph-Based Stochastic-Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation (NeurIPS 2026 · similarity 0.86)
- AutoStep: Locally adaptive involutive MCMC (ICML 2025 · similarity 0.86)
- Monte-Carlo Tree Search with Uncertainty Propagation via Optimal Transport (ICML 2025 · similarity 0.86)
- Hypergraph Generation via Structured Stochastic Diffusion (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.