Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
Authors: Jie Hu
Yi-Ting Ma
Do Young Eun
Venue: ICML 2025 oral (2025)
Keywords: Nonlinear MCMC
History-Driven Target
Computational Efficiency
Near-Zero Variance
Primary area: probabilistic_methods->monte_carlo_and_sampling_methods
TL;DR: This paper presents an efficient framework for adaptive MCMC sampling in discrete spaces, incorporating self-repellence into an self-adaptive target distribution for any advanced MCMC techniques with near-zero variance.

Abstract: 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{\\mu}$. 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{\\pi}[\\mathbf{x}]$ to replace the original target $\\boldsymbol{\\mu}$ in any graph sampler, where $\\mathbf{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{\\mu}$ 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.

Beyond Self-Repellent Kernels: Nonlinear MCMC on General Graphs
History-Driven Target Towards Efficient
Jie Hu
Yi-Ting Ma
Do Young Eun
Abstract
1. Introduction
Random walks on general graphs are fundamental tools across diverse disciplines, including physics, statistics, chine learning, biology, and social sciences (Robert & Casella, 2013; Grover & Leskovee, 2016; Masuda et al., 2017; Kim et al., 2024), powering applications like online social networks (Xie et al., 2021), web crawling (Olston et al., 2010), robotic exploration (Placed et al., 2023), and mobile networks (Triasteyn et al., 2022; Ayache al., 2023). Starting from any state (node), walker transitions one of its neighbors along the connected edges using only local information, combining simplicity with scalability. This makes random walks powerful for exploring large networks and performing graph-based Markov chain Monte Carlo (MCMC) tasks to generate samples from target distributions μ4 on the graph (e.g., uniform, begree-based, or energy- based). They also enable distributed optimization net- worked systems (Sun al., 2018; Hu al., 2022; Even, 2023; Hendrikx, 2023). Simple random walks (Gjoka et al., 2011; Perozzi et al., 2014) and Metropolis- Hastingss (MH) random walks (Metropolis et al., 1953; Hastings, 1970; Xia et al., 2019) are foundational methods for these tasks, though they can suffer from slow mixing and local trapping.
We propose history-driven target (HDT) frame- work in Markov Chain Monte Carlo (MCMC) to improve any random walk algorithm on dis- crete state spaces, such as general undirected graphs, for efficient sampling from target distri- bution μ.. With broad applications in network sci- ence and distributed optimization, recent innova- tions like the self-repellent random walk (SRRW) achieve near-zero variance by prioritizing under- sampled states through transition kernel modi- fications based on past visit frequencies. How- ever, SRRW's reliance on explicit computation of transition probabilities for all neighbors 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 tran- sition kernel, HDT introduces history-dependent target distribution [x] to replace the original tar- get a in any graph sampler, where represents the empirical measure of past visits. This design preserves lightweight implementation by requir- ing 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 μ and near-zero variance perfor- mance. Extensive experiments in graph sampling demonstrate consistent performance gains, and memory-efficient Least Recently Used (LRU) cache ensures scalability to large general graphs.
1.1. Recent Advances in Graph Sampling
In social networks, e-commerce, recommendation systems and other domains, practitioners need to estimate graph size, node degree distribution, and label distribution (Xie et al., 2021). These applications include detecting bot pop- ulations, identifying high-value user segments scarce features (Nakajima & Shudo, 2023), and gradient of local loss for token algorithms in distributed optimizations (Sun et al., 2018; 8; Even, 2023), especially with limited graph ac- cess. However, a standard random walk can be slow in discovering underrepresented regions or rare features, fore- ing more samples to achieve acceptable levels of accuracy. To improve the sampling efficiency of the MH algorithm, MH with Delayed Rejection reduces persistent rejections to facilitate exploration (Green & Mira, 2001). Another variant is the Multiple-Try Try Metropolis (MTM), which pro- poses multiple candidates at each step and selects one based on their weights (Liu et al., 2000; Pandolfi et al., 2010).
'Department of Electrical and Computer Engineering, North Carolina State University, Raleigh, North Carolina, USA. Corre- spondence to: Do Young Eun <dyeun@ nesu.edu>.
Proceedings of the ndnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Input: unnormalized target dist. f
Input: unnormalized target dist. ç
Initialize empirical measure No
Initialize empirical measure Xo
Reversible MCMC kernel P
Update x via past samples
Paradigm Shift
Update target dist. π x
Update x via past samples
je-g,, MH, MHDR, MTM)
?
Construct SRRW kernel K [[x] by modifying P
Kernel Mod.
4
Both Reversible & Non-reversible MCMC
Adaptive Target
(e.a. MH, MHDR, MTM, MHDA, NRMH, 2-cycle method, etc.) Lightweight: only replace target μ -> xr(x] in the sampler
(High computational cost: require evaluation of Pty for j)
Generate samples )
Generate samples
(a). Self-Repellent Random Walk
(b). Our History-Driven Target Framework
Figure 1. Flowchart comparison between (a) SRRW (Doshi et al., 2023) and (b) History- -rivve Target (HDT) framework.
The choice of weights is further refined by Chang et al. (2022) with the integration of locally balanced functions in Zanella (2020), quantifying the improvement in mixing time. Further improvements have been achieved via non- reversible random walk techniques. These include lifted Markov chains, which augment the state space with direc- tional information (Chen et al., 1999; Diaconis al., 2000; Apers et al., 2017); 2-cycle MCMC methods, which alter- nate between two reversible chains (Maire et al., 2014; Ma et al., 2016; Andrieu & Livingstone, 2021); and modifi- cations from a reversible chain by adding antisymmetric perturbations (Suwa& & Todo, 2010; Chen & Hwang, 2013; Bierkens, 2016; Thin et al., 2020). Non- baubbacttrakknng ran- dom walks, which avoid revisiting the immediate past, have also improved exploration (Alon et al., 2007; Lee et al., 2012; Hermon, 2019).
Markov chain with μ-invariant transition kernel P. as shown by Box @ in Figure 1(a). Unlike non-backtracking random walks relying solely on the most recent history (Alon et al., 2007: Lee et al., 2012), SRRW incorporates the entire past trajectory to adaptively adjust transition prob- abilities towards less-visited states while preserving con- vergence to μ.. Formally, let g = =(Xt, E) be a connected, undirected graph with node set X' and edge set E, and let (ii) & {j E X (i.)) E} be the neighbor set of state i. Its cardinality is denoted [W(i)). (Vi) N(ii) U {i} be the 'expanded' neighborhood of state i. Denote by z E (0, 1) the visit frequency of state i E X. Given a time- reversible kernel P with p.P., = my, where P.j > only if (i.j) E E, SRRW constructs a nonlinear kernel K K[x], parametrized by è [æe]eex. such that, for j E (i).
K [x| = 2, Pis(aas/))))
(1)
In fields such as statistical physics (e.g., Ising or Potts models (Grathwohl et al., 2021; Zhang et al., 2022)), ma- chine learning (e.g., energy-based models for image tasks or Bayesian methods for variable selection (Hinton, 2012: Sun et al., 2023a)), and econometrics (e.g., MCMC-MLE for random graph models (Bhamidi et al., 2011: Byshkin et al., 2016)), discrete state space can be represented graph. Here, nodes denote configurations, which are linked by edges via predefined Hamming distance. Efficient explo- ration yields quicker. more accurate system representation and inference. Specifically, informed proposals (Zanella, 2020) utilize local data to optimize acceptance-exploration balance but struggle with large-scale applicability. Gradient- based methods improve these proposals through techniques like Taylor series, cattopolls-adjustee Langevin, and New- ton approximations (Grathwohl et al., 2021; Rhodes & Gut- mann, 2022; Zhang et al., 2022; Sun et al., 2023b; Xiang et al., 2023). Nonetheless, they are designed for structured spaces and specific energy functions, unlike our focus on general graphs and arbitrary distributions μ., which renders gradient-based MCMC methods inapplicable.
where 2 0 is the strength of self- self-repellency, and the nor- malizing constant Z, EE Pa (1(2/// (=x///x))- Note that Kig |x] = 0 for j & (i), conforming to the graph structure. The transition probability to state j is dynamically enlarged or reduced from the original probability P. based on the history so far via the ratio (z between empirical measure and target distribution of state j (Box @ in Fig- ure 1). The kernel (1) is also known to be 'scale-invariant in the sense that it remains unchanged under any constant multiple of x or μ.. This self-repellent scheme shows re- markable success, achieving near-zero variance for large a at a rate of O(1/a) ) for graph sampling (Doshi et al., 2023) and (1/aa²) for distributed optimization (Hu et al., 2024a), and can even outperform i.i.d. sampling (i.e., random jumper) while still walking on the graph.
1.2. Limitations of SRRW
Computational Issue. Despite its theoretical appeal and general applicability to reversible MCMC samplers, SRRW suffers from critical computational overhead that under- mines its practicality, a shortfall overlooked in Doshi et al.
All the aforementioned works are still rooted in Markov chains. A recent breakthrough is the self-repellent random walk (SRRW) over general graphs (Doshi et al., 2023), a nonlinear Markov chain that modifies a time-reversible
In practice, the unnormalized target is typically used in MCMC algorithms instead of the normalized μ., bypassing the need for calculating the normalizing constant.
2

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
(2023). To fully understand these challenges, it important to first clarify the role of self-transition probability P. in the time-reversible chain P and how it is used in SRRW. In the MH algorithm, from state i, another neighbor state i E (ii) is proposed with probability Qij and accepted with probability A. A min 1z p/Qus/P:Qu }. If accepted, the walker moves to j. making the transition probability P.j = Qig Aij. keeping it reversible with respect to the given target μ.. If rejected, the chain remains at i, contribut- ing to the self transsaanition probability P, 1,=1-> Ejze Ayj Note that P. > 0 unless Ag =1 for all j # i, a rare case where the proposal Q is already p--invariant. Importantly, Pa is just byproduct out of the accept-reject mechanism, whose value is never explicitly pre-computed in standard MH algorithms. In addition, the acceptance ratio Ai is eval- uated only for the proposed state j. ensuring a lightweight sequential implementation.
memory capacity in simulations. Thus, it is natural ask:
Can design universal method to harness SRRW benefits, while tackling these challenges: (i) maintain computational efficiency. (ii) leverage both reversible and non-reversible MCMC samplers, and (iii) reduce memory usage?
1.3. Our Approach and Contributions
In this work, we tackle the three aforementioned challenges arising from nonlinear kernels of SRRW. Specifically, we theoretically resolve two of them: computational issue and incompatibility with non-reversible Markov chains, and pro- pose heuristic scheme that reduces storage requirements for memory issue. Comprehensive applications to exponen- tially large state spaces, i.e., high-dimensional problems, are deferred to future work.
In SRRW, the self-repellent mechanism is embedded di- rectly into the transition kernel K [x], leading to significant computational costs, as discussed earlier. However, the essence of a history-dependent scheme need not reside in the kernel itself. As depicted in Box @ of Figure 1(b), we shift this scheme to family of 'history-driven' targel (HDT) distributions. Specifically, we replace the original target fu, a single point in the probability simplex, with an adaptive distribution π π(x] parameterized by the empirical measure x, which evolves dynamically at each step based on the 'feedback' from past visits. The exact formulation of π π(x] in (6) ensures that less/more- visited state is as- signed higher/lower probabilities than the original target Pú, dynamically over time. Our approach allows for seam- less integration with any MCMC technique, using the target T[x] for a given x. Unlike SRRW. in our framework, we can reuse any advanced MCMC technique by simply replacing target μ by our design π[x] in both reversible and non- reversible samplers, retaining the lightweight, sequential, and adaptive nature of MCMC methods, as shown in Box @ of Figure 1. By decoupling the self-repellent mechanism from the transition kernel, we overcome the computational limitations of SRRW while achieving near-zen variance. This paradigm shift offers the best of both worlds: compu- tational efficiency and broad compatibility with advanced MCMC samplers. Our contributions
However, evaluating Kig [xx] in (1) demands pre-computation of the normalizing constant Zi, which necessitates knowl- edge of Pij for all j E (i), including the self-transition probability P.: when j = i, implying that all Auj must be prl-calculated. This modification completely destroys the essence of MH, where the acceptance ratio is evaluated on demand only for a proposed state one at a time and is never pre-quantified for all possible E (i). This issue becomes even more pronounced in scenarios with a large neighborhood size (i)),, where the computational cost scales accordingly. On the other hand, sampling, j directly from K(t+)[x] x Po..,((r///.))) /1.) as a target distribution over (i) might be deemed as alternative to bypass direct computation of the normalizing constant Z,. However, such approach also fails because it still requires knowledge of the target distribution up to a multiplicative constant, including Pa. defying the purpose of lightweight sampling. In short, P& becomes a requirement in SRRW rather than a natu- ral outcome of MH, translating to equivalent computational costs to sample from K(.,)) [x]. and thus offering no benefits.
Requirement of Time-Reversibillty Another significant drawback of SRRW is its strict reliance on time-reversible Markov chains. While this reversibility ensures a well- defined stationary distribution for the modified kernel K [x] (Doshi et al., 2023, Proposition 2.1), it inherently excludes non-reversible MCMC techniques that still converge to the same target distribution μe with better performance (Neal, 2004; Suwa& & Todo, 2010; Lee et al., 2012; Chen & Hwang, 2013; Maire et al., 2014; Ma et al., 2016; Bierkens, 2016; Andrieu & Livingstone, 2021).
follows.
1. A General Self-Repellent Framework: the HDT framework, which replaces the target μ by the history-driven target distribution π[x] via rigor- ous design. This formulation is compatible with both reversible and non-reversible MCMC samplers while climinating the computational overhead in SRRW.
We introduce
Memory Constraints.
Despite being technically viable, SRRW encounters memory issues in large graphs and con- figuration spaces where the empirical measure shares the dimensionality with the size of the state space. Retaining complete historical data through x at each step can exceed
2. Theoretical Guarantees: We prove that our HDT framework converges almost surely to the original tar- get μ and achieves O(1/a) variance reduction com- pared to the base sampler in the central limit theorem (CLT). Moreover, we establish a cost-based CLT, show-
3

---

History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
ing additional 0(1/E[[N(() variance reduction relative SRRW by the average neighhorhood size. 3. Empirical Evaluation: We perform extensive graph sampling simulations across various settings, includ- ing real-world graphs and both reversible and non- reversible MCMC samplers, and showcase the consis- tent efficiency and adaptability of our HDT framework. 4. Scalable Implementation for Large Graphs: We im- plement an LRU (Least Recently Used) cache scheme to manage x with limited memory. For example, even when maintaining visit frequencies for only 10% of states, our method leads to more than a 10% reduction in total variation distance over the original MCMC method, highlighting HDT's effectiveness in limited- memory environments.
The ergodic theorem for Markov chains (Brémaud, 2013, Theorem 3.3.2) states that the empirical measure X, of ergodic Markov chain, updated via (2), almost surely converges to
+ oc. In addition, the multivariate CLT (Brooks et al., 2011, Chapter 1.8.1) shows that vn(x,, 14) weakly converges to N (0, V), where the covariance matrix
V = -im +xx) (0x. (0x (3)
which serves the covariance matrix of both reversible and non-reversible MCMC samplers in Theorem 3.3. By Brémaud (2013, Chapter 6.3.3), V can be rewritten as
1 + X
V
>3 D Duoruu
(4)
When P is reversible, the property u, = D2 i gives V 1+A
Ei 1-x u.u"" See Appendix A for the derivation of (4).
2. Preliminaries
Properties of SRRW. The SRRW algorithm in Doshi et al.
Basic Notations. Let X' denote a finite discrete state space. Vectors are denoted by lower-case bold letters, e.g., V- A [ui]iEx, and matrices by upper-case bold, e.g., M [MyJaJex. The diagonal matrix De is constructed from the vector v, with its components placed along the main diagonal. We denote by 1,0 vectors of all ones and zeros with proper dimensions, respectively. Denote by Σ the |x|-ddmmesioona probability simplex over X, with Int(E) being its interior, i.e., x Int(E) implies that r; E (0, 1), Vi E X. For probability vector x Σ, we write X to denote any of its unnormalized counterparts, i.c., x = x/(17x) & x. Define ò; as the canonical vector whose components are all zero, except the i-th entry being one. Let N(, V) represent the multivariate Gaussian distribution with zero mean and covariance matrix V. We use for dist.
(2023) includes two steps at each time n: First, sample Xa+1 ((x,.,)Xxx) [x,]] in (1) using the current empirical measure x, and state Xni Second, update X via (2). This ensures that the SRRW kernel K[x] is adapted to the updated empirical measure Xn at each time n, mak- ing it a nonlinear Markov chain. A notable property of SRRW is acale-invariance" i.e.,, for any non-zero scalar C, Kaj [x][C]]= K,,[x), Vi,j X, such that computing K₁ [x] only requires knowing vectors x, l up to some constant multiples. It has been theoretically proved that the empirical measure Xn, + fa almost surely as n - co, and the scaled error v vT((xn -14 11) R-x, N NO,, SSRWW (a)), where
dist.
1+ A
V SSRRW (a)
Σ (A +1)+1
1- u.u,
(5)
weak convergence.
and Ao u. are eigenvalues and left eigenvectors of the time- reversible base MCMC kernel P leveraged by SRRW.
Ergodic Markov Chains. Consider an ergodic Markov chain with transition kernel P - and target distri- bution E Int("), satisfying P1 = 1 and μ²¹ P= n²=. In MCMC, the transition kernel P is defined by the target μ.. Throughout this work, we assume that P is full-rank and continuous in μ.. Denote by (A₁, Ue U;) the eigenpair of P. comprising the eigenvalues well as the corresponding left and right eigenvectors. Here, the eigenvalue A = 1 with its corresponding eigenvectors u1 14 and vn = 1. In addition, u 0; = 1 and uu"0; = for all i,j E [x]] with * j. Consider the sample path {2.) driven by an ergodic Markov chain on X, with 5(-) as the indicator function. The cu- mulative visit count state i by time n is expressed as (1) & Σ.= 8(X, = i), ensuring Eiex ā,,() (i) n. The empirical measure x,, e fa,, (e),()))) (i)liex is the normalized version of x,, hence x,, /1,(11 (1'"x,, xx,) = k,/n. Alterna- tively, we can express x,, iteratively as follows:
3. Main Results
We present our theoretical findings by first outlining the design principles for a HDT distribution that balances explo- ration with computational efficiency. Next, we examine the convergence and statistical properties of the HDT-MCMC algorithm. Lastly, we evaluate its computational cost against SRRW within a fixed budget using cost-based CLT, show- casing the performance benefits of HDT-MCMC.
3.1. Design of History-Driven Target Distribution
The foundation of HDT-MCMC is in the design of history- driven target π (x. 14] that relies solely on the visit count x and an unnormalized target js (as an input). while encapsu- lating self-repellent behavior in the resulting kernel. Our goal is to design the HDT π fx, μh] to satisfy the following four conditions:
1
Xa+1= = Xn + n (áxm11 xx))
(2)
4

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
CI (Scale Invariance). ny. [x, |=]= jr].
Algorithm 1 HDT-MCMC: Graph Sampling Framework
C2 (Local Dependence). The unnormalized term ß [x, 14] depends only on ju, and 2;, and is continuous in It, P4-
Input: Graph ( E), parameter a 2 0. unnormalized target fr, number of iterations T, base MCMC sampler (Bring Your Own MCMC).
Henceforth, we suppress I and simply write лíx] for brevity, whenever its dependence on is clear from the context.
Initialization: state Xo EX' visit count =(i)> 0, ViEX. for n = 0 to T' - do
C3 (Fixed Point). T Tiu]- = μ..
Step 1: Use the base sampler (reversible or non- reversible) to draw Xn+1 with history-driven target T[x] from (7).
C4 (History Dependence). л (xx) promotes/deters explo- ration of under/over-sampled states.
Step 2: Update visit count ( end for
Cl preserves the key property that our HDT-MCM algo- rithm only needs the unnormalized terms jı, and X when, for instance, computing an acceptance ratio of MH. Examples of the unnormalized target ji include: já = 1 for uniform target, ر, [i)) for degree-based target, and jr. = - (() for energy-spectie target (Gjoka et al., 2011; Lee et al., 2012; Grathwohl et al., 2021; Pynadath et al., 2024). C2 ensures that the sampler uses only minimal local informa- tion, i.e., 2; and f.. in its update. By eliminating neighbor information, the algorithm avoids prohibitive computational costs associated with increasing neighborhood size, e.g- in large or complete graphs. C3 indicates that if empirical measure x converges to the target μe, the HDT π [u] remains u itself. Indeed, if [u]] * μr, then an MCMC sampler with its target π [x] would converge
Output: A set of samples (X,, 17 JT-1-
As an example, we here illustrate our HDT-MCMC if we use the standard MH algorithm as the base MCMC sampler (Step 1) in Algorithm 1. At current state X,, = i, a can- didate j E (i) is selected with probability Qiz. then the acceptance ratio is calculated through
A,I[]= min (1, ny [x
min 1, (150 Qq (8)
The (a)
where only the unnormalized terms jua رراة Ty and ăÿ are required, keeping the same computational cost as standard MH with true target μ.. Then, the sampler accepts state j with probability A.y [x] and sets Xn+1 = j. rejects it with probability 1 - Ai, [x] upon which Xx+1 = i and repeats the procedure. Note that we recover the acceptance ratio Aij of the standard MH with target μu, when o = 0. This manner alters the target μ of the standard MH algorithm by HDT π [x] while preserving the lightweight, on- on-demand nature of MH, in contrast SRRW in which P.y must be evaluated for all possible j E (i) for a sample X In addition to computational efficiency, Aij [x] inherently embeds the 'self-repellent' effect. If state j is relatively less-visited than state i, i.e., / < ã.//i, it then follows that A: [x] 2 Aij. implying that state j is more likely to be accepted than the case with standard MH, and vice versa.
different distribution, contradicting our goal of preserving yu as the true target distribution. C4 is to facilitate exploration, ensuring that the sampler adaptively 'pushes' itself away from states al- ready visited more often than μ4, thereby mimicking the key self-repellent effect of SRRW in Doshi et al. (2023).
Lemma 3.1. Conditions CI- C4 hold if and only if
Ty [x] x p;(xz/ -a for any a > O.
(6)
The proof of Lemma 3.1 can be found in Appendix B. It reveals that an HDT distribution [x] satisfying all four con- ditions C1 - C4 must take the simple form of (6). A special case a = 0 reduces [x]] to the original target Ja, which be- comes history- independent.... Lemma 3.1 also demonstrates that our design (6) suffices to work with unnormalized quan- tities jú and x in place of μ and x, i.e.,
Remark 3.1. In Doshi et al. (2023), SRRW directly modi- fies a rive-reversible Markov chain P to incorporate self- repellency into the kernel K K[x] as in (1), which is then shown to be, for any given x E Int(Z), reversible w.n.t
T. [x] x म.. [x] = (,.
(7)
Following Lemma 3.1, Algorithm 1 shows the steps in our HDT-MCMC framework.2 2 As illustrated by Box @ in Fig- ure 1, the base MCMC sampler for graph sampling in our framework can either be time-reversible, i.e., MH (Metropo- lis et al., 1953; Hastings, 1970), MHDR (Green & Mira, 2001), MTM (Liu et al., 2000; Chang et al., 2022), non- reversible, i.c., MHDA (Lee et al., 2012), 2-cycle Markov chains (Maire et al., 2014; Andrieu & Livingstone, 2021), and non-reversible MH (Bierkens, 2016; Thin et al., 2020).
T: SKKW |x| X (1(A//H)) -
Σ P,(l,//n))"" V JEN(()
whose proof in Doshi et al. (2023, Appendix A) critically de- pends on the reversibility of P w.r.t. μ. Note that ा. [x] is the byproduct of the constructed kernel K [xx] as in (1), thus inheriting the same neighborhood dependency. Sim- ply adopting sSRw [x] in our Algorithm violates C2 and would incur high computational cost for resulting nonlinear
Similar to Doshi et al. (2023), we initialize &. > 0 with fake visit count for well-defined x (x] at every step. In reality, memory is allocated for states that have received actual visits, enabling adaptive storage for x.
Detailed overview of Algarithm applied to advanced MCMC samplers are in Appendix C.
5

---

History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs
kernels. In contrast, our HDT (6) decouples neighbors in the target distribution itself, which eliminates the need to eval- uate transition probabilities for all neighbors at each step, offering substantial computational savings and compatibility with both reversible and non-reversible samplers.
The full proof of Theorem 3.3 is in Appendix E, where we leverage the existing asymptotic analysis from the SA lit- erature (Delyon et al., 1999; Fort, 2015), similarly used in Doshi et al. (2023, Appendix C). However, the primary tech- nical challenge arises from handling non-reversible Markov chains, which is excluded from Doshi et al. (2023) by the nature of their kernel design. We proceed with our analysis that is specifically tailored to the augmented state space which the non-reversible Markov chain is defined, and solve mismatch issue between the augmented space and the original space by only tracking the marginal empirical measure x E Int(2)) in the original space X. Theorem 3.3 highlights two appealing features of HDT-MCMC: (i) preserves the unbiased sampling by converging to the true target μ. (ii) It offers an (11/a) variance reduction, achiev- ing similar near-zero variance phenomenon of SRRW but without additional computational overhead or the need for time-revessibility When = 0, we recover the baseline scenario π [[X] = f and VHDT = Viuse as expected.
3.2. Performance of HDT-MCMC
We next analyze HDT-MCMC regarding (i) almost-sure convergence of the empirical measure Xn to μa, and (ii) an ((1/a) variance reduction relative to the base MCMC sampler with true target J.
Observe that (2) allows us to decompose x,+1 as
1
Xn+1 X. + n +
[T[xx] xx.x
(xx++) T (x..
[xxx))
noise term which is the standard step in stochastic approximation (SA)
deterministic drift
with controlled Markovian dynamics (Kushner & Yin, 2003; Benveniste et al., 2012: Borkar, 2022). It can be viewed
as combining a deterministic drift π [xm] - Xn, towards the solution of the ODE
Moreover, Theorem 3.3 leads to an instant result as follows.
Corollary 3.4. Suppose two MCMC samplers S1 and S converge je with limiting covariances VS. and VSa sat- isfying VSi < =VS+4 Applying HDT framework to both, yielding VS.HDT(a)) and VS..iD))) (ai), preserves the ordering:
(9) and noise term 6x x.+1 π [_ The ODE viewpoint clar- ifies the global asymptotic stability of μe, while the noise
(t) π [x(())] x(t)
term characterizes fluctuations around p.
VS,IID(()) 3 VS, Ya 2 0.
Lemma 3.2. For [x]] in (6), the ODE (9) has a unique fixed point pt, which is globally asymptotically stable.
The proof is straightforward from (10). Hence, any known covariance orderings between reversible and nen-reversible samplers (see lee et al. (2012); Maire et al. (2014); Bierkens (2016); Andrieu & Livingstone (2021)) carry over to our HDT-MCMC framework, whereas SRRW cannot accommo- date non-revee rov-reversible Markov chains.
Proofs follow by showing that target μ is the unique stable equilibrium and employing standard Lyapunov stability the- ory, as detailed in Appendix D. For the iteration x,, in (2), we need to additionally account for the noise term driven by a history-dependent MCMC from Algorithm 1. We impose the following assumption on x,, throughout the paper.
3.3. Comparative Analysis of Computational Costs
Assumption 1. x,, E Int( for all n 2 0 almost surely.
We now compare the performance of our HDT-MCMC to SRRW (Doshi et al., 2023) under a fixed total computa- tional budget B. Although both methods achieve an O(1/a) variance reduction, HDT-MCMC requires significantly less computation per sample.
Assumption 1 guarantees Wr (t) > 0 almost surely for all e X and n 20 0, keeping π| [x] well-defined at each step. This type of assumption is standard in the SA literature (Fort, 2015; Borkar, 2022: Li et al., 2023). In practice, it can be enforced using nuncation-based methods within (2), as discussed in Doshi et al. (2023, Remark 4.5 and Appendix E). These methods effectively prevent any component xx, (i) from approaching zero, thus maintaining x,, E (E.). Un- der this assumption, we obtain the following:
Because SRRW mandates a time-reversible base MCMC sampler, we restrict our comparison to the same reversible chain (as illustrated in Boxes @ and + of Figure 1). Let a (resp. b₂) E (0, oo) be the computational cost of the i-th sample in HDT-MCMC (resp. SRRW). Define:
Theorem 3.3 (Ergodicity and CLT), HDT-MCMC in Algo- rithm 1 satisfies
THE (B) - max (1 + 02 + ... + ag $ B}
SRRW (B) - max(k' b1 + b2 + +.... by S B)
(a) Xn - f almost surely as n + co.
so that THDT (resp. TRRE (B)) represents the total num- ber of samples that HDT-MCMC (resp. SRRW) can gener- ate before hitting the budget B. Intuitively, under the same
(b) Vn(xx- 14)
7000
NO, VHD (a)), where
dist. VIDT
1
(a)
2a + V
(10)
and Vhaw is the limiting covariance of the base MCMC
Two symmetric matrices M,, M2 follow M, M2 (or M, 2 M2) if M2- M, is positive (or negative) semi-definite.
sampler (reversible or rev-rrvvrs) with target μ in (3).
6

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
budget, SRRW's higher per-sample cost yields fewer total samples. To quantify this effect, we now compare these two frameworks under the same but large amount of total budget B instead of the number of samples as done in Section 3.2.
updates the unbiased MCMC estimator (f), aiming to approximate the ground truth f. such as a global attribute of the unknown graph, and their expressions are defined in the following:
Clearly, we have (B) - Do and T (B) + oo as B + co. Let Xn (resp. yn) be the empirical measure of HDT-MCMC (resp. SRRW). As B - co, both B) and (B still converge almost surely to μa, an instant result of our Theorem 3.3(a) and Doshi et al. (2023, Theorem 4.1). Analogous to our Theorem 3.3, rather than evaluating at n oc, we quantify how HDT-MCMC and SRRW behave under B- oo via the following cost-based CLT:
1 T E ((x),
(T(
/ piS(i). VEX
Equivalently, we can rewrite the MCMC estimator as (f( = fxx since XT = T _T 5x, and f f(i), where f a [f(i]]kxx E RI Thus, the cost-based variance of (f) for HDT-MCMC and SRRW is derived by left multiplying f into (11) and (12), yielding
Theorem 3.5 (Cost-Based CLT). Suppose that as B B- 00, B/THD (B) + C!!DT, B/TSRRR (B) + SRRW a.s.
(1 ( (f) f)
T NO, HDT (a)),
(13)
Then, we have
dist.
VB BB(xpuo(BB) u))
B+000 CO,, CH V (a)) (11)
Vi (f)
T N(0, Var SREW (a)), (14)
dist.
dist.
(Syyss 1))
B B+x,, N(0,
CIREW Y (a)) (12)
where Var (a) C ft VIlT(() f. and Var (a)
Var CSERW 8 VTVW fa) respectively. By Lemma 3.6 and the
dist.
where (a) given by (10), and V (a) by (5).
Loewner ordering in footnote 4, we have for any a > 0,
We leverage the random-change-of-tinn 2013) and Slutsky's 's theorem (Ash & Doléans- 2000)
theory (Billingsley,
Var (a) S (2/BIIN((I)) Var (a),
to transform our time-basee based CLT (Theorem 3.3) to the cost- based CLT (Theorem 3.5), with details in Appendix F.
which translates into at least factor of 2 (/E( times smaller cost-based variance of the MCMC estimator (fr(s) than the case with SRRW. In addition, unlike SRRW, HDT- MCMC also accommodates non-reversible base samplers (see Corollary 3.4), further enhancing efficiency in many applications.
In practice HDT-MCMC's per-sample cost CHRI can be significantly smaller than CSREW because the latter must pre- compute the transition probability Kay [x] at each step. As a concrete example, we focus on the MH framework as the base sampler utilized in many advanced MCMC schemes
(Liu et al., 2000; Green & Mira, 2001; Lee al., 2012: Bierkens, 2016; Zanella, 2020; Chang et al., 2022). As- suming that computing the proposal probability Qi and inquiring ias incurs e units of cost per each pair (i,,j) E E, it requires 2c costs for Ay [x] in (8). Thus, HDT-MCMC spends 2c per sample, whereas SRRW incurs (1) sub- ject state as discussed in Section 1.2. The following lemma shows the ordering of their cost-based covariances:
4. Simulations
We design series of experiments to evaluate the perfor- mance of HDT-based MCMC methods in graph sampling tasks. Our goal is to compare HDT-MCMC with various advanced MCMC algorithms, including both reversible and non-reversible Markov chains, and compare HDT-MCMC with SRRW within the same total computational budget.
Lemma 3.6. The cost-based covariances between SRRW and HDT-MCMC in (11) and (12) are ordered follows:
4.1. Simulation Setup
We conduct experiments on two real-world graphs, i.e., face- book (4039 nodes with 88234 edges) and p2p-Gnutella04 (10876 nodes with 39994 edges) from SNAP (Leskovec & Krevl, 2014). We use uniform target distribution μ1 | 1 throughout this section while deferring the experiments of non-uniform target to Appendix H.6. In the reversible set- ting, we apply the standard MH algorithm (MHRW) and MTM with locally balanced weights and K = 3 proposed candidates (Chang et al., 2022). In the non-reversible setting, we adopt MHDA (Lee et al., 2012). Additional experiments on WikiVote, p2p- 22p-Gnutella08, and reverssbrli 2-cycle Markov chains appear in Appendix H. To assess conver-
y HOT (a) = (2/E:- (WWII) C.SRAW y SARW (a).
See Appendix G for the proof. Lemma 3.6 implies that the cost-based covariance of HDT-MCMC at least a fac- tor of 2/E][V((i]] times smaller than that of SRRW in Loewner ordering for each a, suggesting universal ad- vantage. This factor becomes more pronounced in dense or nearly complete graphs, where the average neighborhood size is [i)] >> 2.
For unbiased graph sampling, at each time T, the sampling agent records state Xr, obtains the value f(Xr) R, and
7

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Table 1. Mean (std error) TVD and NRMSE n 15,000 steps on facehook graph under different No groups and fake visit counts Xo- All std error values are in units of 10-
Initial State (Xo)
Fake Count (Xp)
Low Dog
High Deg
Deg
Non-unif
Unif
Method
TVD
NRMSE
TVD
NRMSE
TVD
NRMSE
TVD
NRMSE
TVD
NRMSE
HD
0.372 (1.221)
0.027
0.371 (1.296)
0.029
0.371 (1.246)
0.028
0.371 (1.281)
0.028
0.371 (1 (1.246)
0.028
HDT-MTM
0,283 (1.199)
0.070
0.284 (1.280)
0.068
0.288 (1.751)
0.098
0.285 (1.456)
0.047
0.285 (1.496)
0.062
HDT-MHDA
0,364 (1.230)
0.026
0.365 (1.292)
0.028
0.365 (1.281)
0.027
0.365 (1.246)
0.028
0,366 (1.258)
0.027
gence, we use the total variation distance
effect is not reflected in the number of steps. We shall ex- amine SRRW's performance under fixed budget in the next experiment. We do not combine SRRW with MTM in this experiment due to its heavy computation in P.j for all pos- sible combinations of K intermediate proposed candidates, whereas HDT integrates seamlessly into MTM without ad- ditional cost. Moreover, we conduct the experiment on the effect of different a values influence HDT--HRWW algo- rithm in Appendix H.4 and observe consistent improvement with smaller TVD using larger a.
TVD(xa, 11) _ Xn pell1
for the distance between the empirical measure x, of the collected samples and the target J.. We also evaluate nor- malized root mean squared error
NRMSE( Li,, (h) V (f)
for graph-based group-size estimation with test function f defined in Appendix H.2. Each experiment consists of 1000 independent runs, and one-third of the total iterations is used as the burn-in period.
4.3. Robustness to Different Initializations
To demonstrate that HDT-MCMC is robust to different ini- tializations, we evaluate its performance when initialized at various nodes, using base chains MHRW, MTM, and MHDA for the HDTT-nnhacedd versions. We show the experimental results for the Facebook graph in Table and include the results for other graphs in Appendix H.3. In particular, we examine the effects of both initial state Xo and the fake visit counts Xg. The initiate state Xo is randomly chosen from either low-degree group (where the node's degree is smaller than the average degree) or high-degree group. This is to test the sensitivity of our algorithm starting from sparse or dense regions. On the other hand, fake visit count X, is initialized using one of the following settings: 'Deg" (proportional to node degree, c.g., ã, (i) for all i E [NV), 'Non-unif" (a non-uniform draw from Dirichlet distribution with de- fault hyperparameter 0.5), and 'Unif' (same initial count across all nodes, e.g., 3. = for all i E [N]). In Table 1, both TVD and NRMSE show consistent performance when starting from either the low-degree group or the high-degree group. Similarly, a robust result is observed when using different settings of fake visit counts.
p2p GrutellsDE Graph
1.0
vieww HET SHER (e- 5)
HH
HOT (a
0.-
HTM
MHES ig- 9
MIDA
NOTHIEAASS -5)
0.7
NRSASE
0.06
smnt (2=3)
0.5
0.62
02
5050
20003
Steps
Steps
Figure 2. TVD and NRMSE Comparison of MDT-MCMC with base chain MHRW, MTM, and MHDA.
4.2. Comparison of Base MCMC and its HDT Version
We first compare each base MCMC algorithm with its HDT- enhanced version, setting a 5 in the target π [x] in (6). Figure 2 shows the average TVD and NRMSE for MTM and MHDA, with MHRW serving as a benchmark. In both cases, MTM and MHDA outperform MHRW when targeting μ.. which aligns with the theoretical results in Chang et al. (2022) and Lee et al. (2012). Moreover, the HDT-enhanced versions (HDT-MTM and HDT-MHDA) consistently attain lower TVD and NRMSE than their respective base algo- rithms, indicating faster convergence μr, consistent with Theorem 3.3. A similar trend is observed in other graphs us- ing TVD and NRMSE metrics (see Appendix H.2). Notably, SRRW (with MHRW as its base) achieves the lowest TVD and NRMSE among all methods but entails substantially higher computational overhead to obtain one sample, whose
4.4. Computational Cost Comparison with SRRW
We compare HDT-MHRW and SRRW under fixed com- putational budget B. At each iteration, SRRW needs to compute or retrieve transition probabilities for every neigh- bor due to the nature of the kernel design (1), whereas HDT only updates the proposal for a single candidate. This com-
'NRMSE inherently measures the deviation from the true value, hence confidence intervals are provided for this metric.
8

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
putational cost aligns with the concerns of the (()( eval- uations in the proposal distribution highlighted in Zanella (2020); Grathwohl et al. (2021) in high-dimensional spaces. In graph sampling, simply counting samples to assess perfor- mance can be misleading under rate-limited API constraints, e.g. online social network sampling (Xu et al., 2017: Li et al., 2019). The performance gap between HDT-MHRW and SRRW in budget B increases with the degree of the node, as proved in Lemma 3.6. Figure 3 shows that under the same total budget, HDT-MHRW consistently achieves lower TVD and NRMSE than SRRW. The discrepancy is even more pronounced in the Facebook graph in both plots, where the average degree (43.6) far exceeds that of p2p- Gnutella04 (7.4), supporting our discussion after Lemma 3.6, where larger neighborhood size leads to more perfor- mance advantage of HDT-MCMC compared to SRRW.
true visit count. We examine HDT-MCMC using an LRU cache with size [C] = r|X] where 0 < < 1. In Figure 4, the average TVD of HDT-MHRW with LRU outperforms MHRW even without exact empirical measure due to it limited capacity. In most scenarios, HDT-MHRW with LRU leads to 10% smaller TVD than the base MHRW with over 90% memory reduction. The performance of HDT-MHRW with LRU is robust to the choice of in most cases. Due to space constraint, we defer more result of LRU scheme in plus-combined graph (over 100K nodes) to Appendix H.5.
face Graph
p2pp Ge.--e
3.0
VHEW
is -5) with
0.5
4000 with ro
0.5
Matia 5)) withh to
0.4
HCT siW tei 31 with rib.l
unai ke- 3) with mi0.00
HET la with
NET-MARA to 55-5) 1/otthr-.22 25
6:30
1898
0.7
0.7
0.8
025
di Ceareiate ppm
6.20
6.5
NRMSE
0.1
033
0.4
0.6
4000 Ledet Stops
10980
Steps
20000
25000
0.5
130
Figure 4. Performance of HDT-MHRW with LRU cache scheme.
SAAR Dombook
505
HOT NOT-MIWWW ca Grioelaee
03
3000 10000 isdes
z0des 2550s 20000
500
3600
22000 2000 25505 20000 Computational Costs
18081
Computational Costs
Figure 3. TVD and NRMSE Comparison between HDT-MHRW and SRRW under budget constraints.
5. Conclusion
In this paper, we propose history-driven target (HDT) framework for MCMC sampling on general graphs. By embedding repf-rcpy in the target rather than the tran- sition kernel, HDT maintains unbiased sampling with a lightweight design and provides an O(1/a) variance reduc- tion without high computational cost or time-reversibility constraints from SRRW. Our theoretical analysis covers both reversible and non-reversible MCMC samplers, while empirical results on real-world graphs show robust perfor- mance gains and reduced computational overhead. To han- dle memory limitations, we introduce a Least Recently Used (LRU) cache scheme, enabling partial tracking of the em- pirical measure without loss in sampling efficiency. Future directions include more refined memory approximations for exponentially large configuration spaces and applications to high-dimensional statistical inference and network analysis.
4.5. Least Recently Used (LRU) Cache Scheme
A core challenge in HDT-MCMC, as noted in Section 1.2, involves handling large graphs or exponentially growing configuration state spaces, where storing the entire visit counts x E RI of | dimension becomes infeasible. To address this challenge, we propose a memory-efficient Least Recently Used (LRU) cache strategy and emulate its effect on real-world graphs that serves as a pilot study prior to full deployment in large configuration spaces (beyond this paper's scope).
The essential idea is to track only recently visited states, discarding the least-recently used when capacity in cache C is reached. This leverages temporal locality, as non- neighboring states do not affect self-repellency. Unlike sparsification methods (Verma et al., 2024: Barnes et al., 2024), which ignore the walker's position, LRU's local sim- plicity aligns with our HDT-MCMC. For a neighbor j & C of current state i, we approximate its frequency via
A Acknowledgments and Disclosure of Funding
We thank anonymous reviewers for their constructive com- ments and Bohyung Han from Scoul National University for the valuable discussions. This work was supported in part by National Science Foundation under Grant Nos. CNS- 2007423, IIS-2421484 and by Brain Pool program funded by the Ministry of Science and ICT through the National Research Foundation of Korea (No. RS-2024-00405 0040000))))
ス N
Σ ax/Pu.
(15)
kENGinee
This approach approximates L which mimics (6) via temporal closeness among states frequently visited around i, allowing the sampler to maintain self-repe without

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Impact Statement
Byshkin, M., Stivala, A., Mira, A., Krause, R., Robins, G., and Lomi, A. Auxiliary parameter meme for exponential random graph models. Journal of Statistical Physics, 165: 740-754, 2016.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chang. H., Lee, C., Luo, Z. T., Sang, H., and Zhou, Q. Rapidly mixing multiple-try metropolis algorithms for model selection problems. Advances in Neural Informa- tion Processing Systems, 35:25842-25855, 2022.
References
Alon, N., Benjamini, I., Lubetzky, E.,, and Sodin, S. Non- backtracking random walks mix faster. Communications in Contemporary Mathematics, 9044):555-633, 2007.
Chen, F., Lovász, L., and Pak, I. Lifting markov chains to speed up mixing. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp. 275-281, 1999.
Andrieu, C. and Livingstone, S. Peskun-tierney ordering for markovian monte carlo: beyond the reversible scenario. 2021.
The Annals of Statistics,
Chen, T.LL. and Hwang, C.-R. Accelerating reversible markov chains. Statistics & Probability Letters, 83(9): 1956-1962, 2013.
Apers, S., Ticozzi, F., and Sarlette, A. Lifting markov chains to mix faster: limits and opportunities. arXiv preprint 2017.
Delyon, B. Stochastic approximation with decreasing gain: Convergence and asymptotic theory. Technical report, Université de Rennes, 2000.
Ash, R. B. and Doléans-Daie Dade, C. A. Probability and mea- sure theory. Academic press, 2000.
Delyon, B., Lavielle, M., and Moulines, E. Convergence of stochastic approximation version of the em algorithm. Annals of statistics, pp. 94-128, 1999.
Ayache, G., Dassari, V., and El Rouayheb, S. Walk for learning: A random walk approach for federated learning from heterogeneous data. IEEE Journal on Selected Areas in Communications, 41(4):929-94) 940, 2023.
Diaconis, P., Holmes, S., and Neal, R. M. Analysis of a nonreversible markov chain sampler. Annals of Applied Probability, pp. 726-752, 2000.
Barnes, L., Chow, T., Cohen, E., Frankston, K., Howard, B., Kochman, F., Scheinerman, D., and VanderKam, Efficient unbiased sparsification. arXiv preprint arXiv:2402.14925. 2024.
Doshi, V., Hu, J., and Eun, D. Y. Self-repellent random walks on general graphs-achieving minimal sampling variance via nonlinear markov chains. In International Conference on Machine Learning, 2023.
Benveniste, A., Métivier, M., and Priouret, P. Adaptive algorithms and stochastic approximations, volume 22. Springer Science Business Media, 2012.
Even, M. Stochastic gradient descent under markovian sam- pling schemes. In International Conference on Machine Learning, 2023.
Bhamidi, S.. Bresler, G., and Sly, A. Mixing time of expo- nential random graphs. The Annals of Applied Probability, pp. 21 2146-2170, 2011.
Fort, G. Central limit theorems for stochastic approxima- tion with controlled markov chain dynamics. ESAIM: Probability and Statistics, 19:60-80, 2015.
Bierkens, J. Non-reversible cattoppolis-hsttngss Statistics and Computing, 26(6):1113-1228, 2016.
Gjoka, M., Kurant, M., Butts, C. T., and Markopoulou, A. Practical recommendations on crawling online social networks. IEEE Journal on Selected Areas in Communi- cations, 1972 2011.
Billingsley, P. Convergence of probability measures. John Wiley & Sons, 2013.
Borkar, V. Stochastic Approximation: Dynamical Sys- tems Viewpoint: Second Edition. Texts and Readings in Mathematics. Hindustan Book Agency, 2022. ISBN 9788195196111.
Grathwohl, W., Swersky, K., Hashemi, M., Duvenaud, D., and Maddison, C. Oops took a gradient: Sealable sam- pling for discrete distributions. In International Con- ference on Machine Learning, pp. 3831-3841. PMLR, 2021.
Brémaud, Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31. Springer Science & Business Media, 2013.
Green, P. J. and Mira, A. Delayed rejection in reversible jump metropolis-hastings, Biometrika, 88(4):1035-1053 2001.
Brooks, S., Gelman, A., Jones, G., and Meng. X. Handbook of Markov Chain Monte Carlo. CRC Press, 2011.
10

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Grover, A. and Leskovec, J. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discov- ery and data mining, pp. 855-864) 2016.
Leskovec, J., Kleinberg, J., and Faloutsos, C. Graphs over time: densification laws, shrinking diameters and possible explanations. ACM SIGKDD, pp. 177-187, 2005.
Li, X., Liang, J., and Zhang. Z. Online statistical inference for nonlinear stochastic approximation with markovian data, arXiv preprint arXiv: 2023.
Hastings, W. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1)997-109, 1970.
Li, Y. Wu, Z., Lin, S., Xie, H., M., Xu, Y., and Lui, J. C. Walking with perception: Efficient random walk sampling via common neighbor awareness. In 2019 IEEE 35th International Conference on Data Engineering (ICDE),
Hendrikx, H. principled framework for the design and analysis of token algorithms. In International Confer- ence on Artificial Intelligence and Statistics, pp. 470-489. PMLR, 2023.
pp. 962-973. IEEE, 2019.
Hermon, J. Reversibility of the non-backtracking random walk. In Annales de l'Institul Henri Poincaré, Proba- bilités et Statistiques, volume 55, pp. 2295-2319. Institut Henri Poincaré, 2019.
Liu, J. S., Liang, F., and Wong, W. H. The multiple-try method and local optimization in metropolis sampling. Journal of the American Statistical Association, 95(449): 121-134, 2000.
Ma, Y-A.,, Chen, T., Wu, L.., and Fox, E. B. A unifying framework for devising efficient and irreversible mcme samplers. arXiv preprint
Hinton, G. E. A practical guide training restricted boltz- mann machines. In Neural Networks: Tricks of the Trade: Second Edition, pp. 599-619. Springer, 2012.
1e0:: 2016.
Mahadevan, P., Krioukov, D., Fomenkov, M., Dimitropou- los, X., Vahdat, A., et al. The internet as- topology: three data sources and one definitive metric. ACM SIG- COMM, 36(1):17-22) 2006.
Hu, J., Doshi, V., and Eun, D.-Y. Efficiency ordering of stochastic gradient descent. In Advances in Neural Infor- mation Processing Systems, volume 35, pp. 15875-15888, 2022.
Maire, F., Douc, R., and Olsson, Comparison of Asymp- totic Variances of Inhomogeneous Markov Chains with Application to Markov Chain Monte Carlo Methods. The Annals of Statistics, 2(4):1483-1510 2014.
Hu, J., Doshi, V., and Eun, D. Y. Accelerating distributed stochastic optimization via self-repellent random walks. In International Conference on Learning Representations, 2024a.
Masuda, N., Porter, M. A., and Lambiotte, R. Random walks and diffusion on networks. Physics reports, 716: 1-58, 2017.
Hu, J., Ma, Y.-T., and Eun, D. Y. Does worst-performing agent lead the pack? analyzing agent dynamics in unified distributed sgd. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024b.
Metropolis, N., Rosenbluth. A. W., Rosenbluth, M. N., Teller, A. H., and Teller, E. Equation of state calculations by fast computing machines. The journal of chemical physics, 2166):188711092, 1953.
Khalil, H. Nonlinear Systems. Pearson Education. Prentice Hall, 2002.
Kim, J., Zaghen, O., Suleymanzade, A., Ryou, Y., and Hong, S. Revisiting random walks for learning graphs. arXiv preprint vrXiv:2407.01214 2024.
Nakajima, K. and Shudo, K. Random walk sampling in so- cial networks involving private nodes. ACM Transactions on Knowledge Discovery from Data 17(4):1-28. 2023.
Kushner, H. and Yin, G. G. Stochastic approximation and re- cursive algorithms and applications, volume 35. Springer Science & Business Media, 2003.
Neal, R. M. Improving asymptotic variance meme esti- mators: Non-reversible chains are better. arXiv preprint math/0407281, 2004.
Lee, C.-H., Xu, X., and Eun, D. Y. Beyond random walk and metropolis- hiatttigiiss samplers: why you should not back- track for unbiased graph sampling. ACM SIGMETRICS Performance evaluation review, 40(1)3319-330 2012.
Olston, C., Najork, M., et Web crawling. Founda- tions and Trends@ in Information Retrieval, 4(3):175- 246, 2010.
Pandolfi, S., Bartolucci, F., and Friel, N. A generalization of the multiple-try metropolis algorithm for bayesian estima- tion and model selection. In Proceedings of the thirteenth international conference on artificial intelligence and
Leskovec, J. and Krevl, A. SNAP Datasets: Stan- ford large network dataset collection. http://snap. stanford. edu/ data, June 2014.

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
statistics, pp. 581-588. JMLR Workshop and Conference Proceedings, 2010.
Verma, B. D., Pratap, R., and Dubey, P. P. Sparsifying count sketch. Information Processing Letters, 186:106490, 2024.
Perozzi, B., Al-Rfou, R., and Skiena, S. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference Knowl- edge discovery and data mining. pp- 701-710, 2014.
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., and Kong, X. Random walks: A review of algorithms and applications. IEEE Transactions on Emerging Topics in Computational Intelligence, 4(2):95-107, 2019.
Placed, J. A., Strader, J., Carrillo, H., Atanasov, N., Indel- man, V., Carlone, L., and Castellanos, J. A. A survey active simultaneous localization and mapping: State of the art and new frontiers. IEEE Transactions on Robotics, 3963)1666-1705, 2023.
Xiang, Y., Zhu, D., Lei, B., Xu, D., and Zhang. R. Efficient informed proposals for discrete distributions via newton's series approximation. In International Conference on Ar- tificial Intelligence and Statistics, pp. 7288-7310 PMLR. 2023.
Pynadath, P., Bhattacharya, R., HARIHARAN, A. N., and Zhang, R. Gradient-based discrete sampling with auto- matic cyclical scheduling. In ICML 2024 Workshop on Structured Probabilistic Inference & Generative Model- ing, 2024.
Xie, H. Yi, Li, Y., and Lui, J. C. Optimizing random walk based statistical estimation over graphs via bootstrapping. IEEE Transactions Knowledge and Data Engineering, 35(3):2916-2922 2021.
Xu, X., Lee, C.-H., al. Challenging the limits: Sampling online social networks with cost constraints. In IEEE Infocom 2017-IEEE Conference Computer Communi- cations, pp. 1-9. IEEE, 2017.
Rhodes, B. and Gutmann, M. U. Enhanced gradient-based meme in discrete spaces. Transactions on Machine Learn- ing Research, 2022.
Robert, C. P. and Casella, G. Monte Carlo statistical meth- ods. Springer, 2013.
Zanella, G. Informed proposals for local meme in discrete spaces. Journal of the American Statistical Association, 115(530):852 865, 2020.
Sun, H., Dai, B., Sutton, C., Schuurmans, D., and Dai, H. Acy-scale balanced samplers for discrete space. In International Conference on Learning Representations, 2023a.
Zhang. R., Liu, X., and Liu, Q. A langevin-like sampler for discrete distributions. In International Conference on Machine Learning, pp.
PMLR, 2022.
Sun, H., Dai, H., Dai, B., Zhou, H., and Schuurmans, D. Discrete langevin samplers via wasserstein gradient flow. In International Conference on Artificial Intelligence and Statistics, pp. 6313. PMLR, 2023b.
Sun, T., Sun, Y., and Yin, W. On markov chain gradient descent. In Advances in neural information processing systems, volume 31, 2018.
Suwa, H. and Todo, S. Markov chain monte carlo method without detailed balance. Physical review letters, 105 (226:120003, 2010.
Thin, A., Kotelevskii, N., Andrieu, C., Durmus, A., Moulines, E., and Panov, M. Nonreversible meme from conditional invertible transforms: complete recipe with convergence guarantees. arXiv preprint arXiv:2012.155500 2020.
Triastcyn, A., Reisser, M., and Louizos, C. Decentralized learning with random walks and communication-efffccaa adaptive optimization. In Workshop on Federated Learn ing: Recent Advances and New Challenges (in Conjunc- tion with NeurlPS 2022), 2022.
12

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
A. Matrix Form of Covariance Matrix (4)
The multivariate version of Brémaud (2013, eq. (6.33) shows that
|2| Σ ((x)) 1(x)) ;) (arr((((Xo)) +2
[ Σ ((xx)
((xx))
-F)
lim 1000
f
(16)
i=2
where ((X) E IRd S (O), E ERIxix and Var (f pp²) )f-
Replacing the function f(-) in (16) with our canonical vector )(.) defined in Section 2, we have
{ Σ 6x. 11)
Lox
V
lim 10x0
E
X
As
=D md
+2
Duvin?
X3
1=2
X
X
A;
Dμ
Σ
T
m1 T
+
+DD, #
X y.u!
X 1 A D
-=((11²) ut
Σ
1 ansaa
++
A D p..
X3
where the second equality is because I [ and the third equality comes from the fact that I E v.ue?
B. Proof of Lemma 3.1
(a) Following C2, we let n, πr[x] = Esex ((1ya1y) for some continuous differentiable function f Ryo x Rs0 + Ry0 : (z,
+
(). Then, CI implies that for any scalars c1, > 0,
f (xi,Hs)
(17)
ΣvEX ff (ciek, c2H4)
ΣLEx If (Io px)
Now we show that function f has a specific form
f'r 02p) g(c1,,2)5(x.1))
(18)
for any u (0, 1), 02,02 and some continuous differentiable function g (0, 00)2 Boo (2, - g((), 02)-
Proof of (18). Rearranging (17) gives
Etex (131))221a) f (I;, u4). Σrex I (IRR)M))
ff (CLT;
Then, with slight abuse of notation, we take glc,, C2 x, x.) Exex Hap Etex (axitt))
In other words,
f (c124, 02/4) = g(C1, C2 x, (x,,))
(19)
for any i E X' and arbitrary choices x, f E Int(E). Then, we show that function g(c1, C22 x, (1) is independent of parameters x, ps corresponding to (18).
13

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Consider pairs of probability vectors (x, (4) and (x, ji), whose i-th coordinate identical, i.e., 24 Ti 14 Da.
Then, (C1 c22;) f (c; c2ãt), and [( [[,, Rt)) By (19), have g((1, C2, x,) g(11, (2 22,X,, ja).
Similarly, we construct another pair (&. ( such that 2; 33 and P. Bi for j-th coordinate (where i * j), then we have g(c1, C2, X. ( = (C1, 02, X, fi).
Therefore, the pair (x, pi) serves as a 'brdgge' to (x, pe) and (x, (i), leading to g C x, M4) g(c,, 02. 8, jt).
(20)
This implies that for a given pair (x,4), 14., we can always construct distinct pair (R, pi) such that (20) holds true, indicating that function g must be identical for any pair (x, 14). Hence, function cannot actually depend on xor μe; it must be a function (c1, o2) alone.
Next, we have the following proposition regarding the exact form of function f.)).
Proposition B.1. The function fx. μ)) satisfying (18) must be of the form
[(x, 11) Cx p!²
(21)
for some positive constant C and P1 I..
Proof of Proposition B.I. Taking the logarithm of both sides of (18) gives:
log f(ex,, c2p) log g(1, 02) log f(x p))
(22)
Define function F such that
F(log z, log log (a. 14)
Substituting function F to (22) gives:
F(log ci + log x, log 02 + log log. 02) + F F'log log
Focusing on partial derivatives, let 02 1, i.e., log C2 isolate x. Then,
F F(log + log x, log μ)) F(log log ô log cj
log g(c1, 1).
i log C1
As C1 1, Tl log (1, 1) approaches some constant P1 irrelevant p. Thus, the partial derivative of function F(oog x, log ()) w.r. log x a constant and we have the form
F(log x. log (4) = log + some function of log /s.
Similarly, the partial derivative of F(log log (4) w.r.t log y is constant Pa R independent of x. Thus, we have
F(log log μ) pı log x + 02 log μ + b = log ((x, 1)
where b is constant. Therefore,
f(x,1) e'
which completes the proof.
Following Proposition B.1, for P1-P2 E IR, we have
ny (x) x 0r p
(23)
'We admit that this result is likely be well known but were unable locate reliable Thus, provide the proof for completeness.
14

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
where the constant C' in Proposition B.1 is absorbed into the normalizing constant. Then, based the condition π [/x f in C3, we have
11 22 P Σx
Ti [0]
14g-
Pk
Since this holds for any i E X' we have
P2-1
14
P1
M4
( Mi
(1-P2)/01
P4
Hj
Hly
thus p2)/2) = 1, or equivalently, P1 + P2 = 1, and
n,(x]] ur( p4) ( Ppp
Now, considering C4, we need to prioritize the node that is under-sampled, i.e., node with v,/ μ4 < should have a higher probability than μa, such that P2 I 1. Thus, a P2 - z 0, and [i[x] oc pi(a:/p;)= which completes the proof.
C. Implementation of Algorithm For Advanced MCMC Samplers
C.1. Multiple-try Metropolis algorithm with locally balanced weighs function (MTM)
We followed the MTM algorithm in (Chang et al., 2022), where weights function incorporated locally balanced function h introduced by (Zanella, 2020). Specifically, the locally balanced weights function is defined as
Mg Q3 11
w (iii)
Vi,jE,
(24)
where Q the random walk proposal. Thus, the corresponding locally balanced weights function of HDT-MTM is defined as
TTj [x, (Qj T. X Qi5
Wx., (jlb) = 1
ViJEx
(25)
where x is the empirical measure at step Typical choices of function h(u) include Vū, max(1, u), min(1, u), u/ + u) and 1 + u. In the simulation in Section 4, we choose h as h(u)) = Vu, and the algorithm of HDT-MTM is described as below.
Algorithm 2 HDT-MTM
Input: The number of candidates K, weight function w parameterized by x defined in (25), the number of iterations T. Initialization: state X, EX, visit count ā(i) > 0, VieX. for 0 T do
Step 1:Draw Yi.... .ÝK u.a.r. from (tom.((X,)) and compute Wx,, (Y,)),,) for h [K] Step 2: Select j E [K] with probability proportional to wxx., (X, and let Y = Y; from.((Y) NYY and compute aMTM Step 3: Sample XI,..., Xx-1 u.a.r. from
ΣjE[K] Uxx, (Y,1X,))
QMTM min
Wx., (X,lY) ΣjE(k-1| Wxx, (X
Step 4: With probability OMTM, accept Y and let X = Y; otherwise, Xnt1 X,.
Stpe 5: Update visit count ((X,+1) + ((X,+1) +1. end for Output: A set of samples {T
C.2. Metropolis-Hasting algorithm with delayed acceptance (MHDA)
MHDA (Lee et al., 2012) a nonreversible chain where reduces the probability of the process from backtracking. Unlike standard MH always taking the next step once it accepted, MHDA avoid non con-backtracking by re-proposing other neighboring
15

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
states uniformly with another acceptance probability whenever is about backtrack. This acceptance probability is related the base time-reversible chain P with target μ.. It is proven to ensure the asymptotic variance of MHDA is no larger than that of MHRW. To apply our framework, we change the target distributiony inside the first and the second The detailed HDT-MHDA algorithm is described in Algorithm 3.
acceptance probability by xxx].
Algorithm 3 HDT-MHDA
Input: The number of iterations T. Initialization: state Xo EXX, last visit Yo Xo, visit count 0, ViE.. for
T do Step 1: Draw & u.a.r. from from.((X, (Xx,
Step 2: Generate p ~ (0,1)) 1) Te. I.lx.,dd..... TX,, [.]])( then
if S min
yn = and d(xx)) then
Choose u.a.r from ((X.)) {1: and generate q ~ U(0, 1)
if q S min { 1, min 1,
xx, N xx,(), )²) max (1,
xx (x. [d(k) 21)
then
ne Xm ((
Xn+1 Yn X,
else
Xn+1 = k, Xn+1 = Xn
end if
else
Xa+1 k, Yn+1 Xx
end if
else
Xn+1 = Xn, Yn+1 = Yn
end if
Step 3: Update visit count ((X++1) + x(Xn+1) +
end for
Output: A set of samples (X,)
C.3. 2-cycle MCMC
HDT--2-cycle MCMC alternates between two reversible Markov chains (Pi and P2) targeting the history-dependent distribution π [x]. At each iteration n, n is even, the next state X is generated using Pi; odd, P2 is used. Both chains adaptively target π r[xx,. via the updated empirical measure x,, at each step. After sampling the state Xn+1, the visit count t(Xn+1) is incremented by 1, which will guide exploration by penalizing over-visited states, detailed in Algorithm 4.
Algorithm 4 HDT-2-cycle MCMC
Input: Two reversible chain P1 and Pa with respect target μ4 the number of iterations T. Initialization: state Xo X,, visit count 2, V. for 0 to T 1 do
Step 1: (Run chain P)
if n%2 = then Generate sample X from chain PX with target π [x,]]
else
Generate sample X from chain Pz(Xn,)) :) with target π [xx]]
end if
Step 2: Update visit count 2(Xn+1) +- ((x++1) + 1.
end for
16

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
D. Proof of Lemma 3.2
The proof consists of three parts: We first show that
V(x)
Σ
(26)
1EA
the Lyapunov function of the ODE
π [x] X.
(27)
Then, we prove that μ is the unique fixed point of the ODEs.
Last, with LaSalle's invariance principle (Khalil, 2002, Corollary 4.2), we can prove that ş globally asymptotically stable, Part I. To prove (26) is the Lyapunov function, we take partial derivative of V (xx w.r.t such that
(v
(x
Σ
I
01
Ex
F2
pz(zi/p1)
ΣKEx MR (k( / px)
iEX
pa( (1)
-2)- -2a-1
Di
-0
a
EKEX MR (V/(T///1N/
M4i
11
iE
27
-a
Σ ux) 200-1 jEx
-2000
Σ
Iz
Hi
Vxx
VEX
-a-1
27
-
Σ
p1(2///))) -2a-2
Iz
I2
S
0,
Vxx)
EE
where the fourth equality comes from the definition of V(x (26), and the last inequality from Cauchy-Sehwartz inequality by rewriting
Σ NEE
Li
Σ
1/2
1/2
Σ
Σ
xi(Is//1e (((s:////> (cc(s:/u)-2200 -2a-2
H4
HE
NE
WEX
--1 for some constant C and any E X. Or equivalently, x μ. Then, (xx S 0 and the equality holds only when x 14, which the equilibrium of the ODE (27). Thus, V(x) in the form of (26) is the Lyapunov function of the ODE (27).
and its equality holds only when z 1/2 21/2 1/2 (23// (x:/14)
Part II. Then, show that is the unique fixed point of π [x] in C3. xetxx be the fixed point of π [x], i.e.,
|4( /14)
m [x*]
ΣKEX 1h (af(///)))))))))))))))))(()))( xi e X.
Rearranging and combining terms on both sides of the equation gives
Σ mu(x//1x) KEX
Since the RHS is invariant index i, we have
(x (xi/Pz) -a-1 - Vi.j E X.
Since a 2 0, we have 2t/u4 23/ for all j, E X, implying that x; Chi for some scalar C and any i E X', and thus
x" = 1u because x", x² E Int.
Part III. We first provide the LaSalle's 's invariance principle below for self-contained purpose.
17

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Theorem D.1 (LaSalle's invariance principle (Khalil, 2002)). Let x" be an equilibrium point for the ODE x - f(x). Let V: domf > R be a continuously differentiable, radially unbounded function, positive definite function such that ( S O for all dom .et S = {x E domf(V(x) = 0} and suppose that no solution stay identically in S other than the trivial solution x(t) = x'. Then, x' is globally asymptotically stable.
To apply Theorem D.1, we let [x) A [xx] x such that domf- Tnd(EE). The set S = [11). By construction, V(x) 2 0 and (x) + do as x + OΣ (the boundary of the probability simplex, where at least one entry I, of the empirical measure x becomes zero). Along with the design of π [x] in (6) following that is the unique fixed point, we prove that is globally asymptotically stable for the ODE (27).
E. Proof of Theorem 3.3
We leverage the stochastic approximation theories from Delyon (2000) and Fort (2015) for asymptotic analysis within HDT-MCMC framework regarding the iteration of the empirical measure X,. We obtain almost sure convergence and CLT results in Appendix E.I and E.2, as was done similarly for SRRW in Doshi et al. (2023). However, we adopt the asymptotic analysis to non-reversible Markov chains as detailed in Appendix E.3, to which SRRW cannot accommodate.
To start with, we first introduce the following theorem for almost sure and CLT results of the stochastic approximation.
Theorem E.1 (Delyynn, 2000) Theorem 15, (Fort, 2015) Theorem 3.2). Consider the following stochastic approximation:
X = Xn + Tn-1 H (Xn, Xu+1);
(28)
where {Xn]nzn is driven by a Markov chain Pix), parameterized by x E Id, with stationary distribution ा [x), and function H Rdd x X + Rd. (x, X) + ((xxX). Moreover, the mean feed h(x) = Ei-m(x] (x, For the following conditions:
(BI) Function h: Rd + Rd is continuous on X, there exists non-negative disferentiable, radially unbounded function functioon V such that (xV h(x)) S O, Vx E Rd and the set S = fx (VV h(x)) = 0} is such that VSS) has empty interior. There exists a compact set K. C R& such that (vV. h(x)) < 0 if K:;
(B2) For every x, there exists a function mx(1) such that for every E X,
mx (1) - (P(x]mx) H (xx i) h(x)).
(29)
For any compact set C Rdd
sup xEC,1EX
[X, i)11 ml oo.
(30)
There exists a continuous function éc, @0) = 0, such that for any x, x' E C.
sup [I (P(x' ) s de (f|x - x(11))
(31)
(B3) The step size follows "nn 2 0, Enzi 7n oc, En21 22 < oo and En21 1m41 - 7rl co.
(B4) sup,, |xxl|2 < oo almost surely.
(B5) Function h is continuous, differentiable in some neighborhood xf E S, and matrix Vh(x))==H (written as Vh(x*)
for brevity) has all its eigenvalues with negative real parts.
(BI) -B4) are satisfied, then almost surely,
lim sup lim inf ||x., - x" x/1 = 0. ES
(32)
If additionally (B5) is satisfied, then condition on Xn + >x" where x* E S, we have
Vn(xx, - xx) n-000 NO, V),
dist.
18

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
where
(33)
and
( (Eur(xx))- -10x-((x)) -(xx)))
U = lim -E 1000 1
{
[(1(x',33)) Xx) m(>x))
(34)
We interpret the iteration of empirical measure x,, of Algorithm here an instance of stochastic approximation.
1
xx+1 = Nxx +
n + 2 (6x.4) - Xn. = Xn
++2 (T [x) x, AN(x.)
n + (6x_:1-x(x.))
(35)
3 H((xnXn 1)
E.1. Ergodicity
We examine conditions (B1) -B4) to obtain the almost sure convergence. (B1) stems from the stability of the related
ODE, which has been proved in Appendix D Part III. Specifically, the Lyapunov function V is of the form in (26), and
S= { contains singleton μa, which is the unique fixed point of the ODE, equivalently, h(μ) j4] / 0. (B3) is automatically satisfied since 7n = 1/(n + 1) as in (35). (B4) is guaranteed since x E Int(E) so that x ll S 1 almost surely for any 2 0.
Now, we focus on (B2). In our Algorithm 1, replacing the target of the base MCMC sampler from μa to π[x results in an ergodic transition matrix P[x] parameterized by x, which π xx] invarriat... For a function m : X - Rd, we define the operator
(P(x]m)(1 & Σ Paylx|m(j).
JEX
For the function H(x,) :): + R! there always exists a corresponding function mx(+) : R| that satisfies the
Poisson equation (29). According to Hu et al. (2024b, Appendix C), the solution mx(1) to the Poisson equation (29) is of the form
m (1) (1
|xxx|"); (H(x,)) h(x)).
(36)
JEX
where [[x + 1 is the fundamental matrix and it is always well-defined whenever P[x] is an ergodic Markov chain with stationary distribution π [xx (Brémaud, 2013, Chapter 6.3.1). Because π [x] Int(E) the probability simplex and ( is the canonical vector, we have (x, = | x S 2, as well as [|x(x) = | [x] - x|| S 2, we have
1 (1)lla S E (I - Pix] + 1xxx)"),; < oo for all i X. Therefore, (30) satisfied.
Next, note that the MCMC sampler for the target is associated with a transition kernel P. exhibiting continuity in relation to p.. Since т [x] in the form (6) is continuous x, we have P[x] continuous in its target ग [x]] and in turn continuous in x E Int(E). As consequence, (36) continuous in x such that for every compact subset C of probability simplex Σ, (i) is continuous in x C for any i E X, and thus Lipschitz in C. Therefore, (31) holds. As result, (B2) is satisfied, and (32) shows X,, -> f as ao almost surely.
E.2. CLT
To obtain the CLT result, we examine (B5). Note that [xx] in the form of (6) is continuous and differentiable in x e IIn(2)). In addition, we take the partial derivative of h(x) w.r.t x and obtain the following: After some algebraic computations, for
j a
a Hr(xs/Hi) Dæ, h,(2) = Ox, Σtex Mu (u///un)- 2i
am, [x]
Similarly, when j = i,
0
h₂(x)= = amm [xTs[x](1 mx(x))
Ox,
24
19

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Setting 1a in above partial derivatives gives
① h4 (z) apt ① (x) ap4 (a + 1),
dr;
or equivalently, Vh(μ) = ap11 - (a+ + 1) which has all eigenvalues no larger than -1. Thus, (B5) is satisfied.
Now, we have the CLT result from Theorem E. We translate the form of V, U from (33) and (34) to our settings. (3) shows that
1 Σ (5x, m1
U
lim 400
E
Σ E(5x, (6x, -w)
Vise
Before proceeding with the expression matrix (a). we first provide a result: U = 0" by considering the above expression of matrix U and 1 1'xx- - 1"p = Then,
V HDDT HDT
(a)
|
x
(a+1/2) u + 1c
U
Σ
c
(a+1/2)
uiu +
-1/ ==1
u1²
dt
1
T
x
Σ 6
(a+ 1/21 u
U
Σ
e
(a+ 12+1 u0u?
dt
X
(o (c- Uv,,?)
x
Σ j
U
Σ j=2
Uuuy
2a +1
1=2
(I- w1- 14x²
2a
U
2a +
2a +
where the third equality comes from the eigendecomposition the matrix exponential form. The fourth and the second last equalities stem from the fact U
0. The third last equality comes from the fact that I = > u
u1 -I Gno and I" =1p" > u.ui
F.3. Adaptation Non-Reversible Markoy Chains
For non-reversible Markov chains that directly modify the transition probabilities such as Suwa Todo (2010); Chen Hwang (2013); Bierkens (2016); Thin al. (2020), they typically add some target-dependent mass to the standard MH kernel P with target μ., and let satisfy the 'skew detailed balance' condition, e.g., Thin et (2020, eq. (3)). For example, Bierkens (2016) introduces vorticity matrix Tp,, which always exists, to break the reversibility while ensuring that the chain retains an arbitrary target distribution μe E Int(E). When applied in our Algorithm 1, for each given empirical measure x, there will be a specific I m(x). still maintaining the target distribution as π [x]. This vorticity matrix I <[x] always exists for a given x because T [x] is simply new target distribution. Therefore, in this case, for any given x, the resulting transition
kernel P[x] emerging from the non-reversible Markov chain is still ergodic and π invariann We note that in the proof of ergodicity and CLT, we never require the time reversibility of the underlying Markov chain P P[x] for a given x E Int(EE). For
20

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
the proof, the sole requirement is the continuity of the kemne P. determined by its target μa, from the non-reversible MCMC algorithms. Consequently, this line of work can he directly covered by the theoretical analysis in Appendix E.1 and E.2.
However, the above argument does not work for non-reversible Markov chains with augmented state spaces, like MHDA and 2-cycle Markov chain, which incorporate an additional variable to induce directional bias in transitions (Lee et al., 2012; Maire et al., 2014; Andrieu & Livingstone, 2021), rather than acting on the original state space X. Specifically, their trajectory is usually defined as {(X,, In20. where the sample Xn E X is defined in the original state space X. and Y, E y defined on some state space, such as y {0. 1} for a 2-cycle Markov chain such that Y, E {0, to indicate which Markov chain to use in each iteration, and y X' for MHDA such that Y, Xn-1, which represents the most recent sample.
Recall the stochastic approximation (28) requires (X..) 3 to be controlled Markovian dynamics. That is, Xn+1 is drawn from a transition kernel space (X, ))), then } in isolation cannot be viewed as a controlled Markov chain, since Xn+1 depends not only on Xn; Xn, but also on the auxiliary state Yn E V. More concretely, mixing these spaces (using a transition matrix on (X, ))) but a function (x, -) only defined on X) causes a dimensional mismatch. For example, in (36), the solution my (1) not well defined because P[x] is specified on (X)) while (x, -) is only on X. On the other hand, a natural solution the above mismatch is to record visit frequencies of the augmented state in the empirical measure update (35). This resolves dimensional mismatch but inflates the dimension of x. For example, this would increase the dimension of x from | to | for the MHDA and to | for the 2-cycle Markov chain. This is especially problematic for large state space X.
X..] parameterized by empirical measure X,, If the chain instead operates on an augmented
In the following, we provide a trick to accommodate the proofs in Appendix E.1 and E.2 to the non-reversible Markov chains on the augmented state space without modifying the empirical measure x, i.e. the empirical measure still defined on the original state space X.
Given target μe, denote by j the stationary distribution defined on the augmented state space X' D/ and admits the marginal stationary distribution 14 = -Ej P((J) because these non-reversible Markov chains are designed to achieve the same target distribution jl on the original state space X, e.g., Lee et al. (2012, Theorem 6), Maire et al. (2014, Proposition 13). Thus, when adopting these algorithms under our HDT-MCMC framework, for given x E Int(E)), we alter their target distribution by π [xx], and let o [x] be the joint distribution of the augmented states with n. [x] = Σjey ((.,)) [x]. Then, we T such that (x H(x, ō; x. Then, the x, update (35)
define another function + R| X' y becomes
X = Xn +
ae (x,, Xn+1, Mnt1). n n 2
(37)
For any x E En)(E),, we have
xxx) A E Dx
Σ SEXTED
= HH(x,) Σ [ = Σ H(x, (m( = h(x).
TEX
JEY
SEX
Thus, the mean field ((-) is identical to h(.). Therefore, instead of analyzing (35), the analyses in Appendix E.1 and E.2 now directly carry over to the iteration (37), where we replace the function H by & and its mean field h by d.
Moreover, the matrix U is given by
U lim 1000
E
Σ (0"
Zz)
Σ F Zz)
2 H HH,
Σ Xz)
Σ
lim E
which is exactly the definition of the asymptotic covariance for non-reversible Markov chains, as studied in Lee et al. (2012); Maire et al. (2014); Andrieu& & Livingstone (2021). Therefore, we maintain the same expression of V from Appendix E.2 for non-reversible Markov chains on augmented state spaces. This completes the proof.
Remark E. A caveat here is that we no longer have the alternative form for the matrix V as in (4) because the transition kernel for the non-reversible Markov chain is defined on the augmented state space X' x ), while the asymptotic covariance here is only on the original state space X. This is the reason that in Theorem 3.3, we refer to the original definition of the asymptotic variance in (3) rather than (4).
21

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
F. Proof of Theorem 3.5
Due to the fact that Xn, - - - E. 1 (8x, - 11), we first rewrite
I (B)
THD B))
B THDT (B)
v (( (1) VB. THOT(B) (B)
Σ
(ōx, 11)
(ōx, -)).
(38)
/THDI
Term
To deal with Term A, we state the random--hange-of-time theory as follows.
Theorem F.1 ((Billinsseey 2013) Theorem 14.4). Given a sequence of random variable 01, 0,, with partial sum S. - Ee 1=1 Og such that
Sn. ~ N(O,
Vn
dist.
Let ni be some positive random variable taking integer value such that Ong is on the same space as On In addition, for some deterministic sequence {cr 120. which goes to infinity, n1/q + for a positive constant c. Then.
Sm
L N(O, V).
n4
diet.
By Theorem 3.3(b), we have vn(xx (1)
n n-000
N(0, V(a)), and vn(x, - u) -m))=>>>o E. 1 (ōx, p)) We have
dist.
deterministic sequence 21,2,... [B]]. where [-] is the floor function, and the condition B/T - C in Theorem 3.5. Thus, view of Theorem F.I. we have
TIDT
(8x, 1)) B- N(0, V).
(39)
THDT (
dist.
Now, we state the Slutsky's theorem follows.
Theorem F.2 (Slutsky's 's theorem (Ash & Doléans-Dade, 2000)). Let {An} and (Br} be the sequence of random variables. If An n=00 for some distribution A and B, + almost surely as n + Do for a non-zero constant then dist.
An/ Bn 11000 A/b. dist.
Following (39), B/THDT (B) +
CHIT almost surely, and Theorem F.2. B cc, (38) converges weakly to (00 (a)). We can follow the same procedures for SRRW, which completes the proof.
G. Proof of Lemma 3.6
We first briefly explain the cost of our HDT-MCMC and SRRW per sample. At each step, our HDT-MCMC computes the proposal distribution Qiy and Qj. with 2 costs. Thus, we have a, 2c and CHDT 2c.
On the other hand, in SRRW, normalizing Kij(x [x] over all (i) costs 2c])(ii), since each neighbor's acceptance ratio must be calculated. Based the definition in (12), we derive the inequality for B /SKK (B):
k+I (X.)) m=
== 2c(((X,..
(40)
K
T TSRRR
(B)
k
Taking B -+ oo is equivalent to taking &o + co, so the RHS of (40) becomes
2c
lim
[(Xx)) 2c ([)(
K
22

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
where the equality comes from the ergodicity in Theorem 3.3(a). Similarly, we can rewrite the LHS of (40)
Σ カ= (Xx)
2x(N(Xx+11)
Since c(N < co, the LHS of (40) still converges to 2e [i) and
as - co. Hence, CSRRW ([Vliinl(iii))
C /C Ee~nulli ([V(I
(41)
Note that the 'expanded' neighborhood size [iii 2 2 because the graph is connected so that each state has at least one neighbor plus itself, thus [[V)][ 2 2.
From (5), (10) and by noting the eigenvalue X 11 we show that
x
1 A
V SRRW
X i
20
1)
+1
|
1
A
un
4a
(42)
i=2
20 +
V (a)
4a +
(a).
= 2
where the second inequality (by Loewner ordering) because X S such that 2a(A:+1)+1 Ja+1 2 and
Ei 21(A
L+d: Ja I-X u is positive semi-definite using the definition of Loewner ordering, i.c., for any
non-zero vector 2,
12
Ix 2 == == Σ 1=2
1 1 >; " - 4a 1 1 1- A;
1 A (x ux 2 O. 2a(A; +1)+1 4a 41) 1 1-
x
Σ
+1+
The last inequality comes from 2011 such that 20+1 positive semi-definite by its definition in (10)).
VHDT(a))
_ (a) is positive semi-definite (note that VIDT (a)
4a+1
Then, by Theorem 3.5, we have
SHRWW SRRW (a) C (1) V SKRW (a)
CIDT yuDT (a) B[W(O))
where the first equality comes from (41), and the second inequality is from (42). This completes the proof.
H. Additional Simulation
H.1. Simulation setting for graph sampling
Table 2. Summary of graph datasets.
Name
# of nodes.
of edges
Average degree
WikiVote
2,914
6.55
Facebook
4039
88,234
43.69
p2p- GnutellaO8
6301
20,777
6.59
p2p- 22p-Gautella04
10876
39,994
7.35
Table 2 shows the detailed summary of the graph used in our experiments. We used different numbers of iterations for each graph T (3000, 15000, 15000, 3000), respectively. In addition to TVD, we also simulate normalized root mean
23

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
square error (NRMSE) under HDT-MCMC framework in graph sampling, where the NRMSE of the MCMC estimator (J) - n/ - (s) for some test function f X -> IR with the ground truth up _ [f] is defined as
NRMSE( Wn. x5) V ((() ///0
Vilovuta Grash
Gww.-Gnutelllloooo Graph
WildVote Graph
Sepp-Gnutellleeeeo Graph
1.0
N--RI
VHiR
Hi
H.0TH-RR 5)
HDT-MAAN (4- 51
( -5
HDTHH-RH te-
3.9
Vetza
0.2
3.8
2.0
TVD
0.7
0.7
3.6
1.3
0.5
25
0.3
0.3
13
500
1000
1500 Steps
2000
2500
3000
2500 5000
7500 10530 13500 15000
550
1030
3500 Steps
2000
2530
3010
2506
5000
7500 Steps
10301
12530 15020
Steps
Figure 5. TVD improvement over HDT framework. The upper row for nonreversible chain; TVD improvement over HDT-MTM with locally balanced weights function where MHRW is a special case when K 1.
H.2. More results on HDT-MCMC in graph sampling
In this section, we present more simulation results on the algorithm that utilizes HDT-MCMC framework for graph sampling in other graph. To demonstrate the impact of HDT-MCMC, we implement HDT-version of both reversible and nonreversible chain. For instance, we implement HDT-MTM as a reversible chain, and HDT-MHDA, HDT-2-cycle as non-reww nonrreversible chains. A detailed implementation can be found in Appendix C. We use TVD and NRMSE as the metrics, and set our test function X 1). This form of test function can be interpreted the label of each node. Estimating the density of the node label is crucial, especially in online social networks.
For each graph, we first randomly assign nodes with label 1 with some probability p and 0 otherwise. Namely, Let S be the set of the node that is assigned to label 1, i.e. S = f E (1) = 1} We aim to estimate the true proportion of label I using graph sampling. The assigned probability p is set as 0.3. Figure 6 include the result of MHRW, MTM, MHDA and their corresponding HDT-version. We observe that HDT version algorithms consistently outperform the base version across different graphs. We also notice that HDT version algorithms have better performance than SRRW, shown in Facebook graph and p2p- Sap-Guttella088 graph.
Remark H.I. We conjecture that TVD metric reflects the exploration speed of the random walker, as it equally weights contributions from visited and unvisited states. SRRW achieves superior performance by adjusting its transition kernel to reduce self-transition probabilities. In contrast, HDT-MCMC's use of the Metropolis-Hastings (MH) algorithm may increase eeff-transition probabilities compared to SRRW. However, for graph sampling, even partial graph exploration with unbiased MCMC estimator can accurately approximate the true value effectively, explaining its improved NRMSE performance.
Figure 5 shows the TVD result of HDT-MCMC framework over the graph dataset. The improvement in TVD is also consistent among all the graph, showing the benefits of utilizing HDT-MCMC framework can convergence faster than the base chain.
We also implemented HDT version of 2-cycle MCMC as an another nonreversible chain that be benefits from this works. In particular, we used MTM and MH as two reversible chains in 2-cycle MCMC while its HDT version is constructed by replacing MTM and MH with their HDT versions. Figure 7 shows the result where HDT version 2-cycle MCMC outperforms the base 2-cycle chain among all the graph dataset.
24

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
117
110
REM
REM
5:08
Figure 6. NRMSE Comparison for HDT framework.
H.3. Different Initializations State Xo and Fake Visit Counts
Here, conduct experiments under different setups to demonstrate the robustness of HDT-MCMC across several aspects. In addition to Facebook graph presented in the main body, we further evaluate the robustness of HDT-MCMC to the choice of initial state Xo using p2p-Gnutella04 graph. The results in Table and Table 4 show both TVD and NRMSE maintain consistent performance across different initializations.
Table Mean (std error) TVD 30, 000 step with different Xo initializations GnutGllteel. All std values in units of 10
Low-Deg Group
High- Group
MHRW
0.545 (1.738)
0.545 (1.704)
HDT-MHRRW
0.403 (0.748)
0.403 (0.765)
MTM
0.514 (1.546)
0.514 (1.556)
HDT-MTM
0.328 (0.999)
0.328 (1.035)
MHDA
0.522 (1.616)
0.521 (1.549)
HDT-MHDA
0.388 (0.708)
0.388 (0.747)
Table 4. Mean NRMSE
30, 000 step with different Xo initializations p2p-Gmutella04.
Low-Deg Group
High- Group
MHRW
0.030
0,031
HDT-MHRW
0.013
0,013
MTM
0.025
0.025
HDT-MTM
0.012
0,013
MHDA
0.028
0.029
HDT-MHDA
0.013
0.012
Next, we consider experiments in which the fake visit count X is initialized from
Deg' scenario: Fake visit counts set by node degrees, heavily favoring high-degree nodes.
'Non-unif" scenario: Fake visit counts randomly drawn from Dirichlet distribution with default concentration parameter of 0.5.
'Unif' scenario: Same initial count for all nodes.
Here, we use Facebook graph and p2p- 22p-Gnutella04 graph in our simulation and show TVD in Tables 5 - 6, and NRMSE in Tables 7 8, both with confidence intervals 95%. Similar to the conclusions from the results on different initialization on state Xo, our HDT framework robust to different fake visit counts, and our HDT version still showcases improvements over their baseline counterparts in both TVD and NRMSE metrics.
25

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Table 5, Mean (std error) TVD at 15, 000 with different fake visit counts Xo on Facebook. All std error values are in units of 10
Deg
Non-unif
Unif
MHRW
0.520 (2.256)
0.520 (2.256)
0.520 (2.256)
HDT-MHRW
0.371 (1.246)
0.371 (1.281)
0.371 (1 .246)
MTM
0.487 (2. 128)
0,487 (2.128)
0,487 (2. (2.128)
HDT-MTM
0.288 (1.751)
0.285 (1.456)
0.285 (1 (1,496)
MHDA
0.513 (2.175)
0.513 (2.1.75)
0.513 (2.175)
HDT-MHDA
0.365 (1.281)
0.365 (1.246)
0.366 (1.258)
Table 6. Mean (std error) TVD at n 30, 000 with different fake visit counts D2p-Gnutella04. All std enror values are in units of 10
Deg
Non-unif
Unif
MHRW
0.545 (1.621)
0.545 (1.621)
0.545 (1.621)
HDT-MHRW
0.403 (0.744)
0.403 (0.742)
0.403 (0.745)
MTM
0,514 (1.587)
0.514 (1,587)
0.514 (1.587)
HDT-MTM
0.325 (1.031)
0.330 (0.987)
0.328 (1.069)
MHDA
0.522 (1.573)
0.522 (1.573)
0.522 (1.573)
HDT-MHDA
0.388 (0.757)
0.388 (0.702)
0.388 (0.733)
Table 7. Mean NRMSE at 15, 000 step with different fake visit counts Facebook.
Deg
Non-unif
Unif
MHRW
0.079
0.079
0.079
HDT-MHRW
0.028
0.028
0.028
MTM
0.056
0.056
0.056
HDT-MTM
0.098
0.047
0.062
MHDA
0.068
0.068
0.068
HDT-MHDDA
0.027
0.028
0.027
Table 8. Mean NRMSE n 15, 000 step with different fake visit counts xo on p2p-Gnutella04.
Deg
Non-unif
Unif
MHRW
0.030
0.030
0.030
HDT-MHRW
0.013
0.013
0.013
MTM
0.023
0.023
0.023
HDT-MTM
0.013
0.012
0.012
MHDA
0.028
0.028
0,028
HDT-MHDA
0.013
0.012
0.013
H.4. Effect of on Convergence
To illustrate the impact of a, we run HDT-MHRW under a E 1,,1,,25, 10), with = 0 being the MHRW. We observed in Figure that the performance of average TVD is asymptotically improved with larger a, supporting the theoretical result in Theorem 3.3 where larger a leads to smaller covariance.
H.S. LRU on Larger graph
Here, we test our LRU with HDT-MHRW on WikiVote graph and p2p-Gnutella graph, and the result is shown in Figure 9, We also observed LRU with 80% memory reduction can still outperforms standard MH. Moreover, in p2p-Gnutella08 graph, we notice that the performance LRU design is robust to the choice of the memory capacity. comparable performance
26

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Wold Graph
facebook Graph
p2p Sww.e/atneeleeoo Graph
p2p Cnutella04 Graph
NTHaC
NTV-3C
NTV-3C
-TT-32
51
()
2.6
0.2
2.0
2.0
0.3
TVD
3.7
0.7
3.4
0.5
0.-
3.4
0.3
0.4
1020 3350
2000
2530
2000
2300
2000
1500 Steps
10200
12500
18020
2000
7500 Sleps
1020: 12500 15000
3000
10030 15023 20003 2302E 30000
Steps
Steps
Figure 7. TVD Comparison for 2oy-
WileWWtee Graph
P20-GrutellecB Graph
facebook Graph
p2p-Snatellad4 Graph
2.0
Hi RAT-EET Tam 25
VIRA- (o 1)
MI (a 20
MIRIH DT
MIRWW- (a 20
0.9
Hi MIRAA 10
Hi RI (o 2
0.2
VH (o- 50
(a-
0.5
vieweed la- 101
WH 50
HHRAAA to- 50
TVD
0.7
5.7
0.7
0.6
0.6
0.5
15
1.5
04-
502
2000
1300
2003
2000
2002
2000
5000
7303
33000
32503 15003
2500 5000
7500 Steps
32000
23500 15000
5002
16600
25000 20000 25000 30000 Steps
Steps
Steps
Figure& 8. -Simulation of HDDT-HHWW with different choices of a where MHRW can he viewed as the special case when a = 0.
when r is chosen within 5 to 20.
Furthermore, we test our design using the ego-Gplus graph (Leskovec & Krevl, 2014), which contains about 100K nodes, and implemented r = 0.01 and r = 0.1 in LRU, For simulation setting, We run 50 independent trials with 300,000 steps and set one-third of the number of steps as burn-in period before collecting samples. Figure 11 shows the result. We observed a similar robustness behavior of the choice of LRU capacity with respect to average TVD. The performance of using r = 0.01 is comparable to using/ r = 0.1 where both cases outperforms MHRW. This findings open a possibility that we may only requires an approximated empirical measure to implement MDT-MCMC while remaining fast convergence. Furthermore, the corresponding theoretical result of that can be one possible future work.
WikiVote Graph
p2p-Gnutella08 Graph
1.0
MHRW
1.0
MHRW
HDT HIDT-MHRW 5) with r=0.01
HDT-MHRW (a- 5) with 0=0.01
HDT-MHRW (a- 5) with 0-0.05
HDT-MHRW (a- 5) with 0-0.05
0.9
HDT-MHRW 5) with r-0.10
0.9
HDT-MHRW (R- 5) with r-0.10
HDT- MIDT-MHRW 5) with r=0.15
HDT-MHRW (a 5) with r=0.15
HDT-MHRW 5) with r=0.20
HDT-MHRW (a 5) with r=0.2
0.8
HDT-MHRW 5) with r-1
HDT-MHRW (a 5) with r-1
TVD
0.7
0.7
0.6
0.5
0.4
500
1000
1500
2000
2500
3000
2000 4000 6000
8000 100001200014000
Steps
Steps
Figure 9, Simulation of incorporating LRU in HDT-MHRW framework to reduce memory issues.
27

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
542
Wilevote Graph
0.4
fa.ebbokk Graph
5.2
płp Snutela08 Graph
0.0-
p2p Cnutelladd Graph
5.35
2.35
0.35
0.35
HD0 ViEW with eii.E
He-M00 with
4577 welag with
-00T- la 113
407 Hi-Rit 54 with ca in
407 He RI- aat 1n
-077 He-ett lam 31 with mireiii
-ET--015t (a=31ath
HE1 aerer iim 31 with po 25
HDT WE-er 10 ve
NRMSE
1.25
Stathee1
NRNSE
0.25
HD1 Heree limm wan
NRNSE
3.25
HeTe (am31 W0
NRMSE
0.25
1911 He-- lamal 10
5.23
0.23
0.23
0.23
0.12
4.10
0.13
1.05
1.05
5.0
2.03
1,02
1000
2008
2050
2002
2300
5050
1500 Steps
10000 12550 15002
1.0
2205
5000
7500
10000 1.500 15003
0.07
5005
20500
35023 20000 30000
Steps
Sleps
Steps
Figure 10. NRMSE result of HDT-MHRW framework with LRU
gplus combined Graph
1.0
MHRW
NOT-MHRW (a 5) with 0=
HDT MHRW (a 5) with r-0.1
HDT-MHRW (a with r=1
0.8
0.7
0.6
0.5
1.0
1.5
2.0
2.5
3.0
Steps
x10P
Figure 11. Simulation of the HDT-MHRW with different LRU capacity for graph sampling on gplus-combined graph.
H.6. Additional Experiments on Non-Uniform Target
Since HDT-MCMC can generally be applied to any target distribution μa, we conducts additional experiments on non-uniform target with HDT-MMCM. In particular, we conduct MHRW, MTM and MHDA with their HDT improvements over AS-733 graph (with 6474 nodes and 13895 edges) (Leskovec et al., 2005) and Whois graph (with 7476 nodes and 56.9K edges) (Mahadevan et al., 2006), and set the target distribution proportional to the degree distribution, i.e. 14 x d; with a = 1 in HDT. Similar to the simulation settings in our manuscript, we compare HDT-MCMC to baseline algorithms through TVD (with 95% confidence interval in shaded region) and NRMSE metrics. Since the target distribution is no longer uniform, we adopt importance sampling (Doshi et al., 2023) to obtain an unbiased estimator and then compute NRMSE. The following experimental results are obtained through 100 independent runs.
We first show the comparison between HDTT-MMMC and baseline algorithms using the TVD metric in Figure 12, where HDT outperforms its counterpart in both AS-733 and Whois graphs. In addition, for two baseline Then, we show the performance ordering of HDT-MHRW in terms of different a values. As illustrated in Figure 13, larger a leads to a smaller TVD, aligning with our theoretical findings in our Theorem 3.3. We also test the performance of HDT-MCMC with heuristic LRU cache scheme in Figure 14. In the Whois graph, HDT-MHRW combined with LRU results in a 10% smaller TVD compared to the base MHRW, with over a 90% decrease in memory usage. On the other hand, on the AS-733 graph, the LRU caching scheme yields only modest benefits, achieving a 5% TVD reduction with approximately 50% less memory consumption (with r = 0.5). In Figure 15, we compare the performance of HDT-MHRW and SRRW the under the same computational budget. Since SRRW always requires computing the transition probability around its neighbor at each iteration, it induces large computation during sampling. In contrast, HDT-MHRW only queries one node per iteration, making it more lightweight. In the experiment, we set a = 1 and the total steps as 30000 without a burn-in period. We also observe HDT-MCMC achieves better performance in terms of TVD metric given any fixed budget. Moreover, the performance gap between SRRW and HDT-MHRW is larger on the Whois graph, where average degree of is approximately 15 and is larger than average degree of AS 733, around 4. This also aligns with our Lemma 3.6 where the HDT framework
28

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
provide more efficiency in dense graph under limited budget.
In the simulation of estimating the density of the node label, we retain the same test functions as in Appendix H.2 in our submission. However, since the target distribution is no longer uniform, we have to use importance reweighting to adjust the weight of each sample. In Figure 16, we show that in the long run, HDT-MCMC still outperforms its baseline counterpart.
35733 Grape
as733 Grash 2hwml))
whols Graph
whot Graph Pown Rl
HOT-N
HOT-MIAN
0.10
4.4
MIDDA POTIMIIA
0:23
MIDDA
HI-DA
POT-M//DA
POTTFIII
4.19
0.16
0.24
0.4
0.
6.-
0.12
1.2
3000
10000
15200
20000
20000 32000
1900
26302
27030
20000
15000
32000
0.2
1000 10000
25200 Steps
20026 20000 32000
"2o00
20003
27000
2000
20302
30020
Steps
Steps
Steps
Figure 12. Comparison of HDT- with base chain MHRW, MTM, and MHDA via TVD metric in AS-733 and Whois graphs. The plots in the right column the zoom in version of those in the left column.
as733 Graph
whois Graph
0.40
1.0
MHRW
MHRW
HDT-MHRW 0.5)
HDT-MHRW (a 0.5)
HDT-MHRW (a- 1)
0.35
HDT- MOTT-MHRW (ar 1)
0.8
HDT-MHRW (a 2)
HDT-MHRI (a
HDT-MHRW 5)
HDT-MHRW (a
HDT-MHRW (a 10)
0.30
HDDT-MHRW (a 10)
TVD
0.6
0.25
0.4
0.20
0.15
0.2
0.10
5000
10000
15000
20000
25000 30000
5000
10000
15000
20000 25000 30000
Steps
Steps
Figure 13. Simulation of HDT-MHRW with different choices of a where MHRW can viewed as the special case when a
75733 Geaph
wx733 Graph
whiis Graph
whols Eragh
3.200
0.6
0.310
HDS MN-
HD1 HPH
HES DETIAMMEEM.... / 0.71
0.165
-DllNeeeww/-DD 01
3.200
HET-MMIE 0.25
HETT-IRW. 2.000
2.5
3.355
0.200
NITT-MHH...... /-02
2.4
3.185
3.3
3.100
HIT UHAN HIT
HOT-
540 10030
1540
29956 p000 32000
24000
290-0 29d0n 2000 VI6C0
5200 1003) 1940
2090 2500 st8ce
24606
20000 20003 93600
Stops
Steps
Steps
Steps
Figure 14. Performance of HDT-MHRW with LRU cache scheme.
29

---

History-Driven Target Towards Efficient Nonlincar MCMC on General Graphs
Cost comparison
1.0
0.8
0.6
0.4
HDT-MHRW (a= 1) whois
0.3
SRRW (a 1) whols
HDT-MHRW MHRW (a= 1) a5733
SRRW (a 1) as 733
0
5000 10000 15000 20000 25000 30000 Budget
Figure 15. TVD comparison between HDT-MHRW and SRRW under budget constraints.
Grash
Crugh [dxmi)]
1220
Grapph
Graph
NHNW
HOT WHEN
010
HIT WHRM 10
MIN 1C-31
HIST MHNIN
0.30
1.150
01C
HoT. HoT- low
NRMSE
0.07
2.075
06
2.00
0.02
0.000
2,000
16200
20303
20266
43000
35.00
20003
15200
50003
5.000
2000 10000
15000 30000 25400 30000 Steps
10000 36000 35400 3E000
Sleps
Stepp
Steps
Figure Comparison HDT-MCMC (with thicker solid curves) to base chain MHRW. MTM, and MHDA (with thinner dash-dot curves) via NRMSE metric in AS-733 and Whois graphs. The plots in the right column is the zoom in version of those in the left column.
30


Reviews:
[{"review_id": "3mjNZoytYL", "reviewer": "Reviewer_Fmtv", "summary": "- Propose a history-driven target (HDT) framework, extending the self-repellent random walk (SRRW) framework on general graphs [Doshi et al., 2023] to allow for construction from a non-reversible sampler, whereas the original framework in [Doshi et al., 2023] required a reversible sampler.\n\n- On the practical side, HDT exhibits local dependence, meaning that each particle update only requires local information rather than accessing information from all its neighbors. This significantly reduces per-step computational cost compared to SRRW, which is particularly important for walking on large, dense graphs. The authors provide both theoretical analysis and empirical evidence demonstrating the computational efficiency of HDT.\n\n- The authors also introduce an efficient implementation of HDT with improved memory scalability over SRRW, making it more practical for use on large-scale graphs.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and detailed review. We appreciate your positive remarks on our paper’s theoretical depth and are grateful for the questions you raised. Below, we address each of your points in turn.\n\n---\n\n## Response to Q1\n\nWe agree that this point warrants further explanation. Here is a streamlined proof by contradiction:\n1. Assume that $g(c_1,c_2,x,\\\\mu)$ depends on $x, \\\\mu$.\n2. According to Line 650, for any coordinate $i \\\\in [N]$\n$$\nf(c_1 x_i,c_2 μ_i )=g(c_1,c_2,x,μ)f(x_i,μ_i),\n$$\nwhere the function $f :\\\\mathbb{R}\\_{>0}×\\\\mathbb{R}\\_{>0}→\\\\mathbb{R}\\_{>0}$.\n3. Consider two pairs $(x,μ)$ and $(\\\\hat x,\\\\hat μ)$ whose $i$-th coordinate are identical (i.e., $x_i=\\\\hat x_i,μ_i=\\\\hat μ_i$). Then, $f(c_1 x_i,c_2 μ_i )=f(c_1 \\\\hat x_i,c_2 \\\\hat μ_i )$ and $f(x_i,μ_i )=f(\\\\hat x_i,\\\\hat μ_i )$. By the equation in step 2, it follows that \n$$\ng(c_1,c_2,x,μ)=g(c_1,c_2,\\\\hat x, \\\\hatμ).\n$$\n4. Similarly, construct another pair ($\\\\tilde x,\\\\tilde μ$) (i.e., $\\\\tilde x_j=\\\\hat x_j,\\\\tilde μ_j=\\\\hat μ_j$ for $j$-th coordinate) such that $g(c_1,c_2,\\\\tilde x, \\\\tilde μ)=g(c_1,c_2,\\\\hat x,\\\\hat μ)$. Then, $(\\\\hat x, \\\\hat μ)$ serves as a ‘bridge’ to $(x,μ)$ and $(\\\\tilde x,\\\\tilde μ)$, leading to\n$$\ng(c_1,c_2,x,μ)=g(c_1,c_2,\\\\tilde x,\\\\tilde μ).\n$$\nFor a given pair $(x,μ)$, we can always construct a distinct pair $(\\\\tilde x,\\\\tilde μ)$ such that $g(c_1,c_2,x,μ)=g(c_1,c_2,\\\\tilde x, \\\\tilde μ)$, indicating that function $g$ must be identical for any $(x,μ)$. Hence $g$ cannot actually depend on $x$ or $μ$; it must be a function of $(c_1,c_2)$ alone.\n\nWe will revise Lines 653–655 in the manuscript with this explanation to clarify why $g$ must be independent of $(x,μ)$.\n\n---\n\n## Response to Q2\n\nThank you for catching this. We will correct the mentioned typo and any others in the revision.\n\n---\n\n## Response to Q3\n\nThis is an excellent question. You are correct that Appendix E.1 and E.2 do not assume reversibility, allowing non-reversible chains to operate directly on the state space $\\\\mathcal{X}$ of interest. Let $\\\\mathcal{Y}$ be the auxiliary state space. Below, we explain why analyzing non-reversible chains on the augmented state space $\\\\mathcal{Z}≜\\\\mathcal{X}×\\\\mathcal{Y}$ is more than $P[x]$ preserving $π[x]$, and discuss the technical challenges in directly applying the stochastic approximation (SA) framework, as well as how Appendix E.3 addresses them.\n\n1. **State Space Inconsistency in SA Analysis**  \nThe SA iteration\n$$\nx_{n+1}=x_n+γ_{n+1} H(x_n,X_{n+1})≡x_n+\\\\frac{1}{n+1}(δ_{X_{n+1}}-x_n)\n$$\nrequires $\\\\{X_n\\\\}$ to be *controlled Markovian dynamics*. That is, $X_{n+1}$ is drawn from a transition kernel $P_{(X_n,⋅)} [x_n]$ parameterized by empirical measure $x_n$ (in Line 891). If the chain instead operates on an augmented space $\\\\mathcal{Z}$, then $\\\\{X_n\\\\}$ *in isolation* cannot be viewed as a controlled Markov chain, since $X_{n+1}$ depends not only on $X_n, x_n$, but also on the auxiliary state $Y_n\\\\in \\\\mathcal{Y}$.  \nMore concretely, mixing these spaces (using a transition matrix on $\\\\mathcal{Z}$ but a function $H(x,⋅)$ only defined on $\\\\mathcal{X}$) causes a dimensional mismatch in the SA analysis. For example, in Eq. (32) around Line 952, the solution\n$$\nm_x (i)=∑_{j∈\\\\mathcal{Z}} (I-P[x]+1π[x]^T)_{ij}^{-1} (H(x,j)-h(x))\n$$\nto the Poisson equation is not well-defined because $P[x]$ is specified on $\\\\mathcal{Z}$, whereas $H(x,⋅)$ is only on $\\\\mathcal{X}$. From the viewpoint of SA iteration, a direct redefinition of $H$ via\n$$\nH:(0,1)^{|\\\\mathcal{X}|}×\\\\mathcal{Z}→\\\\mathbb{R}^{|\\\\mathcal{X}|}:(x,Z)→δ_Z-x\n$$\ndoes not resolve the core mismatch because $δ_Z$ (a canonical vector in $\\\\mathcal{Z}$) does not align with the dimension of $x$ (an empirical measure in $\\\\mathcal{X}$).\n\n2. **Dimension and Memory Overhead**  \nA natural solution to the above mismatch is to record visit frequencies for the augmented space $\\\\mathcal{Z}$, thereby resolving dimensional mismatch but *inflating* the dimension of $x$. For instance, this would increase the dimension of $x$ from $|\\\\mathcal{X}|$ to $|\\\\mathcal{X}|^2$ for MHDA (Lee et al., 2012) and to $2|\\\\mathcal{X}|$ for the 2-cycle Markov chain (Maire et al., 2014). This is especially problematic for large state space $\\\\mathcal{X}$.\n\n**Our “Trick” in Appendix E.3**  \nWe address these issues by replacing $H$ with  \n$$\nϕ: (0,1)^{|\\\\mathcal{X}|}×\\\\mathcal{Z}→\\\\mathbb{R}^{|\\\\mathcal{X}|}:(x,(X,Y))→δ_X-x\n$$\nso that the augmented state $Z∈\\\\mathcal{Z}$ is 'accepted' by $\\phi$, but we *only* store visit frequencies for $\\\\mathcal{X}$ (i.e., we project $\\\\mathcal{Z}$ onto $\\\\mathcal{X}$). This reconciles the SA analysis with the non-reversible Markov chain on $\\\\mathcal{Z}$ (via the function $\\phi$) without inflating the dimension of $x$.\n\nWe will revise Line 1043 in the manuscript to clearly emphasize how this approach extends our SA analysis to non-reversible chains on augmented state spaces, mitigating both dimensional mismatch and memory concerns.", "claims_and_evidence": "- The main claims are: \n1. The HDT sampler (alg 1) converges to the right target. \n2. HDT allows for both non-reversible and reversible sampler. \n3. better performance/ cost ratio than the SRRW.  \n- All claims are well supported by both theoretical investigations and empirical results.", "methods_and_evaluation_criteria": "they make sense.", "theoretical_claims": "I checked all the proofs (with particular  focus on the proof of Theorem 3.3); I believe they are all correct. I do have a few minor questions though, but I do not think there are any correctness issues.\n\nQuestions:\n \n- Line 654: It's not trivial to me why $g(c1, c2, x_i, \\mu_i)$ has to be independent to $x_i, \\mu_i$. Could you please provide a proof by contradiction that if $g$ indeed depends on $x, \\mu$, things won't work?\n- Minor typo: in Eq(24) the step size should be $\\gamma_n$ instead of $1/(n+1)$?\n- About non-reversability: As the author mentioned in Line 1030 - line 1032, the proof in E.1. and E.2. does not explicitly require the reversability of the Markov chain that drives $X_n$. To To my awareness, the proof only requires that $P[x]$ preserves $\\pi[x]$, which is true by construction. So why does one need extra care about the non-reversable case? I do understand that some non-reversible Markov chain, by design, operates on a augmented state space, but they typically still maintain the right stationary distribution in the subspace that we care about (I'd love to be proven wrong here).  And to my knowledge, a Markov process is ergodic (not geometric ergodic) if it obeys a unique stationary distribution; unless the uniqueness here is violated in some non-reversability case, I don't see why the original proof doesn't apply.\n\nGood things about the theory: I've learned many new techniques when reading the proof of this work (though I'm sure it's due to my lack of knowledge in recent advances of MCMC on graphs/general discrete spaces). I find the following things particularly interesting:\n- Lemma 3.1: using ODE stability analysis to show that the Markov process exhibits a unique stationary distribution.\n- Theorem E.1: using general theory of SGD to show ergodicity and CLT of the sampler. Though this has been used in previous works as discussed by the authors.\n- The cost aware CLT is also new to me.", "experimental_designs_or_analyses": "good", "relation_to_broader_scientific_literature": "It's relavent to the literature of building efficient MCMC on general graphs. Particularly, it extends the recent advances on SRRW [Doshi et.al. 23]. Many proof techniques are from the CLT type analysis for stochastic aproximations Delyon (2000) and Fort (2015). \n\nThe authors discussed relevant literatures whenever needed.", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strength: \n\n- Well-written and self-contained: The paper is exceptionally well-written, with a concise yet comprehensive review of SSRW. The exposition is clear, making it accessible to a broad audience.\n\n- Clarity in problem formulation: The authors clearly outline the challenges this work aims to address and provide careful explanations of the proposed methodological components. The discussion in Lines 212–245 is particularly well-structured and insightful. Similarly, each theoretical result is accompanied by a concise discussion of its implications, which greatly enhances readability.\n\n- Strong theoretical foundation: The theoretical results are solid, with well-organized proofs. Even the appendix is a pleasure to read, demonstrating the rigor and care put into the analysis.\n\n- Versatility and practical impact: The proposed algorithm is highly versatile and simple to implement. Algorithm 1 is not only elegant but also provably enhances vanilla MCMC performance on graphs at no additional cost. Given its efficiency and general applicability, I believe this approach will set a new standard for graph-based sampling and become the default algorithm in this domain.\n\nI have a VERY positive opinion on this work; it is not very common to see submissions like this with good writing, careful theoretical analysis, simple algorithm, and superior performance.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "see previous comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "49ouT4Diif", "reviewer": "Reviewer_mrvq", "summary": "This paper introduces the History-Driven Target (HDT) framework, a novel approach to improving Markov Chain Monte Carlo (MCMC) sampling on discrete state spaces, such as general undirected graphs. The HDT framework replaces the original target distribution with a history-dependent target distribution $ \\boldsymbol{\\pi}[\\mathbf{x}] $, which adapts dynamically based on past visit frequencies. This design achieves compatibility with both reversible and non-reversible MCMC samplers, reduces computational overhead compared to Self-Repellent Random Walks (SRRW), and provides unbiased sampling with near-zero variance performance. The authors also propose a memory-efficient Least Recently Used (LRU) cache scheme to address scalability challenges in large graphs. Extensive experiments demonstrate consistent performance gains across various graph types and MCMC methods.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your constructive and practical feedback. We agree that demonstrating robustness to initialization and quantifying uncertainty in our results will enhance the paper. Below is the setting of additional experiments. Due to space constraints, we defer the simulation results on more real-world graphs under TVD and NRMSE metrics in the anonymous linked PDF:\n\nhttps://www.dropbox.com/scl/fi/ujmodl9e8721nef5dx2k5/ICML_2025_Rebuttal_Additional_Simulations.pdf?rlkey=80cp2rhdvf59cvjukrtrcz5km&st=b96ipxpx&dl=0\n\n---\n\n## Robustness of HDT-MCMC to different initialization strategies and uncertainty quantification.\nWe run $1000$ independent trials for different MCMC methods on the wikiVote graph with uniform target and show the TVD $\\mathbb{E}[||x_n-\\mu||_1]$ at $n=3000$ steps with 95% confidence intervals:\n1. **Varying the Initial State $X_0$:**  \n   Besides random selection, we started from nodes in different regions of the graph:\n    - Low-degree group (nodes with below-average degree)\n    - High-degree group (nodes with above-average degree)\n\n    ---\n    **Table 1.** Mean (std error) TVD with different $X_0$ initializations. *All std error values are in units of* \\\\(10^{-4}\\\\).\n\n    | **Method**| **Low-Deg Group**| **High-Deg Group**|\n    |--------------|-----------------|-----------------|\n    | MHRW         | 0.573 (7.316)    | 0.573 (7.290)    |\n    | HDT-MHRW     | 0.417 (3.785)    | 0.417 (3.804)    |\n    | MTM          | 0.533 (6.818)    | 0.533 (7.076)    |\n    | HDT-MTM      | 0.331 (5.417)    | 0.330 (4.154)    |\n    | MHDA         | 0.544 (7.419)    | 0.543 (7.185)    |\n    | HDT-MHDA     | 0.395 (3.564)    | 0.395 (3.569)    |\n    ---\n\n2. **Varying the Fake Visit Count $x_0$:**  \nWe use three scenarios:\n    - 'Deg' scenario: Fake visit counts set by node degrees, heavily favoring high-degree nodes.\n    - 'Non-unif' scenario: Fake visit counts randomly drawn from a Dirichlet distribution with default concentration parameter of $0.5$.\n    - 'Unif' scenario: Same initial count for all nodes.\n\n    In this part, we start with $X_0$ uniformly at random. Note that baseline methods (MHRW, MTM, MHDA) do not depend on fake visit counts $x_0$, so they give identical TVD values in all three scenarios.\n\n    ---\n    **Table 2.** Mean (std error) TVD with different $x_0$ initializations. *All std error values are in units of* \\\\(10^{-4}\\\\).\n\n    | **Method**   | **Deg**       | **Non-unif**   | **Unif**       |\n    |--------------|---------------|---------------|----------------|\n    | MHRW         | 0.573 (7.085)  | 0.573 (7.085)  | 0.573 (7.085)   |\n    | HDT-MHRW     | 0.416 (3.767)  | 0.416 (3.877)  | 0.416 (3.810)   |\n    | MTM          | 0.532 (7.092)  | 0.532 (7.092)  | 0.532 (7.092)   |\n    | HDT-MTM      | 0.325 (4.301)  | 0.332 (4.200)  | 0.330 (4.130)   |\n    | MHDA         | 0.543 (7.219)  | 0.543 (7.219)  | 0.543 (7.219)   |\n    | HDT-MHDA     | 0.395 (3.605)  | 0.395 (3.657)  | 0.396 (3.587)   |\n    ---\n\nIn both Tables 1 and 2, HDT-MCMC shows robust convergence and consistent variance reduction relative to the baseline. We observe that the initialization effect quickly vanishes during the burn-in period (one third of the total samples) so they do not affect the performance of HDT-MCMC. Even when the initial visitation $x_0$ is heavily skewed (such as degree-based distribution where weight goes mostly to the node with largest degree), the HDT forces rapid exploration of under-sampled regions.\n\nIn most cases, the standard error for our HDT-MCMC framework is smaller than baseline algorithms, indicating the consistency of HDT-MCMC across repeated runs. This shows that every sample path generated by our HDT framework performs consistently. These results suggest that the HDT $π[x]$ contributes to stable sampling trajectories that rapidly converge to the target distribution $μ$. We conjecture that this consistent performance of HDT-MCMC is due to the correctness behavior from our design of history-aware scheme in every trajectory to drive $x_n$ closer to the target distribution $μ$.\n\nWe will include detailed simulation setups and plots in the revised paper to illustrate these findings if our paper is accepted.", "claims_and_evidence": "The paper makes several clear claims:\n- HDT is compatible with both reversible and non-reversible MCMC samplers.\n- HDT achieves $ O(1/\\alpha) $ variance reduction relative to baseline MCMC samplers.\n- HDT avoids SRRW's computational overhead by decoupling self-repellency from the transition kernel.\n- The LRU cache scheme enables HDT-MCMC to scale efficiently to large graphs.", "methods_and_evaluation_criteria": "The methods proposed are appropriate for the problem at hand:\n- The HDT framework is rigorously designed to preserve lightweight implementation while achieving self-repellency through adaptive target distributions.\n- Evaluation metrics include TVD and RMSE, which effectively measure convergence speed and estimator accuracy.\n- Experiments span diverse graph types and include comparisons between HDT-enhanced algorithms and baseline MCMC methods.", "theoretical_claims": "The proofs of convergence to $ \\boldsymbol{\\mu} $, variance reduction, and global asymptotic stability are detailed and mathematically rigorous. \n\n  - Lemma 3.1 ensures that $ \\boldsymbol{\\pi}[\\mathbf{x}] $ satisfies scale invariance, local dependence, fixed-point properties, and history dependence.\n  - Theorems 3.3 and 3.5 provide ergodicity and cost-based CLT results that align with stochastic approximation theory.\n\nI did not rigorously check the theoretical claims, but it generally looks reasonable to me.", "experimental_designs_or_analyses": "The experimental designs are valid:\n- Experiments test HDT-MCMC across reversible and non-reversible chains on real-world graphs.\n- Results consistently show improvements in TVD and NRMSE compared to baseline methods.\n- Simulations investigate the effect of key parameters like $ \\alpha $, demonstrating its impact on convergence speed.", "relation_to_broader_scientific_literature": "The paper builds upon prior work in MCMC sampling (e.g., Metropolis-Hastings, SRRW) while addressing their limitations:\n- SRRW introduced self-repellency but suffered from high computational costs and reliance on time-reversibility.\n- Gradient-based methods are efficient but limited to structured spaces.", "essential_references_not_discussed": "The authors provide a comprehensive review of related works but could include additional references on stochastic approximation techniques relevant to their framework.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The HDT framework introduces a novel way to achieve self-repellency without modifying transition kernels.\n- The contributions are well-explained, with detailed experiments and proofs provided in the main text and appendix.\n\n**Weaknesses**\n- The paper does not explore how different initializations affect empirical results or robustness.\n- No confidence intervals or sensitivity analyses are provided for metrics like TVD or NRMSE under varying conditions.", "other_comments_or_suggestions": "None.", "questions_for_authors": "How do different initialization strategies (e.g., initial sample state or fake visit counts) affect convergence speed or variance reduction? Have you tested robustness under varying initialization? Maybe providing uncertainty quantification for TVD or NRMSE metrics across multiple runs would be beneficial.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "R0gddmtVTc", "reviewer": "Reviewer_nUqH", "summary": "The paper introduces a new \"history-driven target\" (HDT) framework to improve Markov Chain Monte Carlo (MCMC) sampling on graphs. HDT modifies the target distribution based on the history of visited states, improving efficiency. This helps overcome the computational limitations of the recently-proposed class of self-repellent random walks (SRRW), which in contrast uses a nonlinear transition kernel that scales poorly with graph size. Unlike SRRW, HDT is compatible with both reversible and non-reversible MCMC samplers. The authors make strong theoretical contributions and test their claims with experiments. They introduce a heuristic scheme that they call the “least recently used (LRU) cache” to further reduce storage requirements.\n\n## Update after rebuttal:\nThe authors have clarified the downstream benefits of their algorithm, the impact of graph properties on its effectiveness, and performance with a non-uniform target measure. I'm satisfied with the responses and have raised my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Q1. Downstream benefits in ML algorithms\nOur HDT framework enables more efficient sampling of large or complex graphs for arbitrary target measures, reducing estimator variance and cost. Key impacts include:\n1. **Estimating Global Properties of Large-Scale Graphs:** In social networks, e-commerce systems, recommender systems and other domains, practitioners need to estimate graph size, node degree distribution, vertex label distribution [Xie et al. 2023]. These applications include detecting bot populations, identifying high-value user segments or scarce features [Nakajima et al. 2023], and gradient of local loss for token algorithms in distributed optimizations [Sun et al. 2018, Even 2023], especially with limited graph access. However, a standard random walk can be slow to discover underrepresented regions or rare features, forcing more samples to achieve acceptable levels of accuracy. \n2. **Sampling from Large-Scale Graphs:** In statistical physics (e.g., Ising or Potts models) [Grathwohl et al. 2021, Zhang et al. 2022], machine learning (e.g., Restricted Boltzmann machines / energy-based models for image generation, reconstruction or partition, Bayesian variable selection for high-dimensional regression/classification) [Hinton 2010, Zanella 2020, Rhodes et al. 2022, Chang et al. 2022, Sun et al. 2023], and econometrics (e.g., MCMC-MLE method for exponential random graph models) [Bhamidi et al. 2011, Byshkin et al. 2016], the general discrete state space can always be translated into a graph where each node represents a possible configuration and edges link configurations that differ by the Hamming distance. Efficient exploration yields quicker, more accurate system representation and inference.\n\nHDT-MCMC strategically modifies the target distribution at minimal extra cost compared to baseline MCMC and SRRW, achieving equivalent accuracy with fewer samples and computations. While fully deployment in exponentially large configuration state spaces present ongoing memory challenges beyond this paper's scope, our method offers versatile and simple implementation alongside significant efficiency improvements for sampling on general graphs. We plan to detail these applications in a revised appendix if our paper is accepted.\n\n[*References not included in our manuscript are listed below for this response.*]\n\nG. Hinton. \"A practical guide to training restricted Boltzmann machines.\" Momentum, 2010.\n\nS. Bhamidi et al. \"Mixing time of exponential random graphs.\" Ann. Appl. Probab., 2011.\n\nM. Byshkin et al. \"Auxiliary parameter MCMC for exponential random graph models.\" J. Stat. Phys., 2016.\n\nT. Sun et al. \"On markov chain gradient descent.\" NeurIPS, 2018.\n\nH. Xie et al. \"A bootstrapping approach to optimize random walk based statistical estimation over graphs.\" IEEE TKDE, 2023.\n\nK. Nakajima et al. \"Random walk sampling in social networks involving private nodes.\" ACM TKDD, 2023. \n\nM. Even. \"Stochastic gradient descent under markovian sampling schemes.\" ICML, 2023.\n\n---\n\n## Q2. Impact of graph properties on the gain of HDT-MCMC\nThe gains of HDT-MCMC relative to baseline MCMC and SRRW are addressed as follows:\n1. **HDT-MCMC v.s. Baseline MCMC:** Our Theorem 3.3 shows HDT-MCMC reduces sampling variance by a factor of $1/(2α+1)$ compared to baseline MCMC:\n$$\nV^{HDT} (α)=\\\\frac{1}{2α+1} V^{base}.\n$$\n$V^{base}$ is defined via transition kernel’s spectrum in Eq. (4) in Line 215 and is also related to spectral gap and mean hitting time [Aldous et al. 2014, Remark after Theorem 2.17 & Eq. (11.4)], where graph with higher connectivity usually ensures smaller spectral gap and mean hitting time. However, HDT-MCMC *uniformly* reduces variance by the $1/(2α+1)$ factor. Corollary 3.4 adds that a more efficient baseline *amplifies* this gain: the better the baseline, the more HDT lowers the variance, regardless of the graph or target measure.\n2. **HDT-MCMC v.s. SRRW:** Our Lemma 3.6 highlights HDT-MCMC’s cost-based variance reduces by a factor of $\\\\frac{2}{\\\\mathbb{E}\\_{i∼μ} [|\\\\bar{\\\\mathcal{N}}(i)|]}$ compared to SRRW. The average degree $\\\\mathbb{E}\\_{i∼μ} [|\\\\bar{\\\\mathcal{N}}(i)|]$ (including self-loops) depends on graph density and the target measure $\\mu$. Even for a sparse graph with an average degree of $3$, the factor is smaller than $0.5$, translated into over 50% variance reduction compared to SRRW under limited budgets. Gains are more pronounced in denser graphs (higher average degree under $\\mu$), making HDT particularly effective for large, high-degree networks, as shown numerically in Figure 3 and around Lines 418 - 423.\n\nD. Aldous et al. \"Reversible Markov chains and random walks on graphs.\" Unfinished monograph, 2014.\n\n---\n## Additional experiments on non-uniform target\nWhile we use the uniform target in our paper, we've added experiments targeting degree distribution on more graphs to address this. Due to space limits, these results are in the PDF with a link in the response to reviewer mrvq.", "claims_and_evidence": "The claims are supported by theoretical and empirical evidence. See below.", "methods_and_evaluation_criteria": "The authors compare a variety of MCMC algorithms against their new “history-driven target” (HDT) counterparts, and consistently find faster convergence to a uniform target distribution. They consider facebook (N=4039) and p2p-Gnutella04 (N=10876), with a few more graphs in the appendix. They also compare to SRRW for fixed computational budget. Whilst this convincingly backs up their core claims, I wonder if the authors could have tried some more ambitious applications of graph-based MCMC to show real-world advantages of HDT over existing methods – i.e. faster convergence to the target distribution actually unlocking better performance in things directly relevant to ML practitioners.", "theoretical_claims": "The authors prove that their HDT framework converges almost surely to the original target distribution and achieves variance reduction compared to the base sampler in the CLT. They show further variance reduction relative to SRRW that depends on the average neighborhood size. I did not check the proofs in detail, but all theoretical proofs seem reasonable.", "experimental_designs_or_analyses": "See above. The experiments do indeed back up the authors’ central claims, but they do not convincingly demonstrate downstream benefits for ML or scaling to very large graphs. Only a limited number of graphs are considered (2 in the main body, and a few more in the appendix – by my count, 2). Do all experiments take a uniform target distribution? If so, this also seems restrictive.", "relation_to_broader_scientific_literature": "Improving MCMC graph sampling algorithms to encourage efficient exploration is a storied line of work – e.g. Metropolis Hastings with delayed rejection reduces repeated rejections (Green & Mira, 2001), and multiple-try Metropolis proposes multiple candidates at each step and picks one based on their weights (Liu et al., 2000; Pandolfi et al., 2010). The authors’ method can be used to enhance each of these variants by introducing a history-dependent target distribution, as demonstrated in Fig. 2. It provides a computationally cheaper alternative to SRRWs, introduced by Doshi et al. in 2023.", "essential_references_not_discussed": "The references seem reasonable.", "other_strengths_and_weaknesses": "**Strengths**:\n- Clear presentation of a novel idea (history-driven targets), capable of enhancing a range of previous graph-based MCMC samplers using information about walker history\n- Impressive theoretical contributions\n- Central claims of more efficient graph sampling are backed up by Figs 2 and 3\n- LRU caching scheme seems reasonable to further reduce computational cost\n\n**Weaknesses**:\n- Limited number of graphs considered, and limited evidence of benefits for downstream ML tasks (though I don’t doubt that they exist)", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- Can you demonstrate downstream benefits from improved efficiency of graph sampling in ML algorithms?\n- How do the gains provided by your scheme depend on the properties of the graph? What properties of the graph govern the size of the gains? (I appreciate that this is a big one…) Also, how do the gains depend on the target measure?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary.**

The topic of this work is MCMC (Markov Chain Monte Carlo) on discrete spaces. Specifically, the paper introduces the so-called **HDT (History-Driven Target)** framework for improving existing MCMC sampling algorithms over discrete spaces.

The method shares strong conceptual similarities with the previously introduced **SRRW** (Self-Repellent Random Walks) [Doshi et al., 2023] framework, in as much as the method is **adaptive to the empirical distribution**: less visited states tend to gain increased probabilities of future visits.

However, the key conceptual difference is that one modifies the target distribution based on the current empirical distribution, instead of modifying the transition kernel (SRRW).

As a secondary contribution, the authors propose a cache scheme for reducing memory requirements.

**Strengths.**

* The method achieves a variance reduction compared to the base sampler which is at least similar to SRRW and even more pronounced on denser graphs.
* While SRRW could only be applied to reversible MCMC algorithms, the newly proposed method can also be applied to non-reversible MCMC algorithms.
* The new method is less computationally expensive than SRRW.
* The quality of the writing is very high. Clarity of the paper has been praised by the referees.
* Both theoretical and empirical justification for the claims.

**Weaknesses.**

* The experimental value was considered to lack ambition.

**Discussion and reviewer consensus.**

* There is a consensus among the reviewers that the paper should be accepted.
* Reviewers are enthusiastic about the paper; it has received a lot of praises.
* There was an original concern about initialization, but that was rebutted.
Decision: Accept (oral)