On Evaluation Metrics for Graph Generative Models

Rylee ThompsonBoris KnyazevElahe GhalebiJungtaek KimGraham W. Taylor

article2022ICLR63 citations

Proposes scalable, single-score evaluation metrics for graph generative models based on untrained random graph neural networks, enabling fast and feature-aware measurement of generated graph fidelity and diversity.

Listen

Graph generative models create complex structured data used in high-impact domains such as molecular discovery and structural engineering. However, evaluating how closely generated graphs match real target graphs is a major operational challenge. Existing standard evaluation methods rely on computing multiple disconnected statistics based on graph properties (such as node degree and clustering coefficients). This practice causes three critical problems: it produces conflicting metrics that prevent clear model selection, it fails to account for underlying node and edge features, and it is computationally prohibitive on large datasets.

The article systematically evaluates alternative evaluation metrics and demonstrates that randomly initialized, untrained Graph Isomorphism Networks can serve as fast, reliable, and domain-agnostic feature extractors for graph model evaluation.

To conduct this assessment, the researchers designed controlled benchmarking experiments across six diverse graph datasets, including social, biological, structural, and molecular networks. They generated controlled perturbations to simulate fidelity loss and diversity failures (such as mode dropping and mode collapse). Across these scenarios, they evaluated three broad families of metrics: traditional graph-statistic and kernel baselines, metrics using pretrained graph networks, and metrics using untrained random graph networks.

The findings show that traditional evaluation methods suffer from a severe blind spot: while they detect basic fidelity loss, they fail to measure graph diversity, scoring below 0.50 in correlation when graph modes collapse. In contrast, neural-network-based metrics using an untrained, random network achieved near-perfect correlation (up to 0.96 across fidelity and diversity). Furthermore, pretraining the feature extractor provided no meaningful performance gain over random initialization, proving expensive pretraining pipelines are unnecessary. Finally, the random network approach reduced evaluation runtimes by multiple orders of magnitude—taking roughly 120 seconds for 10,000 samples compared to over 100,000 seconds for traditional clustering-based methods—while seamlessly handling discrete and continuous node and edge attributes.

These results establish that organizations do not need complex, custom-trained networks or slow, multi-score heuristics to benchmark graph generative models. Adopting unified random-network metrics significantly reduces computational overhead and risks, accelerates development timelines, and ensures that generated structures accurately reflect both the quality and diversity of target data.

The article recommends two primary scalar metrics: the maximum mean discrepancy using a radial basis function kernel (MMD RBF) for general model selection, and the harmonic mean of precision and recall (F1 PR) when datasets have fewer than roughly 42 samples or extreme compute limits exist. In practice, teams should use a standard random three-layer network architecture and establish baseline comparisons using split target datasets. While confidence in these metrics is high across standard benchmark datasets, caution is warranted when evaluating extremely small sample sizes (under 100 graphs), where metric variance increases and requires careful replication.

Pohang University of Science and Technology Samsung SAIL University of Guelph Vector Institute computational efficiency directed graphs generative model graph generative models evaluation metrics graph kernels

arXiv: 2201.09871 uoguelph-mlrg/GGM-metrics

Paper: How Powerful are Graph Neural Networks?, Keyulu Xu et al. (2019). Introduces the Graph Isomorphism Network (GIN) architecture and theoretical Weisfeiler-Lehman expressiveness bounds that serve as the foundational feature extractor used for generative model evaluation in the source paper.
Paper: Weisfeiler-Lehman Graph Kernels, Nino Shervashidze et al. (2011). Establishes the Weisfeiler-Lehman graph kernels that form standard traditional baseline metrics for evaluating graph similarity.
Paper: Strategies for Pre-training Graph Neural Networks, Weihua Hu et al. (2020). Provides the foundational methodologies for pre-training graph neural networks, which the source paper directly benchmarks against untrained, randomly initialized networks.
Paper: Pitfalls of Graph Neural Network Evaluation, Oleksandr Shchur et al. (2018). Highlights standard benchmarking pitfalls and evaluation fragility across graph neural network architectures, motivating the source paper's rigorous assessment of evaluation metrics.

Paper: Benchmarking Graph Neural Networks, Vijay Prakash Dwivedi et al. (2023). Extends standardized, reproducible graph evaluation methodology by introducing unified medium-scale benchmarks and strict parameter budgets across diverse graph learning tasks.
Paper: Universal Prompt Tuning for Graph Neural Networks, Taoran Fang et al. (2023). Applies Graph Isomorphism Network representations to universal prompt tuning across varied graph pre-training strategies.

Cover for On Evaluation Metrics for Graph Generative Models

Abstract

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

Topics

computational efficiency directed graphs generative model genetic selection graph neural networks image generation mode selection bipartite graphs weighted graph complexity metrics

Keywords

graph generative models evaluation metrics graph kernels graph statistics molecular graphs random graphs

1 Introduction
2 Background & related work
2.1 Classical metrics
2.2 Graph neural networks
2.3 Neural-network-based metrics
2.4 Benchmarking evaluation metrics
3 The effectiveness of random GNNs
4 Experiments
4.1 Measuring fidelity
4.2 Measuring diversity
4.3 Sensitivity to node and edge features
4.4 Sample efficiency
4.5 Computational efficiency
4.6 GGM selection
5 Discussion
6 Conclusion
References
A Additional metric details
B Additional experimental details
B.1 Datasets
B.2 Measuring diversity
B.3 Randomizing edge features
B.4 Randomizing node features
B.5 Computational efficiency
B.6 GGM selection
B.7 GNN pretraining
C Additional results
C.1 Individual experiments
C.2 All experiments grouped by GIN configuration
C.3 All results grouped by dataset
C.4 Mixing generated graphs
C.5 Computational efficiency
C.6 Comparing other GNNs
C.7 Comparing σ\sigma selection strategies
C.8 GGM selection
C.9 Stability of GGM rankings

Knowls

Knowl 1 — Random Graph Isomorphism Network Embeddings for Graph Generative Model Evaluation
model/method
An untrained, randomly initialized Graph Isomorphism Network (GIN) can be used as a domain-agnostic feature extractor to map any graph $G = (V, E)$ to a fixed-dimensional embedding vector $\mathbf{x} \in \mathbb{R}^{L \cdot d}$ for evaluating graph generative models.

Given a graph $G = (V, E)$ with vertices $V$ and edges $E = \{(i, j) \mid i, j \in \{1, \dots, |V|\}\}$ , initial node feature vectors $\mathbf{h}_v^{(0)}$ are assigned. For graphs without explicit node attributes, the scalar node degree expressed as an integer is used as $\mathbf{h}_v^{(0)}$ to improve discriminability. When categorical edge features $\mathbf{A}_{i,j,:}$ are present, they are concatenated to the node messages during propagation.

For each graph propagation layer $l \in \{1, \dots, L\}$ , node representations $\mathbf{h}_v^{(l)} \in \mathbb{R}^d$ are computed as: $\mathbf{h}_v^{(l)} = \text{MLP}^{(l)}\left( \mathbf{h}_v^{(l-1)} + \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(l-1)} \right)$ where $\mathcal{N}(v)$ denotes the neighbors of node $v$ , and $\text{MLP}^{(l)}$ is a multi-layer perceptron with weights initialized using orthogonal weight initialization.

The overall graph embedding $\mathbf{x}$ is formed by concatenating sum readouts from every intermediate propagation round $l \in \{1, \dots, L\}$ : $\mathbf{x} = \text{CONCAT}\left(\left[\sum_{v \in V} \mathbf{h}_v^{(l)} \;\middle|\; l \in \{1, \dots, L\}\right]\right)$ yielding an embedding dimensionality of $L \cdot d$ . The standard recommended architecture configuration is $L = 3$ propagation rounds and node embedding size $d = 35$ , producing a $105$ -dimensional graph representation.
Knowl 2 — Maximum Mean Discrepancy with Multi-Scale RBF Kernel (MMD RBF) for Graph Embeddings
model/method
To measure the distance between a generated set of graph embeddings $S_g = \{\mathbf{x}_1^g, \dots, \mathbf{x}_n^g\}$ and a reference set $S_r = \{\mathbf{x}_1^r, \dots, \mathbf{x}_m^r\}$ , Maximum Mean Discrepancy (MMD) is computed using an RBF kernel with an adaptive multi-scale bandwidth selection heuristic: $\text{MMD}^2(S_g, S_r; \sigma) = \frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m k_\sigma(\mathbf{x}_i^r, \mathbf{x}_j^r) + \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n k_\sigma(\mathbf{x}_i^g, \mathbf{x}_j^g) - \frac{2}{nm} \sum_{i=1}^n \sum_{j=1}^m k_\sigma(\mathbf{x}_i^g, \mathbf{x}_j^r)$ where the Gaussian RBF kernel is defined as: $k_\sigma(\mathbf{x}_i, \mathbf{x}_j) = \exp\left( -\frac{\|\mathbf{x}_i - \mathbf{x}_j\|_2^2}{2\sigma^2} \right)$

