research-article

Agenda: Robust Personalized PageRanks in Evolving Graphs

Authors:

Siqiang LuoAuthors Info & Claims

CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

Pages 1315 - 1324

https://doi.org/10.1145/3459637.3482317

Published: 30 October 2021 Publication History

Abstract

Given a source node s and a target node t in a graph G, the Personalized PageRank (PPR) from s to t is the probability of a random walk starting from s terminates at t. PPR is a classic measure of the relevance among different nodes in a graph, and has been applied in numerous real-world systems. However, existing techniques for PPR queries are not robust to dynamic real-world graphs, which typically have different evolving speeds. Their performance is significantly degraded either at a lower graph evolving rate (e.g., much more queries than updates) or a higher rate.

To address the above deficiencies, we propose Agenda to efficiently process, with strong approximation guarantees, the single-source PPR (SSPPR) queries on dynamically evolving graphs with various evolving speeds. Compared with previous methods, Agenda has significantly better workload robustness, while ensuring the same result accuracy. Agenda also has theoretically-guaranteed small query and update costs. Experiments on up to billion-edge scale graphs show that Agenda significantly outperforms state-of-the-art methods for various query/update workloads, while maintaining better or comparable approximation accuracies.

References

[1]

https://spark-summit.org/2017/events/random-walks-on-large-scale-graphswith-apache-spark/.

[2]

https://www.businessofapps.com/data/twitter-statistics/.

[3]

https://techjury.net/blog/linkedin-statistics//.

[4]

https://www.similarweb.com/zh/website/twitter.com/?competitors=linkedin.com.

[5]

https://www.engadget.com/twitter-2020-q2--112630105.html.

[6]

Genda technical report. https://sites.google.com/view/agenda-technical-report/, 2020.

[7]

Abraham, I., Delling, D., Goldberg, A. V., and Werneck, R. F. A hub-based labeling algorithm for shortest paths in road networks. In International Symposium on Experimental Algorithms (2011), pp. 230--241.

Digital Library

[8]

Andersen, R., Borgs, C., Chayes, J., Hopcraft, J., Mirrokni, V. S., and Teng, S.-H. Local computation of pagerank contributions. In International Workshop on Algorithms and Models for the Web-Graph (2007), Springer, pp. 150--165.

Digital Library

[9]

Andersen, R., Chung, F., and Lang, K. Local graph partitioning using pagerank vectors. In FOCS (2006), pp. 475--486.

Digital Library

[10]

Bahmani, B., Chakrabarti, K., and Xin, D. Fast personalized pagerank on mapreduce. In SIGMOD (2011), pp. 973--984.

Digital Library

[11]

Bahmani, B., Chowdhury, A., and Goel, A. Fast incremental and personalized pagerank. VLDB 4, 3 (2010).

Digital Library

[12]

Bahmani, B., Kumar, R., Mahdian, M., and Upfal, E. Pagerank on an evolving graph. In KDD (New York, NY, USA, 2012), Association for Computing Machinery.

Digital Library

[13]

Bast, H., Funke, S., Sanders, P., and Schultes, D. Fast routing in road networks with transit nodes. Science 316, 5824 (2007), 566--566.

[14]

Chakrabarti, S. Dynamic personalized pagerank in entity-relation graphs. In WWW (2007), pp. 571--580.

Digital Library

[15]

Fang, Y., Cheng, R., Li, X., Luo, S., and Hu, J. Effective community search over large spatial graphs. Proceedings of the VLDB Endowment 10, 6 (2017), 709--720.

Digital Library

[16]

Fang, Y., Cheng, R., Luo, S., and Hu, J. Effective community search for large attributed graphs. VLDB 9, 12 (2016), 1233--1244.

Digital Library

[17]

Fogaras, D., Rácz, B., Csalogány, K., and Sarlós, T. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics 2, 3 (2005), 333--358.

[18]

Fujiwara, Y., Nakatsuji, M., Yamamuro, T., Shiokawa, H., and Onizuka, M. Efficient personalized pagerank with accuracy assurance. In KDD (2012), pp. 15--23.

Digital Library

[19]

Guo, W., Li, Y., Sha, M., and Tan, K.-L. Parallel personalized pagerank on dynamic graphs. VLDB 11, 1 (2017), 93--106.

Digital Library

[20]

Gupta, M., Pathak, A., and Chakrabarti, S. Fast algorithms for topk personalized pagerank queries. In WWW (2008), pp. 1225--1226.

Digital Library

[21]

Gupta, P., Goel, A., Lin, J., Sharma, A., Wang, D., and Zadeh, R. Wtf: The who to follow service at twitter. In WWW (2013), pp. 505--514.

Digital Library

[22]

Haveliwala, T., Kamvar, S., Klein, D., Manning, C., and Golub, G. Computing pagerank using power extrapolation. Tech. rep., Stanford, 2003.

[23]

Järvelin, K., and Kekäläinen, J. IR evaluation methods for retrieving highly relevant documents. In SIGIR (2017), vol. 51, pp. 243--250.

Digital Library

[24]

Li, R.-H., Qin, L., Yu, J. X., and Mao, R. Influential community search in large networks. VLDB 8, 5 (2015), 509--520.

Digital Library

[25]

Lin, D., Wong, R. C.-W., Xie, M., and Wei, V. J. Index-free approach with theoretical guarantee for efficient random walk with restart query. In ICDE (2020), pp. 913--924.

[26]

Liu, D. C., Rogers, S., Shiau, R., Kislyuk, D., Ma, K. C., Zhong, Z., Liu, J., and Jing, Y. Related pins at pinterest: The evolution of a real-world recommender system. In WWW (Companion) (2017), pp. 583--592.

Digital Library

[27]

Lofgren, P., Banerjee, S., and Goel, A. Personalized pagerank estimation and search: A bidirectional approach. In WSDM (2016), pp. 163--172.

Digital Library

[28]

Lofgren, P. A., Banerjee, S., Goel, A., and Seshadhri, C. FAST-PPR: scaling personalized pagerank estimation for large graphs. In KDD (2014), pp. 1436--1445.

Digital Library

[29]

Luo, S. Distributed pagerank computation: An improved theoretical study. AAAI (2019), 4496--4503.

[30]

Luo, S. Improved communication cost in distributed PageRank computation -- a theoretical study. In ICML (2020), pp. 6459--6467.

[31]

Luo, S., Kao, B., Li, G., Hu, J., Cheng, R., and Zheng, Y. Toain: a throughput optimizing adaptive index for answering dynamic k nn queries on road networks. VLDB 11, 5 (2018), 594--606.

Digital Library

[32]

Luo, S., Kao, B., Wu, X., and Cheng, R. MPR-A partitioning-replication framework for multi-processing kNN search on road networks. In ICDE (2019), pp. 1310--1321.

[33]

Luo, S., Luo, Y., Zhou, S., Cong, G., and Guan, J. DISKs: a system for distributed spatial group keyword search on road networks. VLDB 5, 12 (2012), 1966--1969.

Digital Library

[34]

Luo, S., Luo, Y., Zhou, S., Cong, G., Guan, J., and Yong, Z. Distributed spatial keyword querying on road networks. In EDBT (2014), pp. 235--246.

[35]

Luo, S., Xiao, X., Lin, W., and Kao, B. Baton: Batch one-hop personalized pageranks with efficiency and accuracy. TKDE (2019).

[36]

Luo, S., Xiao, X., Lin, W., and Kao, B. Efficient batch one-hop personalized pageranks. In ICDE (2019), pp. 1562--1565.

[37]

Maehara, T., Akiba, T., Iwata, Y., and Kawarabayashi, K.-i. Computing personalized pagerank quickly by exploiting graph structures. VLDB 7, 12 (2014), 1023--1034.

Digital Library

[38]

Myers, S. A., and Leskovec, J. The bursty dynamics of the twitter information network. In WWW (2014), pp. 913--924.

Digital Library

[39]

Myers, S. A., Sharma, A., Gupta, P., and Lin, J. Information network or social network? the structure of the twitter follow graph. In WWW (2014), pp. 493--498.

Digital Library

[40]

Ohsaka, N., Maehara, T., and Kawarabayashi, K.-i. Efficient pagerank tracking in evolving networks. In SIGKDD (2015), pp. 875--884.

Digital Library

[41]

Page, L., Brin, S., Motwani, R., and Winograd, T. The pagerank citation ranking: Bringing order to the web. Tech. rep., Stanford InfoLab, 1999.

