Using the wisdom of the crowds for keyword generation

ABSTRACT

In the sponsored search model, search engines are paid by businesses that are interested in displaying ads for their site alongside the search results. Businesses bid for keywords, and their ad is displayed when the keyword is queried to the search engine. An important problem in this process is 'keyword generation': given a business that is interested in launching a campaign, suggest keywords that are related to that campaign. We address this problem by making use of the query logs of the search engine. We identify queries related to a campaign by exploiting the associations between queries and URLs as they are captured by the user's clicks. These queries form good keyword suggestions since they capture the "wisdom of the crowd" as to what is related to a site. We formulate the problem as a semi-supervised learning problem, and propose algorithms within the Markov Random Field model. We perform experiments with real query logs, and we demonstrate that our algorithms scale to large query logs and produce meaningful results.

REFERENCES

• 1: Vibhanshu Abhishek , Kartik Hosanagar, Keyword generation for search engine advertising using semantic similarity between terms, Proceedings of the ninth international conference on Electronic commerce, August 19-22, 2007, Minneapolis, MN, USA [doi>10.1145/1282100.1282119]
• 2: Reid Andersen , Kevin J. Lang, Communities from seed sets, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135814]
• 3: 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]
• 4: K. Bartz, V. Murthi, and S. Sebastian. Logistic regression and collaborative filtering for sponsored search term recommendation. Second Workshop on Sponsored Search Auctions, 2006.
• 5: 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]
• 6: Andrei Z. Broder , Marcus Fontoura , Evgeniy Gabrilovich , Amruta Joshi , Vanja Josifovski , Tong Zhang, Robust classification of rare queries using web knowledge, 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.1277783]
• 7: Olivier Chapelle, Bernhard Scholkopf, and Alexander Zien. Semi-Supervised Learning. The MIT Press, 2006.
• 8: Nick Craswell , Martin Szummer, Random walks on the click graph, 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.1277784]
• 9: P. Doyle and L. Snell. Random Walks and Electrical Networks. Mathematical Association of America, 1984.
• 10: Eibe Frank , Gordon W. Paynter , Ian H. Witten , Carl Gutwin , Craig G. Nevill-Manning, Domain-Specific Keyphrase Extraction, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.668-673, July 31-August 06, 1999
• 11: Zoltán Gyöngyi , Hector Garcia-Molina , Jan Pedersen, Combating web spam with trustrank, Proceedings of the Thirtieth international conference on Very large data bases, p.576-587, August 31-September 03, 2004, Toronto, Canada
• 12: Anette Hulth, Improved automatic keyword extraction given more linguistic knowledge, Proceedings of the 2003 conference on Empirical methods in natural language processing, p.216-223, July 11, 2003 [doi>10.3115/1119355.1119383]
• 13: Michael I. Jordan , Zoubin Ghahramani , Tommi S. Jaakkola , Lawrence K. Saul, An introduction to variational methods for graphical models, Proceedings of the NATO Advanced Study Institute on Learning in graphical models, p.105-161, March 1998, Erice, Italy
• 14: Amruta Joshi , Rajeev Motwani, Keyword Generation for Search Engine Advertising, Proceedings of the Sixth IEEE International Conference on Data Mining - Workshops, p.490-496, December 18-22, 2006 [doi>10.1109/ICDMW.2006.104]
• 15: D. Kelleher and S. Luz. Automatic hypertext keyphrase extraction. IJCAI, pages 1608--1609, 2005.
• 16: 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]
• 17: S. Z. Li, Markov random field modeling in computer vision, Springer-Verlag, London, 1995
• 18: J. Rocchio. The SMART Retrieval System: Experiments in Automatic Document Processing, chapter Relevance feedback in Information Retrieval, pages 313--323. Prentice Hall, 1971.
• 19: Dou Shen , Rong Pan , Jian-Tao Sun , Jeffrey Junfeng Pan , Kangheng Wu , Jie Yin , Qiang Yang, Q²C@UST: our winning solution to query classification in KDDCUP 2005, ACM SIGKDD Explorations Newsletter, v.7 n.2, p.100-110, December 2005 [doi>10.1145/1117454.1117467]
• 20: Peter D. Turney, Learning Algorithms for Keyphrase Extraction, Information Retrieval, v.2 n.4, p.303-336, May 2000 [doi>10.1023/A:1009976227802]
• 21: P. Turney. Coherent keyphrase extraction via web mining. IJCAI, pages 434--439, 2003.
• 22: Ji-Rong Wen , Jian-Yun Nie , Hong-Jiang Zhang, Clustering user queries of a search engine, Proceedings of the 10th international conference on World Wide Web, p.162-168, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371974]
• 23: Gui-Rong Xue , Yong Yu , Dou Shen , Qiang Yang , Hua-Jun Zeng , Zheng Chen, Reinforcing Web-object Categorization Through Interrelationships, Data Mining and Knowledge Discovery, v.12 n.2-3, p.229-248, May 2006 [doi>10.1007/s10618-005-0015-5]
• 24: Gui-Rong Xue , Hua-Jun Zeng , Zheng Chen , Yong Yu , Wei-Ying Ma , WenSi Xi , WeiGuo Fan, Optimizing web search using web click-through data, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031192]
• 25: Yiming Yang, An Evaluation of Statistical Approaches to Text Categorization, Information Retrieval, v.1 n.1-2, p.69-90, 1999 [doi>10.1023/A:1009982220290]
• 26: Wen-tau Yih , Joshua Goodman , Vitor R. Carvalho, Finding advertising keywords on web pages, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135813]
• 27: X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. ICML, pages 912--919, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

Additional Classification:
  J. Computer Applications
  J.0 GENERAL

General Terms:
Algorithms

Keywords:
absorbing random walks, keyword generation, markov random fields, query click logs, sponsored search