Journal Home > Volume 2 , Issue 1

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 GuFei GaoRuiqi 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:

network representation, link prediction, deep learning
Received: 01 December 2020 Accepted: 04 January 2021 Published: 16 February 2021 Issue date: March 2021
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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[20]
A. L. Barabási and R. Albert, Emergence of scaling in random networks, Science, vol. 286, no. 5439, pp. 509-512, 1999.
[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.
[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
[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.
[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.
[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.
[27]
G. Rücker, Network meta-analysis, electrical networks and graph theory, Res. Synth. Methods, vol. 3, no. 4, pp. 312-324, 2012.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
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