[42]

Sarma, A. D., Molla, A. R., Pandurangan, G., and Upfal, E. Fast distributed pagerank computation. In ICDCN (2013), Springer, pp. 11--26.

[43]

Shin, K., Jung, J., Lee, S., and Kang, U. Bear: Block elimination approach for random walk with restart on large graphs. In SIGMOD (2015), pp. 1571--1585.

Digital Library

[44]

Wang, S., Tang, Y., Xiao, X., Yang, Y., and Li, Z. HubPPR: effective indexing for approximate personalized pagerank. VLDB 10, 3 (2016), 205--216.

Digital Library

[45]

Wang, S., Yang, R., Wang, R., Xiao, X., Wei, Z., Lin, W., Yang, Y., and Tang, N. Efficient algorithms for approximate single-source personalized pagerank queries. TODS 44, 4 (2019), 1--37.

Digital Library

[46]

Wang, S., Yang, R., Xiao, X., Wei, Z., and Yang, Y. FORA: simple and effective approximate single-source personalized pagerank. In KDD (2017), pp. 505--514.

Digital Library

[47]

Wang, Y., Wang, Q., Koehler, H., and Lin, Y. Query-by-sketch: Scaling shortest path graph queries on very large networks. In SIGMOD (2021), pp. 1946--1958.

Digital Library

[48]

Wei, Z., He, X., Xiao, X., Wang, S., Shang, S., and Wen, J.-R. Topppr: top-k personalized pagerank queries with precision guarantees on large graphs. In SIGMOD (2018), pp. 441--456.

Digital Library

[49]

Wu, H., Gan, J., Wei, Z., and Zhang, R. Unifying the global and local approaches: An efficient power iteration with forward push. In Proceedings of the 2020aCM SIGMOD International Conference on Management of Data (2021), p. 1996--2008.

Digital Library

[50]

Yoon, M., Jin, W., and Kang, U. Fast and accurate random walk with restart on dynamic graphs with guarantees. In WWW (2018), P. Champin, F. Gandon, M. Lalmas, and P. G. Ipeirotis, Eds., ACM, pp. 409--418.

Digital Library

[51]

Yoon, M., Jung, J., and Kang, U. TPA: Fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. In ICDE (2018), pp. 1132--1143.

[52]

Yu, W., and McCann, J. Random walk with restart over dynamic graphs. In ICDM (2016), pp. 589--598.

[53]

Yuan, H., Li, G., Bao, Z., and Feng, L. Effective travel time estimation: When historical trajectories over road networks matter. In SIGMOD (2020), pp. 2135--2149.

Digital Library

[54]

Zhan, F. B., and Noon, C. E. Shortest path algorithms: an evaluation using real road networks. Transportation science 32, 1 (1998), 65--73.

Digital Library

[55]

Zhan, Z., Hu, R., Gao, X., and Huai, N. Fast incremental pagerank on dynamic networks. In Web Engineering (Cham, 2019), M. Bakaev, F. Frasincar, and I.-Y. Ko, Eds., Springer International Publishing, pp. 154--168.

Digital Library

[56]

Zhang, H., Lofgren, P., and Goel, A. Approximate personalized pagerank on dynamic graphs. In KDD (2016), pp. 1315--1324.

Digital Library

[57]

Zhu, A. D., Ma, H., Xiao, X., Luo, S., Tang, Y., and Zhou, S. Shortest path and distance queries on road networks: towards bridging theory and practice. In SIGMOD (2013), pp. 857--868.

Digital Library

[58]

Zhu, F., Fang, Y., Chang, K. C.-C., and Ying, J. Incremental and accuracy-aware personalized pagerank through scheduled approximation.

Cited By

Zhu ZWang KLiu HLi JLuo SBaeza-Yates RBonchi F(2024)Topology-monitorable Contrastive Learning on Dynamic GraphsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671777(4700-4711)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671777
Yang MWang HWei ZWang SWen J(2024)Efficient Algorithms for Personalized PageRank Computation: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.337600036:9(4582-4602)Online publication date: Sep-2024
https://doi.org/10.1109/TKDE.2024.3376000
Zhang XHuang JZhang FWang S(2024)FICOM: an effective and scalable active learning framework for GNNs on semi-supervised node classificationThe VLDB Journal10.1007/s00778-024-00870-z33:5(1723-1742)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00778-024-00870-z
Show More Cited By

