Beyond PageRank: machine learning for static ranking

ABSTRACT

Since 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 independent of the link structure of the Web. We gain a further boost in accuracy by using data on the frequency at which users visit Web pages. We use RankNet, a ranking machine learning algorithm, to combine these and other static features based on anchor text and domain characteristics. The resulting model achieves a static ranking pairwise accuracy of 67.3% (vs. 56.7% for PageRank or 50% for random).

REFERENCES

• 1: Brian Amento , Loren Terveen , Will Hill, Does “authority” mean quality? predicting expert quality ratings of Web documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.296-303, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345603]
• 2: Brian T. Bartell , Garrison W. Cottrell , Richard K. Belew, Automatic combination of multiple ranked retrieval systems, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.173-181, July 03-06, 1994, Dublin, Ireland
• 3: Paolo Boldi , Massimo Santini , Sebastiano Vigna, PageRank as a function of the damping factor, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060827]
• 4: J. Boyan, D. Freitag, and T. Joachims. A machine learning architecture for optimizing web search engines. In AAAI Workshop on Internet Based Information Systems, August 1996.
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 6: Andrei Z. Broder , Ronny Lempel , Farzin Maghoul , Jan Pedersen, Efficient pagerank approximation via graph aggregation, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013537]
• 7: Chris Burges , Tal Shaked , Erin Renshaw , Ari Lazier , Matt Deeds , Nicole Hamilton , Greg Hullender, Learning to rank using gradient descent, Proceedings of the 22nd international conference on Machine learning, p.89-96, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102363]
• 8: David Carmel , Doron Cohen , Ronald Fagin , Eitan Farchi , Michael Herscovici , Yoelle S. Maarek , Aya Soffer, Static index pruning for information retrieval systems, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.43-50, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383958]
• 9: Junghoo Cho , Sourashis Roy, Impact of search engines on page popularity, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988676]
• 10: Junghoo Cho , Sourashis Roy , Robert E. Adams, Page quality: in search of an unbiased web ranking, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066220]
• 11: Nick Craswell , Stephen Robertson , Hugo Zaragoza , Michael Taylor, Relevance weighting for query independent evidence, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076106]
• 12: Nilesh Dalvi , Pedro Domingos , Mausam , Sumit Sanghai , Deepak Verma, Adversarial classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014066]
• 13: O. Dekel, C. Manning, and Y. Singer. Log-linear models for label-ranking. In Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press, 2003.
• 14: Steve Fox , Kuldeep Karnawat , Mark Mydland , Susan Dumais , Thomas White, Evaluating implicit measures to improve web search, ACM Transactions on Information Systems (TOIS), v.23 n.2, p.147-168, April 2005 [doi>10.1145/1059981.1059982]
• 15: T. Haveliwala. Efficient computation of PageRank. Stanford University Technical Report, 1999.
• 16: 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]
• 17: D. Hawking and N. Craswell. Very large scale retrieval and Web search. In D. Harman and E. Voorhees (eds), The TREC Book. MIT Press.
• 18: R. Herbrich, T. Graepel, and K. Obermayer. Support vector learning for ordinal regression. In Proceedings of the Ninth International Conference on Artificial Neural Networks, pp. 97--102. 1999.
• 19: Melody Y. Ivory , Marti A. Hearst, Statistical profiles of highly-rated web sites, Proceedings of the SIGCHI conference on Human factors in computing systems: Changing our world, changing ourselves, April 20-25, 2002, Minneapolis, Minnesota, USA [doi>10.1145/503376.503442]
• 20: Thorsten Joachims, Optimizing search engines using clickthrough data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775067]
• 21: Thorsten Joachims , Laura Granka , Bing Pan , Helene Hembrooke , Geri Gay, Accurately interpreting clickthrough data as implicit feedback, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076063]
• 22: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 23: A. Langville and C. Meyer. Deeper inside PageRank. Internet Mathematics 1(3):335--380, 2004.
• 24: Fabien Mathieu , Mohamed Bouklit, The effect of the back button in a random walk: application for pagerank, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013480]
• 25: Frank McSherry, A uniform approach to accelerated PageRank computation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060829]
• 26: Yasuhiko Minamide, Static approximation of dynamically generated Web pages, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060809]
• 27: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford University, Stanford, CA, 1998.
• 28: Sandeep Pandey , Christopher Olston, User-centric Web crawling, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060805]
• 29: M. Richardson and P. Domingos. The intelligent surfer: probabilistic combination of link and content information in PageRank. In Advances in Neural Information Processing Systems 14, pp. 1441--1448. Cambridge, MA: MIT Press, 2002.
• 30: C. Sherman. Teoma vs. Google, Round 2. Available from World Wide Web (http://dc.internet.com/news/article.php/ 1002061), 2002.
• 31: T. Upstill, N. Craswell, and D. Hawking. Predicting fame and fortune: PageRank or indegree?. In the Eighth Australasian Document Computing Symposium. 2003.
• 32: Trystan Upstill , Nick Craswell , David Hawking, Query-independent evidence in home page finding, ACM Transactions on Information Systems (TOIS), v.21 n.3, p.286-313, July 2003 [doi>10.1145/858476.858479]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
PageRank, RankNet, relevance, search engines, static ranking