<div>
	Исследование возможности применения эволюционных алгоритмов для условной генерации атрибутированных графов</div>

Деева Ирина Юрьевна , Андреева Полина Олеговна, Шиков Егор Николаевич, Калюжная Анна Владимировна

doi:10.17586/2226-1494-2025-25-3-438-445

2025 , ТОМ 25, НОМЕР 3 ( май-июнь )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Меню

Публикации

Главный редактор

НИКИФОРОВ
Владимир Олегович
д.т.н., профессор

Партнеры

doi: 10.17586/2226-1494-2025-25-3-438-445

УДК 004.852

Исследование возможности применения эволюционных алгоритмов для условной генерации атрибутированных графов

Деева И.Ю., Андреева П.О., Шиков Е.Н., Калюжная А.В.

Читать статью полностью

Язык статьи - русский

Ссылка для цитирования:

Деева И.Ю., Андреева П.О., Шиков Е.Н., Калюжная А.В. Исследование возможности применения эволюционных алгоритмов для условной генерации атрибутированных графов // Научно- технический вестник информационных технологий, механики и оптики. 2025. Т. 25, № 3. С. 438–445. doi: 10.17586/2226-1494-2025-25-3-438-445

Аннотация

Введение. Область синтетической генерации атрибутированных графов активно развивается благодаря прогрессу в генеративном моделировании. Однако ключевой проблемой современных методов остается ограниченное разнообразие синтезируемых графов, которое зависит от характеристик реальных данных, используемых для обучения генеративных моделей. Также ограничение связано с топологическими свойствами графов и статистическими характеристиками атрибутов, критически влияющими на эффективность графовых моделей машинного обучения. В данной работе проверена гипотеза о том, что комбинация эволюционных алгоритмов и байесовских сетей может обеспечить гибкий контроль над генерацией как топологии, так и атрибутов графа. Метод. Предложенный подход включает два ключевых компонента: эволюционные алгоритмы для управления топологическими характеристиками графа (например, средняя степень вершины, коэффициент кластеризации) и байесовские сети для генерации атрибутов с заданными статистическими параметрами, такими как ассортативность или средняя корреляция между атрибутами. Метод позволяет явно задавать ограничения на свойства графа, обеспечивая вариативность, не зависящую от исходных данных. Основные результаты. Эксперименты подтвердили, что подход способен генерировать атрибутированные графы с широким спектром топологических характеристик и заданными статистическими параметрами атрибутов с достаточно низкой ошибкой генерации. Обсуждение. Результаты демонстрируют перспективность использования эволюционных и байесовских методов для условной генерации графов. Основное преимущество подхода — возможность декомпозиции задачи на независимое управление топологией и атрибутами, что открывает новые возможности для тестирования алгоритмов машинного обучения в контролируемых условиях. Ограничением является вычислительная сложность эволюционной оптимизации, что требует дальнейшей работы по оптимизации алгоритма. В перспективе метод может быть расширен для генерации динамических графов и интеграции с глубокими генеративными моделями.

Ключевые слова: атрибутированные графы, генерация синтетических графов, эволюционная оптимизация, байесовские сети, топологические характеристики графов, статистические характеристики атрибутов

Благодарности. Исследование выполнено при финансовой поддержке Российского научного фонда, договор № 24-71-10093, https://rscf.ru/en/project/24-71-10093/.

Список литературы

