"Bridge": Enhanced Signed Directed Network Embedding

ABSTRACT

Signed directed networks with positive or negative links convey rich information such as like or dislike, trust or distrust. Existing work of sign prediction mainly focuses on triangles (triadic nodes) motivated by balance theory to predict positive and negative links. However, real-world signed directed networks can contain a good number of "bridge'' edges which, by definition, are not included in any triangles. Such edges are ignored in previous work, but may play an important role in signed directed network analysis.%Such edges serve as fundamental building blocks and may play an important role in signed network analysis.

In this paper, we investigate the problem of learning representations for signed directed networks. We present a novel deep learning approach to incorporating two social-psychologic theories, balance and status theories, to model both triangles and "bridge'' edges in a complementary manner. The proposed framework learns effective embeddings for nodes and edges which can be applied to diverse tasks such as sign prediction and node ranking. Experimental results on three real-world datasets of signed directed social networks verify the essential role of "bridge" edges in signed directed network analysis by achieving the state-of-the-art performance.

References

1. Smriti Bhagat, Graham Cormode, and S Muthukrishnan. 2011. Node classification in social networks. In Social network data analytics . Springer, 115--148.
2. Léon Bottou. 1991. Stochastic gradient learning in neural networks. Proc. of Neuro-Nimes , Vol. 91, 8 (1991).
3. Sergey Brin and Lawrence Page. 2012. Reprint of: The anatomy of a large-scale hypertextual web search engine. Computer networks , Vol. 56, 18 (2012), 3825--3833.
4. Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable Feature Learning for Networks. In Proc. of SIGKDD. 855--864.
5. Ramanthan Guha, Ravi Kumar, Prabhakar Raghavan, and Andrew Tomkins. 2004. Propagation of trust and distrust. In Proc. of WWW. ACM, 403--412.
6. Fritz Heider. 1946. Attitudes and cognitive organization. The Journal of psychology , Vol. 21, 1 (1946), 107--112.
7. Mohammad Raihanul Islam, B Aditya Prakash, and Naren Ramakrishnan. 2018. Distributed Representation of Signed Networks. In Accepted by PAKDD .
8. Jinhong Jung, Woojeong Jin, Lee Sael, and U Kang. 2016. Personalized ranking in signed networks using signed random walk with restart. In Proc. of ICDM. IEEE, 973--978.
9. Cristobald de Kerchove and Paul Van Dooren. 2008. The pagetrust algorithm: How to rank web pages when negative links are allowed?. In Proc. of SDM . SIAM, 346--352.
10. Junghwan Kim, Haekyu Park, Ji-Eun Lee, and U Kang. 2018. SIDE: Representation Learning in Signed Directed Networks. In Proc. of WWW. International World Wide Web Conferences Steering Committee, 509--518.
11. Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).
12. Jon M Kleinberg. 1999. Authoritative sources in a hyperlinked environment. JACM , Vol. 46, 5 (1999), 604--632.
13. Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010a. Predicting positive and negative links in online social networks. In Proc. of WWW. ACM, 641--650.
14. Jure Leskovec, Daniel Huttenlocher, and Jon Kleinberg. 2010b. Signed networks in social media. In Proc. of SIGCHI. ACM, 1361--1370.
15. David Liben-Nowell and Jon Kleinberg. 2007. The link-prediction problem for social networks. JASIST , Vol. 58, 7 (2007), 1019--1031.
16. Symeon Papadopoulos, Yiannis Kompatsiaris, Athena Vakali, and Ploutarchos Spyridonos. 2012. Community detection in social media. DMKD , Vol. 24, 3 (2012), 515--554.
17. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014. Deepwalk: Online learning of social representations.. In Proc. of SIGKDD . 701--710.
18. Moshen Shahriari and Mahdi Jalili. 2014. Ranking nodes in signed social networks. SNAM , Vol. 4, 1 (2014), 172.
19. Jiliang Tang, Yi Chang, Charu Aggarwal, and Huan Liu. 2016. A survey of signed network mining in social media. ACM Computing Surveys (CSUR) , Vol. 49, 3 (2016), 42.
20. Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. 2015. LINE: Large-scale Information Network Embedding. In Proc. of WWW. 1067--1077.
21. Vincent A Traag, Yurii E Nesterov, and Paul Van Dooren. 2010. Exponential Ranking: Taking into Account Negative Links.. In SocInfo. Springer, 192--202.
22. Suhang Wang, Charu Aggarwal, Jiliang Tang, and Huan Liu. 2017a. Attributed signed network embedding. In Proc. of CIKM. ACM, 137--146.
23. Suhang Wang, Jiliang Tang, Charu Aggarwal, Yi Chang, and Huan Liu. 2017b. Signed network embedding in social media. In Proc. of SDM. SIAM, 327--335.
24. Robert West, Hristo S Paskov, Jure Leskovec, and Christopher Potts. 2014. Exploiting Social Network Structure for Person-to-Person Sentiment Analysis. TACL , Vol. 2, 1 (2014), 297--310.
25. Zhaoming Wu, Charu C Aggarwal, and Jimeng Sun. 2016. The troll-trust model for ranking in signed networks. In Proc. of ICDM. ACM, 447--456.
26. Xiaofeng Yu and Junqing Xie. 2014. Learning Interactions for Social Prediction in Large-scale Networks. In Proc. of CIKM . 161--170.
27. Shuhan Yuan, Xintao Wu, and Yang Xiang. 2017. Sne: signed network embedding. In Proc. of PAKDD. Springer, 183--195.
28. Kiyana Zolfaghar and Abdollah Aghaie. 2010. Mining trust and distrust relationships in social Web applications. In Proc. of ICCP. IEEE, 73--80.

Index Terms

• Information systems

  • Information systems applications

    • Data mining