Extrapolation methods for accelerating PageRank computations

ABSTRACT

We present a novel algorithm for the fast computation of PageRank, a hyperlink-based estimate of the ''importance'' of Web pages. The original PageRank algorithm uses the Power Method to compute successive iterates that converge to the principal eigenvector of the Markov matrix representing the Web link graph. The algorithm presented here, called Quadratic Extrapolation, accelerates the convergence of the Power Method by periodically subtracting off estimates of the nonprincipal eigenvectors from the current iterate of the Power Method. In Quadratic Extrapolation, we take advantage of the fact that the first eigenvalue of a Markov matrix is known to be 1 to compute the nonprincipal eigenvectors using successive iterates of the Power Method. Empirically, we show that using Quadratic Extrapolation speeds up PageRank computation by 25-300% on a Web graph of 80 million nodes, with minimal overhead. Our contribution is useful to the PageRank community and the numerical linear algebra community in general, as it is a fast method for determining the dominant eigenvector of a matrix that is too large for standard fast methods to be practical.

REFERENCES

• 1: A. Aitken. On Bernoulli's numerical solution of algebraic equations. Proc. Roy. Soc. Edinburgh, 46:289--305, 1926.
• 2: A. Arasu, J. Novak, A. Tomkins, and J. Tomlin. PageRank computation and the structure of the web: Experiments and algorithms. In Proceedings of the Eleventh International World Wide Web Conference, Poster Track, 2002.
• 3: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 4: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 5: Soumen Chakrabarti , Mukul M. Joshi , Kunal Punera , David M. Pennock, The structure of broad topics on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511480]
• 6: Soumen Chakrabarti , Martin van den Berg , Byron Dom, Focused crawling: a new approach to topic-specific Web resource discovery, Proceeding of the eighth international conference on World Wide Web, p.1623-1640, May 1999, Toronto, Canada
• 7: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 9: G. Grimmett and D. Stirzaker. Probability and Random Processes. Oxford University Press, 1989.
• 10: T. H. Haveliwala. Efficient computation of PageRank. Stanford University Technical Report, 1999.
• 11: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 12: T. H. Haveliwala and S. D. Kamvar. The second eigenvalue of the Google matrix. Stanford University Technical Report, 2003.
• 13: Jun Hirai , Sriram Raghavan , Hector Garcia-Molina , Andreas Paepcke, WebBase: a repository of Web pages, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.277-293, June 2000, Amsterdam, The Netherlands
• 14: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 16: J. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. The web as a graph: Measurements, models, and methods. In Proceedings of the International Conference on Combinatorics and Computing, 1999.
• 17: U. Krieger. Numerical solution of large finite markov chains by algebraic multigrid techniques. In Proceedings of the 2nd International Workshop on the Numerical Solution of Markov Chains, 1995.
• 18: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Stanford Digital Libraries Working Paper, 1998.
• 19: Davood Rafiei , Alberto O. Mendelzon, What is this page known for? Computing Web page reputations, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.823-835, June 2000, Amsterdam, The Netherlands
• 20: M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in pagerank. In Advances in Neural Information Processing Systems, volume 14. MIT Press, Cambridge, MA, 2002.
• 21: L. N. Trefethen and D. Bau. Numerical Linear Algebra. SIAM Press, Philadelphia, 1997.
• 22: P. Wynn. On the convergence and stability of the epsilon algorithm. SIAM Journal of Numerical Analysis, 33:91--122, 1966.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering; Search process

General Terms:
Algorithms, Experimentation

Keywords:
PageRank, eigenvector computation, link analysis