Проблемы генерации структурно разнообразных графов

Для многих задач, связанных с графами, принципиально важно располагать набором структурно разнообразных графов. Например, такие графы могут использоваться для тестирования графовых алгоритмов или их нейросетевых аппроксимаций. Однако, насколько нам известно, задача генерации структурно разнообразных графов ранее не рассматривалась в литературе. В настоящей работе мы восполняем этот пробел. Сначала мы обсуждаем, как определить разнообразие набора графов, почему эта задача нетривиальна и как выбрать подходящую меру разнообразия. Затем для заданной меры разнообразия мы предлагаем и сравниваем несколько оптимизирующих её алгоритмов: рассматриваются подходы на основе стандартных моделей случайных графов, локальной оптимизации графов, генетических алгоритмов и нейронных генеративных моделей. Мы показываем, что разнообразие сгенерированных графов можно существенно повысить по сравнению с базовыми генераторами случайных графов. Кроме того, анализ сгенерированных графов позволяет лучше понять свойства функций расстояний между графами: в зависимости от того, какая функция расстояния используется для оптимизации, получаемые графы могут обладать весьма различными структурными свойствами, что даёт более глубокое понимание расстояния между графами, лежащего в основе меры разнообразия.

1. Boccaletti S. et al. Complex networks: Structure and dynamics. Physics Reports. Elsevier, 2006, vol. 424, no. 4-5, pp. 175-308.

2. Georgiev D. G. et al. Beyond Erdős-Rényi: Generalization in algorithmic reasoning on graphs. The Second Learning on Graphs Conference, 2023.

3. Veličković P., Blundell C. Neural algorithmic reasoning. Patterns. Elsevier, 2021, vol. 2, no. 7, p. 100273.

4. Veličković P. et al. The CLRS Algorithmic Reasoning Benchmark. Proceedings of the 39th International Conference on Machine Learning, 2022.

5. Rodionov G., Prokhorenkova L. Neural Algorithmic Reasoning Without Intermediate Supervision. Advances in Neural Information Processing Systems, 2023, vol. 36.

6. Rodionov G., Prokhorenkova L. Discrete Neural Algorithmic Reasoning. Proceedings of the 42nd International Conference on Machine Learning, 2025.

7. Palowitch J. et al. GraphWorld: Fake graphs bring real insights for GNNs. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022, pp. 3691-3701.

8. Karrer B., Newman M. E. Stochastic blockmodels and community structure in networks. Physical review E. APS, 2011, vol. 83, no. 1, p. 016107.

9. Erdős P., Rényi A. et al. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 1960, vol. 5, no. 1, pp. 17-60.

10. Tantardini M. et al. Comparing methods for comparing networks. Scientific Reports. Springer, 2019, vol. 9, no. 1, pp. 1-19.

11. Tsitsulin A. et al. NetLSD: hearing the shape of a graph. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018, pp. 2347-2356.

12. Yaveroğlu Ö. N. et al. Revealing the hidden language of complex networks. Scientific Reports. Nature Publishing Group UK London, 2014, vol. 4, p. 4547.

13. Bagrow J. P., Bollt E. M. An information-theoretic, all-scales approach to comparing networks. Applied Network Science. Springer, 2019, vol. 4, no. 1.

14. Friedman D., Dieng A. B. The Vendi Score: A Diversity Evaluation Metric for Machine Learning. Transactions on Machine Learning Research, 2023.

15. Xie Y. et al. How Much Space Has Been Explored? Measuring the Chemical Space Covered by Databases and Machine-Generated Molecules. The Eleventh International Conference on Learning Representations, 2023.

16. Velikonivtsev F., Mironov M., Prokhorenkova L. Challenges of Generating Structurally Diverse Graphs. Advances in Neural Information Processing Systems (NeurIPS), 2024.

17. Mironov M., Prokhorenkova L. Measuring Diversity: Axioms and Challenges. arXiv preprint, 2024. DOI: 10.48550/arXiv.2410.14556. 2024.

18. You J. et al. GraphRNN: Generating realistic graphs with deep auto-regressive models. International conference on machine learning. PMLR, 2018, pp. 5708-5717.

19. Martinkus K. et al. SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators, 2022.

20. Vignac C. et al. DiGress: Discrete Denoising diffusion for graph generation. The Eleventh International Conference on Learning Representations, 2023.

21. Barabási A.-L., Albert R. Emergence of scaling in random networks. Science. American Association for the Advancement of Science, 1999, vol. 286, no. 5439, pp. 509-512.

22. Holme P., Kim B. J. Growing scale-free networks with tunable clustering. Physical review E. APS, 2002, vol. 65, no. 2, p. 026107.

23. Chung F., Lu L. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics. Springer, 2002, vol. 6, no. 2, pp. 125-145.

24. Penrose M. Random geometric graphs. Oxford University Press, 2003.

25. Holland P. W., Laskey K. B., Leinhardt S. Stochastic blockmodels: First steps. Social networks. Elsevier, 1983, vol. 5, no. 2, pp. 109-137.