Matrix Factorization with Explicit Trust and Distrust Side Information for Improved Social Recommendation

Abstract

With the advent of online social networks, recommender systems have became crucial for the success of many online applications/services due to their significance role in tailoring these applications to user-specific needs or preferences. Despite their increasing popularity, in general, recommender systems suffer from data sparsity and cold-start problems. To alleviate these issues, in recent years, there has been an upsurge of interest in exploiting social information such as trust relations among users along with the rating data to improve the performance of recommender systems. The main motivation for exploiting trust information in the recommendation process stems from the observation that the ideas we are exposed to and the choices we make are significantly influenced by our social context. However, in large user communities, in addition to trust relations, distrust relations also exist between users. For instance, in Epinions, the concepts of personal “web of trust” and personal “block list” allow users to categorize their friends based on the quality of reviews into trusted and distrusted friends, respectively. Hence, it will be interesting to incorporate this new source of information in recommendation as well. In contrast to the incorporation of trust information in recommendation which is thriving, the potential of explicitly incorporating distrust relations is almost unexplored. In this article, we propose a matrix factorization-based model for recommendation in social rating networks that properly incorporates both trust and distrust relationships aiming to improve the quality of recommendations and mitigate the data sparsity and cold-start users issues. Through experiments on the Epinions dataset, we show that our new algorithm outperforms its standard trust-enhanced or distrust-enhanced counterparts with respect to accuracy, thereby demonstrating the positive effect that incorporation of explicit distrust information can have on recommender systems.

References

