main| new issue| archive| editorial board| for the authors| publishing house|
Ðóññêèé
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house

 

 


ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 6. Vol. 31. 2025

DOI: 10.17587/it.31.291-307

P. B. Petrenko, Dr. of Tech. Sc., Professor, Synergy Design Bureau,
Signal Processing Center, St. Petersburg, Russian Federation,
À. S. Tolpygin, Cand. of Tech. Sc.,
Bauman Moscow State Technical University, Moscow, Russian Federation

Graph Neural Networks and their Extensions Based on Hyperbolic Geometry: a Review

Received on 13.08.24
Accepted on 29.10.24

Graph neural networks generalize traditional neural networks for graph-structured data and have attracted wide attention due to their impressive capabilities. They are in demand in machine learning, as they can work with heterogeneous information, help to identify relationships between events and data, provide robustness to incomplete, unclear and noisy data, allow to analysis of large amounts of data and structures in the form of knowledge graphs. Training of graph neural networks in hyperbolic space has gained popularity in recent years due to their ability to model graphs with hidden hierarchical data, and because they are more compact and denser. The purpose of applying non-Euclidean geometry theory in modifying graph neural networks is to ensure their stability and better performance compared to Euclidean neural networks. The review of research and development is devoted to the analysis of modern achievements in the field of graph neural networks creation and consideration of accompanying problems. Particular attention is paid to the issues of graph embedding and their representation in non-Euclidean space. This is due to the fact that the performance of models is largely determined by the embedding algorithms and the choice of geometric space for representing graph structures. The prospectivity and efficiency of this approach have been confirmed by works on the creation of hyperbolic convolutional networks of graphs with the property of controlling the curvature of the space in each layer. At the same time, today there is a need for a more detailed consideration of the possibilities of graph neural networks based on the application of methods of hyperbolic geometry because of the insufficient attention paid to these issues in the domestic literature.
Keywords: graph neural networks (GNN), graph representation learning, hyperbolic geometry, hyperbolic graph neural networks (HGNN), Poincare model, Lorenz model, hyperbolic graph convolutional networks (HGCN), hyperbolic convolutional, hyperbolic deep graph convolutional neural network (HDGCNN)

P. 291-307

Full text on eLIBRARY

