2012 LowRankModelingofSignedNetworks

• (Hsieh et al., 2012) ⇒ Cho-Jui Hsieh, Kai-Yang Chiang, and Inderjit S. Dhillon. (2012). “Low Rank Modeling of Signed Networks.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339612

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222012%22+Low+Rank+Modeling+of+Signed+Networks
• http://dl.acm.org/citation.cfm?id=2339530.2339612&preflayout=flat#citedby

Quotes

Author Keywords

• Data mining; low rank model; signed networks; structural balance

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 LowRankModelingofSignedNetworks	Inderjit S. Dhillon Cho-Jui Hsieh Kai-Yang Chiang			Low Rank Modeling of Signed Networks				10.1145/2339530.2339612		2012