В.С. Гаврилов1, Р.А. Кочкаров2, А.А. Кочкаров3, Д.В. Сердечный4, С.А. Корчагин5

1–5 Финансовый университет при Правительстве РФ (Москва, Россия)

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

Постановка проблемы. Генерация реалистичных и разнообразных графовых структур является важной задачей в области машинного обучения и искусственного интеллекта. Многие реальные сетевые структуры, такие как социальные сети, биологические сети и транспортные сети, обладают сложными фрактальными и иерархическими характеристиками, которые необходимо учитывать при моделировании и анализе таких систем. Традиционные методы генерации графов часто не могут воспроизвести эти важные особенности, что ограничивает их применение.

Цель. Разработать алгоритм генерации графовых структур на основе анализа существующих методов, который позволит создавать реалистичные графы с фрактальными и иерархическими свойствами.

Результаты. Разработан алгоритм генерации графовых структур, основанный на принципах фрактальной геометрии и иерархической композиции. Показано, что предложенный алгоритм позволяет создавать графы с реалистичными топологическими свойствами, такими как распределение степеней узлов, высокая кластеризация. Продемонстрировано, что сгенерированные графы могут обладать самоподобными и фрактальными характеристиками.

Практическая значимость. Разработанный подход к генерации графовых структур имеет широкий спектр практических применений. Полученные графы могут быть использованы для тестирования и оценки алгоритмов анализа сетей, новостных потоков, моделирования динамических процессов на сетях, а также в качестве синтетических данных для обучения моделей машинного обучения. Кроме того, предлагаемый метод может быть применен для генерации реалистичных модельных сетей в различных областях, таких как экономика, финансы, социология, транспорт и информационные технологии.

Гаврилов В.С., Кочкаров Р.А., Кочкаров А.А., Сердечный Д.В., Корчагин С.А. Генерация глубоких графов с элементами фрактальной структуры и их применение на примере моделирования новостных сетей // Нейрокомпьютеры: разработка, применение. 2024. T. 26. № 6. С. 86-98. DOI: https://doi.org/10.18127/j19998554-202406-11

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 promiscuous 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. Блохин Н.В., Макрушин С.В. Построение векторного представления отраслей экономики с помощью графовых нейронных сетей // Информационно-измерительные и управляющие системы. 2023. Т. 21. № 5. С. 7−15. DOI 10.18127/j20700814-202305-02.
6. Li L., Xiao Ju., Shi H., Wang W., Shao J., Liu A., 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2303.10944, дата обращения 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2203.06714, дата обращения 18.05.2024.
18. Zang C., Wang F. MoFlow: An Invertible Flow Model for Generating Molecular Graphs. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2006.10137, дата обращения 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2203.00412, дата обращения 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/ pdf/2201.11932, дата обращения 18.05.2024.
24. Luo Y., Yan K., Ji S. GraphDF: A Discrete Flow Model for Molecular Graph Generation. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2102.01189, дата обращения 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2102.00546, дата обращения 18.05.2024.
27. Lee S., Jo J., Hwang J.S. Exploring Chemical Space with Score-based Out-of-distribution Generation. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2206.07632, дата обращения 18.05.2024.
28. Vignac C., Krawczuk I., Siraudin A., Wang B., Cevher V., Frossard P. DiGress: Discrete Denoising Diffusion for Graph Generation. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2209.14734, дата обращения 18.05.2024.
29. Jo J., Lee S., Hwang S.J. Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2202.02514, дата обращения 18.05.2024.
30. Ahn S., Chen B., Wang T., Song L. Spanning Tree-based Graph Generation for Molecules. [Электронный ресурс] – Режим доступа: https://openreview.net/forum?id=w60btE_8T2m, дата обращения 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2101. 07965, дата обращения 18.05.2024.
35. Shen W., Wu S., Yang Y., Quan X. Directed acyclic graph network for conversational emotion recognition. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2105.12907, дата обращения 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. [Электронный ресурс] – Режим доступа: https://arxiv.org/pdf/2001.06216, дата обращения 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.