References

  1. Broadwater K., Stillman M. Graph Neural Networks in Action. Version 4. MEAP Edition, USA, Manning Publications Co, 2020, 300 ð.
  2. Zonghan W., Pan S., Chen F., Long G. A comprehensive survey on graph neural networks, IEEE Transactions on Neural Networks and Learning Systems, 2020, vol. 32, edition 1, pp. 4—24.
  3. Ward I. R., Joyner J., Lickfold C., Guo Y., Benna-moun M. A Practical Tutorial on Graph Neural Networks, arXiv:2010.05234v3, 2021, pp. 35.
  4. 4. Sperduti A., Starit A. Supervised neural networks for the
    classification of structures, IEEE Transactions on Neural Networks, 1997, vol. 8, no. 3, pp. 714—735.
  5. Zhang Z., Cui P., Zhu W. Deep Learning on Graphs: A Survey, Journal of Latex Class Files, 2015, vol. 14, no. 8, pp. 24.
  6. Nickel M., Kiela D. Poincar'e embeddings for learning hierarchical representations, 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA, 2017, p. 10.
  7. Ritter H. Self-organizing maps on non-Euclidean spaces, In Kohonen maps, Elsevier, 1999, pp. 97—109.
  8. Nickel M., Kiela D. Learning Continuous Hierarchies in the Lorentz Model of Hyperbolic Geometry, Proceedings of the 35th International Conference on Machine Learning (ICML 2018), Stockholm, Sweden, 2018, 10—15 July, pp. 3776—3785.
  9. Zhang Y., Wang X., Shi C., Liu N., Song G. Lorentzian. Graph Convolutional Networks, Proceedings of the The Web Conference (WWW 2021), Ljubljana, Slovenia, 2021, 19—23 April, ACM/IW3C2, 2021, pp. 1249—1261.
  10. Liu Q., Nickel M., Kiela D. Hyperbolic Graph Neural Networks, arXiv:1910.12892v1, 2019.
  11. Bronstein M. M., Bruna J., LeCun Y., Szlam A., Vander-gheynst P. Geometric deep learning: going beyond Euclidean data, IEEE Signal Processing Magazine, 2017, vol. 34, no. 4, pp. 18—42.
  12. Khamsi M. A. An Introduction to Metric Spaces and Fixed-Point Theory, New York, Wiley, 2001, 320 p.
  13. Chami I., Ying Z., R’e C., Leskovec J. Hyperbolic graph convolutional neural networks, Advances in Neural Information Processing Systems, 2019, vol. 32, pp. 4868—4879.
  14. Zamir J. A. R., Savarese S., Saxena A. Structural-RNN: Deep Learning on Spatio-Temporal Graphs, Computer Science, 2016, p. 10.
  15. Wang J., Zheng V. W., Liu Z., Chang K. C.-C. Topological Recurrent Neural Network for Diffusion Prediction, Compute Science, 2017, vol. 1, pp. 475—484.
  16. Chen J., Ma T., Xiao C. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling, Proceedings of the 6th International Conference on Learning Representations (ICLR 2018), Vancouver, BC, Canada, 2018, p. 15.
  17. Bruna J., Zaremba W., Szlam A., LeCun Y. Spectral Networks and Locally Connected Networks on Graphs, Proceedings of the 2nd International Conference on Learning Representations (ICLR 2014), Banff, AB, Canada, ICLR, 2014, p. 14.
  18. 18. Jain A., Zamir A. R., Savarese S., Saxena A. Structural-RNN: Deep Learning on Spatio-Temporal Graphs, Computer Science, 2016, p. 10.
  19. Zhang C., Swami A., Chawla N. V. SHNE: Representation Learning for Semantic-Associated Heterogeneous Networks, Proceedings of the 12th International Conference on Web Search and Data Mining (WSDM 2019), Melbourne, VIC, Australia, 2019, pp. 690—698.
  20. Sahili Z. A., Awad M. Spatio-Temporal Graph Neural Networks: A Survey, Preprint, 2023, 12 p.
  21. Zhang H., Li P., Zhang R., Li X. Embedding Graph Auto-Encoder for Graph Clustering, IEEE Transactions on Neural Networks and Learning Systems, 2022, pp. 11.
  22. Scarselli F., Gori M., A. Chung T., Hagenbuchner M., Monfardini G. The Graph Neural Network Model, IEEE Transactions on Networks, 2009, vol. 20, no. 1, pp. 61—80.
  23. Blasius T., Friedrich T., Katzmann M., Meyer U., Pen-schuck M., Weyand C. Efficiently generating geometric inhomo-geneous and hyperbolic random graphs, Network Science, 2022, pp. 1—20.
  24. Khemani B., Patil S., Kotecha K., Tanwar S. A review of graph neural networks: concepts, architectures, techniques, challenges, datasets, applications, and future directions, Journal of Big Data, 2024, no. 18, pp. 2—40.
  25. Nunes M., Pappa G. L. Neural Architecture Search in Graph Neural Networks, arXiv:2008.00077v1, 2020, p. 15.
  26. LeCun Y., Bottou L., Bengio Y., Haffner P. Gradient-Based Learning Applied to Document Recognition, Proceedings of the IEEE. 1998, vol. 86, no. 11, pp. 2278—2324.
  27. Zhou J., Cui G., Hu S., Zhang Z., Yang C., Liu Z., Wang L., Li C., Sun M. Graph neural networks: A review of methods and applications, AI Open. 2020, vol. 1, pp. 57—81.
  28. Makarov I., Kiselev D., Nikitinsky N., Subelj L. Survey on graph embeddings and their applications to machine learning problems on graphs, Peer. J. Comput. Sci., 2021, p. 62.
  29. Cai H., Zheng V. W., Chang K. C.-C. A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applica­tions, arXiv:1709.07604v3, 2018, p. 20.
  30. Xu M. Understanding graph embedding method and their application, arXiv:2012.08019v1, 2020, p. 34.
  31. Cao S., Lu W., Xu Q. GraRep: Learning graph representa­tions with global structural information, Proceedings of the 24th ACM International on conference on information and knowledge management, 2015, pp. 891—900.
  32. Ou M., Cui P., Pei J., Zhang Z., Zhu W. Asymmetric transitivity preserving graph embedding, Proceedings of the 22nd ACMSIGKDD International conference on Knowledge discovery and datamining, 2016, pp. 1105—1114.
  33. Perozzi B., Al-Rfou R., Skiena S. Deepwalk: Online learning of social representations, Proceedings of the 20th AC-MSIGKDD International conference on Knowledge discovery and datamining, 2014, pp. 701—710.
  34. Tang J., Qu M., Wang M., Zhang M., Yan J., Mei Q. Line: Large-scale information network embedding, Proceedings of the 24th International conference on world wide web, 2015, pp. 1067—1077.
  35. Grover A., Leskovec J. Node2vec: Scalable feature lear­ning for networks,Proceedings of the 22nd ACMSIGKDD In­ternational conference on Knowledge discovery and data mining, 2016, pp. 855—864.
  36. Wang D., Cui P., Zhu W. Structural deep network embedding, Proceedings of the 22nd ACMSIGKDD International conference on Knowledge discovery and datamining, 2016, pp. 1225—1234.
  37. Bojchevski À ., Gunnemann S. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking, Journal reference: International Conference on Learning Representations ICLR, 2018, p. 13.
  38. He S., Liu K., Ji G., Zhao J. Learning to represent knowledge graphs with gaussian embedding, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, 2015, pp. 623—632.
  39. Zhu D., Cui P., Wang D., Zhu W. Deep variational net­work embedding in Wasserstein space, Proceedings of the 24th ACMSIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 2827—2836.
  40. Hoang V. T., Jeon H.-J., You E.-S., Yoon Y., Jung S., Lee O.-J. Graph Representation Learning and Its Applications: A Survey, Sensors (Basel), 2023, vol. 23, no. 8, p. 104.
  41. Nikolentzos G., Siglidis G., Vazirgiannis M. Graph Kernels: A Survey, J. Artif. Intel. Res. , 2021, vol. 72, pp. 943—1027.
  42. Brody S., Alon U., Yahav E. How Attentive are Graph Attention Networks?, Proceedings of the 10th International Conference on Learning Representations (ICLR2022). Virtual Event, 2022, p. 26.
  43. Lee J. B., Rossi R. A., Kim S., Ahmed N. K., Koh E. Attention models in graphs: a survey, ACM Transactions on Knowledge Discovery from Data 2019, vol. 13, no. 6, pp. 1—25.
  44. Abu-El-Haija S., Perozzi B., Al-Rfou R., Alemi A. Watch Your Step: Learning Graph Embeddings Through Attention, arXiv:1710.09599v1. 2017, p. 8.
  45. Krioukov D., Papadopoulos F., Kitsak M., Vahdat A., Boguna M. Hyperbolic geometry of complex networks, Statisti­cal Mechanics. Cornell Univ., 2010, p. 18.
  46. Zhou Y., Huo H., Hou Z., Bu L., Wang Y., Mao J., Lv X., Bu F. An End-To-End Hyperbolic Deep Graph Convolutional Neural Network Framework, Computer Modeling in Engineering & Sciences, 2024, vol. 139, no. 1, pp. 538—563.
  47. Papadopoulos F., Psomas C., Krioukov D. Network Map­ping by Replaying Hyperbolic Growth, IEEE/ACM Transactions on Networking, 2015, vol. 23, no. 1, pp. 198—211.
  48. Kovacs B., Palla G. Model-independent embedding of directed networks into Euclidean and hyperbolic spaces, Communications Physics, 2023, vol. 6, no. 28, p. 16.
  49. Benedetti R., Petronio C. Lectures on hyperbolic geometry. Springer-Verlag Berlin Heidelberg GmbH, 1992, 330 p.
  50. Peng W., Varanka T., Mostafa A., Shi H., Zhao G. Hyperbolic Deep Neural Networks: A Survey, IEEE Trans Pattern. Anal. Mach. Intel., 2022, vol. 44, no. 12, pp. 10023—10044.
  51. Gromov M. Hyperbolic groups. In Essays in group theory. Mathematical Sciences Research Institute Publications, 1987, pp. 75—263.
  52. Dai J., Wu Y., Gao Z., Jia Y. A Hyperbolic-to-Hyperbolic Graph Convolutional Network, Computer Science. Machine Learning, 2021, no. 16, p. 10.
  53. Miller G. A., Beckwith R., Fellbaum C., Gross D., Miller K. Introduction to WordNet: An On-line Lexical Database, International Journal of Lexicography, 1991, p. 87.
  54. Ungar A. A. A gyrovector space approach to hyperbolic geometry, Synthesis Lectures on Mathematics and Statistics, 2008, vol. 1, no. 1, pp. 1—194.
  55. Ungar A. A. Analytic hyperbolic geometry and Albert Einstein's special theory of relativity, World scientific, 2008, 628 p.
  56. Yang M., Zhou M., Li Z., Liu J., Pan L., Xiong H., King I. Hyperbolic Graph Neural Networks: A Review of Methods and Applications, arXiv:2202.13852v2, 2023, p. 13.
  57. Liu Z., Cao S., Li Y., Zikatanov L. Neural networks with trainable matrix activation functions, Preprint, arXiv:2109.09948v5 [cs.LG], 2024, pp. 9, doi:10.48550/arXiv.2109.09948.
  58. Chen W., Han X., Lin Y., Zhao H., Liu Z., Li P., Sun M., Zhou J. Fully Hyperbolic Neural Networks, Proceedings of the 60th Annual Meeting of the Association for Computational Lin­guistics, 2022, vol. 1, pp. 5672—5686.
  59. Moretti V. The interplay of the polar decomposition theo­rem and the Lorentz group, arXiv:math-ph/0211047, 2002, p. 7.
  60. Vermeer J. A geometric interpretation of Ungar's addition and of gyration in the hyperbolic plane, Topology and its Applications, 2005, vol. 152, no. 3, pp. 226—242.
  61. Ungar A. A. Thomas precession and its associated grouplike structure, American Journal of Physics, 1991, vol. 59, no. 9, pp. 824—834.
  62. Fan X., Yang C., Vemuri B. C. Nested Hyperbolic Spaces for Dimensionality Reduction and Hyperbolic, IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2022, pp. 356—365.
  63. Sun L., Zhang Z., Ye J., Peng H., Zhang J., Su S., Yu P. S. A Self-Supervised Mixed-Curvature Graph Neural Network, Proceedings of the AAAI Conference on Artificial Intelligence, 2022, vol. 36, no. 4, pp. 4146—4155.
  64. W. Ju, Y. Wang, Y. Qin, Z. A. Mao, Z. Xiao, J. Luo, J. Yang, Y. Gu, D. Wang, Q. Long, S. Yi, X. Luo, M. Zhang. Towards Graph Contrastive Learning: A Survey and Beyond J. ACM, vol. 1, no. 1, 2024, p. 35.
  65. Fu X., Li J., Wu J., Sun Q., Ji C., Wang S., Tan J., Peng H., Yu P. S. ACE-HGNN: Adaptive Curvature Exploration Hyperbolic Graph Neural Network, 2021 IEEE International Conference on Data Minin g (ICDM), 2021, p. 10.
  66. Liu J., Yang M., Zhou M., Feng S., Fournier-Viger P. Enhancing hyperbolic graph embeddings via contrastive learning, NeurIPS'21. 2nd Workshop on Self-Supervised Learning, 2022, p. 7.
  67. Ni C., Y. Lin, Luo F., Gao J. Community detection on net­works with Ricci flow, Scientific reports, 2019, vol. 9, no. 1, pp. 1—12.
  68. Zhang X., He Y., Brugnone N., Perlmutter M., Hirn M. MagNet: A Neural Network for Directed Graphs, 35th Conference on Neural Information Processing Systems (NeurIPS), 2021, p. 13.
  69. Dosovitskiy A., Springenberg J., Tatarchenko M., Brox T. Learning to Generate Chairs, Tables and Cars with convolutional networks, IEEE Transactions on Pattern Analysis and Machine Intelligence. arXiv:1411.5928v4. 2017, p. 14.
  70. The Hyperbolic Geometry of Networks. Site of the HPI's Algorithm Engineering group lead by Tobias Friedrich. URL: https://hpi.de/friedrich/research/hyperbolic-networks.html.
  71. Wilson R. C., Hancock E. R., Pekalska E., Duin P. W. Spherical and Hyperbolic Embeddings of Data, IEEE Trans Pattern Anal Mach Intelligence, 2014, vol. 36, no. 11, pp. 2255—2269.
  72. Bachmann G., Becigneul G., Ganea O.-E. Constant Curvature Graph Convolutional Networks, Proceedings of the 37 th International Conference on Machine Learning, 2020, p. 11.
  73. Suzuki A., Nitanda A., Wang J., Xu L., Yamanishi K., Cavazza M. Generalization error bound for hyperbolic ordinal embedding, ICML, Proceeding soft he 38th International Conference on Machine Learning, PMLR139, 2021, pp. 10011—10021.
  74. Graph Neural Networks. UBC Wiki. URL: https://wiki. ubc .ca/Graph_Neural_Networks.
  75. Kochurov M., Ivanov S., Burnaev E. Are hyperbolic representations in graphs created equal?, Proceedings of the 37th International Conference on Machine Learning, Vienna, Austria, PMLR 108, 2020, p. 7.
  76. Cao Z., Xu Q., Yang Z., Cao X., Huang Q. Geometry Interaction Knowledge Graph Embeddings, Proceedings of the 36th Conference on Artificial Intelligence (AAAI 2022). Virtual Event. 2022. 22 February—1 March, pp. 5521—5529.
  77. Dedus A. F., Dedus F. F., Makhortykh S. A., Us-tinin M. N. Generalized spectral-analytic method. Part I. Theoretical foundations , Proc. SPIE, 1995, vol. 2363, pp. 109—112
  78. Muhammet B., Guillaume R., Pierre H., Benoit G., Sebastien A., Paul H. When Spectral Domain Meets Spatial Domain in Graph Neural Networks, Conference: ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020, p. 9.
  79. Linial N., London E., Rabinovich Y. The geometry of graphs and some of its algorithmic applications, Combinatorica, 2001, vol. 15, no. 2, pp. 215—245.
  80. Tao Yu, Christopher De Sa. HyLa: Hyperbolic Laplacian Features for Graph Learning, arXiv:2202.06854v1, 2022, p. 11.

To the contents