Madhav CHANDANE, Pranav NERURKAR, Sunil BHIRUD

Survey of network embedding techniques for social networks

High dimensionality of data is a challenging scenario in the current era as the digital transformation ofthe society is in process. This problem is particularly complex in social networks as in such systems, it is coupledwith other challenges such as interdependency of data points and heterogeneity of data sources. To overcome suchdisadvantages and aid in creation of downstream applications for social network analysis, network embedding techniqueshave been proposed. These techniques, in themselves, are not important but are the backbone of various network-basedapplications. Due to the scientific interest in this domain there has been a mushrooming of embedding techniques. Ithas therefore become crucial to learn the intuitions behind these techniques in order to compare and contrast them.The current analytical study is drawn with the following broad objectives: providing practitioners with understandingof network representative learning mathematical study of state-of-the-art techniques and highlighting the evolution ofthe literature in this field.

PDF

___

[1] Denny M. Social Network Analysis. Institute for Social Science Research, University of Massachusetts, Amherst, MA, USA: Academic Press, 2014.
[2] Pei J, Zhu W, Cui P, Wang X. A survey on network embedding. IEEE Transactions on Knowledge and Data Engineering 2018; 21: 126-139.
[3] Denny M. Intermediate Social Network Theory. Institute for Social Science Research, University of Massachusetts, Amherst, MA, USA: Academic Press, 2015.
[4] Hoff PD, Raftery AE, Handcock MS. Latent space approaches to social network analysis. Journal of the American Statistical Association 2002; 64: 1090-1098.
[5] Snijders TAB. Longitudinal methods of network analysis. Encyclopedia of Complexity and System Science 2009; 24: 5998–6013.
[6] Ferrara E, Galstyan A, Goyal P, Hosseinmardi H. Capturing edge attributes via network embedding. arXiv preprint 2018; arXiv:1805.03280.
[7] Hu X, Huang X, Li J. Label informed attributed network embedding. In: ACM 2017 Proceedings of the Tenth International Conference on Web Search and Data Mining; New York, NY, USA; 2017. pp. 731-739.
[8] Hu X Huang X, Li J. Accelerated attributed network embedding. In: SIAM 2017 Proceedings of the International Conference on Data Mining; Houston, TX, USA; 2017. pp. 633-641.
[9] Tang J, Qu M, Wang M, Zhang M, Yan J et al. Line: Large-scale information network embedding. In: WWW 2015 Proceedings of the 24th International Conference on World Wide Web; Florence, Italy; 2015. pp. 1067-1077.
[10] Huang X, Li J, Hu X. Label informed attributed network embedding. In: ACM 2017 Proceedings of the Tenth International Conference on Web Search and Data Mining; Cambridge, United Kingdom; 2017. pp. 731–739.
[11] Huang X, Li J, Hu X. Accelerated attributed network embedding. In: ACM 2017 Proceedings of the SIAM International Conference on Data Mining; Notre Dame, IN, USA; 2017. pp. 633-641.
[12] Zhang H, Chua TS, Liao L, He X. Attributed social network embedding. arXiv preprint 2017; arXiv:1705.04969.
[13] Bandyopadhyay S, Kara H, Kannan A, Murty MN. Fscnmf: Fusing structure and content via nonnegative matrix factorization for embedding information networks. arXiv preprint 2018; arXiv:1804.05313.
[14] Tsitsulin A, Mottin D, Karras P, Muller E. Verse: Versatile graph embeddings from similarity measures. In: WWW 2018 Proceedings of the Conference on World Wide Web; Lyon, France; 2018. pp. 539–548.
[15] Ou M, Cui P, Pei J, Zhang Z, Zhu W. Asymmetric transitivity preserving graph embedding. In: ACM 2016 Proceedings of the 22nd SIGKDD International Conference on Knowledge Discovery and Data Mining; San Francisco, CA, USA; 2016. pp. 1105–1114.
[16] Rozemberczki B, Davies R, Sarkar R, Sutton C. Gemsec: Graph embedding with self clustering. arXiv preprint 2018; arXiv:1802.03997.
[17] Rozemberczki B, Sarkar R. Fast sequence based embedding with diffusion graphs. In: Springer 2018 International Conference on Complex Networks; Cambridge, United Kingdom; 2018. pp. 99-107.
[18] Yang Z, Cohen WW, Salakhutdinov R. Revisiting semi-supervised learning with graph embeddings. arXiv preprint 2016; arXiv:1603.08861.
[19] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations. In: ACM 2014 Proceedings of the 20th SIGKDD International Conference on Knowledge Discovery and Data Mining; Washington, DC, USA; 2014. pp. 701-710.
[20] Grover A, Leskovec J. node2vec: Scalable feature learning for networks. In: ACM 2016 Proceedings of the 22nd SIGKDD International Conference on Knowledge Discovery and Data Mining; San Francisco, CA, USA; 2016. pp. 855-864.
[21] Sheikh N, Kefato Z, Montresor A. gat2vec: representation learning for attributed graphs. Computing 2018; 9: 1-23.
[22] Mikolov T, Sutskever I, Chen K, Corrado GS, Dean J. Distributed representations of words and phrases and their compositionality. Advances in Neural Information Processing Systems 2013; 23: 3111–3119.
[23] Cao S, Lu W, Xu Q. Grarep: Learning graph representations with global structural information. In: ACM 2015 Proceedings of the 24th International on Conference on Information and Knowledge Management; Melbourne, VIC, Australia; 2015. pp. 891-900.
[24] Liu Q, Li Z, Lui J, Cheng J. Powerwalk: Scalable personalized pagerank via random walks with vertex centric decomposition. In: ACM 2016 Proceedings of the 25th International on Conference on Information and Knowledge Management; Indianapolis, Indiana, USA; 2016. pp. 195-204.
[25] Pandhre S, Mittal H, Gupta M, Balasubramanian VN. Stwalk: learning trajectory representations in temporal graphs. In: ACM 2018 Proceedings of the Joint International Conference on Data Science and Management of Data; Goa, India; 2018. pp. 210-219.
[26] Mikolov T, Chen K, Corrado G, Dean J. Efficient estimation of word representations in vector space. arXiv preprint 2013; arXiv:1301.3781.
[27] Lin Y, Liu Z, Sun M, Liu Y, Zhu X. Learning entity and relation embeddings for knowledge graph completion. In: AAAI 2015 Proceedings of the Twenty-Ninth Conference on Artificial Intelligence; Austin, Texas, USA; 2015. pp. 2181-2187.
[28] Wang Z, Ye X, Wang C, Wu Y, Wang C et al. Rsdne: Exploring relaxed similarity and dissimilarity from completelyimbalanced labels for network embedding. Network 2018; 11: 14-26.
[29] Zhang M, Cui Z, Neumann M, Chen Y. An end-to-end deep learning architecture for graph classification. In: AAAI 2018 Proceedings of Conference on Artificial Intelligence; New Orleans, LA, USA; 2018. pp. 531-538.
[30] Welling M, Kipf TN. Semisupervised classification with graph convolutional networks. arXiv preprint 2016; arXiv:1609.02907.
[31] Leskovec J, Zitnik M, Agrawal M. Modeling polypharmacy side effects with graph convolutional networks. arXiv preprint 2018; arXiv:1802.00543.
[32] Zitnik M, Leskovec J. Predicting multicellular function through multilayer tissue networks. Bioinformatics 2017, 33: 190-198.
[33] Balasubramanian M, Schwartz EL. The isomap algorithm and topological stability. Science 2002; 295: 7.
[34] Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science 2000; 290: 2323-2326.
[35] Zhu Q, Kaplan L, Han J, Shi Y, Gui H. Aspem: Embedding learning by aspects in heterogeneous information networks. In: SIAM 2018 Proceedings of the International Conference on Data Mining; San Diego, California, USA; 2018. pp. 144-152.
[36] Liao L, He X, Zhang H, Chua TS. Attributed social network embedding. arXiv preprint 2017; arXiv:1705.04969.
[37] Ozer Z, Ozer I, Findik O. Diacritic restoration of Turkish tweets with word2vec. Engineering Science and Technology 2018; 21: 1120-1127.
[38] Perozzi B, Kulkarni V, Chen H, Skiena S. Don’t walk, skip!: online learning of multiscale network embeddings. In: ACM 2017 Proceedings of the International Conference on Advances in Social Networks Analysis and Mining; Sydney, Australia; 2017. pp. 258-265.
[39] Zhao D, Sun M, Chang EY, Yang C, Liu Z. Network representation learning with rich text information. In: TwentyFourth International Joint Conference on Artificial Intelligence; Buenos Aires, Argentina; 2015. pp. 2111-2117.
[40] Hamilton W, Ying Z, Leskovec J. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems 2017; 31: 1024-1034.
[41] Scarselli F, Gori M, Tsoi AC, Hagenbuchner, M, Monfardini, G. The graph neural network model. IEEE Transactions on Neural Networks 2005; 20: 61-80.
[42] Chen CM, Tsai MF, Lin YC, Yang YH. Query-based music recommendations via preference embedding. In: ACM 2016 Proceedings of the 10th Conference on Recommender Systems; Boston, MA, USA; 2016. pp. 79-82.
[43] Song L, Dai H, Dai B. Discriminative embeddings of latent variable models for structured data. In: ACM 2016 Proceedings of the 33rd International Conference on Machine Learning; New York, NY, USA; 2016. pp. 2702-2711.
[44] Narayanan A, Chandramohan M, Chen L, Liu Y, Saminathan S. Subgraph2vec: Learning distributed representations of rooted subgraphs from large graphs. arXiv preprint 2016; arXiv:1606.08928.
[45] Hamilton W, Ying Z, Leskovec J. Representation learning on graphs: methods and applications. arXiv preprint 2017; arXiv:1709.05584.
[46] Bronstein MM, Bruna J, LeCun Y, Szlam A, Vandergheynst P. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine 2017; 34: 18-42.
[47] Mei Q, Tang J, Qu M. Pte: Predictive text embedding through large-scale heterogeneous text networks. In: ACM 2015 Proceedings of the 21th SIGKDD International Conference on Knowledge Discovery and Data Mining; Sydney, NSW, Australia; 2015. pp. 1165-1174.
[48] Li Y, Tarlow D, Brockschmidt M, Zemel R. Gated graph sequence neural networks. arXiv preprint 2016; arXiv:1511.05493.
[49] Chen J, Ma T, Xiao C. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv preprint 2018; arXiv:1801.10247.
[50] Kunegis J. Handbook of network analysis [konect–the koblenz network collection]. arXiv preprint 2014; arXiv:1402.5500.
[51] Preusse J, Kunegis J. Fairness on the web: Alternatives to the power law. In: ACM 2012 Proceedings of the 4th Annual Web Science Conference; Evanston, IL, USA; 2012. pp. 175-184.