Personalized PageRank (PPR) Algorithm

A Personalized PageRank (PPR) Algorithm is a PageRank Algorithm that is based on a random surfer algorithm.

• Context:
  • It can be implemented by a Personalized PageRank-based System.
  • …
• Example(s):
  • PPRGo Algorithm (Bojchevski et al., 2020),
  • Edge-Weighted Personalized PageRank Algorithm (Xie et al., 2015),
  • Personalized Pagerank with Accuracy Assurance Algorithm (Fujiwara et al., 2012),
  • …
• Counter-Example(s):
  • Random Walk with Restart on Multiplex Networks (RWR-M) Algorithm,
  • Random Walk with Restart on Multiplex-Heterogeneous Networks (RWR-MH) Algorithm,
  • Random-Walk-based NLP Algorithm,
  • Sequence Alignment Algorithm,
  • Simple Random Walk (SRW) Algorithm,
  • Self-Interacting Random Walk Algorithm.
• See: Random Walk Process, Random Graph Walk, PageRank Algorithm, PageRank Value, Random Walk NLP Algorithm, Random Walk Image Processing Algorithm.

---

---

References

2020

• (Bojchevski et al., 2020) ⇒ Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. (2020). “Scaling Graph Neural Networks with Approximate PageRank.” In: arXiv preprint arXiv:2007.01570.
  • QUOTE: ... Recent work shows that personalized PageRank (Jeh & Widom, 2003) can be used to directly incorporate multi-hop neighborhood information of a node without explicit message-passing [ 33 ]. Intuitively, propagation based on personalized PageRank corresponds to infinitely many neighborhood aggregation layers where the node influence decays exponentially with each layer. However, as proposed, Klicpera et al., 2019)’s approach does not easily scale to large graphs since it performs an expensive variant of power iteration during training.

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: 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.

    (...)

    In the PageRank model, a random walker moves through the nodes in a graph, at each step moving to a new node by transitioning along an edge (with probability $\alpha$) or by “teleporting” to a position independent of the previous location (with probability $\left(1 − \alpha\right)$).

2012

• (Fujiwara et al., 2012) ⇒ Yasuhiro Fujiwara, Makoto Nakatsuji, Takeshi Yamamuro, Hiroaki Shiokawa, and Makoto Onizuka. (2012). "Efficient Personalized Pagerank with Accuracy Assurance". In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339538
  • QUOTE: PPR is defined with respect to a “random surfer model” and needs to be computed iteratively. Informally speaking, PPR is the stationary distribution of random walks; at each step in a random walk, it randomly selects an outgoing edge from the current node, and, with a certain probability, it jumps to a node in accordance with a given preference distribution.

2010

• (Bahmani et al., 2010) ⇒ Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. (2010). “Fast Incremental and Personalized PageRank.” Proceedings of the VLDB Endowment 4, no. 3

2010

• (Lao et al., 2010) ⇒ Ni Lao, and William W. Cohen. (2010). “Relational Retrieval Using a Combination of Path-constrained Random Walks.” In: Machine Learning Journal, 81(1). doi:10.1007/s10994-010-5205-8
  • QUOTE: In general, the appropriate notion of “proximity” may be task- or user-specific, and hence must be learned or engineered; however, there are also general-purpose graph proximity measures such as random walk with restart (RWR) (also called personalized PageRank) which are fairly successful for many types of tasks.

2006

• (Tong et al., 2006) ⇒ Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. (2006). “Fast Random Walk with Restart and Its Applications.” In: Proceedings of the Sixth International Conference on Data Mining. ISBN:0-7695-2701-9 doi:10.1109/ICDM.2006.70
  • QUOTE: … random walk with restart (RWR) provides a good relevance score between two nodes in a weighted graph, and it has been successfully used in numerous settings, like automatic captioning of images, generalizations to the “connection subgraphs”, personalized PageRank, and many …

2004

• (Fogaras & Racz, 2004) ⇒ Daniel Fogaras, and Balazs Racz (2004). "Towards Scaling Fully Personalized PageRank". In: Proceedings of the International Workshop on Algorithms and Models for the Web-Graph Algorithms and Models for the Web-Graph (WAW 2004).
  • QUOTE: Personalized PageRank expresses backlink-based page quality around user-selected pages in a similar way as PageRank expresses quality over the entire Web. Existing personalized PageRank algorithms can however serve on-line queries only for a restricted choice of page selection. In this paper we achieve full personalization by a novel algorithm that computes a compact database of simulated random walks; this database can serve arbitrary personal choices of small subsets of web pages.

2002

• (Haveliwala, 2002) ⇒ Taher H. Haveliwala. (2002). “Topic-sensitive PageRank.” In: Proceedings of the 11th International Conference on World Wide Web. doi:10.1145/511446.511513

---