Edge-Weighted Personalized PageRank Algorithm

An Edge-Weighted Personalized PageRank Algorithm is a Personalized PageRank Algorithm in which the edge weights are personalized.

• Context:
  • It was first developed and implemented by Xie et al. (2015).
  • …
• Example(s):
  • …
• Counter-Example(s):
  • PPRGo Algorithm,
  • Node-Weighted Personalized PageRank Algorithm,
  • Personalized Pagerank with Accuracy Assurance Algorithm.
• See: Random Walk Process, Random Graph Walk, PageRank Algorithm, PageRank Value, Random Walk NLP Algorithm, Random Walk Image Processing Algorithm.

---

---

References

2015

• (Xie et al., 2015) ⇒ Wenlei Xie, David Bindel, Alan Demers, and Johannes Gehrke. (2015). "Edge-Weighted Personalized PageRank: Breaking A Decade-Old Performance Barrier". In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783278.
  • QUOTE: 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.

    (...)

    Through these edge and node weights, PageRank can be personalized to particular users or queries. Concretely, in node-weighted personalized PageRank, we solve

    $Mx(w)=(1-\alpha)v(w),\quad w\in \R^d$

    where $w$ is a vector of personalization parameters. In edge-weighted personalized PageRank, we solve

    $M(w)x(w)=(1-\alpha)v,\quad w\in \R^d$

    For example, the personalization vector can specify the topic preference for the query, so the random walker will teleport to nodes associated with preferred topics (node-weighted personalized PageRank) or move through edges associated with preferred topics more frequently (edge-weighted personalized PageRank).

---