Cho-Jui Hsieh
ABSTRACT
Trust networks, where people leave trust and distrust feedback, are becoming increasingly common. These networks may be regarded as signed graphs, where a positive edge weight captures the degree of trust while a negative edge weight captures the degree of distrust. Analysis of such signed networks has become an increasingly important research topic. One important analysis task is that of sign inference, i.e., infer unknown (or future) trust or distrust relationships given a partially observed signed network. Most state-of-the-art approaches consider the notion of structural balance in signed networks, building inference algorithms based on information about links, triads, and cycles in the network. In this paper, we first show that the notion of weak structural balance in signed networks naturally leads to a global low-rank model for the network. Under such a model, the sign inference problem can be formulated as a low-rank matrix completion problem. We show that we can perfectly recover missing relationships, under certain conditions, using state-of-the-art matrix completion algorithms. We also propose the use of a low-rank matrix factorization approach with generalized loss functions as a practical method for sign inference - this approach yields high accuracy while being scalable to large signed networks, for instance, we show that this analysis can be performed on a synthetic graph with 1.1 million nodes and 120 million edges in 10 minutes. We further show that the low-rank model can be used for other analysis tasks on signed networks, such as user segmentation through signed graph clustering, with theoretical guarantees. Experiments on synthetic as well as real data show that our low rank model substantially improves accuracy of sign inference as well as clustering. As an example, on the largest real dataset available to us (Epinions data with 130K nodes and 840K edges), our matrix factorization approach yields 94.6% accuracy on the sign inference task as compared to 90.8% accuracy using a state-of-the-art cycle-based method - moreover, our method runs in 40 seconds as compared to 10,000 seconds for the cycle-based method.
Supplemental Material
- J.-F. Cai, E. J. candés, and Z. Shen. A singular value thresholding algorithm for matrix completion. Society for Industrial and Applied Mathematics (SIAM), 20(4):1956--1982, 2010. Google Scholar
Digital Library
- E. J. Candés and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory, 56(5):2053--2080, 2009. Google ScholarDigital Library
- E. J. Candés and B. Recht. Exact matrix completion via convex optimization. Found. of Comput. Math., 9:712--772, 2008. Google ScholarDigital Library
- D. Cartwright and F. Harary. Structure balance: A generalization of Heider's theory. Psychological Review, 63(5):277--293, 1956.Google ScholarCross Ref
- K.-Y. Chiang, N. Natarajan, A. Tewari, and I. S. Dhillon. Exploiting longer cycles for link prediction in signed networks. In CIKM, 2011. Google ScholarDigital Library
- F. Chung, L. Lu, and V. Vu. Spectra of random graphs with given expected degrees. Internet Mathematics, 1, 2004.Google Scholar
- J. A. Davis. Clustering and structural balance in graphs. Human Relations, 20(2):181--187, 1967.Google ScholarCross Ref
- I. S. Dhillon, Y. Guan, and B. Kulis. Weighted graph cuts without eigenvectors: A multilevel approach. IEEE Trans. on pattern analysis and machine intelligence, 29(11):1944--1957, 2007. Google ScholarDigital Library
- R. V. Guha, R. Kumar, P. Raghavan, and A. Tomkins. Propagation of trust and distrust. In WWW, 2004. Google ScholarDigital Library
- S. Hanneke and E. P. Xing. Network completion and survey sampling. In AISTATS, 2009.Google Scholar
- F. Harary. On the notion of balance of a signed graph. Michigan Mathematical Journal, 2(2):143--146, 1953.Google ScholarCross Ref
- P. Jain, R. Meka, and I. Dhillon. Guaranteed rank minimization via singular value projection. In NIPS, pages 934--945, 2010.Google Scholar
- M. Kim and J. Leskovec. The network completion problem: infering missing nodes and edges in networks. In SDM, 2011.Google ScholarCross Ref
- Y. Koren, R. M. Bell, and C. Volinsky. Matrix factorization techniques for recommender systems. IEEE Computer, 42:30--37, 2009. Google ScholarDigital Library
- J. Kunegis, A. Lommatzsch, and C. Bauckhage. The slashdot zoo: Mining a social network with negative edges. In WWW, pages 741--750, 2009. Google ScholarDigital Library
- J. Kunegis, S. Schmidt, A. Lommatzsch, J. Lerner, E. W. DeLuca, and S. Albayrak. Spectral analysis of signed graphs for clustering, prediction and visualization. In SDM, pages 559--570, 2010.Google ScholarCross Ref
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. Predicting positive and negative links in online social networks. In WWW, 2010. Google ScholarDigital Library
- A. Y. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, 2001.Google ScholarDigital Library
- 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
- B. Yang, W. Cheung, and J. Liu. Community mining from signed social networks. IEEE Trans. on knowledge and data engineering, 19(10):1333--1348, 2007. Google ScholarDigital Library
Index Terms
- Low rank modeling of signed networks
Recommendations
Signed Network Modeling Based on Structural Balance Theory
CIKM '18: Proceedings of the 27th ACM International Conference on Information and Knowledge ManagementThe modeling of networks, specifically generative models, has been shown to provide a plethora of information about the underlying network structures, as well as many other benefits behind their construction. There has been a considerable increase in ...
Prediction and clustering in signed networks: a local to global perspective
The study of social networks is a burgeoning research area. However, most existing work is on networks that simply encode whether relationships exist or not. In contrast, relationships in signed networks can be positive ("like", "trust") or negative ("...
SigGAN: Adversarial Model for Learning Signed Relationships in Networks
Signed link prediction in graphs is an important problem that has applications in diverse domains. It is a binary classification problem that predicts whether an edge between a pair of nodes is positive or negative. Existing approaches for link prediction ...
Comments