Random Walk with Restart (RWR) Algorithm

A Random Walk with Restart (RWR) Algorithm is a Random Walk Algorithm with a restart step.

• Context:
  • It was first published by Kim et al. (2009).
  • …
• Example(s):
  • a Personalize PageRank (PPR) Algorithm,
  • a Random Walk with Restart on Multiplex Networks (RWR-M) Algorithm (e.g. Valdeolivas, 2019),
  • a Random Walk with Restart on Multiplex-Heterogeneous Networks (RWR-MH) Algorithm (e.g. Valdeolivas, 2019),
  • …
• Counter-Example(s):
  • a Random Surfing Algorithm,
  • a Random-Walk-based Sense Disambiguation Algorithm,
  • a Sequence Alignment Algorithm,
  • a Simple Random Walk (SRW) Algorithm,
  • a 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.

2019

• (Valdeolivas, 2019) ⇒ Alberto Valdeolivas, Laurent Tichit, Claire Navarro, Sophie Perrin, Gaelle Odelin, Nicolas Levy, Pierre Cau, Elisabeth Remy, and Anais Baudot (2019). "Random walk with restart on multiplex and heterogeneous biological networks". In: Bioinformatics, Volume 35, Issue 3.
  • QUOTE: In this study, we extended the RWR algorithm to multiplex and heterogeneous networks.

    (...)

    The source code is available on GitHub at: https://github.com/alberto-valdeolivas/RWR-MH.

    In addition, an R package is freely available through Bioconductor at: http://bioconductor.org/packages/RandomWalkRestartMH/.

2015

• (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

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

2010a

• (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

2010b

• (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.

2009

• (Kim el al., 2009) ⇒ Tae Hoon Kim, Kyoung Mu Lee, and Sang Uk Lee (2009). "Generative Image Segmentation Using Random Walks with Restart". In: In European conference on computer vision (pp. 264-275). Springer, Berlin, Heidelberg. DOI:10.1007/978-3-540-88690-7_20.

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 …

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

---