TopPPR: Top-k personalized pagerank queries with precision guarantees on large graphs

Zhewei Wei, Xiaodong He, Xiaokui Xiao, Sibo Wang, Shuo Shang, Ji Rong Wen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

58 Scopus citations


Personalized PageRank (PPR) is a classic metric that measures the relevance of graph nodes with respect to a source node. Given a graph G, a source node s, and a parameter k, a top-k PPR query returns a set of k nodes with the highest PPR values with respect to s. This type of queries serves as an important building block for numerous applications in web search and social networks, such as Twitter's Who-To-Follow recommendation service. Existing techniques for top-k PPR, however, suffer from two major deficiencies. First, they either incur prohibitive space and time overheads on large graphs, or fail to provide any guarantee on the precision of top-k results (i.e., the results returned might miss a number of actual top-k answers). Second, most of them require significant pre-computation on the input graph G, which renders them unsuitable for graphs with frequent updates (e.g., Twitter's social graph). To address the deficiencies of existing solutions, we propose TopPPR, an algorithm for top-k PPR queries that ensure at least ? precision (i.e., at least ? fraction of the actual top-k results are returned) with at least 1-1/n probability, where ? ? (0, 1] is a userspecified parameter and n is the number of nodes in G. In addition, TopPPR offers non-trivial guarantees on query time in terms of ?, and it can easily handle dynamic graphs as it does not require any preprocessing. We experimentally evaluate TopPPR using a variety of benchmark datasets, and demonstrate that TopPPR outperforms the state-of-the-art solutions in terms of both efficiency and precision, even when we set ? = 1 (i.e., when TopPPR returns the exacttop-k results). Notably, on a billion-edge Twitter graph, TopPPR only requires 15 seconds to answer a top-500 PPR query with ? = 1.

Original languageEnglish (US)
Title of host publicationSIGMOD 2018 - Proceedings of the 2018 International Conference on Management of Data
EditorsGautam Das, Christopher Jermaine, Ahmed Eldawy, Philip Bernstein
PublisherAssociation for Computing Machinery (ACM)
Number of pages16
ISBN (Electronic)9781450317436
StatePublished - May 27 2018
Event44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018 - Houston, United States
Duration: Jun 10 2018Jun 15 2018

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078


Conference44th ACM SIGMOD International Conference on Management of Data, SIGMOD 2018
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© 2018 Association for Computing Machinery.


  • Personalized pagerank
  • Top-k queries

ASJC Scopus subject areas

  • Software
  • Information Systems


Dive into the research topics of 'TopPPR: Top-k personalized pagerank queries with precision guarantees on large graphs'. Together they form a unique fingerprint.

Cite this