Keywords

1 Introduction

With the emergence of online social networks, individuals show more interests in participating in social intercourse on the Internet. Numerous studies focus on unsigned social networks while only a few of them have studied the signed ones. Due to the existence of negative edges, many effective unsigned social network analysis methods cannot be applied to signed social networks directly [4,5,6]. Signed social networks are usually based on balance theory [1, 2] and status theory [3], both of which are proposed by observing social phenomena. At the same time, with the rapid development of deep learning technology, many scholars have begun to adopt the idea of network embedding to solve the problem of sign prediction. Although these methods have achieved good sign prediction performance, they have some drawbacks. Firstly, most methods basing on balance theory [9, 11] obtain the node embedding by optimizing single balance triangle each edge involves during each round of training process. These methods can have some limitations: 1. The interactions between multiple triangles each edge involves are ignored. 2. Most methods only consider triangles that satisfy the balance theory, and ignore those violating the theory, which will lead to the key information loss. 3. There is no common neighbor between the two endpoints of an edge, which is called a “bridge” edge in the paper [9]. Thus, how to properly model this type of edges is also an essential aspect. Secondly, for some methods based on skip-gram models [12, 13], they use shallow models to train node embedding and cannot capture the non-linear structure information of the network well. Thirdly, a sign prediction method should fuse balance theory and status theory reasonably to obtain optimal sign prediction performance [9], but there are few methods considering both theories together. Last but not least, as stated in the paper [7], it is necessary to specifically design a solution framework for sign prediction problem.

The main contributions of this paper are:

  • This paper proposes an end-to-end framework: Deep Sign Prediction (DSP) method, which uses the deep learning technology and optimizes a loss function specifically designed for sign prediction.

  • This paper extends the balance theory by considering all possible “triangle” structures each edge involves and solves the drawbacks of former methods which only model single balanced triangle each edge involves.

  • In this paper, a two-layer neural network architecture is designed to combine the balance theory with status theory reasonably.

  • We conduct experiments and evaluations on five real signed social networks and compare the proposed DSP method with multiple state-of-the-art methods. Experimental results show that our method outperforms other methods in terms of four metrics (AUC, binary-F1, micro-F1, macro-F1).

2 Related Work

Signed Network Embedding:

Signed network embedding methods can be roughly divided into following four categories. The first category does not consider any sociological theory. In [10], Yuan et al. propose a SNE method, which uses a log-bilinear model to train the target embedding of nodes along a given path. The second category makes use of balance theory. For example, SiNE [11] method is based on the extended structural balance theory. In SIGNet [12], the authors propose a scalable signed network embedding method. In [13], Kim et al. propose the SIDE method, which fully encodes the direction and sign of the edges in the learned embedding space. The third category is based on status theory. In SSNE [14], the authors design an energy-based ranking loss function based on status theory. The last type considers both two theories. For example, the BESIDE method in [9].

Sign Prediction:

There are many methods solving sign prediction from different perspectives, apart from signed network embedding methods mentioned above. For example, in [8], Leskovec et al. manually extract degree features of the nodes and triad features of edges to train a logistic regression classifier for sign prediction. In [15], Javari et al. design a probability prediction model based on the local and global structure of networks in order to deal with the sparsity problem of signed social networks.

3 Preliminary

Signed Social Network:

A signed social network can be modeled as a directed signed graph \( G\, = \,\left( {V, E, E^{ + } , E^{ - } , S} \right) \), where \( V,E,E^{ + } ,E^{ - } \) represent the sets of all nodes, signed edges, positive edges, and negative edges in the network; \( S \) is a signed adjacency matrix, and each entry \( S_{ij} \) of \( S \) represents the relationship from node \( i \) to \( j \) (Specifically, \( S_{ij} \, = \,1, - 1, 0 \) indicates positive, negative, no relationship in the current network).

Sign Prediction:

Given a signed social network \( G \), sign prediction aims to predict the sign of edges that are not observed in current network.

4 The Proposed Method

4.1 Model “Triangle” Structures Each Edge Involves

