Estimating Hitting Times Locally at Scale
Authors: Themistoklis Haris
Fabian Christian Spaeh
Spyros Dragazis
Charalampos Tsourakakis
Venue: NeurIPS 2025 poster ()
Keywords: random walks
hitting times
local algorithms
graphs
effective resistance
markov chains
Primary area: theory
TL;DR: We develop local algorithms for estimating hitting times and effective resistances.

Abstract: Hitting times provide a fundamental measure of distance in random processes, quantifying the expected number of steps for a random walk starting at node $u$ to reach node $v$. They have broad applications across domains such as network centrality analysis, ranking and recommendation systems, and epidemiology.  

In this work, we develop local algorithms for estimating hitting times between a pair of vertices $u,v$ without accessing the full graph, overcoming scalability issues of prior global methods. Our first algorithm uses the key insight  that hitting time computations can be truncated at the meeting time of two independent random walks from $u$ and $v$. This leads to an efficient estimator analyzed via the Kronecker product graph and Markov Chain Chernoff bounds. We also present an algorithm extending the work of Peng et al. [2021] that introduces a novel adaptation of the spectral cutoff technique to account for the asymmetry of hitting times. This adaptation captures the directionality of the underlying random walk and requires non-trivial modifications to ensure accuracy and efficiency. In addition to the algorithmic upper bounds, we also provide tight asymptotic lower bounds. 

Finally, we reveal a connection between hitting time estimation and distribution testing, and we validate our algorithms using experiments on both real and synthetic data.

Estimating Hitting Times Locally At Scale
Themistoklis Haris Department Computer Science Boston University
Fabian Spaeh Celonis
Spyros Dragazis
Department of Computer Science Boston University
Charalampos Tsourakakis Department of Computer Science Boston University
Abstract
Hitting times provide fundamental measure of distance in random processes, quantifying the expected number of steps for random walk starting at node u to reach node v. They have broad applications across domains such as network centrality analysis, ranking and recommendation systems, and epidemiology.
In this work, we develop local algorithms for estimating hitting times between a pair of vertices u, U without accessing the full graph, overcoming scalability issues of prior global methods. Our first algorithm uses the key insight that hitting time computations can be truncated the meeting time of two independent random walks from and v. This leads to efficient estimator analyzed via the Kronecker product graph and Markov Chain Chernoff bounds. We also present an algorithm extending the work of Peng et al. [2021] that introduces novel adaptation of the spectral cutoff technique to account for the asymmetry hitting times. This adaptation captures the directionality of the underlying random walk and requires non-trivial modifications to ensure accuracy and efficiency. addition to the algorithmic upper bounds, also provide tight asymptotic lower bounds.
We also reveal connection between hitting time estimation and distribution testing, and validate our algorithms using experiments on both real and synthetic data'.
Introduction
Markov chains are fundamental framework for modeling random processes, with widespread applications across scientific domains including bioinformaties [Krogh, 1998], economics [Chib and Greenberg, 1996], and network science [Xia al., 2019]. They are particularly prominent in modern machine learning, natural language processing [Almutiri et al., 2022], and the analysis of large-scale social networks [Amati al., 2018), where the underlying graphs can massive. In such settings, storing processing the entire graph globally is often infeasible due to memory or computational constraints. This motivates the development of algorithms that access and process only small portion of the graph graph-so-calleds local algorithms.
In this work, we study the problem of computing the hitting time statistic between two vertices in an Markov chain. The input is an undirected graph G, where we consider simple random walks: from any vertex, the next step is chosen uniformly random among neighbors. Given two vertices and v the hitting time (c v) is defined as the expected number of steps required for random walk starting at u to reach v for the first time. This quantity is fundamental measure the analysis
'The code is available at https: /tt/ttttttttbut// com/ tkhar hhttthitttiggggggggeeeeeeetgittt time- aatee-at-se at-scale. Work done partially while Boston University.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

