# Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 51 references that are in the map.
- First posted on arXiv 2 Jun 2021.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Permutation Invariant Graph Generation via Score-Based Generative Modeling](https://mlsanity.com/paper/2003.00638/) (2020)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Wasserstein Weisfeiler-Lehman Graph Kernels](https://mlsanity.com/paper/1906.01277/) (2019)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [Topological Graph Neural Networks](https://mlsanity.com/paper/2102.07835/) (2021)
- [Graph Filtration Learning](https://mlsanity.com/paper/1905.10996/) (2019)
- [GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation](https://mlsanity.com/paper/2001.08184/) (2020)
- [Scalable Deep Generative Modeling for Sparse Graphs](https://mlsanity.com/paper/2006.15502/) (2020)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [Learning metrics for persistence-based summaries and applications for graph classification](https://mlsanity.com/paper/1904.12189/) (2019)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Geodesic Exponential Kernels: When Curvature and Linearity Conflict](https://mlsanity.com/paper/1411.0296/) (2014)
- [The Shape of Data: Intrinsic Distance for Data Distributions](https://mlsanity.com/paper/1905.11141/) (2019)
- [A Test of Relative Similarity For Model Selection in Generative Models](https://mlsanity.com/paper/1511.04581/) (2015)
- [Multiscale Strategies for Computing Optimal Transport](https://mlsanity.com/paper/1708.02469/) (2017)
- [Persistence paths and signature features in topological data analysis](https://mlsanity.com/paper/1806.00381/) (2018)
- [Topological Machine Learning with Persistence Indicator Functions](https://mlsanity.com/paper/1907.13496/) (2019)

## Built on by (most cited first, 30 of 39)

- [Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations](https://mlsanity.com/paper/2202.02514/) (2022)
- [Generative Diffusion Models on Graphs: Methods and Applications](https://mlsanity.com/paper/2302.02591/) (2023)
- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [A Survey on Deep Graph Generation: Methods and Applications](https://mlsanity.com/paper/2203.06714/) (2022)
- [On Evaluation Metrics for Graph Generative Models](https://mlsanity.com/paper/2201.09871/) (2022)
- [Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generation](https://mlsanity.com/paper/2301.00427/) (2023)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Metric Space Magnitude for Evaluating the Diversity of Latent Representations](https://mlsanity.com/paper/2311.16054/) (2023)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoders](https://mlsanity.com/paper/2210.16844/) (2022)
- [A Framework for Large Scale Synthetic Graph Dataset Generation](https://mlsanity.com/paper/2210.01944/) (2022)
- [HiGen: Hierarchical Graph Generative Networks](https://mlsanity.com/paper/2305.19337/) (2023)
- [Evaluating Graph Generative Models with Contrastively Learned Features](https://mlsanity.com/paper/2206.06234/) (2022)
- [Prior-Informed Flow Matching for Graph Reconstruction](https://mlsanity.com/paper/2601.22107/) (2026)
- [GEMS: Scene Expansion using Generative Models of Graphs](https://mlsanity.com/paper/2207.03729/) (2022)
- [PolyGraph Discrepancy: a classifier-based metric for graph generation](https://mlsanity.com/paper/2510.06122/) (2025)
- [GRAN is superior to GraphRNN: node orderings, kernel- and graph embeddings-based metrics for graph generators](https://mlsanity.com/paper/2307.06709/) (2023)
- [HC-GST: Heterophily-aware Distribution Consistency based Graph Self-training](https://mlsanity.com/paper/2407.17787/) (2024)
- [Point Cloud Synthesis Using Inner Product Transforms](https://mlsanity.com/paper/2410.18987/) (2024)
- [Discovering Graph Generation Algorithms](https://mlsanity.com/paper/2304.12895/) (2023)
- [SANGEA: Scalable and Attributed Network Generation](https://mlsanity.com/paper/2309.15648/) (2023)
- [Quality Measures for Dynamic Graph Generative Models](https://mlsanity.com/paper/2503.01720/) (2025)
- [Exploring Variational Graph Autoencoders for Distribution Grid Data Generation](https://mlsanity.com/paper/2509.02469/) (2025)
- [Beyond MMD: Evaluating Graph Generative Models with Geometric Deep Learning](https://mlsanity.com/paper/2512.14241/) (2025)
- [GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphs](https://mlsanity.com/paper/2202.03884/) (2022)
- [GrannGAN: Graph annotation generative adversarial networks](https://mlsanity.com/paper/2212.00449/) (2022)
- [On Hierarchical Multi-Resolution Graph Generative Models](https://mlsanity.com/paper/2303.03293/) (2023)
- [Computing Expected Motif Counts for Exchangeable Graph Generative Models](https://mlsanity.com/paper/2305.01089/) (2023)
- [Combinatorial Complex Score-based Diffusion Modelling through Stochastic Differential Equations](https://mlsanity.com/paper/2406.04916/) (2024)

## Abstract (arXiv)

Graph generative models are a highly active branch of machine learning. Given the steady development of new models of ever-increasing complexity, it is necessary to provide a principled way to evaluate and compare them. In this paper, we enumerate the desirable criteria for such a comparison metric and provide an overview of the status quo of graph generative model comparison in use today, which predominantly relies on the maximum mean discrepancy (MMD). We perform a systematic evaluation of MMD in the context of graph generative model comparison, highlighting some of the challenges and pitfalls researchers inadvertently may encounter. After conducting a thorough analysis of the behaviour of MMD on synthetically-generated perturbed graphs as well as on recently-proposed graph generative models, we are able to provide a suitable procedure to mitigate these challenges and pitfalls. We aggregate our findings into a list of practical recommendations for researchers to use when evaluating graph generative models.