In a signed social network, there are multiple situations for the interaction between any directed edge \( e_{ij} \) and any node \( k \). Nodes \( i, j, {\text{and }}k \) can form a triangle, which may not necessarily conform to balance theory, or they cannot even form a triangle. And, \( e_{ij} \) may be involved in multiple “triangles” at the same time. As shown in Fig. 1, without considering the edge sign, edge \( e_{ij} \) and node \( k \) can form four possible “triangle” structures (dashed line indicates that edge may not exist). Each “triangle” type corresponds to interactions between the neighbor structure of node \( i \) and that of the node \( j \) in directed edge \( e_{ij} \). For example, the first type of “triangle” corresponds to the interaction between the out-neighbor structure of node \( i \) and the in-neighbor structure of node \( j \).

Fig. 1.
figure 1

Four possible “triangle” structures each edge involves.

Full size image

According to Fig. 1, we generate a “balance” neighbor structure vector for two endpoints of the directed edge \( e_{ij} \):

$$ b\_st_{i} \, = \,\left[ {S_{i}^{out} ;S_{i}^{out} ;S_{i}^{in} ;S_{i}^{in} } \right],\,b\_en_{j} \, = \,\left[ {S_{j}^{in} ;S_{j}^{out} ;S_{j}^{in} ;S_{j}^{out} } \right] $$
(1)

in formula (1): \( b\_st_{i} \), \( b\_en_{j} \, \in \,R^{1 \times 4\left| V \right|} \); \( S_{i}^{out} \, \in \,R^{1 \times \left| V \right|} \) is the \( i \) th row of the matrix \( S \), and \( S_{i}^{in} \, \in \,R^{1 \times \left| V \right|} \) is the \( i \) th column of the matrix \( S \).

By constructing \( b\_st_{i} \) and \( b\_en_{j} \) for each edge \( e_{ij} \), and training \( b\_st_{i} \) and \( b\_en_{j} \) simultaneously, our method can consider the four “triangle” types in Fig. 1. This solution extends the balance theory and considers all possible “triangle” structures each edge involves comprehensively. Next we want to find a function \( f \), which takes \( b\_st_{i} \) or \( b\_en_{j} \) as input, and output the “balance” embedding \( b\_em_{i} \) or \( b\_em_{j} \). Namely,

$$ b\_em_{i} \, = \,f\left( {b\_st_{i} } \right),\,b\_em_{j} \, = \,f\left( {b\_en_{j} } \right) $$
(2)

in formula (2): \( b\_em_{i} \, \in \,R^{1 \times d} \) and \( d \) is the dimension of “balance” embedding.

4.2 Modeling Directed Edges by Status Theory

For a user in signed social networks, her status is determined by two parts: her “subjective” status/self-evaluation, and her “objective” status, which is evaluated by others. The “subjective”/“objective” status can be reflected by the user’s out-neighbor/in-neighbor structure. Then for a node \( i \), we want to find a function \( g\left( { \cdot , \cdot } \right) \) which inputs the \( S_{i}^{out} \) and \( S_{i}^{in} \) and outputs a “status” neighbor structure vector: \( s\_ne_{i} \).

$$ s\_ne_{i} \, = \,g\left( {S_{i}^{out} , S_{i}^{in} } \right) $$
(3)

we use the vector addition to define the function \( g \). In formula (3): \( s\_ne_{i} \, \in \,R^{1 \times \left| V \right|} \).

After obtaining the “status” neighbor vectors of node \( i \), \( j \), we will learn two functions: \( st\_h \) and \( en\_h \) to obtain the “status” embedding: \( s\_em_{i} \), \( s\_em_{j} \) respectively.

$$ s\_em_{i} \, = \,st\_h\left( {s\_ne_{i} } \right), s\_em_{j} \, = \,en\_h\left( {s\_ne_{j} } \right) $$
(4)

in formula (4): \( s\_em_{i} ,s\_em_{j} \, \in \,R^{1 \times d} \), d is the dimension of the “status” embedding.

Based on status theory, we define a status loss function \( L_{st} \), as:

$$ L_{{st_{ij} }} \, = \,{ \hbox{max} }\left( {0,\updelta - \left( {Status_{i} - Status_{j} } \right)\, \times \,\left( { - S_{ij} } \right)} \right) $$
(5)

in formula (5): \( Status_{i} \, \in \,\left( { - 1, 1} \right) \) is the status value of node \( i \), which is generated by the non-linear mapping function \( sta\_h \);

$$ Status_{i} \, = \,sta\_h\left( {s\_em_{i} } \right) $$
(6)

\( S_{ij} \) is the sign of \( e_{ij} \); \( \updelta \) is the threshold of the difference between the two status values, and we set it to 0.5 according to the previous experimental research.

4.3 Deep Sign Prediction Model

Our network architecture is divided into two parts: the first part is used to extend balance theory, and the second part is used to consider the status theory. The input of DSP is an edge. The detailed network architecture of the DSP method is shown in Fig. 2.

Fig. 2.
figure 2

Network architecture of the DSP method

Full size image

First, we use a two-layer fully connected neural network to define function \( f \).

$$ b\_em_{i} \, = \,{ \tanh }\left( {{ \tanh }\left( {b\_st_{i} W^{0} + b^{0} } \right)W^{1} + b^{1} } \right) $$
(7)

in formula (7): \( { \tanh } \) is a non-linear activation function; \( W^{0} \, \in \,R^{4\left| V \right| \times 2d} \) and \( W^{1} \, \in \,R^{2d \times d} \) are the weight parameters; \( b^{0} \, \in \,R^{1 \times 2d} \) and \( b^{1} \, \in \,R^{1 \times d} \) are the bias parameters.

For the functions \( st\_h \) and \( en\_h \), they are defined by using a layer of fully connected neural network, respectively.

$$ s\_em_{i} \, = \,\tanh \left( {s\_ne_{i} W^{2} + b^{2} } \right),\,\,s\_em_{j} \, = \,{ \tanh }\left( {s\_ne_{j} W^{3} + b^{3} } \right) $$
(8)

in formula (8): \( W^{2} \), \( W^{3} \, \in \,R^{\left| V \right| \times d} \); \( b^{2} \), \( b^{3} \, \in \,R^{1 \times d} \).

We also use a layer of fully connected neural network to define the function \( sta\_h \).

$$ Status_{i} \, = \,{ \tanh }\left( {s\_em_{i} W^{4} + b^{4} } \right) $$
(9)

in formula (9): \( W^{4} \, \in \,R^{d \times 1} \); \( b^{4} \, \in \,R^{1 \times 1} \).

Then, we concatenate “balance” embedding and “status” embedding of two endpoints of each edge as the final feature representation.

$$ final_{ij} \, = \,\left[ {b\_em_{i} ;b\_em_{j} ;s\_em_{i} ;s\_em_{j} } \right] $$
(10)

in formula (10): \( final_{ij} \, \in \,R^{1 \times 4d} \) is the final embedding vector.

For the prediction layer, we use a three-layer fully connected neural network to generate the edge’s prediction value.

$$ p_{ij} \, = \,{\text{softmax}}\left( {{\text{ReLU}}\left( {{\text{ReLU}}\left( {final_{ij} W^{5} + b^{5} } \right)W^{6} + b^{6} } \right)W^{7} + b^{7} } \right) $$
(11)

in the formula (11): \( {\text{ReLU}} \) and \( {\text{softmax}} \) are two non-linear activation functions; \( W^{5} \, \in \,R^{4d \times d} \), \( W^{6} \, \in \,R^{{d \times \frac{d}{2}}} \), and \( W^{7} \, \in \,R^{{\frac{d}{2} \times 2}} \); \( b^{5} \, \in \,R^{1 \times d} \), \( b^{6} \, \in \,R^{{1 \times \frac{d}{2}}} \), and \( b^{7} \in R^{1 \times 2} \). We use the cross-entropy loss to define the loss of sign prediction.

$$ L_{{sign_{ij} }} \, = \, - \sum\nolimits_{m} {y_{{ij_{m} }} } \log p_{{ij_{m} }} $$
(12)

