# Challenges of Generating Structurally Diverse Graphs

arXiv: https://arxiv.org/abs/2409.18859 · HTML: https://mlsanity.com/paper/2409.18859/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 27 Sep 2024.

## Builds on (most cited first, 11 of 11)

- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [The Vendi Score: A Diversity Evaluation Metric for Machine Learning](https://mlsanity.com/paper/2210.02410/) (2022)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Neural Algorithmic Reasoning](https://mlsanity.com/paper/2105.02761/) (2021)
- [GraphWorld: Fake Graphs Bring Real Insights for GNNs](https://mlsanity.com/paper/2203.00112/) (2022)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [On Evaluation Metrics for Graph Generative Models](https://mlsanity.com/paper/2201.09871/) (2022)
- [How Much Space Has Been Explored? Measuring the Chemical Space Covered by Databases and Machine-Generated Molecules](https://mlsanity.com/paper/2112.12542/) (2021)
- [An information-theoretic, all-scales approach to comparing networks](https://mlsanity.com/paper/1804.03665/) (2018)
- [Network comparison and the within-ensemble graph distance](https://mlsanity.com/paper/2008.02415/) (2020)

## Built on by (most cited first, 6 of 6)

- [Measuring Diversity: Axioms and Challenges](https://mlsanity.com/paper/2410.14556/) (2024)
- [DMol: A Highly Efficient and Chemical Motif-Preserving Molecule Generation Platform](https://mlsanity.com/paper/2504.06312/) (2025)
- [Beyond One-Size-Fits-All: Adaptive Subgraph Denoising for Zero-Shot Graph Learning with Large Language Models](https://mlsanity.com/paper/2603.02938/) (2026)
- [emb-diversity: A Tool for Embedding-Based Measurement of Data Diversity](https://mlsanity.com/paper/2607.19848/) (2026)
- [Visualization Tasks for Unlabeled Graphs](https://mlsanity.com/paper/2504.14115/) (2025)
- [Evaluating the Diversity of AI-Generated Content with Diversity Profiles](https://mlsanity.com/paper/2608.17731/) (2026)

## Abstract (arXiv)

For many graph-related problems, it can be essential to have a set of structurally diverse graphs. For instance, such graphs can be used for testing graph algorithms or their neural approximations. However, to the best of our knowledge, the problem of generating structurally diverse graphs has not been explored in the literature. In this paper, we fill this gap. First, we discuss how to define diversity for a set of graphs, why this task is non-trivial, and how one can choose a proper diversity measure. Then, for a given diversity measure, we propose and compare several algorithms optimizing it: we consider approaches based on standard random graph models, local graph optimization, genetic algorithms, and neural generative models. We show that it is possible to significantly improve diversity over basic random graph generators. Additionally, our analysis of generated graphs allows us to better understand the properties of graph distances: depending on which diversity measure is used for optimization, the obtained graphs may possess very different structural properties which gives a better understanding of the graph distance underlying the diversity measure.