V.S. Gavrilov1, R.A. Kochkarov2, A.A. Kochkarov3, D.V. Serdechny4, S.A. Korchagin5

1–5 Financial University under the Government of the Russian Federation (Moscow, Russia)

1 232114@edu.fa.ru, 2 rkochkarov@fa.ru, 3 akochkarov@fa.ru, 4 dvserdechny@fa.ru, 5 sakorchagin@fa.ru

Generating realistic and diverse graph structures is an important task in the field of machine learning and artificial intelligence. Many real-world network structures, such as social networks, biological networks, and transportation networks, have complex fractal and hierarchical characteristics that must be taken into account when modeling and analyzing such systems. Traditional graph generation methods often fail to reproduce these important features, which limits their application. Develop a new algorithm for generating graph structures based on the analysis of existing methods, which will allow creating realistic graphs with fractal and hierarchical properties. The proposed algorithm should provide flexibility in managing the characteristics of the generated graphs to cover a wide range of applications. A new algorithm for generating graph structures based on the principles of fractal geometry and hierarchical com-position. The proposed algorithm allows creating graphs with realistic topological properties, such as power-law distribution of node degrees, high clustering. In addition, the authors demonstrated that the generated graphs can have self-similar and fractal characteristics. The developed approach to generating graph structures has a wide range of practical applications. The obtained graphs can be used to test and evaluate algorithms for analyzing networks, news flows, modeling dynamic processes on networks, and as synthetic data for training machine learning models. In addition, the proposed method can be applied to generate realistic model networks in various fields, such as economics, finance, sociology, transport and information technology

Gavrilov V.S., Kochkarov R.A., Kochkarov A.A., Serdechny D.V., Korchagin S.A. Generation of deep graphs with elements of fractal structure and their application on the example of modeling news networks. Neurocomputers. 2024. V. 26. № 6. Р. 86-98. DOI: https://doi.org/10.18127/j19998554-202406-11 (In Russian)

