网络表示学习算法的分析与验证
|
摘要
网络表示学习算法是社交网络分析领域的一个热点问题。该文旨在研究现有的各种网络表示学习算法,并分析各类算法在不同结构的网络数据中的性能,对3大类别、共10种网络表示学习算法在8个网络上进行了网络节点的多标签分类以验证算法的性能,以此来全面评价各类算法的效果、效率和应用范围。实验结果表明,DeepWalk这种流行的深度学习算法在各种类型的网络中有着稳定而较好的效果。而基于矩阵分解算法的应用,则受限于其较高的空间复杂度。
The network representation learning algorithm is a popular issue in social network analysis,and this paper is to verify the existing network representation learning algorithms by network data with different structures.To evaluate the effect,the efficiency and the application limits of various algorithms,we choose the multi-label classification task of network nodes to compare ten algorithms of three categories on eight data sets.The experimental results show that Deep Learning algorithms like DeepWalk have stable and good performance on various types of networks,and the application of algorithms based on matrix factorization are limited by their high space complexity.
The network representation learning algorithm is a popular issue in social network analysis,and this paper is to verify the existing network representation learning algorithms by network data with different structures.To evaluate the effect,the efficiency and the application limits of various algorithms,we choose the multi-label classification task of network nodes to compare ten algorithms of three categories on eight data sets.The experimental results show that Deep Learning algorithms like DeepWalk have stable and good performance on various types of networks,and the application of algorithms based on matrix factorization are limited by their high space complexity.
引文
[1]Agarwal A,Phillips J M,Venkatasubramanian S.Universal multi-dimensional scaling[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,NY,USA:ACM,2010:1149-1158.
[2]Tenenbaum J B,De Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.
[3]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[4]Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of the NIPS,2001:585-591.
[5]Ahmed A,et al.Distributed large-scale natural graph factorization[C]//Proceedings of the 22nd International Conference on World Wide Web.ACM,2013:37-48.
[6]Cao S,Lu W,Xu Q.Grarep:Learning graph representations with global structural information[C]//Proceedings of the 24th ACM International Conference on Information and Knowledge Management,2015:891-900.
[7]Ou M,et al.Asymmetric transitivity preserving graph embedding[C]//Proceedings of the ACM SIGKDD International Conference,2016:1105-1114.
[8]Perozzi B,R Al-Rfou,Skiena S.Deepwalk:Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2014:701-710.
[9]Tang J,et al.Line:Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web.2015:1067-1077.
[10]Zheng V W,et al.From node embedding to community embedding[J].arXiv preprint arXiv:1610.09950.2016.
[11]Grover A,Leskovec J.node2vec:Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2016:855-864.
[12]Levy O,Goldberg Y.Neural word embedding as implicit matrix factorization[C]//Proceedings of Advances in Neural Information Processing Systems,2014:2177-2185.
[13]Vincent P,et al.Stacked denoising autoencoders:Learning useful representations in a deep network with a local denoising criterion[J].Journal of Machine Learning Research,2010,11(Dec):3371-3408.
[14]Cao S.Deep neural network for learning graph representations[C]//Proceedings of AAAI.2016.
[15]Wang D,Cui P,Zhu W.Structural deep network embedding[C]//Proceedings of the ACM SIGKDD International Conference,2016:1225-1234.
[16]Ng A Y,et al.On spectral clustering:Analysis and an algorithm[C]//Proceedings of NIPS,2001:849-856.
[17]Newman M E.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577.
[18]Sen P,et al.Collective classification in network data[J].AI Magazine,2008.29(3):93.
[19]Bollacker K D,Lawrence S,Giles C L.CiteSeer:an autonomous Web agent for automatic retrieval and identification of interesting publications[C]//Proceedings of International Conference on Autonomous Agents,1998:116-123.
[20]Zafarani R,Liu H.Social computing data repository at ASU[Z].2009.
[21]Mahoney M.Large text compression benchmark[EB/OL].URL:http://www/.mattmahoney.net/text/text.html,2009.
[22]Breitkreutz B,et al.,The BioGRID interaction database:2008update[J].Nucleic Acids Research,2008,36(suppl 1):D637-D640.
[2]Tenenbaum J B,De Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.
[3]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500):2323-2326.
[4]Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of the NIPS,2001:585-591.
[5]Ahmed A,et al.Distributed large-scale natural graph factorization[C]//Proceedings of the 22nd International Conference on World Wide Web.ACM,2013:37-48.
[6]Cao S,Lu W,Xu Q.Grarep:Learning graph representations with global structural information[C]//Proceedings of the 24th ACM International Conference on Information and Knowledge Management,2015:891-900.
[7]Ou M,et al.Asymmetric transitivity preserving graph embedding[C]//Proceedings of the ACM SIGKDD International Conference,2016:1105-1114.
[8]Perozzi B,R Al-Rfou,Skiena S.Deepwalk:Online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2014:701-710.
[9]Tang J,et al.Line:Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web.2015:1067-1077.
[10]Zheng V W,et al.From node embedding to community embedding[J].arXiv preprint arXiv:1610.09950.2016.
[11]Grover A,Leskovec J.node2vec:Scalable feature learning for networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2016:855-864.
[12]Levy O,Goldberg Y.Neural word embedding as implicit matrix factorization[C]//Proceedings of Advances in Neural Information Processing Systems,2014:2177-2185.
[13]Vincent P,et al.Stacked denoising autoencoders:Learning useful representations in a deep network with a local denoising criterion[J].Journal of Machine Learning Research,2010,11(Dec):3371-3408.
[14]Cao S.Deep neural network for learning graph representations[C]//Proceedings of AAAI.2016.
[15]Wang D,Cui P,Zhu W.Structural deep network embedding[C]//Proceedings of the ACM SIGKDD International Conference,2016:1225-1234.
[16]Ng A Y,et al.On spectral clustering:Analysis and an algorithm[C]//Proceedings of NIPS,2001:849-856.
[17]Newman M E.Modularity and community structure in networks[J].Proceedings of the National Academy of Sciences,2006,103(23):8577.
[18]Sen P,et al.Collective classification in network data[J].AI Magazine,2008.29(3):93.
[19]Bollacker K D,Lawrence S,Giles C L.CiteSeer:an autonomous Web agent for automatic retrieval and identification of interesting publications[C]//Proceedings of International Conference on Autonomous Agents,1998:116-123.
[20]Zafarani R,Liu H.Social computing data repository at ASU[Z].2009.
[21]Mahoney M.Large text compression benchmark[EB/OL].URL:http://www/.mattmahoney.net/text/text.html,2009.
[22]Breitkreutz B,et al.,The BioGRID interaction database:2008update[J].Nucleic Acids Research,2008,36(suppl 1):D637-D640.