in the formula (12): \( m\, \in \,\left\{ {0,1} \right\} \) is the subscript. \( y \) denotes the one-hot encoding vector of the edge sign (negative and positive); \( p \) defines the predicted probability for each type of sign (negative and positive). For the DSP method, the overall loss function is:

$$ L\, = \, \frac{1}{\left| E \right|}\sum\nolimits_{{e_{ij} \in E}} {\left( {L_{{sign_{ij} }} + L_{{st_{ij} }} } \right)} $$
(13)

The input scale of the DSP method is \( {\text{O}}\left( {\left| E \right|} \right) \). We use the Adam [17] algorithm to optimize the DSP model. The learning rate is 0.0001, and the batch size is 128.

5 Experiments

5.1 Datasets

We conduct experiments and evaluations on five real online signed social networks. The specific statistical information of five datasets is shown in Table 1.

Table 1. The statistical information of five datasets
Full size table

5.2 Baseline Methods

We compare the proposed DSP method with several state-of-the-art sign prediction methods: two feature engineering methods (All23 [8] and FxG [16]), two unsigned network embedding methods (DW [4] and N2V [6]), three signed network embedding methods (SIGNet [12], SIDE [13], and BESIDE [9]), and the part of extends balance theory in DSP model (DSP_B). For the above methods, we use the same parameters setting recommended by the original papers. For the unsigned network embedding methods, we ignore edge sign during training process. For the node embedding methods, we concatenate the node embedding to obtain the edge embedding, and then train a logistic regression model for sign prediction. Our method uses the DSP framework for sign prediction and sets the dimension of the embedding vector \( d\, = \,40 \).

5.3 Sign Prediction

As in previous studies [9], we use AUC, binary-F1, micro-F1, and macro-F1 to evaluate the performance of sign prediction. We randomly divide the datasets into a test set and a training set with a ratio of 2–8. The experimental results are shown in Table 2.

Table 2. The result of sign prediction
Full size table

From Table 2, we can see that the DSP method has obtained the best experimental results in most cases. It is better than All23 and FxG, which shows the powerful learning ability of deep model. The performance of two unsigned network embedding methods is relatively poor, which means the unsigned network embedding methods cannot adapt to sign prediction. By comparing DSP with SIGNet and SIDE, we find that using deep models and considering both balance theory and status theory together can achieve better sign prediction performance. DSP is superior to BESIDE, indicating that comprehensive consideration of all possible “triangle” structures each edge involves can capture the latent features related to sign prediction well. The results also indicate that solution framework specifically designed for sign prediction problem is crucial to achieve better sign prediction performance by comparing DSP with other methods of signed network embedding. In most cases, the DSP method is better than DSP_B, which shows that combining balance theory with status theory reasonably can achieve the best sign prediction performance.

We compare the prediction performance of each algorithm on a test set that contains only “bridge” edges. The experimental results on “bridge” edges are shown in Table 3. From Table 3, we can see that BESIDE achieves the best performance on all baseline methods, which means that BESIDE method with status theory is quite useful for modeling “bridge” edges. The proposed DSP and DSP_B methods are both superior to BESIDE, showing that considering the neighbor structures of two endpoints of each edge comprehensively, the “bridge” edges can be trained and predicted well.

Table 3. The performance of sign prediction on the “bridge” edges.
Full size table

6 Conclusion and Future Work

This paper presents a DSP method specifically for solving sign prediction task. DSP makes use of the powerful learning ability of deep learning to capture the complex structure of signed social networks. At the same time, the DSP method extends the balance theory, comprehensively considers all possible “triangle” structures each edge involves. Finally, the DSP method reasonably combines balance theory with status theory. We perform two types of comparative experiments on the five real signed social network datasets. The experimental results on four commonly used evaluation metrics show the superiority of our proposed methods.

Although DSP achieves excellent sign prediction performance, there are still some directions that can be further explored. For example, in the future, we will explore more ways of combining balance theory with status theory. Moreover, we will explore the attribute information of nodes in the next research work.