1. Freire M, Antunes F, Costa J.P. Enhancing decision-making support by mining social media data with social network analysis. Social Network Analysis and Mining. 2023. V. 13. № 1. P. 86. DOI 10.1007/s13278-023-01089-6.
2. Porokhin V., Liu Li.P., Hassoun S. Using graph neural networks for site-of-metabolism prediction and its applications to ranking pro-miscuous enzymatic products. Bioinformatics. 2023. V. 39. № 3. DOI 10.1093/bioinformatics/btad089.
3. Buldeo Rai H., Dablanc L. Hunting for treasure: a systematic literature review on urban logistics and e-commerce data. Transport Reviews. 2023. V. 43. № 2. P. 204–233. DOI 10.1080/01441647.2022.2082580.
4. Li Yu., Xie Sh., Wan Zh., Lv H., Song H., Lv Zh. Graph-powered learning methods in the Internet of Things: A survey. Machine Learning with Applications. 2023. V. 11. P. 100441. DOI 10.1016/j.mlwa.2022.100441.
5. Blokhin N.V., Makrushin S.V. Construction of a vector representation of economic activities using graph neural networks. Information-measuring and Control Systems. 2023. V. 21. № 5. P. 7−15. DOI 10.18127/j20700814-202305-02 (in Russian)
6. Li L., Xiao Ju., Shi H., Wang W., Shao J., Liu An., Yang Yi., Chen L. Label Semantic Knowledge Distillation for Unbiased Scene Graph Generation. IEEE Transactions on Circuits and Systems for Video Technology. 2024. V. 34. №. 1. P. 195–206. DOI 10.1109/ tcsvt.2023.3282349.
7. Jin T., Guo F., Meng Q., Zhu S., Xi X., Wang W., Mu Z., Song W. Fast Contextual Scene Graph Generation with Unbiased Context Augmentation. IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023. P. 6302–6311. DOI 10.1109/CVPR52729. 2023.00610.
8. Li L., Ji W., Wu Y., Li M., Qin Y., Wei L., Zimmermann R. Panoptic Scene Graph Generation with Semantics-Prototype Learning. Proceedings of the AAAI Conference on Artificial Intelligence. 2024. V. 38. № 4. P. 3145–3153. DOI 10.1609/aaai.v38i4.28098.
9. Zhang Y., Pan Y., Yao T., Huang R., Mei T., Chen C.-W. Boosting scene graph generation with visual relation saliency. ACM Transactions on Multimedia Computing, Communications, and Applications. 2022. V 19. № 1. P. 1–17. DOI 10.1145/3514041.
10. Özsoy E., Holm F., Saleh M., Czempiel T., Pellegrini C., Navab N., Busam B. Location-Free Scene Graph Generation. [Electronic resource] – Access mode: https://arxiv.org/pdf/2303.10944, date of reference 18.05.2024.
11. Zheng C., Lyu X., Gao L., Dai B., Song J. Prototype-Based Embedding Network for Scene Graph Generation. IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023. P. 22783–22792. DOI 10.1109/CVPR52729.2023.02182.
12. Cong Y., Yang M.Y., Rosenhahn B. RelTR: Relation Transformer for Scene Graph Generation. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2023. V. 45. № 9. P. 11169–11183. DOI 10.1109/TPAMI.2023.3268066.
13. Huang H., Sun L., Du B., Lv W. Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generation. Proceedings of the AAAI Conference on Artificial Intelligence. 2023. V. 37. № 4. P. 4302–4311. DOI 10.1609/aaai.v37i4.25549.
14. Duchemin Q. Reliable prediction in the Markov stochastic block model. ESAIM. Probability and Statistics. 2023. V. 27. P. 80–135. DOI 10.1051/ps/2022019.
15. Duchemin Q., De Castro Y. Markov random geometric graph, MRGG: A growth model for temporal dynamic networks. Electronic Journal of Statistics. 2022. V. 16. № 1. DOI 10.1214/21-ejs1969.
16. Duchemin Q., De Castro Y., Lacour C. Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains. Bernoulli. 2023. V. 29. № 2. DOI 10.3150/22-bej1485.
17. Zhu Y., Du Y., Wang Y., Xu Y., Zhang J., Liu Q., Wu S. A survey on deep graph generation: Methods and applications. [Electronic resource] – Access mode: https://arxiv.org/pdf/2203.06714, date of reference 18.05.2024.
18. Zang C., Wang F. MoFlow: An Invertible Flow Model for Generating Molecular Graphs. [Electronic resource] – Access mode: https://arxiv.org/pdf/2006.10137, date of reference 18.05.2024.
19. Guo X., Du Y., Zhao L. Deep Generative Models for Spatial Networks. Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 2021. P. 505–515. DOI 10.1145/3447548.3467394.
20. Du Yu., Guo X., Cao H., Ye Ya, Zhao L. Disentangled Spatiotemporal Graph Generative Models. Proceedings of the AAAI Conference on Artificial Intelligence. 2022. V. 36. № 6. P. 6541–6549. DOI 10.1609/aaai.v36i6.20607.
21. Du Y., Guo X., Shehu A., Zhao L. Interpretable Molecular Graph Generation via Monotonic Constraints. [Electronic resource] – Access mode: https://arxiv.org/pdf/2203.00412, date of reference 18.05.2024.
22. Du Yu., Guo X., Wang Y., Shehu A., Zhao L. Small molecule generation via disentangled representation learning. Bioinformatics. 2022. V. 38. № 12. P. 3200–3208. DOI 10.1093/bioinformatics/btac296.
23. Wang S., Guo X., Zhao L. Deep Generative Model for Periodic Graphs. [Electronic resource] – Access mode: https://arxiv.org/pdf/ 2201.11932, date of reference 18.05.2024.
24. Luo Y., Yan K., Ji S. GraphDF: A Discrete Flow Model for Molecular Graph Generation. [Electronic resource] – Access mode: https://ar-xiv.org/pdf/2102.01189, date of reference 18.05.2024.
25. Du Y., Liu X., Shah N., Liu S., Zhang J., Zhou B. ChemSpacE: Interpretable and Interactive Chemical Space Exploration. Biological and Medicinal Chemistry. 2022. V. 3. DOI 10.26434/chemrxiv-2022-x49mh-v3.
26. Liu M., Yan K., Oztekin B., Ji S. GraphEBM: Molecular Graph Generation with Energy-Based Models. [Electronic resource] – Access mode: https://arxiv.org/pdf/2102.00546, date of reference 18.05.2024.
27. Lee S., Jo J., Hwang J.S. Exploring Chemical Space with Score-based Out-of-distribution Generation. [Electronic resource] – Access mode: https://arxiv.org/pdf/2206.07632, date of reference 18.05.2024.
28. Vignac C., Krawczuk I., Siraudin A., Wang B., Cevher V., Frossard P. DiGress: Discrete Denoising Diffusion for Graph Generation. [Electronic resource] – Access mode: https://arxiv.org/pdf/2209.14734, date of reference 18.05.2024.
29. Jo J., Lee S., Hwang S.J. Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations. [Electronic resource] – Access mode: https://arxiv.org/pdf/2202.02514, date of reference 18.05.2024.
30. Ahn S., Chen B., Wang T., Song L. Spanning Tree-based Graph Generation for Molecules. [Electronic resource] – Access mode: https://openreview.net/forum?id=w60btE_8T2m, date of reference 18.05.2024.
31. Guo X., Du Yu., Tadepalli S., Zhao L., Shehu A. Generating tertiary protein structures via interpretable graph variational autoencoders. Bioinformatics Advances. 2021. V. 1. № 1. DOI 10.1093/bioadv/vbab036.
32. Yao D., Hu H., Du L., Cong G., Han S., Bi J. TrajGAT: A Graph-based Long-term Dependency Modeling Approach for Trajectory Similarity Computation. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022. P. 2275–2285. DOI 10.1145/3534678.353935.
33. Bongini P., Bianchini M., Scarselli F. Molecular generative Graph Neural Networks for Drug Discovery. Neurocomputing. 2021. V. 450. P. 242–252. DOI 10.1016/j.neucom.2021.04.039.
34. Thost V., Chen J. Directed acyclic graph neural networks. [Electronic resource] – Access mode: https://arxiv.org/pdf/2101.07965, date of reference 18.05.2024.
35. Shen W., Wu S., Yang Y., Quan X. Directed acyclic graph network for conversational emotion recognition. [Electronic resource] – Access mode: https://arxiv.org/pdf/2105.12907, date of reference 18.05.2024.
36. Gandhi S., Iyer A.P. P3: Distributed deep graph learning at scale. 15th USENIX Symposium on Operating Systems Design and Implementation. 2021. P. 551–568.
37. Huang Q., Yamada M., Tian Y. Singh D., Yin D., Chang Y. GraphLIME: Local interpretable model explanations for graph neural networks. [Electronic resource] – Access mode: https://arxiv.org/pdf/2101.07965, date of reference 18.05.2024.
38. Ling C., Yang C., Zhao L. Deep Generation of Heterogeneous Networks. IEEE International Conference on Data Mining. 2021. P. 379–388. DOI 10.1109/ICDM51629.2021.00049.
39. Zhao J., Wang X., Shi Ch., Hu B., Song G., Ye Y. Heterogeneous Graph Structure Learning for Graph Neural Networks. Proceedings of the AAAI Conference on Artificial Intelligence. 2021. V. 35. № 5. P. 4697-4705. DOI 10.1609/aaai.v35i5.16600.
40. Ahmedt-Aristizabal D., Armin M.A., Petersson L., Denman S., Fookes C. Graph-based deep learning for medical diagnosis and analysis: Past, present and future. Sensors. 2021. V. 21. № 14. DOI 10.3390/s21144758.