of random processes and has been extensively studied from various theoretical perspectives [Port and Stone. 1967, Patel et al., 2016, Aldous, 1989, Janson and Peres, 2012, Sauerwald and Zanetti, 2019, Oliveira and Peres, 2019, Feige, 1995, Cohen et al., 2016]. It also serves as crucial building block in several algorithmic applications, including recommender systems [Cooper et al., 2014] and learning mixtures of Markov chains [Spaeh et al., 2024].
Despite its importance, computing hitting times exactly is computationally expensive, requiring up to O(n") time in the worst case [Xia et al., 2019]. To address this, several approaches have been developed that either approximate Hş(u. v) [Cohen et al., 2016] or impose structural assumptions on the input graph to enable more efficient computation [Von Luxburg et al., 2010]. However, these methods are inherently global: they require access to the entire graph to produce an estimate. This global nature poses a significant scalability challenge, making such algorithms impractical for massive graphs with millions or billions of nodes.
In this paper, we introduce a suite of algorithms that estimate hitting times locally, by executing a small number of short random walks centered around the vertices u and v. We rigorously analyze these algorithms and formally prove that they achieve approximation guarantees comparable to those of global methods-while operating with significantly lower time complexity and without requiring access to the full graph.
Related work Our work is closely related to that of Peng et al. [2021], who design local algorithms for computing the effective resistance Rer(u, v) distance measure that captures the voltage difference between u and v when one unit of current is injected at and edges act as electrical resistors. Their approach is based on spectrally decomposing the random walk transition matrix, interpreting Rer(u, v) light-tailed sum that can be efficiently truncated. Effective resistance linked to the hitting time as Hu(u, v) + HG(r, u) = 2m Rer(u, v). As a result, the hitting time can be efficiently estimated using the effective resistance in graphs where Ho(u, u) x Ho(", u), such as vertex transitive graphs. However, real-world networks exhibit an asymmetric and skewed hitting time distribution, meaning that new ideas beyond the work of Peng et al. [2021] need to be introduced.
We also build directly on the work of Cohen et al. [2016], who derive an identity expressing the hitting time in terms of the Laplacian of the graph G. While powerful, their algorithm remains global in nature. Finally, key component of our method is the connection between hitting time and the notion of meeting time-the expected time for two independent random walks, starting at u and v, to meet. Related concepts such as the coalescence time have been studied extensively and are known for many specific graph families [Kanade et al., 2023, Cooper et al., 2013, Oliveira, 2012]. We utilize this connection from algorithmic lens, using it to obtain an efficient and practical estimator.
Our Results
We summarize our main contributions below:
1. We design and analyze an efficient local algorithm for estimating hitting times, based on novel analysis of meeting times (Algorithm 1). We demonstrate its practical effectiveness through extensive experiments on both synthetic and real-world datasets (Section 6).
2. We extend the spectral cutoff technique introduced by Peng al. [2021] derive an alternative local algorithm for hitting time estimation (Algorithm 3). While generally less efficient than our meeting-based method, can outperform it in certain settings.
3. We provide a detailed theoretical study of the trade-off between approximation and sample complexity in hitting time estimation, including both upper and lower bounds (Section 5).
4. We uncover a theoretical connection between hitting time estimation and sublinear-time property testing (Subsection 4.1).
2 Preliminaries
Let G = EV, be an undirected graph with (n, m) = (EV),EE) and A E {0, 1]axx be its adjacency matrix. Let D be diagonal matrix containing the degrees of the vertices in V in its diagonal. Let P A be the row-stochastic transition matrix of G. Throughout, we assume that G is connected and the associated random walk aperiodic. is known that the transition matrix has full spectrum

---

t = 1> 2 2 An > -1. A random walk in G is a sequence of vertices (X))120 such X, V and
Pr|X++1= = X; = uj deg(u) Puv
We also let be the stationary distribution of G. where 7e deg can be shown that any initial distribution over the vertices eventually converges to π.
Definition 2.1 (Mixing Time). The s-mixing time G is defined as:
mix = fmx = min(t: max I|=P" allrv S
xEA,
Definition 2.2 (Hitting Time). Let u. U V. The hitting time Ho(u, v) is the expected number of steps required reach from In other words, we let T min (t 2 0: X₁ v) then
Hc(u, E Xo = u].
The following useful Lemma expresses Ho(u, v) in terms of the Laplacian -- I-PT Let use e, R" to denote the v-th vector of the standard basis.
Lemma 2.1 ([Cohen et al., 2016]). It true that:
(I (I-PT)*Xxu )
Ho(u, v) 11-1e
(I)
Sv
We define the effective resistance Rar(U, v) in terms of the hitting time, although other equivalent definitions also exist [Spielman, 2019]:
Rar(u, v) (Hc(u, Ho(u, u))
2m
We shall make scarce use of the Kronecker Product between two graphs.
Definition 2.3 (Kronecker Product). The Kronecker product of two graphs G (Va, Ea) and = (Va x VH, EGxH) where (u,v), (w, 2}) E EGgH
H =VH, E④) ) defined as graph and only if w) EG and (v, E En-
Additional preliminary definitions and results are shown in Appendix A.
3 Meeting Time Perspective
Our primary contribution is an algorithm that estimates the hitting time by relating to the meeting time of two parallel random walks starting at and We simulate the walks step-by-step, accumu- lating terms in the hitting time sum until they meet. Due to the cancellation structure of the infinite sum defining Ho(u, v), this truncated computation suffices. Our algorithm is given as pscudocode in Algorithm I.
To analyze Algorithm 1, we first bound the meeting time in probability using the mixing time:
Lemma 3.1. Let (Xi)ao and (Y:)c20 be two random walks starting at states Xo and Yo Let T' min 2 0: X,, Y.) be the meeting time of the random walks. Then,
( ( exp (- (_||TG 112t ))
Pr[T 50
72t
Proof. The proof uses Markov Chain concentration bound the Kronecker product G G and is included in Appendix B.
Next, we argue that we make tmax large enough, all the random walks will, with high probability, meet before then.
Lemma 3.2. Algorithm I outputs Failure with probability at most 1

---

Algorithm 1: Estimating the Hitting Time via Meeting Times
Graph (V, F.), vertices u, v E V, mixing time mix: accuracy Output: Estimate H., of the hitting time (u) Define
Input:
100 mix In Ta(u)Ta(o)
B
21 max Inn
maxx
|
and
=
a (
Initialize random walks X for E I with I = (1, .1.,.....
8 Initialize random walks y for j E with J = 21,2......
Let Huv f-
7 for / = 0,1,2..... mmax do
Let Fw == 1ii E T x
w)l and yu = Mi E J: v(0) w)l for each E V.
for w E V do
10
2 min( y
Remove arbitrary indices i E / for which x, and indices j for which Y w.
11
Update
iuw t Huw + Ye Zv
{ {T)
Advance the random walks ( for i E I and Y for E J by one step as defined by G.
13
14 / = @ then
15
return Hue
16 else
17
return Failure
Proof. Let us pretend that random walks Algorithm 1 continue after meeting and are not eliminated. Let then Tú min(t (t 2 0 x = y, E Nzu be the meeting time of the of the i-th random walk starting from u and the j-th random walk starting from v.
Let be the event corresponding to Tig S Imax for i, E [0]2. We claim that, conditioned on E, Algorithm 2 does not output Failure. Consider bipartite graph G = (VB, Fig) where VB = A B correspond to the random walks X and Y. The edges of this graph represent the meeting event of two random walks and they are provided in online manner: in timestep t = 0, 1,... max we see observe a set of random walks in A meeting another set of random walks in B for the first time. In other words, observe all the edges A, x B, where A, S A and B, S B. Once an edge has been given, it is not given again, so this a partition of the edge set of the graph.
with A| = B
fmax is a partition of all the edges. Since & occurs, the bipartite graph is complete and {A, B, I t=o Our algorithm tries to produce matching a between and by greedily matching and removing vertices as the edges appear in batches. We output Failure if and only if we fail to output a matching. We claim that, given ε, we will always find matching.
This can be seen via an inductive argument: we claim that before any timestep & we have a valid matching over all vertices that have appeared as part of previously revealed edges. This easily holds at é = 0 because the initial matching is empty. Suppose then that it holds for some t. When the edges A, X B, are revealed, consider the subsets A S A, and B' S B, of unmatched nodes. There has to exist perfect matching in A x B' because all those edges are revealed. We pick any such matching arbitrarily and so our matching is successfully extended.
Finally, we need to bound the probability that & holds. We know that for any i, E [$] we have:
Pr[Ti. [max] 00 (
(VVT(())(()) exp
(- uttmax
))
72t

---

Hence, by a union bound over (2) pairs of random walks;
C
|| [
Pr (=a(w)malo)
exp
72/
by our choice of maa and L, where we can assume & S n as an upper bound.
Next, express the hitting time function of random walks that stop upon meeting. To that end, we first show a structural result similar to [Peng et al., 2021]: By spectrally decomposing the Laplacian matrix, subsequently truncate the tail.
express the hitting time infinite series, from which we can
Lemma 3.3. Let W == PT AD-! The following identity holds:
Ho(u, Σ
(1
T(U) (1)
W W'Xue Xuv
(3)
We prove this lemma shortly, in Section 4. With it in place, meeting time analysis proceed.
Lemma 3.4. Let (Xt) and (Yt) be two random walks in G starting from Xo and Yo respectively. Let T minft 0: X, Yi} be a random variable for the meeting time of the two random walks. The following holds:
Σ (1 -1 1|x
HG(u, v) = E
LTT
Proof. The hitting time formula of Lemma 2.1 can be written as an infinite sum. Algebraic manipula- tion then gives that:
T
Ho(u, v)
To(U) 1, W W Xuv
1
Σ Pr(u 3² w|
Pr/u +" 1)
Σ wEV
Pr(v +² w] TG())
Pr(c - v)
TT(
WEV
(Pr[u -² v] - Pr(u -² ol)
(because G is connected)
(v)))
Due to memorylessness, (Xe) and (Ye)ez have the same distribution. Hence,
Tc(u) =
(Pr(v- - b] Pr(u + vl)
E
11 [X==]] - 1 (x
E
Y= - 1 (x1=0)
+ +
Σ 12T
[1 xi==
KT
E
1 M=zo
11 (xx==0)
lTT
We conclude our analysis by showing that algorithm approximates Ho(u, v) well.
5

---

Lemma 3.5. If Algorithm I does not fail, it outputs estimate H == Ho(u, v) where (Ho(u,)) Ho(u, u)] S with probability at least 1/n.
Proof. Let us denote with (x,") 120 and (Y, (1)()) )220 the i-th random walk starting form and v, respectively. Let A, (0 v
T: x et} be the number of times that the i-th random walk X() visits before it gets eliminated by meeting time T. We define B, accordingly for y which allows us to write the output of Algorithm as
(B, (A,) TT(U)
and we immediately that [[]] H)(u, v) by Lemma 3.4. If the algorithm does not report failure, we know that A,, B, S fmax and hence B, 16-44 -Ail S 2tmax. By a Hoeffding bound,
Pr H Ho(u, w)Il 20] s 2ee (- [
(
1
21 max
for our choice of f.
Finally, arrive at the following Theorem:
Theorem 3.1. There exists an algorithm that, given any u, v V outputs, with probability at least 1 2/n, an estimate H such that I|I Ho(u, v)] and has total runtime
o
(
112 (v) E² log" (T((()) To(()) )
13
mix
n
Proof. The runtime follows directly from Lemmata 3.2 and 3.5 with a union bound.
3.1 Effective Resistance Calculation
Having established Theorem 3.1, we can use to calculate the effective resistance Rar(u, v).
Algorithm Estimating the Effective Resistance Meeting Times
Input: Graph G (V, EV, vertices u, v V, mixing time mixx accuracy
2 Output: Estimate It of the effective resistance Ro (u, v)
Huv HITTINGTIME(G; u, tmixx em/2)
H HITTINGTIME(G U, u, mixx, em/2)
5 R + 1 (Hiw + Hvw)
2m
return Nt
Corollary 3.1. There exists an algorithm that, given any u, outputs, with probability least
1 1/n n an estimate R. such that R Reg( u. v) S and has runtime
o
1
p m log²
n
| 1
(T(l) TT(V)
where Nu, = min (u)) =c(1)}.
Proof. Running Algorithm with e = 2m we get that:
- R Run (u, v)
(H., Ho(u,v) + (Ho. Ho(u,u)) S
2m
The runtime follows from the runtime of Algorithm

---

Hitting Times via Spectral Cutoff
In this section we describe yet another local algorithm for estimating the hitting time Ha(u, u) between vertices and We first prove the spectral decomposition result from earlier.
Lemma 4.1. Let W = =PT AD-1, The following identity holds:
80
_
Ho(u, v)
Σ k=
1
W Xux
((U)
Proof. Let Y1 2 A2 2 ...2 An be the spectrum of W, so the eigendecomposition of W is:
W =
where the vectors Wi,... Wn form an orthonormal basis. Note that À = 1, so we can write the pseudo-inverse of W
n (I W)+
Σ - 2g w
j=2
Then have by the of an infinite geometric series that:
00
0c
-
ΣΣ
E( w w
f=
==
Now substitute back to the hitting time calculation of Lemma 2.1:
00
) (w3 www Xxur "xwr
Σ 1 1
π()) m W'xwv
T
Hc(u,v) 2
e.
(5)
1=0
since wi Xue = because W1
1
L
Our local algorithm for estimating the hitting time Hp(u, v) relies on Lemma 4.1. We identify
T threshold such that truncating the sum (1 ক e,,) W Xu. incurs additive error up to from the total sum. Then, we estimate the rest using a collection of independent random walks.
Algorithm 3: A "Cutoff" Algorithm for Estimating Hitting Times
Inputs: Adjacency matrix and degree query access to graph G, Vertices u, v E V.
Output: Estimate (w, v) of the hitting time Ho(u, v).
3 Parameters: Spectral gap A E 1),, > 0
Let E + log x-Ex (/g(1/A)
8 Initialize ho(s, + O. for i 0 l do
Let +- 32 log(40e)
<²x(1)²
Execute random walks from length i and let T, T2 be the number those that end in u and v respectively.
Let Pi,.. - deg(u)
deg(u) T. Update ha(u,v) v) hu(u, + (pi, D
2m Ta and Pi, +
2m
Output (io(u,))

---

Theorem 4.1. Algorithm 3 returns an estimate hi(sst) t) such that with probability at least 9/10 it holds that:
(ol(s,t) Hc(s,t)
Is runtime is bounded by
e
log 8-88 log x
TT(2 loge): where (=
for the spectral gap == max AalB of
Proof. The proof is given in Appendix C.
Remark 4.1. Using this algorithum in the formula Reg(u, u) 2m (Ha(u, Ha(v, u)) gives us an algorithm with roughly the same runtime is Algorithm of Peng et al. [2021].
4.1 A Connection with Property Testing
In Algorithm 3, we define the "cutoff" point for the hitting time sum by spectrally decomposing the Laplacian matrix, done by Peng al. [2021]. However, this approach requires knowing the spectral gap A, which can only be computed by analyzing the entire graph, and is related to the Markov Chain's mixing time, which may be arbitrarily large.
To address this, we propose a local truncation method. Intuitively, if the states u and v are "close", random walks from both should converge quickly, even with large mixing time. We introduce
local mixing time (e) (u, v) and show that when the Markov Chain converges quickly, the cutoff point is determined by this local mixing time. This result follows from convergence lemma for ergodic Markov Chains [Freedman, 2017]. Though we focus on the effective resistance problem for simplicity, the theory extends to hitting times well.
The challenge then becomes determining (s) (u, v), which we solve using property testing algorithms [Batu et al., 2013, Chan et al., 2014] to perform a binary search for a good upper bound. These algorithms run in sublinear time, making our method also sublinear. Under mild convergence assumptions, this approach removes the need for X and (mix- yielding a fully local algorithm. Details of this theoretical development can be found in Appendix
5 The Optimality of Walk Sampling
In Appendix D we use Chernoff bound for Markov Chains to analyze possibly the simplest local algorithm for hitting time estimation: sample a number of arbitrarily long random walks and return the average hitting time. Our analysis yields the following result:
Theorem 5.1. Let M be an ergodic Markov chain with stationary distribution и. Let 8 and be two different states. There exists an algorithm calculating the hilting time Ha(s, to within absolute error of e with probability at least that uses
δ
mix
ग. (1)
random walk samples of length at most (tmmix/ (t)).
Could we have sampled fewer random walks in similar fashion and aggregated them obtain good estimate? In Appendix E we answer this question in the negative: the walk sampling algorithm has optimal sample complexity. Our proof involves carefully constructed "barbell" graph and utilizes anti- coneennncettation arguments for the geometric and binomial distributions.
Theorem 5.2. Suppose an algorithm is able to estimate HG(u, v) within additive error e with constant probability of success by taking the average length. Then, in the worst case, we must have that:
random walk samples of unbounded
T Ω
mix
2
8

---

2
Un
U2
U1
Kn
Uy
n
Figure 1: "barbell"-iit graph: star, path and a clique
These results demonstrate that estimating hitting times is inherently computationally hard. Nev- ertheless, our local algoribmss-depite having comparable theoretical runtime to the sampling outperform it in practice.
Experimental Results
In this section, perform comparative study of different algorithms for estimating the hitting time (u v) between vertices u and v. Our experiments are conducted in Python 3.6 with Numba 0.53 on 2.9 GHz Intel Xeon Gold 6226R processor with 384GB of RAM.
Kiriig This Alpattin
Nustin Tims Agoithi Alpniaa
Mesting Time Aorthr Agaatla
1.5
Ageill
bust geeetre
bus Aggrttm
2.00
222
130
20.0 Number warm
3153
8:00
60.00
$.00
1000
1E30
Mumber wolts
Tux mede
10/
Caal
bus Ageetvr
DV
Keriin Alarthn
Hesting
Semping Ageetvs
Sampling
10
Musiig Agerttre
Mastin Aigetinn
Nesing This Alaatiin
Larplng Agaiter
Semplig Rigeles
+
Gadd goike
+
Couf Algrilen
Ceull Agrilln
0.-
3.03
13.0
05.00
10000
0..0
4.03
60.0
30.00
10:50
2000
4.00
430
30.0
19.0
Sumder
Kamber
Nander
Figure Hitting time estimation on synthetic networks as a function of the number of nodes. Depicted are: Barabasi-Alber graphs (left), Erdos-Reny's graphs (middle) and Stochastic Block
Model (SBM) Graphs (right).
We compare between Algorithm 1, Algorithm 3, the walk sampling algorithm and an exact solver which determines Ho(u, v) by solving linear system: Let H E IR" be such that H. Ho v). Then, for every u E V we have: H., = Ha(u, v) E N(1)) deg(u) H..
Additional information on our experimental setting, experiments with parallelization, and other ablation studies can be found in Appendix G.

---

Synthetic Datasets We first compare the performance and eтror of each of those algorithms on synthetic graph datasets. We focus on three random graph models: Frdös-Rénye where each pair of vertices forms an edge with probability p. Barabási-Albers where a preferential attachment mechanism used, and the Stochastic Block Model (SBM), where we model the emergence of community structures. We estimate the hitting time from the first to the last node. We compare the relative error, running time and number of sample walks.
Our experiments show that our algorithms estimate the hitting time with low relative error. Among the methods evaluated, the naive walk- sampling algorithm performs the worst, requiring more samples and yielding weaker error guarantees. In contrast, the meeting- time-basedddded algorithm is highly efficient while also maintaining very low error. It also notably exhibits much lower variance in the error than both the sampling algorithm and the cutoff algorithm.
Real World Large Graphs We also run our algorithms on real world graphs, specifically the American Football Division IA games graph [Girvan and Newman, 2002] and the SNAP Facebook and Twitter graphs [Leskovec and Mcauley, 2012]. To stress test our algorithms adequately, we randomly sample pairs u, uniformly, but also proportionally and inversely proportional according to the product degrees or Pagerank centralities Page al. [1999]: Figure 5 in Appendix shows the correlation between hitting times and the degree and Pagerank centrality products. We find that Algorithm consistently achieves low error with small variance. Note also that we were not able to compute the true hitting time for the Twitter via (sparse) linear system. Thus, report the mean absolute and mean squared error compared to 100 iterations of the meeting time algorithm, as is the only algorithm which is unbiased.
Table 1: Relative estimation error for different pair sampling strategies.
deg(u) deg(v)
pagerank(u) prop
pagerank(()
Algorithm
uniform
prop.
inv-prop.
inv-prop.
Football
Meeting Time Alg.
0.013 1 0.009
0.012 1 0.009
0.012 1 0.009
0.011 T 0.009
0.012 1 0.009
Cutoff Alg,
1.061 + 0.778
1.047 = 0.805
1.061 0.806
0.983 + 0.763
0.994 0.778
Sampling Alg.
0.025 + 0.019
0.025 = 0.019
0.026 + 0.019
0.025 + 0.019
0.025 = 0.019
Facebook
Meeting Time Alg.
0.011 = 0.010
0,011 + 0.010
0.016 0.014
0.016 + 0.017
0.012 0.011
Cutoff Alg.
0.078 + 0.096
0.108 = 0,129
0.253 + 0.297
0.193 + 0.357
0.147 = 0.156
Sampling Alg.
0.026 + 0.020
0.025 + 0.021
0.030 0.025
0.026 + 0.021
0.027 = 0.021
Twitter
Meeting Time Alg.
0.002 + 0.001
0.002 + 0.002
0.010 + 0.007
0.009 + 0.007
0.005 = 0.004
Cutoff Alg.
0.022 + 0.016
0.023 + 0.017
0.162 + 0.126
0.102 + 0.077
0.086 = 0.066
Sampling Alg.
0.025 1 0.019
0.024 1 0.018
0.026 1 0.019
0.027 1 0.020
0.024 1 0.018
Limitations
Our local algorithms approximate Ho(u, v), with accuracy depending the graph's structure- typical trade-off for efficiency. Our algorithms can be thus less efficient when the mixing time is large, though this also affects prior methods.
7 Conclusion
We presented theoretical and empirical results on efficient estimators for hitting times in random walks, bridging Markov chain theory with sublinear-ting time algorithms. Future research directions include establishing universal lower bounds, and exploring applications of such algorithms in domains like recommender systems.
10

---

References
David Aldous.
Hitting times for random walks on vertex-transitive graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 106, pages 179-191. Cambridge University Press, 1989.
David Aldous and James Allen Fill. Reversible markov chains and random walks on graphs, 2002. Unfinished monograph, recompiled 2014, available at http:://ww.. stat. berkeley. edw////eeeedeeeee Mimballouu//A//boooll html.
J Aldous. Some inequalities for reversible markov chains. Journal the London Mathematical Society, 233):564-57, 1982.
Talal Almutiri, Farrukh Nadeem, et al. Markov models applications in natural language processing: survey. Int. J. Inf. Technol. Comput. Sci, 2:1-16, 2022.
Viviana Amati, Alessandro Lomi, and Antonietta Mira. Social network modeling. Annual Review of Statistics and Its Application, 5(1):343-369, 2018.
Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White. Testing closeness of discrete distributions. Journal of the ACM (JACM), 60(1):1-25, 2013.
Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant. Optimal algorithms for testing closeness of discrete distributions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1193-1203. SIAM, 2014.
Siddhartha Chib and Edward Greenberg. Markov chain monte carlo simulation methods economet- rics. Econometric theory, 12(3):409-31, 1996.
Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-hoefdiing bounds for markov chains: Generalized and simplified. In STACS, volume 14 of LIPIcs, pages 124-135. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2012.
Michael B Cohen, Jonathan Kelner, John Pecbles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In 2016 IEEE 57th annual symposium on foundations of computer science (FOCS), pages 583-592. IEEE, 2016.
Colin Cooper, Robert Elsasser, Hirotaka Ono, and Tomasz Radzík. Coalescing random walks and voting on connected graphs. SIAM Journal on Discrete Mathematics, (((4)::748-175))) 2013.
Colin Cooper, Sang Hyuk Lee, Tomasz Radzik, and Yiannis Siantos. Random walks in recommender systems: exact computation and simulations. In Proceedings of the 23rd international conference world wide web, pages 81 1-816, 2014.
Uriel Feige. A tight upper bound on the cover time for random walks on graphs. Random structures and algorithms, 6(1):51-54, 1995.
Ari Freedman. Convergence theorem for finite markov chains. 2017.
Michelle Girvan and Mark EJ Newman. Community structure social and biological networks. Proceedingss of the national academy of sciences, 99(12);7821-7866 2002.
Svante Janson and Yuval Peres. Hitting times for random walks with restarts. SIAM Journal Discrete Mathematics, 26(2):537-547, 2012.
When is coalescing as fast as meeting? ACM Transactions on Algorithmss 19(2):1-46, 2023. Varun Kanade, Frederik Mallmann-Treem and Thomas Sauerwald. On coalescence time in graphs:
Anders Krogh, An introduction to hidden markov models for biological sequences. In New compre- hensive biochemistry, volume 32, pages 45-63, Elsevier, 1998.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. Advances in neural information processing systems, 25, 2012.

---

Nima Mousavi. How tight is chermoff bound. Unpublished manuscript, 2010.
Roberto Oliveira. On the coalescence time of reversible random walks. Transactions of the American Mathematical Sociery, 364(4))2199-2128, 2012.
Roberto Oliveira and Yuval Peres. Random walks on graphs: new bounds on hitting, meeting, coalescing and returning. In 2019 Proceedings of the Sixteenth Workshop Analytic Algorithmics and Combinatorics (ANALCO), pages 119-126. SIAM, 2019.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford infolab, 1999.
Rushabh Patel, Andrea Carron, and Francesco Bullo. The hitting time of multiple random walks. SIAM Journal on Matrix Analysis and Applications, 37(3):933-99) 9544, 2016.
Pan Peng, Daniel Lopatta, Yuichi Yoshida, and Gramoz Goranci. Local algorithms for estimating effective resistance. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1329-133 1338, 2021.
Sidney C Port and Charles J Stone. Hitting time and hitting places for non-lattice recurrent random walks. Journal of Mathematics and Mechanics, 17(1):35-5) 1967.
Thomas Sauerwald and Luca Zanetti. Random walks on dynamic graphs: Mixing times, hittingtimes, 2019.
and return probabilities. arXiv preprint
Fabian Spach, Konstantinos Sotiropoulos, and Charalampos Tsourakakis. Ultra-me: A unified approach to learning mixtures of markov chains via hitting times. arXiv preprint arXiv:2405. /5094, 2024.
Daniel Spielman. Spectral and algebraic graph theory. Yale lecture notes, draft of December, 4:47, 2019.
Ulrike Von Luxburg, Agnes Radl, and Matthias Hein. Hitting and commute times in large graphs often misleading. arXiv preprint arXiv: 1003. 1266, 2010.
Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. Random walks: review of algorithms and applications. IEEE Transactions on Emerging Topics Computational Intelligence, 4(2):95 107, 2019.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We design Algorithm and Algorithm 3 as local algorithms for hitting time estimation. We perform experiments in Section to verify our algorithms" performance.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

We provide full proofs of our claims in the main body of the paper and in the Appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmata that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We provide full pseudocode for our algorithms, as well as the datasets and parameters used in our experiments (Section 6)
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We include our codebase as part of our submission.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: /nipp..ccc ccppp.ccpppulcc///eecccc/ wetpiiiiiggiee...eeeeo/eooeoeeee /CodeSubmia (isoiicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section 6 we provide detailed deseriptions of our experimental setup.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In Figure 2 we showcase the error guarantees achieved by our algorithm.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
15

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We clarify our compute environment in Section 6.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that NeurIPS Code of Ethics https://neuripp: httppp///ourrrss.cpppllllle///// cttpublic//chhiccctteeellellllll
didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the
Answer: [Yes]
Justification:
We do not foresee our results to have any ethical implications.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Though they can used for algorithms analyzing social networks, our work has no direct social impact as it is focused on the mathematical understanding of theoretical problem.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not existing assets apart from popular Python libraries.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
We document our code in detail and provide guidelines for reproducing our results.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https:/ //tpr///eeu..peeeee wtteurrps.cc/ooffiiie 22LM/LLM for what should or should be described.
19

---

A Additional Preliminaries
In this Section we deposit additional preliminary definitions and lemmata essential to our main exposition.
Definition A.1 (Ergodic Markov Chains). Markov Chain is ergodic if it is aperiodic and positive recurrent. It is aperiodic when the ged of all possible return times any state is equal to 1, and it is positive recurrent if the expected return time to any state is finite.
We shall assume that the Markov chain defined G is ergodic, and that G is connected with minimum vertex degree at least 1. The following theorem describes the rate of convergence of an ergodic Markov Chain its stationary distribution π.
Theorem A.1 (Theorem 4.9 from [Freedman, 2017]). If P is ergodic, with stationary n, then there exist constants 0 < a < 1 and > O such that:
max wEV
(6)
More specifically, let be the smallest integer for which Puv > for all u, E V and = 1 min Pua, Then, the constants a, C above defined u.vEV x(0)
:2/ and C
We call and C the convergence parameters of the Markov Chain.
The following theorem is Chernoff Chemoff-Hooffding bound for Discrete-Time Markov Chains:
Theorem A.2 (Theorem 3.1. from [Chung et al., 2012]). Let M be an ergodic Markov Chain with state space [n] and stationary distribution Let
mmix (m)
minst: max =EAr
|| ~ Se}
be its s-mixing time for s < 1/8. Lel (V1,.., V/) denote a 1-step random walk on M starting from an
initial distribution on [n], i.e. V1 Φ. For every E [t], let fa [n]] - [0, 1] be weight function
at step such that Eu- [u)] = for all i. Define the total weight of the walk by:
X = ((()))
1=1
There exists some constant c such that:
Pr[X (1 8) < [cl@]] exp( 1aapp-52pdt (tt(()2)), for 0 5 5 [dll6)+ exp(-5ptt 8pt/ /jtt((2T)) (72T)), for 8 >>
(7)
Pr[X < (1 - ml] S c||0||> exp(-6" ul (72T)) for 0 < 881
(8)
where || || the n-norm induced by the inner product under the T-kernel:
(u, v)sr
Σ
T(1)
ic(m]
B Proof of Lemma 3.1
Lemma B.1. Let (X,)e20 and (Y))22 be two random walks starting at states X, and Yo
Let = minft 2 0: Xx Yr) be the meeting time of the two random walks. Then,
(-11 12tt
Pr[T > 5
exp
Voa(
72
Proof. Note that 2, (X,, Y.) V V can be modeled as a random walk on the Kronecker
product G x G. where TGxG 3) n (x))((v) and (mix x G) (G)) In order to apply
20

---

Markov Chain Chernoff bound (Theorem A.2), we define the weight function f(z, y) = 1 if x
and f(z,y) y) 0, otherwise. Let / = Er= f(x, Y.) and observe that t < if and only if F O.
Since TGxG (z, y) = (c(x)=a(V) we also have μ = || If 5 = 1, then Theorem A.2 gives:
Pr[T' > | Pr[F 0] = Pr[F 2 (1 0) 5o (Vra (VzO(u)T((()) exp (- ||TT ll
72t
C Proof of Theorem 4.1
In this Section we prove Theorem 4.1.
Theorem C.1. Algorithm 3 returns an estimate ha 1) such that with probability least 9/10 holds that:
hho(s Hc((s S
Its runtime is bounded by
E2 TT(2)² loge): where (= log g-2X
log 1
for the spectral gap À = max Amll of
Proof. It is easy to see that the algorithm runs in Ö(r(²), which gives us the claimed runtime. We therefore just need to argue about the algorithm's 's correctness. Analogously to the effective resistance approach taken [Peng al., 2021], we want find cut-off point for the series Equation That is, we want to find as small an f(E) as possible such that:
8-1
Holu, 0) - Σ
x(o)_1)
W Xun
S E
x(v)
2
We first spectrally decompose the i-th power of W:
W = Σ X 1n
before. Then, we have that:
1 1 1,
Wi
_ 1,
Σ xae Xuv
T(U)
n ((0) 1.. _
(Xirew3) Xun
(as w Xst 0)
1 ( 1.) (mmi,) Xuv
(Definition of A)
j=2
We give straightforward bound for the main term. if E n2.
1 (1- π(7) 11111 (mrw3) Xao S Mmmmll Xavlli S vn.
21

---

since we can choose wy so that
|| I|2 = 1. Thus:
Ha(s,t) - Σ (--1)
1, (1-
1 200 ((t)
)1)
Xat
$
X Nnnn n
<
x
n nvn
1- X
i=!
since < 1. Now, we aim set À such that:
A 1- nyn
E 2
It suffices, thus, to set our threshold to:
log
4ny/n 5-EX
log E-Eλ (og(1/A)
(1/)
Therefore only need to ensure that:
Too(u v) -
1
1 1, (())
W W'Kun
5
(9)
and then by triangle inequality we would be done. Our algorithm approximates, for each i {0, I.... l - 1 the following term:
1 π(v) 1.) W
Xuv W'xw
I.
T()) 1, W 1, II 1. W
x(v)
(1 w'1, 1. w'1))
T())
where the cancellations in the first equality follow from the fact that W = TT. Now we have that:
1 W'1, Pr/u -$ w] and 1. J'W,, = Pr(v 4 u]
where Pr(s + t] is the probability random walk starting from reaches in i steps. We estimate these probabilities by performing independent random walks starting at and letting T, and T, be the number of those walks ending up in u and v respectively. Then, we estimate:
2m Tu
2m
T.
Pi
deg(v)
r
and Pt deg(u)
We know that as a sum of indicators we have:
B[T.] Pr(t -² s]
and so the Hoeffding bound gives:
1
2 deg(t)
Pr
Pi,s
Pr[t
+ s]
Pr
T. E[T.]]
rr. 86m
T (1)
48
222²
< eex
64P2 .r)
< 1
208
when we set:
32F²
r 2
22 log(408)
Through simple use of the union bound over 28 sums, we conclude that Equation holds with probability least 9/10 which concludes our theorem.
22

---

D A Walk Sampling Algorithm
In this section we analyze a simple algorithm for estimating the hitting time Ha(s, t): sampling collection of random walks from of various lengths and counting how many of them hit t. The analysis uses Chernoff bound for Markov Chains [Chung et al., 2012].
Theorem D.I. Let M be an ergodic Markov chain with stationary distribution x. Let s and be two different states. There exists an algorithm calculating the hitting time Ha(s, t) to within an absolute error of e with probability at least 1 that uses
T2
(1))EE2
random walk samples of length at most (t)/=(t)), where the e-mixing time of M.
Proof. Recall the definition of the hitting time:
H i Pr = Xo ====s)) s)],
We wish to identify a threshold l such that:
i Pr = Xo = 8)] <E
In the context of Theorem A.2, let f(u) = if a = t and f(u) = otherwise. Then, f =
Ex~a [f(]]] = Prx [X = f| = st)). Suppose F(i) = Ejsi f(X)). Our distribution & has
weight 0 for all points other than so || |r v 10, Ø) V ক(क]
and thus we have:
Pr(F() < (1 [1- v
-82 pi
exp
(())
72T
Pr(F() <0 1
c
(t)i
exp
V (())
72T
where we chose
1. For all i, we have Pr(F 0) 2 Pr[Ti (t) = = s] and thus
8
Σ
(i+1) (r(Ti = (i + 1) = $) S Σ (i+1) Pr(F =
i=2-1
(-7(0)
S Vi(3) i=1-
Σ
(1+1) cxp
(27
Σ (i+1) 1) a²
Vi(s)
i=f-1
a--1
(l 1)a--1
Va(s)
(1 a1-a) a)²
1 a
2cl
Vi(s)
1-a
for a exp(-x < 1, where for the derivation we used differentiation on the geometric series. We seek some & that makes the tail have weight at most f2, for reasons we will discuss shortly, where - /2
2cl
d-1
3311 a) (Ts)
+ aal-1
(T(() 1 T-a
rf.
2c
c²(1 a) / (T)
(e-1) + In(() <
2c
23

---

1
Ed
a)
v (T()
In
4 4nne
In
2c
Since we must have that e 2 1, it suffices to set:
1,1 In (all-)y/nn
((())
T T())
(()
l max
In a
This means that it suffices to take random walks of length approximately equal to the e-mixing time. Next, we need to figure out how many of those random walks we need.
Assume now we perform r independent random walks from to t and record the number of steps as the random variables X1...., X,, Let use E denote the event that X; for all By another application of Theorem A.2 and our choice of e,
(()e 72T
Pr[X; > 4 Pr(F(O) S 0 S
exp
Σ
6
T(()
rl
and thus Pr
F.
S r.
by union bound. By the law of total expectation,
x - 1
x
E
E [X1]
E
[X1
E]
P
X
E
E
X
E|
S SPr
Pr E
X1 E.
ePr[[E]
Pr =inE
i=#+
PPr
Σ
i-Pr
2
On the other hand, by a Hoeffding bound taken after conditioning on we have that:
Σ x
Σ x
2r f
Pr
E
E
2
E
S 2 exx
we choose
Ig
T
r=
z²
(()
then, in combination with (*) we get that with probability least
7
Σ
x;
Σ
X
3
and that concludes our proof.
E Lower Bound to the Number of Sampled Walks
natural question is whether the upper bound established by analysis of the walk sampling algorithm is tight. In this section we answer this question in the affirmative, showing that the number of random walk samples required to estimate the hitting time is 22 graphs. This result can be interpreted in the sense that there no "free lunch" in estimating the hitting time of Markov Chain, there always pathological graphs that require many samples.
12 ==)) for certain class of
Our lower bound applies path. The main idea is that we can model the hitting time from the clique the start by the product On²² Geom(1 n). Arguing about the anti-concentration of geometric-like distributions we arrive at the desired result.
class "barbell" graphs with one star and one clique connected by
24

---

E.1 Preliminaries
Our analysis starts with the following standard anti-connenttattio bounds on the Binomial Distribu- tion:
Lemma E.1 (Anti-concenttration of upper tail, [Mousavi, 2010].. Let X,,..,, Xm be iid Bernoulli
random variables with parameter p. I 1/4, then for any t 2 0 we have:
2t
Pr
X mp +t 2 exp
(10)
mp
We this result to give a bound on the lower tail of the geometric distribution:
Lemma E.2. Let Y1, .,,..., Yx ~ Gcom(1/H) and Y = Ei Y, Let Y
L. Then if e is
positive constant with S p/2, have:
1 (- Pr exp
4kk 122
Proof. Let denote with Bin(r) the sum of r Bernoulii random variables with probability 1/μ. The event of having Y S k( corresponds to performing at most k(μ 5(ju-8 e) such Bernoulli trials before observing k successes. Alternatively, the number of successes in the first k(p E) Bernoulli trials is at least k. So:
Pr Y S - Pr (Bin -)) 2 k]
Let R[Bin(k(a c)) = k k Since 28, we have that 1r2 E/4 2 4²
and so by our
upper tail anti-concentration bound in Lemma E. we have:
Pr[Bink((p - <)) 2 k] = Pr
Bin(k( -e)) 2 U- + -
11.
2k?62
1
2
exp
4
112
k - kE/P
1
2k
exp
4
112 E/l
4ks
exp
Therefore, we get that:
4ks²
Pr [I - ul 2
2 exp
(-
112
desired.
We will also use the following "relaxation lemma" to decouple a random process into two easier-to- analyze processes and lower bound each anti-concentration separately.
Lemma E.3 (Anti- ConenConnenttationn Relaxation). Let T be a distribution over N with mean pe 2 1 and A be right skewed distribution over Rzo with mean μ. > O. Further, let T T and A1, A2,-.. ... A be independent samples. Define the random variables = Et= A, and Y = PAT with means μ = [E[X] B
μTHA Then we have:
Xt 2|2 S
Proof. Let X : ΣT Ao, where T and A, A are all mutually independent random variables. We have the following sequence of bounds:
E AX A
Pr|X < - Pr TSPT
25

---

I
S PT
A 3-
t=1
8 A
2 Pr
T S PT
ASH-E
(because T S (TT
Pr PT
Pr
A A
(independence)
P.d
t=1
Finally, because A is right-skewed, we can write:
Pr ヒー Pr|y uu- 4- Pr
Σ
A S MA
UT
MA
t=1
PT
NT
= Pr(y & p 1--66 -...P s Pr
A S
Σ
A
1=1
2 Pr|Y s p
as desired.
As corollary, consider applying the relaxation Lemma E.3 to the setting of an average of r random variables X,. We can change the definition of T relax the anti-concentration in that setting well: Corollary E.1. Let T be distribution over No with mean μT 2 1 and A be real, right-skewed distribution with mean μlAA O. Further, let T T and A1, A2.... A be independent samples. Define the random variables X -i= At and Y pATTT with means μ E[X] EE[] = PTMA- Then, suppose we have random variables X1 Xy, all independently and identically distributed. We have:
Pr I -
Pr
where Y2,..,,Y; are independently defined as Y, MA.. H..T.
Proof. Consider a random variable 7
Σ T3 where Ti ~ T. Suppose 7 ~ T'. Then:
T
X Σ 4
where A; ~ A is right skewed as scaling by positive value does not affect skewness. Since
uT TPT and μA F.A.A apply Lemma E.3 to get:
Pr
x, 1
Pr Σ Y S--
E.2 The Lower Bound Proof
We now proceed to proving our lower bound.
Theorem E.1. Let be graph and u, v be two different vertices of Suppose an algorithm is able to estimate Ho(u, v) within additive error with constant probability of success by taking the average over r random walk samples of unbounded length. Then we must have that:
==
mixx
in the worst case, where tmix is the mixing time of the graph.
26

---

Proof. Let G be a "barbell"- graph, as in Figure 3, consisting of cliques Y = {y11 ..., Gn and
star S ( Un2, J connected via a path P : (x Un + un-1 6 ++ 21 + y1)
2
Un
U2
U1
Kn
Uy
n2
Figure 3: "barbell"-like graph: star, path and a clique
Suppose we want to estimate Hy(U1 Un). Our estimation procedure samples r random walks from u1 and averages the time they take to reach un Let t, be the time it takes for the i-th random walk to reach Un. Then our estimator:
est :
LE
an unbiased estimator of the hitting time.
We claim that (( /E²) samples are required to guarantee that:
lest HH u,,] S
By a Theorem of Feige [Feige, 1995] for the hitting time in lollipop graphs, we know that the maximum hitting time from any vertex in PU Y any other vertex is O(n²). If the random walk starts from some vertex in S, then it takes it an expected O(n²) steps until reaches fn-1- By standard "drunkard's walk" argument Onn²). Therefore, by a Theorem of Aldous [Aldous and Fill, 2002, Aldous, 1982] stating that the mixing time is characterized by the maximum hitting time, we get that fmix Onn)), We also know that π (u,) = (l1) and therefore the O( (s²) lower bound gives us the desired ( lower bound.
conclude that the expected hitting time any vertex in Y is
mix/ (T(x//(TTT))))
For the remainder of the proof we focus on proving that r 2 22nn/=/) is required. Our proof relies on modeling the random walk from ii u, through a chain of independent samples from appropriate distributions. Consider a random walk starting at uj and let p be the probability that reaches before entering the clique Y. It is standard calculation that p 1/n: Let pe be the probability random walk reaches before entering Y it starts from u, By conditioning on the first step of the random walk, we get the recurrence:
P: (p: + Pi+1)
0. We solve this by p; n-it1 which gives the expression p Pn 1. Starting from in and conditioned on the event that does not reach uns the random walk can either follow the path, or become trapped in the clique. As a result, we can model the time takes for a random walk starting at 01 to reach un as:
with boundary conditions P1 1 and Pn+1
A
where ly Geom(1 (1/)) and:
A return time i1 in path P,
with probability Mun
with probability
return time to #y from clique Y,
where the A; random variables are all mutually independent. Both return times in the distribution of A; can be modeled geometric random variables. Thus, their mixture is right skewed, so can invoke Corollary E. to get that:
4sp-s
2
2
G. S (n)))
27

---

with G; ~ (eeom(1/)). By Lemma E.2 we have that
Pr Σ G.sn
e (n?))
2 exp
no (=no
(-
4re²
4
Since we seek an algorithm that makes the error at most & with least constant probability, we must have that = (2nnn/////e/ / initially claimed.
F Local Algorithms via Mixing Time Testing
In this section we expand upon our previous discussion on using property testing for hitting time estimation.
F1 Choosing cutoff using local mixing times
For simplicity, we focus on the calculation of effective resistances. Recall the following definition: Definition F.1 (Effective Resistance). The effective resistance between vertices t V is:
Rc(s,t) X Xe.t.
(11)
where the Laplacian is defined as L = A, with D being the degree diagonal matrix and A being the udjacency matrix.
Yoshida and Peng [Peng et al., 2021] show that the effective resistance can be written as a series with light tail.
Lemma F.1 ([Peng et al., 2021)). It holds that:
20
Ro(s,t) = Xst Σ P'D-1 Xst
(12)
At this point, we depart from the exposition of [Peng et al., 2021] and bound the tail of this series by using a different quantity: the E-(8, -mixinn time, which we define as follows:
Definition F22 Let s,t V and O. Then the E-(s,t)- t)-mming time is defined as the minimum number of steps required so that random walks starting from 8 and t have roughly the same distribution the states:
(() (s, (): == min{i E N | - 1, Se}
(13)
We prove that the c-(8, m)-mixing time can be used the cutoff point instead of À for irreducible and aperiodic Markov Chains.
Lemma F.2. Assume that our Markov chain is ergodic with convergence parameters (a, C). Let
log
[e/4)
5'(Ia))
=
min
log a
Then it holds that:
Ro(s, EXTP'D-
Xat
(14)
Proof. If we truncate the series at Equation 12 after index E, the error sustain is at most:
X TP'
Xat
IXTP
X
i=!
Suppose E' =//4. Now, we have by Hölder's inequality that:
1T, D''
P ||D Xoolloo
28

---

( 1
$|1,P* 1,P'l11
minnvy deg(v)
m (v)(v)
Se'
for 2 (s, t). We further claim that this term decreases an exponential rate for ergodic Markov Chains.
Claim F.1. It holds that f(i) = Pi Xsrl = (O"((())eeeee for some constant 0 < a 1.
Proof. We have that:
f(i) = : Jzel | - 2P + Pit
Let O(a²). Since our Markov Chain is ergodic, Theorem A.I gives that for any E V we have Paw (P'lu) I Tw 71 and Ps 2 nw 1/, So:
f(i) - Ta + Tu Tu + 2n + n. + 4n O(a')
With Claim F.1 in place, we can bound the error term as follows:
00
8
se Ca
Σ
EXP''' Xst < +
1-a
log( 20
Setting f
bounds the error by 2='
log
Remark F.1. In general, this approach suffers from the same "locality" issue as the original algorithm of [Peng al., 2021] which requires knowing X. In fact, the rafe is closely connected to À and they are both connected to the overall mixing time of the Markov chain via Cheeger's inequality. Even with good estimate of min a very close to if we do not know a itself. which, like X, is a global property. Therefore, for the remainder of this section we shall assume that (tmmin ), ignoring such degenerate cases.
unable bound the error in really degenerate cases where
F.2 Guessing (c) by property testing
Following Lemma F.2, we are finally ready design a new algorithm for estimating Ro(s, t), one that does not require knowledge of X. The idea is to provide an upper bound for ((e) (s, by using property tester. The algorithm of [Batu et al., 2013) can be used decide whether Markov chain close to mixing not. The notion of "almost-mixing" used by that algorithm relates to our localized mixing:
Definition F.3. A Markov Chain is (e, t)-mxing if there exists some distribution such that for all E V we have:
1' s|11 S
This kind of mixing implies s-(s, f) f)-mixing;
Lemma F.3. If a Markov chain is (s, t)-mixing, then for any states u E V we have (22) (s, S
Proof. Suppose g is the distribution that referenced by the (e, -mmxiin definition. By the triangle inequality:
11 - 1,, < ||,Pt* -qlli + || all1 S 2e
As result, if we can find some i such that our Markov Chain is (s/2, m)mmxing, we would have an upper bound to min. We can do this via binary search, assuming that we possess an oracle for deciding approximate mixing. The problem of deciding whether a Markov Chain is (e, ()-mixing can be reduced the problem of testing whether two distributions are close to each other in -idisttacce The algorithm provided by [Batu et al., 2013] provides the following guarantee:
29

---

Theorem F.1 (Mixing Test [Batu et al., 2013]). Let M be Markov chain. Suppose we are given tester for closeness of distributions & norm with time complexity E(n,E,5) and distance gap [(e) that takes input sample oracles to distributions p. q E <[(m)) and oulputs, with probability at least 6:
"accepi" if 4|l1 S f(e)
"reject" ilp 4ll1
Then there exists tester Tmixing with time complexity O(nt T(n,,,8/m)) such that:
If is (f(e)/2, (((e)/2,t)mmittee -)mmxing,, then Pr(M is accepted] > 1 - 6,
If is not (e, -mixing then Pr[M is accepted) 8.
We can use the ( closeness tester of [Chan et al., 2014] as the tester T. As shown in [Chan et al., 2014], this is optimal sample complexity for any tester.
Theorem F2 (Closeness test [Chan et al., 2014]). There exists a tester that runs in ( fn 2/3g -4/3 1//3.///222 time that, with probability at least 2/3, distinguishes between
and 1pp 41l 2
Since (e) 0, combining Theorem F.1 and Theorem F.2, along with a repetitive boosting argument gives us an algorithm Tiixing that runs in Ot n g/ log (1/8) time and can, with probability at least 1 - 5 distinguish whether a markov chain is (e, m)-ixi not.
Putting everything together, we consider binary searching for such that M is (e, ()-mixing. We know that 1 S 1 S D, where is the diameter of the graph. Using Tmixing with a boosted success probability of (D)( we conclude the following theorem:
Theorem F.3. There exists a (local) algorithm that determines the smallest such that Markov Chain M with n states is (E, miiiiing The algorithm runs in O ( (lo((10)) time, where D is the diameter of the graph.
As a consequence, this algorithm gives an upper bound to (E) and can therefore be used in the context of Lemma F.2 to approximate the effective resistance without knowledge of spectral gap
G Additional Experimental Results
In this section we deposit additional experimental results and information pertaining to our algorithms.
G.1 Synthetic Experiments Setup Details
Table 2 contains information about the networks we used for our synthetic experiments in the main body of the paper.
Table 2: Synthetic Networks
Name
7
771
Bidoos-Reyyl p = 0.01
000
5 007.4 + 32.0
Barabasi-Alle Albertt---Abrttttta 10
1 000
9 900
Communities Pinter = 0.01, Pintra = 0.05
1 000
9 021.4
+ 51.8
Football
115
613
Facebook
4 039
88 234
G.2 Benefits from parallelism
Our algorithms are highly parallelizable because their local nature lends itself to multi-threaded computation. Through parallelization we obtain even better performance in computing the hitting time compared the exact solver, as shown in Table 3. Here, we compute hitting times on the Facebook network using 10000 random walks.
30

---

Table 3: Speedup through parallelism. We show the running time in seconds.
Algorithm / Number of cores
5
10
20
Meeting Time Algorithm
0.554 + 0.071
0.377 + 0.065
0.335 + 0.026
0.359 + 0.018
Exact Algorithm
2.165 + 1.270
3.556 + 2.047
1.255 = 0.026
1.238 + 0.024
G.3 Ablation studies
We present additional ablation studies evaluating runtime and relative estimation error as functions of the number of random walks, using the Football and Facebook networks. We also perform the same experiment for our synthetic datasets. In the Football network, our cutoff algorithm under-performs the others, likely due to an overestimated À highhggt- its sensitivity hyperparameter tuning. In contrast, Algorithm appears more robust. We also visualize the correlation between hitting times and two pair sampling measures, illustrating how our method differs from simpler uniform sampling.
i' Algsttee
Aigrthin
Aluakke
04-
100
2.0
400
3.5
091
1000
201
D40
Mottng Alpester
Sanal Aggittin
1011
Cast Alpith
Bornctew
Mastin Algrttin
Fear Nop (Spas))
Sampl Aggeton
Caull Aquztii
- Essc Aggitios (puasa
Nao sombiu
Figure 4: Ablation study for the number of random walks in the Football and Facebook networks.
Eust Agpilias
Algar
34
15%4
of
3V'
Aggio cadss
deptst degit
33"
Algurtho
15-
16:
33
inpoekkast (mpsaddr)
Figure 5: Correlation between the hitting time and the degree product deg(u) dog(v) (top) and the product of pagerank centralities pagerank(u) pagerank(v) (bottom) on the Football (left) and Facebook (right) networks.
31

---

6.2
0.23
133
6.10
Ersc Agmn
Appelivs
6.15
0.30
Canaf
Aggittin
Doct Alpnttre
0083
6,5
Nidee
0023
610
-015
Vieit ig Tris Agpridin lig Arpe Alpelhls
Marting Thms Alpoitiir
Mizin Tii Ageili Alpethess
ng Alpnitis Aguakk Algertire
Alpontbrr
Aigettirs
2.0
9.0 Number rinden mil
13.
8.0
2003
250
Summber random
Number rance vala
17"
Nawherd
Hipellos
Aggithin
Caulf Aguille
Nax
Figure 6: Ablation study for the number of random walks in synthetic datasets.
30--
Meatin Agettv
Cacal Ain Sumoting Algontie
1500
Goall Agusi
Masting Algritin
1233
Sampl Aggnntir
8003
17
280
12.0 1404
H02F (4107)
Bl2ng timw 1-1
Figure 7: Absolute estimation error for uniformly sampled pairs on the Football (left) and Facebook (right) networks. The estimation errors are grouped by the hitting time.
32


Reviews:
[{"review_id": "86QVQQujcU", "reviewer": "Reviewer_BMmT", "summary": "This paper is on estimating the hitting time in an undirected graph. Classic algorithms that compute the hitting time run in O(n^3) time. This paper gives a random walk based algorithm that estimates the hitting time. The core idea is to use (what I would call) a \"bidirectional estimator\". To estimate the hitting time from u to v, one runs random walks from both u and v, look at the walks that \"collide\", and scale that to get an estimate. The difficult part is usually in bounding the concentration and proving that the estimate converges with a few samples.\n\nEssentially, when the mixing time is small (much smaller than the hitting time), then the bidirectional estimates converge rapidly. This can be shown using matrix Chernoff bounds.\n\nThe running time of this estimator is expressed in terms of the mixing time and the stationary distribution. In the worst case, the running time significantly worse than O(n^3). If the graph is an expander (mixing time = O(\\log n)), then the running time is better than the worst cast (though still worse than n^3?). If the degree distribution is skewed, then I think there is a significant advantage.\n\nThe result also gives empirical experiments showing that the algorithm works well in practice, which I think is nice.", "questions": "1. As said earlier: please give an explanation of when the algorithm is better than n^3, and the impact of skewed pi(v) values.\n2. There is a lot of literature on similar estimators used for PageRank, PersonalizedPageRank, and estimating the stationary distribution. I would recommend citing some of these papers, and the papers that they cite.\n - FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs, Peter Lofgren, Siddhartha Banerjee, Ashish Goel, and C. Seshadhri, KDD 2014.\n - Personalized PageRank Estimation and Search: A Bidirectional Approach. Peter Lofgren, Siddhartha Banerjee, Ashish Goel. WSDM 2016\n - Fast Bidirectional Probability Estimation in Markov Models. Siddhartha Banerjee, Peter Lofgren. NIPS 2015\n - Estimating Single-Node PageRank in O ̃ (min{dt,√m}) Time. Hanzhi Wang and Zhewei Wei, VLDB 2023\n - Efficient Algorithms for Personalized PageRank Computation: A Survey. Mingji Yang, Hanzhi Wang, Zhewei Wei, Sibo Wang, and Ji-Rong Wen. TKDE 2024\n - Revisiting Local PageRank Estimation on Undirected Graphs: Simple and Optimal. Hanzhi Wang. KDD 2024", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Getting local/sublinear graph algorithms is a fantastic topic and needs more focus. I think the hitting time is an excellent testbed for such algorithm. The bidirectional estimator has shown much promise in theory and practice, and it's great to see more applications of this technique.\n\nThe major weakness is a lack of an explanation of when this algorithm works. Theorem 3.1 and Corollary 3.1 should be accompanied with worst-case running times (in terms of n), an explanation of the rapidly mixing case, and possible of the skewed degree distribution case (so that \\pi(v) can be much larger than 1/n). I believe that the latter is the reason why the algorithm works well in practice.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback.\n* We agree that a more detailed discussion of worst-case running times for our algorithms under various parameter regimes would improve the exposition. In Theorem 3.1, the mixing time $t_{\\text{mix}}$ can reach $n^3$ in the worst case, while $\\pi(v) \\geq 1/n^2$ and $|\\pi_G|_2 \\geq \\sqrt{1 / n}$. However, these worst-case bounds are not independent of each other, making a direct maximization of the expression nontrivial. For this reason, we chose to express the running time in terms of the mixing time and stationary distribution parameters. We also considered upper bounding the mixing time using the conductance $\\Phi$ [1] and the maximum degree $\\Delta$. We will include a discussion of these points in our revision.\n* We agree that graphs with skewed degree distributions are an important regime to study, often allowing our algorithms to perform much more efficiently compared to the worst case. Obtaining tight bounds for such graphs is a promising direction for future work.\n* Finally, we appreciate the reviewer’s suggestions regarding related literature on Personalized PageRank. We agree that such related measures are a natural point of comparison for our algorithms, and we will incorporate a more thorough discussion of this connection in our revision.\n\n[1] Lovász, László, and Ravi Kannan. \"Faster mixing via average conductance.\" Proceedings of the thirty-first annual ACM symposium on Theory of computing. 1999."}, {"review_id": "Pn7uwIcNk0", "reviewer": "Reviewer_fb21", "summary": "This paper introduces local algorithms for estimating the hitting time $H_G(u,v)$ between two vertices.  The central idea is simple: consider the meeting time of two independent random walks originating at different vertices, $u$ and $v$.  Because the infinite series that defines a hitting time collapses once the walks intersect, the resulting estimator is unbiased, comes with explicit additive‑error guarantees, and provably uses nearly the minimum possible number of samples.\n\nBeyond this meeting‑time approach, the authors adapt the spectral‑cutoff method of Peng et al. to the asymmetric case.  They provide matching lower bounds that justify why straightforward walk sampling cannot achieve the same accuracy, and they reinterpret hitting‑time estimation as a property testing problem, swapping global mixing‑time parameters for quantities that can be measured locally.", "questions": "Please refer to the weakness section", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe results are backed up with strong theory: Provides additive‑error guarantees, a near‑optimal lower bound, an asymmetric spectral‑cutoff analysis, and a reduction to a property testing problem.\n\nWeakness:\n\n1) It would strengthen the paper to include experiments on graphs of at least 100k nodes (and ideally larger) to demonstrate scalability.\n\n2) Adding empirical comparisons against common heuristics, such as personalized or approximate PageRank, would help illustrate the method’s practical relevance.", "was_revised": true, "final_justification": "The paper presents a thorough theoretical examination of various aspects of the proposed algorithm, supported by a practical proof of concept. The exploration of local or sublinear graph algorithms is an exciting and valuable research direction that merits greater attention. Having read the rebuttal, I have decided to maintain my score.", "rebuttal": "We thank the reviewer for their time and thoughtful comments.\n* We agree that experiments on even larger graphs would help further demonstrate the scalability of our approach. As per the reviewer’s suggestion, we will include experiments on even larger graphs in our revision. We expect the results to mimic the trend of our current experimental setup.\n* We also appreciate the reviewer’s suggestion that our work’s practical relevance could be better contextualized through comparison with approaches for related measures such as Personalized PageRank (PPR) [1]. We will add a discussion of this point in the revised version. This is a very promising direction for future work as well!\n\nWe thank the reviewer again for raising these important points. In an extended version of the paper, we plan to include experiments on larger datasets and explore using PPR as a proxy baseline for our algorithms.\n\n[1] Chung, Fan, and Olivia Simpson. \"Computing heat kernel pagerank and a local clustering algorithm.\" European Journal of Combinatorics 68 (2018): 96-119."}, {"review_id": "sasb5H4c8P", "reviewer": "Reviewer_Sw5f", "summary": "The work studies graphs as markov chains and formulate several methods to estimate hitting times using local state management of the graph random walks. Assuming steady state achievable markov chains on these graphs, they first relate chain mixing times to expected meeting times between 2 nodes/states on the graph. This helps them device parameters to decide on the estimated duration until which they run their algorithm (algorithm 1) and estimate hitting times based on several random walks they initiated from both the source and the target nodes. They also extend existing results on hitting times based on spectral values and tweak it into a local algorithm that runs on estimated local mixing time approximations. For all of these methods, authors provide algorithms, probabilistic error bounds, sample complexity bounds and run-time complexities. The focus was largely on the accuracy of the algorithm in achieving the true value in using fewer instances of random walks initiated by their algorithms. This was then backed by experiments on graphs where ground truth values of hitting times could be calculated.", "questions": "1. Algorithm 1 line 8, definition of $y_w$ should use $Y$ family of random walks to make sense.\n2. Algorithm 1 line 14 should be some another variable, maybe $I$ or $J$ instead of $\\chi$, right?\n3. Moving from last expression in line 117 to 118 first expression, how did the $\\pi_G(v)$ transform to $\\pi_G(u)$?", "limitations": "1. Extensions like algorithm 3 also face prohibitively large values of $r$, random walks with growth factors $\\frac{m^2}{\\epsilon^2}$. This is a crucial issue especially when one of the core assumptions is that the graph is connected and likely cannot be sparse!\n2. While identified by authors themselves in their diligent analysis, expecting $t_{\\text{mix}}$ as a one-shot input usually means running further sampling and approximation to estimate that first!", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strength: 1. Rigorous theoretical analysis of several aspects of the proposed algorithm along with practical proof of concept.\n2. At first glance step line 9 of Algorithm 1 looks prohibitively expensive, especially for large graphs, but the running time grows at most $\\log^3n$, which is very promising for practice!\n\nWeakness: 1. While they prove tight bounds on the samples required for the algorithms, $l$ that is the number of processes that they start random walk for, are practically large for large graphs. While authors mention that one of the core motivations was to avoid using global algorithms that prohibit working with large graphs, the design choice of $l$ (which comes with excellent guarantees as well), is proportional to squared total edges in the graph as well as inverse square of the accuracy error. While the local approach allows them to not store all these walks, even storing the current state of these many walks incurs huge memory as well, albeit the memory requirements decline as the algo does away with intersected random walks.", "was_revised": true, "final_justification": "The authors have addressed my concerns and subsequent clarification, actions from their side, and overall strengths and limitations of the paper has been discussed and agreed upon. As acknowledged before, I'll keep my score.", "rebuttal": "We thank the reviewer for their positive feedback and helpful comments.\n\nThe reviewer correctly noted that the pseudocode appears, at first glance, to loop over all nodes. While this presentation was chosen for simplicity, we agree that it is misleading in retrospect. The algorithm actually only iterates over a significantly smaller subset of nodes. We will revise the pseudocode and accompanying explanation to make this clear.\n\nRegarding the worst-case performance of our algorithms: we agree with the reviewer that the mixing time plays a central role in the time complexity and can indeed become a bottleneck in some regimes. Obtaining tight bounds for estimating hitting times remains an interesting open problem. Designing average-case algorithms for such problems is yet another such promising direction for future research.\n\nFinally, we will address the specific corrections the reviewer kindly pointed out:\n* In Algorithm 1, we will replace the incorrect terminating condition symbol $\\chi$ with $I$ or $J$, as suggested.\n* We will fix the typo on Line 8 of Algorithm 1.\n* In Lines 117–118, we will correct the expression to $\\pi(v)$.\n\nWe thank the reviewer again for their close reading and valuable suggestions."}, {"review_id": "Firop8pB93", "reviewer": "Reviewer_t7iu", "summary": "This paper considers the problem of estimating hitting times in a simple random walk on a graph. The paper puts forth three approaches. The first (Algorithm 1) estimates hitting times through meeting times. The second (Algorithm 3) is based on a truncation of a hitting time summation representation, given in Lemma 4.1. The third approach simply samples long random walks and returns the average hitting time. Experiments on real and synthetic data are included.", "questions": "I did not follow the failure probability bound at the bottom of page 3. There is an intersection over \\sigma, but in the text above, \\sigma is defined to be a particular permutation. \n\nPlease address the point about Line 126.\n\nWhy does the Hoeffding bound apply in the line below 128? You are essentially conditioning on some events involving the A_i, B_i random variables, so you don’t have independence.", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "This paper provides two new approaches for hitting times estimation, given in Algorithms 1 and 3. There were some issues with clarity. In particular, I felt that Lemma 4.1 should be moved earlier, so that Lemma 3.3. would not need a forward reference. \n\nMy biggest confusion is in Lemma 3.4. Why is there a single meeting time T? I thought there were multiple meeting times? As a result I am not understanding the definitions of A_i and B_i, and therefore I am not seeing how the display below Line 126 is the output of Algorithm 1. Furthermore, the stopping condition of Algorithm 1 refers to $\\chi$, but I don’t see $\\chi$ defined.\n\nAlso, Lemma 3.3 refers to W, but W is not defined until Lemma 4.1.\n\nThere were a few cases where notation was not defined: \n- Line 84: $\\chi_{uv}$\n- The set $\\chi$ is not defined in Algorithm 1, so I cannot interpret the failure condition.", "was_revised": true, "final_justification": "The authors addressed my concerns, so I raised my score.", "rebuttal": "We thank the reviewer for their thorough comments and positive feedback on the quality and significance of our work. Below, we address the main concerns raised, which primarily relate to clarity. We believe these issues can be effectively resolved in a revision and appreciate the reviewer’s helpful suggestions for improvement.\n\n**On Lemma 3.4** : \n* *“Why is there a single meeting time T?”*: In the definition of $A_i$ and $B_i$, we assume that the $i$-th random walk from $u$ meets and eliminates the $i$-th walk from $v$, which is without loss of generality since the walk label indices are arbitrarily chosen. We will denote the meeting time of each pair as $T_i$ to make clear that it is specific to each matched pair. The variables $A_i$ and $B_i$ count how many times the respective walks hit state $v$ before meeting. Line 126 in Algorithm 1 reflects this by incrementing or decrementing the hitting time estimate based on which walk visits $v$. We will update our write-up to make this important point clearer.\n* *“Why does the Hoeffding bound apply in the line below 128?”*: One of the ideas in our analysis is that the overall estimate can be written as a sum over $A_i - B_i$. As Lemma 3.4 conditions on successful meeting (i.e., within $t_{\\max}$ steps), the random variables $|A_i - B_i|$ are bounded by $t_{\\max}$ with (conditional) probability $1$. Combined with the fact that $|A_i - B_i|$ for all $i$ are independent, this justifies our application of Hoeffding’s inequality. We will make this clearer in the revision.\n\n**On Lemma 3.2 and the definition of $\\sigma$**: The confusion likely stems from the wording. We take a conjunction over all possible permutations, and denote one such permutation by $\\sigma$. We will clarify this in the proof to avoid ambiguity.\n\n**Other typos and clarifications:**\n* We will fix the typo in the stopping condition of Algorithm 1, replacing $\\mathcal{X}$ with either $I$ or $J$, as appropriate.\n* We will move Lemma 4.1 between Lemmas 3.2 and 3.3 to avoid the forward reference and ensure that $W$ is properly defined.\n* Additional minor typos noted by the reviewer will also be addressed.\n\nWe appreciate the reviewer’s close reading and helpful suggestions, which have improved the clarity and correctness of our presentation."}]

Author rebuttal:

Meta-review: One of the key quantities that can be attached to a random walk over a graph $G$ is the (expected) hitting time of a vertex $v$ when the random walk starts from vertex $u$. This paper provides a "local" method to compute such quantities. To be more specific: by performing lots of independent random walks on the graph, and keeping track of which pairs of random walks have met (and occasionally "killing" some of the random walks), one gets a good additive estimate of the hitting time. The main results still allow for a large time complexity -- i.e. a large total number of RW steps -- but two points must be added here. One is that, on skewed degree distributions, the theoretical bounds actually perform better. The other is about space complexity: the fact that the method is "local" means that one never needs to load the full graph into memory. The paper also contains a number of relatively small-scale experiments (restricted to graphs with 10^4 nodes) that suggest its method (or rather, methods) perform well. 

The strengths of the paper are numerous. As noted above, there are clear advantages to using "local" algorithms. The present paper builds on related mathematical works on random walks to obtain interesting applicable methods. This theoretical analysis is interesting, although "wasteful" in that it is very unlikely that e.g. A_i-B_i ever reaches t_{\max} (to mention one very technical point). In fact, I think that much of the success in the experiments can be credited to this feature. The notion of "local mixing time" introduced in the analysis of the second method would be an interesting object for further study. 

As for weaknesses, some typos and slightly imprecise steps in the analysis were identified (see comments by Sw5f and t7iU). It seems to me that all of these can be easily fixed. In the present form, the paper also lacks more large scale experiments (one reviewer suggested graphs with 10^5 nodes). The authors have also suggested that they will add such experiments, but it remains to be seen what there will look like. Another weakness is that its theme is not quite central to NeurIPS. About this, however, I would say that the paper is at the very least related to the analysis of large networks, which is an important direction in statistics and ML. Therefore, my evaluation is that these weaknesses are not serious. 

To sum up, I agree with the reviewers' positive assessment of this submission. As noted above, it makes interesting contributions in terms of theory, and the experimental evidence, while not quite conclusive (due to the small network sizes), looks promising. (The discussion was uneventful, which I see as a sign that the paper is well written!)
Decision: Accept (poster)