Learning latent semantic relations from clickthrough data for query suggestion

ABSTRACT

For a given query raised by a specific user, the Query Suggestion technique aims to recommend relevant queries which potentially suit the information needs of that user. Due to the complexity of the Web structure and the ambiguity of users' inputs, most of the suggestion algorithms suffer from the problem of poor recommendation accuracy. In this paper, aiming at providing semantically relevant queries for users, we develop a novel, effective and efficient two-level query suggestion model by mining clickthrough data, in the form of two bipartite graphs (user-query and query-URL bipartite graphs) extracted from the clickthrough data. Based on this, we first propose a joint matrix factorization method which utilizes two bipartite graphs to learn the low-rank query latent feature space, and then build a query similarity graph based on the features. After that, we design an online ranking algorithm to propagate similarities on the query similarity graph, and finally recommend latent semantically relevant queries to users. Experimental analysis on the clickthrough data of a commercial search engine shows the effectiveness and the efficiency of our method.

REFERENCES

• 1: Eugene Agichtein , Eric Brill , Susan Dumais, Improving web search ranking by incorporating user behavior information, 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.1148177]
• 2: Ricardo Baeza-Yates , Alessandro Tiberi, Extracting semantic relations from query logs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281204]
• 3: R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In EDBT Workshops, pages 588--596, 2004.
• 4: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 5: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 6: Paul - Alexandru Chirita , Claudiu S. Firan , Wolfgang Nejdl, Personalized query expansion for the web, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277746]
• 7: Hang Cui , Ji-Rong Wen , Jian-Yun Nie , Wei-Ying Ma, Query Expansion by Mining User Logs, IEEE Transactions on Knowledge and Data Engineering, v.15 n.4, p.829-839, July 2003 [doi>10.1109/TKDE.2003.1209002]
• 8: G. Dupret and M. Mendoza. Automatic query recommendation using click-through data. In IFIP PPAI, pages 303--312, 2006.
• 9: Nadav Eiron , Kevin S. McCurley , John A. Tomlin, Ranking the web frontier, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988714]
• 10: Wei Gao , Cheng Niu , Jian-Yun Nie , Ming Zhou , Jian Hu , Kam-Fai Wong , Hsiao-Wuen Hon, Cross-lingual query suggestion using query logs of different languages, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277821]
• 11: D. Gleich and L. Zhukov. Svd subspace projections for term suggestion ranking and clustering. In Technical Report of Yahoo! Research Labs, 2004.
• 12: Bernard J. Jansen , Amanda Spink , Judy Bateman , Tefko Saracevic, Real life information retrieval: a study of user queries on the Web, ACM SIGIR Forum, v.32 n.1, p.5-17, Spring 1998 [doi>10.1145/281250.281253]
• 13: Glen Jeh , Jennifer Widom, SimRank: a measure of structural-context similarity, 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.775126]
• 14: Jiwoon Jeon , W. Bruce Croft , Joon Ho Lee, Finding similar questions in large question and answer archives, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany [doi>10.1145/1099554.1099572]
• 15: 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]
• 16: Thorsten Joachims , Filip Radlinski, Search Engines that Learn from Implicit Feedback, Computer, v.40 n.8, p.34-40, August 2007 [doi>10.1109/MC.2007.289]
• 17: 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]
• 18: 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
• 19: Reiner Kraft , Jason Zien, Mining anchor text for query refinement, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988763]
• 20: John Lafferty , Guy Lebanon, Diffusion Kernels on Statistical Manifolds, The Journal of Machine Learning Research, 6, p.129-163, 12/1/2005
• 21: L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. In Technical Report Paper SIDL-WP-1999-0120 (version of 11/11/1999), 1999.
• 22: M. Pasca and B. V. Durme. What you seek is what you get: Extraction of class attributes from query logs. In IJCAI '07: Proceedings of International Joint Conferences on Artificial Intelligence, pages 2832--2837, 2007.
• 23: Greg Pass , Abdur Chowdhury , Cayley Torgeson, A picture of search, Proceedings of the 1st international conference on Scalable information systems, p.1-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146848]
• 24: D. Shen, M. Qin, W. Chen, Q. Yang, and Z. Chen. Mining web query hierarchies from clickthrough data. In AAAI '07: Proceedings of the 22th Conference on Artificial Intelligence, pages 341--346, 2007.
• 25: Craig Silverstein , Hannes Marais , Monika Henzinger , Michael Moricz, Analysis of a very large web search engine query log, ACM SIGIR Forum, v.33 n.1, p.6-12, Fall 1999 [doi>10.1145/331403.331405]
• 26: Jian-Tao Sun , Dou Shen , Hua-Jun Zeng , Qiang Yang , Yuchang Lu , Zheng Chen, Web-page summarization using clickthrough data, 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.1076070]
• 27: Martin Theobald , Ralf Schenkel , Gerhard Weikum, Efficient and self-tuning incremental query expansion for top-k query processing, 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.1076077]
• 28: Bienvenido Vélez , Ron Weiss , Mark A. Sheldon , David K. Gifford, Fast and effective query refinement, ACM SIGIR Forum, v.31 n.SI, p.6-15
• 29: Xuanhui Wang , ChengXiang Zhai, Learn from web search logs to organize search results, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277759]
• 30: Query clustering using user logs, ACM Transactions on Information Systems (TOIS), v.20 n.1, p.59-81, January 2002 [doi>10.1145/503104.503108]
• 31: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]
• 32: Haixuan Yang , Irwin King , Michael R. Lyu, DiffusionRank: a possible penicillin for web spamming, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277815]
• 33: Ding Zhou , Shenghuo Zhu , Kai Yu , Xiaodan Song , Belle L. Tseng , Hongyuan Zha , C. Lee Giles, Learning multiple graphs for document recommendations, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367517]
• 34: Shenghuo Zhu , Kai Yu , Yun Chi , Yihong Gong, Combining content and link for classification using matrix factorization, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277825]

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, Performance

Keywords:
clickthrough data, matrix factorization, query suggestion, similarity propagation, web search