# PolyGraph Discrepancy: a classifier-based metric for graph generation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 53 references that are in the map.
- First posted on arXiv 7 Oct 2025.

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

- [Demystifying MMD GANs](https://mlsanity.com/paper/1801.01401/) (2018)
- [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)
- [GuacaMol: Benchmarking Models for De Novo Molecular Design](https://mlsanity.com/paper/1811.09621/) (2018)
- [Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models](https://mlsanity.com/paper/1811.12823/) (2018)
- [Revisiting Classifier Two-Sample Tests](https://mlsanity.com/paper/1610.06545/) (2016)
- [Generative Moment Matching Networks](https://mlsanity.com/paper/1502.02761/) (2015)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [A Note on the Inception Score](https://mlsanity.com/paper/1801.01973/) (2018)
- [Fr'echet Audio Distance: A Metric for Evaluating Music Enhancement Algorithms](https://mlsanity.com/paper/1812.08466/) (2018)
- [Fr'echet ChemNet Distance: A metric for generative models for molecules in drug discovery](https://mlsanity.com/paper/1803.09518/) (2018)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators](https://mlsanity.com/paper/2204.01613/) (2022)
- [Learning Graph Models for Retrosynthesis Prediction](https://mlsanity.com/paper/2006.07038/) (2020)
- [On Evaluation Metrics for Graph Generative Models](https://mlsanity.com/paper/2201.09871/) (2022)
- [Graph Diffusion Transformers for Multi-Conditional Molecular Generation](https://mlsanity.com/paper/2401.13858/) (2024)
- [Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions](https://mlsanity.com/paper/2106.01098/) (2021)
- [Efficient and Scalable Graph Generation through Iterative Local Expansion](https://mlsanity.com/paper/2312.11529/) (2023)
- [WyckoffDiff -- A Generative Diffusion Model for Crystal Symmetry](https://mlsanity.com/paper/2502.06485/) (2025)
- [Feature Likelihood Divergence: Evaluating the Generalization of Generative Models Using Samples](https://mlsanity.com/paper/2302.04440/) (2023)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [Evaluating Graph Generative Models with Contrastively Learned Features](https://mlsanity.com/paper/2206.06234/) (2022)
- [Quantitatively Evaluating GANs With Divergences Proposed for Training](https://mlsanity.com/paper/1803.01045/) (2018)
- [Fast Graph Generation via Autoregressive Noisy Filtration Modeling](https://mlsanity.com/paper/2502.02415/) (2025)

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

- [Same Graph, Different Likelihoods: Calibration of Autoregressive Graph Generators via Permutation-Equivalent Encodings](https://mlsanity.com/paper/2604.05613/) (2026)
- [Diversity Curves for Graph Representation Learning](https://mlsanity.com/paper/2605.06466/) (2026)
- [Two-Sample Testing for Random Graphs without Vertex Correspondence](https://mlsanity.com/paper/2610.07503/) (2026)

## Abstract (arXiv)

Existing methods for evaluating graph generative models primarily rely on Maximum Mean Discrepancy (MMD) metrics based on graph descriptors. While these metrics can rank generative models, they do not provide an absolute measure of performance. Their values are also highly sensitive to extrinsic parameters, namely kernel and descriptor parametrization, making them incomparable across different graph descriptors. We introduce PolyGraph Discrepancy (PGD), a new evaluation framework that addresses these limitations. It approximates the Jensen-Shannon distance of graph distributions by fitting binary classifiers to distinguish between real and generated graphs, featurized by these descriptors. The data log-likelihood of these classifiers approximates a variational lower bound on the JS distance between the two distributions. Resulting metrics are constrained to the unit interval [0,1] and are comparable across different graph descriptors. We further derive a theoretically grounded summary metric that combines these individual metrics to provide a maximally tight lower bound on the distance for the given descriptors. Thorough experiments demonstrate that PGD provides a more robust and insightful evaluation compared to MMD metrics. The PolyGraph framework for benchmarking graph generative models is made publicly available at https://github.com/BorgwardtLab/polygraph-benchmark.