Efficient and Accurate PageRank Approximation on Large Graphs
Article No.: 196, Pages 1 - 26
Abstract
PageRank is a commonly used measurement in a wide range of applications, including search engines, recommendation systems, and social networks. However, this measurement suffers from huge computational overhead, which cannot be scaled to large graphs. Although many approximate algorithms have been proposed for computing PageRank values, these algorithms are either (i) not efficient or (ii) not accurate. Worse still, some of them cannot provide estimated PageRank values for all the vertices. In this paper, we first propose the CUR-Trans algorithm, which can reduce the time complexity for computing PageRank values and has lower error bound than existing matrix approximation-based PageRank algorithms. Then, we develop the T 2-Approx algorithm to further reduce the time complexity for computing this measurement. Experiment results on three large-scale graphs show that both the CUR-Trans algorithm and the T 2-Approx algorithm achieve the lowest response time for computing PageRank values with the best accuracy (for the CUR-Trans algorithm) or the competitive accuracy (for the T 2-Approx algorithm). Besides, the two proposed algorithms are able to provide estimated PageRank values for all the vertices.
References
[1]
Ziv Bar-Yossef andLi-Tal Mashiach. 2008. Local approximation of pagerank and reverse pagerank. In CIKM. 279--288.
[2]
Eugenio Angriman, Alexander van der Grinten, Michael Hamann, Henning Meyerhenke, and Manuel Penschuck. 2022. Algorithms for Large-Scale Network Analysis and the NetworKit Toolkit. In Algorithms for Big Data - DFG Priority Program 1736. Vol. 13201. 3--20.
[3]
Anton Anikin, Alexander Gasnikov, Alexander Gornov, Dmitry Kamzolov, Yury Maximov, and Yurii Nesterov. 2022. Efficient numerical methods to solve sparse linear equations with application to pagerank. Optimization Methods and Software, Vol. 37 (2022), 907--935.
[4]
Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, and Natalia Osipova. 2007. Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient. SIAM J. Numer. Anal., Vol. 45 (2007), 890--904.
[5]
Bahman Bahmani, Kaushik Chakrabarti, and Dong Xin. 2011. Fast personalized PageRank on MapReduce. In SIGMOD. 973--984.
[6]
Sudipto Banerjee and Anindya Roy. 2014. Linear algebra and matrix analysis for statistics. Crc Press.
[7]
András A. Benczúr, Károly Csalogány, and Tamás Sarlós. 2005. On the feasibility of low-rank approximation for personalized PageRank. In WWW. 972--973.
[8]
Monica Bianchini, Marco Gori, and Franco Scarselli. 2005. Inside PageRank. ACM Trans. Internet Techn., Vol. 5 (2005), 92--128.
[9]
Paolo Boldi, Bruno Codenotti, Massimo Santini, and Sebastiano Vigna. 2004. UbiCrawler: a scalable fully distributed Web crawler. Softw. Pract. Exp., Vol. 34 (2004), 711--726.
[10]
Arsineh Boodaghian Asl, Jayanth Raghothama, Adam Darwich, and Sebastiaan Meijer. 2021. using PageRank and social network analysis to sprcify mental health factors. Proceedings of the Design Society, Vol. 1 (2021), 3379--3388.
[11]
L. A. Breyer. 2002. Markovian page ranking distributions: some theory and simulations. Technical Report.
[12]
Sergey Brin and Lawrence Page. 1998. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Comput. Networks, Vol. 30, 1--7 (1998), 107--117.
[13]
Jie Chen and Yousef Saad. 2009. On the tensor SVD and the optimal low rank orthogonal approximation of tensors. SIAM journal on Matrix Analysis and Applications, Vol. 30 (2009), 1709--1734.
[14]
Yen-Yu Chen, Qingqing Gan, and Torsten Suel. 2004. Local methods for estimating pagerank values. In CIKM. 381--389.
[15]
Zhen Chen, Xingzhi Guo, Baojian Zhou, Deqing Yang, and Steven Skiena. 2023. Accelerating Personalized PageRank Vector Computation. In KDD. 262--273.
[16]
Eunjoon Cho, Seth A Myers, and Jure Leskovec. 2011. Friendship and mobility: user movement in location-based social networks. In SIGKDD. 1082--1090.
[17]
Fan Chung. 2014. A Brief Survey of PageRank Algorithms. IEEE Trans. Netw. Sci. Eng., Vol. 1 (2014), 38--42.
[18]
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to algorithms. MIT press.
[19]
Gianna M. Del Corso, Antonio Gulli, and Francesco Romani. 2005. Fast PageRank Computation via a Sparse Linear System. Internet Math., Vol. 2 (2005), 251--273.
[20]
Jason V. Davis and Inderjit S. Dhillon. 2006. Estimating the global pagerank of web communities. In SIGKDD. 116--125.
[21]
Petros Drineas and Ravi Kannan. 2001. Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. In FOCS. 452--459.
[22]
Petros Drineas and Ravi Kannan. 2003. Pass efficient algorithms for approximating large matrices. In ACM-SIAM. 223--232.
[23]
Petros Drineas, Ravi Kannan, and Michael W. Mahoney. 2006 a. Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM J. Comput., Vol. 36 (2006), 132--157.
[24]
Petros Drineas, Ravi Kannan, and Michael W. Mahoney. 2006 b. Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. SIAM J. Comput., Vol. 36 (2006), 158--183.
[25]
Petros Drineas, Ravi Kannan, and Michael W. Mahoney. 2006 c. Fast Monte Carlo Algorithms for Matrices III: Computing a Compressed Approximate Matrix Decomposition. SIAM J. Comput., Vol. 36 (2006), 184--206.
[26]
Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. 2008. Relative-Error CUR Matrix Decompositions. SIAM J. Matrix Anal. Appl., Vol. 30 (2008), 844--881.
[27]
Carl Eckart and Gale Young. 1936. The approximation of one matrix by another of lower rank. Psychometrika, Vol. 1 (1936), 211--218.
[28]
David F Gleich, Andrew P Gray, Chen Greif, and Tracy Lau. 2010. An inner-outer iteration for computing PageRank. SIAM Journal on Scientific Computing, Vol. 32 (2010), 349--371.
[29]
Gene H Golub, Alan Hoffman, and Gilbert W Stewart. 1987. A generalization of the Eckart-Young-Mirsky matrix approximation theorem. Linear Algebra and its applications, Vol. 88 (1987), 317--327.
[30]
Gene H Golub and Christian Reinsch. 1971. Singular value decomposition and least squares solutions. In Handbook for Automatic Computation: Volume II: Linear Algebra. Springer, 134--151.
[31]
Chuanqing Gu, Fei Xie, and Ke Zhang. 2015. A two-step matrix splitting iteration for computing PageRank. J. Comput. Appl. Math., Vol. 278 (2015), 19--28.
[32]
Charles R. Harris, K. Jarrod Millman, Stéfan van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. 2020. Array programming with NumPy. Nat., Vol. 585 (2020), 357--362.
[33]
Somaia Awad Hassan, A. M. Hemeida, and Mountasser M. M. Mahmoud. 2016. Performance Evaluation of Matrix-Matrix Multiplications Using Intel's Advanced Vector Extensions (AVX). Microprocess. Microsystems, Vol. 47 (2016), 369--374.
[34]
Taher Haveliwala et al. 1999. Efficient computation of PageRank. Technical Report. Citeseer.
[35]
Fumio Hiai and Dénes Petz. 2014. Introduction to matrix analysis and applications. Springer Science & Business Media.
[36]
Guanhao Hou, Xingguang Chen, Sibo Wang, and Zhewei Wei. 2021. Massively Parallel Algorithms for Personalized PageRank. Proc. VLDB Endow., Vol. 14 (2021), 1668--1680.
[37]
J Jackson. 2013. Facebook?s graph search puts Apache Giraph on the map. Retrieved July, Vol. 25 (2013), 2015.
[38]
Kalervo Järvelin and Jaana Kekäläinen. 2002. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems (TOIS), Vol. 20, 4 (2002), 422--446.
[39]
Sepandar Kamvar, Taher Haveliwala, and Gene Golub. 2004. Adaptive methods for the computation of PageRank. Linear Algebra Appl., Vol. 386 (2004), 51--65.
[40]
Sepandar D Kamvar, Taher H Haveliwala, Christopher Manning, and Gene H Golub. 2003 a. Exploiting the block structure of the web for computing pagerank. Technical Report.
[41]
Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, and Gene H. Golub. 2003 b. Extrapolation methods for accelerating PageRank computations. In WWW. 261--270.
[42]
Seunghwa Kang, Joseph Nke, and Brad Rees. 2022. Analyzing Multi-trillion Edge Graphs on Large GPU Clusters: A Case Study with PageRank. In HPEC. 1--7.
[43]
George Karypis and Vipin Kumar. 1999. Parallel Multilevel series k-Way Partitioning Scheme for Irregular Graphs. SIAM Rev., Vol. 41 (1999), 278--300.
[44]
N Kishore Kumar and Jan Schneider. 2017. Literature survey on low rank approximation of matrices. Linear and Multilinear Algebra, Vol. 65, 11 (2017), 2212--2244.
[45]
Milovs Kotlar, Marija Punt, and Veljko Milutinović. 2022. Energy efficient implementation of tensor operations using dataflow paradigm for machine learning. In Advances in Computers. Vol. 126. 151--199.
[46]
Liang Lan, Kai Zhang, Hancheng Ge, Wei Cheng, Jun Liu, Andreas Rauber, Xiao-Li Li, Jun Wang, and Hongyuan Zha. 2017. Low-rank decomposition meets kernel learning: A generalized Nyström method. Artificial Intelligence, Vol. 250 (2017), 1--15.
[47]
Amy Nicole Langville and Carl Dean Meyer. 2003. Survey: Deeper Inside PageRank. Internet Math., Vol. 1 (2003), 335--380.
[48]
Mu Li, James Tin-Yau Kwok, and Baoliang Lü. 2010. Making large-scale Nyström approximation possible. In ICML. 631.
[49]
Xiaocan Li, Shuo Wang, and Yinghao Cai. 2019. Tutorial: Complexity analysis of singular value decomposition and its variants. arXiv (2019).
[50]
Meihao Liao, Rong-Hua Li, Qiangqiang Dai, and Guoren Wang. 2022. Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach. In SIGMOD. 2048--2061.
[51]
Wenting Liu, Guangxia Li, and James Cheng. 2015. Fast PageRank approximation by adaptive sampling. Knowl. Inf. Syst., Vol. 42 (2015), 127--146.
[52]
Jun Lu. 2021. A rigorous introduction to linear models. arXiv (2021).
[53]
Jun Lu. 2022. Matrix decomposition and applications. arXiv (2022).
[54]
Siqiang Luo. 2019. Distributed PageRank Computation: An Improved Theoretical Study. In AAAI. 4496--4503.
[55]
Siqiang Luo, Xiaowei Wu, and Ben Kao. 2022. Distributed PageRank computation with improved round complexities. Inf. Sci., Vol. 607 (2022), 109--125.
[56]
Michael W. Mahoney and Petros Drineas. 2009. CUR matrix decompositions for improved data analysis. Proc. Natl. Acad. Sci. USA, Vol. 106, 3 (2009), 697--702.
[57]
Julian J. McAuley and Jure Leskovec. 2012. Learning to Discover Social Circles in Ego Networks. In NIPS. 548--556.
[58]
Alan Mislove, Massimiliano Marcon, P. Krishna Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007. Measurement and analysis of online social networks. In SIGCOMM. 29--42.
[59]
Dingheng Mo and Siqiang Luo. 2023. Single-Source Personalized PageRanks With Workload Robustness. IEEE Trans. Knowl. Data Eng., Vol. 35 (2023), 6320--6334.
[60]
Yuji Nakatsukasa. 2020. Fast and stable randomized low-rank matrix approximation. arXiv:2009.11392 (2020).
[61]
José Ignacio Orlicki, Pablo Ignacio Fierens, and J. Ignacio Alvarez-Hamelin. 2008. Faceted Ranking of Egos in Collaborative Tagging Systems. CoRR, Vol. abs/0809.4668 (2008).
[62]
José Ignacio Orlicki, Pablo Ignacio Fierens, and J. Ignacio Alvarez-Hamelin. 2009. Faceted Ranking in Collaborative Tagging Systems - Efficient Algorithms for Ranking Users based on a Set of Tags. In WEBIST. 626--633.
[63]
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1998. The pagerank citation ranking: Bring order to the web. Technical Report. Technical report, stanford University.
[64]
C-T Pan. 2000. On the existence and computation of rank-revealing LU factorizations. Linear Algebra Appl., Vol. 316 (2000), 199--222.
[65]
R Piziak and PL Odell. 1999. Full rank factorization of matrices. Mathematics magazine, Vol. 72 (1999), 193--201.
[66]
Atish Das Sarma, Anisur Rahaman Molla, Gopal Pandurangan, and Eli Upfal. 2015. Fast distributed PageRank computation. Theor. Comput. Sci., Vol. 561 (2015), 113--121.
[67]
Christian L Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. 2016. NetworKit: A tool suite for large-scale complex network analysis. Network Science, Vol. 4, 4 (2016), 508--530.
[68]
Min Tao, Xinmin Yang, Gao Gu, and Bohan Li. 2020. Paper recommend based on LDA and PageRank. In ICAIS. 571--584.
[69]
Zhaolu Tian, Yong Liu, Yan Zhang, Zhongyun Liu, and Maoyi Tian. 2019. The general inner-outer iteration method based on regular splittings for the PageRank problem. Appl. Math. Comput., Vol. 356 (2019), 479--501.
[70]
Hanghang Tong, Christos Faloutsos, and Jia-Yu Pan. 2006. Fast Random Walk with Restart and Its Applications. In ICDM. 613--622.
[71]
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C J Carey, .Ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. 2020. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, Vol. 17 (2020), 261--272.
[72]
Hanzhi Wang, Zhewei Wei, Junhao Gan, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. 2022. Edge-based Local Push for Personalized PageRank. Proc. VLDB Endow., Vol. 15 (2022), 1376--1389.
[73]
Sibo Wang and Yufei Tao. 2018. Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks. In SIGMOD. 1113--1127.
[74]
Sibo Wang, Renchi Yang, Runhui Wang, Xiaokui Xiao, Zhewei Wei, Wenqing Lin, Yin Yang, and Nan Tang. 2019. Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries. ACM Trans. Database Syst., Vol. 44 (2019), 18:1--18:37.
[75]
Yizhuo Wang, Weixing Ji, Xu Chen, and Sensen Hu. 2015. Task Parallel Implementation of Matrix Multiplication on Multi-socket Multi-core Architectures. In ICA3PP, Vol. 9530. 93--104.
[76]
Yao Wu and Louiqa Raschid. 2009. ApproxRank: Estimating Rank for a Subgraph. In ICDE. 54--65.
[77]
Yajun Xie, Lihua Hu, and Changfeng Ma. 2023. A Parameterized Multi-Splitting Iterative Method for Solving the PageRank Problem. Mathematics, Vol. 11, 15 (2023), 3320.
[78]
Ya-Jun Xie and Chang-Feng Ma. 2018. A relaxed two-step splitting iteration method for computing PageRank. Computational and Applied Mathematics, Vol. 37 (2018), 221--233.
[79]
Reynold S Xin, Joseph E Gonzalez, Michael J Franklin, and Ion Stoica. 2013. Graphx: A resilient distributed graph system on spark. In First international workshop on graph data management experiences and systems. 1--6.
[80]
Jieping Ye and Qi Li. 2005. A two-stage linear discriminant analysis via QR-decomposition. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 27 (2005), 929--941.
[81]
Fuzhen Zhang. 2015. A matrix decomposition and its applications. Linear and Multilinear Algebra, Vol. 63 (2015), 2033--2042.
[82]
Shijie Zhou, Kartik Lakhotia, Shreyas G. Singapura, Hanqing Zeng, Rajgopal Kannan, Viktor K. Prasanna, James Fox, Euna Kim, Oded Green, and David A. Bader. 2017. Design and implementation of parallel PageRank on multicore platforms. In HPEC. 1--6.
Index Terms
- Efficient and Accurate PageRank Approximation on Large Graphs
Recommendations
L(2,1)-labeling of dually chordal graphs and strongly orderable graphs
An L(2,1)-labeling of a graph G=(V,E) is a function f:V(G)->{0,1,2,...} such that |f(u)-f(v)|>=2 whenever uv@__ __E(G) and |f(u)-f(v)|>=1 whenever u and v are at distance two apart. The span of an L(2,1)-labeling f of G, denoted as SP"2(f,G), is the ...
Beyond PageRank: machine learning for static ranking
WWW '06: Proceedings of the 15th international conference on World Wide WebSince the publication of Brin and Page's paper on PageRank, many in the Web community have depended on PageRank for the static (query-independent) ordering of Web pages. We show that we can significantly outperform PageRank using features that are ...
Associated pagerank: improved pagerank measured by frequent term sets
VECIMS'09: Proceedings of the 2009 IEEE international conference on Virtual Environments, Human-Computer Interfaces and Measurement SystemsWeb search engines encounter many new challenges while the amount of information on the web increases rapidly. Web documents have been a main resource for various purposes, and people rely on search engines to retrieve the desired documents. This paper ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2024
458 pages
Copyright © 2024 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 the author(s) 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].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 September 2024
Published in PACMMOD Volume 2, Issue 4
Author Tags
Qualifiers
- Research-article
Funding Sources
- GuangDong Basic and Applied Basic Research Foundation
- National Natural Science Foundation of China
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 39Total Downloads
- Downloads (Last 12 months)39
- Downloads (Last 6 weeks)32
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in