# On Evaluation Metrics for Graph Generative Models

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

## Key facts

- Cited by 46 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 55 references that are in the map.
- First posted on arXiv 24 Jan 2022.

## Builds on (most cited first, 30 of 34)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Improved Techniques for Training GANs](https://mlsanity.com/paper/1606.03498/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Demystifying MMD GANs](https://mlsanity.com/paper/1801.01401/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Improved Precision and Recall Metric for Assessing Generative Models](https://mlsanity.com/paper/1904.06991/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Exact solutions to the nonlinear dynamics of learning in deep linear neural networks](https://mlsanity.com/paper/1312.6120/) (2013)
- [Reliable Fidelity and Diversity Metrics for Generative Models](https://mlsanity.com/paper/2002.09797/) (2020)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [A note on the evaluation of generative models](https://mlsanity.com/paper/1511.01844/) (2015)
- [Are GANs Created Equal? A Large-Scale Study](https://mlsanity.com/paper/1711.10337/) (2017)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium](https://mlsanity.com/paper/1706.08500/) (2017)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [MolecularRNN: Generating realistic molecular graphs with optimized properties](https://mlsanity.com/paper/1905.13372/) (2019)
- [An empirical study on evaluation metrics of generative adversarial networks](https://mlsanity.com/paper/1806.07755/) (2018)
- [NeVAE: A Deep Generative Model for Molecular Graphs](https://mlsanity.com/paper/1802.05283/) (2018)
- [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)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)
- [Deep Video Generation, Prediction and Completion of Human Action Sequences](https://mlsanity.com/paper/1711.08682/) (2017)
- [Structured agents for physical construction](https://mlsanity.com/paper/1904.03177/) (2019)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation](https://mlsanity.com/paper/2106.06189/) (2021)

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

- [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)
- [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)
- [Sparse Training of Discrete Diffusion Models for Graph Generation](https://mlsanity.com/paper/2311.02142/) (2023)
- [NVDiff: Graph Generation through the Diffusion of Node Vectors](https://mlsanity.com/paper/2211.10794/) (2022)
- [Metric Space Magnitude for Evaluating the Diversity of Latent Representations](https://mlsanity.com/paper/2311.16054/) (2023)
- [Improving Graph Generation by Restricting Graph Bandwidth](https://mlsanity.com/paper/2301.10857/) (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)
- [Zero-One Laws of Graph Neural Networks](https://mlsanity.com/paper/2301.13060/) (2023)
- [Controllable Graph Generation with Diffusion Models via Inference-Time Tree Search Guidance](https://mlsanity.com/paper/2510.10402/) (2025)
- [HiGen: Hierarchical Graph Generative Networks](https://mlsanity.com/paper/2305.19337/) (2023)
- [Challenges of Generating Structurally Diverse Graphs](https://mlsanity.com/paper/2409.18859/) (2024)
- [Evaluating Graph Generative Models with Contrastively Learned Features](https://mlsanity.com/paper/2206.06234/) (2022)
- [Descriptive Kernel Convolution Network with Improved Random Walk Kernel](https://mlsanity.com/paper/2402.06087/) (2024)
- [Diffusing Gaussian Mixtures for Generating Categorical Data](https://mlsanity.com/paper/2303.04635/) (2023)
- [Any-Property-Conditional Molecule Generation with Self-Criticism using Spanning Trees](https://mlsanity.com/paper/2407.09357/) (2024)
- [Generating Directed Graphs with Dual Attention and Asymmetric Encoding](https://mlsanity.com/paper/2506.16404/) (2025)
- [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)
- [Large Generative Graph Models](https://mlsanity.com/paper/2406.05109/) (2024)
- [IFH: a Diffusion Framework for Flexible Design of Graph Generative Models](https://mlsanity.com/paper/2408.13194/) (2024)
- [Absolute Evaluation Measures for Machine Learning: A Survey](https://mlsanity.com/paper/2507.03392/) (2025)
- [SBGD: Improving Graph Diffusion Generative Model via Stochastic Block Diffusion](https://mlsanity.com/paper/2508.14352/) (2025)
- [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)
- [PRING: Rethinking Protein-Protein Interaction Prediction from Pairs to Graphs](https://mlsanity.com/paper/2507.05101/) (2025)
- [Generator-based Graph Generation via Heat Diffusion](https://mlsanity.com/paper/2602.03612/) (2026)

## Abstract (arXiv)

In image generation, generative models can be evaluated naturally by visually inspecting model outputs. However, this is not always the case for graph generative models (GGMs), making their evaluation challenging. Currently, the standard process for evaluating GGMs suffers from three critical limitations: i) it does not produce a single score which makes model selection challenging, ii) in many cases it fails to consider underlying edge and node features, and iii) it is prohibitively slow to perform. In this work, we mitigate these issues by searching for scalar, domain-agnostic, and scalable metrics for evaluating and ranking GGMs. To this end, we study existing GGM metrics and neural-network-based metrics emerging from generative models of images that use embeddings extracted from a task-specific network. Motivated by the power of certain Graph Neural Networks (GNNs) to extract meaningful graph representations without any training, we introduce several metrics based on the features extracted by an untrained random GNN. We design experiments to thoroughly test metrics on their ability to measure the diversity and fidelity of generated graphs, as well as their sample and computational efficiency. Depending on the quantity of samples, we recommend one of two random-GNN-based metrics that we show to be more expressive than pre-existing metrics. While we focus on applying these metrics to GGM evaluation, in practice this enables the ability to easily compute the dissimilarity between any two sets of graphs regardless of domain. Our code is released at: https://github.com/uoguelph-mlrg/GGM-metrics.