基于邻域相似的层次粒化的网络表示学习方法
|
摘要
捕获更多的结构特征给网络表示学习方法带来较高的复杂度.基于分层递阶思想,文中提出基于邻域相似的层次粒化的网络表示学习方法,降低已有网络表示学习方法的复杂度.首先利用节点邻域相似性将网络逐步压缩至粗粒度的表示空间中.然后利用已有的网络表示学习方法学习粗粒的特征表示.最后利用图卷积网络将已学习的粗粒特征逐步细化为原始网络的节点表示.在多个数据集上的实验表明,文中方法可以快速有效大幅压缩网络,降低算法的运行时间.针对节点分类和链接预测任务,当粒化层次较低时,文中方法可以较大幅度提升原有算法的性能.
The acquisition of structural features brings higher complexity to network representation learning. Based on the idea of hierarchy, an effective method is proposed to reduce the complexity of existing network representation learning methods. The network is gradually compressed into a coarse-grained representation space via node neighborhood similarity. And the coarse-grained feature representation is learned by the existing network representation learning methods. Finally, the learned coarse-grained features are gradually refined into the node representation of the original network using the graph convolution network model. Experimental results on several datasets show that the proposed method compresses the network efficiently and quickly, and the running time of the existing algorithms is greatly reduced. For the task of node classification and link prediction, the proposed method can greatly improve the performance of the original algorithm while the granularity level is low.
The acquisition of structural features brings higher complexity to network representation learning. Based on the idea of hierarchy, an effective method is proposed to reduce the complexity of existing network representation learning methods. The network is gradually compressed into a coarse-grained representation space via node neighborhood similarity. And the coarse-grained feature representation is learned by the existing network representation learning methods. Finally, the learned coarse-grained features are gradually refined into the node representation of the original network using the graph convolution network model. Experimental results on several datasets show that the proposed method compresses the network efficiently and quickly, and the running time of the existing algorithms is greatly reduced. For the task of node classification and link prediction, the proposed method can greatly improve the performance of the original algorithm while the granularity level is low.
引文
[1] SHEIKH N T,KEFATO Z T,MONTRESOR A.Semi-supervised Heterogeneous Information Network Embedding for Node Classification Using 1D-CNN[C/OL].[2019-02-25].http://disi.unitn.it/～montreso/pubs/papers/snams18b.pdf.
[2] XU G L,WANG X K,WANG Y,et al.Edge-Nodes Representation Neural Machine for Link Prediction.Algorithms,2019,12(1).DOI:10.3390/a12010012.
[3] BHATIA V,RANI R.A Distributed Overlapping Community Detection Model for Large Graphs Using Autoencoder.Future Generation Computer Systems,2019,94:16-26.
[4] 涂存超,杨成,刘知远,等.网络表示学习综述.中国科学(信息科学),2017,47(8):980-996.(TU C C,YANG C,LIU Z Y,et al.Network Representation Learning:An Overview.Scientia Sinica Informationis,2017,47(8):980-996.)
[5] MEYER-BR?TZ F,SCHIEBEL E,BRECHT L.Experimental Eva-luation of Parameter Settings in Calculation of Hybrid Similarities:Effects of First- and Second-Order Similarity,Edge Cutting,and Weighting Factors.Scientometrics,2017,111(3):1307-1325.
[6] ZHANG H G,KONIUSZ P.Power Normalizing Second-Order Similarity Network for Few-Shot Learning[C/OL].[2019-02-25].https://arxiv.org/pdf/1811.04167.pdf.
[7] SONG G F.The Role of Structure and Content in Perception of Vi-sual Similarity between Web Pages.International Journal of Human-Computer Interaction,2011,27(8):793-816.
[8] ZHANG J P,DING X Y,YANG J.Revealing the Role of Node Similarity and Community Merging in Community Detection.Know-ledge Based Systems,2019,165:407-419.
[9] HAJIZADEH R,AGHAGOLZADEH A,EZOJI M.Mutual Neighbors and Diagonal Loading-Based Sparse Locally Linear Embedding.Applied Artificial Intelligence,2018,32(5):496-514.
[10] MA M H,DENG T Q,WANG N,et al.Semi-supervised Rough Fuzzy Laplacian Eigenmaps for Dimensionality Reduction.International Journal of Machine Learning and Cybernetics,2019,10(2):397-411.
[11] PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online Lear-ning of Social Representations // Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2014:701-710.
[12] BRA?INSKAWS A,HAVRYLOV S,TITOV I.Embedding Words as Distributions with a Bayesian Skip-Gram Model // Proc of the 27th International Conference on Computational Linguistics.Stroudsburg,USA:ACL,2018:1775-1789.
[13] TANG J,QU M,WANG M Z,et al.LINE:Large-Scale Information Network Embedding // Proc of the 24th International Confe-rence on World Wide Web.New York,USA:ACM,2015:1067-1077.
[14] CAO S S,LU W,XU Q K.GraRep:Learning Graph Representations with Global Structural Information // Proc of the 24th ACM Internatio-nal Conference on Information and Knowledge Management.New York,USA:ACM,2015:891-900.
[15] GROVER A,LESKOVEC J.Node2vec:Scalable Feature Learning for Networks // Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2016:855-864.
[16] CAO S S,LU W,XU Q K.Deep Neural Networks for Learning Graph Representations // Proc of the 30th AAAI Conference on Artificial Intelligence.Palo Alto,USA:AAAI,2016:1145-1152.
[17] FAN X N,ZHANG S W,ZHANG S Y,et al.Prediction of lncRNA-Disease Associations by Integrating Diverse Heterogeneous Information Sources with RWR Algorithm and Positive Pointwise Mutual Information.BMC Bioinformatics,2019,20(1):871-883.
[18] VINCENT P,LAROCHELLE H,LAJOIE I,et al.Stacked Denoising Autoencoders:Learning Useful Representations in a Deep Network with a Local Denoising Criterion.Journal of Machine Learning Research,2010,11:3371-3408.
[19] KIPF T N,WELLING M.Semi-supervised Classification with Graph Convolutional Networks[C/OL].[2019-02-25].https://arxiv.org/pdf/1609.02907.pdf.
[20] HAMILTON W L,YING R,LESKOVEC J.Inductive Representation Learning on Large Graphs[C/OL].[2019-02-25].https://arxiv.org/pdf/1706.02216.pdf.
[21] WANG H W,WANG J,WANG J L,et al.GraphGAN:Graph Representation Learning with Generative Adversarial Nets[C/OL].[2019-02-25].https://arxiv.org/pdf/1711.08267.pdf.
[22] 赵姝,赵晖,陈洁,等.基于社团结构的多粒度结构洞占据者发现及分析.智能系统学报,2016,11(3):343-351.(ZHAO S,ZHAO H,CHEN J,et al.Recognition and Analysis of Structural Hole Spanner in Multi-granularity Based on Community Structure.CAAI Transactions on Intelligent Systems,2016,11(3):343-351.)
[23] 张燕平,张铃,吴涛.不同粒度世界的描述法——商空间法.计算机学报,2004,27(3):328-333.(ZHANG Y P,ZHANG L,WU T.The Representation of Different Granular Worlds:A Quotient Space.Chinese Journal of Compu-ters,2004,27(3):328-333.)
[24] 赵姝,柯望,陈洁,等.基于聚类粒化的社团发现算法.计算机应用,2014,34(10):2812-2815.(ZHAO S,KE W,CHEN J,et al.Community Detection Algorithm Based on Clustering Granulation.Journal of Computer Applications,2014,34(10):2812-2815.)
[25] SARKAR P,CHAKRABARTI D,BICKEL P.The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels // Proc of the 28th International Conference on Neural Information Processing Systems.Cambridge,USA:The MIT Press,2015,II:3016-3024.
[26] BAG S,KUMAR S K,TIWARI M K.An Efficient Recommendation Generation Using Relevant Jaccard Similarity.Information Sciences,2019,483:53-64.
[27] HAMERS L,HEMERYCK Y,HERWEYERS G,et al.Similarity Measures in Scientometric Research:The Jaccard Index Versus Salton′s Cosine Formula.Information Processing and Management,1989,25(3):315-318.
[28] ADAMIC L A,LENTO T M,ADAR E,et al.Information Evolution in Social Networks // Proc of the 9th ACM International Conference on Web Search and Data Mining.New York,USA:ACM,2016:473-482.
[29] MCCALLUM A K,NIGAM K,RENNIE J,et al.Automating the Construction of Internet Portals with Machine Learning.Information Retrieval,2000,3(2):127-163.
[30] GAO H C,HUANG H.Self-paced Network Embedding // Proc of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2018:1406-1415.
[31] WU W,LI B,CHEN L,et al.Efficient Attributed Network Embedding via Recursive Randomized Hashing // Proc of the 27th International Joint Conference on Artificial Intelligence.Hackensack,USA:World Scientific,2018:2861-2867.
[32] TANG L,LIU H.Relational Learning via Latent Social Dimensions // Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2009:817-826.
[33] FAWCETT T.An Introduction to ROC Analysis.Pattern Recognition Letters,2006,27(8):861-874.
[2] XU G L,WANG X K,WANG Y,et al.Edge-Nodes Representation Neural Machine for Link Prediction.Algorithms,2019,12(1).DOI:10.3390/a12010012.
[3] BHATIA V,RANI R.A Distributed Overlapping Community Detection Model for Large Graphs Using Autoencoder.Future Generation Computer Systems,2019,94:16-26.
[4] 涂存超,杨成,刘知远,等.网络表示学习综述.中国科学(信息科学),2017,47(8):980-996.(TU C C,YANG C,LIU Z Y,et al.Network Representation Learning:An Overview.Scientia Sinica Informationis,2017,47(8):980-996.)
[5] MEYER-BR?TZ F,SCHIEBEL E,BRECHT L.Experimental Eva-luation of Parameter Settings in Calculation of Hybrid Similarities:Effects of First- and Second-Order Similarity,Edge Cutting,and Weighting Factors.Scientometrics,2017,111(3):1307-1325.
[6] ZHANG H G,KONIUSZ P.Power Normalizing Second-Order Similarity Network for Few-Shot Learning[C/OL].[2019-02-25].https://arxiv.org/pdf/1811.04167.pdf.
[7] SONG G F.The Role of Structure and Content in Perception of Vi-sual Similarity between Web Pages.International Journal of Human-Computer Interaction,2011,27(8):793-816.
[8] ZHANG J P,DING X Y,YANG J.Revealing the Role of Node Similarity and Community Merging in Community Detection.Know-ledge Based Systems,2019,165:407-419.
[9] HAJIZADEH R,AGHAGOLZADEH A,EZOJI M.Mutual Neighbors and Diagonal Loading-Based Sparse Locally Linear Embedding.Applied Artificial Intelligence,2018,32(5):496-514.
[10] MA M H,DENG T Q,WANG N,et al.Semi-supervised Rough Fuzzy Laplacian Eigenmaps for Dimensionality Reduction.International Journal of Machine Learning and Cybernetics,2019,10(2):397-411.
[11] PEROZZI B,AL-RFOU R,SKIENA S.Deepwalk:Online Lear-ning of Social Representations // Proc of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2014:701-710.
[12] BRA?INSKAWS A,HAVRYLOV S,TITOV I.Embedding Words as Distributions with a Bayesian Skip-Gram Model // Proc of the 27th International Conference on Computational Linguistics.Stroudsburg,USA:ACL,2018:1775-1789.
[13] TANG J,QU M,WANG M Z,et al.LINE:Large-Scale Information Network Embedding // Proc of the 24th International Confe-rence on World Wide Web.New York,USA:ACM,2015:1067-1077.
[14] CAO S S,LU W,XU Q K.GraRep:Learning Graph Representations with Global Structural Information // Proc of the 24th ACM Internatio-nal Conference on Information and Knowledge Management.New York,USA:ACM,2015:891-900.
[15] GROVER A,LESKOVEC J.Node2vec:Scalable Feature Learning for Networks // Proc of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2016:855-864.
[16] CAO S S,LU W,XU Q K.Deep Neural Networks for Learning Graph Representations // Proc of the 30th AAAI Conference on Artificial Intelligence.Palo Alto,USA:AAAI,2016:1145-1152.
[17] FAN X N,ZHANG S W,ZHANG S Y,et al.Prediction of lncRNA-Disease Associations by Integrating Diverse Heterogeneous Information Sources with RWR Algorithm and Positive Pointwise Mutual Information.BMC Bioinformatics,2019,20(1):871-883.
[18] VINCENT P,LAROCHELLE H,LAJOIE I,et al.Stacked Denoising Autoencoders:Learning Useful Representations in a Deep Network with a Local Denoising Criterion.Journal of Machine Learning Research,2010,11:3371-3408.
[19] KIPF T N,WELLING M.Semi-supervised Classification with Graph Convolutional Networks[C/OL].[2019-02-25].https://arxiv.org/pdf/1609.02907.pdf.
[20] HAMILTON W L,YING R,LESKOVEC J.Inductive Representation Learning on Large Graphs[C/OL].[2019-02-25].https://arxiv.org/pdf/1706.02216.pdf.
[21] WANG H W,WANG J,WANG J L,et al.GraphGAN:Graph Representation Learning with Generative Adversarial Nets[C/OL].[2019-02-25].https://arxiv.org/pdf/1711.08267.pdf.
[22] 赵姝,赵晖,陈洁,等.基于社团结构的多粒度结构洞占据者发现及分析.智能系统学报,2016,11(3):343-351.(ZHAO S,ZHAO H,CHEN J,et al.Recognition and Analysis of Structural Hole Spanner in Multi-granularity Based on Community Structure.CAAI Transactions on Intelligent Systems,2016,11(3):343-351.)
[23] 张燕平,张铃,吴涛.不同粒度世界的描述法——商空间法.计算机学报,2004,27(3):328-333.(ZHANG Y P,ZHANG L,WU T.The Representation of Different Granular Worlds:A Quotient Space.Chinese Journal of Compu-ters,2004,27(3):328-333.)
[24] 赵姝,柯望,陈洁,等.基于聚类粒化的社团发现算法.计算机应用,2014,34(10):2812-2815.(ZHAO S,KE W,CHEN J,et al.Community Detection Algorithm Based on Clustering Granulation.Journal of Computer Applications,2014,34(10):2812-2815.)
[25] SARKAR P,CHAKRABARTI D,BICKEL P.The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels // Proc of the 28th International Conference on Neural Information Processing Systems.Cambridge,USA:The MIT Press,2015,II:3016-3024.
[26] BAG S,KUMAR S K,TIWARI M K.An Efficient Recommendation Generation Using Relevant Jaccard Similarity.Information Sciences,2019,483:53-64.
[27] HAMERS L,HEMERYCK Y,HERWEYERS G,et al.Similarity Measures in Scientometric Research:The Jaccard Index Versus Salton′s Cosine Formula.Information Processing and Management,1989,25(3):315-318.
[28] ADAMIC L A,LENTO T M,ADAR E,et al.Information Evolution in Social Networks // Proc of the 9th ACM International Conference on Web Search and Data Mining.New York,USA:ACM,2016:473-482.
[29] MCCALLUM A K,NIGAM K,RENNIE J,et al.Automating the Construction of Internet Portals with Machine Learning.Information Retrieval,2000,3(2):127-163.
[30] GAO H C,HUANG H.Self-paced Network Embedding // Proc of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2018:1406-1415.
[31] WU W,LI B,CHEN L,et al.Efficient Attributed Network Embedding via Recursive Randomized Hashing // Proc of the 27th International Joint Conference on Artificial Intelligence.Hackensack,USA:World Scientific,2018:2861-2867.
[32] TANG L,LIU H.Relational Learning via Latent Social Dimensions // Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM,2009:817-826.
[33] FAWCETT T.An Introduction to ROC Analysis.Pattern Recognition Letters,2006,27(8):861-874.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |