Link Label Prediction in Signed Social Networks
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2591-2596.
© 2013 International Joint Conferences on Artificial Intelligence
Abstract
Online social networks continue to witness a tremendous growth both in terms of the number of registered users and their mutual interactions. In this paper, we focus on online signed social networks where positive interactions among the users signify friendship or approval, whereas negative interactions indicate antagonism or disapproval. We introduce a novel problem which we call the link label prediction problem: Given the information about signs of certain links in a social network, we want to learn the nature of relationships that exist among the users by predicting the sign, positive or negative, of the remaining links. We propose a matrix factorization based technique MF-LiSP that exhibits strong generalization guarantees. We also investigate the applicability of logistic regression Leskove et al. in this setting. Our experiments on Wiki-Vote, Epinions and Slashdot data sets strongly corroborate the efficacy of these approaches.
- O. Bousquet and A. Elisseeff. Stability and Generaliza- tion. JMLR, 2:499-526, 2002.
- E.J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inform. Theory, 56:2053-2080, 2009.
- K.-Y. Chiang, N. Natarajan, A. Tewari, I.S. Dhillon. Ex- ploiting longer cycles for link prediction in signed net- works. In Proceeding of ACM CIKM, pages 1157-1162, 2011.
- P. Cui, F. Wang, S. Liu, M. Ou, S. Yang, and L. Sun. Who should share what?: item-level social influence predic- tion for users and posts sign prediction. In SIGIR, 2011.
- J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chan- dra. Efficient Projections onto the l 1 -Ball for Learning in High Dimensions. In ICML, 2008.
- J. Kunegis, A. Lommatzsch, and C. Bauckhage. The Slashdot zoo: Mining a social network with negative edges. In WWW, pages 740-750, 2009.
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. Signed networks in social media. In ACM SIGCHI, pages 1361- 1370, 2010.
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. Predict- ing Positive and Negative Links in Online Social Net- works. In WWW, 2010.
- D. Liben-Nowell and J.M. Kleinberg. The link predic- tion problem for social networks. Proceedings of the 12th ACM International Conference on Information and Knowledge Management (CIKM), pages 556-559, 2003.
- U. Kuter and J. Golbeck. SUNNY: A New Algorithm for Trust Inference in Social Networks Using Probabilistic Confidence Models. In the Proceedings of AAAI, pages 1377-1382, 2007.
- H. Ma, D. Zhou, C. Liu, M.R. Lyu, and I. King. Recom- mender Systems with Social Regularization. In WSDM, 2011.
- A.K. Menon and C. Elkan. sign prediction via matrix factorization. In ECML PKDD, 2011.
- J. Scripps, P.-N. Tan, F. Chen, and A.-H. Esfahanian. A matrix alignment approach for sign prediction. In ICPR, pages 1-4, 2008.
- N. Srebro and A. Shraibman. Rank, trace-norm and max-norm. In COLT, pages 545560, 2005.
- S.-H. Yang, A.J. Smola, B. Long, H. Zha, and Y. Chang. Friend or frenemy?: predicting signed ties in social net- works. In Proceedings of SIGIR, pages 555-564, 2012.
- F. Wang, T. Li, X. Wang, S. Zhu, and C. Ding. Com- munity discovery using nonnegative matrix factorization. Data Mining and Knowledge Discovery, 22(3):493-521, 2011.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
The proliferation of user activity on online social communities, micro-blogging sites and other media such as Slashdot, Wikipedia, Facebook, and Twitter etc. offers a tremendous scope for mining interesting user behavior. Not only have these social networks been registering a steep growth in the number of new users, but also the interactions amongst the users. Typically, these interactions are either positive (indicating friendship or support) or negative (indicating antagonism or opposition) [6; 7]. How a user perceives his future interactions or considers his past experiences with other users involves underpinnings of several, possibly contradictory, factors. For instance, users with many common friends tend to develop an affinity for each other even in the absence of any direct interaction. The scenario becomes much more complicated in the case of a mixed bag of acquaintances: a user may have a negative impression of some contacts, and positive of some others, of a common friend. This effect becomes even more pronounced when the impact of several users is taken into account while determining the overall perception of each user toward others. We use the sign or label of a link to refer to the nature of this link. Given the information about signs of certain links in a social network, a central problem of interest concerns learning the nature of relationships that exist among the users by predicting the sign, positive or negative, of the remaining links. Hereafter we refer to this problem as the link label prediction problem.
∗P. Agrawal and V. K. Garg contributed equally to this work.
Several challenges arise in the given context. First, the global behavior of the different users needs to be accounted for, albeit the local interactions do play a significant role too [8]. Second, in a realistic scenario, determining the most important or discriminative features may not be a straightforward task; more broadly, there may be correlations among the users and/or features that are not readily decipherable (or are hidden), or worse, the different social networks may not be amenable to a predetermined set of features. Third, determining the exact nature of relationships is often a tedious and costly process. In particular, due to manual effort involved in amassing the training data, information about only a subset of pairs of users may be available.
In this work, we address some of these key issues. We formulate link sign prediction as a matrix completion problem in a setting, where the data is represented as a partially observed (and typically asymmetric) matrix. We propose a technique, MF-LiSP (Matrix Factorization for Link Sign Prediction), which employs a trace norm regularizer with a particularly suited variation of the pair-wise hinge loss to approximate the given matrix. Our approach is strongly motivated by recent results [2; 14] that suggest the use of such a regularizer as an excellent alternative to other complexity measures such as the rank of the matrix. We provide rigorous generalization bounds for MF-LiSP via algorithmic stability [1]. Additionally, we investigate the suitability of the logistic regression model [8] in the multiple label prediction setting. Our experiments suggest that the maximum likelihood based logistic regression model works very well in the current setting too.
The rest of this paper is organized as follows. We first present the related work in §1.1, and introduce some definitions in §2. Next we formulate the problem and propose our main technique in §3. We then present the theoretical justification of this work by providing rigorous generalization bounds in §4. We provide a detailed analysis on the results of our experiments in §6 and a summary of our work in §7.
1.1 RelatedWork
Techniques based on matrix factorization have been recently used for analyzing social networks. For instance, Scripps et al. [13] and Menon and Elkan [12] proposed algorithms for sign prediction in graphs. Cui et al. [4] leveraged matrix factorization to rank users with the objective of maximizing the social influence for a given item, Ma et al. [11] looked into social network based recommendation systems, and Wang et al. [16] devised a method for community detection.
Recently, there has been much interest in the problem of predicting links and their signs. Liben-Nowell and Kleinberg [9] leveraged measures that captured proximity of nodes, whereas Chiang et al. [3] investigated the use of social imbalance measures and proposed a supervised learning approach. Kuter and Golbeck [10] proposed an algorithm for trust (positive sign) inference with a probabilistic interpretation. Yang et al. [15] designed algorithms to infer the signs of social ties completely based on decision making behavior of the users.
Leskovec et al., in a seminal work [8], introduced the edge sign prediction problem: Given a social network with signs on all the edges, except that from node u to node v, how reliably can one infer this sign s(u, v)? In this paper, we generalize their setting to encompass several missing links. To the best of our knowledge, our work is the first to tackle simultaneous label prediction of multiple links.
2 Loss and Stability
Consider a learner that receives instances from a training set, S = {S1 , S2 , . . . , Sm}, where Si = {(xi1 , yi1 ), . . . , (xin , yin )|xij ∈ X ⊆ R, yij ∈ Y ⊆ R} denotes the sample set of links 1 available with user i. Let St,z i,i′ (and the abbreviated notation S′ ) refer to the sample obtained by replacing (xit , yi t ) in S with (xi′ z , yi′ z ) for some 1 ≤ i, i′ ≤ m and 1 ≤ t, z ≤ n. The goal is to learn a real-valued sign prediction function f using S.
Definition 1. (Loss function) A loss function l : RX ×(X × Y) × (X × Y) → R+ ∪ {0} assigns to each f : X → R and (xij , yij ), (xik , yik ) ∈ (X × Y), a non-negative real number l(f, (xij , yij ), (xik , yik )), which is interpreted as the penalty or loss incurred by f due to its relative predictions of xij and xik given the corresponding labels yij and yik . We shall require that the loss function l be symmetric with respect to (xij , yij ) and (xik , yik ), i.e., for all f, (xij , yij ), and (xik , yik ),
Definition 2. (Expected l-error) Let f : X → R be a sign prediction function on X , and l : RX ×(X ×Y)×(X ×Y) → R+ ∪{0} be a loss function. Define the expected l-error of f: Rl(f) = E((Xi j ,Y i j ),(Xik ,Y i k ))∈D×D[l(f, (Xi j , Y i j ), (Xik , Y i k ))], where both the training and the unseen examples are assumed to be drawn randomly and independently according to some (unknown) distribution D.
1 We use links and examples interchangeably in the sequel.
Definition 3. (Empirical l-error) Let f : X → R be a function on X and l : RX ×(X ×Y)×(X ×Y) → R+ ∪{0} be a loss function. Define the empirical l-error of f, denoted by ˆRl(f; S), as
where QSi is the set of link pairs that are available with the user i in S.
Definition 4. (Uniform loss stability) Let Abe an algorithm whose output on a training sample S we denote by fS, and let l be a loss function. Let β : N×N → R. We say that A has uniform loss stability β with respect to l if ∀ m, n ∈ N, S ∈ (X × Y)m×n , 1 ≤ i, i′ ≤ m and 1 ≤ t, z ≤ n, we have ∀(xij , yij ), (xik , yik ) ∈ (X × Y),
Definition 5. (Uniform score stability) Let A be a sign prediction algorithm whose output on a training sample S is denoted by fS. Let ν : N×N→R. We say that A has uniform score stability ν if ∀ m, n ∈ N, S ∈ (X×Y)m×n , 1 ≤ i, i′ ≤ m and 1 ≤ t, z ≤ n, we have ∀x ∈ X ,
Definition 6. (σ-admissibility) Let F be a class of realvalued functions on X. Let l be a sign prediction loss function and let σ > 0. We say that l is σ-admissible (or Lipschitz continuous) with respect to F if for all f1, f2 ∈ F and all (xij , yij ), (xik , yik ) ∈ (X × Y), we have
3 MF-LiSP
Formally, we consider a sparse matrix (A)m×m ∈ Rm×m corresponding to a social network with m nodes. Each known entry Aij represents the sign (1 for positive links and 0 for negative links) of the edge from node i to node j. Let Ai denote the ith row of A, and S the set of known entries in A. Assuming the entries in A are sampled from a uniform distribution, our objective is to employ matrix factorization based on the unweighted trace-norm to fill the remaining entries in A. We accomplish this by approximating the matrix A with a matrix (X)m×m = (U)m×d(V )′m×d , for some suitable d, such that the discrepancy between A and X is minimized. For our sign prediction problem, instead of using the point-wise error, we introduce the following pair-wise empirical error:
where QSi is the set of link pairs that are available with the user i in S. This empirical error loss function is reminiscent of the hinge loss convex surrogate for 0/1 loss in classification. We use this particular variation since it elegantly captures the correlations amongst the users and thereby makes the technique more robust to fluctuations in individual behaviors. Moreover, albeit we are concerned with binary prediction in this work, we emphasize that this loss function can be readily translated to the more generic multi-label settings, especially owing to its invariance to scale. For the current setting, our goal is to determine appropriate U and V to minimize the empirical prediction error ˆRl(X; S), or equivalently
To avoid over-fitting, we incorporate a convex regularization term:
and obtain the following primal formulation:
subject to
The corresponding dual is obtained by introducing Lagrange multipliers:
subject to
where
Our algorithm, MF-LiSP, solves this convex quadratic program (QP) by following a stochastic gradient projection approach [5]. See Algorithm 1 for more details.
4 Generalization Bounds
We now provide generalization bounds for MF-LiSP. All our theoretical results hold very generally about labels on links, covering link strength as well as link sign. We present guarantees that hold for real (multi) valued matrices and subsume the current 0/1 setting. Therefore, our algorithm can be readily adapted to more generic settings: for instance, when in addition to the (weighted) positive and negative links, there may be no links or unsigned links. But the main application in this paper is link sign prediction. To the best of our knowledge, MF-LiSP is the first technique that has provable guarantees for such general link labels. Due to space constraints, we only outline the main steps of the proofs and omit the details.
Algorithm 1 MF-LiSP
Inputs:
Parameters C, η0, pmax
Initialize:
For p = 1 to pmax do
Randomly select a row i.
Update αi :
- [Gradient step]
Output:
Theorem 1. Let A be an algorithm whose output, for a user i ∈ [m], on a training sample S we denote by fiS, and let l be a bounded loss function such that 0 ≤ l(fi, (xij , yij ), (xik , yik )) ≤ B for all fi : X → R and (xij , yij ), (xik , yik ) ∈ (X × Y). Let β : N → R be such that A has uniform loss stability β with respect to l. Then for any 0 < δ ≤ 1, with probability at least 1 - δ over the draw of S,
Proof. Define φi(S) = Rl(fiS) - ˆRl(fiS; S). We first show that φi satisfies the bounded difference requirement of the McDiarmid's inequality. We have ∣∣φi(S) - φi(St,z i′ ,i′′ )∣∣
It is easy to show that
Now consider ∣∣∣∣ ˆRl(fiS ; S)- ˆRl(fiSt,z i′,i′′ ; St,z i′ ,i′′ )∣∣∣∣. Considering the four different cases separately (whether i′ = i and/or i′′ = i is true), we can show that for all 1 ≤ i′ , i′′ ≤ n
Then, fromMcDiarmid's inequality, we have for any ϵ > 0,
It can be shown that E [Rl(fiS) - ˆRl(fiS; S)] ≤ 2β(|Si|), which immediately gives the result on setting δ = exp- ϵ2 |Si|2 2(|Si|β(|Si|)+B)2 .
Theorem 2. Let A be a symmetric sign prediction algorithm whose output, for a user i ∈ [m], on a training sample S we denote by fiS, and let l be a bounded sign prediction loss function such that 0 ≤ l(fi, (xij , yij ), (xik , yik )) ≤ B for all fi : X → R and (xij , yij ), (xik , yik ) ∈ (X × Y). Let A have uniform loss stability β : N → R with respect to l and uniform score stability ν : N → R. Then, we must have β(|Si|) = 2ν(|Si|). Furthermore, for any 0 ≤ δ ≤ 1, the following holds with probability at least 1 - δ over the draw of S
Proof. Without introducing any ambiguity, for the purpose of this proof, we succinctly denote St,z i′ ,i′′ by S′ . Now, to prove β(|Si|) = 2ν(|Si|), we need to show for (xij , yij ), (xik , yik ) ∈ (X × Y),
In order to avoid triviality of the result, let us assume without loss of generality that
It is easy to argue that we must have
max (fS(xji ) - fS(xki ), fS′(xji ) - fS′(xki )) < yij - yik , whence
The theorem follows immediately by substituting this result in Theorem 1.
4.1 Stability Results
A stable algorithm is understood to be one whose output does not change significantly with a small change in the input. In this section, we derive the stability bounds for our algorithm. Consider the following regularized empirical l-error of a sign prediction function fi ∈ Fi with respect to a sample S and a regularization parameter λi > 0, where Fi ⊆ F is a class of real valued functions and N : F → R+ ∪{0} is a regularized functional: ˆRλ l (fi; S) = ˆRl(fi; S) +λiN(fi).
Let fiS ∈ F denote the minimizer of this regularized empirical error on S, i.e., fiS = argminfi∈Fi ˆRλ l (fi; S).
Lemma 1. Let Fi ⊆ F be a class of real-valued functions on X. Let l be a sign prediction loss function that is convex in fi, and let σ > 0 be such that l is σ-admissible with respect to Fi. Let λi > 0 and let N : F → R+ ∪ {0} be a functional defined on F such that for any sample S, the regularized empirical l-error ˆRλ l (fi; S) has a minimizer (not necessarily unique) fiS in F. Then for any p ∈ [0, 1],
Proof. We have, for any p ∈ [0, 1], using the convexity of ˆRl(fiS; S) in f (since l is convex in f):
Since F is convex, (fiS +p∆fiS; S), (fiSt,z i′,i′′ -p∆fiS; S) ∈ F. Further, since fiS and fiSt,z i′,i′′ are, respectively, the minimizers of ˆRλ l (fi; S) and ˆRλ l (fi; St,z i′ ,i′′ ), we must have
The result follows by combining (1), (2), (3) and (4).
4.2 Regularization in the Hilbert Space
We now prove that MF-LiSP can be used for efficient sign prediction in a Reproducible Kernel Hilbert Space (RKHS).
Theorem 3. Let F be an RKHS with kernel K such that for all x ∈ X,K(x, x) ≤ κ2 < ∞. Let l be a sign prediction loss function that is convex in fi ∈ Fi ⊆ F, and let σ > 0 be such that l is σ-admissible with respect to F. Let λi > 0, and let A be a sign prediction algorithm that, given a training sample S, outputs a sign prediction function fiS ∈ Fi that satisfies fiS = argminfi∈Fi { ˆRl(fi; S) + λi||fi||2K }. Then A has uniform score stability ν given by ν(|Si|) = 8σκ2 λi|Si| . Furthermore, for any 0 < δ ≤ 1, the following holds with probability at least 1 - δ over the draw of S:
Proof. Let N(f) = ||f||2K . Then, defining∆fiS = fiSt,z i′ ,i′′ - fiS and applying Lemma 1 with p = 0.5, we get
Applying the Cauchy-Schwarz inequality in conjunction with reproducing property of the RKHS, we have for all x ∈ X and all f ∈ F,
Since F is an RKHS and ∆fiS ∈ F, therefore 1 2 ||∆fiS ||2K
which yields ||∆fiS||K ≤ 8σκ λi|Si| . Using (6), the following holds for all x ∈ X ,
Thus, ν(|Si|) = 8σκ2 λi|Si| . The error bound follows immediately from Theorem 2.
5 Logistic Regression based Approach
The Logistic Regression model [8] provides a sound approach to address the link label prediction problem. As suggested in [8], we represent each signed edge as a 23-dimensional vector of following features: (a) 7 features based on (signed) degree on nodes that include the embeddedness of an edge, which corresponds to the number of neighbors its vertices have in common; and (b) 16 features corresponding to 16 triads involving that edge [8]. We use the following model for predicting the sign of an edge x (in the test set) represented as a vector of k features (x1, . . . , xk)
where the parameters w0, . . . ,wk are estimated using the training data. Note that in [8], the logistic regression model is trained on the entire set of the edges except for a test edge (Leave-one-out (LOO) analysis is conducted using each edge as a test edge exactly once). The same model can be readily extended to applications that generate limited training data, and learn the model on the training data all at once.
6 Empirical Evaluation
We evaluated the empirical performance of MF-LiSP and logistic regression (LR) using both the synthetic and real world data sets. We observed the performance of LR based approach for three different sets of features: 7-dimensional vector of degree features, 16-dimensional vector of triad features and 23-dimensional vector of all features. We first describe the network data sets that we used for our experiments.
Real World Network Data Set: We carried out experiments on the voting network of Wikipedia, henceforth referred to as the Wiki-Vote data set. The network comprises 7118 users and 107080 links among these users. Each of these 107080 links is signed: the sign of each link indicates a positive or negative vote by a user about the promotion in status to admin for some other user. Out of these 107080 links, 78.41% are positive and the rest negative. We employed three-fold cross validation, i.e., two-thirds of the data was used for training and the rest for testing.
Synthetic Data Sets: We generated two datasets each comprising 10000 users drawn randomly from real-world datasets Epinions and Slashdot, so that the network structure and distribution of links in these synthetic data sets closely follows the real-world social networks.
For all the data sets, we executed our experiments over 10 runs and then averaged the results to account for statistical significance. We compared the link sign prediction accuracy of methods based on MF-LiSP and LR with two baseline heuristics, namely random and weighted random. In the context of random sign prediction method, we randomly predict the sign of any given link to be either positive or negative. Note that the distribution of the positive and negative links could be very skewed (e.g. in the Wiki-Vote data set about 78.41% of the links are positive). To take into account this skewness, for any given link, we also predicted the sign of this link to be positive or negative in proportion to the respective share, and we refer to this as the weighted method.
We followed the methodology of Leskovec et al. [8] to evaluate the performance of these methods for different threshold embeddedness, Em. Specifically in the case of logistic regression, as described in Section 5, we represented each signed edge as a 23-dimensional vector (of which 16 features (triads) become relevant only when the edge vertices have common neighbors). Therefore, we expect LR methods to perform better with increasing embeddedness. In our experiments, we used three different levels of minimum embeddedness, Em = 0 (no filtering), Em = 10 and Em = 25.