Index Terms

Agenda: Robust Personalized PageRanks in Evolving Graphs
1. Information systems
  1. Information systems applications
    1. Data mining
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms

Recommendations

CoUPE: Continuous Query Processing Engine for Evolving Graphs
BIGDATACONGRESS '15: Proceedings of the 2015 IEEE International Congress on Big Data

Continuously Evolving Graphs (CEGs) are graphs whose connectivity constantly changes over time is uniquely important for many domains such as social networks, evolutionary genomics, communication networks etc. In many of these it is often important to ...
BLINKS: ranked keyword searches on graphs
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Query processing over graph-structured data is enjoying a growing number of applications. A top-k keyword search query on a graph finds the top k answers according to some ranking criteria, where each answer is a substructure of the graph containing all ...
A Characterization of $K_{2,4}$-Minor-Free Graphs

We provide a complete structural characterization of $K_{2,4}$-minor-free graphs. The 3-connected $K_{2,4}$-minor-free graphs consist of nine small graphs on at most eight vertices, together with a family of planar graphs that contains $2n-8$ ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '21: Proceedings of the 30th ACM International Conference on Information & Knowledge Management

October 2021

4966 pages

ISBN:9781450384469

DOI:10.1145/3459637

General Chairs:
Gianluca Demartini
The University of Queensland, Australia
,
Guido Zuccon
The University of Queensland, Australia
,
Program Chairs:
J. Shane Culpepper
RMIT University, Australia
,
Zi Huang
The University of Queensland, Australia
,
Hanghang Tong
University of Illinois at Urbana-Champaign, USA

Copyright © 2021 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 October 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NTU
MOE Singapore

Conference

CIKM '21

Sponsor:

CIKM '21: The 30th ACM International Conference on Information and Knowledge Management

November 1 - 5, 2021

Queensland, Virtual Event, Australia

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
350
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)6

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu ZWang KLiu HLi JLuo SBaeza-Yates RBonchi F(2024)Topology-monitorable Contrastive Learning on Dynamic GraphsProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671777(4700-4711)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671777
Yang MWang HWei ZWang SWen J(2024)Efficient Algorithms for Personalized PageRank Computation: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.337600036:9(4582-4602)Online publication date: Sep-2024
https://doi.org/10.1109/TKDE.2024.3376000
Zhang XHuang JZhang FWang S(2024)FICOM: an effective and scalable active learning framework for GNNs on semi-supervised node classificationThe VLDB Journal10.1007/s00778-024-00870-z33:5(1723-1742)Online publication date: 22-Jul-2024
https://doi.org/10.1007/s00778-024-00870-z
Li YShen YChen LYuan M(2023)Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRankProceedings of the VLDB Endowment10.14778/3583140.358315016:6(1332-1345)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583150
Hou GGuo QZhang FWang SWei Z(2023)Personalized PageRank on Evolving Graphs with an Incremental Index-Update SchemeProceedings of the ACM on Management of Data10.1145/35887051:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588705
Li ZFu DHe J(2023)Everything Evolves in Personalized PageRankProceedings of the ACM Web Conference 202310.1145/3543507.3583474(3342-3352)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583474
Mo DLuo S(2023)Single-Source Personalized PageRanks With Workload RobustnessIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.317581435:6(6320-6334)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3175814
Tsuchida KMatsumoto NShin AKaneko K(2023)Cache-Efficient Approach for Index-Free Personalized PageRankIEEE Access10.1109/ACCESS.2023.323773811(6944-6957)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3237738
Liao NMo DLuo SLi XYin P(2023)Scalable decoupling graph neural network with feature-oriented optimizationThe VLDB Journal10.1007/s00778-023-00829-633:3(667-683)Online publication date: 27-Dec-2023
https://doi.org/10.1007/s00778-023-00829-6
Yeh WZhu WHuang CHsu TLiu ZTan S(2022)A New BAT and PageRank Algorithm for Propagation Probability in Social NetworksApplied Sciences10.3390/app1214685812:14(6858)Online publication date: 6-Jul-2022
https://doi.org/10.3390/app12146858
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents