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

W. Xie, D. Bindel, A. Demers, and J. Gehrke, “Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier,” in 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
pagerankseminar external invited

Model Reduction for Edge-Weighted Personalized PageRank

Hong Kong Baptist University
pagerankseminar external invited

Model Reduction for Edge-Weighted Personalized PageRank

Stanford LA/Opt Seminar
pagerankseminar external invited

Model Reduction for Edge-Weighted Personalized PageRank

Berkeley Matrix Computations Seminar
pagerankseminar external invited

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

KDD 2015 (poster session)
pagerankmeeting external poster

Model Reduction for Edge-Weighted Personalized Page Rank

Cornell SCAN Seminar
pagerankseminar local