图嵌入方法与应用:研究综述

doi:10.3969/j.issn.0372-2112.2020.04.023

摘要/Abstract

摘要： 图模型越来越广泛地应用于数据管理、知识发现和信息服务等问题中，图嵌入作为图分析和应用的重要技术手段，成为了人工智能领域研究的热点之一.本文从图嵌入研究中面临的挑战出发，主要介绍了基于矩阵分解、基于随机游走和基于深度学习的图嵌入方法.接着，介绍了图嵌入方法常用的测试数据集、评测标准和典型应用.最后，总结了图嵌入未来研究的趋势和方向.

关键词: 图模型, 图嵌入方法, 图嵌入应用, 测试数据集, 评测标准

Abstract: Graphs are increasingly used in data management,knowledge discovery and information services.As an important strategy of graph analysis and applications,graph embedding has become one of the subjects with great attention in artificial intelligence.Starting from the challenges faced in graph embedding studies,this paper introduces the principal methods based on matrix decomposition,random walk and deep learning.Then,we introduce general test datasets,evaluation criteria as well as typical applications widely used in graph embedding.Finally,we summarize the trend and future research issues of graph embedding.

Key words: graph model, graph embedding method, graph embedding application, test datasets, evaluation metrics

中图分类号:

TP3-0

祁志卫, 王笳辉, 岳昆, 乔少杰, 李劲. 图嵌入方法与应用:研究综述[J]. 电子学报, 2020, 48(4): 808-818.

QI Zhi-wei, WANG Jia-hui, YUE Kun, QIAO Shao-jie, LI Jin. Methods and Applications of Graph Embedding:A Survey[J]. Acta Electronica Sinica, 2020, 48(4): 808-818.

参考文献

[1] 王啸,崔鹏,朱文武.网络表征学习中的基本问题初探[J].中国计算机学会通讯,2018,14(3):11-15. WANG Xiao,CUI Peng,ZHU Wen-wu.A preliminary research on the fundamental problems of network representation learning[J].Communications of the CCF,2018,14(3):11-15.(in Chinese)
[2] QIAO S,HAN N,GAO Y,et al.A fast parallel community discovery model on complex networks through approximate optimization[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(9):1638-1651.
[3] WHITE H,BOORMAN S,BREIGER R.Social structure from multiple networks-blockmodels of roles and positions[J].American Journal of Sociology,1976,81(4):730-780.
[4] ADAMIC L,ADAR E.Friends and neighbors on the web[J].Social Networks,2003,25(3):211-230.
[5] FU T,LEE W,LEI Z.HIN2Vec:explore meta-paths in heterogeneous information networks for representation learning[A].Proceedings of the 2017 ACM on Conference on Information and Knowledge Management[C].Singapore:ACM,2017.1797-1806.
[6] TANG J,QU M,MEI Q.Pte:Predictive text embedding through large-scale heterogeneous text networks[A].Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Sydney,Australia:ACM,2015.1165-1174.
[7] YUE K,FANG Q,WANG X,et al.A parallel and incremental approach for data-intensive learning of Bayesian networks[J].IEEE Transactions on Cybernetics,2015,45(12):2890-2904.
[8] GOYAL P,FERRARA E.Graph embedding techniques,applications,and performance:A survey[J].Knowledge-Based Systems,2018,151:78-94.
[9] CAI H,ZHENG V,CHANG C.A comprehensive survey of graph embedding:problems,techniques and applications[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(9):1616-1637.
[10] CUI P,WANG X,PEI J,et al.A survey on network embedding[J].IEEE Transactions on Knowledge and Data Engineering,2019,31(5):833-852.
[11] HAMILTON W,YING R,LESKOVEC J.Representation learning on graphs:methods and applications[J].IEEE Data Engineering Bulletin,2017,40(1):52-74.
[12] 涂存超,杨成,刘知远,等.网络表示学习综述[J].中国科学:信息科学,2017,47(8):980-996. TU Cunchao,YANG Cheng,LIU Zhiyuan,et al.Network representation learning:an overview[J].SCIENTIA SINICA Informationis,2017,47(8):980-996.(in Chinese)
[13] BELKIN M,NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering[A].Proceedings of Advances in Neural Information Processing Systems[C].Vancouver,British Columbia,Canada:MIT Press,2001.585-591.
[14] TENENBAUM J,DE SILVA V,LANGFORD J.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.
[15] ROWEIS S,SAUL L.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[16] PEROZZI B,AI-RFOU R,SKIENA S.Deepwalk:Online learning of social representations[A].Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].New York,USA:ACM,2014.701-710.
[17] YANG C,LIU Z,ZHAO D,et al.Network representation learning with rich text information[A].Proceedings of the 24th International Joint Conference on Artificial Intelligence[C].Buenos Aires,Argentina:Morgan Kaufmann,2015.2111-2117.
[18] TU C,LIU H,LIU Z,et al.Cane:Context-aware network embedding for relation modeling[A].Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics[C].Vancouver,Canada:ACL,2017.1722-1731.
[19] LUO D,DING C,NIE F,et al.Cauchy graph embedding[A].Proceedings of the 28th International Conference on Machine Learning[C].Bellevue,Washington,USA:ACM,2011.553-560.
[20] CAO S,LU W,XU Q.Grarep:Learning graph representations with global structural information[A].Proceedings of the 24th ACM International Conference on Information and Knowledge Management[C].Melbourne,Australia:ACM,2015.891-900.
[21] OU M,CUI P,PEI J,et al.Asymmetric transitivity preserving graph embedding[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Francisco,CA,USA:ACM,2016.672-681.
[22] GROVER A,LESKOVEC J.Node2vec:Scalable feature learning for networks[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Francisco,CA,USA:ACM,2016.855-864.
[23] DONG Y,CHAWLA N,SWAMI A.metapath2vec:Scalable representation learning for heterogeneous networks[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Halifax,NS,Canada:ACM,2017.135-144.
[24] WANG D,CUI P,ZHU W.Structural deep network embedding[A].Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].San Francisco,CA,USA:ACM,2016.1225-1234.
[25] CAO S,LU W,XU Q.Deep neural networks for learning graph representations[A].Proceedings of the 33rd AAAI Conference on Artificial Intelligence[C].Phoenix,Arizona,USA:AAAI,2016.1145-1152.
[26] HAMILTON W,YING R,LESKOVEC J.Inductive representation learning on large graphs[A].Proceedings of Advances in Neural Information Processing Systems [C].Long Beach,CA,USA:MIT Press,2017.1024-1034.
[27] TANG J,QU M,WANG M,et al.Line:Large scale information network embedding[A].Proceedings of the 24th International World Wide Web Conference[C].Florence,Italy:ACM,2015.1067-1077.
[28] YANG C,SUN M,LIU Z,et al.Fast network embedding enhancement via high order proximity approximation[A].Proceedings of the 26th International Joint Conference on Artificial Intelligence[C].Melbourne,Australia:Morgan Kaufmann,2017.3894-3900.
[29] BOURIGAULT S,LAGNIER C,LAMPRIER S,et al.Learning social network embeddings for predicting information diffusion[A].Proceedings of the 7th ACM International Conference on Web Search and Data Mining[C].New York,NY,USA:ACM,2014.393-402.
[30] LI C,MA J,GUO X,et al.DeepCas:An end-to-end predictor of information cascades[A].Proceedings of the 26th International Conference on World Wide Web[C].Perth,Australia:ACM,2017.577-586.
[31] BORDES A,USUNIER A,et al.Translating embeddings for modeling multi-relational data[A].Proceedings of the 27th Annual Conference on Neural Information Processing Systems[C].Lake Tahoe,Nevada,United States:MIT Press,2013.2787-2795.
[32] ZOU L,CHEN L,ZHAO D,et al.Answering pattern match queries in large graph databases via graph embedding[J].VLDB Journal,2012,21(1):97-120.
[33] MIKOLOV T,SUTSKEVER I,CHEN K,et al.Distributed representations of words and phrases and their compositionality[A].Proceedings of Advances in Neural Information Processing Systems [C].Lake Tahoe,Nevada,United States:MIT Press,2013.3111-3119.
[34] 潘博,于重重,张青川,等.基于词性与词序的相关因子训练的word2vec改进模型[J].电子学报,2018,46(8):1976-1982. PAN Bo,YU Chong-chong,ZHANG Qing-chuan,et al.The improved model for word2vec based on part of speech and word order[J].Acta Electronica Sinica,2018,46(8):1976-1982.(in Chinese)
[35] WANG Z,ZHANG J,FENG J,et al.Knowledge graph embedding by translating on hyperplanes[A].Proceedings of the 28th AAAI Conference on Artificial Intelligence[C].Québec City,Québec,Canada:AAAI,2014.1112-1119.
[36] LIN Y,LIU Z,SUN M,et al.Learning entity and relation embeddings for knowledge graph completion[A].Proceedings of the 29th AAAI Conference on Artificial Intelligence[C].Austin,Texas,USA:AAAI,2015.2181-2187.
[37] JI G,HE S,XU L,et al.Knowledge graph embedding via dynamic mapping matrix[A].Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics[C].Stroudsburg,PA:ACL,2015.687-696.
[38] JI G,LIU K,HE S,et al.Knowledge graph completion with adaptive sparse transfer matrix[A].Proceedings of the 30th AAAI Conference on Artificial Intelligence[C].Phoenix,Arizona,USA:AAAI,2016.985-991.
[39] HE S,LIU K,JI G,et al.Learning to represent knowledge graphs with Gaussian embedding[A].Proceedings of the 24th ACM International Conference on Information and Knowledge Management[C].Melbourne,VIC,Australia:CIKM,2015.623-632.
[40] RIBA P,LLAD ÓS J,FORNÉS A,et al.Large-scale graph indexing using binary embeddings of node contexts for information spotting in document image databases[J].Pattern Recognition Letters,2017,87:203-211.
[41] LINIAL N,LONDON E,RABINOVICH Y.The geometry of graphs and some of its algorithmic applications[J].Combinatorica,1995,15(2):215-245.
[42] LI J,ZHU J,ZHANG B.Discriminative deep random walk for network classification[A].Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics[C].Stroudsburg,PA:ACL,2016.1004-1013.
[43] PEROZZI B,KULKARNI V,CHEN H,et al.Don’t walk,skip! online learning of multi-scale network embeddings[A].Proceedings of the 2017 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining[C].Sydney,Australia:IEEE/ACM,2017.258-265.
[44] CAVALLARI S,ZHENG V,CAI H,et al.Learning community embedding with community detection and node embedding on graphs[A].Proceedings of the 2017 ACM Conference on Information and Knowledge Management[C].Singapore:ACM,2017.377-386.
[45] HALKIDI M,BATISTAKIS Y,VAZIRGIANNIS M.On clustering validation techniques[J].Journal of Intelligent Information Systems,2001,17(2-3):107-145.
[46] MAATEN L,HINTON G.Visualizing data using t-sne[J].Journal of Machine Learning Research,2008:2579-2605.
[47] BHAGAT S,COMODE G,MUTHUKRISHNAN S.Node Classification in Social Networks.Social Network Data Analytics[M].Boston,MA:Springer,2011.115-148.
[48] TU C,ZENG X,WANG H,et al.A unified framework for community detection and network representation learning[J].IEEE Transactions on Knowledge and Data Engineering,2018,DOI:10.1109/TKDE.2018.2852958.
[49] HU R,AGGARWAL C,MA S,et al.An embedding approach to anomaly detection[A].Proceedings of the 32nd IEEE International Conference on Data Engineering[C].Helsinki,Finland:IEEE,2016.385-396.
[50] SHI C,HU B,ZHAO W,et al.Heterogeneous information network embedding for recommendation[J].IEEE Transactions on Knowledge and Data Engineering,2019,31(2):357-370.
[51] ZHOU Y,CHENG H,YU J.Graph clustering based on structural/attribute similarities[J].The Proceedings of the VLDB Endowment,2009,2(1):718-729.
[52] CLAUSET A,MOORE C,Newman M.Hierarchical structure and the prediction of missing links in networks[J].Nature,2008,453(7191):98-101.
[53] LIU W,YUE K,YUE M,et al.A Bayesian network based approach for incremental learning of uncertain knowledge[J].International Journal of Uncertainty,Fuzziness,and Knowledge-based Systems,2018,26(1):87-108.