Jing Wang
ABSTRACT
This work studies the binary matrix completion problem underlying a large body of real-world applications such as signed link prediction and information propagation. That is, each entry of the matrix indicates a binary preference such as "like" or "dislike", "trust" or "distrust". However, the performance of existing matrix completion methods may be hindered owing to three practical challenges: 1) the observed data are with binary label (i.e., not real value); 2) the data are typically sampled non-uniformly (i.e., positive links dominate the negative ones) and 3) a network may have a huge volume of data (i.e., memory and computational issue).
In order to remedy these problems, we propose a novel framework which {i} maximizes the resemblance between predicted and observed matrices as well as penalizing the logistic loss to fit the binary data to produce binary estimates; {ii} constrains the matrix max-norm and maximizes the F-score to handle non-uniformness and {iii} presents online optimization technique, hence mitigating the memory cost. Extensive experiments performed on four large-scale datasets with up to hundreds of thousands of users demonstrate the superiority of our framework over the state-of-the-art matrix completion based methods and popular link prediction approaches.
- D. Billsus and M. J. Pazzani. Learning collaborative information filters. In Proceedings of the 15th International Conference on Machine Learning, pages 46--54, 1998.Google Scholar
Digital Library
- S. Burer and R. D. Monteiro. Local minima and convergence in low-rank semidefinite programming. Mathematical Programming, 103(3):427--444, 2005. Google ScholarDigital Library
- R. Busa-Fekete, B. Szörényi, K. Dembczynski, and E. Hüllermeier. Online f-measure optimization. In NIPS, pages 595--603, 2015.Google Scholar
- J.-F. Cai, E. J. Candès, and Z. Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4):1956--1982, 2010. Google ScholarDigital Library
- T. Cai and W.-X. Zhou. A max-norm constrained minimization approach to 1-bit matrix completion. The Journal of Machine Learning Research, 14(1):3619--3647, 2013.Google ScholarDigital Library
- E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717--772, 2009. Google ScholarDigital Library
- K.-Y. Chiang, N. Natarajan, A. Tewari, and I. S. Dhillon. Exploiting longer cycles for link prediction in signed networks. In CIKM, pages 1157--1162, 2011. Google ScholarDigital Library
- G. Chowdhury. Introduction to modern information retrieval. Facet publishing, 2010.Google Scholar
- M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http://cvxr.com/cvx, Mar. 2014.Google Scholar
- R. V. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In WWW, pages 403--412, 2004. Google ScholarDigital Library
- İ Güneş, Ş. Gündüz-Ö güdücü, and Z. Çataltepe. Link prediction using time series of neighborhood-based node similarity scores. Data Mining and Knowledge Discovery, 30(1):147--180, 2016. Google ScholarDigital Library
- C. Hsieh, K. Chiang, and I. S. Dhillon. Low rank modeling of signed networks. In KDD, pages 507--515, 2012. Google ScholarDigital Library
- J. Huang, F. Nie, and H. Huang. Robust discrete matrix completion. In AAAI, pages 424--430, 2013.Google Scholar
- J. Huang, F. Nie, H. Huang, Y. Lei, and C. Ding. Social trust prediction using rank-k matrix recovery. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence, pages 2647--2653, 2013.Google ScholarDigital Library
- J. Huang, F. Nie, H. Huang, and Y.-C. Tu. Trust prediction via aggregating heterogeneous social networks. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pages 1774--1778, 2012. Google ScholarDigital Library
- P. Jain, R. Meka, and I. S. Dhillon. Guaranteed rank minimization via singular value projection. In NIPS, pages 937--945, 2010.Google ScholarDigital Library
- G. Jeh and J. Widom. Simrank: a measure of structural-context similarity. In Proceedings of the 8th ACM SIGKDD iInternational Conference on Knowledge Discovery and Data mining, pages 538--543, 2002. Google ScholarDigital Library
- Z. Kang, C. Peng, and Q. Cheng. Top-n recommender system via matrix completion. In AAAI, pages 179--185, 2016.Google ScholarDigital Library
- H. Kashima, T. Kato, Y. Yamanishi, M. Sugiyama, and K. Tsuda. Link propagation: A fast semi-supervised learning algorithm for link prediction. In SDM, volume 9, pages 1099--1110. SIAM, 2009. Google ScholarCross Ref
- L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39--43, 1953. Google ScholarCross Ref
- R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from a few entries. IEEE Transactions on Information Theory, 56(6):2980--2998, 2010. Google ScholarDigital Library
- Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer, 42(8):30--37, 2009. Google ScholarDigital Library
- J. D. Lee, B. Recht, N. Srebro, J. Tropp, and R. R. Salakhutdinov. Practical large-scale optimization for max-norm regularization. In NIPS, pages 1297--1305, 2010.Google Scholar
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. Predicting positive and negative links in online social networks. In Proceedings of the 19th International Conference on World Wide Web, pages 641--650, 2010. Google ScholarDigital Library
- P. Li, T. Hastie, and K. W. Church. Very sparse random projections. In KDD, pages 287--296, 2006. Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):1019--1031, 2007. Google ScholarCross Ref
- D. Liben-Nowell and J. M. Kleinberg. The link prediction problem for social networks. In CIKM, pages 556--559, 2003. Google ScholarDigital Library
- N. Linial, S. Mendelson, G. Schechtman, and A. Shraibman. Complexity measures of sign matrices. Combinatorica, 27(4):439--463, 2007. Google ScholarDigital Library
- H. Ma, D. Zhou, C. Liu, M. R. Lyu, and I. King. Recommender systems with social regularization. In WSDM, pages 287--296. ACM, 2011. Google ScholarDigital Library
- M. E. Newman. Clustering and preferential attachment in growing networks. Physical Review E, 64(2):025102, 2001. Google ScholarCross Ref
- R. Ni and Q. Gu. Optimal statistical and computational rates for one bit matrix completion. In AISTATS, pages 426--434, 2016.Google Scholar
- N. Rao, H.-F. Yu, P. K. Ravikumar, and I. S. Dhillon. Collaborative filtering with graph information: Consistency and scalable methods. In NIPS, pages 2098--2106, 2015.Google Scholar
- B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471--501, 2010. Google ScholarDigital Library
- J. Shen, H. Xu, and P. Li. Online optimization for max-norm regularization. In NIPS, pages 1718--1726, 2014.Google ScholarDigital Library
- A. Shrivastava and P. Li. Asymmetric minwise hashing for indexing binary inner products and set containment. In WWW, pages = 981--991, year = 2015. Google ScholarDigital Library
- A. Shrivastava and P. Li. Fast near neighbor search in high-dimensional binary data. In ECML-PKDD, pages 474--489, 2012. Google ScholarDigital Library
- N. Srebro, J. D. Rennie, and T. Jaakkola. Maximum-margin matrix factorization. In NIPS, pages 1329--1336, 2004.Google ScholarDigital Library
- N. Srebro and A. Shraibman. Rank, trace-norm and max-norm. In Learning Theory, pages 545--560. 2005. Google ScholarDigital Library
- J. Tang, S. Chang, C. C. Aggarwal, and H. Liu. Negative link prediction in social media. In WSDM, pages 87--96, 2015. Google ScholarDigital Library
- J. Tang, H. Gao, X. Hu, and H. Liu. Exploiting homophily effect for trust prediction. In WSDM, pages 53--62, 2013. Google ScholarDigital Library
- J. Tang and H. Liu. Trust in social media. Synthesis Lectures on Information Security, Privacy, & Trust, 10(1):1--129, 2015.Google Scholar
Index Terms
- Online Matrix Completion for Signed Link Prediction
Recommendations
A link prediction algorithm based on low-rank matrix completion
Link prediction is an essential research area in network analysis. Based on the technique of matrix completion, an algorithm for link prediction in networks is proposed. We propose a new model to describe matrix completion. In addition to the observed ...
Non-linear matrix completion
Conventional matrix completion methods are linear methods. This paper proposed a non-linear matrix completion (NLMC) method that is able to handle data of non-linear structures and high-rank matrices.NLMC significantly outperforms existing methods in ...
T-product factorization based method for matrix and tensor completion problems
AbstractLow rank matrix and tensor completion problems are to recover the incomplete two and higher order data of low rank structures. The essential problem in the matrix and tensor completion problems is how to improve the efficiency. For a matrix ...
Comments