Abstract
In the era of big data, the study of networks has received an enormous amount of attention. Of recent interest is network embedding—learning representations of the nodes of a network in a low dimensional vector space, so that the network structural information and properties are maximally preserved. In this paper, we present a review of the latest developments on this topic. We compare modern methods based on matrix factorization, including GraRep [5], HOPE [22], DeepWalk [23], and node2vec [12], in a collection of 12 real-world networks. We find that the performance of methods depends on the applications and the specific characteristics of the networks. There is no clear winner for all of the applications and in all of the networks. In particular, node2vec exhibits relatively reliable performance in the multi-label classification application, while HOPE demonstrates success in the link prediction application. Moreover, we provide suggestions on how to choose a method for practical purposes in terms of accuracy, speed, stability, and prior knowledge requirement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
- 5.
- 6.
- 7.
- 8.
- 9.
- 10.
The similar reason also applies to the Cora and Citeseer networks.
References
Ahmed, A., Shervashidze, N., Narayanamurthy, S., Josifovski, V., Smola, A.J.: Distributed large-scale natural graph factorization. In: Proceedings of the 22nd International World Wide Web Conference, WWW 2013, Rio de Janeiro, Brazil, pp. 37–48 (2013)
Barabási, A.L.: Linked: The New Science of Networks. Perseus Publishing, Cambridge (2002)
Bhagat, S., Cormode, G., Muthukrishnan, S.: Node classification in social networks. In: Social Network Data Analytics, pp. 115–148 (2011)
Cai, H., Zheng, V.W., Chang, K.C.C.: A comprehensive survey of graph embedding: problems, techniques and applications. arXiv preprint arXiv:1709.07604 (2017)
Cao, S., Lu, W., Xu, Q.: GraRep: learning graph representations with global structural information. In: Proceedings of the 24th ACM Conference on Information and Knowledge Management, CIKM 2015, Melbourne, Australia, pp. 891–900 (2015)
Cao, S., Lu, W., Xu, Q.: Deep neural networks for learning graph representations. In: Proceedings of 20th AAAI Conference on Artificial Intelligence, AAAI 2016, Phoenix, AZ, USA, pp. 1145–1152 (2016)
Chen, S., Niu, S., Akoglu, L., Kovačević, J., Faloutsos, C.: Fast, warped graph embedding: unifying framework and one-click algorithm. arXiv preprint arXiv:1702.05764 (2017)
Faerman, E., Borutta, F., Fountoulakis, K., Mahoney, M.W.: LASAGNE: locality and structure aware graph node embedding. arXiv preprint arXiv:1710.06520 (2017)
GarcĂa-Durán, A., Niepert, M.: Learning graph embeddings with embedding propagation. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS 2017, Long Beach, CA, USA (2017)
Getoor, L., Diehl, C.P.: Link mining: a survey. ACM SIGKDD Explor. Newsl. 7(2), 3–12 (2005)
Goyal, P., Ferrara, E.: Graph embedding techniques, applications, and performance: a survey. arXiv preprint arXiv:1705.02801 (2017)
Grover, A., Leskovec, J.: node2vec: scalable feature learning for networks. In: Proceedings of the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2016, San Francisco, CA, USA, pp. 855–864 (2016)
Hamilton, W.L., Ying, R., Leskovec, J.: Representation learning on graphs: methods and applications. arXiv preprint arXiv:1709.05584 (2017)
Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations, ICLR 2017, Toulon, France (2017)
Levy, O., Goldberg, Y.: Neural word embedding as implicit matrix factorization. In: Proceedings of the 27th International Conference on Neural Information Processing Systems, NIPS 2014, pp. 2177–2185 (2014)
Lü, L., Medo, M., Yeung, C.H., Zhang, Y., Zhang, Z., Zhou, T.: Recommender systems. Phys. Rep. 519, 1–49 (2012)
Lü, L., Zhou, T.: Link prediction in complex networks: a survey. Physica A 390, 1150–1170 (2011)
Mikolov, T., Chen, K., Corrado, G., Dean, J.: Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 (2013)
Mikolov, T., Sutskever, I., Chen, K., Corrado, G., Dean, J.: Distributed representations of words and phrases and their compositionality. In: Proceedings of the 26th International Conference on Neural Information Processing Systems, NIPS 2013, pp. 3111–3119 (2013)
Newman, M.E.J.: Modularity and community structure in networks. Proc. Natl. Acad. Sci. USA 103(23), 8577–8582 (2006)
Newman, M.E.J.: Networks: An Introduction. Oxford University Press, New York (2010)
Ou, M., Cui, P., Pei, J., Zhang, Z., Zhu, W.: Asymmetric transitivity preserving graph embedding. In: Proceedings of the 22nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2016, San Francisco, CA, USA, pp. 1105–1114 (2016)
Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: online learning of social representations. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2014, New York, NY, USA, pp. 701–710 (2014)
Pržulj, N., Malod-Dognin, N.: Network analytics in the age of big data. Science 353(6295), 123–124 (2016)
Qiu, J., Dong, Y., Ma, H., Li, J., Wang, K., Tang, J.: Network embedding as matrix factorization: unifying DeepWalk, LINE, PTE, and node2vec. In: Proceedings of the 11th ACM International Conference on Web Search and Data Mining, WSDM 2018 (2018)
Ribeiro, L.F.R., Saverese, P.H.P., Figueiredo, D.R.: struc2vec: learning node representations from structural identity. In: Proceedings of the 23rd ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2017, Halifax, Nova Scotia, Canada, pp. 385–394 (2017)
Scholtes, I.: Understanding complex systems: when big data meets network science. IT Inf. Technol. 57(4), 252–256 (2015)
Tang, J., Qu, M., Mei, Q.: PTE: predictive text embedding through large-scale heterogeneous text networks. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2015, Sydney, Australia, pp. 1165–1174 (2015)
Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: LINE: large-scale information network embedding. In: Proceedings of the 24th International World Wide Web Conference, WWW 2015, Florence, Italy, pp. 1067–1077 (2015)
Tang, L., Liu, H.: Relational learning via latent social dimensions. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2009, pp. 817–826 (2009)
Tang, L., Liu, H.: Leveraging social media networks for classification. Data Min. Knowl. Discov. 23(3), 447–478 (2011)
Tu, C., Zhang, W., Liu, Z., Sun, M.: Max-Margin DeepWalk: discriminative learning of network representation. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, pp. 3889–3895 (2016)
Wang, X., Cui, P., Wang, J., Pei, J., Zhu, W., Yang, S.: Community preserving network embedding. In: Proceedings of the 21st AAAI Conference on Artificial Intelligence, AAAI 2017, San Francisco, CA, USA, pp. 203–209 (2017)
Yang, C., Liu, Z., Zhao, D., Sun, M., Chang, E.: Network representation learning with rich text information. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, Austin, TX, USA, pp. 2111–2117 (2015)
Yang, C., Sun, M., Liu, Z., Tu, C.: Fast network embedding enhancement via high order proximity approximation. In: Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, pp. 3894–3900 (2017)
Acknowledgment
This paper is based on results obtained from a project commissioned by the New Energy and Industrial Technology Development Organization (NEDO).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Liu, X., Kim, KS. (2018). A Comparative Study of Network Embedding Based on Matrix Factorization. In: Tan, Y., Shi, Y., Tang, Q. (eds) Data Mining and Big Data. DMBD 2018. Lecture Notes in Computer Science(), vol 10943. Springer, Cham. https://doi.org/10.1007/978-3-319-93803-5_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-93803-5_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-93802-8
Online ISBN: 978-3-319-93803-5
eBook Packages: Computer ScienceComputer Science (R0)