skip to main content
10.1145/2939672.2939804acmconferencesArticle/Chapter ViewAbstractPublication PageskddConference Proceedingsconference-collections
research-article
Public Access

Approximate Personalized PageRank on Dynamic Graphs

Published:13 August 2016Publication History

ABSTRACT

We propose and analyze two algorithms for maintaining approximate Personalized PageRank (PPR) vectors on a dynamic graph, where edges are added or deleted. Our algorithms are natural dynamic versions of two known local variations of power iteration. One, Forward Push, propagates probability mass forwards along edges from a source node, while the other, Reverse Push, propagates local changes backwards along edges from a target. In both variations, we maintain an invariant between two vectors, and when an edge is updated, our algorithm first modifies the vectors to restore the invariant, then performs any needed local push operations to restore accuracy.

For Reverse Push, we prove that for an arbitrary directed graph in a random edge model, or for an arbitrary undirected graph, given a uniformly random target node t, the cost to maintain a PPR vector to t of additive error ε as k edges are updated is O(k + d/ε, where d is the average degree of the graph. This is O(1) work per update, plus the cost of computing a reverse vector once on a static graph. For Forward Push, we show that on an arbitrary undirected graph, given a uniformly random start node s, the cost to maintain a PPR vector from s of degree-normalized error ε as k edges are updated is O(k + 1/ε, which is again O(1) per update plus the cost of computing a PPR vector once on a static graph.

Skip Supplemental Material Section

Supplemental Material

kdd2016_zhang_page_rankon_01-acm.mp4

References

  1. Reid Andersen, Christian Borgs, Jennifer Chayes, John Hopcraft, Vahab S Mirrokni, and Shang-Hua Teng. Local computation of pagerank contributions. In Algorithms and Models for the Web-Graph, pages 150--165. Springer, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In Foundations of Computer Science, 2006. FOCS'06. 47th Annual IEEE Symposium on, pages 475--486. IEEE, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, and Natalia Osipova. Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM Journal on Numerical Analysis, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Lars Backstrom and Jure Leskovec. Supervised random walks: predicting and recommending links in social networks. In Proceedings of the fourth ACM international conference on Web search and data mining. ACM, 2011. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. Bahman Bahmani, Abdur Chowdhury, and Ashish Goel. Fast incremental and personalized pagerank. Proceedings of the VLDB Endowment, 4(3):173--184, 2010. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. Shumeet Baluja, Rohan Seth, D Sivakumar, Yushi Jing, Jay Yagnik, Shankar Kumar, Deepak Ravichandran, and Mohamed Aly. Video suggestion and discovery for youtube: taking random walks through the view graph. In Proceedings of the 17th international conference on World Wide Web, pages 895--904. ACM, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. Pavel Berkhin. Bookmark-coloring algorithm for personalized pagerank computing. Internet Mathematics, 3(1):41--62, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  8. Soumen Chakrabarti. Dynamic personalized pagerank in entity-relation graphs. In Proceedings of the 16th international conference on World Wide Web, pages 571--580. ACM, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  9. Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics, 2005.Google ScholarGoogle ScholarCross RefCross Ref
  10. David F Gleich. Pagerank beyond the web. SIAM Review, 57(3):321--363, 2015.Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. Taher H Haveliwala. Topic-sensitive pagerank: A context-sensitive ranking algorithm for web search. Knowledge and Data Engineering, IEEE Transactions on, 15(4):784--796, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. Glen Jeh and Jennifer Widom. Scaling personalized web search. In Proceedings of the 12th international conference on World Wide Web. ACM, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. Peter Lofgren. On the complexity of the monte carlo method for incremental pagerank. Information Processing Letters, 114(3):104--106, 2014. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Peter Lofgren. Efficient algorithms for personalized pagerank. arXiv preprint arXiv:1512.04633, 2015.Google ScholarGoogle Scholar
  16. Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Bidirectional pagerank estimation: From average-case to worst-case. In Algorithms and Models for the Web Graph, pages 164--176. Springer, 2015. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. Peter Lofgren, Siddhartha Banerjee, and Ashish Goel. Personalized pagerank estimation and search: A bidirectional approach. In WSDM, 2016. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. Peter A Lofgren, Siddhartha Banerjee, Ashish Goel, and C Seshadhri. Fast-ppr: Scaling personalized pagerank estimation for large graphs. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1436--1445. ACM, 2014. Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. Ioannis Mitliagkas, Michael Borokhovich, Alexandros G Dimakis, and Constantine Caramanis. Frogwild!: fast pagerank approximations on graph engines. Proceedings of the VLDB Endowment, 8(8):874--885, 2015. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. Efficient pagerank tracking in evolving networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 875--884. ACM, 2015. Google ScholarGoogle ScholarDigital LibraryDigital Library
  21. Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: bringing order to the web. 1999.Google ScholarGoogle Scholar
  22. Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics, page 3. ACM, 2012. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Approximate Personalized PageRank on Dynamic Graphs

    Recommendations

    Comments

    Login options

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

    Sign in
    • Published in

      cover image ACM Conferences
      KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
      August 2016
      2176 pages
      ISBN:9781450342322
      DOI:10.1145/2939672

      Copyright © 2016 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]

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      • Published: 13 August 2016

      Permissions

      Request permissions about this article.

      Request Permissions

      Check for updates

      Qualifiers

      • research-article

      Acceptance Rates

      KDD '16 Paper Acceptance Rate66of1,115submissions,6%Overall Acceptance Rate1,133of8,635submissions,13%

      Upcoming Conference

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader