Signed networks represent the real world relationships, which are both positive or negative. Recent research works focus on either discriminative or generative based models for signed network em- bedding. In this paper, we propose a generative adversarial network (GAN) model for signed network which unifies generative and discriminative models to generate the node embedding. Our ex- perimental evaluations on several datasets, like Slashdot, Epinions, Reddit, Bitcoin and Wiki-RFA indicates that the proposed approach ensures better macro F1-score than the existing state-of-the-art approaches in link prediction and handling of sparsity of signed networks.

Signed network, link prediction, generative adversarial network, structural balance theory

ACM Reference Format: Roshni Chakraborty, Ritwika Das, and Nilotpal Chakraborty. 2020. Link Prediction in Signed Networks. In 31st ACM Conference on Hypertext and Social Media (HT ’20), July 13–15, 2020, Virtual Event, USA. ACM, New York, NY, USA, 2 pages. https://doi.org/10.1145/3372923.3404805

With the increase in popularity of online social networks, a huge number of users share their views and opinions, interact with other users on these platforms. As understanding and analyzing this user behaviour can provide critical insights into user’s choices and needs, several research works have proposed different approaches to study relevant user behaviour. However, contrary to the existing social networks where relationships are measured either by the magnitude or presence and absence of links, there are signed social networks which capture both polarity and magnitude of the rela- tionship. These polarity relationships can be expressed as trustful or distrustful, friendship or animosity relationships [2]. Further, several studies indicate that the presence of negative links adds more value and information to the relationships among individ- uals [3]. Therefore, the prediction of the sign of a relationship in social networks is receiving significant attention. However, exploit- ing these signed relations between the nodes to predict the sign of a link pose newer challenges when compared to predicting links in conventional unsigned networks.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). HT ’20, July 13–15, 2020, Virtual Event, USA © 2020 Copyright held by the owner/author(s). ACM ISBN 978-1-4503-7098-1/20/07. https://doi.org/10.1145/3372923.3404805

The challenges are mainly due to the inherent differences in the properties of the signed networks from the properties of unsigned networks, like existing theories of social science, homophily, transi- tivity and social influence [2] do not apply to signed networks. As the ratio of negative links is very low compared to the positive links (as shown in table 1), it is challenging to identify the factors that can explain the formation of negative links. Subsequently, there are specific characteristics of signed networks, like structural bal- ance theory, which requires to be incorporated. In order to address these issues, several signed network based embedding approaches has been developed which can be classified into either generative or discriminative based models. While the generative model-based representation learning frameworks rely on the conditional dis- tribution of a node, 𝑣𝑏, being a neighbor of node 𝑣𝑎, given the connectivity preferences of 𝑣𝑎[1, 5], several research works have proposed discriminative based models which predict the presence of an edge based on the characteristics of the node pair, 𝑣𝑎and 𝑣𝑏[3].

Although the generative and discriminative based models repre- sent two different classes of graph representation learning, they can be visualized as two different ways of looking at the same problem [4]. Therefore, recently, research works have proposed different variants of GAN based frameworks to combine genera- tive and discriminative in a game theoretical minimax game for different applications [4]. However, none of these approaches could be directly applied to signed networks due to it’s inherent differ- ence from unsigned graphs. Hence, in this paper, we propose a signed graph GAN based approach which effectively unifies two models generative model that generates likely positive (or, negative), connected neighbors of node, 𝑣𝑎and a discriminative model that identifies whether the generated node pair with the corresponding sign is a true connection or not. Further, the proposed framework explicitly ensures structural balance theory and can handle the high imbalance in the number of negative edges to positive edges of signed networks. Validation on real world datasets, like Slashdot, Epinions, Reddit, Bitcoin and Wiki-RFA indicate that the proposed approaches ensure 2.5−10% better macro F1-score than the existing works in link prediction.

In this section, we discuss the proposed GAN framework which intends to predict the sign of an edge, 𝐸𝑎𝑏between a given pair of nodes, (𝑉𝑎,𝑉𝑏) from a signed network, 𝐺= (𝑉, 𝐸,𝑆) which com- prises of vertics, 𝑉, edges, 𝐸and sign of the edge, 𝑆∈{−1, +1}. In order to predict the link, the proposed framework intends to learn the representation of nodes considering it’s negative and positive connections through generator and discriminator while capturing structural balance theory.Therefore, given the graph𝐺, the proposed model intends to learn two models which we briefly discuss hereby.

Table 1.

(1) Discriminator function, 𝑅(𝑉𝑎,𝑉𝑏;𝜃𝑅) which outputs a sin-

gle scalar value representing the probability of an edge, rep- resented by an ordered pair, (𝑉𝑎,𝑉𝑏), being negative (or posi- tive). We use a variant of the structured deep network embed- ding (SDNE) proposed by Shen et al. [3] as the discriminator which maximizes the log-probability of assigning correct la- bel to the signed neighbour, 𝑉𝑏of 𝑉𝑎by changing the vector representations of 𝑉𝑎and 𝑉𝑏. (2) Generator function, Q(𝑉𝑏|𝑉𝑎;𝜃𝑄) that approximates the true

