Personalized tag recommendation using graph-based ranking on multi-type interrelated objects

ABSTRACT

Social tagging is becoming increasingly popular in many Web 2.0 applications where users can annotate resources (e.g. Web pages) with arbitrary keywords (i.e. tags). A tag recommendation module can assist users in tagging process by suggesting relevant tags to them. It can also be directly used to expand the set of tags annotating a resource. The benefits are twofold: improving user experience and enriching the index of resources. However, the former one is not emphasized in previous studies, though a lot of work has reported that different users may describe the same concept in different ways. We address the problem of personalized tag recommendation for text documents. In particular, we model personalized tag recommendation as a "query and ranking" problem and propose a novel graph-based ranking algorithm for interrelated multi-type objects. When a user issues a tagging request, both the document and the user are treated as a part of the query. Tags are then ranked by our graph-based ranking algorithm which takes into consideration both relevance to the document and preference of the user. Finally, the top ranked tags are presented to the user as suggestions. Experiments on a large-scale tagging data set collected from Del.icio.us have demonstrated that our proposed algorithm significantly outperforms algorithms which fail to consider the diversity of different users' interests.

REFERENCES

• 1: Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005 [doi>10.1109/TKDE.2005.99]
• 2: Shivani Agarwal, Ranking on graph data, Proceedings of the 23rd international conference on Machine learning, p.25-32, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143848]
• 3: D. Cai, X. He, and J. Han. Spectral regression for efficient regularized subspace learning. In Proc. Int. Conf. Computer Vision (ICCV'07), 2007.
• 4: Deng Cai , Xiaofei He , Jiawei Han, SRDA: An Efficient Algorithm for Large-Scale Discriminant Analysis, IEEE Transactions on Knowledge and Data Engineering, v.20 n.1, p.1-12, January 2008 [doi>10.1109/TKDE.2007.190669]
• 5: Paul - Alexandru Chirita , Stefania Costache , Wolfgang Nejdl , Siegfried Handschuh, P-TAG: large scale automatic generation of personalized annotation tags for the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242686]
• 6: CiteULike. http://www.citeulike.org.
• 7: Del.icio.us. http://delicious.com.
• 8: Flickr. http://www.flickr.com.
• 9: Nikhil Garg , Ingmar Weber, Personalized, interactive tag recommendation for flickr, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland [doi>10.1145/1454008.1454020]
• 10: Scott A. Golder , Bernardo A. Huberman, Usage patterns of collaborative tagging systems, Journal of Information Science, v.32 n.2, p.198-208, April 2006 [doi>10.1177/0165551506062337]
• 11: Harry Halpin , Valentin Robu , Hana Shepherd, The complex dynamics of collaborative tagging, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242602]
• 12: X. He and P. Niyogi. Locality preserving projections. In Advances in Neural Information Processing Systems 16. MIT Press, Cambridge, MA, 2003.
• 13: Xiaofei He , Shuicheng Yan , Yuxiao Hu , Partha Niyogi , Hong-Jiang Zhang, Face Recognition Using Laplacianfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.328-340, March 2005 [doi>10.1109/TPAMI.2005.55]
• 14: 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
• 15: Xin Li , Lei Guo , Yihong Eric Zhao, Tag-based social interest discovery, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367589]
• 16: Qiaozhu Mei , Dengyong Zhou , Kenneth Church, Query suggestion using hitting time, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458145]
• 17: Shilad Sen , Shyong K. Lam , Al Mamunur Rashid , Dan Cosley , Dan Frankowski , Jeremy Osterhouse , F. Maxwell Harper , John Riedl, tagging, communities, vocabulary, evolution, Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, November 04-08, 2006, Banff, Alberta, Canada [doi>10.1145/1180875.1180904]
• 18: Börkur Sigurbjörnsson , Roelof van Zwol, Flickr tag recommendation based on collective knowledge, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367542]
• 19: Yang Song , Ziming Zhuang , Huajing Li , Qiankun Zhao , Jia Li , Wang-Chien Lee , C. Lee Giles, Real-time automatic tag recommendation, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390423]
• 20: Jian-Tao Sun , Hua-Jun Zeng , Huan Liu , Yuchang Lu , Zheng Chen, CubeSVD: a novel approach to personalized Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060803]
• 21: Luis von Ahn , Laura Dabbish, Labeling images with a computer game, Proceedings of the SIGCHI conference on Human factors in computing systems, p.319-326, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985733]
• 22: Z. Xu, Y. Fu, J. Mao, and D. Su. Towards the semantic web: Collaborative tag suggestions. In Collaborative Web Tagging Workshop at WWW2006, 2006.
• 23: D. Zhou, J. Weston, A. Gretton, O. Bousquet, and B. Scholkopf. Ranking on data manifolds. In 18th Annual Conference on Neural Information Processing Systems, 2003.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation

Keywords:
personalization, ranking, recommender systems, social tagging