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

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.

1. Palowitch J., Tsitsulin A., Mayer B., Perozzi B. Graphworld: Fake graphs bring real insights for GNNs. Proc. of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022, pp. 3691–3701. https://doi.org/10.1145/3534678.3539203

2. 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.

3. 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.

4. 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

5. Kim M., Leskovec J. Multiplicative attribute graph model of realworld networks. Internet mathematics, 2012, vol. 8, no. 1-2, pp. 113–160. https://doi.org/10.1080/15427951.2012.625257

6. 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

7. Largeron C., Mougel P.-N., Rabbany R., Zaïane O.R. Generating attributed networks with communities. PLoS ONE, 2015, vol. 10, no. 4, pp. e0122777. https://doi.org/10.1371/journal.pone.0122777

8. Barabási A.-L. The Barabási-Albert Model. Network Science, 2016, pp. 164–202.

9. 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

10. 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

11. 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

12. Kipf T.N., Welling M. Variational graph auto-encoders. arXiv, 2016, arXiv:1611.07308. https://doi.org/10.48550/arXiv.1611.07308

13. 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

14. 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

15. 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

16. 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

17. 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

18. 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

19. Barry A., Griffith J., O’Riordan C. An evolutionary and graphrewriting based approach to graph generation. Proc. of the 7th International Joint Conference on Computational Intelligence (IJCCI 2015) , 2015, vol. 1, pp. 237–243. https://doi.org/10.5220/0005597102370243

20. 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

21. Erdos P., Renyi A. On the evolution of random graphs. The Structure and Dynamics of Networks, 2011, pp. 38–82.

22. Koller D., Friedman N. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009, 1231 p.