Efficient Latent Link Recommendation in Signed Networks

ABSTRACT

Signed networks, in which the relationship between two nodes can be either positive (indicating a relationship such as trust) or negative (indicating a relationship such as distrust), are becoming increasingly common. A plausible model for user behavior analytics in signed networks can be based upon the assumption that more extreme positive and negative relationships are explored and exploited before less extreme ones. Such a model implies that a personalized ranking list of latent links should place positive links on the top, negative links at the bottom, and unknown status links in between. Traditional ranking metrics, e.g., area under the receiver operating characteristic curve (AUC), are however not suitable for quantifying such a ranking list which includes positive, negative, and unknown status links. To address this issue, a generalized AUC (GAUC) which can measure both the head and tail of a ranking list has been introduced. Since GAUC weights each pairwise comparison equally and the calculation of GAUC requires quadratic time, we derive two lower bounds of GAUC which can be computed in linear time and put more emphasis on ranking positive links on the top and negative links at the bottom of a ranking list. Next, we develop two efficient latent link recommendation (ELLR) algorithms in order to recommend links by directly optimizing these two lower bounds, respectively. Finally, we compare these two ELLR algorithms with top-performing baseline methods over four benchmark datasets, among which the largest network has more than 100 thousand nodes and seven million entries. Thorough empirical studies demonstrate that the proposed ELLR algorithms outperform state-of-the-art approaches for link recommendation in signed networks at no cost in efficiency.

References

1. L. A. Adamic and E. Adar. Friends and neighbors on the web. Social Networks, 25(3):211 -- 230, 2003.
2. L. Backstrom and J. Leskovec. Supervised random walks: predicting and recommending links in social network. In Proceedings of the 4th ACM international Conference on Web Search and Data Mining, pages 635--644, Hong Kong, China, 2011.
3. M. J. Brozzowski, T. Hogg, and G. Szabo. Friends and foes: ideological social networking. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 817--820, Florence, Italy, 2008.
4. M. Burke and R. Kraul. Mopping up: Modeling wikipedia promotion decisions. In Proceedings of the 2008 ACM conference on Computer Supported Cooperative Work, pages 27--36, 2008.
5. Y. Cao, J. Xu, T.-Y. Liu, H. Li, Y. Huang, and H.-W. Ho. Adapting ranking svm to document retrieval. In Proceedings of the 29th SIGIR Conference on Research and Development, 2006.
6. P. Cremonesi, Y. Koren, and R. Turrin. Performance of recommender algorithms on top-n recommendation tasks. In Proceedings of ACM Conference on Recommender Systems, pages 39--46, 2010.
7. R. V. Guha, R. Kumar, P. Raghavan, and A. Tomkin. Propogation of trust and distrust. In Proceedings of the 13th International Conference on World Wide Web, pages 403--412, New York, NY, 2004.
8. J. A. Hanley and B. J. Mcneil. The meaning and use of the area under a receiver operating characteristic (roc) curve. Radiology, 1982.
9. C. J. Hsieh, K. Y. Chiang, and I. S. Dhillon. Low rank modeling of signed network. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Beijing, China, 2012.
10. L. Katz. A new status index dervied from sociometric analysis. Psychometrika, 18(1):39--43, 1953.
11. Y. Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 426--434, 2008.
12. Y. Koren, R. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer, 42(8):30--37, 2009.
13. C. Lampe, E. Johnston, and R. Resnick. Follow the reader: filtering comments on slashdot. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 1253--1262, San Jose, CA, 2007.
14. J. Lee, S. Bengio, S. Kim, G. Lebanon, and Y. Singer. Local collaborative filtering. In Proceedings of the 23th International Conference on World Wide Web, 2014.
15. J. Leskovec, D. P. Huttenlocher, and J. M. Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 20th International Conference on World Wide Web, pages 641--650, 2010.
16. Y. Li. A generalization of auc to an ordered multiclass diagnoisis and application to longitudianl data analysis on intellectual outcome in pediatric brain-tumor patients. Ph.D Thesis of Geogia State University, 2009.
17. D. Liben-Nowell and J. Kleinberg. The link prediction for social networks. Journal of American Society for Information Science and Technology, 58(7):1019--1031, 2007.
18. A. K. Menon and C. Elkan. Link prediction via matrix factorization. In Proceedings of the European Conference on Machine Learning, Part II, LNAI2912, pages 437--452, 2011.
19. C. T. Nakas and C. T. Yiannoutsos. Ordered multi-class roc analyisis with continuous measurements. Statistics in Medicine, 23:3437--3449, 2004.
20. S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence, pages 452--461, Arlington, Virginia, United States, 2009.
21. J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative filtering. In Proceedings of the 22nd International Conference on Machine Learning, pages 713--719, 2005.
22. R. Salakhutdinov and A. Mnih. Probabilistic matrix factorization. In Proceedings of the Neural Information Processing Systems, 2007.
23. G. Salton and M. J. McGill. Introduction to modern information retrieval. New York: McGraw Hill, 1983.
24. Y. Shi, M. Larson, and A. Hanjalic. List-wise learning to rank with matrix factorization for collaborative filtering. In Proceedings of the 4th ACM Conference on Recommender Systems, pages 269--272, 2010.
25. D. Song and D. A. Meyer. A model of consistent node types in signed directed social networks. In Proceedings of the 6th IEEE/ACM International Conference on Advances in Social Network Analysis and Mining, pages 82--90, Beijing, China,, 2014.
26. D. Song and D. A. Meyer. Recommding positive links in signed social networks by optmizing a generalized auc. In Proceedings of 29th AAAI Conference on Artificial Intelligence, Austin, USA, January, 2015.
27. D. Song, D. A. Meyer, and M. R. Min. Fast nonnegative matrix factorization with rank-one admm. In NIPS Workshop on Optimization for Machine Learning, Montreal, Canada, 2014.
28. J. Tang, S. Chang, C. C. Aggarwal, and H. Liu. Negative link prediction in social media. In Proceedings of the 8th ACM International Conference on Web Search and Data Mining, pages 87--96, 2015.
29. J. Tang, S. Wu, J. Sun, and H. Su. Cross-domain collaboration recommendation. In Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1285--1293, Beijing, China, August, 2012.
30. M. Weimer, A. Karatzoglou, and A. Smola. Improving maximum margin matrix factorization. Machine Leanring, 72(3):263--276, 2008.
31. F. Xia, T.-Y. Liu, J. Wang, W. Zhang, and H. Li. Listwise approach learning to rank - theory and algorithm. In Proceedings of International Conference on Machine Learning, pages 1192--1199, 2008.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Document filtering

      • Information extraction