A directed link prediction method using graph convolutional network based on social ranking theory

Abstract

Graph convolutional networks (GCN) have recently emerged as powerful node embedding methods in network analysis tasks. Particularly, GCNs have been successfully leveraged to tackle the challenging link prediction problem, aiming at predicting missing links that exist yet were not found. However, most of these models are oriented to undirected graphs, which are limited to certain real-life applications. Therefore, based on the social ranking theory, we extend the GCN to address the directed link prediction problem. Firstly, motivated by the reciprocated and unreciprocated nature of social ties, we separate nodes in the neighbor subgraph of the missing link into the same, a higher-ranked and a lower-ranked set. Then, based on the three kinds of node sets, we propose a method to correctly aggregate and propagate the directional information across layers of a GCN model. Empirical study on 8 real-world datasets shows that our proposed method is capable of reserving rich information related to directed link direction and consistently performs well on graphs from numerous domains.

Keywords

Link prediction graph convolutional networks directed graphs social ranking theory

Get full access to this article

View all access options for this article.

References

Adamic

L.A.

and Adar

, Friends and neighbors on the web, Soc. Networks 25(3) (2003), 211–230.

Aiello

Barrat

Schifanella

Cattuto

Markines

and Menczer

, Friendship prediction and homophily in social media, ACM Trans. Web 6(2) (2012), 9:1–9:33.

Atwood

and Towsley

, Diffusion-convolutional neural networks, in: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain, December 5–10, 2016, pp. 1993–2001.

Ball

and Newman

, Friendship networks and social status, Netw. Sci. 1(1) (2013), 16–30.

Barabasi

Jeong

Neda

Ravasz

Schubert

and Vicsek

, Evolution of the social network of scientific collaborations, Physica A-statistical Mechanics and Its Applications 311(3) (2002), 590–614.

Boscaini

Masci

Rodola

and Bronstein

, Learning shape correspondence with anisotropic convolutional neural networks, in: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain, December 5–10, 2016, pp. 3189–3197.

Bruna

Zaremba

Szlam

and Lecun

, Spectral networks and locally connected networks on graphs, in: 2nd International Conference on Learning Representations, Banff, AB, Canada, April 14–16, 2014.

Chen

Zhu

and Song

, Stochastic training of graph convolutional networks with variance reduction, in: Proceedings of the 35th International Conference on Machine Learning, Stockholmsmässan, Stockholm, Sweden, Vol. 80, July 10–15, 2018, pp. 941–949.

Davis

D.A.

Lichtenwalter

R.N.

and Chawla

N.V.

, Supervised methods for multi-relational link prediction, Social Netw. Analys. Mining 3(2) (2013), 127–141.

10.

Davis

and Leinhardt

, The structure of positive interpersonal relations in small groups, Sociological Theories in Progress 2(54) (1972), 218–251.

11.

Defferrard

Bresson

and Vandergheynst

, Convolutional neural networks on graphs with fast localized spectral filtering, in: Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, Barcelona, Spain, December 5–10, 2016, pp. 3837–3845.

12.

Garlaschelli

and Loffredo

, Patterns of link reciprocity in directed networks, Physical Review Letters 93(26) (2004), 268701.

13.

Gasulla

, Link prediction in large directed graphs, PhD thesis, Universitat Politecnica de Catalunya, 2015.

14.

Grover

and Leskovec

, Node2vec: scalable feature learning for networks, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13–17, 2016, pp. 855–864.

15.

Heider

, Attitudes and cognitive organization, The Journal of Psychology 21(1) (1946), 107–112.

16.

Huang

Zhang

Rong

and Huang

, Adaptive sampling towards fast graph representation learning, in: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, Montréal, Canada, December 3–8, 2018, pp. 4563–4572.

17.

Kampffmeyer

Chen

Liang

Wang

Zhang

and Xing

, Rethinking knowledge graph propagation for zero-shot learning, in: IEEE Conference on Computer Vision and Pattern Recognition, Long Beach, CA, USA, June 16–20, 2019, pp. 11487–11496.

18.

Katz

, A new status index derived from sociometric analysis, Psychometrika 18(1) (1953), 39–43.

19.

Kipf

T.N.

and Welling

, Semi-supervised classification with graph convolutional networks, in: 5th International Conference on Learning Representations, Toulon, France, April 24–26, 2017.

20.

Laishram

, Link prediction in dynamic weighted and directed social network using supervised learning, Master’s thesis, Syracuse University, 2015.

21.

Liu

Chen

and Wang

, A potential information capacity index for link prediction of complex networks based on the cannikin law, Entropy 21(9) (2019), 863.

22.

Libennowell

and Kleinberg

, The link-prediction problem for social networks, Journal of the Association for Information Science and Technology 58(7) (2007), 1019–1031.

23.

Lichtenwalter

Lussier

and Chawla

, New perspectives and methods in link prediction, in: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, July 25–28, 2010, pp. 243–252.

24.

