# SteinGen: Generating Fidelitous and Diverse Graph Samples

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 27 Mar 2024.

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

- [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)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Machine Learning on Graphs: A Model and Comprehensive Taxonomy](https://mlsanity.com/paper/2005.03675/) (2020)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [Measuring Sample Quality with Stein's Method](https://mlsanity.com/paper/1506.03039/) (2015)
- [A Systematic Survey on Deep Generative Models for Graph Generation](https://mlsanity.com/paper/2007.06686/) (2020)
- [GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation](https://mlsanity.com/paper/2001.08184/) (2020)
- [On the Power of Edge Independent Graph Models](https://mlsanity.com/paper/2111.00048/) (2021)
- [Learning graphical models from the Glauber dynamics](https://mlsanity.com/paper/1410.7659/) (2014)
- [Generative Subgraph Contrast for Self-Supervised Graph Representation Learning](https://mlsanity.com/paper/2207.11996/) (2022)
- [A Review of Latent Space Models for Social Networks](https://mlsanity.com/paper/2012.02307/) (2020)
- [AgraSSt: Approximate Graph Stein Statistics for Interpretable Assessment of Implicit Graph Generators](https://mlsanity.com/paper/2203.03673/) (2022)
- [Convergence of Contrastive Divergence Algorithm in Exponential Family](https://mlsanity.com/paper/1603.05729/) (2016)
- [On RKHS Choices for Assessing Graph Generators via Kernel Stein Statistics](https://mlsanity.com/paper/2210.05746/) (2022)
- [Can GAN Learn Topological Features of a Graph?](https://mlsanity.com/paper/1707.06197/) (2017)

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

- [Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance](https://mlsanity.com/paper/2502.11778/) (2025)

## Abstract (arXiv)

Generating graphs that preserve characteristic structures while promoting sample diversity can be challenging, especially when the number of graph observations is small. Here, we tackle the problem of graph generation from only one observed graph. The classical approach of graph generation from parametric models relies on the estimation of parameters, which can be inconsistent or expensive to compute due to intractable normalisation constants. Generative modelling based on machine learning techniques to generate high-quality graph samples avoids parameter estimation but usually requires abundant training samples. Our proposed generating procedure, SteinGen, which is phrased in the setting of graphs as realisations of exponential random graph models, combines ideas from Stein's method and MCMC by employing Markovian dynamics which are based on a Stein operator for the target model. SteinGen uses the Glauber dynamics associated with an estimated Stein operator to generate a sample, and re-estimates the Stein operator from the sample after every sampling step. We show that on a class of exponential random graph models this novel "estimation and re-estimation" generation strategy yields high distributional similarity (high fidelity) to the original data, combined with high sample diversity.