### Summary

Personalized PageRank is a standard tool for finding vertices in a graph that are most relevant to a query or user. To personalize PageRank, one adjusts node weights or edge weights that determine teleport probabilities and transition probabilities in a random surfer model. There are many fast methods to approximate PageRank when the node weights are personalized; however, personalization based on edge weights has been an open problem since the dawn of personalized PageRank over a decade ago. In this paper, we describe the first fast algorithm for computing PageRank on general graphs when the edge weights are personalized. Our method, which is based on model reduction, outperforms existing methods by nearly five orders of magnitude. This huge performance gain over previous work allows us — for the very first time — to solve learning-to-rank problems for edge weight personalization at interactive speeds, a goal that had not previously been achievable for this class of problems.

### Papers

*Proceedings of ACM KDD 2015*, 2015.

**Best student paper award.**

@inproceedings{2015-edgeppr, author = {Xie, Wenlei and Bindel, David and Demers, Alan and Gehrke, Johannes}, booktitle = {Proceedings of ACM KDD 2015}, title = {Edge-Weighted Personalized {PageRank}: Breaking A Decade-Old Performance Barrier}, month = aug, year = {2015}, doi = {10.1145/2783258.2783278}, notable = {Best student paper award.}, code = {https://github.com/wenleix/EdgePPR}, slides = {present/2015-08-kdd-talk_kdd-aug15.pdf}, talk = {https://www.youtube.com/watch?v=Cop9Arcw6wY} }

#### Abstract:

Personalized PageRank is a standard tool for finding vertices in a
graph that are most relevant to a query or user. To personalize
PageRank, one adjusts node weights or edge weights that determine
teleport probabilities and transition probabilities in a random surfer
model. There are many fast methods to approximate PageRank when the
node weights are personalized; however, personalization based on edge
weights has been an open problem since the dawn of personalized
PageRank over a decade ago. In this paper, we describe the first fast
algorithm for computing PageRank on general graphs when the edge
weights are personalized. Our method, which is based on model
reduction, outperforms existing methods by nearly *five orders of
magnitude*. This huge performance gain over previous work allows us —
for the very first time — to solve learning-to-rank problems for edge
weight personalization *at interactive speeds*, a goal that had not
previously been achievable for this class of problems.

### Talks

#### Model Reduction for Edge-Weighted Personalized PageRank

Purdue Computational and Applied Mathematics Seminar

pagerank
•
seminar external invited

#### Model Reduction for Edge-Weighted Personalized PageRank

Hong Kong Baptist University

pagerank
•
seminar external invited

#### Model Reduction for Edge-Weighted Personalized PageRank

Stanford LA/Opt Seminar

pagerank
•
seminar external invited

#### Model Reduction for Edge-Weighted Personalized PageRank

Berkeley Matrix Computations Seminar

pagerank
•
seminar external invited

#### Edge-Weighted Personalized PageRank: Breaking a Decade-Old Performance Barrier

KDD 2015

pagerank
•
meeting external

#### Edge-Weighted Personalized PageRank: Breaking a Decade-Old Performance Barrier

KDD 2015 (poster session)

pagerank
•
meeting external poster

#### Model Reduction for Edge-Weighted Personalized Page Rank

Cornell SCAN Seminar

pagerank
•
seminar local