Liu

and Bai

, Similarity indices based on link weight assignment for link prediction of unweighted complex networks, International Journal of Modern Physics B 31(2) (2017), 1650254.

25.

Jin

and Zhou

, Similarity index based on local paths for link prediction of complex networks, Physical Review E 80(4) (2009), 046122–046122.

26.

and Zhou

, Link prediction in complex networks: a survey, Physica A-statistical Mechanics and Its Applications 390(6) (2011), 1150–1170.

27.

Masci

Boscaini

Bronstein

and Vandergheynst

, Geodesic convolutional neural networks on riemannian manifolds, in: 2015 IEEE International Conference on Computer Vision Workshop, ICCV Workshops 2015, Santiago, Chile, December 7–13, 2015, pp. 832–840.

28.

Miller

K.T.

Jordan

M.I.

and Griffiths

T.L.

, Nonparametric latent feature models for link prediction, in: Advances in Neural Information Processing Systems 22: Annual Conference on Neural Information Processing Systems 2009, Vancouver, British Columbia, Canada, December 7–10, 2009, pp. 1276–1284.

29.

Milo

Shenorr

Itzkovitz

Kashtan

Chklovskii

and Alon

, Network motifs: simple building blocks of complex networks, Science 298(5594) (2002), 824–827.

30.

Monti

Boscaini

Masci

Rodola

Svoboda

and Bronstein

M.M.

, Geometric deep learning on graphs and manifolds using mixture model cnns, in: 2017 IEEE Conference on Computer Vision and Pattern Recognition, Honolulu, HI, USA, July 21–26, 2017, pp. 5425–5434.

31.

Newman

, Clustering and preferential attachment in growing networks, Physical Review E 64(2) (2001), 025102.

32.

Niepert

Ahmed

and Kutzkov

, Learning convolutional neural networks for graphs, in: Proceedings of the 33rd International Conference on Machine Learning, New York City, NY, USA, June 19–24, 2016.

33.

Niladri

Singh

D.S.

and Sukumar

, Exploiting reciprocity toward link prediction, Knowledge and Information Systems 55(1) (2018), 1–13.

34.

Cui

Pei

Zhang

and Zhu

, Asymmetric transitivity preserving graph embedding, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13–17, 2016, pp. 1105–1114.

35.

Perozzi

Al-Rfou

and Skiena

, Deepwalk: online learning of social representations, in: The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, August 24–27, 2014, pp. 701–710.

36.

Schall

, Link prediction in directed social networks, Social Netw. Analys. Mining 4(1) (2014), 157.

37.

Shuman

Narang

Frossard

Ortega

and Vandergheynst

, The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag. 30(3) (2013), 83–98.

38.

Tang

Wang

Zhang

Yan

and Mei

, LINE: large-scale information network embedding, in: Proceedings of the 24th International Conference on World Wide Web, Florence, Italy, May 18–22, 2015, pp. 1067–1077.

39.

Wang

and Zhou

, Link prediction in social networks: the state-of-the-art, Science in China Series F: Information Sciences 58(1) (2015), 1–38.

40.

Weisfeiler

and Lehman

, A reduction of a graph to a canonical form and an algebra arising during this reduction, Nauchno-Technicheskaya Informatsia 2(9) (1968), 12–16.

41.

Pan

Chen

Long

Zhang

and Yu

, A comprehensive survey on graph neural networks, CoRR, abs/1901.00596, 2019.

42.

and Wang

, Link prediction in directed network and its application in microblog, Mathematical Problems in Engineering 2014 (2014), 1–8.

43.

Zhang

and Chen

, Link prediction based on graph neural networks, in: Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, Montréal, Canada, December 3–8, 2018, pp. 5171–5181.

44.

Zhang

and Chen

, Weisfeiler-lehman neural machine for link prediction, in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13–17, 2017, pp. 575–583.

45.

Zhang

Cui

Neumann

and Chen

, An end-to-end deep learning architecture for graph classification, in: Proceedings of the 32rd AAAI Conference on Artificial Intelligence, New Orleans, Louisiana, USA, February 2–7, 2018, pp. 4438–4445.

46.

Zhang

, Link prediction in directed and weighted networks, Master’s thesis, Xiangtan University, 2011.

47.

Zhang

Cui

and Zhu

, Deep learning on graphs: a survey, CoRR, abs/1812.04202, 2018.

48.

Zhou

Liu

and Gao

, Scalable graph embedding for asymmetric proximity, in: Proceedings of the 31st AAAI Conference on Artificial Intelligence, San Francisco, California, USA, February 4–9, 2017, pp. 2942–2948.

49.

Zhou

Cui

Zhang

Cheng

Liu

and Sun

, Graph neural networks: a review of methods and applications, CoRR, abs/1812.08434, 2018.

50.

Zhu

Zhang

Sun

Tang

Zhou

and Zhang

, Influence of reciprocal links in social networks, PLOS ONE 9(7) (2014).