Open Access
Issue
Published:
15 October 2018
A Brief Review of Network Embedding
Yuan Yao(
),
),
Cite this article:
Wang Y, Yao Y, Tong H, et al.
A Brief Review of Network Embedding.
Big Data Mining and Analytics,
2019, 2(1): 35-47.
https://doi.org/10.26599/BDMA.2018.9020029
Download citation
723
Views
14
Downloads
Citations
40
Crossref
36
WoS
45
Scopus
0
CSCD
Learning the representations of nodes in a network can benefit various analysis tasks such as node classification, link prediction, clustering, and anomaly detection. Such a representation learning problem is referred to as network embedding, and it has attracted significant attention in recent years. In this article, we briefly review the existing network embedding methods by two taxonomies. The technical taxonomy focuses on the specific techniques used and divides the existing network embedding methods into two stages, i.e., context construction and objective design. The non-technical taxonomy focuses on the problem setting aspect and categorizes existing work based on whether to preserve special network properties, to consider special network types, or to incorporate additional inputs. Finally, we summarize the main findings based on the two taxonomies, analyze their usefulness, and discuss future directions in this area.
menu
Abstract
Full text
Outline
About this article
A Brief Review of Network Embedding
Yuan Yao(
),
),
Abstract
Learning the representations of nodes in a network can benefit various analysis tasks such as node classification, link prediction, clustering, and anomaly detection. Such a representation learning problem is referred to as network embedding, and it has attracted significant attention in recent years. In this article, we briefly review the existing network embedding methods by two taxonomies. The technical taxonomy focuses on the specific techniques used and divides the existing network embedding methods into two stages, i.e., context construction and objective design. The non-technical taxonomy focuses on the problem setting aspect and categorizes existing work based on whether to preserve special network properties, to consider special network types, or to incorporate additional inputs. Finally, we summarize the main findings based on the two taxonomies, analyze their usefulness, and discuss future directions in this area.
Keywords:
network embedding, node representations, context construction
References(80)
[1]
S. Bhagat, G. Cormode, and S. Muthukrishnan, Node classification in social networks, in Social Network Data Analytics, C. C. Aggarwal, ed. Boston, MA, USA: Springer, 2011, pp. 115-148.
[2]
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.
[3]
S. E. Schaeffer, Graph clustering, Comput. Sci. Rev., vol. 1, no. 1, pp. 27-64, 2007.
[4]
L. Akoglu, M. McGlohon, and C. Faloutsos, Oddball: Spotting anomalies in weighted graphs, in Proc. 14th Pacific-Asia Conf. Advances in Knowledge Discovery and Data Mining, Hyderabad, India, 2010, pp. 410-421.
[5]
Y. Yao, H. Tong, F. Xu, and J. Lu, Feature generation for graphs and networks, in Feature Engineering for Machine Learning and Data Analytics, C. Z. Dong and H. Liu, eds. CRC Press, 2018, pp. 167-188.
[6]
L. F. R. Ribeiro, P. H. P. Saverese, and D. R. Figueiredo, struc2vec: Learning node representations from structural identity, in Proc. 23rd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), Halifax, Canada, 2017, pp. 385-394.
[7]
Y. A. Lai, C. C. Hsu, W. H. Chen, M. Y. Yeh, and S. D. Lin, Prune: Preserving proximity and global ranking for network embedding, in Proc. 31st Conf. and Workshop on Neural Information Processing Systems (NIPS), Long Beach, CA, USA, 2017, pp. 5263-5272.
[8]
W. L. Hamilton, R. Ying, and J. Leskovec, Representation learning on graphs: Methods and applications, arXiv preprint arXiv: 1709.05584, 2017.
[9]
T. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks, in Int. Conf. Learning Representations (ICLR), Toulon, France, 2017.
[10]
P. Goyal and E. Ferrara, Graph embedding techniques, applications, and performance: A survey, arXiv preprint arXiv: 1705.02801, 2017.
[11]
D. K. Zhang, J. Yin, X. Q. Zhu, and C. Q. Zhang, Network representation learning: A survey, arXiv preprint arXiv: 1801.05852, 2017.
[12]
P. Cui, X. Wang, J. Pei, and W. W. Zhu, A survey on network embedding, arXiv preprint arXiv: 1711.08752, 2017.
[13]
H. Y. Cai, V. W. Zheng, and K. C. C. Chang, A comprehensive survey of graph embedding: Problems, techniques, and applications, IEEE Trans. Knowl. Data Eng., vol. 30, no. 9, pp. 1616-1637, 2018.
[14]
Q. Wang, Z. D. Mao, B. Wang, and L. Guo, Knowledge graph embedding: A survey of approaches and applications, IEEE Trans. Knowl. Data Eng., vol. 29, no. 12, pp. 2724-2743, 2017.
[15]
Y. Fu and Y. Q. Ma, Graph Embedding for Pattern Analysis. New York, NY, USA: Springer Science & Business Media, 2012.
[16]
J. B. Tenenbaum, V. De Silva, and J. C. Langford, A global geometric framework for nonlinear dimensionality reduction, Science, vol. 290, no. 5500, pp. 2319-2323, 2000.
[17]
S. T. Roweis and L. K. Saul, Nonlinear dimensionality reduction by locally linear embedding, Science, vol. 290, no. 5500, pp. 2323-2326, 2000.
[18]
D. X. Wang, P. Cui, and W. W. Zhu, Structural deep network embedding, in Proc. 22ndACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD), San Francisco, CA, USA, 2016, pp. 1225-1234.
[19]
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 (WWW), Florence, Italy, 2015, pp. 1067-1077.
[20]
S. Y. Chang, W. Han, J. L. Tang, G. J. Qi, C. C. Aggarwal, and T. S. Huang, Heterogeneous network embedding via deep architectures, in Proc. 21th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), Sydney, Australia, 2015, pp. 119-128.
[21]
S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme, BPR: Bayesian personalized ranking from implicit feedback, in Proc. 25th Conf. Uncertainty in Artificial Intelligence, Montreal, Canada, 2009, pp. 452-461.
[22]
A. G. Duran and M. Niepert, Learning graph representations with embedding propagation, in Advances in Neural Information Processing Systems 30 (NIPS), 2017, pp. 5125-5136.
[23]
X. Huang, J. D. Li, and X. Hu, Accelerated attributed network embedding, in Proc. 17th SIAM Int. Conf. Data Mining (SDM), Houston, TX, USA, 2017.
[24]
X. Huang, J. D. Li, and X. Hu, Label informed attributed network embedding, in Proc. 10th ACM Int. Conf. Web Search and Data Mining (WSDM), Cambridge, United Kingdom, 2017.
[25]
J. Tang, M. Qu, and Q. Z. Mei, PTE: Predictive text embedding through large-scale heterogeneous text networks, in Proc. 21th ACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD), Sydney, Australia, 2015, pp. 1165-1174.
[26]
X. F. Sun, J. Guo, X. Ding, and T. Liu, A general framework for content-enhanced network representation learning, arXiv preprint arXiv: 1610.02906, 2016.
[27]
S. H. Wang, J. L. Tang, C. Aggarwal, Y. Chang, and H. Liu, Signed network embedding in social media, in Proc. 17th SIAM Int. Conf. Data Mining (SDM), Houston, TX, USA, 2017.
[28]
S. H. Wang, C. Aggarwal, J. L. Tang, and H. Liu, Attributed signed network embedding, in Proc. 26th Int. Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 137-146.
[29]
J. D. Li, H. Dani, X. Hu, J. L. Tang, Y. Chang, and H. Liu, Attributed network embedding for learning in a dynamic environment, in Proc. 2017 Int. Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 387-396.
[30]
L. C. Xu, X. K. Wei, J. N. Cao, and P. S. Yu, Embedding of embedding (EOE): Joint embedding for coupled heterogeneous networks, in Proc. 10th Int. Conf. Web Search and Data Mining (WSDM), Cambridge, United Kingdom, 2017, pp. 741-749.
[31]
M. Qu, J. Tang, J. B. Shang, X. Ren, M. Zhang, and J. W. Han, An attention-based collaboration framework for multi-view network representation learning, in Proc. 2017 Int. Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 1767-1776.
[32]
L. K. Zhou, Y. Yang, X. Ren, F. Wu, and Y. T. Zhuang, Dynamic network embedding by modeling triadic closure process, in Proc. 32ndAAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[33]
D. J. Yang, S. Z. Wang, C. Z. Li, X. M. Zhang, and Z. J. Li, From properties to links: Deep network embedding on incomplete graphs, in Proc. 2017 Int. Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 367-376.
[34]
L. C. Xu, X. K. Wei, J. N. Cao, and P. S. Yu, On exploring semantic meanings of links for embedding social networks, in Proc. 2018 Web Conference (WWW), Lyon, France, 2018, pp. 479-488.
[35]
X. Wang, P. Cui, J. Wang, J. Pei, W. W. Zhu, and S. Q. Yang, Community preserving network embedding, in Proc. 31st AAAI Conf. Artificial Intelligence, San Francisco, CA, USA, 2017, pp. 203-209.
[36]
O. Levy and Y. Goldberg, Neural word embedding as implicit matrix factorization, in Proc. 27th Int. Conf. and Workshop on Neural Information Processing Systems (NIPS)), Montreal, Canada, 2014, pp. 2177-2185.
[37]
S. S. Cao, W. Lu, and Q. K. Xu, GraRep: Learning graph representations with global structural information, in Proc. 24th Int. Conf. Information and Knowledge Management (CIKM), Melbourne, Australia, 2015, pp. 891-900.
[38]
B. Perozzi, R. Al-Rfou, and S. Skiena, Deepwalk: Online learning of social representations, in Proc. 20th ACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD), New York, NY, USA, 2014, pp. 701-710.
[39]
C. Zhou, Y. Q. Liu, X. F. Liu, Z. Y. Liu, and J. Gao, Scalable graph embedding for asymmetric proximity, in Proc. 31st AAAI Conf. Artificial Intelligence, San Francisco, CA, USA, 2017, pp. 2942-2948.
[40]
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. Joint Conf. Artificial Intelligence (IJCAI), Buenos Aires, Argentina, 2015, pp. 2111-2117.
[41]
M. D. Ou, P. Cui, J. Pei, Z. W. Zhang, and W. W. Zhu, Asymmetric transitivity preserving graph embedding, in Proc. 22nd ACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD), San Francisco, CA, USA, 2016, pp. 1105-1114.
[42]
A. Grover and J. Leskovec, node2vec: Scalable feature learning for networks, in Proc. 22ndACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), San Francisco, CA, USA, 2016, pp. 855-864.
[43]
J. F. Chen, Q. Zhang, and X. J. Huang, Incorporate group information to enhance network embedding, in Proc. 25th ACM Int. Conf. Information and Knowledge Management (CIKM), Indianapolis, IN, USA, 2016, pp. 1901-1904.
[44]
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.
[45]
J. Z. Qiu, Y. X. Dong, H. Ma, J. Li, K. S. Wang, and J. Tang, Network embedding as matrix factorization: Unifying DeepWalk, LINE, PTE, and node2vec, in Proc. 11th Int. Conf. Web Search and Data Mining (WSDM), Marina Del Rey, CA, USA, 2018.
[46]
S. R. Pan, J. Wu, X. Q. Zhu, C. Q. Zhang, and Y. Wang, Tri-party deep network representation, in Proc. 25th Int. Joint Conf. Artificial Intelligence (IJCAI), New York, NY, USA, 2016, pp. 1895-1901.
[47]
Z. L. Yang, W. W. Cohen, and R. Salakhutdinov, Revisiting semi-supervised learning with graph embeddings, in Proc. 33rd Int. Conf. Machine Learning, New York, NY, USA, 2016, pp. 40-48.
[48]
J. F. Hu, R. Cheng, Z. P. Huang, Y. Fang, and S. Q. Luo, On embedding uncertain graphs, in Proc. 2017 ACM on Int. Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 157-166.
[49]
S. H. Chen, S. F. Niu, L. Akoglu, J. Kovaevi, and C. Faloutsos, Fast, warped graph embedding: Unifying framework and one-click algorithm, arXiv preprint arXiv: 1702.05764, 2017.
[50]
Y. X. Dong, N. V. Chawla, and A. Swami, metapath2vec: Scalable representation learning for heterogeneous networks, in Proc. 23rd ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), Halifax, Canada, 2017, pp. 135-144.
[51]
T. Y. Fu, W. C. Lee, and Z. Lei, HIN2Vec: Explore meta-paths in heterogeneous information networks for representation learning, in Proc. 2017 Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 1797-1806.
[52]
T. Lyu, Y. Zhang, and Y. Zhang, Enhancing the network embedding quality with structural similarity, in Proc. 2017 ACM on Conf. Information and Knowledge Management (CIKM), 2017, pp. 147-156.
[53]
R. Feng, Y. Yang, W. J. Hu, F. Wu, and Y. T. Zhang, Representation learning for scale-free networks, in Proc. 32nd AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[54]
Y. Ma, Z. C. Ren, Z. H. Jiang, J. L. Tang, and D. W. Yin, Multi-dimensional network embedding with hierarchical structure, in Proc. 11th Int. Conf. Web Search and Data Mining (WSDM), Marina Del Rey, CA, USA, 2018.
[55]
Q. Y. Dai, Q. Li, J. Tang, and D. Wang, Adversarial network embedding, in Proc. 2018 AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[56]
J. Kim, H. Park, J. E. Lee, and U. Kang, SIDE: Representation learning in signed directed networks, in Proc. 2018 ACM World Wide Web Conf. (WWW), Lyon, France, 2018, pp. 509-518.
[57]
W. Hamilton, Z. T. Ying, and J. Leskovec, Inductive representation learning on large graphs, in Advances in Neural Information Processing Systems 30 (NIPS), 2017, pp. 1025-1035.
[58]
T. Chen and Y. Z. Sun, Task-guided and path-augmented heterogeneous network embedding for author identification, in Proc. 10th ACM Int. Conf. Web Search and Data Mining (WSDM), Cambridge, United Kingdom, 2017, pp. 295-304.
[59]
B. C. Zhang and M. Al Hasan, Name disambiguation in anonymized graphs using network embedding, in Proc. 2017 ACM on Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 1239-1248.
[60]
H. W. Wang, F. Z. Zhang, M. Hou, X. Xie, M. Y. Guo, and Q. Liu, SHINE: Signed heterogeneous information network embedding for sentiment link prediction, in Proc. 11th Int. Conf. Web Search and Data Mining (WSDM), Marina Del Rey, CA, USA, 2018, pp. 592-600.
[61]
A. Ahmed, N. Shervashidze, S. Narayanamurthy, V. Josifovski, and A. J. Smola, Distributed large-scale natural graph factorization, in Proc. 22nd Int. Conf. World Wide Web (WWW), Rio de Janeiro, Brazil, 2013, pp. 37-48.
[62]
C. C. Tu, W. C. Zhang, Z. Y. Liu, and M. S. Sun, Max-margin deepwalk: Discriminative learning of network representation, in Proc. 25th Int. Joint Conf. Artificial Intelligence (IJCAI), New York, NY, USA, 2016, pp. 3889-3895.
[63]
T. Mikolov, K. Chen, G. Corrado, and J. Dean, Efficient estimation of word representations in vector space, arXiv preprint arXiv: 1301.3781, 2013.
[64]
T. Mikolov, I. Sutskever, K. Chen, G. Corrado, and J. Dean, Distributed representations of words and phrases and their compositionality, in Proc. 26th Int. Conf. Neural Information Processing Systems (NIPS), Lake Tahoe, NV, USA, 2013, pp. 3111-3119.
[65]
J. X. Ma, P. Cui, and W. W. Zhu, DepthLGP: Learning embeddings of out-of-sample nodes in dynamic networks, in Proc. 32nd AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[66]
H. W. Wang, J. Wang, J. L. Wang, M. Zhao, W. N. Zhang, F. Z. Zhang, X. Xie, and M. Y. Guo, GraphGAN: Graph representation learning with generative adversarial nets, in Proc. 32nd AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[67]
T. Hoevar and J. Demšar, A combinatorial approach to graphlet counting, Bioinformatics, vol. 30, no. 4, pp. 559-565, 2014.
[68]
Y. P. Gu, Y. Z. Sun, Y. E. Li, and Y. Yang, Rare: Social rank regulated large-scale network embedding, in Proc. 2018 World Wide Web Conf. (WWW), Lyon, France, 2018, pp. 359-368.
[69]
S. H. Yuan, X. T. Wu, and Y. Xiang, SNE: Signed network embedding, in Proc. 21st Pacific-Asia Conf. Knowledge Discovery and Data Mining (PAKDD), 2017, pp. 183-195.
[70]
Y. Z. Sun, J. W. Han, X. F. Yan, P. S. Yu, and T. Y. Wu, PathSim: Meta path-based top-K similarity search in heterogeneous information networks, Proc. VLDB Endowment, vol. 4, no. 11, pp. 992-1003, 2011.
[71]
G. X. Ma, L. F. He, C. T. Lu, W. X. Shao, P. S. Yu, A. D. Leow, and A. B. Ragin, Multi-view clustering with graph embedding for connectome analysis, in Proc. 2017 ACM on Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 127-136.
[72]
R. Trivedi, M. Farajtabar, P. Biswal, and H. Y. Zha, Representation learning over dynamic graphs, arXiv preprint arXiv: 1803.04051, 2018.
[73]
Y. Zhang, Y. Xiong, X. N. Kong, and Y. Y. Zhu, Learning node embeddings in interaction graphs, in Proc. 2017 ACM on Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 397-406.
[74]
K. Tu, P. Cui, X. Wang, F. Wang, and W. W. Zhu, Structural deep embedding for hyper-networks, in Proc. 32nd AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[75]
S. Cavallari, V. W. Zheng, H. Y. Cai, K. C. C. Chang, and E. Cambria, Learning community embedding with community detection and node embedding on graphs, in Proc. 2017 ACM on Conf. Information and Knowledge Management (CIKM), Singapore, 2017, pp. 377-386.
[76]
M. E. J. Newman, Modularity and community structure in networks, Proc. Natl. Acad. Sci. U.S.A., vol. 103, no. 23, pp. 8577-8582, 2006.
[77]
V. Misra and S. Bhatia, Bernoulli embeddings for graphs, in Proc. 32nd AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[78]
H. C. Chen, B. Perozzi, Y. F. Hu, and S. Skiena, Harp: Hierarchical representation learning for networks, in Proc. 32nd AAAI Conf. Artificial Intelligence, New Orleans, LA, USA, 2018.
[79]
P. Yanardag and S. V. N. Vishwanathan, Deep graph kernels, in Proc. 21th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining (KDD), Sydney, Australia, 2015, pp. 1365-1374.
[80]
A. Narayanan, M. Chandramohan, L. H. Chen, Y. Liu, and S. Saminathan, subgraph2vec: Learning distributed representations of rooted sub-graphs from large graphs, arXiv preprint arXiv: 1606.08928, 2016.
Publication history
Copyright
Rights and permissions
Publication history
Received: 10 May 2018
Accepted: 25 May 2018
Published:
15 October 2018
Issue date: March 2019
Copyright
© The author(s) 2019
