Learn Before
Concept

Personalized PageRank (Jeh and Widom, 2003)

Personalized PageRank (PPR) is the seed-specific generalization of PageRank introduced by Jeh and Widom (WWW 2003). The random surfer follows an outgoing edge with probability 1α1-\alpha and teleports with probability α\alpha, but the teleport distribution is replaced by a user-specified preference vector r\mathbf{r} over the nodes, so the resulting stationary score πr\boldsymbol{\pi}_{\mathbf{r}} concentrates near the seeds in r\mathbf{r} rather than spreading uniformly across the graph. Formally, πr\boldsymbol{\pi}_{\mathbf{r}} is the unique solution of πr=(1α)Pπr+αr,\boldsymbol{\pi}_{\mathbf{r}} = (1-\alpha)\, P^{\top} \boldsymbol{\pi}_{\mathbf{r}} + \alpha\, \mathbf{r}, where PP is the row-stochastic transition matrix of the graph. The paper also introduces a hub decomposition and dynamic-programming scheme that lets many such personalized vectors be computed at web scale by combining a small set of precomputed partial vectors with a basis of hub vectors. A truncated variant restricts the computation to the highest-weight entries (or bounds the iteration depth), trading recall for compute and yielding the truncated personalized PageRank commonly used as a graph-retrieval baseline.

0

1

Updated 2026-05-18

Contributors are:

Who are from:

Tags

Science

Auditable Strict-Parity Evaluation of Prerequisite-Graph Retrieval for RAG under Leakage Controls