# Approximate Personalized PageRank on Dynamic Graphs

arXiv: https://arxiv.org/abs/1603.07796 · HTML: https://mlsanity.com/paper/1603.07796/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Mar 2016.

## Built on by (most cited first, 11 of 11)

- [DPPIN: A Biological Repository of Dynamic Protein-Protein Interaction Network Data](https://mlsanity.com/paper/2107.02168/) (2021)
- [Instant Graph Neural Networks for Dynamic Graphs](https://mlsanity.com/paper/2206.01379/) (2022)
- [Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier](https://mlsanity.com/paper/2408.09212/) (2024)
- [Fast Online Node Labeling for Very Large Graphs](https://mlsanity.com/paper/2305.16257/) (2023)
- [Faster Local Solvers for Graph Diffusion Equations](https://mlsanity.com/paper/2410.21634/) (2024)
- [Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata](https://mlsanity.com/paper/2212.06898/) (2022)
- [Accelerating Dynamic Network Embedding with Billions of Parameter Updates to Milliseconds](https://mlsanity.com/paper/2306.08967/) (2023)
- [Fast and Robust Contextual Node Representation Learning over Dynamic Graphs](https://mlsanity.com/paper/2411.07123/) (2024)
- [Efficiently Learning Branching Networks for Multitask Algorithmic Reasoning](https://mlsanity.com/paper/2512.01113/) (2025)
- [Analyzing the Evolution of Graphs and Texts](https://mlsanity.com/paper/2411.06295/) (2024)
- [Coden: Efficient Temporal Graph Neural Networks for Continuous Prediction](https://mlsanity.com/paper/2602.12613/) (2026)

## Abstract (arXiv)

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 + bard / varepsilon), where bard 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.