# Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 71 references that are in the map.
- First posted on arXiv 23 May 2025.

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

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Oops I Took A Gradient: Scalable Sampling for Discrete Distributions](https://mlsanity.com/paper/2102.04509/) (2021)
- [A Survey on Active Simultaneous Localization and Mapping: State of the Art and New Frontiers](https://mlsanity.com/paper/2207.00254/) (2022)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [A Langevin-like Sampler for Discrete Distributions](https://mlsanity.com/paper/2206.09914/) (2022)
- [Random Walks: A Review of Algorithms and Applications](https://mlsanity.com/paper/2008.03639/) (2020)
- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [Random walks and diffusion on networks](https://mlsanity.com/paper/1612.03281/) (2016)
- [Discrete Langevin Sampler via Wasserstein Gradient Flow](https://mlsanity.com/paper/2206.14897/) (2022)
- [Online Statistical Inference for Nonlinear Stochastic Approximation with Markovian Data](https://mlsanity.com/paper/2302.07690/) (2023)
- [Walk for Learning: A Random Walk Approach for Federated Learning from Heterogeneous Data](https://mlsanity.com/paper/2206.00737/) (2022)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [Revisiting Random Walks for Learning on Graphs](https://mlsanity.com/paper/2407.01214/) (2024)
- [Enhanced gradient-based MCMC in discrete spaces](https://mlsanity.com/paper/2208.00040/) (2022)
- [Gradient-based Discrete Sampling with Automatic Cyclical Scheduling](https://mlsanity.com/paper/2402.17699/) (2024)
- [Self-Repellent Random Walks on General Graphs -- Achieving Minimal Sampling Variance via Nonlinear Markov Chains](https://mlsanity.com/paper/2305.05097/) (2023)
- [Efficient Informed Proposals for Discrete Distributions via Newton's Series Approximation](https://mlsanity.com/paper/2302.13929/) (2023)
- [Efficiency Ordering of Stochastic Gradient Descent](https://mlsanity.com/paper/2209.07446/) (2022)
- [Nonreversible MCMC from conditional invertible transforms: a complete recipe with convergence guarantees](https://mlsanity.com/paper/2012.15550/) (2020)
- [Rapidly Mixing Multiple-try Metropolis Algorithms for Model Selection Problems](https://mlsanity.com/paper/2207.00689/) (2022)
- [Lifting Markov Chains To Mix Faster: Limits and Opportunities](https://mlsanity.com/paper/1705.08253/) (2017)
- [Accelerating Distributed Stochastic Optimization via Self-Repellent Random Walks](https://mlsanity.com/paper/2401.09665/) (2024)
- [Efficient Unbiased Sparsification](https://mlsanity.com/paper/2402.14925/) (2024)
- [Does Worst-Performing Agent Lead the Pack? Analyzing Agent Dynamics in Unified Distributed SGD](https://mlsanity.com/paper/2409.17499/) (2024)
- [Comparison of asymptotic variances of inhomogeneous Markov chains with application to Markov chain Monte Carlo methods](https://mlsanity.com/paper/1307.3719/) (2013)
- [Random Walk Sampling in Social Networks Involving Private Nodes](https://mlsanity.com/paper/2305.12314/) (2023)

## Built on by (most cited first, 1 of 1)

- [True Self-Avoiding Walk for Accelerating Markov-Chain Monte Carlo Integration](https://mlsanity.com/paper/2605.30532/) (2026)

## Abstract (arXiv)

We propose a history-driven target (HDT) framework in Markov Chain Monte Carlo (MCMC) to improve any random walk algorithm on discrete state spaces, such as general undirected graphs, for efficient sampling from target distribution boldsymbolμ. With broad applications in network science and distributed optimization, recent innovations like the self-repellent random walk (SRRW) achieve near-zero variance by prioritizing under-sampled states through transition kernel modifications based on past visit frequencies. However, SRRW's reliance on explicit computation of transition probabilities for all neighbors at each step introduces substantial computational overhead, while its strict dependence on time-reversible Markov chains excludes advanced non-reversible MCMC methods. To overcome these limitations, instead of direct modification of transition kernel, HDT introduces a history-dependent target distribution boldsymbolπ[x] to replace the original target boldsymbolμ in any graph sampler, where x represents the empirical measure of past visits. This design preserves lightweight implementation by requiring only local information between the current and proposed states and achieves compatibility with both reversible and non-reversible MCMC samplers, while retaining unbiased samples with target distribution boldsymbolμ and near-zero variance performance. Extensive experiments in graph sampling demonstrate consistent performance gains, and a memory-efficient Least Recently Used (LRU) cache ensures scalability to large general graphs.