Rather than fixing $\sigma = 1$ or relying solely on a median heuristic, the bandwidth $\sigma$ is chosen by maximizing MMD over a discrete candidate set $\Sigma$ : $\text{MMD}_{\text{RBF}}(S_g, S_r) = \max_{\sigma \in \Sigma} \text{MMD}(S_g, S_r; \sigma)$ where $\Sigma$ contains candidate values $\{0.01, 0.1, 0.25, 0.5, 0.75, 1.0, 2.5, 5.0, 7.5, 10.0\}$ multiplied by the mean pairwise Euclidean distance between all samples across $S_g$ and $S_r$ . This scaling makes the metric sensitive across disparate graph domains and feature scales.
Knowl 3 — Manifold Precision and Recall (F1 PR) for Graph Generative Model Evaluation
model/method
Improved Precision and Recall (P&R) applied to graph embeddings extracted from an untrained random Graph Isomorphism Network decouples generative performance into sample realism (Precision) and mode preservation (Recall).

Let $S_r = \{\mathbf{x}_1^r, \dots, \mathbf{x}_m^r\}$ and $S_g = \{\mathbf{x}_1^g, \dots, \mathbf{x}_n^g\}$ be sets of graph embeddings extracted from reference and generated sets, respectively. For each embedding $\mathbf{x}$ , its $k$ -th nearest neighbor Euclidean distance within its own sample set defines the radius $r(\mathbf{x})$ of a hypersphere $B(\mathbf{x}, r(\mathbf{x}))$ . The reference manifold is the union of all reference hyperspheres, and the generated manifold is the union of all generated hyperspheres: $\text{Precision}(S_g, S_r) = \frac{1}{n} \sum_{j=1}^n \mathbb{I}\left( \mathbf{x}_j^g \in \bigcup_{i=1}^m B(\mathbf{x}_i^r, r(\mathbf{x}_i^r)) \right)$ $\text{Recall}(S_g, S_r) = \frac{1}{m} \sum_{i=1}^m \mathbb{I}\left( \mathbf{x}_i^r \in \bigcup_{j=1}^n B(\mathbf{x}_j^g, r(\mathbf{x}_j^g)) \right)$ where $k = 5$ is standard and $\mathbb{I}(\cdot)$ denotes the indicator function.

To yield a single scalar metric measuring generative quality, the harmonic mean ( $F_1\text{ PR}$ ) is computed: $F_1\text{ PR} = \frac{2 \cdot \text{Precision} \cdot \text{Recall}}{\text{Precision} + \text{Recall}}$ Because $F_1\text{ PR}$ achieves sample efficiency requiring only $n = 7$ samples to differentiate real from perturbed graph distributions, it provides a lightweight scalar alternative to kernel MMD.
Knowl 4 — Experimental Protocol for Objective Evaluation of Graph Generative Model Metrics
experimental setup
To evaluate candidate graph generative model evaluation metrics objectively without assuming a linear response to distortion, candidate metrics are benchmarked using synthetic distortion schedules parameterized by a perturbation intensity $t \in [0, 1]$ . Performance is scored by computing the Spearman rank correlation between metric values $\hat{\rho}(S_g, S_r)$ and $t$ , where an ideal metric achieves a rank correlation of $1.0$ .

The benchmark comprises six controlled evaluation tasks evaluated across graph datasets (Lobster, Grid, Proteins, Ego, Community, and ZINC):
1. Fidelity via Random Graph Mixing: A fraction $t \in [0, 1]$ of real graphs in $S_g(t)$ is replaced with size- and sparsity-matched Erdős–Rényi (E-R) random graphs.
2. Fidelity via Edge Rewiring: Each edge in each graph in $S_g$ is rewired to a uniformly sampled target vertex with probability $t \in [0, 1]$ .
3. Diversity via Mode Collapse: Datasets are clustered using Affinity Propagation on Weisfeiler-Lehman subtree kernel similarities. A fraction $t \in [0, 1]$ of clusters in $S_g$ have their member graphs replaced with the respective cluster center graph.
4. Diversity via Mode Dropping: A fraction $t \in [0, 1]$ of clusters are deleted from $S_g$ , with the remaining clusters sampled uniformly with replacement to preserve total sample size $|S_g|$ .
5. Feature Sensitivity: On datasets with categorical attributes (ZINC), node or edge features are randomized with probability $t \in [0, 1]$ .
6. Sample Efficiency: The minimum sample size $n$ required such that $\hat{\rho}(S_r', S_r'') < \hat{\rho}(S_r', S_g')$ holds for all sample counts $\ge n$ , where $S_r', S_r''$ are disjoint reference splits and $S_g'$ is an E-R random graph set.
Knowl 5 — Failure Mode of Classical Graph Statistic MMD Metrics on Diversity Assessment
empirical result
Classical graph generative model evaluation metrics based on Maximum Mean Discrepancy over 1D empirical distributions of graph statistics (Degree MMD, Clustering MMD, and 4-node Orbit Count MMD using Earth Mover's Distance) fail to capture mode collapse and mode dropping in generated graph distributions.

In controlled diversity benchmarks across multiple graph datasets:
- Mode Collapse: Classical metrics exhibited poor Spearman rank correlations with the cluster collapse ratio $t$ : Orbit MMD scored $0.49 \pm 0.046$ , Degree MMD scored $0.51 \pm 0.061$ , and Clustering MMD scored $0.43 \pm 0.047$ . On triangle-free graphs (Grid and Lobster), every node has a clustering coefficient of zero, causing Clustering MMD to register rank correlations of $0.000 \pm 0.000$ .
- Mode Dropping: Classical metrics obtained similarly suboptimal rank correlations: Orbit MMD scored $0.43 \pm 0.034$ , Degree MMD scored $0.76 \pm 0.035$ , and Clustering MMD scored $0.72 \pm 0.030$ . In contrast, random GIN-based metrics such as MMD RBF and $F_1\text{ PR}$ achieved diversity rank correlations of $0.95 \pm 0.003$ and $0.93 \pm 0.003$ , demonstrating that 1D structural histograms cannot capture manifold-level distribution diversity.
Knowl 6 — Parity of Untrained Random GNNs with Pretrained GNNs for GGM Evaluation
empirical result
Untrained Graph Isomorphism Networks (GINs) with random orthogonal weight initializations extract graph representations that are as effective as supervised pretrained GINs for evaluating graph generative model fidelity and diversity.

When aggregated across 20 distinct GIN architectural parameterizations ( $L \in [2, 7]$ propagation rounds, $d \in [5, 40]$ hidden dimension) and six graph datasets:
- Mean combined fidelity and diversity rank correlation for random GINs averaged $0.71 \pm 0.007$ , compared to $0.73 \pm 0.003$ for GINs pretrained on multiclass graph classification.
- For MMD RBF, random GINs achieved fidelity correlation $0.97 \pm 0.002$ and diversity correlation $0.95 \pm 0.003$ , matching pretrained GINs ( $0.97 \pm 0.002$ fidelity, $0.97 \pm 0.002$ diversity).
- For $F_1\text{ PR}$ , random GINs achieved $0.92 \pm 0.004$ fidelity and $0.93 \pm 0.003$ diversity, matching pretrained GINs ( $0.93 \pm 0.002$ fidelity, $0.93 \pm 0.002$ diversity).
- Random GIN metrics exhibited lower variance across random seeds during model checkpoint selection than pretrained networks while eliminating the need to retrain domain-specific GNN models for datasets with incompatible feature dimensions.

Knowl 7 — Benchmark Summary of Graph Generative Model Evaluation Metrics

data/table

Across benchmark experiments evaluating fidelity correlation, diversity correlation, sensitivity to categorical node/edge features, minimum required sample size $n$ , and runtime scaling to 10,000 samples, random-GNN-based metrics outperform classical graph statistics.

Metric	Fidelity	Diversity	Fid. Div. (Rand/Pre)	Node/Edge	Sample Eff. (Rand/Pre)	Comp. Eff. (s)
Orbits MMD	$0.37 \pm 0.048$	$0.49 \pm 0.046$	$0.43 \pm 0.034$	N/A	$122 \pm 22$	$1.4 \times 10^4$
Degree MMD	$1.00 \pm 0.000$	$0.51 \pm 0.061$	$0.76 \pm 0.035$	N/A	$9 \pm 1$	$7.5 \times 10^3$
Clustering MMD	$0.99 \pm 0.003$	$0.43 \pm 0.047$	$0.72 \pm 0.030$	N/A	$7 \pm 0$	$1.1 \times 10^5$
NSPDK MMD	$0.99 \pm 0.001$	$0.78 \pm 0.050$	$0.88 \pm 0.028$	$1.00 \pm 0.000$	$8 \pm 1$	$382$
FD	$0.98 \pm 0.002$	$0.44 \pm 0.013$	$0.71 \pm 0.008$ / $0.74 \pm 0.007$	$0.96 \pm 0.010$	$58 \pm 3$ / $55 \pm 3$	$4.5$
KD	$0.62 \pm 0.015$	$0.32 \pm 0.014$	$0.47 \pm 0.010$ / $0.58 \pm 0.009$	$0.94 \pm 0.011$	$89 \pm 4$ / $63 \pm 3$	$5.1$
Precision	$0.82 \pm 0.007$	$-0.25 \pm 0.010$	$0.29 \pm 0.011$ / $0.29 \pm 0.011$	$0.99 \pm 0.001$	$7 \pm 0$ / $7 \pm 0$	$18$
Recall	$0.70 \pm 0.007$	$0.93 \pm 0.003$	$0.82 \pm 0.004$ / $0.81 \pm 0.005$	$0.80 \pm 0.018$	$7 \pm 0$ / $7 \pm 0$	$18$
Density	$0.90 \pm 0.004$	$-0.10 \pm 0.015$	$0.40 \pm 0.011$ / $0.36 \pm 0.012$	$0.99 \pm 0.001$	$7 \pm 0$ / $7 \pm 0$	$12$
Coverage	$0.91 \pm 0.003$	$0.95 \pm 0.003$	$0.93 \pm 0.002$ / $0.93 \pm 0.003$	$0.99 \pm 0.000$	$7 \pm 0$ / $7 \pm 0$	$12$
F1 PR	$0.92 \pm 0.004$	$0.93 \pm 0.003$	$0.93 \pm 0.003$ / $0.93 \pm 0.002$	$0.99 \pm 0.000$	$7 \pm 0$ / $7 \pm 0$	$18$
F1 DC	$0.95 \pm 0.002$	$0.86 \pm 0.007$	$0.91 \pm 0.004$ / $0.88 \pm 0.004$	$0.99 \pm 0.000$	$7 \pm 0$ / $7 \pm 0$	$12$
MMD Linear	$0.98 \pm 0.002$	$0.37 \pm 0.012$	$0.68 \pm 0.008$ / $0.75 \pm 0.007$	$0.99 \pm 0.005$	$57 \pm 3$ / $31 \pm 2$	$4.5$
MMD RBF	$0.97 \pm 0.002$	$0.95 \pm 0.003$	$0.96 \pm 0.002$ / $0.97 \pm 0.002$	$1.00 \pm 0.001$	$42 \pm 2$ / $12 \pm 1$	$120$

Values represent mean $\pm$ standard error. MMD RBF and F1 PR achieve the highest joint fidelity and diversity sensitivity while maintaining low sample requirements, sensitivity to node/edge attributes, and low computation times.

Knowl 8 — Computational and Memory Scalability of Random GNN Metrics vs Classical Graph MMD
empirical result
Classical graph statistics evaluation metrics (Clustering MMD, Orbit MMD, Degree MMD) become computationally intractable as graph dataset sizes increase, whereas GNN embedding metrics remain orders of magnitude faster.

When evaluated on an Intel Platinum 8160F CPU (4 cores) as the number of graph samples scales up to 10,000:
- Clustering MMD required $1.1 \times 10^5$ seconds ( $\approx 30.5$ hours).
- Orbit MMD required $1.4 \times 10^4$ seconds ( $\approx 3.9$ hours).
- Degree MMD required $7.5 \times 10^3$ seconds ( $\approx 2.1$ hours).
- NSPDK MMD required $382$ seconds.
- In contrast, extracting embeddings and computing FD, KD, MMD Linear, F1 PR, and F1 DC required between $4.5$ and $18$ seconds ( $>1,000\times$ speedup over classical MMD).
- MMD RBF required $120$ seconds due to multi-scale kernel evaluations over the $10,000 \times 10,000$ Gram matrix.
In terms of RAM consumption when scaling graph edge count up to $10^6$ edges per graph, classical graph MMD metrics required $>21.8\text{ GB}$ of RAM, whereas neural network embedding extraction required $10.40\text{ GB}$ .
Knowl 9 — Inconsistent Model Rankings Produced by Multi-Statistic Classical Metrics
empirical result
Evaluating graph generative models with multiple independent classical statistics (Degree, Clustering, and Orbit MMD) leads to conflicting and contradictory model rankings across checkpoints and architectures.

When evaluating GRAN and GraphRNN at training checkpoints ( $33\%$ , $66\%$ , and $100\%$ of total epochs) on the Grid dataset:
- Clustering MMD ranked GRAN-100% best ( $1.24 \times 10^{-6}$ ), while Degree MMD ranked GRAN-66% best ( $3.20 \times 10^{-5}$ ), and Orbit MMD ranked GRAN-100% ( $0.037$ ) ahead of GRAN-66% ( $0.047$ ).
- When evaluating GraphRNN checkpoints, Degree MMD preferred GraphRNN-66% ( $0.015$ ) over GraphRNN-100% ( $0.032$ ), whereas Orbit MMD preferred GraphRNN-33% ( $0.134$ ) over GraphRNN-66% ( $0.169$ ) and GraphRNN-100% ( $0.252$ ).
- In contrast, the scalar MMD RBF metric using a random GIN unambiguously and consistently ranked checkpoints with low standard error across 10 random seeds: GRAN-66% ( $0.061 \pm 0.001$ ), GRAN-100% ( $0.063 \pm 0.001$ ), GraphRNN-66% ( $0.154 \pm 0.00007$ ), GraphRNN-100% ( $0.184 \pm 0.00005$ ), GraphRNN-33% ( $0.248 \pm 0.00006$ ). Evaluating metrics on a 50/50 split of the ground-truth dataset provides a well-defined empirical lower bound representing two indistinguishable sets (e.g., Grid 50/50 split: MMD RBF $= 0.042$ , Degree MMD $= 6.51 \times 10^{-5}$ , Orbit MMD $= 0.018$ ).
Knowl 10 — Decision Trade-offs and Limitations of GNN-Based GGM Evaluation Metrics
limitation
While MMD RBF and F1 PR using a random GIN ( $L=3, d=35$ ) provide expressive scalar evaluations, their deployment involves specific operational trade-offs and domain constraints:
1. Sample Size Constraints: F1 PR requires only $n = 7$ samples to discriminate real from corrupted distributions, whereas MMD RBF requires $n \approx 42$ samples. F1 PR is recommended when sample counts are below $\sim 42$ or when computational efficiency is paramount; otherwise, MMD RBF is preferred.
2. Computational Scaling: MMD RBF exhibits higher fidelity and diversity correlation ( $0.96 \pm 0.002$ vs. $0.93 \pm 0.003$ for F1 PR) and perfect sensitivity to node/edge features ( $1.00 \pm 0.001$ ), but its $O(n^2)$ multi-scale kernel computation requires $120\text{ s}$ for 10,000 samples compared to $18\text{ s}$ for F1 PR.
3. Domain-Specific Validity Exclusions: Scalar distance metrics on random GNN embeddings assess distributional similarity, but they do not replace task-specific validity filters (e.g., chemical valence rules, quantitative estimate of drug-likeness (QED), or physical stability in molecular graph generation).
4. Variance on Small / Poorly Modeled Distributions: On very small datasets with low generative quality (such as Lobster with $N=100$ ), metric ranking stability across different random GIN seeds decreases relative to larger, structured datasets like Grid and Proteins.

Coverage note — Detailed per-architecture ablation listings across all 20 individual GIN hyperparameter combinations were omitted in favor of the aggregated results and the optimal configuration.

References

1.Francis R. Bach, Gert R. G. Lanckriet, and Michael I. Jordan. Multiple kernel learning, conic duality, and the smo algorithm. In Proceedings of the International Conference on Machine Learning (ICML), 2004.
2.Victor Bapst, Alvaro Sanchez-Gonzalez, Carl Doersch, Kimberly Stachenfeld, Pushmeet Kohli, Peter Battaglia, and Jessica Hamrick. Structured agents for physical construction. In Proceedings of the International Conference on Machine Learning (ICML), 2019.
3.Mikołaj Bińkowski, Danica J Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD GANs. arXiv preprint arXiv:1801.01401, 2018.
4.Haoye Cai, Chunyan Bai, Yu-Wing Tai, and Chi-Keung Tang. Deep video generation, prediction and completion of human action sequences. In Proceedings of the European Conference on Computer Vision (ECCV), 2018.
5.Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, and Liping Liu. Order matters: Probabilistic modeling of node sequence for graph generation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1630–1639. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/chen21j.html.
6.Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10, pp. 255–262, Madison, WI, USA, 2010. Omnipress. ISBN 9781605589077.
7.Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
8.Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
9.Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771–783, 2003.
10.Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.
11.Brendan J. Frey and Delbert Dueck. Clustering by passing messages between data points. Science, 315(5814):972–976, 2007.
12.Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint arXiv:1707.07269, 2018.
13.Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain-agnostic labeled graph generation. Proceedings of The Web Conference 2020, Apr 2020. doi: 10.1145/3366423.3380201. URL http://dx.doi.org/10.1145/3366423.3380201.
14.Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel method for the two-sample problem. In Advances in Neural Information Processing Systems (NeurIPS), volume 19, 2006.
15.Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(1):723–773, 2012a.
16.Arthur Gretton, Dino Sejdinovic, Heiko Strathmann, Sivaraman Balakrishnan, Massimiliano Pontil, Kenji Fukumizu, and Bharath K Sriperumbudur. Optimal kernel choice for large-scale two-sample tests. In Advances in Neural Information Processing Systems (NeurIPS), volume 22, 2012b.
17.William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs, 2018.
18.Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, Günter Klambauer, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge to a nash equilibrium. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
19.Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
20.John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. ZINC: A free tool to discover chemistry for biology. Journal of Chemical Information and Modeling, 52 (7):1757–1768, 2012.
21.Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Multi-objective molecule generation using interpretable substructures. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
22.Ana Justel, Daniel Peña, and Rubén Zamar. A multivariate kolmogorov-smirnov test of goodness of fit. Statistics & Probability Letters, 35:251–259, 10 1997. doi: 10.1016/S0167-7152(97)00020-5.
23.Wataru Kawai, Yusuke Mukuta, and Tatsuya Harada. Scalable generative models for graphs with graph attention mechanism, 2019.
24.Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
25.Xiangzhe Kong, Zhixing Tan, and Yang Liu. GraphPiece: Efficiently generating high-quality molecular graph with substructures. arXiv preprint arXiv:2106.15098, 2021.
26.Tuomas Kynkäänniemi, Tero Karras, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Improved precision and recall metric for assessing generative models. In Proceedings of the International Conference on Machine Learning (ICML), 2019.
27.Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.03324, 2018.
28.Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
29.Chia-Cheng Liu, Harris Chan, and Kevin Luk. Auto-regressive Graph Generation Modeling with Improved Evaluation Methods. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
30.Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are GANs created equal? a large-scale study. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
31.Sebastian Lunz, Yingzhen Li, Andrew Fitzgibbon, and Nate Kushman. Inverse graphics GAN: Learning to generate 3D shapes from unstructured 2D data. arXiv preprint arXiv:2002.12674, 2020.
32.Sebastian Moreno, Jennifer Neville, and Sergey Kirshner. Tied kronecker product graph models to capture variance in network populations. ACM Trans. Knowl. Discov. Data, 12(3), mar 2018. ISSN 1556-4681. doi: 10.1145/3161885. URL https://doi.org/10.1145/3161885.
33.Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2019.
34.Muhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh, Yunjey Choi, and Jaejun Yoo. Reliable fidelity and diversity metrics for generative models. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
35.Leslie O'Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metrics for graph generative models: Problems, pitfalls, and practical solutions. In International Conference on Learning Representations, 2022. URL https://openreview.net/forum?id=tBtoZYKd9n.
36.Marco Podda and Davide Bacciu. Graphgen-redux: a fast and lightweight recurrent model for labeled graph generation, 2021.
37.Mariya Popova, Mykhailo Shvets, Junier Oliva, and Olexandr Isayev. MolecularRNN: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv:1905.13372, 2019.
38.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):1736–1741, 2018.
39.Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. In Advances in Neural Information Processing Systems (NeurIPS), volume 29, 2016.
40.Bidisha Samanta, Abir De, Gourhari Jana, Vicenç Gómez, Pratim Kumar Chattaraj, Niloy Ganguly, and Manuel Gomez-Rodriguez. NeVAE: A deep generative model for molecular graphs. Journal of Machine Learning Research, 21(114):1–33, 2020.
41.Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2014.
42.Bernhard Schölkopf, Alexander J. Smola, and Klaus-Robert Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10(5):1299–1319, 1998.
43.Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):93, Sep. 2008.
44.Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(77): 2539–2561, 2011.
45.Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. GraKeL: A graph kernel library in Python. Journal of Machine Learning Research, 21(54):1–5, 2020.
46.Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Gert R. G. Lanckriet, and Bernhard Schölkopf. Kernel choice and classifiability for RKHS embeddings of probability distributions. In Advances in Neural Information Processing Systems (NeurIPS), volume 22, 2009.
47.Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
48.Lucas Theis, Aäron van den Oord, and Matthias Bethge. A note on the evaluation of generative models, 2016.
49.Rylee Thompson, Elahe Ghalebi, Terrance DeVries, and Graham W. Taylor. Building LEGO using deep generative models of graphs. In NeurIPS Workshop on Machine Learning for Engineering Modeling, Simulation, and Design (ML4Eng), 2020.
50.Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4–24, 2020.
51.Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
52.Qiantong Xu, Gao Huang, Yang Yuan, Chuan Guo, Yu Sun, Felix Wu, and Kilian Weinberger. An empirical study on evaluation metrics of generative adversarial networks. arXiv preprint arXiv:1806.07755, 2018.
53.Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the International Conference on Machine Learning (ICML), 2018.
54.Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.

