TY - JOUR
T1 - Efficient algorithms for approximate single-source personalized pagerank queries
AU - Wang, Sibo
AU - Yang, Renchi
AU - Wang, Runhui
AU - Xiao, Xiaokui
AU - Wei, Zhewei
AU - Lin, Wenqing
AU - Yang, Yin
AU - Tang, Nan
N1 - Funding Information:
Sibo Wang is supported by CUHK Direct Grant No. 4055114, CUHK University Startup Grant No. 4930911 and No. 5501570, and a donation from Tencent. Xiaokui Xiao is supported by MOE, Singapore, under grant MOE2015-T2-2-069, and by NUS, Singapore, under an SUG. Zhewei Wei is supported in part by National Natural Science Foundation of China (No. 61972401, 61932001 and 61832017) and by the Fundamental Research Funds for the Central Universities and the Research Funds of Renmin University of China under Grant 18XNLG21. Yin Yang is supported by NPRP grant #NPRP10-0208-170408 from the Qatar National Research Fund. Authors’ addresses: S. Wang, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong; email: [email protected]. edu.hk; R. Yang, Nanyang Technological University, 50 Nanyang Ave, Singapore; email: [email protected]; R. Wang, Rutgers University, New Brunswick, NJ, United States; email: [email protected]; X. Xiao, National University of Singapore, 13 Computing Drive, Singapore; email: [email protected]; Z. Wei (corresponding author), Renmin University of China, Beijing, China; email: [email protected]; W. Lin, Tencent, Shenzhen, China; email: [email protected]; Y. Yang, Hamad Bin Khalifa University, Doha, Qatar; email: [email protected]; N. Tang, Qatar Computing Research Institute, HBKU, Doha, Qatar; email: [email protected]. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. © 2019 Association for Computing Machinery. 0362-5915/2019/10-ART18 $15.00 https://doi.org/10.1145/3360902
Publisher Copyright:
© 2019 Association for Computing Machinery.
PY - 2019/12
Y1 - 2019/12
N2 - Given a graph G, a source node s, and a target node t, the personalized PageRank (PPR) of t with respect to s is the probability that a random walk starting from s terminates at t. An important variant of the PPR query is single-source PPR (SSPPR), which enumerates all nodes in G and returns the top-k nodes with the highest PPR values with respect to a given source s. PPR in general and SSPPR in particular have important applications in web search and social networks, e.g., in Twitter’s Who-To-Follow recommendation service. However, PPR computation is known to be expensive on large graphs and resistant to indexing. Consequently, previous solutions either use heuristics, which do not guarantee result quality, or rely on the strong computing power of modern data centers, which is costly.Motivated by this, we propose effective index-free and index-based algorithms for approximate PPR processing, with rigorous guarantees on result quality. We first present FORA, an approximate SSPPR solution that combines two existing methods—Forward Push (which is fast but does not guarantee quality) and Monte Carlo Random Walk (accurate but slow)—in a simple and yet non-trivial way, leading to both high accuracy and efficiency. Further, FORA includes a simple and effective indexing scheme, as well as a module for top-k selection with high pruning power. Extensive experiments demonstrate that the proposed solutions are orders of magnitude more efficient than their respective competitors. Notably, on a billion-edge Twitter dataset, FORA answers a top-500 approximate SSPPR query within 1s, using a single commodity server.
AB - Given a graph G, a source node s, and a target node t, the personalized PageRank (PPR) of t with respect to s is the probability that a random walk starting from s terminates at t. An important variant of the PPR query is single-source PPR (SSPPR), which enumerates all nodes in G and returns the top-k nodes with the highest PPR values with respect to a given source s. PPR in general and SSPPR in particular have important applications in web search and social networks, e.g., in Twitter’s Who-To-Follow recommendation service. However, PPR computation is known to be expensive on large graphs and resistant to indexing. Consequently, previous solutions either use heuristics, which do not guarantee result quality, or rely on the strong computing power of modern data centers, which is costly.Motivated by this, we propose effective index-free and index-based algorithms for approximate PPR processing, with rigorous guarantees on result quality. We first present FORA, an approximate SSPPR solution that combines two existing methods—Forward Push (which is fast but does not guarantee quality) and Monte Carlo Random Walk (accurate but slow)—in a simple and yet non-trivial way, leading to both high accuracy and efficiency. Further, FORA includes a simple and effective indexing scheme, as well as a module for top-k selection with high pruning power. Extensive experiments demonstrate that the proposed solutions are orders of magnitude more efficient than their respective competitors. Notably, on a billion-edge Twitter dataset, FORA answers a top-500 approximate SSPPR query within 1s, using a single commodity server.
KW - Forward push
KW - Personalized PageRank
KW - Random walk
UR - http://www.scopus.com/inward/record.url?scp=85075592699&partnerID=8YFLogxK
U2 - 10.1145/3360902
DO - 10.1145/3360902
M3 - Journal article
AN - SCOPUS:85075592699
SN - 0362-5915
VL - 44
JO - ACM Transactions on Database Systems
JF - ACM Transactions on Database Systems
IS - 4
M1 - 18
ER -