<div>
	Investigation of the possibility of using evolutionary algorithms for conditional generation of attributed graphs</div>

Irina Yu. Deeva, Polina O. Andreeva, Egor N. Shikov, Anna V. Kaluzhnaya

2025 , VOLUME 25, NUMBER 3 ( may-june )

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

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

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

Investigation of the possibility of using evolutionary algorithms for conditional generation of attributed graphs

I. Y. Deeva, P. O. Andreeva, E. N. Shikov, A. V. Kaluzhnaya

Read the full article

Article in Russian

For citation:

Deeva I.Yu., Andreeva P.O., Shikov E.N., Kalyuzhnaya A.V. Investigation of the possibility of using evolutionary algorithms for conditional generation of attributed graphs. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2025, vol. 25, no. 3, pp. 438–445 (in Russian). doi: 10.17586/2226-1494-2025-25-3-438-445

Abstract

The field of synthetic generation of attributed graphs is actively developing due to advances in generative modeling. However, a key problem of current methods remains the limited diversity of synthesized graphs, due to the dependence on the characteristics of real data used to train generative models. This is a problem because topological properties of graphs and statistical characteristics of attributes critically affect the performance of graph-based machine learning models. In this paper, we test the hypothesis that a combination of evolutionary algorithms and Bayesian networks can provide flexible control over the generation of both graph topology and attributes. The proposed approach includes two key components: evolutionary algorithms to control topological characteristics of the graph (e.g. average vertex degree, clustering coefficient) and Bayesian networks to generate attributes with given statistical parameters such as assortativity or average correlation between attributes. The method allows explicitly setting constraints on graph properties, providing variability independent of the original data. Experiments confirmed that the approach can generate attributed graphs with a wide range of topological characteristics and given statistical parameters of the attributes with sufficiently low generation error. The results demonstrate the promising use of evolutionary and Bayesian methods for conditional graph generation. The main advantage of the approach is the ability to decompose the problem into independent control of topology and attributes, which opens new possibilities for testing machine learning algorithms under controlled conditions. A limitation is the computational complexity of evolutionary optimization, which requires further work to optimize the algorithm. In the future, the method can be extended to generate dynamic graphs and integrate with deep generative models.

Keywords: attributed graphs, synthetic graph generation, evolutionary optimization, Bayesian networks, topological characteristics of graphs, statistical characteristics of attributes

Acknowledgements. This research is financially supported by the Russian Scientific Foundation, Agreement 24-71-10093, https://rscf.ru/ en/project/24-71-10093/.

References

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, pp. 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, vol. 33, pp. 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, vol. 115, pp. 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, vol. 8, no. 1-2, pp. 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, vol. 10, no. N 4, pp. e0122777. https://doi.org/10.1371/journal.pone.0122777
BarabásiA.-L. The Barabási-Albert Model.Network Science, 2016, pp. 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, vol. 17, no. 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, vol. 11139, pp. 412–422. https://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. 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, vol. 545, pp. 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, vol. 10104, pp. 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, vol. 1, pp. 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, vol. 6, no. 2, pp. 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, pp. 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