Community enhancement network embedding based on edge reweighting preprocessing. (English) Zbl 1459.68162
Summary: Network embedding has attracted considerable attention in recent years. It represents nodes in a network into a low-dimensional vector space while keeping the properties of the network. Some methods (e.g. ComE, MNMF, and CARE) have been proposed to preserve the community property in network embedding, and they have obtained good results in some downstream network analysis tasks. However, there still exists a significant challenge because nodes may lose important structural information following embedding. To address this problem, we propose a community structure enhancement framework for network embedding, based on edge reweighting. Through edge reweighting, the weight of intra-community edges is increased while the weight of inter-community edges is decreased. Therefore, after embedding, nodes in the same community are closer to each other than nodes in different communities in the embedding space. We apply the edge reweighting as a preprocessing stage in network embedding, and construct an enhanced network by incorporating enhanced community structures into the original network. By doing this, the embedded vectors from the enhanced network can better perform all downstream network analysis tasks. Extensive experiments are conducted on two network analysis tasks (community detection and node classification) with synthetic and real-world datasets. The results show that our method outperforms state-of-the-art network embedding methods.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68W40 | Analysis of algorithms |
References:
| [1] | Cui P, Wang X, Pei J and Zhu W 2018 A survey on network embedding IEEE Trans. Knowl. Data Eng.31 833-52 · doi:10.1109/tkde.2018.2849727 |
| [2] | Perozzi B, Al-Rfou R and Skiena S 2014 Deepwalk: online learning of social representations Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (New York: ACM) 701-10 |
| [3] | Grover A and Leskovec J 2016 node2vec: scalable feature learning for networks Proc. 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (New York: ACM) 855-64 · doi:10.1145/2939672.2939754 |
| [4] | Zhang F, Yuan N J, Lian D, Xie X and Ma W-Y 2016 Collaborative knowledge base embedding for recommender systems Proc. 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (New York: ACM) 353-62 · doi:10.1145/2939672.2939673 |
| [5] | Wang X, Cui P, Wang J, Pei J, Zhu W and Yang S 2017 Community preserving network embedding 31st AAAI Conference on Artificial Intelligence |
| [6] | Cavallari S, Zheng V W, Cai H, Chang Kevin C-C and Cambria E 2017 Learning community embedding with community detection and node embedding on graphs Proc. 2017 ACM on Conf. on Information and Knowledge Management (New York: ACM) 377-86 |
| [7] | Keikha M M, Rahgozar M and Asadpour M 2018 Community aware random walk for network embedding Knowl.-Based Syst.148 47-54 · doi:10.1016/j.knosys.2018.02.028 |
| [8] | Jin D, You X, Li W, He D, Cui P, Fogelman-Soulié F and Chakraborty T 2019 Incorporating network embedding into markov random field for better community detection 33rd AAAI Conf. on Artificial Intelligence |
| [9] | Xiang J et al 2016 Enhancing community detection by using local structural information J. Stat. Mech. 033405 · Zbl 1457.91314 · doi:10.1088/1742-5468/2016/03/033405 |
| [10] | Cai H, Zheng V W and Chang K C-C 2018 A comprehensive survey of graph embedding: problems, techniques, and applications IEEE Trans. Knowl. Data Eng.30 1616-37 · doi:10.1109/tkde.2018.2807452 |
| [11] | Goyal P and Ferrara E 2018 Graph embedding techniques, applications, and performance: a survey Knowl.-Based Syst.151 78-94 · doi:10.1016/j.knosys.2018.03.022 |
| [12] | Zhang D, Yin J, Zhu X and Zhang C 2020 Network representation learning: a survey IEEE Trans. Big Data6 3-28 · doi:10.1109/TBDATA.2018.2850013 |
| [13] | Mikolov T 2013 Distributed representations of words and phrases and their compositionality Advances in Neural Information Processing Systems26 3111-9 |
| [14] | Cao S, Lu W and Xu Q 2015 Grarep: learning graph representations with global structural information Proc. 24th ACM Int. on Conf. on Information and Knowledge Management (New York: ACM) 891-900 |
| [15] | Tang J, Qu M, Wang M, Zhang M, Yan J and Mei Q 2015 Line: large-scale information network embedding Proc. 24th Int. Conf. on World Wide Web 1067-77 |
| [16] | Zhang Y, Lyu T and Zhang Y 2018 Cosine: community-preserving social network embedding from information diffusion cascades 32nd AAAI Conf. on Artificial Intelligence |
| [17] | Wang D, Cui P and Zhu W 2016 Structural deep network embedding Proc. 22nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (New York: ACM) 1225-34 · doi:10.1145/2939672.2939753 |
| [18] | Cao S, Lu W and Xu Q 2016 Deep neural networks for learning graph representations 30th AAAI Conf. on Artificial Intelligence |
| [19] | Zhang Z, Yang H, Bu J, Zhou S, Yu P and Zhang J 2018 Martin Ester, and Can Wang. Anrl: attributed network representation learning via deep neural networks IJCAI18 3155-61 |
| [20] | Yu W, Zheng C, Cheng W, Aggarwal C C and Wang W 2018 Learning deep network representations with adversarially regularized autoencoders 24th ACM SIGKDD Int. Conf. of Knowledge Discovery and Data Mining · doi:10.1145/3219819.3220000 |
| [21] | Wang S, Tang J, Aggarwal C, Chang Y and Liu H 2017 Signed network embedding in social media Proc. 2017 SIAM Int. Conf. on Data Mining (Philadelphia, PA: SIAM) 327-35 |
| [22] | Yuan S, Wu X and Yang X 2017 Sne: signed network embedding Pacific-Asia Conf. on Knowledge Discovery and Data Mining (Berlin: Springer) 183-95 · doi:10.1007/978-3-319-57529-2_15 |
| [23] | Kim J, Park H, Lee J-E and Kang U 2018 Side: representation learning in signed directed networks Proc. of The 2018 World Wide Web Conf. 509-18 |
| [24] | Gao M, Chen L, He X and Zhou A 2018 Bine: bipartite network embedding 41st Int. ACM SIGIR Conf. on Research & Development in Information Retrieval (New York: ACM) 715-24 |
| [25] | Li J, Dani H, Hu X, Tang J, Chang Y and Liu H 2017 Attributed network embedding for learning in a dynamic environment Proc. 2017 ACM on Conf. on Information and Knowledge Management (New York: ACM) 387-96 |
| [26] | Zhu D, Cui P, Zhang Z, Pei J and Zhu W 2018 High-order proximity preserved embedding for dynamic networks IEEE Trans. Knowl. Data Eng.30 2134-44 · doi:10.1109/TKDE.2018.2822283 |
| [27] | Du L, Wang Y, Song G, Lu Z and Wang J 2018 Dynamic network embedding: an extended approach for skip-gram based network embedding IJCAI 2086-92 |
| [28] | Dong Y, Chawla N V and Swami A 2017 metapath2vec: scalable representation learning for heterogeneous networks Proc. 23rd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (New York: ACM) 135-44 |
| [29] | Xu L, Wei X, Cao J and Philip S Y 2017 Embedding of embedding (eoe): joint embedding for coupled heterogeneous networks Proc. 10th ACM Int. Conf. on Web Search and Data Mining (New York: ACM) 741-9 |
| [30] | Chang S, Han W, Tang J, Qi G-J, Aggarwal C C and Huang T S 2015 Heterogeneous network embedding via deep architectures Proc. 21st ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (New York: ACM) 119-28 · doi:10.1145/2783258.2783296 |
| [31] | van der Maaten L and Hinton G 2008 Visualizing data using t-sne J. Mach. Learn. Res.9 2579-605 · Zbl 1225.68219 |
| [32] | Lai D, Lu H and Nardini C 2010 Enhanced modularity-based community detection by random walk network preprocessing Phys. Rev. E 81 066118 · doi:10.1103/physreve.81.066118 |
| [33] | Pons P and Latapy M 2005 Computing communities in large networks using random walks Int. Symp. on Computer and Information Sciences (Berlin: Springer) 284-93 |
| [34] | Xiang J et al 2019 Identifying multi-scale communities in networks by asymptotic surprise J. Stat. Mech. 033403 · Zbl 1539.91103 |
| [35] | Benesty J, Chen J, Huang Y and Cohen I 2009 Pearson correlation coefficient Noise Reduction in Speech Processing (Berlin: Springer) pp 1-4 |
| [36] | Parlett B N and Scott D S 1979 The lanczos algorithm with selective orthogonalization Math. Comput.33 217-38 · Zbl 0405.65015 · doi:10.1090/s0025-5718-1979-0514820-3 |
| [37] | Fortunato S and Hric D 2016 Community detection in networks: a user guide Phys. Rep.659 1-44 · doi:10.1016/j.physrep.2016.09.002 |
| [38] | Lancichinetti A, Fortunato S and Radicchi F 2008 Benchmark graphs for testing community detection algorithms Phys. Rev. E 78 046110 · doi:10.1103/physreve.78.046110 |
| [39] | Tang L and Liu H 2009 Relational learning via latent social dimensions Proc. 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining 817-26 |
| [40] | Stark C et al 2010 The biogrid interaction database: 2011 update Nucleic Acids Res.39 D698-704 · doi:10.1093/nar/gkq1116 |
| [41] | Toutanova K, Klein D, Manning C D and Singer Y 2003 Feature-rich part-of-speech tagging with a cyclic dependency network Proc. 2003 Conf. of The North American Chapter of The Association for Computational Linguistics on Human Language Technology 173-80 |
| [42] | Qiu J, Dong Y, Ma H, Li J, Wang K and Tang J 2018 Network embedding as matrix factorization: unifying deepwalk, line, pte, and node2vec Proc. 11th ACM Int. Conf. on Web Search and Data Mining (New York: ACM) 459-67 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
