跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2504.16481 · v5

Estimating Random-Walk Probabilities in Directed Graphs

首次提交 2025-04-23 15:47
版本更新 2026-11-17 02:39
雷达观测 2026-11-17 16:10
arXiv ↗PDF ↗

摘要

We study discounted random walks in directed graphs. In each step, the walk either terminates with a constant probability αα, or proceeds to a random out-neighbor. Our goal is to estimate the probability π(s,t)π(s, t) that a discounted random walk starting from ss terminates at tt. This probability is also known as the Personalized PageRank (PPR) score, which measures the relevance of tt to ss, for instance, when ss and tt are web pages on the Internet. We aim to estimate π(s,t)π(s, t) within a constant relative error with constant probability. A variety of algorithms have been developed for several problem variants, such as single-pair, single-source, single-target, and single-node estimation, under both worst-case and average-case settings, and for different combinations of allowed graph queries. However, in many important cases, there remain polynomial gaps between known upper and lower bounds. In this paper, we establish tight bounds for all problem variants and query combinations, closing all existing gaps in both the worst-case and average-case settings. We provide tight (up to logarithmic factors) lower bounds, showing that for all but one query combination, existing algorithms are already optimal. For the remaining case, we design a novel algorithm that matches our new lower bound up to logarithmic factors, thereby nearly achieving optimality. This is the first algorithm to exploit this specific query combination. It uses a new randomized bidirectional framework that combines randomized backward propagation with selective Monte Carlo estimation.

作者备注:35 pages, 12 figures

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v5,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v5 · 2026-11-17 02:39 · 最新观测版本

Estimating Random-Walk Probabilities in Directed Graphs

We study discounted random walks in directed graphs. In each step, the walk either terminates with a constant probability αα, or proceeds to a random out-neighbor. Our goal is to estimate the probability π(s,t)π(s, t) that a discounted random walk starting from ss terminates at tt. This probability is also known as the Personalized PageRank (PPR) score, which measures the relevance of tt to ss, for instance, when ss and tt are web pages on the Internet. We aim to estimate π(s,t)π(s, t) within a constant relative error with constant probability. A variety of algorithms have been developed for several problem variants, such as single-pair, single-source, single-target, and single-node estimation, under both worst-case and average-case settings, and for different combinations of allowed graph queries. However, in many important cases, there remain polynomial gaps between known upper and lower bounds. In this paper, we establish tight bounds for all problem variants and query combinations, closing all existing gaps in both the worst-case and average-case settings. We provide tight (up to logarithmic factors) lower bounds, showing that for all but one query combination, existing algorithms are already optimal. For the remaining case, we design a novel algorithm that matches our new lower bound up to logarithmic factors, thereby nearly achieving optimality. This is the first algorithm to exploit this specific query combination. It uses a new randomized bidirectional framework that combines randomized backward propagation with selective Monte Carlo estimation.

查看此版本解读 →查看此版本原文 ↗