We propose and analyze two algorithms for maintaining approximate
Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added
or deleted. Our algorithms are natural dynamic versions of two known local
variations of power iteration. One, Forward Push, propagates probability mass
forwards along edges from a source node, while the other, Reverse Push,
propagates local changes backwards along edges from a target. In both
variations, we maintain an invariant between two vectors, and when an edge is
updated, our algorithm first modifies the vectors to restore the invariant,
then performs any needed local push operations to restore accuracy.
For Reverse Push, we prove that for an arbitrary directed graph in a random
edge model, or for an arbitrary undirected graph, given a uniformly random
target node $t$, the cost to maintain a PPR vector to $t$ of additive error
$\varepsilon$ as $k$ edges are updated is $O(k + \bar{d} / \varepsilon)$, where
$\bar{d}$ is the average degree of the graph. This is $O(1)$ work per update,
plus the cost of computing a reverse vector once on a static graph. For Forward
Push, we show that on an arbitrary undirected graph, given a uniformly random
start node $s$, the cost to maintain a PPR vector from $s$ of degree-normalized
error $\varepsilon$ as $k$ edges are updated is $O(k + 1 / \varepsilon)$, which
is again $O(1)$ per update plus the cost of computing a PPR vector once on a
static graph.

本文提出并研究了两种算法，用于在动态图上维护近似频繁访问节点的 PPR 向量。其中，两种变体 Forward Push 和 Reverse Push 算法，能通过图的加边和删除边的动态维护算法在保证相似性的情况下进行向前和向后推送，减少计算代价。