BATON: Batch One-Hop Personalized PageRanks with Efficiency and Accuracy

• Published in: IEEE transactions on knowledge and data engineering 2020-10, Vol.32 (10), p.1897-1908
• Main Authors: Luo, Siqiang, Xiao, Xiaokui, Lin, Wenqing, Kao, Ben
• Format: Article
• Language: English
• Subjects: Accuracy; Algorithms; Benchmark testing; graph algorithms; Heuristic algorithms; Monte Carlo methods; Nodes; Personalized PageRanks; Pins; Queries; query performance; Query processing; Search engines; Twitter
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2019.2912606

Personalized PageRank (PPR) is a classic measure of the relevance among different nodes in a graph, and has been applied in numerous systems, such as Twitter's Who-To-Follow and Pinterest's Related Pins. Existing work on PPR has mainly focused on three general types of queries, namely, single-pair PPR, single-source PPR, and all-pair PPR. However, we observe that there are applications that rely on a new query type (referred to as batch one-hop PPR ), which takes as input a set S S of source nodes and, for each node s \in S s∈S and each of s s 's neighbor v v , asks for the PPR value of v v with respect to s s . None of the existing PPR algorithms is able to efficiently process batch one-hop queries, due to the inherent differences between batch one-hop PPR and the three general query types. To address the limitations of existing algorithms, this paper presents Baton , an algorithm for batch one-hop PPR that offers both strong theoretical guarantees and practical efficiency. Baton leverages the characteristics of one-hop PPR to avoid unnecessary computation, and it incorporates advanced mechanisms to improve the cost-effectiveness of PPR derivations. Extensive experiments on benchmark datasets show that Baton is up to three orders of magnitude faster than the state of the art, while offering the same accuracy.