connections of 𝑉𝑎, i.e., by generating that neighbour of 𝑉𝑎 which has higher likeliness to be of the opposite sign from the underlying distribution 𝑝𝑡𝑟𝑢𝑒(𝑉𝑏|𝑉𝑎). In order to select the most likely positively (or, negatively) connected neigh- bour of 𝑉𝑎, i.e., 𝑉𝑏, we calculate the relevance score of likely positively(or, negatively) connected neighbours of 𝑉𝑎and select the node, 𝑉𝑏which has the highest relevance score with respect to 𝑉𝑎 Further, to ensure the proposed approach learns to predict the negative edge with high precision, we select negative edges and positive edges with equal probability for the discriminator to learn. Given the graph 𝐺, generator 𝑄and discriminator 𝑅acts as oppo- nents, i.e., 𝑄tries to generate the positive (or negative) neighbour which are similar to the actual negative (or positive) neighbours of 𝑉𝑎and discriminator 𝑅determines if the generated neighbour is an

actual negative (or positive) neighbour of 𝑉𝑎through a two player mini-max with value function V(𝑄, 𝑅), as follows :

𝑉 Õ

(E𝑉∼𝑝𝑡𝑟𝑢𝑒(·|𝑉𝑎) [log𝑅(𝑉,𝑉𝑎,𝜙;𝜃𝑅)]

V(𝑄, 𝑅) =

min

max

Θ𝑄

Θ𝑅

𝑎=1

+E𝑣∼𝑄(·|𝑉𝑎;𝜃𝑄) [log(1 −𝑅(𝑉,𝑉𝑎,𝜙;𝜃𝑅)]) (1)

Hence, the discriminator and generator alternatively learns the signed connections of 𝑉𝑎through maximizing and minimizing V(𝑄, 𝑅). The continuous rivalry between generator 𝑄and dis- criminator 𝑅along with iterative learning of both the positively(or, negatively) connected neighbours with equal probability ensures handling of the difference in negatively and positively signed links and learning of the sign of the connections. Next, we briefly discuss the discriminator and generator models.

In this section, we evaluate the performance of the proposed ap- proach in predicting the sign of a link on 5 datasets, namely Slashdot, 𝐷𝑆[3], Epinions, 𝐷𝐸[3], Reddit, 𝐷𝑅Bitcoin, 𝐷𝐵and Wikipedia, 𝐷𝑊 [3]. A brief description of the datsets in given in table 1.

For our experiments, we identify a subset of edges for training (80%) our model and the rest of the edges (20%) are used for testing.

Table 2.

The edges are selected randomly for training and testing. As there might be a significant difference between the number of negative and positive edges in the testing set, we show the performance of the proposed approach by macro F1-score which captures the effectiveness of the proposed approach in identifying both positive and negative edges. For the prediction task, we use a logistic re- gression classifier [3] that is trained on the vector representation of the edges, using the Hadamard product of the corresponding node representations. We evaluate the performance of the proposed approach and the baselines through macro F1-score. We consider macro F1-score in order to capture the effectiveness of the proposed approach in predicting the sign for both positively and negatively connected links. On comparing the performance of the proposed approach with DNE-SBP [3], SIDE [1] and SNE [5], we observe as shown in table 2 indicates the proposed approach can ensure 2.5 −10% better than the existing research works.

In this work, we have proposed a GAN based framework for signed networks that unifies two different types of graph representation learning methodologies, i.e., generative methods and discriminative methods, through adversarial training in a minimax game. Further, the proposed approach is shown to ensure explicit integration of the specific properties of the signed network, like extended structural balance theory as well as handling of the inherent issues of a signed network, like a high imbalance in sign, the sparsity of information. Experimental validation on five datasets indicates better effective- ness of the proposed approach than the existing approaches for link prediction in a signed network due to the usage of the adversarial framework. However, in this paper, we did not explore different options for the discriminator, and therefore, the study of the choice of the discriminator remains as future work.

[1] Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang. 2018. Side: representation

learning in signed directed networks. In Proceedings of the 2018 World Wide Web Conference. International World Wide Web Conferences Steering Committee, 509– 518. [2] Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010. Signed networks in

social media. In Proceedings of the SIGCHI conference on human factors in computing systems. ACM, 1361–1370. [3] Xiao Shen and Fu-Lai Chung. 2018. Deep Network Embedding for Graph Repre-

sentation Learning in Signed Networks. IEEE transactions on cybernetics (2018). [4] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng

Zhang, Xing Xie, and Minyi Guo. 2018. Graphgan: Graph representation learning with generative adversarial nets. In Thirty-Second AAAI Conference on Artificial Intelligence. [5] Shuhan Yuan, Xintao Wu, and Yang Xiang. 2017. SNE: signed network embedding.

In Pacific-Asia conference on knowledge discovery and data mining. Springer, 183– 195.