A modified random walk framework for handling negative ratings and generating explanations

Abstract

The concept of random walk (RW) has been widely applied in the design of recommendation systems. RW-based approaches are effective in handling locality problem and taking extra information, such as the relationships between items or users, into consideration. However, the traditional RW-based approach has a serious limitation in handling bidirectional opinions. The propagation of positive and negative information simultaneously in a graph is nontrivial using random walk. To address the problem, this article presents a novel and efficient RW-based model that can handle both positive and negative comments with the guarantee of convergence. Furthermore, we argue that a good recommendation system should provide users not only a list of recommended items but also reasonable explanations for the decisions. Therefore, we propose a technique that generates explanations by backtracking the influential paths and subgraphs. The results of experiments on the MovieLens and Netflix datasets show that our model significantly outperforms state-of-the-art RW-based algorithms, and is capable of improving the overall performance in the ensemble with other models.

References

1. Abbassi, Z., Amer-Yahia, S., Lakshmanan, L. V. S., Vassilvitskii, S., and Yu, C. 2009. Getting recommender systems to think outside the box, in Proceedings of the Recommender Systems Conference. 285--288.
2. Ackley, D. H., Hinton, G. E., and Sejnowski, T. J. 1985. A learning algorithm for Boltzmann Machines. Cognitive Sci. 9, 1, 147--169.
3. Adomavicius, G. and Tuzhilin, A. 2005. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. IEEE Trans. Knowl. Data Eng. 17, 6, 734--749.
4. Athreya, K. B., Doss, H., and Sethuraman, J. 1996. On the convergence of the Markov chain simulation method. Ann. Statist. 24, 1, 69--100.
5. Bomhardt, C. 2004. Newsrec, a svm-driven personal recommendation system for news websites. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence.
6. Brin, S. and Page, L. 1998. Anatomy of a large-scale hypertextual web search engine. In Proceedings of the 7th International World Wide Web Conference.
7. Chapelle, O. and Keerthi, S. S. 2009. Efficient algorithms for ranking with svms. Inf. Retrieval J.
8. Chen, P.-L., Tsai, C.-T., et al. 2011. A linear ensemble of individual and blended models for music rating prediction. In Proceedings of the ACM SIGKDD KDD-Cup Workshop.
9. Cheng, H., Tan, P.-N., Sticklen, J., and Punch, W. F. 2007. Recommendation via query centered random walk on k-partite graph. In Proceedings of the IEEE International Conference on Data Mining. 457--462.
10. Clements, M., de Vries, A., and Reinders, M. J. T. 2009a. Exploiting positive and negative graded relevance assessments for content recommendation. In Proceedings of the 6th International Workshop on Algorithms and Models for the Web-Graph. Springer, 155--166.
11. Craswell N. and Szummer, M. 2007. Random walks on the click graph, In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.
12. Faloutsos, C., McCurley, K. S., and Tomkins, A. 2004. Fast discovery of connection subgraphs. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. 118--127.
13. Fouss, F.,Pirotte, A.,Renders, J.-M., and Saerens, M. 2007. Random-walk computation of similarities between nodes of a graph, with application to collaborative recommendation. IEEE Trans. Knowl. Data Eng., 355--369.
14. Gallagher, B., Tong, H. Eliassi-Rad, T., and Falousos, C. 2008. Using ghost edges for classification in sparsely labeled networks, in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM Press, New York.
15. Gori, M. and Pucci, A. 2007. Itemrank: a random-walk based scoring algorithm for recommender engines. In Proceedings of the International Joint Conference on Artificial Intelligence. 2766--2771.
16. Guha, R., Kumar, R., Raghavan, P., and Tomkins, A. Propagation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web.
17. Haynes, S. R. 2001. Explanation in information systems: A design rationale approach. PhD thesis, Department of Information Systems and Department of Social Psychology, London School of Economics and Political Science.
18. Herlocker, J., Konstan, J., and Riedl, J. 2000. Explaining collaborative filtering recommendations. In Proceedings of the ACM Conference on Computer-Supported Cooperative Work. 241--250.
19. Hofmann, T. Latent semantic models for collaborative filtering. 2004. ACM Trans. Inf. Syst., 22, 1, 89--115.
20. Jamali, M. and Ester, M. 2009. TrustWalker: A random walk model for combining trust-based and item-based recommendation. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. F. Fogelman-Soulié, P. A. Flach, and M. J. Zaki, Eds., ACM, 397--406.
21. Koren, Y., Bell, R. M., and Volinsky, C. 2009. Matrix factorization techniques for recommender systems. Comput. 42, 8.
22. libsvm. http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html.
23. Liu, N. N. and Yang, Q. 2008. Eigenrank: A ranking-oriented approach to collaborative filtering. In Proceedings of the Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 83--90.
24. Liu, N. N., Zhao, M., and Yang, Q. 2009. Probabilistic latent preference analysis for collaborative filtering. In Proceedings of the International Conference on Information and Knowledge Management. 759--766.
25. McKenzie, T.G., Ferng, C. S., Chen, Y. N., Li, C. S., Tsai, C. H., Wu, K. W., Chang, Y. H., and Li, C. Y. 2011. Novel models and ensemble techniques to discriminate favorite items from unrated ones for personalized music recommendation. in Proceedings of the ACM SIGKDD KDD-CUP Workshop.
26. Mirza, B. J., Keller, B. J., and Ramakrishnan, N. 2003. Studying recommendation algorithms by graph analysis. J. Intell. Inf. Syst. 20, 2, 131--160.
27. MovieLens, http://www.grouplens.org/node/73.
28. Netflix Prize. http://www.netflixprize.com/.
29. Parra, D. and P. Brusilovsky, P. 2009. Collaborative filtering for social tagging systems: an experiment with CiteULike. In Proceedings of the 3rd ACM Conference on Recommender Systems.
30. Piotte, M. and M. Chabbert, M. 2009. The pragmatic theory solution to the Netix grand prize. Tech. rep.
31. Resnick, P., Iacovou, N., Suchak, M., Bergstrom, P., and Riedl, J. 1994. GroupLens: An open architecture for collaborative filtering of netnews. In Proceedings of the Conference on Computer Supported Collaborative Work. R. Furuta and C. Neuwirth, Eds., ACM, New York. 175--186.
32. Sarwar, B. M., Karypis, G., Konstan, J. A., and Riedl, J. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th InternationalWorldWideWeb Conference.
33. Takcs, G., Pilszy, I., Nemeth, B., and Tikk, D. 2007. Matrix factorization and neighbor based algorithms for the Netflix prize problem, In Proceedings of the ACM Conference on Recommender Systems.
34. Tong, H. and Faloutsos, C. 2006. Center-piece subgraphs: problem definition and fast solutions. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 404--413.
35. Tong, H., Huiming H., and Jamjoom, H. 2008. Measuring proximity on graphs with side information. In Proceedings of the 8th IEEE International Conference on Data Mining. 598--607.
36. Toscher, A. and Jahrer, M. 2009. The BigChaos solution to the Netix grand prize. Tech. rep.
37. Yildirim, H. and Krishnamoorthy, M. S. 2008. A random walk method for alleviating the sparsity problem in collaborative filtering. In Proceedings of the ACM Conference on Recommender Systems. ACM, New York, NY, 131--138.
38. Zhang, J., Tang, J., Liang, B., Yang, Z., Wang, S., Zuo, J., and Li, J. 2008. Recommendation over a heterogeneous social network. In Proceedings of the 9th International Conference on Web-Age Information Management.
39. Zhang, Z.-K., Zhou, T., and Zhang Y.-C. 2010. Personalized recommendation via integrated diffusion on user-item-tag tripartite graphs. Physica A 389, 179--186
40. Zheng, B., Zheng, X., and Yang, Q. 2010. Collaborative filtering meets mobile recommendation: A user-centered approach. In Proceedings of the National Conference on Artificial Intelligence.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction

  • Information systems applications

    • Data mining