1. Gediminas Adomavicius and Alexander Tuzhilin. 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 (2005), 734--749.
2. Deepak Agarwal and Bee-Chung Chen. 2010. fLDA: Matrix factorization through latent dirichlet allocation. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. ACM, 91--100.
3. Paolo Avesani, Paolo Massa, and Roberto Tiella. 2005. A trust-enhanced recommender system application: Moleskiing. In Proceedings of the ACM Symposium on Applied Computing. 1589--1593.
4. Giacomo Bachi, Michele Coscia, Anna Monreale, and Fosca Giannotti. 2012. Classifying trust/distrust relationships in online social networks. In International Conference on Privacy, Security, Risk and Trust (PASSAT) and International Confernece on Social Computing (SocialCom). IEEE, 552--557.
5. Jesús Bobadilla, Fernando Ortega, Antonio Hernando, and Abraham Gutiérrez. 2013. Recommender systems survey. Knowl. Based Syst. 46 (2013), 109--132.
6. John S. Breese, David Heckerman, and Carl Kadie. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., 43--52.
7. Moira Burke and Robert Kraut. 2008. Mopping up: Modeling Wikipedia promotion decisions. In Proceedings of the ACM Conference on Computer Supported Cooperative Work. ACM, 27--36.
8. Dorwin Cartwright and Frank Harary. 1956. Structural balance: A generalization of Heider's theory. Psychol. Rev. 63, 5 (1956), 277.
9. Gang Chen, Fei Wang, and Changshui Zhang. 2009. Collaborative filtering using orthogonal nonnegative matrix tri-factorization. Inf. Process. Manag. 45, 3 (2009), 368--379.
10. Andrew Cotter, Ohad Shamir, Nati Srebro, and Karthik Sridharan. 2011. Better mini-batch algorithms via accelerated gradient methods. In Conference on Neural Information Processing Systems (NIPS). Vol. 24 1647--1655.
11. David Crandall, Dan Cosley, Daniel Huttenlocher, Jon Kleinberg, and Siddharth Suri. 2008. Feedback effects between similarity and social influence in online communities. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 160--168.
12. Sanjoy Dasgupta, Michael L. Littman, and David McAllester. 2002. PAC generalization bounds for co-training. In Proceedings of the Conference on Neural Information Processing Systems. 375--382.
13. Mukund Deshpande and George Karypis. 2004. Item-based top-n recommendation algorithms. ACM Trans. Inf. Syst. 22, 1 (2004), 143--177.
14. Thomas DuBois, Jennifer Golbeck, and Aravind Srinivasan. 2011. Predicting trust and distrust in social networks. In Proceedings of the IEEE 3rd International Conference on Privacy, Security, Risk and Trust (PASSAT), and IEEE 3rd International Conference on Social Computing (SocialCom). IEEE, 418--424.
15. Rana Forsati, Hanieh Mohammadi Doustdar, Mehrnoush Shamsfard, Andisheh Keikha, and Mohammad Reza Meybodi. 2013. A fuzzy co-clustering approach for hybrid recommender systems. Int. J. Hybrid Intell. Syst. 10, 2 (2013), 71--81.
16. Rana Forsati and Mohammad Reza Meybodi. 2010. Effective page recommendation algorithms based on distributed learning automata and weighted association rules. Expert Syst. Appl. 37, 2 (2010), 1316--1330.
17. Jennifer Golbeck. 2005. Computing and applying trust in web-based social networks. Ph.D. Dissertation, University of Maryland at College Park.
18. Jennifer Golbeck. 2006. Generating predictive movie recommendations from trust in social networks. In Proceedings of the 4th International Conference on Trust Management (iTrust). Lecture Notes in Computer Science, Vol. 3986, Springer, Berlin, 93--104.
19. Jennifer Golbeck and James Hendler. 2006. Filmtrust: Movie recommendations using trust in web-based social networks. In Proceedings of the IEEE Consumer Communications and Networking Conference, Vol. 96. Citeseer.
20. Nathaniel Good, J. Ben Schafer, Joseph A. Konstan, Al Borchers, Badrul Sarwar, Jon Herlocker, and John Riedl. 1999. Combining collaborative filtering with personal agents for better recommendations. In Proceedings of the 16th National Conference on Artificial Intelligence and the 11th Innovative Applications of Artificial Intelligence Conference (AAAI/IAAI). 439--446.
21. Quanquan Gu, Jie Zhou, and Chris Ding. 2010. Collaborative filtering: Weighted nonnegative matrix factorization incorporating user and item graphs. In Proceedings of the SIAM International Conference on Data Mining (SDM). 199--210.
22. R. Guha, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. 2004. Propagation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web. ACM, 403--412.
23. Guibing Guo, Jie Zhang, Daniel Thalmann, Anirban Basu, and Neil Yorke-Smith. 2014. From ratings to trust: An empirical study of implicit trust in recommender systems. In Proceedings of the 29th ACM Symposiam on Applied Computing (SAC).
24. Jonathan L. Herlocker, Joseph A. Konstan, Al Borchers, and John Riedl. 1999. An algorithmic framework for performing collaborative filtering. In Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 230--237.
25. Jonathan L. Herlocker, Joseph A. Konstan, Loren G. Terveen, and John T. Riedl. 2004. Evaluating collaborative filtering recommender systems. ACM Trans. Inf. Syst. 22, 1 (2004), 5--53.
26. Thomas Hofmann. 2004. Latent semantic models for collaborative filtering. ACM Trans. Inf. Syst. 22, 1 (2004), 89--115.
27. Mohsen Jamali and Martin Ester. 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. ACM, 397--406.
28. Mohsen Jamali and Martin Ester. 2010. A matrix factorization technique with trust propagation for recommendation in social networks. In Proceedings of the 4th ACM Conference on Recommender Systems. ACM, 135--142.
29. Mohsen Jamali and Martin Ester. 2011. A transitivity aware matrix factorization model for recommendation in social networks. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Vol. 3. AAAI Press, 2644--2649.
30. Arnd Kohrs and Bernard Merialdo. 1999. Clustering for collaborative filtering applications. In Computational Intelligence for Modelling, Control & Automation. IOS Press.
31. Ioannis Konstas, Vassilios Stathopoulos, and Joemon M. Jose. 2009. On social networks and collaborative recommendation. In Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 195--202.
32. Yehuda Koren. 2008. Factorization meets the neighborhood: A multifaceted collaborative filtering model. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 426--434.
33. Yehuda Koren, Robert Bell, and Chris Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 42, 8 (2009), 30--37.
34. Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010a. Predicting positive and negative links in online social networks. In Proceedings of the 19th International Conference on World Wide Web. ACM, 641--650.
35. Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010b. Signed networks in social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 1361--1370.
36. Wu-Jun Li and Dit-Yan Yeung. 2009. Relation regularized matrix factorization. In Proceedings of the 21st International Conference on Artificial Intelligence (IJCAI'09).
37. Juntao Liu, Caihua Wu, and Wenyu Liu. 2013. Bayesian probabilistic matrix factorization with social relations and item contents for recommendation. Decision Support Syst. 55, 3 (June 2013), 838--850.
38. Hao Ma. 2013. An experimental study on implicit social recommendation. In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 73--82.
39. Hao Ma, Irwin King, and Michael R. Lyu. 2009a. Learning to recommend with social trust ensemble. In Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 203--210.
40. Hao Ma, Michael R. Lyu, and Irwin King. 2009b. Learning to recommend with trust and distrust relationships. In Proceedings of the 3rd ACM Conference on Recommender Systems. ACM, 189--196.
41. Hao Ma, Haixuan Yang, Michael R. Lyu, and Irwin King. 2008. SoRec: Social recommendation using probabilistic matrix factorization. In Proceedings of the 17th ACM Conference on Information and Knowledge Management. ACM, 931--940.
42. Hao Ma, Dengyong Zhou, Chao Liu, Michael R. Lyu, and Irwin King. 2011a. Recommender systems with social regularization. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining. ACM, 287--296.
43. Hao Ma, Tom Chao Zhou, Michael R. Lyu, and Irwin King. 2011b. Improving recommender systems by incorporating social contextual information. ACM Trans. Inf. Syst. 29, 2 (2011), 9.
44. Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze. 2008. Introduction to Information Retrieval. Vol. 1. Cambridge University Press, Cambridge.
45. Paolo Massa and Paolo Avesani. 2004. Trust-aware collaborative filtering for recommender systems. In On the Move to Meaningful Internet Systems 2004: CoopIS, DOA, and ODBASE. Lecture Notes in Computer Science, Vol. 3290. Springer, 492--508.
46. Paolo Massa and Paolo Avesani. 2005. Controversial users demand local trust metrics: An experimental study on Epinions.com community. In Proceedings of the 20th National Conference on Artificial Intelligence (AAAI'05). 121--126.
47. Paolo Massa and Paolo Avesani. 2009. Trust metrics in recommender systems. In Computing with Social Trust. Human-Computer Intercation Series, Springer, 259--285.
48. Prem Melville, Raymond J. Mooney, and Ramadass Nagarajan. 2002. Content-boosted collaborative filtering for improved recommendations. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI). 187--192.
49. Bradley N. Miller, Joseph A. Konstan, and John Riedl. 2004. PocketLens: Toward a personal recommender system. ACM Trans. Inf. Syst. (TOIS) 22, 3 (2004), 437--476.
50. Andriy Mnih and Ruslan Salakhutdinov. 2007. Probabilistic matrix factorization. In Proceedings of the 21st Annual Conference on Neural Information Processing Systems (NIPS). 1257--1264.
51. Uma Nalluri. 2008. Utility of distrust in online recommender systems. Technical Report, Coopstone.
52. Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. 2009. Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19, 4 (2009), 1574--1609.
53. Akshay Patil, Golnaz Ghasemiesfeh, Roozbeh Ebrahimi, and Jie Gao. 2013. Quantifying social influence in epinions. Human 2, 2 (2013).
54. Dmitry Pavlov and David M. Pennock. 2002. A maximum entropy approach to collaborative filtering in dynamic, sparse, high-dimensional domains. In Proceedings of the Annual Conference on Neural Information Processing System (NIPS), Vol. 2. 1441--1448.
55. Michael J. Pazzani. 1999. A framework for collaborative, content-based and demographic filtering. Artif. Intell. Rev. 13, 5--6 (1999), 393--408.
56. David M. Pennock, Eric Horvitz, Steve Lawrence, and C. Lee Giles. 2000. Collaborative filtering by personality diagnosis: A hybrid memory-and model-based approach. In Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence. Morgan Kaufmann Publishers Inc., 473--480.
57. Jasson D. M. Rennie and Nathan Srebro. 2005. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd International Conference on Machine Learning. ACM, 713--719.
58. Ruslan Salakhutdinov and Andriy Mnih. 2008a. Bayesian probabilistic matrix factorization using Markov chain Monte Carlo. In Proceedings of the 25th International Conference on Machine Learning. ACM, 880--887.
59. Ruslan Salakhutdinov and Andriy Mnih. 2008b. Probabilistic matrix factorization. In Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. 1257--1264.
60. Ruslan Salakhutdinov, Andriy Mnih, and Geoffrey Hinton. 2007. Restricted Boltzmann machines for collaborative filtering. In Proceedings of the 24th International Conference on Machine Learning. ACM, 791--798.
61. Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International Conference on World Wide Web. ACM, 285--295.
62. Wanita Sherchan, Surya Nepal, and Cecile Paris. 2013. A survey of trust in social networks. ACM Comput. Surv. 45, 4 (2013), 47.
63. Luo Si and Rong Jin. 2003. Flexible mixture model for collaborative filtering. In Proceedings of the 20th International Conference on Machine Learning (ICML), Vol. 3. 704--711.
64. Ian Soboroff and Charles Nicholas. 1999. Combining content and collaboration in text filtering. In Proceedings of the IJCAI Workshop on Machine Learning for Information Filtering, Vol. 99. 86--91.
65. Nathan Srebro and Tommi Jaakkola. 2003. Weighted low-rank approximations. In Proceedings of the 20th International Conference on Machine Learning (ICML), Vol. 3. 720--727.
66. Nathan Srebro, Jason D. M. Rennie, and Tommi Jaakkola. 2005. Maximum-margin matrix factorization. In Proceedings of the Conference on Neural Information Processing Systems (NIPS). 1329--1336.
67. Mojdeh Talabeigi, Rana Forsati, and Mohammad Reza Meybodi. 2010. A hybrid web recommender system based on cellular learning automata. In Proceedings of the IEEE International Conference on Granular Computing (GrC). IEEE, 453--458.
68. Nele Verbiest, Chris Cornelis, Patricia Victor, and Enrique Herrera-Viedma. 2012. Trust and distrust aggregation enhanced with path length incorporation. Fuzzy Sets Syst. 202 (2012), 61--74.
69. Patricia Victor, Chris Cornelis, Martine De Cock, and Ankur Teredesai. 2011b. Trust- and distrust-based recommendations for controversial reviews. IEEE Intell. Syst. 26, 1 (2011), 48--55.
70. Patricia Victor, Chris Cornelis, and Martine De Cock. 2011a. Trust Networks for Recommender Systems. Atlantis-Computational Intelligence Series, Vol. 4. Springer, Berlin.
71. Patricia Victor, Chris Cornelis, Martine De Cock, and Enrique Herrera-Viedma. 2011c. Practical aggregation operators for gradual trust and distrust. Fuzzy Sets Syst. 184, 1 (2011), 126--147.
72. Patricia Victor, Nele Verbiest, Chris Cornelis, and Martine De Cock. 2013. Enhancing the trust-based recommendation process with explicit distrust. ACM Trans. Web 7, 2 (2013), 6.
73. Fei Wang, Sheng Ma, Liuzhong Yang, and Tao Li. 2006b. Recommendation on item graphs. In Proceedings of the 6th International Conference on Data Mining (ICDM'06). IEEE, 1119--1123.
74. Jun Wang, Arjen P. De Vries, and Marcel J. T. Reinders. 2006a. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 501--508.
75. Grzegorz Wierzowiecki and Adam Wierzbicki. 2010. Efficient and correct trust propagation using closelook. In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT). Vol. 1. IEEE, 676--681.
76. Lei Wu, Steven C. H. Hoi, Rong Jin, Jianke Zhu, and Nenghai Yu. 2009. Distance metric learning from uncertain side information with application to automated photo tagging. In Proceedings of the 17th ACM International Conference on Multimedia. ACM, 135--144.
77. Gui-Rong Xue, Chenxi Lin, Qiang Yang, WenSi Xi, Hua-Jun Zeng, Yong Yu, and Zheng Chen. 2005. Scalable collaborative filtering using cluster-based smoothing. In Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 114--121.
78. Kai Yu, Anton Schwaighofer, Volker Tresp, Xiaowei Xu, and H.-P. Kriegel. 2004. Probabilistic memory-based collaborative filtering. IEEE Trans. Knowl. Data Eng. 16, 1 (2004), 56--69.
79. Sheng Zhang, Weihong Wang, James Ford, and Fillia Makedon. 2006. Learning from incomplete ratings using non-negative matrix factorization. In Proceedings of the 6th SIAM Conference on Data Mining (SDM).
80. Yi Zhang and Jonathan Koren. 2007. Efficient bayesian hierarchical user modeling for recommendation system. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 47--54.
81. Jianke Zhu, Hao Ma, Chun Chen, and Jiajun Bu. 2011. Social recommendation using low-rank semidefinite program. In Proceedings of the 25th AAAI Conference on Artificial Intelligence.
82. Cai-Nicolas Ziegler. 2009. On propagating interpersonal trust in social networks. In Computing with Social Trust Human-Computer Interaction Series, Springer, Berlin, 133--168.
83. Cai-Nicolas Ziegler and Jennifer Golbeck. 2007. Investigating interactions of trust and interest similarity. Decision Support Syst. 43, 2 (2007), 460--475.
84. Cai-Nicolas Ziegler and Georg Lausen. 2005. Propagation models for trust and distrust in social networks. Inf. Syst. Frontiers 7, 4--5 (2005), 337--358.

Index Terms

• Applied computing

  • Law, social and behavioral sciences

• Computing methodologies

  • Machine learning

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction