Social trust prediction using heterogeneous networks

Abstract

Along with increasing popularity of social websites, online users rely more on the trustworthiness information to make decisions, extract and filter information, and tag and build connections with other users. However, such social network data often suffer from severe data sparsity and are not able to provide users with enough information. Therefore, trust prediction has emerged as an important topic in social network research. Traditional approaches are primarily based on exploring trust graph topology itself. However, research in sociology and our life experience suggest that people who are in the same social circle often exhibit similar behaviors and tastes. To take advantage of the ancillary information for trust prediction, the challenge then becomes what to transfer and how to transfer. In this article, we address this problem by aggregating heterogeneous social networks and propose a novel joint social networks mining (JSNM) method. Our new joint learning model explores the user-group-level similarity between correlated graphs and simultaneously learns the individual graph structure; therefore, the shared structures and patterns from multiple social networks can be utilized to enhance the prediction tasks. As a result, we not only improve the trust prediction in the target graph but also facilitate other information retrieval tasks in the auxiliary graphs. To optimize the proposed objective function, we use the alternative technique to break down the objective function into several manageable subproblems. We further introduce the auxiliary function to solve the optimization problems with rigorously proved convergence. The extensive experiments have been conducted on both synthetic and real- world data. All empirical results demonstrate the effectiveness of our method.

References

1. Bedi, P., Kaur, H., and Marwaha, S. 2007. Trust based recommender system for semantic web. In Proceedings of the 20th International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Francisco, CA, 2677--2682.
2. Billsus, D. and Pazzani, M. J. 1998. Learning collaborative information filters. In Proceedings of the 15th International Conference on Machine Learning. Morgan Kaufmann, San Francisco, CA, 46--54.
3. Boyd, S. and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press, Cambridge.
4. Cai, D., He, X., Wu, X., and Han, J. 2008. Non-negative factorization on manifold. In Proceedings of the 8th IEEE International Conference on Data Mining. IEEE, Los Alamitos, CA, 63--72.
5. Candes, E. and Recht, B. 2012. Exact matrix completion via convex optimization. Comm. ACM 55, 6, 111--119.
6. Cao, B., Liu, N., and Yang, Q. 2010. Transfer learning for collective link prediction in multiple heterogenous domains. In Proceedings of the 27th International Conference on Machine Learning. ACM, New York, 159--166.
7. Chapelle, O., Scholkopf, B., and Zien, A. 2006. Semi-Supervised Learning. MIT Press, Cambridge, MA.
8. Crandall, D., Cosley, D., Huttenlocher, D., Kleinberg, J., and Suri, S. 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, New York, 160--168.
9. Davis, J. and Goadrich, M. 2006. The relationship between precision-recall and roc curves. In Proceedings of the 15th International Conference on Machine Learning. ACM, New York, 233--240.
10. Ding, C., Li, T., and Jordan, M. 2010. Convex and semi-nonnegative matrix factorization. IEEE Trans. Pattern Anal. Mach. Intell. 32, 1, 45--55.
11. Getoor, L. and Diehl, C. 2005. Link mining: A survey. ACM SIGKDD Explorations Newsletter 7, 2, 3--12.
12. Guha, R., Kumar, R., Raghavan, P., and Tomkins, A. 2004. Propagation of trust and distrust. In Proceedings of 11th International Conference on World Wide Web. ACM, New York, 403--412.
13. He, X. and Niyogi, P. 2003. Locality preserving projections. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 153--160.
14. Herlocker, J., Konstan, J., Borchers, A., and Riedl, J. 1999. An algorithmic framework for performing collaborative filtering. In Proceedings of the Conference on Research and Development in Information Retrieval. ACM, New York, 230--237.
15. Hofmann, T. and Puzicha, J. 1999. Latent class models for collaborative filtering. In Proceedings of the 16th International Joint Conference on Artificial Intelligence. ACM, New York, 688--693.
16. Huang, J., Nie, F., Huang, H., and Tu, Y.-C. 2012. Trust prediction via aggregating heterogeneous social networks. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management. ACM, New York, NY, 1774--1778.
17. Jeh, G. and Widom, J. 2002. A measure of structural-context similarity. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 538--543.
18. Kamvar, S., Schlosser, M., and Garcia-Molina, H. 2003. The eigentrust algorithm for reputation management in p2p networks. In Proceedings of the 12th International Conference on World Wide Web. ACM, New York.
19. Lee, D. and Seung, H. 2000. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 556--562.
20. Leskovec, J., Huttenlocher, D., and Kleinberg, J. 2010. Predicting positive and negative links in online social networks. In Proceedings of the 19th International Conference on World Wide Web. ACM, New York.
21. Liben-Nowell, D. and Kleinberg, J. 2003. The link prediction problem for social networks. In Proceedings of the 12th International Conference on Information and Knowledge Management. ACM, New York, 556--559.
22. Massa, P. and Avesani, P. 2007. Trust-aware recommender systems. In Proceedings of the 2007 ACM Conference on Recommender Systems. ACM, New York, 17--24.
23. Massa, P. and Avesani, P. 2009. Trust metrics in recommender systems. Comput. Social Trust, 259--285.
24. McPherson, M., Smith-Lovin, L., and Cook, J. 2001. Birds of a feather: Homophily in social networks. Ann. Rev. Sociol. 27, 415--444.
25. Mislove, A., Viswanath, B., Gummadi, P., and Druschel, P. 2010. You are who you know: Inferring user profiles in online social networks. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining. ACM, New York, NY, 251--260.
26. Ng, A., Jordan, M., and Weiss, Y. 2001. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 849--856.
27. Pan, W., Xiang, W., Liu, N., and Yang, Q. 2010. Transfer learning in collaborative filtering for sparsity reduction. In Proceedings of the 24th AAAI Conference on Artificial Intelligence. AAAI Press, Palo Alto, CA, 230--235.
28. Roweis, S. and Saul, L. K. 2000. Nonlinear dimensionality reduction by locally linear embedding. Science 290, 5500, 2323--2326.
29. Salakhutdinov, R. and Mnih, A. 2007. Probabilitistic matrix factorization. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 1257--1264.
30. Salakhutdinov, R. and Mnih, A. 2008. Bayesian probabilistic matrix factorization using Marknov chain Monte Carlo. In Proceedings of the 25th International Conference on Machine learning. ACM, New York, 880--887.
31. Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. 2001. Item-based collaborative filtering recommendation algorithms. In Proceedings of the 10th International Conference on World Wide Web. ACM, New York, NY, 285--295.
32. Shi, J. and Malik, J. 2000. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22, 8, 888--905.
33. Singh, A. and Gordon, G. 2008. Relational learning via collective matrix factorization. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 650--658.
34. Srebro, N. and Jaakkola, T. 2003. Weighted low-rank approximations. In Proceedings of the 20th Annual International Conference on Machine Learning. AAAI Press, Palo Alto, CA, 720--727.
35. von Luxburg, U. 2006. A tutorial on spectral clustering. Stat. Comput. 17, 4, 395--416.
36. Wen, Z. and Lin, C. 2010. On the quality of inferring interests from social neighbors. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, New York, 373--382.
37. Xu, Z., Kersting, K., and Tresp, V. 2009. Multi-relational learning with gaussian process. In Proceedings of the 21st International Joint Conference on Artificial Intelligence. Morgan Kaufmann, San Francisco, CA, 1309--1314.
38. Yu, K. and Chu, W. 2007. Gaussian process models for link analysis and transfer learning. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 1657--1664.
39. Yu, K., Chu, W., Yu, S., Tresp, V., and Zhao, X. 2006. Stochastic relational models for discriminative link prediction. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA, 333--340.
40. Yu, K., Lafferty, J., Zhu, S., and Gong, Y. 2007. Large-scale collaborative prediction using a nonparametric random effects model. In Proceedings of the 26th Annual International Conference on Machine Learning. ACM, New York, 1185--1192.
41. Yuster, R. and Zwick, U. 2005. Fast sparse matrix multiplication. ACM Trans. Algorithms 1, 1, 2--13.
42. Zhu, S., Yu, K., Chi, Y., and Gong, Y. 2007. Combining content and link for classification using matrix factorization. In Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, 487--494.

Index Terms

• Information systems

  • Information retrieval