Estimating Hitting Times Locally At Scale¶

会议: NeurIPS 2025
arXiv: 2511.04343
代码: https://github.com/tkhar/hitting-time-at-scale
领域: 图算法 / 随机游走
关键词: 命中时间, 局部算法, 随机游走, 亚线性复杂度, 谱方法

一句话总结¶

提出两种局部（亚线性）算法估计图上的命中时间——基于相遇时间的 Algorithm 1 和基于谱截断的 Algorithm 3，无需全图访问仅通过以 \(u,v\) 为中心的短随机游走完成估计，在合成和真实图上相对误差 <1.4%，并证明了游走采样的最优样本复杂度下界。

领域现状：命中时间 \(H_G(u,v)\) 是随机游走从 \(u\) 到 \(v\) 的期望步数，广泛用于图聚类、链接预测和推荐系统。精确计算需要 \(O(n^3)\)（求解线性系统/矩阵求逆），大规模图不可行。
现有痛点：朴素的蒙特卡罗方法（模拟到达的随机游走）方差巨大且无理论保证；全局谱方法需要特征值分解 \(O(n^3)\)；没有方法能从局部子图高效估计命中时间。
核心矛盾：命中时间本质上是全局量（依赖图的全局结构），但大规模场景只能做局部计算。能否仅用以 \(u,v\) 为中心的短游走得到有保证的估计？
本文要解决什么？ 设计亚线性时间的局部算法估计命中时间，给出理论误差保证和最优性证明。
切入角度：关键洞察——命中时间可以通过两个独立随机游走（分别从 \(u\) 和 \(v\) 出发）的相遇时间来截断和估计。
核心 idea 一句话：从 \(u,v\) 各发出 \(\ell\) 条随机游走，利用相遇时间截断命中时间估计，避免全图遍历，运行时间仅依赖混合时间和平稳分布。

两种算法：Algorithm 1（主要）——从 \(u,v\) 各启动 \(\ell\) 条随机游走，步进推进，游走相遇时消除并累积命中时间估计。Algorithm 3（谱截断）——将命中时间展开为矩阵幂级数，截断到谱间隙决定的项数，每项用短随机游走估计。

相遇时间截断（Algorithm 1）:
做什么：利用两组游走的相遇事件截断无穷期望
核心思路：Lemma 3.4 证明 \(H_G(u,v) = E[\sum_{t<T}(\frac{1}{2}[Y_t=v] - \frac{1}{2}[X_t=v])]\)，其中 \(T\) 是从 \(u,v\) 出发的两个游走的相遇时间。初始化 \(\ell\) 对游走，逐步推进，相遇则消除该对并累积贡献 \(\tilde{H}_{uv} \leftarrow \tilde{H}_{uv} + (y_v - x_v)/(\ell \cdot \pi(v))\)
设计动机：在 Kronecker 积图 \(G \times G\) 上的 Markov 链 Chernoff 界保证集中性；相遇时间的集中性（Lemma 3.1）使截断误差可控
复杂度：\(O(t_{mix}^3 / (\|\pi\|_2^6 \cdot \pi^2(v) \cdot \varepsilon^2) \cdot \log^3(n/(\pi(u)\pi(v))))\)
谱截断算法（Algorithm 3）:
做什么：利用谱分解将命中时间表示为截断幂级数
核心思路：\(H_G(u,v) = \sum_{i=0}^{\infty} (\mathbb{1} - \frac{1}{\pi(v)}\mathbb{1}_v)^T W^i \chi_{uv}\)，找截断点 \(\ell\) 使尾部和 \(\leq \varepsilon/2\)（由谱间隙 \(\lambda\) 决定），每项用 \(r\) 条长度为 \(i\) 的随机游走估计
设计动机：理论上更清晰但实践中不如 Algorithm 1
最优性证明:
做什么：证明游走采样的样本复杂度下界
核心思路：Theorem 5.1-5.2 证明任何基于游走的局部算法需要 \(\Omega(t_{mix}^2 / (\pi^2(v) \varepsilon^2))\) 次游走，Algorithm 1 接近此下界
设计动机：确认算法是（近）最优的

无训练——纯算法
参数：\(t_{max} = 100 t_{mix} \ln(n/(\pi(u)\pi(v)))/\|\pi\|_2^2\)，\(\ell = 2t_{max}^2 \ln(n) / (\pi^2(v) \varepsilon^2)\)