Palowitch J., Tsitsulin A., Mayer B., Perozzi B. Graphworld: Fake graphs bring real insights for GNNs // Proc. of the 28^th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022. P. 3691–3701. https://doi.org/10.1145/3534678.3539203
Hu W., Fey M., Zitnik M., Dong Y., Ren H., Liu B., Catasta M., Leskovec J. Open graph benchmark: Datasets for machine learning on graphs // Advances in Neural Information Processing Systems. 2020. V. 33. P. 22118–22133.
Shah N. Scale-free, attributed and class-assortative graph generation to facilitate introspection of graph neural networks // Proc. of the MLG '20: ACM Symposium on Neural Gaze Detection. 2020.
Maekawa S., Sasaki Y., Fletcher G., Onizuka M. Gencat: Generating attributed graphs with controlled relationships between classes, attributes, and topology // Information Systems. 2023. V. 115. P. 102195. https://doi.org/10.1016/j.is.2023.102195
Kim M., Leskovec J. Multiplicative attribute graph model of real-world networks // Internet mathematics. 2012. V. 8. N 1-2. P. 113–160. https://doi.org/10.1080/15427951.2012.625257
Tsitsulin A., Rozemberczki B., Palowitch J., Perozzi B. Synthetic graph generation to benchmark graph learning // arXiv. 2022. arXiv:2204.01376. https://doi.org/10.48550/arXiv.2204.01376
Largeron C., Mougel P.-N., Rabbany R., Zaïane O.R. Generating attributed networks with communities // PLoS ONE. 2015. V. 10. N 4. P. e0122777. https://doi.org/10.1371/journal.pone.0122777
BarabásiA.-L. The Barabási-Albert Model // Network Science. 2016. P. 164–202.
Tseng A.M., Diamant N., Biancalani T., Scalia G. GraphGUIDE: interpretable and controllable conditional graph generation with discrete bernoulli diffusion // arXiv. 2023. arXiv:2302.03790. https://doi.org/10.48550/arXiv.2302.03790
Li M., Kreacic E., Potluru V.K., Li P. GraphMaker: Can diffusion models generate large attributed graphs? // arXiv. 2023. arXiv:2310.13833. https://doi.org/10.48550/arXiv.2310.13833
Faez F., Dijujin N.H., Baghshah M.S., Rabiee H.R. SCGG: A deep structure-conditioned graph generative model // PLoS ONE. 2022. V. 17. N 11. P. e0277887. https://doi.org/10.1371/journal.pone.0277887
Kipf T.N., Welling M. Variational graph auto-encoders // arXiv. 2016. arXiv:1611.07308. https://doi.org/10.48550/arXiv.1611.07308
Simonovsky M., Komodakis N. Graphvae: Towards generation of small graphs using variational autoencoders // Lecture Notes in Computer Science. 2018. V. 11139. P. 412–422. h ttps://doi.org/10.1007/978-3-030-01418-6_41
Bojchevski A., Shchur O., Zügner D., Günnemann S. NetGAN: Generating graphs via random walks // arXiv. 2018. arXiv:1803.00816. https://doi.org/10.48550/arXiv.1803.00816
Gasteiger J., Bojchevski A., Günnemann S. Predict then propagate: Graph neural networks meet personalized pagerank // arXiv. 2018. arXiv:1810.05997. 2018. https://doi.org/10.48550/arXiv.1810.05997
Kim D., Oh A. How to find your friendly neighborhood: Graph attention design with self-supervision // arXiv. 2022. arXiv:2204.04879. https://doi.org/10.48550/arXiv.2204.04879
Attar N., Aliakbary S., Nezhad Z.H. Automatic generation of adaptive network models based on similarity to the desired complex network // Physica A: Statistical Mechanics and its Applications. 2020. V. 545. P. 123353. https://doi.org/10.1016/j.physa.2019.123353
Verstraaten M., Varbanescu A.L., de Laat C. Synthetic graph generation for systematic exploration of graph structural properties // Lecture Notes in Computer Science. 2017. V. 10104. P. 557–570. https://doi.org/10.1007/978-3-319-58943-5_45
Barry A., Griffith J., O’Riordan C. An evolutionary and graph-rewriting based approach to graph generation // Proc. of the 7^th International Joint Conference on Computational Intelligence (IJCCI 2015). 2015. V. 1. P. 237–243. https://doi.org/10.5220/0005597102370243
Deb K., Pratap A., Agarwal S., Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II // IEEE Transactions on Evolutionary Computation. 2002. V. 6. N 2. P. 182–197. https://doi.org/10.1109/4235.996017
Erdos P., Renyi A. On the evolution of random graphs // The Structure and Dynamics of Networks. 2011. P. 38–82.
Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009. 1231 p.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License