TPM: Transition probability matrix - Graph structural feature based embedding

Mohammed, Sarmad N. ; Gündüç, Semra

Kybernetika, Tome 59 (2023) no. 2, pp. 234-253

Abstract (VO)

In this work, Transition Probability Matrix (TPM) is proposed as a new method for extracting the features of nodes in the graph. The proposed method uses random walks to capture the connectivity structure of a node's close neighborhood. The information obtained from random walks is converted to anonymous walks to extract the topological features of nodes. In the embedding process of nodes, anonymous walks are used since they capture the topological similarities of connectivities better than random walks. Therefore the obtained embedding vectors have richer information about the underlying connectivity structure. The method is applied to node classification and link prediction tasks. The performance of the proposed algorithm is superior to the state-of-the-art algorithms in the recent literature. Moreover, the extracted information about the connectivity structure of similar networks is used to link prediction and node classification tasks for a completely new graph.

Détail

DOI : 10.14736/kyb-2023-2-0234

Classification : 05C82, 94C15
Keywords: graph representation learning; feature learning; link prediction; node classification; anonymous random walk

Bibliographie

[1] Albert, R., Barabási, A.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74 (2002), 47-97. | DOI | MR

[2] Barabási, A.: Network science. Phil. Trans. R. Soc. A. 371 (2013), 20120375. | DOI

[3] Barabási, A., Bonabeau, E.: Scale-free networks. Scientif. Amer. 288 (2003), 60-69. | DOI

[4] Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., al., et: Relational inductive biases, deep learning, and graph networks. ArXiv, 2018. | arXiv

[5] Bhagat, S., Cormode, G., Muthukrishnan, S.: Node classification in social networks. In: Social Network Data Analytics (C. Aggarwal, ed.), Springer, Boston 2011. | DOI | MR

[6] Buffelli, D., Vandin, F.: The impact of global structural information in graph neural networks applications. Data 7 (2022), 10. | DOI

[7] Cetin, P., Amrahov, S. Emrah: A new overlapping community detection algorithm based on similarity of neighbors in complex networks. Kybernetika 58 (2022), 277-300. | DOI | MR

[8] Cetin, P., Amrahov, Ş. E.: A new network-based community detection algorithm for disjoint communities. Turk. J. Electr. Eng. Co. 30 (2022), 2190-2205. | DOI

[9] Cherifi, H., Palla, G., Szymanski, B. K., Lu, X.: On community structure in complex networks: challenges and opportunities. Appl. Netw. Sci. 4 (2019), 1-35. | DOI | MR

[10] Chi, K., Yin, G., Dong, Y., Dong, H.: Link prediction in dynamic networks based on the attraction force between nodes. Knowledge-Based Systems 181 (2019), 0950-7051. | DOI

[11] Fortunato, S.: Community detection in graphs. Phys. Rep. 486 (2010), 75-174. | DOI | MR

[12] Giles, C. L., Bollacker, K. D., Lawrence, S.: CiteSeer: An automatic citation indexing system. In: Proc. Third ACM conference on Digital libraries, 1998, pp. 89-98.

[13] Girvan, M., Newman, M. E. J.: Community structure in social and biological networks. Proc. Nat. Acad. Sci. 99 (2002), 7821-7826. | DOI | MR

[14] Grover, A., Leskovec, J.: node2vec: Scalable feature learning for networks. In: Proc. 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York 2016, pp. 855-864. | DOI

[15] Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. In: 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach 2017.

[16] Han, X., Wang, L., Cui, C., Ma, J., Zhang, S.: Linking multiple online identities in criminal investigations: A spectral co-clustering framework. IEEE Trans. Inf. Forensics Security 12 (2017), 2242-2255. | DOI

[17] Hanley, J. A., McNeil, B. J.: The meaning and use of the area under a receiver operating characteristic (ROC) curve. Radiology 143 (1982), 29-36. | DOI

[18] Ivanov, S., Burnaev, E.: Anonymous walk embeddings. In: Proc. 35th International Conference on Machine Learning, 2018, pp. 2186-2195.

[19] Khafaei, T., Taraghi, A. Tavakoli, Hosseinzadeh, M., Rezaee, A.: Tracing temporal communities and event prediction in dynamic social networks. Soc. Netw. Anal. Min. 9 (2019), 1-11. | DOI

[20] Kipf, T. N., Welling, M.: Semi-supervised classification with graph convolutional networks. , 2016. | arXiv

[21] Kossinets, G., Watts, D. J.: Empirical analysis of an evolving social network. Science 311 (2006), 88-90. | DOI | MR

[22] Lancichinetti, A., Fortunato, S., Radicchi, F.: Benchmark graphs for testing community detection algorithms. Phys. Rev. E 78 (2008), 046110. | DOI

[23] Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. In: Proc. twelfth international conference on Information and knowledge management, New Orleans 2003, pp. 556-559. | DOI

[24] Martínez, V., Berzal, F., Cubero, J.: A survey of link prediction in complex networks. ACM Comput. Surv. 49 (2016), 1-33. | DOI | MR

[25] McCallum, A. K., Nigam, K., Rennie, J., Seymore, K.: Automating the construction of internet portals with machine learning. Inform, Retrieval 3 (2000), 127-163. | DOI

[26] Mele, A.: A structural model of homophily and clustering in social networks. J. Bus. Econom. Statist. 40 (2022), 1377-1389. | DOI | MR

[27] Micali, S., Zhu, Z. A.: Reconstructing markov processes from independent and anonymous experiments. Discrete Appl. Math. 200 (2016), 108-122. | DOI | MR

[28] Mohammed, S. N., Gündüç, S.: Degree-based random walk approach for graph embedding. Turk. J. Electr. Eng. Co. 30 (2022), 1868-1881. | DOI

[29] Molokwu, B., Shuvo, S. B., Kar, N. C., Kobti, Z.: Node classification and link prediction in social graphs using RLVECN. In: 32nd International Conference on Scientific and Statistical Database Management, Vienna 2020, pp. 1-10. | DOI

[30] Palla, G., Derényi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435 (2005), 814-818. | DOI

[31] Pavlopoulou, M. E. G., Tzortzis, G., Vogiatzis, D., Paliouras, G.: Predicting the evolution of communities in social networks using structural and temporal features. In: 12th International Workshop on Semantic and Social Media Adaptation and Personalization (SMAP), Bratislava 2017, pp. 40-45. | DOI

[32] Perozzi, B., Al-Rfou, R., Skiena, S.: Deepwalk: Online learning of social representations. In: Proc. 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York 2014, pp. 701-710. | DOI

[33] Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., Eliassi-Rad, T.: Collective classification in network data. AI Magazine 29 (2008), 93-93. | DOI

[34] Sun, K., Wang, L., Xu, B., Zhao, W., Teng, S. W., Xia, F.: Network representation learning: From traditional feature learning to deep learning. IEEE Access 8 (2020), 205600-205617. | DOI

[35] Tamassia, R.: Handbook of Graph Drawing and Visualization. (First edition. Chapman and Hall/CRC, New York 2013. | DOI | MR

[36] Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q.: Line: Large-scale information network embedding. In: Proceedings of the 24th International Conference on World Wide Web, Florence, Italy, 2015, pp. 1067-1077. | DOI

[37] Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., Bengio, Y.: Graph attention networks. Stat. 20 (2017), 10-48550.

[38] Vencálek, O., Hlubinka, D.: A depth-based modification of the k-nearest neighbour method. Kybernetika 57 (2021), 15-37. | DOI | MR

[39] Xie, Y., Jin, P., Gong, M., Zhang, C., Yu, B.: Multi-task network representation learning. Front. Neurosci. 14 (2020), 1. | DOI | MR

[40] Xu, M.: Understanding graph embedding methods and their applications. SIAM Rev. 63 (2021), 825-853. | DOI | MR

[41] Zaki, M. J., Meira, W.: Data Mining and Analysis: Fundamental Concepts and Algorithms. Cambridge University Press, 2014.

[42] Zhang, Z., Cui, P., Zhu, W.: Deep learning on graphs: A survey. IEEE Trans. Knowl. Data Eng. 34 (2020), 249-270. | DOI

[43] Zhang, X. M., Liang, L., Liu, L., Tang, M. J.: Graph neural networks and their current applications in bioinformatics. Front, Genetics 12 (2021), 690049. | DOI