Journal Home > Volume 2 , Issue 1
Journal of Social Computing 2021, 2(1): 43-51 https://doi.org/10.23919/JSC.2021.0001
Open Access | Issue | Published: 16 February 2021

Learning Universal Network Representation via Link Prediction by Graph Convolutional Neural Network

Show Author's Information Weiwei Gu,  Fei Gao,  Ruiqi Li( ),  Jiang Zhang( )
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China
School of Systems Science, Beijing Normal University, Beijing 100875, China
Keywords:
deep learning, link prediction, network representation
Cite this article:
Gu W, Gao F, Li R, et al. Learning Universal Network Representation via Link Prediction by Graph Convolutional Neural Network. Journal of Social Computing, 2021, 2(1): 43-51. https://doi.org/10.23919/JSC.2021.0001
Download citation
EndNote(RIS)
BibTeX

1098

Views

110

Downloads

Citations

17

Crossref

N/A

WoS

23

Scopus

N/A

CSCD

Abstract Full text About this article

Network representation learning algorithms, which aim at automatically encoding graphs into low-dimensional vector representations with a variety of node similarity definitions, have a wide range of downstream applications. Most existing methods either have low accuracies in downstream tasks or a very limited application field, such as article classification in citation networks. In this paper, we propose a novel network representation method, named Link Prediction based Network Representation (LPNR), which generalizes the latest graph neural network and optimizes a carefully designed objective function that preserves linkage structures. LPNR can not only learn meaningful node representations that achieve competitive accuracy in node centrality measurement and community detection but also achieve high accuracy in the link prediction task. Experiments prove the effectiveness of LPNR on three real-world networks. With the mini-batch and fixed sampling strategy, LPNR can learn the embedding of large graphs in a few hours.


menu
Abstract
Full text
Outline
About this article

Learning Universal Network Representation via Link Prediction by Graph Convolutional Neural Network

Show Author's information Weiwei Gu, Fei Gao, Ruiqi Li( ), Jiang Zhang( )
College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China
School of Systems Science, Beijing Normal University, Beijing 100875, China

Abstract

Network representation learning algorithms, which aim at automatically encoding graphs into low-dimensional vector representations with a variety of node similarity definitions, have a wide range of downstream applications. Most existing methods either have low accuracies in downstream tasks or a very limited application field, such as article classification in citation networks. In this paper, we propose a novel network representation method, named Link Prediction based Network Representation (LPNR), which generalizes the latest graph neural network and optimizes a carefully designed objective function that preserves linkage structures. LPNR can not only learn meaningful node representations that achieve competitive accuracy in node centrality measurement and community detection but also achieve high accuracy in the link prediction task. Experiments prove the effectiveness of LPNR on three real-world networks. With the mini-batch and fixed sampling strategy, LPNR can learn the embedding of large graphs in a few hours.

Keywords: deep learning, link prediction, network representation

References(41)

[1]
X. Chen, M. X. Liu, and G. Y. Yan, Drug-target interaction prediction by random walk on the heterogeneous network, Mol. BioSyst., vol. 8, no. 7, pp. 1970-1978, 2012.
DOI Google Scholar
[2]
M. Campillos, M. Kuhn, A. C. Gavin, L. J. Jensen, and P. Bork, Drug target identification using side-effect similarity, Science, vol. 321, no. 5886, pp. 263-266, 2008.
DOI Google Scholar
[3]
J. L. Zhou, A. Zeng, Y. Fan, and Z. R. Di, Ranking scientific publications with similarity-preferential mechanism, Scientometrics, vol. 106, no. 2, pp. 805-816, 2016.
DOI Google Scholar
[4]
M. Belkin and P. Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, in Proc. 14th Int. Conf. Neural Information Processing Systems: Natural and Synthetic, Cambridge, MA, USA, 2001, pp. 585-591.
[5]
M. Balasubramanian, E. L. Schwartz, J. B. Tenenbaum, V. De Silva, and J. C. Langford, The isomap algorithm and topological stability, Science, vol. 295, no. 5552, p. 7, 2002.
DOI Google Scholar
[6]
C. Yang, Z. Y. Liu, D. L. Zhao, M. S. Sun, and E. Y. Chang, Network representation learning with rich text information, in Proc. 24th Int. Conf. Artificial Intelligence, Halifax, Canada, 2015, pp. 2111-2117.
[7]
B. Perozzi, R. Al-Rfou, and S. Skiena, Deepwalk: Online learning of social representations, in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 701-710.
DOI
[8]
A. Grover and J. Leskovec, node2vec: Scalable feature learning for networks, in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2016, pp. 855-864.
DOI
[9]
K. M. He, X. Y. Zhang, S. Q. Ren, and J. Sun, Deep residual learning for image recognition, in Proc. IEEE Conf. Computer Vision and Pattern Recognition, Las Vegas, NV, USA 2016, pp. 770-778.
DOI
[10]
J. Gehring, M. Auli, D. Grangier, and Y. N. Dauphin, A convolutional encoder model for neural machine translation, arXiv preprint arXiv: 1611.02344, 2016.
DOI
[11]
S. S. Cao, W. Lu, and Q. K. Xu, Deep neural networks for learning graph representations, in Proc. 30th AAAI Conf. Artificial Intelligence, Phoenix, AZ, USA, 2016, pp. 1145-1152.
[12]
D. X. Wang, P. Cui, and W. W. Zhu, Structural deep network embedding, in Proc. 22nd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2016, pp. 1225-1234.
DOI
[13]
T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks, arXiv preprint arXiv: 1609.02907v4, 2016.
[14]
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, Graph attention networks, arXiv preprint arXiv: 1710.10903, 2017.
[15]
M. Defferrard, X. Bresson, and P. Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering, in Proc. 30th Int. Conf. Neural Information Processing Systems, Red Hook, NY, USA, 2016, pp. 3844-3852.
[16]
W. L. Hamilton, Z. Ying, and J. Leskovec, Inductive representation learning on large graphs, presented at Advances in Neural Information Processing Systems, Los Angele, CA, USA, 2017, pp. 1024-1034.
[17]
J. Chen, T. F. Ma, and C. Xiao, FastGCN: Fast learning with graph convolutional networks via importance sampling, arXiv preprint arXiv: 1801.10247, 2018.
[18]
F. Papadopoulos, M. Kitsak, M. Á. Serrano, M. Boguňá, and D. Krioukov, Popularity versus similarity in growing networks, Nature, vol. 489, no. 7417, pp. 537-540, 2012.
DOI Google Scholar
[19]
Ö. Şimşek and D. Jensen, Navigating networks by using homophily and degree, Proc. Natl. Acad. Sci. USA, vol. 105, no. 35, pp. 12 758-12 762, 2008.
Google Scholar
[20]
A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science, vol. 286, no. 5439, pp. 509-512, 1999.
DOI Google Scholar
[21]
Y. Wu, T. Z. Fu, and D. M. Chiu, Generalized preferential attachment considering aging, J. Informetr., vol. 8, no. 3, pp. 650-658, 2014.
DOI Google Scholar
[22]
M. Craven, D. DiPasquo, D. Freitag, A. McCallum, T. Mitchell, K. Nigam, and S. Slattery, Learning to construct knowledge bases from the world wide web, Artif. Intellig., vol. 118, nos. 1 & 2, pp. 69-113, 2000.
DOI Google Scholar
[23]
A. Popescul and L. H. Ungar, Statistical relational learning for link prediction, in Proc. Workshop on Learning Statistical Models from Relational Data at IJCAI-2003, Acapulco, Mexico, 2003.
[24]
D. Liben-Nowell and J. Kleinberg, The link-prediction problem for social networks, J. Am. Soc. Inf. Sci. Technol., vol. 58, no. 7, pp. 1019-1031, 2007.
DOI Google Scholar
[25]
T. Zhou, L. Y. Lü, and Y. C. Zhang, Predicting missing links via local information, Eur. Phys. J. B, vol. 71, no. 4, pp. 623-630, 2009.
DOI Google Scholar
[26]
H. F. Liu, Z. Hu, H. Haddadi, and H. Tian, Hidden link prediction based on node centrality and weak ties, EPL(Europhys. Lett.), vol. 101, no. 1, p. 18004, 2013.
DOI Google Scholar
[27]
G. Rücker, Network meta-analysis, electrical networks and graph theory, Res. Synth. Methods, vol. 3, no. 4, pp. 312-324, 2012.
DOI Google Scholar
[28]
A. Clauset, C. Moore, and M. E. J. Newman, Hierarchical structure and the prediction of missing links in networks, Nature, vol. 453, no. 7191, pp. 98-101, 2008.
DOI Google Scholar
[29]
Z. Huang, Link prediction based on graph topology: The predictive value of the generalized clustering coefficient, presented at LinkKDD’06, Philadelphia, PA, USA, 2006.
[30]
R. H. Byrd, G. M. Chin, J. Nocedal, and Y. C. Wu, Sample size selection in optimization methods for machine learning, Mathemat. Programm., vol. 134, no. 1, pp. 127-155, 2012.
DOI Google Scholar
[31]
M. Li, T. Zhang, Y. Q. Chen, and A. J. Smola, Efficient mini-batch training for stochastic optimization, in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 661-670.
DOI
[32]
T. Mikolov, K. Chen, G. Corrado, and J. Dean, Efficient estimation of word representations in vector space, arXiv preprint arXiv: 1301.3781v3, 2013.
[33]
J. Devlin, M. W. Chang, K. Lee, and K. Toutanova, BERT: Pre-training of deep bidirectional transformers for language understanding, arXiv preprint arXiv: 1810.04805v2, 2018.
[34]
J. Tang, M. Qu, M. Z. Wang, M. Zhang, J. Yan, and Q. Z. Mei, Line: Large-scale information network embedding, in Proc. 24th Int. Conf. World Wide Web, Republic and Canton of Geneva, Florence, Italy, 2015, pp. 1067-1077.
DOI
[35]
X. Glorot and Y. Bengio, Understanding the difficulty of training deep feedforward neural networks, J. Mach. Learn. Res., vol. 9, pp. 249-256, 2010.
Google Scholar
[36]
D. P. Kingma and J. Ba, Adam: A method for stochastic optimization, arXiv preprint arXiv: 1412.6980, 2014.
[37]
T. N. Kipf and M. Welling, Variational graph auto-encoders, arXiv preprint arXiv: 1611.07308, 2016.
[38]
L. C. Freeman, Centrality in social networks conceptual clarification, Soc. Networks, vol. 1, no. 3, pp. 215-239, 1978.
DOI Google Scholar
[39]
W. W. Gu, L. Gong, X. D. Lou, and J. Zhang, The hidden flow structure and metric space of network embedding algorithms based on random walks, Sci. Rep., vol. 7, p. 13114, 2017.
DOI Google Scholar
[40]
D. S. Wang, C. M. Song, and A. L. Barabási, Quantifying long-term scientific impact, Science, vol. 342, no. 6154, pp. 127-132, 2013.
DOI Google Scholar
[41]
V. D. Blondel, J. L. Guillaume, R. Lambiotte, and E. Lefebvre, Fast unfolding of communities in large networks, J. Statist. Mechan.: Theory Exp., vol. 2008, p. P10008, 2008.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 01 December 2020
Accepted: 04 January 2021
Published: 16 February 2021
Issue date: March 2021

Copyright

© The author(s) 2021

Acknowledgements

We acknowledge the support from the program of the China Scholarships Council (No. 201806040107), the Fundamental Research Funds for the Central Universities, the National Natural Science Foundation of China (Nos. 61673070 and 61903020), and the BUCT Talent Start-up Fund (No. BUCTRC 201825). We acknowledge the help from the Swarma Club.

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return