Research map / Learning theory and algorithms / Sample complexity
Estimating Hitting Times Locally at Scale
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives local algorithms for estimating hitting times between two vertices (meeting-time estimator and a spectral-cutoff variant), with sample-complexity lower bounds and experiments on synthetic and SNAP graphs.
Problem
Computing hitting times between two vertices in a graph exactly or approximately requires global access to the graph, which is infeasible for massive networks.
Approach
Truncate the hitting-time series at the meeting time of two independent random walks from u and v, so only local random-walk samples are needed; also adapt spectral cutoff from effective-resistance work to handle asymmetric hitting times.
Key results
- Meeting-time algorithm achieves mean relative error around 0.002-0.013 on Football, Facebook, and Twitter graphs across pair-sampling strategies.
- Cutoff algorithm has relative error near 1.0 on Football (e.g., 1.061 for deg-product proportional sampling), far worse than meeting-time and sampling methods.
- Theory gives a lower bound of Omega(t_mix^2/(pi(v)^2 eps^2)) samples for walk-sampling estimators on barbell-like graphs, matching the walk sampling upper bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the meeting-time estimator instead of walk sampling | Hitting-time estimation · Football, uniform pair sampling | relative estimation error: 0.025 \pm 0.019 -> 0.012 \pm 0.009 | Helped |
| Use the meeting-time estimator instead of walk sampling | Hitting-time estimation · Facebook, uniform pair sampling | relative estimation error: 0.027 \pm 0.021 -> 0.012 \pm 0.011 | Helped |
| Use the meeting-time estimator instead of walk sampling | Hitting-time estimation · Twitter, uniform pair sampling | relative estimation error: 0.024 \pm 0.018 -> 0.005 \pm 0.004 | Helped |
| Use the meeting-time estimator instead of the spectral cutoff estimator | Hitting-time estimation · Football, uniform pair sampling | relative estimation error: 0.994 \pm 0.778 -> 0.012 \pm 0.009 | Helped |
| Use the meeting-time estimator instead of the spectral cutoff estimator | Hitting-time estimation · Facebook, uniform pair sampling | relative estimation error: 0.147 \pm 0.156 -> 0.012 \pm 0.011 | Helped |
| Use the meeting-time estimator instead of the spectral cutoff estimator | Hitting-time estimation · Twitter, uniform pair sampling | relative estimation error: 0.086 \pm 0.066 -> 0.005 \pm 0.004 | Helped |
| Use the meeting-time estimator instead of walk sampling | Hitting-time estimation · Synthetic Erdős-Rényi, Barabási-Albert, and SBM graphs | relative error | Helped |
Surprising findings
- The spectral cutoff algorithm performs much worse than the walk-sampling baseline on the Football and Facebook graphs, despite its theoretical guarantees.
Limitations
- Accuracy and efficiency depend on mixing time; large mixing time makes the local algorithms less efficient.
- The spectral cutoff variant is generally less efficient and needs the spectral gap, which requires global graph information.
- Lower bounds are shown only in the worst case over graphs (barbell-like constructions).
Experimental setup
Datasets: American Football (IA games) graph SNAP Facebook graph SNAP Twitter graph Erdos-Renyi synthetic graphs Barabasi-Albert synthetic graphs Stochastic Block Model synthetic graphs
Benchmarks: American Football SNAP Facebook SNAP Twitter synthetic ER/BA/SBM graphs
Metrics: relative error mean absolute error mean squared error running time number of sample walks
Baselines: Cutoff Alg. Sampling Alg. exact linear system solver
Builds on: effective resistance local algorithm (Andoni et al.) Laplacian identity for hitting time Markov chain Chernoff bound (Chung et al.)
Closest papers by meaning
- A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering (ICML 2024 · similarity 0.84)
- Beyond Self-Repellent Kernels: History-Driven Target Towards Efficient Nonlinear MCMC on General Graphs (ICML 2025 · similarity 0.83)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.82)
- Approximating Optimal Labelings for Temporal Connectivity (AAAI 2025 · similarity 0.82)
- Repelling Random Walks (ICLR 2024 · similarity 0.82)
- Fast Wasserstein rates for estimating probability distributions of probabilistic graphical models (NeurIPS 2026 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.