research-article

Free access

FAST-PPR: scaling personalized pagerank estimation for large graphs

Authors:

Peter A. Lofgren,

Siddhartha Banerjee,

C. SeshadhriAuthors Info & Claims

KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 1436 - 1445

https://doi.org/10.1145/2623330.2623745

Published: 24 August 2014 Publication History

Abstract

We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s(t) from s to t, guaranteeing that the relative error is small as long π_s(t) > δ. Existing algorithms for this problem have a running-time of Ω(1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O(√d/δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O(1/n) (where n is the number of nodes) for applications. We also complement the algorithm with an Ω(1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved.

We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs.

Supplementary Material

MP4 File (p1436-sidebyside.mp4)

Download
237.18 MB

References

[1]

L. Page, S. Brin, R. Motwani, and T. Winograd, "The pagerank citation ranking: bringing order to the web.," 1999.

[2]

G. Jeh and J. Widom, "Scaling personalized web search," in Proceedings of the 12th international conference on World Wide Web, ACM, 2003.

Digital Library

[3]

P. Yin, W.-C. Lee, and K. C. Lee, "On top-k social web search," in Proceedings of the 19th ACM international conference on Information and knowledge management, ACM, 2010.

Digital Library

[4]

S. A. Yahia, M. Benedikt, L. V. Lakshmanan, and J. Stoyanovich, "Effifficient network aware search in collaborative tagging sites," Proceedings of the VLDB Endowment, 2008.

Digital Library

[5]

M. V. Vieira, B. M. Fonseca, R. Damazio, P. B. Golgher, D. d. C. Reis, and B. Ribeiro-Neto, "Efficient search ranking in social networks," in Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, ACM, 2007.

Digital Library

[6]

D. Horowitz and S. D. Kamvar, "The anatomy of a large-scale social search engine," in Proceedings of the 19th international conference on World wide web, ACM, 2010.

Digital Library

[7]

L. Backstrom and J. Leskovec, "Supervised random walks: predicting and recommending links in socialnetworks," in Proceedings of the fourth ACM international conference on Web searchand data mining, ACM, 2011.

Digital Library

[8]

P. Gupta, A. Goel, J. Lin, A. Sharma, D. Wang, and R. Zadeh, "Wtf: The who to follow service at twitter," in Proceedings of the 22nd international conference on World Wide Web, International World Wide Web Conferences Steering Committee, 2013.

Digital Library

[9]

R. Andersen, F. Chung, and K. Lang, "Local graph partitioning using pagerank vectors," in Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, 2006.

Digital Library

[10]

J. Yang and J. Leskovec, "Defining and evaluating network communities based on ground-truth," in Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, p. 3, ACM, 2012.

Digital Library

[11]

H. Tong, C. Faloutsos, and J.-Y. Pan, "Fast random walk with restart and its applications," 2006.

[12]

T. Sarls, óA. A. Benczúr, K. Csalogány, D. Fogaras, and B. Rácz, "To randomize or not to randomize: space optimal summaries for hyperlink analysis," In Proceedings of the 15th international conference on World Wide Web, ACM, 2006.

Digital Library

[13]

K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova,"Monte carlo methods in pagerank computation: When one iteration is sufficient," SIAM Journal on Numerical Analysis, 2007.

Digital Library

[14]

R. Andersen, C. Borgs, J. Chayes, J. Hopcraft, V. S. Mirrokni, and S.-H. Teng, "Local computation of pagerank contributions," in Algorithms and Models for the Web-Graph, Springer, 2007.

Digital Library

[15]

B. Bahmani, A. Chowdhury, and A. Goel, "Fast incremental and personalized pagerank," Proceedings of the VLDB Endowment, 2010.

Digital Library

[16]

C. Borgs, M. Brautbar, J. Chayes, and S.-H. Teng, "Multi-scale matrix sampling and sublinear-time pagerank computation," Internet Mathematics, 2013.

[17]

A. D. Sarma, A. R. Molla, G. Pandurangan, and E. Upfal, "Fast distributed pagerank computation," Distributed Computing and Networking, 2013.

[18]

P. Lofgren, S. Banerjee, A. Goel, and C. Seshadhri, "Fast-ppr: Scaling personalized pagerank estimation for large graphs," tech. rep., Stanford University, 2014. arXiv preprint arXiv:1404.3181.

Digital Library

[19]

"Laboratory for web algorithmics." http://law.di.unimi.it/datasets.php. Accessed: 2014-02--11.

[20]

D. Fogaras, B. Rácz, K. Csalogány, and T. Sarlós, "Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments," Internet Mathematics, 2005.

[21]

P. Lofgren and A. Goel, "Personalized pagerank to a target node," arXiv preprint arXiv:1304.4658, 2013.

[22]

O. Goldreich and D. Ron, "On testing expansion in bounded-degree graphs," in Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, Springer, 2011.

Digital Library

[23]

S. Kale, Y. Peres, and C. Seshadhri, "Noise tolerance of expanders and sublinear expander reconstruction," in Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, IEEE, 2008.

Digital Library

[24]

D. Dubhashi and A. Panconesi, Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009.

Digital Library

[25]

O. Goldreich and D. Ron, "Property testing in bounded degreegraphs," Algorithmica, 2002. Conference version in STOC 1997.

Digital Library

[26]

P. Boldi, M. Rosa, M. Santini, and S. Vigna, "Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks," in Proceedings of the 20th international conference on World Wide Web, ACM Press, 2011.

Digital Library

[27]

P. Boldi, M. Santini, and S. Vigna, "A large time-aware graph," SIGIR Forum, vol. 42, no. 2, 2008.

Digital Library

[28]

L. Takac and M. Zabovsky, "Data analysis in public social networks," in International. Scientific Conf. & Workshop Present Day Trends of Innovations, 2012.

[29]

A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee, "Measurement and Analysis of Online Social Networks," in Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC'07), (San Diego, CA), October 2007.

Digital Library

[30]

"Stanford network analysis platform (snap)." http://http://snap.stanford.edu/. Accessed: 2014-02-11.

Cited By

Liu HLuo S(2024)BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRankProceedings of the VLDB Endowment10.14778/3665844.366585517:9(2255-2268)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665855
Khan MMello GHabib LEngelstad PYazidi A(2024)HITS-based Propagation Paradigm for Graph Neural NetworksACM Transactions on Knowledge Discovery from Data10.1145/363877918:4(1-23)Online publication date: 13-Feb-2024
https://dl.acm.org/doi/10.1145/3638779
Wang HBaeza-Yates RBonchi F(2024)Revisiting Local PageRank Estimation on Undirected Graphs: Simple and OptimalProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671820(3036-3044)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671820
Show More Cited By

Index Terms

FAST-PPR: scaling personalized pagerank estimation for large graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

PPR-partitioning: a distributed graph partitioning algorithm based on the personalized PageRank vectors in vertex-centric systems
Abstract
Relations among data items can be modeled with graphs in most of big data sets such as social networks’ data. This modeling creates big graphs with many vertices and edges. Balanced k-way graph partitioning is a common problem with big graphs. It ...
Graph-based collaborative ranking

GRank is a novel framework, designed for recommendation based on rank data.GRank handles the sparsity problem of neighbor-based collaborative ranking.GRank uses the novel TPG graph structure to model users' choice context.GRank directly ranks itemsfor a ...
A Case Study of Collaboration and Reputation in Social Web Search

Although collaborative searching is not supported by mainstream search engines, recent research has highlighted the inherently collaborative nature of many Web search tasks. In this article, we describe HeyStaks, a collaborative Web search framework ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '14: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2014

2028 pages

ISBN:9781450329569

DOI:10.1145/2623330

General Chairs:
Sofus Macskassy
Facebook
,
Claudia Perlich
Dstillery
,
Program Chairs:
Jure Leskovec
Stanford University
,
Wei Wang
UCLA
,
Rayid Ghani
University of Chicago

Copyright © 2014 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].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 August 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

KDD '14

Sponsor:

KDD '14: The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 24 - 27, 2014

New York, New York, USA

Acceptance Rates

KDD '14 Paper Acceptance Rate 151 of 1,036 submissions, 15%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

86
Total Citations
View Citations
1,665
Total Downloads

Downloads (Last 12 months)168
Downloads (Last 6 weeks)15

Reflects downloads up to 12 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu HLuo S(2024)BIRD: Efficient Approximation of Bidirectional Hidden Personalized PageRankProceedings of the VLDB Endowment10.14778/3665844.366585517:9(2255-2268)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665855
Khan MMello GHabib LEngelstad PYazidi A(2024)HITS-based Propagation Paradigm for Graph Neural NetworksACM Transactions on Knowledge Discovery from Data10.1145/363877918:4(1-23)Online publication date: 13-Feb-2024
https://dl.acm.org/doi/10.1145/3638779
Wang HBaeza-Yates RBonchi F(2024)Revisiting Local PageRank Estimation on Undirected Graphs: Simple and OptimalProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3637528.3671820(3036-3044)Online publication date: 25-Aug-2024
https://dl.acm.org/doi/10.1145/3637528.3671820
Wang HWei ZWen JYang MMohar BShinkar IO'Donnell R(2024)Revisiting Local Computation of PageRank: Simple and OptimalProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649661(911-922)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649661
Neumann SDong YPeng PChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Sublinear-Time Opinion Estimation in the Friedkin--Johnsen ModelProceedings of the ACM Web Conference 202410.1145/3589334.3645572(2563-2571)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645572
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
Guo QLin DWang SWong RLin W(2024)Efficient Algorithms for Group Hitting Probability Queries on Large GraphsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3349164(1-13)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3349164
Zhu ZLuo SLin WWang SMo DLi C(2024)Personalized PageRanks over Dynamic Graphs - The Case for Optimizing Quality of Service2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00038(409-422)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00038
Gong Y(2023)HedgeRank: Heterogeneity-Aware, Energy-Efficient Partitioning of Personalized PageRank at the EdgeMicromachines10.3390/mi1409171414:9(1714)Online publication date: 31-Aug-2023
https://doi.org/10.3390/mi14091714
Wang HWei Z(2023)Estimating Single-Node PageRank in Õ (min{d, √m}) TimeProceedings of the VLDB Endowment10.14778/3611479.361150016:11(2949-2961)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611500
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents