PolyGraph Discrepancy: a classifier-based metric for graph generation

2025/10/07 by Markus Krimmel, Philip Hartout, Krimmel, Markus +5
Computer Science · #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.2510.06122

openalex publication_date 2025/10/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• WyckoffDiff -- A Generative Diffusion Model for Crystal Symmetry
• Fast Graph Generation via Autoregressive Noisy Filtration Modeling
• Flatten Graphs as Sequences: Transformers are Scalable Graph Generators
• Graph Diffusion Transformers for Multi-Conditional Molecular Generation
• Efficient and Scalable Graph Generation through Iterative Local Expansion
• Feature Likelihood Divergence: Evaluating the Generalization of Generative Models Using Samples
• Curvature Filtrations for Graph Generative Model Evaluation
• Evaluating Graph Generative Models with Contrastively Learned Features
• SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators
• On Evaluation Metrics for Graph Generative Models
• Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions
• Learning Graph Models for Retrosynthesis Prediction
• Efficient Graph Generation with Graph Recurrent Attention Networks
• Fréchet Audio Distance: A Metric for Evaluating Music Enhancement Algorithms
• Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models
• Fréchet ChemNet Distance: A metric for generative models for molecules in drug discovery
• GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
• Quantitatively Evaluating GANs With Divergences Proposed for Training
• A Note on the Inception Score
• Demystifying MMD GANs
• Revisiting Classifier Two-Sample Tests
• Generative Moment Matching Networks
• A Kernel Method for the Two-Sample Problem

Related

• Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions
• From Graph Generation to Graph Classification
• Beyond MMD: Evaluating Graph Generative Models with Geometric Deep Learning
• Evaluating Graph Generative Models with Contrastively Learned Features
• Towards quantitative methods to assess network generative models