TPM: Transition probability matrix - Graph structural feature based embedding

Sarmad N. Mohammed; Semra Gündüç

Kybernetika (2023)

  • Volume: 59, Issue: 2, page 234-253
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

N. Mohammed, Sarmad, and Gündüç, Semra. "TPM: Transition probability matrix - Graph structural feature based embedding." Kybernetika 59.2 (2023): 234-253. <http://eudml.org/doc/299089>.

@article{N2023,
abstract = {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.},
author = {N. Mohammed, Sarmad, Gündüç, Semra},
journal = {Kybernetika},
keywords = {graph representation learning; feature learning; link prediction; node classification; anonymous random walk},
language = {eng},
number = {2},
pages = {234-253},
publisher = {Institute of Information Theory and Automation AS CR},
title = {TPM: Transition probability matrix - Graph structural feature based embedding},
url = {http://eudml.org/doc/299089},
volume = {59},
year = {2023},
}

TY - JOUR
AU - N. Mohammed, Sarmad
AU - Gündüç, Semra
TI - TPM: Transition probability matrix - Graph structural feature based embedding
JO - Kybernetika
PY - 2023
PB - Institute of Information Theory and Automation AS CR
VL - 59
IS - 2
SP - 234
EP - 253
AB - 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.
LA - eng
KW - graph representation learning; feature learning; link prediction; node classification; anonymous random walk
UR - http://eudml.org/doc/299089
ER -

References

top
  1. Albert, R., Barabási, A., , Rev. Mod. Phys. 74 (2002), 47-97. MR1895096DOI
  2. Barabási, A., , Phil. Trans. R. Soc. A. 371 (2013), 20120375. DOI
  3. Barabási, A., Bonabeau, E., , Scientif. Amer. 288 (2003), 60-69. DOI
  4. Battaglia, P. W., Hamrick, J. B., Bapst, V., Sanchez-Gonzalez, A., Zambaldi, V., al., et, , ArXiv, 2018. DOI
  5. Bhagat, S., Cormode, G., Muthukrishnan, S., , In: Social Network Data Analytics (C. Aggarwal, ed.), Springer, Boston 2011. MR3014047DOI
  6. Buffelli, D., Vandin, F., , Data 7 (2022), 10. DOI
  7. Cetin, P., Amrahov, S. Emrah, , Kybernetika 58 (2022), 277-300. MR4467497DOI
  8. Cetin, P., Amrahov, Ş. E., , Turk. J. Electr. Eng. Co. 30 (2022), 2190-2205. DOI
  9. Cherifi, H., Palla, G., Szymanski, B. K., Lu, X., , Appl. Netw. Sci. 4 (2019), 1-35. MR3617263DOI
  10. Chi, K., Yin, G., Dong, Y., Dong, H., , Knowledge-Based Systems 181 (2019), 0950-7051. DOI
  11. Fortunato, S., , Phys. Rep. 486 (2010), 75-174. MR2580414DOI
  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., , Proc. Nat. Acad. Sci. 99 (2002), 7821-7826. MR1908073DOI
  14. Grover, A., Leskovec, J., , 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., , IEEE Trans. Inf. Forensics Security 12 (2017), 2242-2255. DOI
  17. Hanley, J. A., McNeil, B. J., , 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., , Soc. Netw. Anal. Min. 9 (2019), 1-11. DOI
  20. Kipf, T. N., Welling, M., Semi-supervised classification with graph convolutional networks., https://arxiv.org/abs/1609.02907, 2016. 
  21. Kossinets, G., Watts, D. J., , Science 311 (2006), 88-90. MR2192483DOI
  22. Lancichinetti, A., Fortunato, S., Radicchi, F., , Phys. Rev. E 78 (2008), 046110. DOI
  23. Liben-Nowell, D., Kleinberg, J., , 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., , ACM Comput. Surv. 49 (2016), 1-33. MR3431093DOI
  25. McCallum, A. K., Nigam, K., Rennie, J., Seymore, K., , Inform, Retrieval 3 (2000), 127-163. DOI
  26. Mele, A., , J. Bus. Econom. Statist. 40 (2022), 1377-1389. MR4439296DOI
  27. Micali, S., Zhu, Z. A., , Discrete Appl. Math. 200 (2016), 108-122. MR3442578DOI
  28. Mohammed, S. N., Gündüç, S., , Turk. J. Electr. Eng. Co. 30 (2022), 1868-1881. DOI
  29. Molokwu, B., Shuvo, S. B., Kar, N. C., Kobti, Z., , 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., , Nature 435 (2005), 814-818. DOI
  31. Pavlopoulou, M. E. G., Tzortzis, G., Vogiatzis, D., Paliouras, G., , 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., , 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., , AI Magazine 29 (2008), 93-93. DOI
  34. Sun, K., Wang, L., Xu, B., Zhao, W., Teng, S. W., Xia, F., , IEEE Access 8 (2020), 205600-205617. DOI
  35. Tamassia, R., , Chapman and Hall/CRC, New York 2013. MR3156770DOI
  36. Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., Mei, Q., , 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., , Kybernetika 57 (2021), 15-37. MR4231854DOI
  39. Xie, Y., Jin, P., Gong, M., Zhang, C., Yu, B., , Front. Neurosci. 14 (2020), 1. MR4495032DOI
  40. Xu, M., , SIAM Rev. 63 (2021), 825-853. MR4334532DOI
  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., , IEEE Trans. Knowl. Data Eng. 34 (2020), 249-270. DOI
  43. Zhang, X. M., Liang, L., Liu, L., Tang, M. J., , Front, Genetics 12 (2021), 690049. DOI

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.