Citation

MLA

Thompson, R., et al. “On Evaluation Metrics for Graph Generative Models”. arXiv, 2022, http://arxiv.org/abs/2201.09871v2.

APA

Thompson, R., Knyazev, B., Ghalebi, E., Kim, J., & Taylor, G. W. (2022). On Evaluation Metrics for Graph Generative Models. arXiv. http://arxiv.org/abs/2201.09871v2

Chicago

Thompson, R., B. Knyazev, E. Ghalebi, J. Kim, and G. W. Taylor. 2022. “On Evaluation Metrics for Graph Generative Models”. arXiv. http://arxiv.org/abs/2201.09871v2.

Harvard

Thompson, R. et al. (2022) “On Evaluation Metrics for Graph Generative Models”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2201.09871v2.

Vancouver

1. Thompson R, Knyazev B, Ghalebi E, Kim J, Taylor GW (2022) On Evaluation Metrics for Graph Generative Models. arXiv

BibTeX

@article{thompson2022evaluation,
  title = {On Evaluation Metrics for Graph Generative Models},
  author = {Thompson, Rylee and Knyazev, Boris and Ghalebi, Elahe and Kim, Jungtaek and Taylor, Graham W.},
  year = {2022},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2201.09871v2},
  eprint = {2201.09871}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

On Evaluation Metrics for Graph Generative Models

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Random Graph Isomorphism Network Embeddings for Graph Generative Model Evaluation

Knowl 2 — Maximum Mean Discrepancy with Multi-Scale RBF Kernel (MMD RBF) for Graph Embeddings

Knowl 3 — Manifold Precision and Recall (F1 PR) for Graph Generative Model Evaluation

Knowl 4 — Experimental Protocol for Objective Evaluation of Graph Generative Model Metrics

Knowl 5 — Failure Mode of Classical Graph Statistic MMD Metrics on Diversity Assessment

Knowl 6 — Parity of Untrained Random GNNs with Pretrained GNNs for GGM Evaluation

Knowl 7 — Benchmark Summary of Graph Generative Model Evaluation Metrics

Knowl 8 — Computational and Memory Scalability of Random GNN Metrics vs Classical Graph MMD

Knowl 9 — Inconsistent Model Rankings Produced by Multi-Statistic Classical Metrics

Knowl 10 — Decision Trade-offs and Limitations of GNN-Based GGM Evaluation Metrics

References

Citation

BibTeX

Source Code

Access the Paper