(a) Epinions Dataset

To bring forth the importance of pairwise loss function, we present the results in Fig. 1 comparing the pointwise and pairwise loss functions for weighted MF-LiSP with Em = 0. Clearly, our pairwise loss function helps in reducing the classification error relative to the pointwise loss function. We also report the prediction accuracy of the MF-LiSP, LR and random methods with uniform and weighted priors on the synthetic (Figure 2.a and 2.b) and Wiki-Vote (Figure 3) data sets, for varying threshold on embeddedness, Em. Note that we do not include the results for weighted LR methods, as performance gain for LR is achieved using increasing level of minimum embeddedness, Em and we observe that due to greater dependency of LR on features, a weighted prior does not make significant difference.
From the results with Em = 0, i.e. considering all the edges irrespective of their embeddedness, we can clearly infer that MF-LiSP and LR methods outperform the random and the weighted random heuristics. Furthermore, although MF-LiSP has a comparable (slightly inferior) performance to LR, it is crucial to note that determining the important set of features, as required by LR, might not be feasible in all scenarios (for instance, due to privacy issues). MF-LiSP overcomes the need of using features for the learning task, and hence is very generic in its applicability.

The experiments for Em = {10, 25} show that the LR model is most effective for edges with higher embeddedness, while MF-LiSP is robust to varying embeddedness. Naturally, the embeddedness of the edges has no effect on the random methods. Therefore, LR is more useful in specific scenarios, e.g., when the nodes in the network are well connected to each other. However, since in general the social networks exhibit strong connectivity, we expect LR to perform well across a wide spectrum of network topologies.
7 Conclusions
We introduced the link label prediction problem: simultaneously predict the label of several links in social networks, and proposed a technique, MF-LiSP, for this problem. We provided strong generalization guarantees for MF-LiSP thereby theoretically establishing its efficacy for link label prediction. Since the bounds are generic, MF-LiSP can be readily adapted to more generic social network settings (e.g. when no links or only unsigned links are considered), or other domains (e.g. recommender systems). To the best of our knowledge, MF-LiSP is the first technique that has provable guarantees for the general link label prediction problem. We also investigated the applicability of the logistic regression based method [8] in the multiple label prediction setting. Both the techniques outperform the random and weighted-random heuristics on several synthetic data sets and real world benchmarks.
@inproceedings{ijcai2013p382,
title = {Link Label Prediction in Signed Social Networks},
author = {Agrawal, Priyanka and Garg, Vikas K. and Narayanam, Ramasuri},
booktitle = {Proceedings of the Twenty-Third International Joint Conference on
Artificial Intelligence, {IJCAI-13}},
publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
editor = {Francesca Rossi},
pages = {2591--2596},
year = {2013},
month = {8},
url = {https://ijcai.org/proceedings/2013/382},
}
TY - CPAPER TI - Link Label Prediction in Signed Social Networks AU - Agrawal, Priyanka AU - Garg, Vikas K. AU - Narayanam, Ramasuri T2 - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13 PB - AAAI Press / International Joint Conferences on Artificial Intelligence PY - 2013 SP - 2591 EP - 2596 UR - https://ijcai.org/proceedings/2013/382 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: