PolyGraph Discrepancy: a classifier-based metric for graph generation
Authors: Markus Krimmel
Philip Hartout
Karsten Borgwardt
Dexiong Chen
Venue: ICLR 2026 Poster (2026)
Keywords: graph generative models
model evaluation
maximum mean discrepancy
generative models
Primary area: generative models
TL;DR: We propose a new, robust and insightful classifier-based evaluation metric for evaluating graph generative models.

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 PolyGraphScore (PGS), a new evaluation framework that addresses these limitations. It approximates the Jensen-Shannon (JS) 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 scores are constrained to the unit interval $[0,1]$ and are comparable across different graph descriptors. We further derive a theoretically grounded summary score that combines these individual metrics to provide a maximally tight lower bound on the distance for the given descriptors. Thorough experiments demonstrate that PGS provides a more robust and insightful evaluation compared to MMD metrics. A reference implementation of PGD is available at https://github.com/BorgwardtLab/polygraph-benchmark

Published as a conference paper at ICLR 2026
POLYGRAPH DISCREPANCY: A CLASSIFIER-BASBB METRIC FOR GRAPH GENERATION
Markus Krimmel'
Philip Hartout"
Karsten Borgwardt
Dexiong Chen
Max Planck Institute of Biochemistry, Martinsried, Germany (krimmel, hartout, borgout,b dchen paiionem.icccmmmm mpg.
"qqual contribution
ABSTRACT
Existing methods for evaluating graph generative models primarily rely on Maxi- mum Mean Discrepancy (MMD) metries based on graph descriptors. While these metrics can rank generative models, they do not provide an absolute measure performance. Their values are also highly sensitive 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-Shanne Shannon (JS) distance of graph distributions by fitting binary classifiers distinguish be- tween real and generated graphs, featurized by these descriptors. The data log- likelihood of these classifiers approximates variational lower bound on the JS distance between the two distributions. Resulting scores are constrained to the unit interval [0, 1] and are comparable across different graph descriptors. We further derive a theoretically grounded summary score 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 more robust and insightful evaluation compared to MMD metrics. A reference implementation of PGD is available GitHub ? BorgwardtLab/ wtlpll/a/pooyypppbbeeeeeebe benchhark.
INTRODUCTION
Graph generative models (GGMs) are seeing wider adoption across scientific domains, from ret- rosynthesis (Somnath et al., 2021) and social network modeling (Bojchevski et al., 2018) to the discovery of novel drugs and materials (Liu et al., 2024; Kelvinius et al., 2025). However, progress in this field is increasingly bottlenecked by the lack of robust methods for evaluating generated graphs (Thompson et al., 2022; O' Bray et al., 2022).
This evaluation challenge is not unique to graphs. In image generation, the community has largely converged pretrained embeddings paired with distribution distances, such Inception-v3 coupled with Fréchet distance yielding the widely used Fréchet Inception distance (FID) (Heusel et al., 2017), or V2 and density estimation producing the Feature Likelihood Divergence (FLD) (Jiralerspong et al., 2023). While these approaches provide standardized metrics adapted to other fields such as materials (Kelvinius et al., 2025), video (Unterthiner et al., 2019), and audio (Kilgour et al., 2019), limitations remain (Barratt & Sharma, 2018). As an alternative, the classifier two-sample test (C2ST) (Lopez-Paz & Oquab, 2017) recasts evaluation supervised classification task, turning classifier performance into evaluation metrics. To date, the applicability of these approaches to graph-structured data has not yet been explored.
The de facto standard for evaluating GGMs is to compute the Maximum Mean Discrepancy (MMD) (Borgwardt et al., 2006; Gretton et al., 2006; 2012) between distributions of hand-crafted graph descriptors (e.g., degrees, Laplacian spectra, etc.) on small set of synthetic and world graphs (You et al., 2018). While convenient, this approach has critical limitations. The MMD value depends the choice of kernel and descriptor, so (i) single reported value without context carries no absolute notion of the goodness of fit the generative model, and (ii) rankings are sensitive to descriptor and kernel parameter choice (O' Bray al., 2022), with no way of obtaining single

---

Published as a conference paper at ICLR 2026
Table I: Comparison of Maximum Mean Discrepancy and PolyGraph Discrepancy. Normalized kernels bound MMD to [0, 2), but this is seldom adopted in GGM evaluation. Regardless, the interpretation of specific value remains kernel-dependent even within this bounded range. Note that while MMD values can be computed for different descriptors, the resulting scores are not comparable across kernels or feature spaces.
Property
MMD
PGD
Range
[0, 00)
[0. 1]
Intrinsic Scale
Descriptor Comparison
X
Single Ranking
X
ranking across descriptors for consistent and systematic model comparison. These issues persist re- gardless of how much data is available. In practice, rigorous GGM evaluation is further hampered by (iii) the small sample sizes typical of current GGM benchmarks (20 40 test graphs), which introduce substantial bias and variance into MMD estimates (Krimmel et al., 2026).
We introduce PolyGraph Discrepancy (PGD), novel evaluation framework that estimates the Jensen- Shannon distance (ISD) (Endres & Schindelin, 2003) between true and generated graph distributions using probabilistic classification instead of kernel-based distances. A discriminator trained to distinguish real from generated graphs using standard graph descriptors, where the classifier's data log-likelihood provides a lower bound on the JSD. This yields scores in [0. 1] that are directly com- descriptors gives the tightest available bound
parable across descriptors. Taking the maximum while identifying the most informative descriptor. Our formulation of PGD uses TabPFN (Hollmann al., 2025), fast, hyperparameter-free discriminator, making it robust and simple to use. Empiri- cally, we show that PGD monotonically tracks synthetic data perturbations, strongly correlates with model training progress, and accurately captures generated graph quality. also produces robust rankings across representative GGMs. Table summarizes the advantages of PGD over MMD.
Our work makes four primary contributions:
A rigorous reassessment of MMD for GGM evaluation. We empirically show that standard MMD estimators are plagued by high bias and variance at typical benchmark sizes (20-40 graphs), leading to unreliable model rankings, and we provide actionable remedies.
PolyGraph Discrepancy (PGD): an estimate of the JSD distance between distributions. We propose a method to derive interpretable evaluation scores by approximating variational lower bounds on the JSD) via probabilistic discrimination on graph descriptors.
A comprehensive empirical validation. We show that PGD tracks data perturbations monoton- ically and correlates strongly with training dynamics state-of-the-an models. We also provide comprehensive PGD-based benchmark results across synthetic and real-world graphs, including molecules.
An open-source library to advance GGM evaluation. We release the PolyGraph library, including implementations of PGD, MMD estimators, and new, larger benchmark datasets (SBM- L, LOBSTER-L, PLANAR-L.), facilitate more robust and reproducible future research.
2 RELATED WORK
Here we present related work on the evaluation of graph generative models and classifier-based evaluation for general generative models.
Evaluation of Graph Generative Models. The evaluation of GGMs has largely been shaped by methods based on the MMD (Gretton et al., 2012). You et al. (2018) first proposed computing the MMD between generated and real graph distributions using a Wasserstein Gaussian kernel on a set of graph descriptors, including degree histograms, clustering coefficients, and orbit counts. To reduce the computational cost of this method, Liao et al. (2019) introduced a simpler kernel formu- lation using Gaussian kernel with the squared total variation distance, which gained widespread adoption (Martinkus et al., 2022; Vignac et al., 2023; Chen et al., 2025). However, this simplified kernel was shown be indefinite and highly sensitive to hyperparameter choices (O'Bra et al.,
2

---

Published as a conference paper at ICLR 2026
2022). Subsequent work has focused correcting these flaws, either by modifying the kernel to ensure is positive definite (O OrBay et al., 2022) or by employing standard RBF kernels with automated hyperparameter tuning (Thompson et al., 2022; Sriperumbudur et al., 2009). A parallel research effort has concentrated on identifying more expressive graph descriptors for use within the MMD framework. The initial set of statistics was augmented with the graph Laplacian spectrum by Liao et al. (2019), and more recently, graph neural networks (GNNs) have been used as powerful graph featurizers (Thompson al., 2022: Shirzad et al., 2022). These improvements address the reliability of MMD estimation, but a more fundamental limitation remains: since MMD has no inherent, kernel- iinee---ndeeeneent scale, it is difficult to assess whether newly proposed descriptors are better suited for discriminating between real and generaled graphs. PGD, however, is comparable across descriptors and thus explicitly quantifies their discriminative power.
Departing from MMD, other evaluation paradigms have been proposed. Southern et al. (2023) used tools from topological data analysis, featurizing graphs via persistent homology and comparing distributions based on their average persistence landscapes. In a different direction, Martinkus et al. (2022) introduced synthetic benchmark datasets (Planar and SBM) that allow for judging the structural validity of individual graph samples-such as planarity. The small size of the synthetic datasets and the resulting variance in MMD estimates were criticized by Krimmel et al. (2026). We expand these obxervations and propose concrete techniques for quantifying the uncertainty in GGM evaluation metrics, addressing a critical need for more reliable and reproducible evaluations.
Classifir-Basse Evaluation. One relevant family of metrics used for generative model evaluation is derived from the classifier two-sample test (C2ST) (Lopez-Paz & Oquab, 2017). This work proposes discriminate generated from reference samples via binary classification and repurpose the resulting accuracy as measure for the separability of the generated and reference distributions. By extension, it assesses the quality of the generative model.
The MMD can also be viewed through this lens, as it corresponds to the optimal linear risk of a kernel classifier (Sriperumbudur et al., 2009: Gretton Jitkrittum, 2016). Generative adversarial networks (GANs) (Goodfellow et al., 2014; Li et al., 2015; Binkowski et al., 2018; Arjovsky et al., 2017) also leverage a classifier's 's output, not just for training but also for evaluation, where classifier- based divergences (including MMD) have been shown to correlate well with the perceptual quality of generated images (Im et al., 2018).
Despite the success of these methods in other domains, their application to graph generation has been limited. While some work has used fixed multi-class classifiers on generated graphs to measure performance (Liu et al., 2019), classifiers that discriminate between real and generated graphs have not been explored beyond the MMD framework. Our work addresses this gap, proposing a novel classifier-based evaluation framework for GGMs that provides scores that (i) absolute, (äi) comparable across different graph descriptors, and (iil) capable of estimating lower bounds on certain probability metrics.
3 PRELIMINARIES
In this section, review two divergences, MMD and the unified variational perspective: the optimal performance of discriminator tasked with distinguishing between two distributions. We first discuss MMD, interpreting it the linear risk of a classifier in reproducing kernel Hilbert space (RKHS) (Sriperumbudur et al., 2009). We highlight its limitations in the context of graph generation, primarily its lack of an absolute scale, which motivates our subsequent review of the JS distance as foundation for more interpretable, classifier-based evaluation metrics such as the PolyGraph Diserepancy.
(JS) divergence, from
3.1 MMD AND ITS INTERPRETATION AS CLASSIFICATION RISK
Given two probability distributions P and Q over space X (in our case, the space of graphs) and kernel k: X x X - R, the squared MMD is defined as:
(1) The MMD can be expressed as the distance between the mean embeddings of and @ in the RKHS H induced by k. This framing leads to variational formulation where the MMD is precisely the
MMD Q. = Ex,x' - [1 (x.x')) 2B (xx, -g + By.y' - (yk
3

---

Published as a conference paper at ICLR 2026
optimal linear classification risk achievable by discriminator in the unit ball of 'H (Sriperumbudur et al., 2009). We refer to Appendix for a detailed derivation.
A fundamental limitation of MMD for model evaluation is its lack of absolute scale (O Bray et al., 2022). Even within single kernel family such as the RBF kernel, changing the bandwidth o changes the resulting MMD for the same pair of distributions, so single value carries kernel-independent meaning. In practice, this sensitivity is amplified by the choice of input features: with a linear kernel, for instance, simply rescaling the features rescales the MMD by the same factor. As a result, comparing MMD scores across different graph descriptors is not meaningful, and while MMD can rank models for fixed descriptor, it provides no absolute measure of performance.
To overcome this, we turn to metrics that possess fixed intrinsic scale, making them comparable across different graph descriptors. This leads us the Censen-Shannod divergence and, more generally, to the family of f-divergences.
3.2 VARIATIONAL ESTIMATION OF THE SENSEN-SHANNON DISTANCE
(JS) divergence is symmetrized version of the Kullback-Leibler (KL) diver- gence: (DxL (P M) + (2 M)) with M == {P Q)) being the mixture of P and Q. It is constrained to the unit interval [0, 1] and, in contrast to MMD, is independent of extrinsic parameters such as kernel choice. As extensively leveraged in GANs (Goodfellow et al., 2014), the JS divergence admits (under mild conditions) a variational formulation as the maximal data log-likelihood (up to constants) achievable by binary classifier 1) distinguishing between samples from P and Q:
The
sup BB.rrllog, D(x) | -BB-ollogg(( (1))))))))())))-----)))))))))))) 1.
Dis ( ()
D:X-[0.1]
Importantly, the log-like ligeliield of any classifier provides valid lower bound on the JS divergence and the bound is tightened by fitting a classifier via maximum likelihood methods. While the JS divergence is not metric, its square root (termed the JS distance) is (Endres & Schindelin, 2003).
The JS divergence belongs to the larger family of f-divergences. As shown by Nguyen et al. (2010), any f-divergence admits variational formulation similar to Eqn. (2). In Appendix E, investigate the total variation (TV) distance as a possible alternative to the JS distance. Instead of log-likelihood, show that the variational objective of the TV distance given by the classifier's informedness.
4 POLYGRAPH DISCREPANCY: VARIATIONAL ESTIMATES OF THE JS DISTANCE
Building on the variational view of divergences, we introduce PolyGraph Discrepancy (PGD), framework for evaluating GGMs. PGD estimates the distance between a distribution reference graphs and a distribution of generated graphs. The core idea is to reframe the divergence estimation as a classification task: we featurize graphs using a variety of established graph descriptors and measure how well powerful, non-parametric classifier can distinguish between the two sets. The resulting classifier performance, measured in terms of log-likelihood, serves as tight, empirical lower bound on the true JS divergence between the underlying graph distributions. Fig. shows this procedure.
Our method proceeds in two main stages. First, we detail how to estimate lower bound the divergence using a single graph descriptor in Section 4.1. Second, we describe in Section 4.2 how systematically combine multiple descriptors from larger set compute the final PGD, which represents the tightest lower bound from the given descriptors. We provide pseudocode in Appendix B.
4.1 ESTIMATING THE JS DISTANCE WITH A SINGLE DESCRIPTOR
Given a multiset of reference graphs Pief and generated graphs Qgen- along with a single graph descriptor d X R", estimate the divergence of Pref and Q Qgen via featurization by d.
To prevent overfitting, where classifier might perfectly memorize the training data and thus over- estimate the true divergence, randomly partition both Pref and Q gee into disjoint fit and test
4

---

Published as a conference paper at ICLR 2026
Graph descriptors
fit/test split
Cross-validate TabPFN on fit
Train on f
Graph samples
Evaluate on test
Orbit
Strongest descriptor
Reference
PGD log-likelihood
Spectrum
Generated
Computation of the PGD metric. TabPFN is trained to discriminate between generated and reference graphs based on different vectorial descriptions. The most expressive descriptor (here: orbit) is used to derive the final PGD, yielding maximally tight lower bound on the Jensen-Shanme (JS) distance between the generated and reference graph distributions.
Figure I:
sets of equal size, Our goal is to approximate the supremum Eqn. (2) by training discriminator exclusively on the fit set, and computing the final divergence estimate on the held-out test set.
Discriminator Choice. An appropriate discriminator for this task must satisfy three criteria:
1. Probabilistic: must output class probabilities to estimate the JS divergence via its lig-liieldhood objective.
2. Efficient: It must be fast to train, enabling rapid evaluation across many descriptors.
3. Hyperparameter-Free It should be robust and require no manual tuning to ensure fair and reproducible comparisons.
These requirements rule out the training of deep neural networks with gradient descent, because computationally expensive and requires hyperparameter tuning. It also rules out probaabbbiiiittic models such as decision trees and SVMs. As a result, we choose TabPFN v2.5 (Hollmann et al., 2025) in this work. TabPFN is transformer-based model that approximates Bayesian inference over a large space of simple models consisting of Bayesian neural networks and structural causal models. It is fast (see Table 15), requires hyperparameter tuning, and has proven to be powerful classifier for tabular data, making it an idcal choice for our framework since our classifier operates graph descriptors. In Appendix
investigate logistic regression as an alternative choice and show that TabPFN yields tighter bounds in practice. In Appendix R we show that kernel logistic regression also fits naturally into the PGD framework, allowing for the use of, e.g., graph kernels (Borgwardt & Kriegel, 2005; Shervashidze et al., 2011; Grauman & Darrell, 2007). However, similar to logistic regression, we found that those kernel logistic regression- based PGD scores yielded looser bounds in practice, and elected to proceed with TabPFN.
Estimation Procedure. With discriminator selected, we first apply the descriptor d to the graphs in the fit set to create vectorial features. We then train the binary classifier these features using TabPFN. We apply the descriptor to the test set and use the trained classifier to evaluate the data log- ligeliie,,hood, providing approximate lower bound of the JS divergence. Finally, we take the square root to estimate the JS distance.
R
4.2 DESCRIPTOR SELECTION FOR THE TIGHTEST BOUND
A single graph descriptor captures only one specific aspect of graph structure. To obtain a more comprehensive evaluation, we consider a collection of K distinct descriptors (di....,de dx). The goal is to identify the single descriptor that most effectively distinguishes between the reference and generated graphs, as this descriptor will yield the tightest lower bound on the true JS distance. This descriptor selection process must be performed carefully to avoid data leakage from the test set,
5

---

Published as a conference paper at ICLR 2026
which would invalidate our final estimate. We therefore perform selection using only the fit data via cross-validation.
the Fit Set. For cach descriptor de X R", estimate its ability to separate the distributions by performing 4-fold stratified cross- cros-validdttion on the (Pii nef 2gen data. In each fold, three-quarters of the data are used for training discriminator, and the remaining quarter used for validation. The average validation score across the four folds provides a robust estimate of the lower bound achievable by that descriptor.
The PolyGraph Discrepancy. After performing cross-validation for all K descriptors, we select the descriptor dl that yielded the highest average score. This is the descriptor that is empirically the most informative. Finally, we train a new discriminator for d' on the entire fit set and evaluate it on the held-out test set. The resulting score is the PolyGraph Discrepancy (PGD). This procedure ensures that the descriptor selection and final evaluation are performed on separate data, yielding principled and tight estimate of the divergence between the graph distributions.
EXPERIMENTS
We empirically validate PGD through series of experiments designed to test its robustness, sen- sitivity, and practical utility against standard MMD-basee metries for evaluating graph generative models. Our investigation consists of four stages:
First, Section 5.1 shows that MMD evaluations suffer from substantial bias and variance current datasets, motivating the use of larger datasets, unbiased estimators, and subsampling to assess estimate stability.
In Section 5.2, we show that PGD correlates well with controlled perturbationss applied to synthetic datasets, showing the power of JSD distinguish samples from different distributions.
In a realistic use case for oftte-of-hheaar diffusion model (Section 5.3). we show that PGD reliably tracks training progress and performance gains when increasing the number of denoising steps. Our results indicate that PGD captures model quality more reliably than MMD metrics.
Finally, in Section 5.4 we leverage PGD to conduct a comprehensive benchmark of several repre- sentative GGMs.
Unless otherwise stated, all PGD scores are based on the Jensen- -haennnn (JS) distance estimated using TabPFN as the discriminator. Following previous works (You et al., 2018; Liao et al., 2019; Thompson et al., 2022), we use degree histograms (abbreviated as Degree/Deg. and figures), clustering coefficient histograms (Clustering/Clust) the Laplacian spectrum (Spec- tral/Spec.), orbit counts (Orbit), and GIN embeddings (GIN) as descriptors. For molecular graphs, domain-specific descriptors based on topological properties, physico-chemical parameters, and learned representations. We refer to Appendix for further details.
our tables
5.1 HIGH BIAS AND VARIANCE PLAGUE MMD-BASED GGM BENCHMARKS
The evaluation of GGMs is predominantly conducted on synthetic, procedurally gen- erated datasets, including lobster graphs stochastic block models (SBMs), and pla- nar graphs, which permit the generation of arbitrarily large numbers of samples. Krimmel et al. (2026) first raised the is- sue that MMD values computed on such datasets can exhibit considerable variance, thereby casting doubt on the robustness of model rankings derived from these met- rics. In order to more rigorously charac- terize this phenomenon, we exploited the procedural nature these datasets to sys- tematically vary the subsample sizes used in MMD. The MMD shown here is ob- tained with the radial basis function (RBF) kernel; more details given in Appendix G.
RBF Orbit Planar
on
0.3
Graph Sources
10
0.2
DiGress
MMD
MMD
10-2
Graph Sources
Tast Set
10-a
DiGress
0.0
4096
1024
4096
Number of Graphs
Number of Graphs
(a) Biased MMD.
(b) Unbiased MMD.
Figure 2: Examples of MMD estimates that suffer from high bias (left) and variance (right).

---

Published as a conference paper at ICLR 2026
In the regime of commonly used synthetic graph benchmarks (between 20 and 40 test graphs, cf. Appendix P). bias dominates the MMD values (Figure 2a, in log scale for clarity). Even when using the unbiased MMD estimator', the variance across subsamples remains large enough to make model comparisons at these sample sizes unreliable (Figure 2h). Figure 2 illustrates these issues for samples for planar graphs described with orbit counts, but extensive experiments in Appendix G show that they persist across all combinations of models, descriptors, and datasets.
This finding yields three actionable insights. First, prefer unbiased MMD estimates, as bias depends heavily on sample size. Second, akin to Krimmel et al. (2026), use larger sample sizes to reduce estimator variance; we propose SBM-L, PLANAR-L, and LOBSTER-L for this purpose (with more Perroose details in Appendix M)". Third. report the variance of MMD across subsamples to quantify the stability of the estimates. To assess the effect of dataset size on PGD, we conducted analogous experiments in Appendix I., which show that its mean and variance stabilize beyond subsample sizes of about 256. This is particularly relevant because TabPFN's discriminative power may depend on sample size.
5.2 POLYGRAPH DISCREPANCY TRACKS SYNTHETIC DATA PERTURBATIONS
To validate PGD as a reliable metric, we verify its ability to correlate with the magnitude of perturbations applied to graph datasets, standard procedure for evaluating graph metrics (O Bray et al., 2022; Thompson et al., 2022). Our experiments demonstrate that PGD effectively tracks these changes, performing on par with MMDs.
Experimental Setup. We conduct our experiments on five datasets: Protein contact graphs (Dobson & Doig, 2003), ego nets extracted from Citeseer (Sen al., 2008), and three procedural datasets (Planar, SBM, Lobster). Each procedural dataset contains 4096 samples, while the proteins dataset contains 918 samples, and the ego dataset contains 757 samples. Dataset details are in Appendix P.
To simulate data corruption, we apply five distinct perturbation types, four of which are adapted from previous studies (O' Orara al., 2022: Thompson et al., 2022). Each perturbation modifies the graph structure (or dataset) in a controlled manner. Edge deletion/addition removes or adds a specified number of edges selected at random. Edge rewiring replaces one of the incident vertices of some edges with a randomly selected vertex. Mixing operates on the dataset level by replacing a fraction of the graphs within a dataset with new samples from an Erdōs-Rényí model. Finally, we propose a novel perturbation type which we term "edge swapping". Edge swapping selects pairs of edges and swaps two of their incident vertices. This transformation preserves the vertex degrees, making it a more challenging perturbation for some metrics to detect.
Perturbation Experiments. Our core experiment involves splitting each dataset into two equal subsets: one serves fixed reference distribution, and the other is subjected to the perturbations. We then measure the distance between the reference and the perturbed subset using PGD and MMD metrics. In contrast to MMD, whose boundedness requires normalized kernels that are seldom used in practice, PGD) is naturally bounded in [0. 1]. This means it can saturate, or reach its maximum value, when perturbations are too large and the distributions become non-overlapping. To account for this, we first determine the perturbation magnitude at which PGD saturates (specifically, exceeds 0.95). We then apply perturbations only within this non-saturating range and compute the Spearman correlation between the metric scores and perturbation magnitudes. We visualize these correlation coefficients in Fig. 3, where each data point represents a combination of dataset, perturbation type, and metric. Our results show that PGD consistently exhibits a strong rank correlation with perturbation magnitude, comparable to that of MMD metries. We note that while the degree-based and GIN-based MMD metrics struggle to detect the edge-swapping perturbation, PGD remains robust by leveraging multiple descriptors that compensate for compromised ones.
We provide more details in Appendix H. where we illustrate the behavior of PGD function of perturbation magnitude for all combinations of datasets and perturbations. From that analysis, conclude that no single descriptor dominates the others across all combinations of datasets and
'Our MMD estimates not unbiased, as we take the maximum MMD value over of kernel handwidths, but do the unbiased MMD estimate without diagonals, see Eq. 3 Gretton et al. (2012).
2 AutoGraph reaches similar validity, uniqueness and novelty (VUN) scores with markedly lower loss in SBM- I. than on the original SBM dataset (see Appendix N), showing reduced overfitting, which is underexplored in GGMs (Vignac et al., 2023).
7

---

Published as a conference paper at ICLR 2026
Edge Deletion
Edge Rewiring
Edge Swapping
Mixing
Edge Addition
1.00
1.00
1.03
0.75
0.75
0.75
0.75
0.75
0.50
0.50
0.50
0.50
0.50
0.25
0.25
0.25
0.25
0.25
O6d ner
Spec, ner
ner
on mar
Roo
nor
Deg nor ner
Chat sur
ner
Poo
Orta nor Deg ner
ner
Clast ner
cit Roo
ore ner
Dey Spic ner
Clatt nar
city nor
Pop
ors ner Dez ner Speci nor ctst
de sgr
Figure
Spearman correlation of MMDs and PGD with magnitude of perturbation.
Validity
PolyGraph Discrepancy
MMD
x10
x10
xlo
xIo
x10-1
Validity
0.8
0.4
1.0
0.4
0.8
1.0
MMD
3.0
6.0
4.5
7.5
4.5
6.0
1.2
1.8
3.0
-
2.0
-16
-12
0.2
0.2
1.5
1.5
3.0
0.6
0.4
90
30
90
30
90
# Denoising Steps
# Denoising Steps
# Denoising Steps
Validity
Orbit RBF
Spectral RBF Clustering
Gin RBF
PolyGraph Discrepancy
Degree
Figure 4: Trajectory of validity, PGD, and MMDs when increasing the number of denoising steps in DiGress on PLANAR-L.
perturbation types, underlining the necessity considering diverse set of graph descriptors. We present additional experiments for PGD estimating the Total Variation distance in Appendix F.2. Appendix provides similar results for a PGD variant using logistic regression instead of TabPFN.
5.3 POLYGRAPH DISCREPANCY CORRELATES WITH MODEL QUALITY
To demonstrate practical utility, evaluate PGD DiGress (Vignac al., 2023), state-of- the-art GGM, using denoising iterations and training epochs as proxies for model quality. PGD strongly correlates with both, capturing model improvement more faithfully than MMD metrics while maintaining a strong linear correlation with the percentage of valid graphs generated. All metries were computed comparing 2048 reference graphs against 2048 generated graphs.
Denoising Iterations. We first analyze the impact of the number of denoising steps on sample quality. Six DiGress models are trained on the large procedural planar dataset using range of 15 to 90 denoising steps. As shown in Fig. 4, increasing the number of steps generally improves model performance across metrics. We find that PGD has a much stronger linear relationship with validity than MMD metrics, as shown by the Pearson correlation coefficients in Table 2. This tight relationship is especially encouraging as validity, alongside uniqueness and novelty, often considered a gold standard metric for assessing model quality. Yet, validity is not always defined. Uniqueness and novelty can be provided jointly with PGD to offer complementary insights.
Training Iterations. Similarly, assess the ability of MMD and PGD to track model quality throughout the training process on LOBSTER-L, PLANAR-L, and SBM-L. The central hypothesis is that reliable metrics should improve monotonically with training duration. We note that this relationship is non-linen linear, hence the use of Spearman's correlation coefficient. As illustrated for the SBM-L dataset in Fig. 5, PGD and validity align with this hypothesis, whereas MMD metrics exhibit erratic behavior. Analogous results for PLANAR-L and LOBSTER- are provided in Appendix Spearman's rank correlation in Table 3 confirms this quantitatively across all datasets: both PGD and validity are strongly correlated with training duration, while MMD metrics show weak or even negative correlations. The Pearson correlations in Table further show that PGD maintains its strong linear correlation with validity during training, a property not consistently shared by MMD metrics.
5.4 BENCHMARKING REPRESENTATIVE MODELS
We next present concrete PGD values and their associated subscores on set of well-established mod- els spanning distinct generative paradigms, including autoregressive architectures such GRAN
8

---

Published as a conference paper at ICLR 2026
Table Negative Pearson correlation (T) of validity with other distance-based metrics. Denoising refers to the experiments in which we vary the number of denoising iterations. Training refers to the experiments in which we monitor performance metrics during the training DiGress models. Values are multiplied by 100 for readability.
Dataset
PGD
Orb. RBF
Deg. RBF
Eig. RBF
Clust. RBF
GIN RBF
Denoising
PLANAR-L
99.29
73.50
70.87
73.41
71.36
82.52
PLANAR-L
97.65
84.32
59.11
76.47
88.31
68.11
Training
SBM-L
92.42
52.80
5.14
23.32
85.27
6.32
LOBSTER-L
86.54
-34.65
-35.17
-22.95
87.05
-30,55
Validity
PolyGraph Discrepancy
MMD
x10
x10
1.0
Validity
0.8
0.8
5
1.28
1.0
-6
0.6
0.6
MMD-
2.0
4
1.20
0.8
0.4
1.0
1.12
0.4
0.2
0.2
1.04
-
0.0
0.0
0.96
600
1200
0
600
1200
600
1200
Epochs
# Epochs
Epochs
Validity
Orbit RBF
Spectral RBF
RBF
PolyGraph Discrepancy
Degree RBF
Clustering RBF
Figure 5: Trajectory of validity, PGD, and MMD metrics during training of DiGress on SBM-L.
(Liao et al., 2019) and AutoGraph (Chen et al., 2025) and diffusion models such as ESGG (Bergmeis- ter et al., 2024) and DIGRESS (Vignae al., 2023). We benchmark them on our proposed datasets, SBM-I,, LORSTER-I,, and PLANAR-LL (with 4096 samples each, see Appendix M) as well as the Proteins dataset with 92 test samples (Dobson & Doig, 2003). Additionally, we present PGD bench- marks of AutoGraph and DiGress the molecular datasets GuacaMol (Brown et al., 2019) and MOSES (Polykovskiy et al., 2020) using 10,000 generated samples for benchmarking. For these datasets, we propose domainnspecciio descriptors which describe in Appendix C.2. Appendix K contains further benchmarking methodological details.
As shown in Table 4, AutoGraph and DiGress achieve the best overall PGD scores datasets. PGD generally aligns with VUN or validity rankings, though some exceptions exist-ESGG ranks highest in VUN on PLANAR-L but performs worse in PGD. The Proteins dataset yields the highest scores, suggesting greater modeling difficulty; its higher standard deviations reflect the smaller test set (92 samples vs. 4096 for procedural datasets). Max-reduction proves helpful in edge cases like LOBSTER-L, where clustering coefficients are uniformly zero, preventing a single uninformative subscore from masking other structural flaws. When interpreting the final PGD score, note it can differ from individual subscores since they use different datasets. Subscores are averaged over cross-validation splits on the training sel to select the most informative descriptor, while the final PGD is computed the test potentially yielding different results. Appendix K compares MMD and PGD values using Gaussian pseudo-kernels (Table 11) and optimized RBF kernels (Tables 12 and 13). Overall, PGD yields more interpretable model rankings than MMDs.
We also consider a feature concatenation variant of PGD as an alternative to max-reduction, where we concatenate all descriptors and train single discriminator on the combined features (Appendix Q)- While this yields tighter bounds (higher JSD estimates), it prevents identifying the most informative descriptor; therefore, we recommend max-reduction in practice.
6 CONCLUSION
We introduce PGD, classifier-based evaluation that yields unit-scale metrics by training dis- criminator on standard graph descriptors and selecting the most informative one. Instantiated with TabPFN to estimate the JS distance, PGD is fast and tuning-free Across perturbation and model- quality studies, PGD increases monotonically with synthetic noise and correlates strongly-and often linearly-with validity and training progress. It also produces robust rankings with descriptor-specific

---

Published as a conference paper at ICLR 2026
Table 3: Sign-adjusted Spearman correlation (T) of validity, PGD, and MMDs with the number of training iterations for DiGress.
Dataset
Val.
PGD
Orb, RBF
Deg. RBF
Eig. RBF
Clust. RBF
GIN RBF
PLANAR-I.
96.36
93.64
75.45
68.18
50.00
86.36
77.27 -24.55
SBM-L
82.73
77.27
23.64
10.91
10.91
68.18
LOBSTER-L
85.47
83.33
-7.35
-13.24
6.86
68.14
1.23
Table 4: Mean PGD + standard deviation across synthetic and real-world graphs. AutoGraph" denotes a model pretrained on the PubChem dataset. More details can be found in the original paper (Chen et al., 2025). Values are multiplied by 100 for readability. Subscores are computed on the training set to select the best descriptor, and the final PGD refers to the score computed on the test with the best descriptor. All results have been obtained with TabPFN 2.5.
Datuset
Model
PGD subscores
VUN (t)
PGD (1)
Clust. (
Deg. ())
GIN ()
Orb5. ())
Orb4, ())
Eig. ())
PLANAR-L
AutoGrraph
34.1
8.7
9.8
DiGruss
79.6
46.7 =
28.3 +23
25.4 +0
29.8 #20
46.7 1/
43.0
39.9 +
GRAN
99.5
1.4
1007
99.4
ESGG
93.9
47.7 1:1
16.4.330
26.3 1:2
33.1 122
47.7 1:11
45.3 116
30.9 1:1
Lousna-LL
AutoGraph
82.6
13.4
12.4 1.5
DiGarss
918
1.1
2.3
1.4 1.7
3.5 -11
5.8 1.2
5.9 5.
L.0 1.6
GRAN
42.9
ESGG
70,9
70.6 0.06
0.0 0.0
64.0 1:099
67.4 1.0
70.6 2.6.
66.0 1.0.
$6.6 4
SBM-L
AutoGraph
87.1
6.8 1.2
1.3 1.4
5.6 2.66
688 211
3,3 2.3
3,9 1:28
3.2 1.9
DiGRESS
14.1
16.6-1v
7.0
+0.4
14.3
16.6
14.7
7.8
ESGG
11.0
99.3 2:03
97.1 0.0.
97.4 #:6
98.6 20.
95.6 2:3
90.2 A:A
99.3 t:0.3
Proteins
AutoCiraph DIGRESS
$7.3 11.5
39.8 à: 14.3
26.7 21.1
44.3 7.
62.1 #:1
48.1 4.9
50.0 a: 10.5
86,7
29.0 1
17.2 11.1
13.6 1.5
86.7 124
$7.3 1:46
23.3 a
GRAN
88.9 3.5
83.0 4.3
68.1 4.4
68.6 7.1
90.7 2:2
86.7 1.3.6
64.8 2:3
ESGG
78.8 2.00
58.4 188.5
55.2
59.3 152
19.4
72.0
29.3 1
Dataset
Model
PGD subscores
Valid (1)
PGD (1)
Topo ())
Morgan ())
ChemNet (L)
MolCLR ())
Lipinski (L)
GUACAMOL
AutoGraph
91.6
27.3 1.5
10.0
18.2
21.3 205
17.4 105
22.8 0.4
AutuGraphi
95.9
11.5 2..5
6.3 2.4
5.6
2.3
3.6
11.5 0.5
DiGRnss
85.2
37.4 +07
22.1 +.5
25.3 +0.
37.
24.8 +0.
35.2 +.5
MOsES
AutoGraph
87.4
33.5
24.5
24.8
33.0.20
26.1
33,5
DIGRESs
83.7
37.1 6.3
28.7 2.0.
29.5 2:07
36.3 205
30,2 2.066
37.1 2:0.
subscores. To standardize GGM evaluation and model selection, we release the PolyGraph library, PGD, and the larger datasets, which we show necessary to avoid high bias and variance observed hope that our work
evaluation metrics. We discuss potential limitations Appendix catalyzes progress in graph generation and, more broadly, enables effective evaluations of generative models where multiple combinations of possibly complementary descriptors are required.
ETHICS STATEMENT
This work develops evaluation methods for graph generative models and does not involve human subjects, animals, personal data. We foresee no harm to individuals, groups, or the environment.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of all results and plots of this work, we provide the PolyGraph library at ? BorgwardtLab/ hwwerrdtlaa/oolggppp--bbbbb war.yygraap--behcarr.... benchmark, implementing the PolyGraph Discrepancy, MMD metrics, and datasets discussed here, with tests ensuring consistency with the MMD implementations of Liao et al. (2019); Thompson et al. (2022). Details on the PGD estimation procedure, graph descriptors, and procedural dataset generation including model checkpoints and computed metrics, will be stored long-term private archive with minimum guaranteed access period of ten years.
in Appendices B, C and M. All generated data,
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Martín Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning (ICML), 2017. 3
Shane Barratt and Rishi Sharma. note on the inception score. arXiv preprint arXiv: arXiv:1801.000 180101993, 2018. 1,2
Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, and Roger Wattenhofer. Efficient and scalable graph generation through iterative local expansion. In International Conference Learning Representations (ICLR), 2024.
Miko laj Binkkoski, Danica J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying mmd
gans. In International Conference on Learning Representations (ICLR), 2018. 3
Aleksandar Bojchevski, Oleksandr Shehur, Daniel Zügner, and Stephan Günnemann. Netgan: Gen- erating graphs via random walks. In International Conference on Machine Learning (ICML), pp- 609-618, 2018.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels graphs. In Fifth IEEE international conference on data mining (ICDM 2005), pp. 8 8-pp. IEEE, 2005. 5, 30
Karsten M. Borgwardt, Arthur Gretton, Malte J. Rasch, Hans-Peter Kriegel, Bernhard Schölkopf, and Alex J. Smola. Integrating structured biological data by kernel maximum mean discrepancy. In Bioinformatics, volume 22, pp. e49-e57, 2006.
Nathan Brown, Marco Fiscato, Marwin HS Segler, and Alain Vaucher. Guacamol: benchmarking models for de novo molecular design. Journal of chemical information and modeling, 59(3): 1096-1108, 2019. 9
Dexiong Chen, Markus Krimmel, and Karsten M. Borgwardt. Flatten graphs sequences: Trans- formers are scalable graph generators. In Advances Neural Information Processing Systems (NeurIPS), 2025. 2, 9, 10
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Mol. Biol., 337(4):771-783, July 2003. 9,
Dominik Maria Endres and JE Schindelin. A new metric for probability distributions. IEEE Transactions on Information Theory, 49(7):1858-186) 2003. doi: 10. 10.1109/TT.220033813333 2, 4, 30
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems (NeurIPS), 2014. 3,4
Kristen Grauman and Trevor Darrell. The pyramid match kernel: Efficient learning with sets of features. Journal of Machine Learning Research (JMLR), 8(4), 2007. 5, 30
Arthur Gretton and Wittawat Jitkrittum. Openreview comment on "revisiting classifier two-sample tests". https: /
http://www........../////eeooee. cessed: 2025-07-22. 3
2016. Ac-
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel method for the two-sample problem. In Advances in Neural Information Processing Systems (NeurIPS), pp. 520, 2006.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research (JMLR), 13:723-773, 2012. 1, 2, 7, 23
Arie Hagberg, Pieter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. report,, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008. 29
11

---

Published as a conference paper at ICLR 2026
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems (NeurIPS), volume 30, pp. 6626-6637. Curran Associates, Inc., 2017.
Noah Hollmann, Samuel Müller, Lennart Purucker, Arjun Krishnakumar, Max Körfer, Shi Bin Hoo, Robin Tibor Schirrmeister, and Frank Hutter. Accurate predictions on small data with a tabular foundation model. Nature, 637:319-326, 01 2025. doi: 10. 10.1038/441556-0240088222
2,
Tomáš Hočevar. ORCA: ORbit Counting Algorithm. httpss:/gil htt///iithbbb thub com/thocevvr/orca, 2025. GitHub repository, GPL-3.0 License, last accessed: 2025-09-16.
Daniel Jiwoong Im, He Ma, Graham W. Taylor, and Kristin Branson. Quantitatively evaluating gans with divergences proposed for training. In International Conference on Learning Representations (ICLR), 2018. 3
Marco Jiralerspong, Avishek Joey Bose, Ian Gemp, Chongli Qin, Yoram Bachrach, and Gauthier Gidel. Feature likelihood divergence: Evaluating the generalization of generative models using samples. Advances in Neural Information Processing Systems (NeurIPS), volume 36, 2023.
Filip Ekström Kelvinius, Oskar B. Andersson, Abhijith S Parackal, Dong Qian, Rickard Armiento, and Fredrik Lindsten. Wyckoffdiff a generative diffusion model for crystal symmetry. In International Conference Machine Learning (ICMI.), 2025.
Kevin Kilgour, Mauricio Zuluaga, Dominik Roblek, and Matthew Sharifi. Fréchet audio distance: A reference-free metric for evaluating music enhancement algorithms. Proc. Interspeech, pp- 2350-2354, 2019, doi: 10.2 htt5:///meesspecch201122220
Markus Krimmel, Jenna Wiens, Karsten M. Borgwardt, and Dexiong Chen. Fast graph generation via autoregressive noisy filtration modeling. Transactions Machine Learning Research (TMLR), 2026. 2, 3, 6,
Yujia Li, Kevin Swersky, and Richard S. Zemel. Generative moment matching networks. In International Conference on Machine Learning (ICML), 2015. 3
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang. William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks. In Advances Neural Information Processing Systems (NeurIPS), pp. 4257 4267, 2019. 2, 3, 6,
9, 10, 4, 22
Chia-Cheng Liu, Harris Chan, and Kevin Luk. Auto-regressive graph generation modeling with improved evaluation methods. Presented at the NeurIPS Workshop on Graph Representation Learning, 2019. URL https://grlearning github. hww.bb/i/ppppes/7ppppom Workshop paper, Accessed: 2025-07-26.
Gang Liu, Jiaxin Xu, Tengfei Luo, and Meng Jiang. Graph diffusion transformers for multi- conditional molecular generation. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang (eds.), Advances in Neural Information Processing Systems, volume 37, pp. 8065-8091
Curran Associates, Inc., 2024.
David Lopez-Paz and Maxime Oquab. Revisiting classifier two-sample tests. In International Conference on Learning Representations (ICLR), 2017. 1,
Karolis Martinkus, Andreas Loukas, Nathanaël Perraudin, and Roger Wattenhofer. SPECTRE:
spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In International Conference on Muchine Learning (ICML), 2022. 2, 3, 28, 29
Andreas Mayr, Günter Klambauer, Thomas Unterthiner, Marvin Steijaert, Jörg K Wegner, Hugo Ceulemans, Arné Clevert, and Sepp Hochreiter Large-scale comparison of machine learning methods for drug target prediction on ChEMBL. Chem Sci, (124):544155451 June 2018. 8. 4,5
12

---

Published as a conference paper at ICLR 2026
XuanLong Nguyen, Martin J. Wainwright, and Michael I. Jordan. Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Trans. Inf. Theory. 56( 1)):8777- 5861, 2010. doi: 10.1 00.11099TT22010206688770 URL https://doi.org/ 101.///...11/III0001111 2068870. 4, 6,
Leslie O' O'Bayy, Max Horn, Bastian Rieck, and Karsten M. Borgwardt. Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions. In International Conference Learning Representations (ICLR), 2022. 1, 2, 3,47
Daniil Polykovskiy, Alexander Zhebrak, Benjamin Sanchez-Lengeling, Sergey Golovanov, Oktai Tatanov, Stanislav Belyaev, Rauf Kurbanov, Aleksey Artamonov, Vladimir Aladinskiy, Mark Veselov, Artur Kadurin, Simon Johansson, Hongming Chen, Sergey Nikolenko, Alan Aspuru- Guzik, and Alex Zhavoronkov. Molecular Sets (MOSES): A Benchmarking Platform for Molecular Generation Models. Frontiers in Pharmacology, 1 11:565644, 2020. 565644. 9
doi: 10.3389/fphar.2020)
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Günter Klambauer. Fréchet chemnet distance: A metric for generative models for molecules in drug discovery. Journal of Chemical Information and Modeling, 58(9): 1741, Sep 2018. ISSN 1549-9596. 4
RDKit. Rdkit: Open-source cheminformatics. https://ww.rrkiie
2024. [Online; accessed
15-September-2225. Version 2024.09.6], 4,5
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. AI Mag., 29(3):93-106, 2008 doi: 10.1609/AIMAG. V2913.2157. URL https://doi. org/ 10. 11110..6..1 1609/ aimag. 22293.2157,. 7,29
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardr. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research (JMLR), 12 (9), 2011. 30
Hamed Shirzad, Kaveh Hassani, and Danica Sutherland. Evaluating graph generative models with contrastively learned features. In Advances in Neural Information Processing Systems (NeurIPS), 2022. 3
Vignesh Ram Somnath, Charlotte Bunne, Connor Coley, Andreas Krause, and Regina Barzilay, Learning graph models for retrosynthesis prediction. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems (NeurIPS), volume 34, pp. 9405-9415. Curran Associates, Inc., 2021.
Joshua Southern, Jeremy Wayland, Michael M. Bronstein, and Bastian Rieck. Curvature filtrations for graph generative model evaluation. In Advances Neural Information Processing Systems (NeurIPS), 2023. 3
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Gert R. G. Lanckriet, and Bernhard Schölkopf. Kernel choice and classifiabilityy for RKHS embeddings of probability distributions. In Advances in Neural Information Processing Systems (NeurIPS), 2009. 3, 4
Rylee Thompson, Boris Knyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W. Taylor. On evalua- tion metries for graph generative models. In International Conference on Learning Representations (ICLR), 2022. 1, 3, 6, 7, 10, 4, 12, 23
Thomas Unterthiner, Sjoerd van Steenkiste, Karol Kurach, Raphaäl Marinier, Marcin Michalski, and Sylvain Gelly. FVD: A new metric for video generation. In Deep Generative Models for Highly Structured Data, ICLR 2019 Workshop, New Orleans, Louisiana, United States, May 6, 2019, 2019. 1
Aad W. van der Vaart. Asymptotic Statisties. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 1998. See Section 10.2 for the Bernstein-von Mises theorem. 12
Clément Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang. Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In International Con- ference Learning Representations (ICLR), 2023. 2, 7, 8,8,
13

---

Published as a conference paper at ICLR 2026
Yuyang Wang, Jianren Wang, Zhonglin Cao, and Amir Barati Farimani. Molecular contrastive learning of representations via graph neural networks. Nat. Mach. Intell. ((3):279-287, 2022. 4, 5
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning (ICML), 2018. 6,4
14

---

Published as a conference paper at ICLR 2026
Appendix
CONTENTS
A Limitations
2
PGD Pseudocode
C Graph Descriptors
D MMD as Linear Classification Risk
Background on f-Divergences and Total Variation Distance
PGD-TV: Estimating Total Variation Distances
G Supplemental for: High Bias and Variance Plague MMD-based GGM Benchmarks
12
Supplemental for: PGD Tracks Synthetic Data Perturbations
17
I Supplemental for: PGD Correlates With Model Quality
19
J Ablation: TabPEN vs Logistic Regression
20
K Supplemental for: Benchmarking Representative Models
20
Stability of PGD under varying sample sizes.
25
M Larger Procedural Reference Datasets for Better GGM Benchmarking
28
N Influence of Training Set Size on AutoGraph
28
Common Shortfalls Existing Solutions
28
P Dataset details
29
Feature concatenation as an alternative to max-reduction
29
Kernel logistic regression with graph kernels
30
S Use of Large Language Models
30

---

Published as a conference paper at ICLR 2026
A LIMITATIONS
Here, we touch upon some of the limitations of this work.
Descriptor dependence and information loss. PGD operates on hand-crafted descriptors rather than raw graphs. It therefore yields a lower bound of the divergence between descriptor distributions, which itself is lower bound of the divergence between the graph distributions. the divergence between descriptor distributions does not tightly approximate the divergence between graph distri- butions, the PGD is also inherently loose bound on the divergence between graph distributions. This highlights the importance of considering expressive descriptors.
The final max-reduction can also under-utilize complementary signals across descriptors. This could be addressed by combining features prior to TabPFN fitting, and using TabPFN extensions for automatic feature selection'.
Sample-size dependence On the one hand, PGD requires several hundred samples get an accurate metric value, as indicated in Appendix L, which requires some computational burden, especially for difficultto-coomuute descriptors. On the other hand, the sample size used our formulation of PGD is constrained by TabPFN's recommended 10k training limit, though this restriction only an implementation detail. This might be problematic practice a large number of samples is required to obtain tight bound. We recommend that users assess the variance of PGD carefully when considering new descriptors, graph types, and discriminators, The TabPFN extensions package also implements some approaches to extend the training size via subsampling and ensembling".
Feature dimensionality. While MMD) can operate high-dimensional graph descriptors, the classifier used in PGD may be less effective on very high-dimensional features. The graph descriptors proposed previous works (ef. Appendix C.I) are low-dimensional and well-suited for TabPFN v2.5, which does not impose feature dimensionality limits. In the context of evaluating molecule generative models, we employ random projections to map 512-dimensional graph representations to more compact feature space (ef. Appendix C.2). A more sophisticated feature selection process may yield tighter bounds on the IS distance. We leave the exploration optimal feature selection to future work.
Scopes of graph types, datasets, and models. Our experiments focus on common procedural datasets (with specific parameters), proteins, and molecules. We do not evaluate directed, temporal, or heterogeneous graphs, and leave this to future work. While we benchmark four different GGMs, covering autoregressive and denoising diffusion paradigms, we hope that future works adopt the PGD framework to extend benchmarks to wider variety of methods.
Application other domains. We focus on applying PGD generative graph evaluation, where the need for rigorous assessment is particularly acute. Nonetheless, the same approach could extend to other domains, though we leave this unexplored. One promising direction is improving V3-stlee scoring: our multi multi-deseriptor strategy could mitigate the sensitivity of FID to network initialization by max max-reducing across multiple Inception initializations, which was shown to be problematic by Barratt & Sharma (2018). 8).
B PGD PSEUDOCODE
We provide pseudocode for the computation of PGD in Algorithm 1. We note that the pro- cedure estimate .ivergencee corresponds to the algorithm we describe in Section 4.1 while polygraphscore implements the combination of descriptors we outline in Section 4.2.
see Footmote
2

---

Published as a conference paper at ICLR 2026
Algorithm PGD computation
1: procedure estimate divergence(train, val, mode)
2: clf + fit tabpfnl train)
3: preds + clf.
4: if mode "jsd" then
5:
metric mmax hikelhoooiiel val.y).0)
6:
else
7:
-
max info thresholddclf.preeeee (train.x), train.y)
8:
metric e informedness(pred, val.y.
9:
return metric
10:
procedure train. testeeesttiiieee serrrddivvegeeeeeeefeeeeeeee gentreeeeeeeeeeeeeenennnnnnneddd descriptor, mode,
12:
ref train, ref test + reference() :: 2]. refeerrecc 2]
Split reference graphs
gen_train, gen_test + generated[O) :: 2]. generated[1
Split generated graphs
14:
(X, Y) (descriptor((ref.rriin || gen_train),
1])
15:
folds + stratiffied
16:
metric + 0
17:
for train, val folds do
18:
ev_metric
metricc estimmate.divergencee,
val, mode)
CV metric cv metric/k
20: (Xiest, Yees) e (descriptor(ref test gen test), (0...0.1 1... 1])
test_metric < pestimateediveereee divergenceeee) Y), (Xiest- Yees), mode)
22:
return cv_metric, test_metric
23:
24: procedure htt.ygrraapdisscrppcccceceeee gen, mode)
25:
deserescssss + [orbit4, orbit5, deg, clust, spec, gin] all metrics + hash map()
26:
27:
for all descriptors do all all_metrics[d]] -
28:
gen, d, mode, 4)
29:
best desc +- arg max, all metrics[d] [d]].v]]] .ev evmeetiic
return all metrics[bes desc]. test metric

---

Published as a conference paper at ICLR 2026
C GRAPH DESCRIPTORS
In this section, we discuss the vectorial graph descriptions used in work. In Appendix C.I, we provide details on the descriptors we apply to the synthetic datasets (PLANAR-L, SBM-L, LOBSTER-L) and the Proteins dataset. These descriptors
for the most part, identical to established descriptors introduced for MMD evaluations (You et al., 2018; Liao et al., 2019; Thompson et al., 2022). In Appendix C.2, we introduce novel descriptors for evaluating generative models for molecules.
We recommend that practitioners use domain-specific and expressive descriptors whenever possible, similar procedure for molecules in Appendix C.2. As discussed previously, one should aim to maximize the PGD metric when engineering graph descriptors.
C.1 GENERIC DESCRIPTORS
We use graph descriptors that have previously been proposed for evaluations via Maximum Mean Discrepancy. Histograms of clustering coefficients and node degrees, as well as 4-node orbit counts, have been proposed by You et al. (2018). These descriptors were extended by Liao al. (2019) via the spectrum of the graph Laplacian. Finally, Thompson et al. (2022) proposed to featurize graphs via randomly initialized GIN models. We extend these descriptors with 5-node orbit counts, computed with the ORCA algorithm (Hočevar, 2025). In our model benchmarks, we find that 5-node orbit counts oftentimes yield the highest PGD, hence representing a strong descriptor (cf. Table 4). However, we find in the perturbation experiments (cf. Appendix H) that no single descriptor consistently dominates the others. This demonstrates the importance of considering a wide variety of graph featurizers. We summarize our deseriptors in Table 5.
Table 5: Generic graph descriptors.
Descriptor
Meaning
Reference
Clust.
Histogram of clustering coeffi- cients, discretized to 100 bins in
You et al. (2018)
[0,
Deg,
Histogram of node degrees
You et al. (2018)
GIN
Activations of randomly initial- ized GIN graph neural network
Thompson et al. (2022)
Eig.
Histogram of Laplacian spectrum, discretized to 200 bins in [-10- $22]
Liao et al. (2019)
Orb. 4
4-node orbit counts
You et al. (2018); Hočevar (2025)
Orb. 5
5-node orbit counts
Hočevar (2025)
C.2 MoLrcuLE-SPrcIICC DESCRIPTORS
We propose several novel descriptors for evaluating generative models for molecules via the PolyGraphScore framework. Some of these descriptors are established in chemoin- formatics and are computed via RDKit (RDKit, 2024). Namely, topological quantities (rdkit. Chem. GraphDescriptors) physico-chemice parameters (rdkit. Chem. www..hhee..meeeeeeeeeceeeeeetste and classical Morgan molecule fingerprints (rdkit. Chem. AllChem. GetMorgaanGenrattor)) Addi- tionally, we use learned representations extracted either from a SMILES-based LSTM model (Mayr et al., 2018) (termed ChemNet), from the contrastively trained MoICLR graph neural net- work (Wang et al., 2022). The SMILES-based model has previously been used to formulate the Fréchet ChemNet distance (Preuer al., 2018). To obtain more compact features, map the learned representations into a 128-dimensional space via sparse random projections with a fixed random seed.
These descriptors can only be computed for molecular graphs which can be converted into rdkit. Chem. rdchem. Mol objects, i.e., for graphs which chemically valid. Hence, must

---

Published as a conference paper at ICLR 2026
filter generated graphs before computing PGD score. A similar approach has been taken in the Fréchet ChemNet distance.
We summarize these descriptors in more detail in Table 6.
Table 6: Descriptors used for molecular graphs.
Descriptor
Meaning
Features
Reference
Morgan
128-D Morgan count fin-
Substructure hash counts
RDKit (2024)
gerprint
ChemNet
128-D projection of Latent
Mayr (2018)
ChemNet embedding of canonical SMILES string
MolCLR
128-D projection of
Latent
Wang al. (2022)
MolCLR embedding of molecule graph
Topo
Topologicaltopochemical descriptors based on the bond structure
1. AvgIpc
RDKit (2024)
2. BertzCT
3. Balaban]
HallKierAlpha
Kappal
6. Kappa2
7. Kappa3
8. Chi@
Chi@n
10. Chi@v
11. Chil
12. Chiln
13. Chilv
14. ChiZn
ChiZv
16. Chi3n
17. Chi3v
18. Chi4n
19. Chi4v
Lipinski
Structural and physicu- chemical parameters
HeavyAtomCount
RDKit (2024)
NHOHCount
3. NOCount
4. NumliAccppoors
MunHDonors
NunHeteroatons
7. NumRotatableBonds
8. RingCount
9. NumAl phaticcarbooccllss
10. NunAl iptttiiceeeieeeeocycllees
NumAliphaticRings
KumAtromaticCarboocycle.
13. Nimarromaticceeeeercyyll..
14. NumAromaticRings
15. NumHeterocyyles
NumssturaatelCaarboyyyllsss
KunSatuuratedlieeeerrccy...le
18. KunSaturateeRRings
19. VumAmideBonde
20.
NumAtomStereet tereeeentrrrre
Kunthspeci
XunBridgeheadAttmss
NumSpiroAtoms
24.
FractionCSP3
25. Phi
5

---

Published as a conference paper at ICLR 2026
D MMD AS LINEAR CLASSIFICATION RISK
In this section, we expand on the discussion Section 3.1 and derive how MMD may be seen as the optimal risk for distinguishing between P and of binary classifier in the reproducing kernel Hilbert space H.
Using the notation Bx[k(x, )] for the Riesz representative of the (under mild conditions) bounded linear form f - &,I(S (x,, ))}, one may show:
MMD(P, =|[xx-p(k(x,
By-elk(y,, -)lll
sup (D, Bx-rlk(x, - Bl--y-elk(), )])
11DIES1
sup (D, (k<x, )) (D. (0--elk(x )1)
(3)
[PDlwsl
sup
- -By-o(D())
[PP|WS!
We use the Cauchy-Schward incquality in the second equality, the linearity of the inner product in the third equality, and the definition of the Riesz representative in the last equality.
This framing reveals that MMD is precisely the optimal linear classification risk achievable by discriminator D in the unit ball of the function space induced by the kernel.
E BACKGROUND ON
- f-DIVEGGENCES AND TOTAL VARIATION DISTANCE
Let P and Q be probability measures on X that are assumed to be absolutely continuous with respect to base measure ju, having densities and q. For now, also assume P to be absolutely continuous w.r.t. Q. For convex, semiooscmioonssuuuus function f -R+-- - R satisfying f(0) 1, the
f-divergence P from Q is defined as:
f {(x)
p(x) g(x)
Dy D2
du
(4)
As shown by Nguyen et al. (2010), f -iierreence can be estimated via a variational objective similar that of MMD. Using the Fenchel conjugate (v) suPue3, av f(u), the f-divergence is lower-bounded by: Dy(P
2 sup B.-r(D(x)) - -By-el Def
(5)
for any family F of measurable functions 1) D - R. The bound is tight if and only if the functional class sufficiently expressive contain a subderivative of f at the density ratio (x)). Such function then achieves the supremum. The variational formulation of the Jensen-Shannon divergence Eqn. (2) is a special case of Eqn. (5)
Total Variation Distance. The total variation (TV) distance corresponds to f(x = 2 x One may easily verify that the integral in Eqn. (4) evaluates to half of the L' distance between p and q. As show in Appendix F.1, its variational objective in Eqn. (5) can be reduced to:
sup D:X-10.11 y=[0,1]
Ex-P [[D(x) yll - Ex-oo ([D(x) > y]].
(6)
where the Iverson bracket (D(x) y] denote the binarization of D the threshold y- This objective is also known as the Informedness (or Youden's statistic) of the discriminator D. has clear geometric interpretation as the maximum vertical distance between the ROC curve of D and the chance diagonal, with fixed scale of [0, 1].
F PGD-TV: ESTIMATING TOTAL VARIATION DISTANCES
In this section, we propose an alternative variant of the PGD, using variational estimates of the total variation (TV) distance in place of the
distance. We term this variant PGD-TV.

---

Published as a conference paper at ICLR 2026
We recall from Appendix E that the variational objective for the TV distance is given by the informedness of a dichotomized classifier. We provide a proof of this fact in Appendix F.I. When computing PGD-TV, the choice of binarization threshold is considered part of the fitting process of the classifier. Hence, we choose y to maximize the vertical distance of the ROC on the fir set. We refer to Appendix B for pseudocode. In Appendices F.2 and F.3, present empirical investigation of PGD-TV, analogous to the experiments presented in Sections 5.2 and 5.3. Finally, we discuss the advantages of PGD over PGD-TV in Appendix F.4
F.1 VARIATIONAL. FORMULATION OF TV DISTANCE
One may easily verify that for f(u) = ul, we have the following Fenchel conjugate:
2 if
v v< - v 2.
((v) sup av
2 u| =
V if
(7)
weR.
if 2
We recall the variational lower bound: Drv(P 2 sup -By--
(8)
DEF
Without weakening the lower bound, we may restrict ourselves to families of functions which are upper-bounded by almost everywhere w.r.t. Q. Indeed, discriminators assuming P < Q, the discriminators are then
that do not satisfy
this have variational bound of -co. Since also upper-bounded almost everywhere w.r.t. P. Hence, w.l.o.g., we may assume that they are hoper-bounded by everywhere. Under these assumptions, we obtain the simpler formulation:
Drv(P 2 sup Bx-p(D(x)) - -y-- max ((.)-11) DET
/ D(x)p(x) max (D(S). g(x))) Def _
sup
Under the constraint that D(x) s 2. we may maximize the expression above in a pointwise fashion by:
1 if p(x) q(x)
D(x)
[- if p(x) s (xx)
(10)
We note that this is consistent with the finding of Nguyen et al. (2010) that D(x) should attain subderivative of f at the point p(x) Therefore, without weakening the lower bound, may write: (xx)
PP [P 112) z
sup Bx-r(D(x)] - Bx-Q max (
(D())_ -20)--2)
(-X-(-1.1)
sup
E.-rl (D)) Ex-olD(x)
D (-++)
(11)
sup
Bx-r P [x()) Ex-e(D(x))
D:X-(0.1)
Ex-p (D)()) > yl1 - -xx-o((-(()) > yll
D:X-10.11 y=[0.1]
The first equality is derived from the observation that D(x) 2 - al always holds and the maximum therefore redundant. The second equality is obtained by noting that the expression is invariant under the addition of constants to D (in this case, we add 5
Without relying on the results of Nguyen et al. (2010), now show that this bound is tight, even when P * Q. To work in this more general setting, we redefine the total variation distance as half the L' distance of p and g:
1 =>1pp= all (x = - [p(x) - -xx))
Drv
(12)
7

---

Published as a conference paper at ICLR 2026
One may verify that this matches our original definition when P < Q. For any measurable set X, we note that:
1= p(x)du++ [xc p(x)du= g(x)du+ JSC ((x)
(13)
Hence, rearranging, obtain:
J. p(xx) - qxx)du== Ssc 9(x) - q(x)- p(x)
(14)
Defining A == XxEX: p(x) 2 q(x)) and applying this identity, we get:
2 f (p(x) g(x)ldu 1
1
9(x) 2 J. p(x) 9(x) 2 / 9(x) - -
(15)
= -f, p(x) - -q(x)du
Since A is exactly the set which p(x) ((x) is non-negative, it is also clear that for any other
C X, we have:
2 / (p(x) ((x))dux 2 / p(x) ((x)du
1
(16)
Thus, we may write:
Drv DPv(P sup / p(x) q(x)d
BCX J
f ((x)(p(x) q(x)) (:X-
sup
(17)
sup Bx-r[D(s)]- -Ixx) D.X-(0.1)
This is exactly the variational lower bound which we have derived above. Hence, we have shown to be tight, even in the setting where P $ Q.
F.2 PGD-TV TRACKS SYNTHETIC DATA PERTURBATIONS
We now present perturbation experiments for the PGD-TV variant that are analogous to those shown Section 5.2.
We plot summary of the Spearman correlation of the metrics with perturbation magnitude in Fig. 6. Compared to Fig. we find that PGD-TV exhibits slightly lower correlations. Figs. 7 and show the response of PGD-TV perturbation over the entire and cropped magnitude range, respectively. For a more detailed explanation of this type of plot, we refer to Appendix H. From the plots we conclude that PGD-TV qualitatively exhibits the expected behavior of increasing with perturbation magnitude and eventually saturating. However, in some cases (e.g., edge addition on proteins), the PGD-TV flattens out, leading lower correlations.
Edge Delction
Edge
Swapping
Addition
1.00
1.00
1.00
0.75
0.50
Dag Aur
Spoc nar
clet Adr
Gel ReP
Rab
fiore ade Clust sar Ean AMP PDD
Orai RoP Spec AiF Chart Rae
cit ear
RSD
Rar
tas ear Soor RBF Curr Rer cis Agr
croncer Dee Rar Spee Aar
Cust roe
ow Par PiD
Figure 6: Spearman correlation of MMD metrics and PGD-TV with the magnitude of perturbation of datasets.
8

---

Published as a conference paper at ICLR 2026
Edge Deletion PGD 0.53
Edge Rewiring PGD 0.60
Edge Swapping PGD 0.21
Mixing PGD 1.00
Edge Addition PGD 0.24
1.00
0.75
PG0
0.50
Planar
0.25
0.70
PGD p 0.99
PGD p 1.00
PGD
Lobster
0.50
0.25
0.00
0.0
0.5
0.0
0.5
0.0
1.0 0.0
0.5
1.0
0.5
1.0
PGD 0.86
PGD pM 0.86
PGD p 0.89
PGD p 0.99
PGD 0.89
1.00-
0.75
Proteins
0.00
0.0
0.5
1.0
0.0
0.5
1.0 0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
PGD 0,79
PGD 0.77
PGD 0.62
PGD 1.00
PGD 0.04
2.00
0.75
0.50
MBB
1.0
1.0
0.57
PGD 0.87
PGD 0.90
PGD 0.99
PGD
0.75
RGP
0.50
0.25
0.00
0.0
0.5
0.5 Noise Level
1.0
1.0
Ncise Level
Noise Level
Noise Level
Noise Level
Metric
Orbit PGD
PGD
Clustering
PGD
PGD
Spectral
GIN
Figure 7: Behavior of descriptor-specifee and aggregated PGD-TV as data distributions are perturbed. The perturbation type varies across rows while dataset varies across columns. The Spearman correlation of the aggregate PGD and the perturbation level is denoted by p.

---

Published as a conference paper at ICLR 2026
Edge Deletion PGD 0.99
Edge Rewiring PGD 0.99
Edge Swapping PGD 1.00
Mixing PGD 1.00
Edge Addition PGD 1.00
1.00
0.75
PGD
0.50
Planar
0.25
p
PGD p
p 0.99
1.00
p 0.99
Lobster
0.50
0.25
0.00
0.00
0.05
0.10
0.0
0.1
0.2
0.0
0.5
1.0
0.0
0.5
1.0
0.00
0.05
0.10
PGD p= 0.99
PGD p = 0.98
PGD p 0.98
PGD p 0.99
PGD p 0.96
1.00
0.75
Proteins
0.00
0.00
0.05
0.10
0.5
0.00
0.02
0.04
0.06
0.00
0.02 0.04 0.06
0.0
0.5
1.0 0.000 0.025 0.050 0.075
PGD p= 1.00
PGD
1.00
PGD p 1.00
PGD 1.00
PGD 1.00
1.004
0.75
0.50
MBB
0.00
6.1
0.000 0.025 0.050 0.075
0.00
0.65
0.10
0.s
1.0 0.000
0.255 0.050 0.075
PGD
PGD
PGD 0.97
0.99
0.75
RGP
0.50
0.25
0.00
0.00
0.05
010
0.5
0.0
0.1
0.2
0.0
0.2
0.4
0.6
0.0
0.5
1.0
0.1
0.2
Noise Level
Noise Level
Noise Level
Noise Level
Noise Level
Metric
Orbit PGD
PGD
Clustering
PGD
PGD
Spectral
GIN
Figure 8: Behavior of descriptor-specife and aggregated PGD-TV as data distributions are perturbed. The perturbation type varies across rows, while the dataset varies across columns. The Spearman correlation of the aggregate PGD and the perturbation level is denoted by p.
10

---

Published as a conference paper at ICLR 2026
F.3 PGD-TV CORRELATES WITH MODEL QUALITY
Analogous to Section 5.3, we now investigate how the PGD-TV v correlates with proxy variables of model quality. In Fig. illustrate how PGD-TV behaves the number of denoising steps in DiGress is varied. As in Fig. 4, we find that PGD-TV correlates with validity in a highly linear fashion.
As in Section 5.3, we compute Pearson correlation coefficients between PGD-TV and validity. When varying the number denoising steps, find that PGD-TV exhibits a more linear relationship with validity than any of the MMD metrics.
Validity
PolyGraph Discrepancy
MMD
x10
x10
x10
x10
x10
1.0
1.0
2.0
Validity
0.8
6.0
2.4
1.6
0.6
0.6
4.5
1.8
0.4
0.4
2
3.0
0.8
0.0
0.0
1.5
0.6
0.4
90
90
30
Denoising Steps
Denoising Steps
Denoising Steps
Validity
Spectral RBF
PolyGraph Discrepancy
Degree
Figure 9: Behavior of validity, PGD-TV, and MMDs as the number of denoising steps in DiGress is varied on PLANAR-L.
We examine the behavior of PGD-TV throughout training in Fig. Qualitatively, clear positive relationship emerges between training duration and PGD-TV. This trend is confirmed quantitatively in Table where Spearman correlation coefficients show that most MMD metrics often exhibit weak or negative correlations, while PGD-TV consistently correlates positively with training duration. However, this correlation is weaker than that of PGD-JS (see Table 3) and the clustering- MMD metric. A similar pattern appears in Table 7 (bottom three rows): PGD-TV correlates reliably with validity, whereas most MMD metrics show inconsistent behavior. Nevertheless, in two out of three cases, the clustering- based MMD metric achieves stronger correlation with validity than PGD-TV.
Validity
PolyGraph Discrepancy
MMD
x10
X10
XIO
X10
X10-1
Planar-L
Validity
0.6
0.8
1.0
0 0.6
1.0
0.8
MMD-
0.8
1.2
3.0
4.2
3.6
5
7
4
6
0.6
1.2
0.8
0.6
0.8
1.0
0.2
0.4
2.4
0.4
0.4
0.0
0.0
F2
0.2
1500
3000
3000
x10=
x10-
XIO
X1O
x10
1.0
1.0
SBM-L
Validity
0.8
0.8
MMD*
2.5
1.28
1.20
0.8
0.4
0.4
1.5
-3
1.12
0.6
0.4
0.2
0.2
0.5
2
1.04
0.2
2
0.0
0.0
0.96
600
1200
600
1200
600
1200
x10-2
xI0=2
Lobster-L
Validity
1.0
1.0
M
2.5
3.0
2.4
1.6
1.5
6.0
0.6
0.6
MMO
1.8
1.2
0.9
4.5
0.4
0.4
1.0
1.2
0.6
330
0.2
0.2
0.5
0.6
0.4
0.0
0.0
0.0
0.0
0
400
800
400
800
400
800
# Epochs
Epochs
# Epochs
Validity PolyGraph Discrepancy
Orbit RBF
Spectral RBF
Gin RBF
Degree RBF
Clustering RBF
Figure 10: Behavior of validity, PGD-TV, and MMD metrics throughout training of DiGress on procedural graph datasets.
11

---

Published as a conference paper at ICLR 2026
Table 7: Negative Pearson correlation (T) of validity with other performance metrics. Denoising refers to the experiments in which we vary the number of denoising iterations. Training refers to the experiments in which we monitor performance metries during the training of DiGress models.
Dataset
TV-PGD
Orb. RBF
Deg. RBF
Eig. RBF
Clust. RBF
GIN RBF
Denoising
PLANAR-L
98.56
73.50
70.87
73.41
71.36
82.52
PLANAR-L
95.23
84.32
59.11
76,47
88.31
68.11
Training
SBM-L
85.56
53.22
6.59
23.49
85.07
6.85
LODSTER-L
70.49
-34.65
-35.17
-22.95
87.05
-30.55
Table 8: Sign-adjusted Spearman correlation (1) of validity, PGD-TV, and MMDs with number of training iterations DiGress.
Dataset
Val.
PGD
Orb. RBF
Deg. RBF
Eig. RBF
Clust. RBF
GIN RBF
PLANAR-I.
96.36
95.45
75.45
68.18
50.00
86.36
77.27
SBM-L
87.27
72.73
23.64
10.91
10.91
68.18
-24.55
LOBSTER-L
85.47
66.58
-7.35
-13.24
6.86
68.14
1.23
E44 COMPARISON OF PGD AND PGD-TV
Overall, the experiments in Appendices F.2 and F.3 have demonstrated that PGD-TV viable alternative to the PGD metric presented in the main paper, correlating to high degree with synthetic data perturbations and proxy variables of model quality. Nevertheless, we found that PGD exhibits stronger correlations and appears like more robust choice.
While we have no definite explanation for these observations, we hypothesize that the choice of binarization threshold in PGD-TV may introduce some noise into the estimate. Additionally, maxi- mum likelihood classifiers (like logistic regression) inherently maximize the log-likelihove objective of the IS divergence. Bayesian inference (approximated by TabPFN) may be expected to behave similarly in the large sample size limit (van der Vaart, 1998). However, neither maximum likelihood estimation nor Bayesian inference directly optimizes the variational objective of the TV distance, i.e., informedness. This can lead to misalignment when estimating the PGD-TV, potentially resulting looser variational bounds.
For these reasons, we recommend using the PGD variant presented in the main paper, estimating lower bounds on the
distance.
G SUPPLEMENTAL FOR: HIGH BIAS AND VARIANCE PLAGUE MMD-BASER GGM BENCHMARKS
Here, we show that the conclusions of Section 5.1 expand to all combinations of models, descriptors, and datasets, and provide additional experimental details. All MMD estimates provided here and in Figs. 2a and 2b are RBF MMDs, as proposed by Thompson et. (2022). The kernel is selected by tak- ing the maximum over the bandwidths {or:) (0.01, 0. 0.25, 0.5, 0.75, 1.0, 2.5, 5.0, 7.5, 10.0).
Specifically, we subsampled 8 to 4096 graphs 100 times with replacement from total of 8192 samples for the reference and generated graphs. We subsequently computed the median, 5th and 95th quantiles to estimate the variation of MMD. We computed such experiments for all model-generated samples we considered (ESGG, AutoGraph, DiGress and GRAN) and considered all descriptors (degree histogram, clustering histogram, orbit count for graphlet sizes and 5, and the graph Laplacian cigenvalues) and all procedural datasets (SBM, Lobster and Planar).
Based on those findings, introduce PLANAR-L, SBM-L, and LOBSTER-L, larger versions of the previously used datasets. Details for these new datasets are presented Appendix
12

---

Published as a conference paper at ICLR 2026
Spec.
Deg.
Lobster
20-2
10-1
10-1
10
10"
20-1
10
10a2
10-2
10-1-
10-1
10-4
10-4
10-4
10
10
10-1
10
10a
10a
10a
30-1
10-1
10-4
10-1
10a
HMD
10a2
10
10a2
10
10
256
250
1024
4030
3028
2096
236
1024
25g
Number of Graphs
Number of Graphs
Number of Graphs Number Graphs
Number of Graphs
Number of Graphs
Graph
Test Set
DiGress
Figure 11: Behavior of biased MMD estimates as the number of samples is varied DiGress.
Spec.
GIN
Deg.
0.3
0.2
Lobster
MHD
0.2
0.2
0.1
0.0
0.0
0.0
0.0
0.0
0.2
0.2
2
MMD
0.1
0.1
0.1
0.0
0.0
0.0
0.0
0.0
0.3
0.10
MMD
0.1
0.05
0.0
0.0
0
0.0
0.00
1034
Number of Graphs
Number of Graphs
Number of Graphs Number Graphs
Number of Graphs
Number of Graphs
Graph sources:
Test Set
-
DiGress
Figure 12: Behavior of unbiased MMD estimates as the number of samples varied for DiGress.
13

---

Published as a conference paper at ICLR 2026
Spec.
Deg.
Lobster
10-1
10:4
10-a
10-1
10*2
10-2
20-1
10-2
10a2
10
10*2
10-4
10-1
20-1
10.4
10-4
10-1
10.2
10
10
10a2
30-1
10-4
10-1
10a
10a2
10
10a2
10
10
256
256
1024
4030
3028
4098
256
1024
25g
Number of Graphs
Number of Graphs
Number of Graphs
Number Graphs
Number of Graphs
Number of Graphs
Test Set
AutoGraph
Figure 13: Behavior of biased MMD estimates as the number of samples is varied for AutoGraph.
Orbit
Spec.
GIN
Deg.
0.2
Lobster
0.2
MMD
0.1
0.0
0.0
0.0
0.0
0.0
3
0.15
0.30
Planar
MMD
0.2
2-
0.1
1.
0.05
0.0
0.0
0
0.0
0.00
0.00
0.3
0.3
0.2
0.10
MMD
0.2
0.1
0.2
0.0
0.0
0.0
0.00
1034
4038
Number of Graphs
Number of Graphs
Number of Graphs
Number Graphs
Number of Graphs
Number of Graphs
Graph
Test Set
- AutoGraph
Figure 14: Behavior unbiased MMD estimates the number of samples is varied for AutoGraph.
14

---

Published as a conference paper at ICLR 2026
Spec.
Deg.
109
109
Lobster
10:1
10-4-
10
10-2
10"4
10-1
10-4
10-1
10-1
10-1
10
10-2
10a²
10
10
30-1
10-1
10-1
10-1
10:4
10-2
10-2
10-1
10
10
10
256
256
258
1024
4030
3024
4098
236
1024
25g
Number of Graphs
Number of Graphs
Number of Graphs
Number Graphs
Number of Graphs
Number of Graphs
Graph
Test Set
GRAN
Figure 15: Behavior biased MMD estimates as number samples is varied for GRAN.
Spec.
GIN
Deg.
0.6
0.6
Lobster
MMD
0.4
0.2
0.2
0.2
0.0
0.0
0.0
0.0
0.0
0.2
0.2
0.3
Planar
MMD
0.1
0.05
0.05
0.0
0.0
0.0
0.00
0.00
0.3
0.2
0.15
MMD
0.
0.2
0.30
0.1
0.0
0.0
0
0.0
0.0
0.00
1034
Number of Graphs
Number of Graphs
Number of Graphs
Number Graphs
Number of Graphs
Number of Graphs
Graph sources:
Test Set
GRAN
Figure 16: Behavior of unbiased MMD estimates as the number of samples varied for GRAN.
15

---

Published as a conference paper at ICLR 2026
Spec.
Deg.
Lobster
10.-
10:
10-1
10-7
20"
10-4
10:4
10-4
10-1
10:1-
10:2
10
10
10a2
30-1
10
20
10-1
10-1
10-2
20-1
7
10a
10-2
10-1
10-1
10
256
250
1024
4030
3028
4098
236
1024
25g
Number of Graphs
Number of Graphs
Number of Graphs Number Graphs
Number of Graphs
Number of Graphs
Graph
Test Set
ESGG
Figure 17: Behavior of biased MMD estimates as the number of samples is varied for ESGG.
Spec.
GIN
Deg.
0.2
Lobster
0.4
MMD
0.2
0.2
0.1
0.1
0.0
0.0
0.0
0.0
0.0
0.3
0.2
2
MMD
0.05
0.05
0.0
0.0
0
0.0
0.00
0.00
0.15
MMD
0.10
0.05
0.05
0.0
0.0
0.00
0.0
0.00
0.00
1034
Number of Graphs
Number of Graphs
Number of Graphs
Number Graphs
Number of Graphs
Number of Graphs
Graph sources:
Test Set
ESGG
Figure 18: Behavior of unbiased MMD estimates as the number of samples varied for ESGG.
16

---

Published as a conference paper at ICLR 2026
H SUPPLEMENTAL FOR: PGD TRACKS SYNTHETIC DATA PERTURBATIONS
In this section, we provide further details for the experiments presented Section 5.2. In particular, we illustrate in more detail how PGD responds to perturbations and present results for the TV variant.
In Fig. 19, we illustrate how PGD (deseriptor-speecfic scores and the summary PGD) responds to various perturbations on different datasets. In this figure. illustrate the response over the whole range of magnitudes [O. 1]. As anticipated, the PGD saturates quickly as the support of the perturbed distribution becomes disjoint from the support of the true data distribution. We note that the PGD consistently responds in a monotonic fashion to the magnitude of perturbation.
Deletion
Edge Rewiring PGD 0.11
Swapping PGD p 0.07
Edge Addition
PGD p
PGD p 1.00
PGD p -0,08
1.00
0.75
Panar
0.50
0.25
0.00
0.0
0.5
1.0
0.0
0.5
6.0
0.5
1.0
0.0
0.5
1.0 0.0
0.5
1.0
PGD 0,91
PGD 0.95
PGD 0.99
PGD p 1.00
PGD 0.89
1.00
0.75
0.50
0.00
1.0
1.0
PGD 0.98
PGD 0.86
PGD 0.90
PGD 0.99
PGD 0.97
1.00
0.75
0.50
0.25
0.96
PGD p 0.92
PGD p 0.94
PGD p= 1.00
PGD p 0.39
2.00
P60
0.50
wBs
0.25
0.00
0.0
0.5
0.0
0.5
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
PGD 0,90
PGD p 0.98
PGD p 0.93
PGD p 0.99
PGD 0.98
1.00
0.75
063
0.25
0.00
0.0
0.5
1.0
0.0
0.5 Noise Level
1.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
Noise Level
Noise Level
Noise Level
Noise Level
Orbit PGD
Degree PGD
Clustering PGD
PGD
Orbit PGD
Spectral PED
GIN PED
Figure 19: Behavior of sepcrie and aggregated PGD (JS) as data distributions are per- turbed.
Based on the data from Fig. 19, we select a threshold for each combination of perturbation type and dataset which the summary PGD saturates above 0.95. We illustrate the behavior of PGD-JS on these cropped ranges in Fig. 20.
We find that there is no single descriptor that consistently provides the tightest PGD estimate. This highlights the importance of evaluating many different descriptors when computing PGD.
17

---

Published as a conference paper at ICLR 2026
Edge Deletion PGD 0.99
Edge Rewiring PGD 0.99
Edge Swapping PGD 1.00
Mixing
Edge Addition PGD 1.00
PGD 1.00
1.00
0.75
PGD
0.50
Planar
0.25
p
PGD p
PGD p 0.99
1.00
p
Lobster
0.50
0.25
0.00
0.00
0.05
0.10
0.0
0.1
0.2
0.0
0.5
1.0
0.0
0.5
1.0
0.00
0.05
0.10
PGD p= 1.00
PGD 0.99
PGD p 0.98
PGD p 0.99
PGD p 0.98
1.00-
0.75
Proteins
0.00
0.00
0.05
0.10
0.5
0.00
0.02
0.04
0.66
0.00 0.02 0.04 0.06
0.0
0.5
1.0 0.000 0.025 0.050 0.075
PGD p= 1.00
PGD
1.00
PGD p 1.00
PGD 1.00
PGD 1.00
1.004
0.75
PGD
0.50
0.00
6.1
0.000 0.025 0.050 0.675
0.00
0.05
0.10
0.5
1.0 0.000 0.25 0.050 0.075
PGD
PGD 0.98
0.99
0.75
0.50
0.25
0.00
0.00
0.05
010
0.5
0.0
0.1
0.2
0.0
0.2
0.4
0.6
0.0
0.5
1.0
0.2
Noise Level
Noise Level
Noise Level
Noise Level
Noise Level
Metric
Orbit PGD
PGD
Clustering
PGD
PGD
Spectral
GIN
Figure 20: Behavior of descriptor-specife and aggregated PGD (JS) data distributions are per- turbed. The perturbation type varies across rows, while the dataset varies across columns. The Spearman correlation of the aggregate PGD and the perturbation level is denoted by p.
18

---

Published as a conference paper at ICLR 2026
I SUPPLEMENTAL FOR: PGD CORRELATES WITH MODEL QUALITY
In this section, we provide further details for the experiments presented in Section 5.3.
In Table provide the exact MMD metrics attained by DiGress the number of denoising iterations is varied. Analogously, we provide the values of the PGD and descriptor-specific subscores in Table 10. We find that orbit counts appear be the most discriminative descriptors, they lead to the highest PGD values.
Table 9: Behavior of RBF-based MMD metrics as the number of denoising steps in DiGress is varied. separate model is trained for each row for 5k epochs on PLANAR-L.
Steps
Orb. RBF
Deg. RBF
Eig. RBF
Clust. RBF
GIN RBF
15
0.6489
0.0748
0.0301
0.4722
0,2027
30
0,1892
0.0281
0,0088
0.1181
0.0939
45
0.0925
0.0212
0.0047
0.0566
0.0636
60
0,0686
0.0162
0,0031
0.0363
0,0451
75
0.0511
0.0182
0.0026
0.0331
0.0338
90
0.0435
0.0162
0.0022
0.0246
0.0308
Table 10: Behavior of PGD as the number of denoising steps in DiGress is varied. A separate model is trained for each row for 5k epochs on PLANAR-L.
Steps
VUN
PGD
Orb.
Orb5.
Deg.
Eig.
Clust.
GIN
15
0.00
100.00
100.00
100.00
69.92
98.87
99.97
79.19
30
4.05
97.04
96.90
97.04
45.37
79.25
90.65
56.17
45
18.70
91.81
90.07
91.81
33.88
63.69
77.58
43.13
60
30.76
84.25
81.78
84.25
28.60
49.20
70.06
37.42
75
44.09
74.62
72.74
74.62
32.15
43.23
59.21
37.58
90
51.27
69.30
66.47
69.30
27.72
38.26
51.35
33.51
In Fig. 21, supplement the experiments presented previously in Fig. 5 with the corresponding results on PLANAR-L and LOBSTER-L.
19

---

Published as a conference paper at ICLR 2026
Validity
PolyGraph Discrepancy
MMD
x10
X10
X1O
XIO
X10
Planar-L
Validity
0.6
0.8
0.6
0.8
1.0
MMD
1.0
4.8
4.2
3.6
5
6
7
1.2
1.0
0.8
1.0
0.8
0.4
&. 0.4
0.6
0.6
0.2
0.2
2.4
0.4
0.4
1.8
0.2
1500
3000
1500
3000
1500
3000
x10
x10
x10
x1O
x10
1.0
1.0
SBM-L
Validity
0.6
0.8
1
0.6
0.8
MMD
2.0
2.5
L.5
1.12
1.28
1.20
1.0
0.6
-5
1.0
0.4
1.04
0.0
0.0
0.96
1200
1200
600
1200
x10-2
x10-2
X10-
X1O-
X10
Lobster-L
Validity
0.6
0.8
1.0
08 0.6
0.8
1.0
MMD
m
2.0
2.5
3.0
1.8
2.4
2.0
1.2
1.5
1.2
4.5
6.0
1.2
0.8
0.6
3.0
0.2
0.2
0.5
0.6
0.3
0.0
0.0
0.0
0.0
1.5
800
400
400
800
# Epachs
Epachs
Epochs
validity
Orbit RBF
Spectral RBF
RBF
PolyGraph Discrepancy
Degree RBF
Clustering RBF
Figure 21: Behavior of validity, PGD, and MMD metrics throughout training DiGress on proce-
dural datasets.
J ABLATION: TABPFN vs LOGISTIC REGRESSION
In this section, we study logistic regression as an alternative to TabPEN as a discriminator. To this end, repeat the perturbation experiments from Section 5.2 and Appendix H with logistic regression as a discriminator. We refer to the PGD variant using logistic regression LR PGD.
In Fig. 22 we plot the response of PGD and LR PGD to synthetic perturbations. We find that TabPFN consistently produces PGD estimates that are at least as high as those obtained by logistic regression. In some cases, TabPFN clearly outperforms logistic regression. This may attributed to the fact that TabPFN can model non-linear decision boundaries and is thus more powerful than logistic regression. We also qualitatively observe that logistic regression leads a noisier response to the variation of perturbation magnitude.
Hence, since TabPFN simultaneously produces tighter bounds and less noisy estimates, we prefer to logistic regression.
K SUPPLEMENTAL FOR: BENCHMARKING REPRESENTATIVE MODELS
In this Appendix, we do a thorough benchmark of PGD and MMD on LOBSTER-L, PLANAR-L, SBM-L and Proteins. To obtain the standard deviations for PGD scores and MMD values in Tables 4 and to 13, we subsample half of the dataset without replacement (2048 samples for procedural datasets, and 92 samples for proteins) 10 times. In all those tables, means and standard deviations are scaled by factor of 100 for legibility purposes. The time taken to compute each of those metrics is reported in Table 15. Timing experiments were run on a compute node equipped with two AMD EPYC 9534 CPUs (using 10 vCPUs in total), NVIDIA H100 GPU with 80 GB memory (CUDA 12.2, driver 535.230.02. 22,,233, and 128 GB system RAM. Reference values (i.e. the score obtained by computing the metric between the train and test set) for all metries discussed that the PGD discrepancy between the train and test set of MOSES is relatively high, as the test set consists of separate scaffold split. Importantly, the PGD between the train and test set very close to 0 (save for MOSES due to changes in the underlying distribution), further showing the absolute nature of PGD, making it much easier interpret compared to MMD.
in Tables 16 and 17. We note
20

---

Published as a conference paper at ICLR 2026
Edge Deletion
Edge Rewiring
Edge Swapping
Miking
Edge Addition
160
0.6
Panar
0.4
0.2
0.00
0.01
0.02
0.03
0.00
0.01
0.02
0.03
0.00
0.02
0.04
0.0
0.5
1.0
0.00
0.00
0.02
0.03
2.0
0.8
Lobster
0.0
0.05
PGD
0.6-
Proteins
0.4
0.00
0.05
0.10
0.15
0.00
0.02
0.04
0.06
0.00
0.02
0.04
0.68
0.0
0.5
1.0
0.000 0.025 0.050
0.075
1.0
with tonn 2000
Frend wwiggeea
R5D
SaN
0.2
0.0
0.2
0.000
0.050 0.075
0.06
0.10
0.0
0.000 0.025 0,050 0.075
0.8
by sunn te
0.6
063
0.4
0.00
0.05
0.10
0.15
0.0
0.1
0.2
0.3
0.2
0.4
0.6
0.0
0.5
1.0
0.0
0.1
0.2
Noise Level
Noise Level
Noise Level
Noise Level
Noise Level
UR KGD
TARPFN PGD
Figure 22: Comparing the behavior of the aggregated PGD (JS) computed via logistic regression (LR PGD) to the aggregated PGD computed via a TabPFN classifier (PGD).
21

---

Published as a conference paper at ICLR 2026
Comparison of VUN and PGD with biased Gaussian TV-based MMD formulations from Liao et al. (2019). We computed the standard deviation from 10 subsamples of size 2048 except for Proteins, where the subsample size is 92 (50% of the size of the test set). All MMD hyperparameter
Table 11:
choices are specified in table 14.
Datasel
Model
CUN
PGD (1)
GTV MMD Deg. ()
CTV MMD Clust. (1)
GTV MMD Orb (
GTV MMD- Fip.. ())
PLANARAL
AutoCaraph
33,451 11332
6,5416-05
2.113-005
2.239c-08 63
4.57--04
1.219t- 44 5550--05
9.8946-04 a 7:300-15
DiClenss
45.391 11:00
5,521e-04
1.504e-02
1.55--00
3.781c-03
1.365--01 a mi
GRAN
99.257 siee
7,046e-05
4,876e
5.324e 01
1,332e
ESGG
45.012 1:393
18966-4S
1.944-05
5.787e
50000-00
1.333e 2.3322--00
8.016e-44 #.335
LousTEeL
AutuGraph
16,415 11:00
3.400c:01
1.200e-
5.235e
1.49--48
DiGruss
3,924 2.30
5,1686-05
1.525e-06
Sittte--r
3.385e-04
:: 111lie-u
2.171e-44 2:3.59 db
GRAN
1.179e002
2 2..022--
3.275c-03
03
4.500004
1.905c-00
2.333e-002
FSGG
69.881 +-4.94
6.423c-03
195--0
0.00
1 (0ae00)
6.474c-02 + 5-74--0
1.0644-02 + 1.900--
SBM-L
AutoGraph
1.396c-04 : 7.412e-05
2,000e 03 1.215e
1.893e400 43 2.999---
2.500e444 2:1.135 4s
DiCienas
16,09 1:751
7.3022-04
2-200-0
2,152-03
3. 3.1015-001
1,204-044
GRAN
9.831c003
4:2222--
3.9% 03
1.392e402
L251c-01
ESGG
3,442c-03
0:110-04
4.54
2.765x-02
Proteims
AutuGraph
55,308
3.936c-03
1.23e-ts
5.877e-02
2.460x-00
4.824e-03 29.300--0
DiClenas
36788 4:2000
6.364e-04
5.006e-02
1.610-007
2.8077-433
GRAN
36.062 27:22
3,525c-00 02
1,425e
01 1147--00
3.239e 01 26
1.19He 02 # 1.82 48
ESGG
77.764 2:10
2.50He-01
a 1.005--05
8.180e-02 02= 1.219-400
1.3822-80
a 29.423--41
3.543e-003
a 7.3//4--4
Table 12: Unbiased RBF kernel-based MMD estimates. We computed the standard deviation from 10 subsamples of size 2048 except for Proteins, where the subsample size is 92 (50% of the size of the test set). All MMD hyperparameter choices are specified in table 14.
Dataset
Model
UMVE Deg. (L)
UMVE Clust. ())
UMVE Orb. ())
UMVE Fig. (
PLANAR-L
AutoGraph
1.582e-03 + 7.653v-44
5.774e-04 3.84
2.539e-03
1.3276-00
1.086c-03 03 + 8,244
DIGRESS
1446c-02 a: 1.002-11
1.418c-02
2.011e-00
3.373c-02 5.418-000
1.668c-03
1.676e-00
GRAN
7.801c-03
814
7.889c-03 1.033e-04
8.947c-03
7.59
7.807c-03 95.350
ESGG
1.607-03 1.006x-04
4.901e-03
1.100-03
3.055e-02
147.147--00
8.361e-04
1.417e-004
LOBSTER-L
AutoGraph
6.481c-03
1.049
4,949c-05
3.900-
7.372c-03
2.547e--0
7.146c-03
1.919e--0
DIGRESS
5,082c-44 : 4.
5,340c-06
3.790e--0
7.115c-00
:: 6.26%--0
2.744c-04
2: 4.0776e-00
GRAN
3.032c-01 i: 91
7.566c-03 1.163e-03
1.608c-01
7.665e-03
2.356c-01
3.755
ESGG
8.858e-02
0.995--00
0.000c+00
0.000c++00
2.242c-01
1.451e-02
6.965c-02
5.450e-00
SBM-L
AutoGraph
5.239c-444
4.515c-u4
4.474c-04
2.889e00
6.822e-04
0.766e-04
18665e-04
8.5
DIGRESS
3.763e-03 1.100e-0
1,911e-03
4.720=004
4.264c-03
1.646e-03
2.368c-04
6.20ke-00
GRAN
5.071c-02 # 2.711e-0
4,454c-02
= 1.38te-05
1.575c-02
2: 5,07l-003
4.043c-03
ESGG
3.196c-02 + 20
5.450e-02
03
8.004e-02
0.063-00
4.765e-02
+ 8.56
Proteins
AutoGraph
1888e-02 :: 6.
3.906e-02 02
1.135e-02
005
1.544c-02 3.011c--0
DIGRESS
1.718c-412 10
1.740c-02 033
3.312e-02 2.090-002
1.601e003 1.711e-00
GRAN
3 3.440e-01 = 8.555e-0
2.642e-01 4.05ee-02
3,983e-01
8.373-002
5,004e-02
=1.00ee002
ESGG
8.358e-02 + m.
8.125e-02
2.79
4.607e-02 -07
4.234e-03 +1.44%-03
Table 13: Biased RBF kernel-based MMD estimates. We computed the standard deviation from 10
subsamples of size 2048 except for Proteins, where the subsample size is 92 (50% of the size of the test set). All MMD hyperparameter choices are specified in table 14.
Datasel
Model
RBF Deg, (L)
RBF Clust. (L)
RBF Orb. (L)
RBF Eig, (L)
PLANAR-L
AutoGraph
2.943c-03
7.042c-04
2.139c-03 2.93ee00
3.915e-03 1.179c-03
2.509c-03
6.13e-05
DiGRuss
1.528e-02 + 1.802e00
1.520e-02 -3000-03
3.475e-02 + 5.50e-00
2,946e-(33
1.25%-044
GRAN
9.743e-03 + 8.800e08
9.833e-03
= 1.032e-04
1.079e-02
63166-00
9.752c-03
= 9,333e--05
ESGG
3.152e-03 6.404--04
5.962e-033 100
3.160e-02
197-
2.316e-03 1.045e004
LOBSTER-L
AutoGraph
7.492c-03
2.000
6.176c-05
8.1022-03
2.507
8.110c-03 1.915e-00
DiGRess
2.121e-433 + 1:61
1.042e-055
-5
2.302e-033
+ 5.577-0-
2.030e--03 -0
GRAN
3.043c-01 1: 11
7.728c-03
= 1.1
1.619c-01
a: 7.
2.368c-01 4:3.5le--
ESGG
8.945e-02 +: 5.056x-
0.000e+00
+: 0.000+000
2.249c-01
1.4
7.052e-02 5..446
SBM-L
AutoGraph
2.174e-03 a: 24
2.114e-03
144
2.345e-03
6.156e
1.979c-03
2.045e
DIGRESS
4.814c-03
1.055--11
3,091c-03 4.050
5.155c-03
1.641a-00
1.959e-03
6.636v
GRAN
5.168c-02 2.770e-u
4,556c-02 05
3.685c-02
1 5.084e-00
5.610c-03
5.36kc--0
ESGG
3.347c-02 a: 13
5.608c-02 2.254e
8.1 8.034e-00
4.926c-02
a 8.573e
Proteins
AutoGraph
5.178c-02 = 7.611e-1
6.716c-02 = 1.57te-u2
2.369e-02 2: 4.44922
5.063c-02 2 4.687-003
DIGRESS
5.236c-02 a: 1149
5.146e-02
6.23te--05
6.808c-02 a 02
4.360e-02 a -009
GRAN
3.652e-01
8.576e-02
2.913c-01
3.995-002
4.156e-01
5.41l-022
7.697c-02
1.011e-02
ESGG
1.130c-01
2.740l--12
1.098c-01
2.652e-02
8.222c-02
2-51e-00
4.360c-02
1.778e-02
22

---

Published as a conference paper at ICLR 2026
Table 14: Mapping of display columns results tables MMD configurations, For all RBF MMDs, the final MMD was computed as the maximum value over the following bandwidths {or (.51, 1.0, 2.0, 5.0, 10.0} as per Thompson et al. (2022). For the descriptor parameters, we used 100,000 for the width of the sparse degree histogram, 100 bins for the clustering histogram, and for the orbit count. RBF: radial basis function; GTV: Gaussian total variation distance; UMVE: unbiased minimum variance estimator, see Gretton et al. (2012).
Name
Variant
Kernel
Descriptor
Name
Parameter
GTV MMD Deg.
1.0
Degree
GTV MMD
Clust.
Biased
GTV
0.1
Clustering
GTV MMD
Orb.
30
Orbit
GTV MMD Eig.
1.0
Eigenvalues
RBF MMD Deg.
Degree
RBF MMD Clust.
Clustering
UMVE
RBF
{o1)
RBF MMD Orb.
Orbit
RBF MMD Eig.
Eigenvalues
RBF MMD 2 Deg.
Degree
RBF 2MD Clust. Biased
Clustering
RBF
{or))
RBF 2MD Orb.
Orbit
RBF MMD
Eig.
Eigenvalues
Table 15: Compute time (s) per metric across datasets. Standard deviations obtained from the metries computed on different model samples. Caching of intermediate or reused MMD values in PolyGraph help make MMD computations substantially faster. Int. indicates whether the metric yields an interval through subsampling. VUN scores were parallelized across 10 CPUs.
Metric
Int.
PLANAR-L
LousEEe-
SBM-L
Proteins
Overall
VUN
x
425.60 17.72
253.32 8.95
1181.26 101.98
620.06 37.98
PGD
73.64
3.01
338.82 190.27
125.02 17.77
140.35 73.67
169.46 52.81
PGD
14.27 192.13
696.11 367.93
280.98 47.45
223.67 = 111.39
348.22 118.35
RBF MMD Deg.
12.61 = 0.33
12.38 = 0.14
12.72 = 0.27
3.68 0.59
10.35 0.23
Biased RBF MMD2 Deg.
10.50
GTV MMD
7.74 1.22
8.21
8.46 2.54
3.26 0.40
6.88 0.78
GTV MMD' Deg.
0.25
3.32
3.83 0.39
3.51 a 0.70
3.60 a 0.21
RBF MMD Clust.
16.23 + 0.46
13.69
22.63 + 1.61
16.48 + 8.16
17.26 + 1,86
Biased RBF MMD Clust.
16.60 0.50
1.20
25.60 +
16.73 8.25
18.23 + 2.26
MMD Clust.
11.80
0.13
16.75 +
13.24 1.93
GTV MMD' Clust.
7.06
0.14
12,90 2.09
14.27
10.08
RBF MMD Orb.
11.87 0.20
1.38
14,58 1 0.62
4.84 2.64
10.78 0.66
Biased RBF MMD Orb.
11.82
0.36
14.64 0,52 0,52
4.75 2.69
10,79 0.70
GTV 2MD Orb.
5.75
5.85 0
6.71 + 1.31
3.73 2.13
5.51 + 0.56
GTV MMD*
1.02
1.22
2.73
2.12
2.32 0.50
RBF MMD Eig.
0.83
2.71
25.83
Biased RBF MMD" Eig.
25.16 6.52
1..75
25.86 + 1.84
=1.1116.31
25,72 2.80
GTV MMD Fig.
17.85 1.18
0..5
20.77 + 1.83
29.67 + 17.44
21,46 4.21
GTV MMD Fig.
X
13.80 + 0.09
1292 0.16
16.88 + 1.56
32.26 + 19.52
18.97 4.82
23

---

Published as a conference paper at ICLR 2026
Table 16: Reference values between the test and training set for various metrics.
Metric
PLANAR-L
LOBSTER-L
SBM-L
Proteins
PGD (L)
0.2 0.6
0.0 0.0
0.4 +.888
1.6 2.7
Clust. (1)
0.5 0.9
0,0 0.0
0.7 1.5
3.4 4.9
Deg. (L)
0.3 0.7
0,4 0.6
1.2 +
2.4 2
GIN (1)
0.2 0.6
0.2 0.3
0.9 #.9
3.6
Orb5. (U)
0.3
0.2
0.4 4.9.
2.2
Orb4. (U)
0,5 0.8
0,2 0.4
1.0 1.2
2.0
Eig. (
0.4 0.7
1.0
0.3 0.0.8
1.0
GTV MMD Clust. (L)
2.91e-04
0.00e+00
4.87c-04
0.0068
GTV MMD Clust. ())
5.87c-04 + 1.3e 04
0.00e+00
= 0.00.00
9.69c-04 # 9.4e 06
0.0104 + 9.4e-- 04
RBF MMD Clust.
3.44e-05 5.te
0.00c+00
0.0e
1.62e-06
0.0014
RBF MMD Clust. (U)
5.34e-04 1.5c-14
0.00c+00
+ 0.0c+00
6. 00e-40
+ 2.6e-05
0.0077 0.0020
GTV MMD Deg. (D
1.51e-05
1.79e-05
1.69e-05
3.16c-04
GTV MMD Deg. (L)
2.14c-05
1.1e-05
3.06e-05
0.3
3.86c-05 +: 2.4e-05
5,67e-04 4.6e-04
RBF MMD Deg. (L)
1.69c-04 + 1.7e 04
1.19c-04 + 1.2e-0e 04
1.48e-04 = 1.2e 04
0.0052 + 0.0038
RBF MMD Deg. (L)
6.38e-04
2.7e-04
6.03e-04
2.0e-04
8.54c-04 1.3e-14
0.0117 0.0039
GTV MMD Orb. (L)
3,43e-06
1.36e-05
3.26e-04
0.0032
GTV 2MD Orb. (L)
2.18c-05
+ 2.1-00
5.79c-05
+ 2.8e-05
8.79c-04 + 2.1e-04
0,0065 0.0042
RBF MMD Orb. ())
1.0Se-04 9.8e-0
3.41e-04
2.8c-04
2.98c-05
0.0044 0.0055
RBF MMD Orb. (L)
0,0010 + 3.3e-05
0,0012 + 2.3e-04
9.99e-04
# 3.44-05
0.0132 = 0.0038
GTV MMD Eig. (L)
7.39c-05
5.12c-05
4.93c-05
4.85c-04
GTV MMD Eig. (L)
1.27e-04 2.5
1.10e-04
2.6e-05
9.75e-05 + 1.9e-05
6.97e-04 + 1.1e-04
RBF MMD Eig. (L)
1.69c-05 2.9e-05
2.78c-05
4.0e-05
5.21c-06 # M.7. 9.7e-06
c-14 # 2.1e-1H
RBF 2MD Eig. (L)
5.80e-04 5.0
6.43e-04
1.0e-04
4.02e-04
3.
0.0024
Table 17: Reference PGD metries between the molecule test and training sets. Note that MOSES scaffold split, resulting in high discrepancy between the train and test set.
Dataset
PGD subscores
PGD (L)
Topo (l)
Morgan (L)
ChemNet (l)
MolCLR ())
Lipinski (J)
GUACAMOL.
0.2 +
0.2 0.4
0.3 = 0.5
0.3 0.6
0.1 0
0.0
MOSES
21.0 + 0.6
21.0 + 0.6
17.8 + 0.7
16.0 + 1.2
18.0 + 0.8
20.7 + 0.7
24

---

Published as a conference paper at ICLR 2026
L STABILITY OF PGD UNDER VARYING SAMPLE SIZES.
Figs. 23 to 26 show the relationship between the PGD score and the number of samples. The PGD score of the reference graphs with respect to another set of reference graphs issued from the same distribution is given as a comparison. For all experiments, we show the mean as well as the 5th and 95th quantile to give an estimate of the variance of PGD at different sample sizes.
For most models, some separation from the test set occurs above 256 samples, with PGD scores, and especially the upper bound is mostly stable beyond this range. This both showeases the stability of the metric, the number of samples required to get reliable PGD estimate, as well as the overall PGD ranges for the various models we considered for this study.
1.0- PGD
Orbit FGD
Orbit-5 FGD
Spectral PGD
GIN PGD
Degree PGD
Clustering PGD
Labster
PGD
0.5
0.0
1.0-
Planar
PGD
0.0
1.0-
SBM
PGD
0.0
1024
4096
256
1024
3096
1024
4096
250
1024
2096
236
1024
4006
1024
2024
Number of Graphs Number Graphs
Number of Graphs
Number Graphs
Number Graphs
Number of Graphs Number Graphs
Graph Sources:
AutoGraph
Test baseline
Figure 23: PGD obtained from varying sample sizes generated by AutoGraph.
25

---

Published as a conference paper at ICLR 2026
Orbit Orbit-5
GIN PGD
Degree PGD
Clustering
1.0
Labster
0.5
1.0
Planar
PGD
0.5
SBM
PGD
0.5
255
1024
4096
2095
256
3024
2006
296
1024
4096
256
1024
4086
3024
4096
2006
Number of Graphs Number Graphs Number of Graphs Number of Graphs Number of Graphs Number of Graphs Number of Graphs
DiGress
Test baseline
Figure 24: PGD obtained from varying sample sizes generated by DIGRESS.
Orbit Orbit-S
Spectral
GIN FGD
Degree FGD
Clustering PGD
1.0
Labster
PGD
0.5
Planar
PGD
0.5
1.0-
SBM
PGD
0.5
3024
2096
2095
3024
3024
4096
2056
3024
Number of Graphs Number Graphs Number of Graphs Number of Graphs Number of Graphs
Number of Graphs Number of Grophs
GRAN
baseline
Figure 25: PGD obtained from varying sample sizes generated by GRAN.
26

---

Published as a conference paper at ICLR 2026
Orbit Orbit-5 Spectral
GIN
Degree
Clustering
1.0
Labxter
PGD
0.5
1.0
Planer
PGD
0.5
SBM
P3D
0.3-
1024
2096
3024
256
1024
4096
Number of Graphs Number of Graphs Number of Graphs Number of Graphs Number of Graphs Number of Graphs Number of Graphs
Graph
ESGG
Test baseline
Figure 26: PGD obtained from varying sample sizes generated by ESGG.
27

---

Published as a conference paper at ICLR 2026
M LARGER PROCEDURAL REFERENCE DATASETS FOR BETTER GGM BENCHMARKING
Following findings of Section 5.1 and Appendix G, introduce larger proceduraally-genraaeed datasets for planar, lobster and SBM graphs, which we term PLANAR-L, LOBSTER-L and SBM-L. LOBSTER-L set of tree-shaped lobster graphs generated using nx. _random_lbbster, by expected node count (80) and attachment probabilities to the backbone and its neighbors (set to 0.7 for both). PLANAR-L positions in the unit square and forming the Delaunay triangulation via scipy spatial DDllauna,, yielding planar edge sets from triangle simplices. SBM-L a set stochastic block model graphs with the number of communities sampled uniformly from 2 to 5 and nodes per community from 20 to 40, where edges are drawn with intra-conma community probability 0.3 and communit probability 0.005. SBM-L, PLANAR-L, and LOBSTER-L datasets follow networkx's s BSD-3 license.
lobster, controlled
of connected planar graphs generated by uniformly sampling 64 node
Table 18: Dataset sizes (number of graphs) per split.
Dataset
Train
Val
Test
SBM-L
8192
4096
4096
PLANAR-I.
8192
4096
4096
LOBSTER-L
8192
4096
4096
N INFLUENCE OF TRAINING SET SIZE ON AUTOGRAPH
As shown in Fig. 27, AutoGraph converges similar VUN values across datasets, yet the loss is substantially lower for SBM-L after training than for SBM-S. This finding indicates that models may overfit on the existing small procedural datasets, further drawing into question the validity of previously reported evaluation results (Vignac et al., 2023).
Validation loss vs VUN
30
TWW85
BMMS
T
VUN
0.7
Time Step
Time Step
15
15
0.6
SBM-5
5
1.44
1.46
1.48
1.50
1.52
Validation
Figure 27: VUN vs. Loss for AutoGraph over the course of a training run.
COMMON SHORTFALLS OF EXISTING SOLUTIONS
To address the lack of inherent scale in MMD, some have proposed normalizing the MMD between generated and test graphs by the MMD between train and test graphs (Martinkus al., 2022).
However, this approach has several shortcomings:
Limited theoretical justification MMD was originally introduced as a kernel two-sample test. Its performance metric or for p-value computation remains
manipulation beyond direct poorly understood.
Lack of compusability The MMD ratio does not enable combining information across multiple descriptors.
28

---

Published as a conference paper at ICLR 2026
Sample-size sensitivity shown in Appendix G, MMD strongly depends sample size. Dividing MMDs computed on different sample sizes produces ratios with unclear or unreliable interpretation.
P DATASET DETAILS
Here, we provide details about the datasets used this study. Licenses for those datasets are summarized in Table 19. Table 20 shows the dataset statistics of the Citeseer dataset (Sen et al., 2008). The statistics for the small procedural datasets are presented Table (Planar), Table 22 (SBM), and Table 23 (Lobster).
Table 19: License and author information of the datasets used in our experiments.
Dataset
Author
License
Citeseer
(Sen al., 2008)
CC BY-NC-SA 3.0 BSD-3
Procedural (Planar, SBM, Lobster)
(Martinkus et al., 2022; Hagberg al., 2008) (Dobson & Doig, 2003)
Proteins
CCO 1.0 Universal
Table 20; Ego dataset statisties (extracted from Citeseer).
Metric
Train
Val
Test
Number of Graphs
454
151
152
Minimum number of Nodes
50
50
50
Maximum number of Nodes
399
333
364
Average number of Nodes
141.72
139.29
158.08
Minimum number of Edges
64
56
63
Maximum number of Edges
1066
898
1004
Average number of Edges
325.16
321.87
369.30
Edge/Node Ratio
2.29
2.31
2.34
Table 21: Dataset statistics for the Planar dataset (train, validation, and test splits).
Metric
Train
Validation
Test
Number of Graphs
128
32
40
Minimum Number of Nodes
64
64
64
Maximum Number of Nodes
64
64
64
Average Number of Nodes
64.00
64.00
64.00
Minimum Number Edges
173
174
174
Maximum Number of Edges
181
181
181
Average Number of Edges
177.83
177.75
177.93
Edge-to-Node Ratio
2.78
2.78
2.78
FEATURE CONCATENATION AS AN ALTERNATIVE TO MAX-REDUCTION
An alternative to taking the maximum JSD across descriptors consists of obtaining an overall PGD score by concatenating all vectors arising from the different descriptors, and training a discriminator atop these concatenated features. This makes attributing potentially high values to specific descriptors impossible, but in practice still results in a tighter bound (i.c., higher scores) as can be seen in Tabble 24.
29

---

Published as a conference paper at ICLR 2026
Table 22: Dataset statistics for the SBM dataset (train, validation, and test splits).
Metric
Train
Validation
Test
Number of Graphs
128
32
40
Minimum Number of Nodes
44
49
54
Maximum Number of Nodes
187
162
174
Average Number Nodes
105.99
91.28
107.85
Minimum Number of Edges
129
183
210
Maximum Number of Edges
1129
857
972
Average Number of Edges
512.51
425.19
521.88
Edge-to-Node Ratio
4.84
4.66
4.84
Table 23: Dataset statistics for the Lobster dataset (train, validation, and test splits).
Metric
Train
Validation
Test
Number of Graphs
60
20
20
Minimum Number of Nodes
10
14
Maximum Number of Nodes
98
98
84
Average Number Nodes
53.67
56.30
50.80
Minimum Number of Edges
10
13
Maximum Number of Edges
97
97
83
Average Number of Edges
52.67
55.30
49.80
Edge-to-Node Ratio
0.98
0.98
0.98
R KERNEL, LOGISTIC REGRESSION WITH GRAPH KERNELS
One adopt the kernel logistic regression classifier and use graph kernels directly to evaluate GGMs, effectively showing that any (graph) kernel also suitable for MMD can also be used in PGD. We showcase this with the Weisfeiler--eehman (Shervashidze et al., 201 2011), shortest path (Borgwardt. & Kriegel, 2005), and PyramidMatch (Grauman & Darrell, 2007) graph kernels in Table 25. However, they almost always show looser bounds compared to the standard PGD formulation, so we do favor such kernels.
S
USE OF LARGE LANGUAGE MODELS
The authors used large language models in the following ways:
Intelligent tab completion During software development, tools for intelligent line-wise tab com- pletion were used.
Preparation of visualizations LLMs were partly used to generate code for figure layouts. The correctness of code and data was checked manually. The data shown in the figures was generated by manually written code.
Information retrieval LLMs were queried for related work, but produced no relevant results. All related work presented in the manuscript was manually retrieved, save for Endres & Schin- delin (2003), which was manually checked to contain the required proof.
Polishing of manuscript LLMs were occasionally used to refine or rephrase individual sentences.
30

---

Published as a conference paper at ICLR 2026
Comparison VUN, max-reduced PGD (the default we also use in Table 4) and PGD with concatenated descriptors. PGD-Concat. is obtained by concatenating all descriptor features and training a single discriminator on the combined representation. The final score obtained similarly to PGD.
Table 24:
Dataset
Model
VUN (1)
PGD (L)
PGD-Concat. ())
PLANAR-L
AutoGraph
85.7
34.1 1.7
46.2 2.1
DIGRESS
79.6
46.7 1.7
55.7 t 1.9
GRAN
3.1
99.5 0.5
99.3
ESGG
93.9
4.1
53.7 + 1.6
LOBSTER-L
AutoGraph
82.6
16.6 1.4
34.7 + 1.4
DIGRESS
91.8
4.0 3.1
47.6 +: 1.0
GRAN
42.9
86.0 0.7
86.3 0.5
ESGG
70.9
70.6 + 0.6
71.0 + 1.1
SBM-L
AutoGraph
87.1
7.1 + 1.4
29.1 + 1.6
DIGRESS
74.1
16.6 1.9
33.2 2.5
GRAN
22.3
69.1 1.11
78. 1
ESGG
11.0
99.3 + 0.3
98.2 0.5
Proteins
AutoGraph
57.3 + 11.5
81.6 5.7
DIGRESS
86.7 2.4
97.7 0.9
GRAN
88.9 + 5.5
98.7 008
ESGG
78.8
98.8 +03
Table 25: Comparison of PGD (as shown in Table 4) with PGD variant with a graph kernel logistic regression (GKLR) model as the classifier. The kernels used here the PyramidMatch (PM) kernel, the shortest-path (SP) kernel, and the Weisfeiler-Lehman (WL) kernel.
Dataset
Model
Subscores
PGD (L)
PGD-GKLR ())
PM (L)
SP (L)
WI. (L)
PLANAR-L
AutoGraph
33.5 1.3
6.6
5,8 0.7
5,3 0.8
7.3 # 1.0
DIGRESS
45.4
1..
19.1
22.7 1.8
20.4
GRAN
99.3 1.1
43.1 0.4
8.1
1.6
4..1
ESGG
4..0
1..4
2.7
12.8 0.7
1..6
LOBSTER-L
AutoGraph
16
8.8 +.1
9.5
6,2
8.3 1
DIGRESS
3.2
2.0 2.3
2.8 2.3
1.5 2.2
0.3 + 1.0
GRAN
85.7
72.5 0.88
$2.4
57.5 1.3
72.5 # 0.8
ESGG
6.69
56.1 0.6
4.60
41.8 1.0
56.1
SBM-L
AutoGraph
5,8
2.3 2.6
1.5
3.0
0.5 1.3
DIGRESS
16.7 + 68.8 1.1
8.7 2.5
8.0
4.4
9.1 2.4
GRAN
46.7 + 1.2
45.9
32.4
46.7 1.2
ESGG
99.4
93.5 + 0.3
23.8 1.8
93.5
42.6 1.1
Proteins
AutoGraph
55.3 +
38.2 3.4
13.2
38.2
14.1 +.7
DIGRESS
86.8 2.9
38.6 2.4
1.2 2
38.6
3.5 + +39
GRAN
86.1 7.2
53.6 3.1
48.5 2.9
40.5
3..6
ESGG
77.8 5.1
27.7 4
11.8 # 2.4
29.5 #3.1
16.1 #
31


Reviews:
[{"review_id": "VqXHfR3OSO", "reviewer": "Reviewer_VfPn", "summary": "This paper proposes PolyGraphScore (PGS), a novel evaluation framework for graph generative models (GGMs) that addresses key weaknesses of the current standard Maximum Mean Discrepancy (MMD)-based metrics. Instead of computing kernel distances between graph descriptors, PGS trains a probabilistic discriminator (TabPFN) to distinguish real and generated graphs, using standard descriptors such as degree histograms, Laplacian spectra, or GIN embeddings. The classifier’s log-likelihood provides a variational lower bound on the Jensen–Shannon (JS) distance, yielding a unit-scaled score in [0, 1] that is interpretable and comparable across descriptors.\nComprehensive experiments demonstrate that PGS tracks synthetic perturbations, correlates strongly with model validity and training progress, and provides consistent model rankings across datasets and descriptors.", "questions": "How sensitive is PolyGraphScore (PGS) to the choice of graph descriptors? Have the authors explored combining multiple descriptors instead of selecting the best-performing one through max-reduction?\n\nCould the authors clarify how PGS behaves when using different classifier architectures beyond TabPFN (e.g., GNNs), and whether this affects the tightness of the JS lower bound?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well written and easy to follow. The problem statement is clearly defined and well-motivated. The proposed evaluation framework is both theoretically sound and empirically well validated, demonstrating strong performance across diverse experiments.", "weaknesses": "1. Although TabPFN is relatively fast, training separate discriminators for each descriptor introduces additional computational overhead compared to a single MMD computation.\n\n2. Regarding empirical validation, while the paper provides benchmarks on both real and synthetic datasets, expanding the experiments to include more specialized synthetic datasets could further demonstrate the generality of the proposed approach. Specifically, [1] notes that for Grid datasets — which consist of graphs with highly regular local structures — correlations between evaluation metrics are not close to 1, unlike for other datasets. Similarly, [2] reports different performance patterns of GGMs when generating grid-like structures. Comparing the proposed evaluation method with more expressive approaches, such as [1], on datasets where neither statistic-based MMD methods nor GNN-based methods clearly dominate, could further highlight the potential advantages of PGS.\n\n3. The stability analysis of PGS under varying sample sizes (Figures 23–25) indicates that, similar to MMD-based approaches, PGS suffers from relatively high variance, particularly for graph sets containing fewer than 256 samples.\n\n\n[1]. Shirzad, Hamed, Kaveh Hassani, and Danica J. Sutherland. \"Evaluating graph generative models with contrastively learned features.\" NeurIPS 2022.\n\n[2]. Zahirnia, Kiarash, et al. \"Neural graph generation from graph statistics.\" NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "s5vsc3wp6z", "reviewer": "Reviewer_bnvC", "summary": "- The paper proposes PolyGraphScore (PGS), a new metric for evaluating graph generative models by measuring how well a classifier can distinguish real from generated graphs.\n- PGS estimates the Jensen–Shannon divergence between the two distributions using probabilistic classification instead of kernel-based distances like MMD.\n- It uses graph descriptors (e.g., degree, spectrum, GIN embeddings) as tabular features and applies a TabPFN classifier to compute an interpretable score between 0 and 1.\n- Experiments show that PGS provides stable, bounded, and interpretable evaluations that correlate strongly with model quality and training progress, outperforming traditional MMD metrics.", "questions": "- Could you elaborate on why you chose the Jensen–Shannon divergence as the foundation for PolyGraphScore, instead of other f-divergences (e.g., KL, Hellinger)?\n- Does the PolyGraphScore framework extend naturally to weighted, directed, or attributed graphs, or are there fundamental challenges?\n- The paper uses TabPFN as the discriminator; could you provide more detailed empirical evidence comparing it to other probabilistic classifiers (e.g., random forest, XGBoost, small MLP)?\n- Since TabPFN supports only limited feature dimensions, how would PGS scale to very high-dimensional descriptors (e.g., graph embeddings >1000 dimensions)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper introduces a principled, classifier-based metric that provides an interpretable and bounded measure of distance between real and generated graphs.\n- The method is model-agnostic and descriptor-agnostic, allowing fair comparison across graph generative models without retraining or fine-tuning.\n- It demonstrates strong empirical correlations with true model quality and training progress, showing that the score behaves predictably and robustly.", "weaknesses": "- The choice of TabPFN as the discriminator is only weakly justified, with limited empirical evidence beyond a single logistic-regression ablation.\n- The method's dependence on precomputed graph descriptors introduces information loss and may underrepresent complex graph structures.\n- The paper lacks error bars or confidence intervals, which limits the reader's ability to assess the statistical reliability and variability of the reported results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tTYTl526MA", "reviewer": "Reviewer_3AL7", "summary": "This paper introduces PGS, an alternative to MMD for measuring the dissimilarity between sets of graphs. The introduced measure is based on the Jensen-Shannon divergence. The authors make use of the property that this divergence is bounded by the best possible binary classifier between these distributions. To obtain an estimate of this bound, they train classifiers based on graph representations and estimate the JS divergence. \n\nThe authors perform several experiments that highlight defects of MMD and which demonstrate that their JS divergence overcomes these defects.", "questions": "Can you comment on the running time and scalability of PGS?\n\nPGS uses descriptors as input rather than kernels. Could it be modified so that it works with graph kernels? I could imagine that some k-NN classifier could work, where we take nearest neighbors in the training set and use the validation set to estimate performance. That is, for a graph $G$ in the validation set, we find the $k$ graphs in the training set that best resemble it according to the kernel, and then estimate $D(G)$ as the fraction of these training graphs of each class.\n\nSection 5.2 shows experiments with \"Data perturbations\" akin to those from O'Bray and Thompson. Instead of perturbing a given distribution, we could interpolate between pairs of graph distributions, as is done in [2]. In particular, it would be interesting to see how well PGS performs on interpolations that are quite subtle, like between geometric graphs with 1D and 2D latent geometries.\n\nTable 2 uses Pearson correlation rather than Spearman correlation, which is used in Figure 3. Why are we interested in *linear* rather than *rank* correlation in the \"Trianing Iterations\" experiment?\n\nIf I understand Figure 2 correctly, we evaluate the MMD between two graph samples from the same distribution. This experiment is used to demonstrate the bias of MMD. However, since the true MMD should be zero and MMD is always nonnegative, it seems to me that any estimate with positive variance would be biased. Am I missing something here?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The information-theoretical setup of the JS divergence is very elegant. \n\nWhile the idea is simple, executing it properly requires some amount of engineering. From what I can see, the authors did a good job at this.\n\nTheir approach finds the graph descriptor that is best at discriminating the two graph samples (among some selection of descriptors). It is nice that this gives insight into the aspect in which the samples differ.\n\nThe paper is well written and I enjoyed reading it.", "weaknesses": "From the paper, it is not entirely clear to me how efficiently PGS can be computed. I'm assuming that it is considerably heavier than computing MMDs based on the same descriptors. In line 231, it says that it is based on TabPFN, which is \"fast\", though it does not elaborate on this claim.\n\nThere's several popular and interesting graph kernels that are missing from the comparison. Like the Weisfeiler-Lehman (WL) kernel, the PyramidMatch (PM, [1]) kernel and the Shortest-Paths (SP) kernel. The SP kernel, in particular, seems to fit the descriptor framework well and it was shown to be very powerful in distinguishing graphs from different distributions [2].\n\nThe experiments are somewhat hard to follow and some of the figures are somewhat messy. For example, Figure 3 could be replaced by box-plots for clarity and Figure 5 is quite dense.\n\nThe authors mention that MMD lacks an intrinsic scale, but most kernels satisfy some Cauchy-Schwarz-like bound $k(x,y)\\le\\sqrt{k(x,x)k(y,y)}$, which can be used to normalize the kernels like $k(x,y)/\\sqrt{k(x,x)k(y,y)}$. After doing so, the MMD is in the interval [0,2].\n\nTable 1 describes \"Multi-Descriptor Aggregation\" as one of the advantages of PGS over MMD. I can't find where in the text this is explained. MMD can also be used to combine different descriptors. For example, we can concatenate the descriptors (before computing kernels) or take the mean of several kernels. I do agree that PGS utilizes multiple descriptors more efficiently than MMD, but I would call this \"selection\" rather than \"aggregation\".\n\nIn the introduction, the authors characterize MMD as a way to compare graph samples using descriptors. I always interpreted MMD as a way to aggregate graph kernels to a distance between sets of graphs. These kernels are usually based on comparing graph descriptors, but this is not a necessity. For example, for the PM or WL kernel, it is cumbersome to think of them in terms of descriptors.\n\nIn Appendix M, I see that you generate planar graphs from Delauney triangulations. Note that this does not lead to a uniform sample among planar graph. To sample uniformly from this sample, one could use Boltzmann samplers [3]. I found this implementation that seems to do this https://github.com/towink/boltzmann-planar-graph (disclaimer: I did not test this implementation). Moreover, it appears that in the SBM generation, the connection probabilities are kept constant while the community sizes and number of communities are varied. Perhaps it is better to change these probabilities with the sizes to ensure each vertex has a constant (expected) number of neighbors inside and outside its communities. With the current probabilities, the SBM with $2\\times20$ nodes will only have have two inter-community edges in expectation.\n\n[1] Borgwardt, Karsten M., and Hans-Peter Kriegel. \"Shortest-path kernels on graphs.\" *Fifth IEEE international conference on data mining (ICDM'05)*. IEEE, 2005.\n\n[2] Gösgens, Martijn, Alexey Tikhonov, and Liudmila Prokhorenkova. \"Evaluating Graph Generative Models with Graph Kernels: What Structural Characteristics Are Captured?.\" *Transactions on Machine Learning Research*.\n\n[3] Fusy, Éric. \"Uniform random sampling of planar graphs in linear time.\" *Random Structures & Algorithms* 35.4 (2009): 464-522.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pvqxUhWUMd", "reviewer": "Reviewer_VKfC", "summary": "This work introduces PGS: a method for evaluating graph generative models. The idea behind the paper is to use the JS divergence to measure the similarity between the true graph distribution (reference)  and that of the generated distribution. Similar to the literature employing MMD instead of using the graph distribution it uses the distribution of certain descriptors derived from statistics of the graph (like degrees, orbit counts, etc.) The benefit of using JSD over MMD is that the former is bounded. JSD has been used in GANs as the objective function. Hence, this work approximates JSD using a binary classifier that tries to distinguish the original graph from the generated ones. To take into account multiple predictors it takes the maximum divergence among all descriptors as the divergence between the reference and generated graphs.", "questions": "Q1: Have the authors considered other aggregations than max, or was it some certain predictor that shows higher sensitivity to perturbations and thus most frequently dominates?\nQ2: How fast is the training of TabPFN?\nQ3: Taking into account that for real graphs (as opposed to synethetic ones) the number of reference graphs could be limited, do the authors see a limitation in a method that also requires to split the dataset into train/test sets and hence a small number of graphs could be available for either training or testing? How many samples does usually TabPFN require?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The proposed method for evaluating GGMs addresses some of the limitations of MMD: Critically, its unboundedness and the lack of a way to combine predictors\n* It introduces a new axis of evaluating how suitable a given measure (or metric) is: How predictable it is with respect to the training steps of well-known models. Intuitively, the distance should decrease as the training steps increase.", "weaknesses": "* On the other hand, it follows the existing paradigm of MMD -- using a set of predictors to approximate the graph distance with the distance of predictors, without offering a new angle that would revitalize the literature in GGM evaluation.\n* The proposed way to aggregate multiple predictors (by taking the maximum distance) is potentially susceptible to outliers & does not take complementary signals from predictors into account.\n* The scale issue is remediated by using a bounded in [0,1] distance. However, certain predictors  (or classifiers applied to those predictors) might be more sensitive to perturbations than others, hence the max aggregation scheme could favor them.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)