Node-Centric Random Walk for Fast Index-Free Personalized PageRank

Kohei Tsuchida, Naoki Matsumoto, Kunitake Kaneko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Personalized PageRank (PPR) is a popular graph computation in various real-world applications. Since massive real-world graphs are evolving rapidly, PPR computation methods require index-free and fast. In general, index-free methods go through Forward Push phase and random walk Monte-Carlo simulation phase respectively. While existing methods have succeeded in accelerating the Forward Push phase, there is a space for running-time improvements in the second phase that performs a large number of sequential random walks. Through this sequential process, each random walk needs to obtain neighbor nodes for every single step, which causes redundant operation at each node as a result. Our proposal is a node-centric random walk that aggregates random walks at each node and minimizes the total number of obtaining neighbor nodes in the second phase. Most of the random walks can be aggregated while maintaining theoretical guarantees because they do not need to memorize the starting node. In addition, we review the expected running time of random walk Monte-Carlo simulation focusing on the total number of obtaining neighbor nodes. We conducted extensive experiments using four real-world graphs. Experimental results showed that our proposed method is up to 3.3x faster than the existing methods.

Original languageEnglish
Title of host publication37th International Conference on Information Networking, ICOIN 2023
PublisherIEEE Computer Society
Pages194-199
Number of pages6
ISBN (Electronic)9781665462686
DOIs
Publication statusPublished - 2023
Event37th International Conference on Information Networking, ICOIN 2023 - Bangkok, Thailand
Duration: 2023 Jan 112023 Jan 14

Publication series

NameInternational Conference on Information Networking
Volume2023-January
ISSN (Print)1976-7684

Conference

Conference37th International Conference on Information Networking, ICOIN 2023
Country/TerritoryThailand
CityBangkok
Period23/1/1123/1/14

Keywords

  • Index-Free
  • Personalized PageRank
  • Random Walk

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems

Fingerprint

Dive into the research topics of 'Node-Centric Random Walk for Fast Index-Free Personalized PageRank'. Together they form a unique fingerprint.

Cite this