Web projections: learning from contextual subgraphs of the web

ABSTRACT

Graphical relationships among Web pages have been exploited inmethods for ranking search results. To date, specific graphicalproperties have been used in these analyses. We introduce a WebProjection methodology that generalizes prior efforts of graphicalrelationships of the web in several ways. With the approach, wecreate subgraphs by projecting sets of pages and domains onto thelarger web graph, and then use machine learning to constructpredictive models that consider graphical properties as evidence. Wedescribe the method and then present experiments that illustrate theconstruction of predictive models of search result quality and userquery reformulation.

REFERENCES

• 1: 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]
• 2: 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
• 3: D. M. Chickering. The winmine toolkit. Technical Report MSR-TR-2002-103, Microsoft, 2002.
• 4: David Maxwell Chickering, Optimal structure identification with greedy search, The Journal of Machine Learning Research, 3, p.507-554, 3/1/2003
• 5: Steve Cronen-Townsend , Yun Zhou , W. Bruce Croft, Predicting query performance, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564429]
• 6: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 7: E. Garfield. Citation analysis as a tool in journal evaluation. Science, 178(60):471--479, November 1972.
• 8: 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]
• 9: 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]
• 10: Rosie Jones , Benjamin Rey , Omid Madani , Wiley Greiner, Generating query substitutions, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135835]
• 11: R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85--103. 1972.
• 12: H. Kashima, K. Tsuda, and A. Inokuchi. Marginalized kernels between labeled graphs. In ICML '03, 2003.
• 13: 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]
• 14: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 15: T. Kudo, E. Maeda, and Y. Matsumoto. An application of boosting to graph classification. In NIPS '05. 2005.
• 16: Tessa Lau , Eric Horvitz, Patterns of search: analyzing and modeling Web query refinement, Proceedings of the seventh international conference on User modeling, p.119-128, June 1999, Banff, Canada
• 17: J. Leskovec, N. Milic-Frayling, and M. Grobelnik. Impact of linguistic analysis on the semantic graph coverage and learning of document extracts. In AAAI '05, 2005.
• 18: Einat Minkov , William W. Cohen , Andrew Y. Ng, Contextual search and name disambiguation in email using graphs, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148179]
• 19: Lan Nie , Brian D. Davison , Xiaoguang Qi, Topical link analysis for web search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148189]
• 20: Zaiqing Nie , Yuanzhi Zhang , Ji-Rong Wen , Wei-Ying Ma, Object-level ranking: bringing order to Web objects, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060828]
• 21: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Dig. Lib. Tech. Proj., 1998.
• 22: G. Pinski and F. Narin. Citation influence for journal aggregates of scientific publications: Theory, with application to the literature of physics. Information Processing and Management, 12:297--312, 1976.
• 23: Filip Radlinski , Susan Dumais, Improving personalized web search using result diversification, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148320]
• 24: M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in pagerank. In NIPS '02, 2002.
• 25: Sergei Vassilvitskii , Eric Brill, Using web-graph distance for relevance feedback in web search, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148199]
• 26: S. Wasserman, K. Faust, and D. Iacobucci. Social Network Analysis: Methods and Applications. Cambridge University Press, 1994.
• 27: Baoning Wu , Vinay Goel , Brian D. Davison, Topical TrustRank: using topicality to combat web spam, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135792]
• 28: Wensi Xi , Benyu Zhang , Zheng Chen , Yizhou Lu , Shuicheng Yan , Wei-Ying Ma , Edward Allan Fox, Link fusion: a unified link analysis framework for multi-type interrelated data objects, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988715]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

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

General Terms:
Algorithms, Experimentation

Keywords:
contextual subgraph, query reformulation, web graph, web projection, web search