mlsanityData to 7 Oct 2026

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

arXiv 2106.01098 ↗First posted 2 Jun 2021cs.LG cs.SI stat.MLcited by 38

Not on the map. Why?

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.

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

Builds on

22 of 51 references.

References · 22

  1. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,277
  2. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 406
  3. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 263
  4. 2019Efficient Graph Generation with Graph Recurrent Attention Networkscited by 231
  5. 2017Near-linear time approximation algorithms for optimal transport via Sinkhorn iterationcited by 219
  6. 2016Stochastic Optimization for Large-scale Optimal Transportcited by 188
  7. 2019Wasserstein Weisfeiler-Lehman Graph Kernelscited by 104
  8. 2016Generative Models and Model Criticism via Optimized Maximum Mean Discrepancycited by 99
  9. 2021Topological Graph Neural Networkscited by 86
  10. 2019Graph Filtration Learningcited by 68
  11. 2020GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generationcited by 65
  12. 2020Scalable Deep Generative Modeling for Sparse Graphscited by 63
10 more
  1. 2020Graph Kernels: State-of-the-Art and Future Challengescited by 63
  2. 2019Learning metrics for persistence-based summaries and applications for graph classificationcited by 57
  3. 2018NetLSD: Hearing the Shape of a Graphcited by 51
  4. 2016On Valid Optimal Assignment Kernels and Applications to Graph Classificationcited by 49
  5. 2014Geodesic Exponential Kernels: When Curvature and Linearity Conflictcited by 47
  6. 2019The Shape of Data: Intrinsic Distance for Data Distributionscited by 38
  7. 2015A Test of Relative Similarity For Model Selection in Generative Modelscited by 25
  8. 2017Multiscale Strategies for Computing Optimal Transportcited by 18
  9. 2018Persistence paths and signature features in topological data analysiscited by 17
  10. 2019Topological Machine Learning with Persistence Indicator Functionscited by 11

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 10; 2023: 11; 2024: 5; 2025: 8; 2026: 4.

38 papers.

Sort:

By area:

  1. 2022Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equationscited by 273
  2. 2023Generative Diffusion Models on Graphs: Methods and Applicationscited by 79
  3. 2023Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modelingcited by 75
  4. 2022A Survey on Deep Graph Generation: Methods and Applicationscited by 69
  5. 2023Conditional Diffusion Based on Discrete Graph Structures for Molecular Graph Generationcited by 46
  6. 2022On Evaluation Metrics for Graph Generative Modelscited by 44
  7. 2022GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generationcited by 43
  8. 2023Curvature Filtrations for Graph Generative Model Evaluationcited by 18
  9. 2023Metric Space Magnitude for Evaluating the Diversity of Latent Representationscited by 16
  10. 2025Flatten Graphs as Sequences: Transformers are Scalable Graph Generatorscited by 12
  11. 2022Micro and Macro Level Graph Modeling for Graph Variational Auto-Encoderscited by 8
  12. 2022Evaluating Graph Generative Models with Contrastively Learned Featurescited by 5
26 more
  1. 2022A Framework for Large Scale Synthetic Graph Dataset Generationcited by 5
  2. 2023HiGen: Hierarchical Graph Generative Networkscited by 5
  3. 2022GEMS: Scene Expansion using Generative Models of Graphscited by 3
  4. 2026Prior-Informed Flow Matching for Graph Reconstructioncited by 3
  5. 2023GRAN is superior to GraphRNN: node orderings, kernel- and graph embeddings-based metrics for graph generatorscited by 2
  6. 2024HC-GST: Heterophily-aware Distribution Consistency based Graph Self-trainingcited by 2
  7. 2024Point Cloud Synthesis Using Inner Product Transformscited by 2
  8. 2025PolyGraph Discrepancy: a classifier-based metric for graph generationcited by 2
  9. 2023Discovering Graph Generation Algorithmscited by 1
  10. 2023SANGEA: Scalable and Attributed Network Generationcited by 1
  11. 2025Quality Measures for Dynamic Graph Generative Modelscited by 1
  12. 2025Exploring Variational Graph Autoencoders for Distribution Grid Data Generationcited by 1
  13. 2025Beyond MMD: Evaluating Graph Generative Models with Geometric Deep Learningcited by 1
  14. 2022GraphDCA -- a Framework for Node Distribution Comparison in Real and Synthetic Graphscited by 0
  15. 2022GrannGAN: Graph annotation generative adversarial networkscited by 0
  16. 2023On Hierarchical Multi-Resolution Graph Generative Modelscited by 0
  17. 2023Computing Expected Motif Counts for Exchangeable Graph Generative Modelscited by 0
  18. 2024Combinatorial Complex Score-based Diffusion Modelling through Stochastic Differential Equationscited by 0
  19. 2024Heterogeneous Graph Generation: A Hierarchical Approach using Node Feature Poolingcited by 0
  20. 2024Vertical Validation: Evaluating Implicit Generative Models for Graphs on Thin Support Regionscited by 0
  21. 2025Graph Generative Models Evaluation with Masked Autoencodercited by 0
  22. 2025NGTM: Substructure-based Neural Graph Topic Model for Interpretable Graph Generationcited by 0
  23. 2025Explainable Graph Representation Learning via Graph Pattern Analysiscited by 0
  24. 2026Diversity Curves for Graph Representation Learningcited by 0
  25. 2026GraphK: Variable-Size Graph Generation with Efficient Edge Constructioncited by 0
  26. 2026ProtoGuide: Prototype-Driven Guidance for Class-Conditional Graph Generationcited by 0