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

Leslie O'BrayMax HornBastian RieckKarsten M. Borgwardt

article2022ICLR50 citations

Demonstrates critical flaws in evaluating graph generative models with Maximum Mean Discrepancy and establishes practical guidelines to ensure reliable and standardized model benchmarking.

Listen

Graph generative models are increasingly used to synthesize complex relational structures, such as molecular networks and social connections. However, determining which model performs best remains challenging because visual inspection cannot reliably distinguish graph distributions. Today, the field relies heavily on a statistical distance metric called Maximum Mean Discrepancy (MMD) to evaluate and rank newly proposed models. In practice, researchers map graphs into feature histograms—such as node degrees, clustering coefficients, or spectral properties—and calculate MMD using fixed kernel functions and arbitrary parameters.

The article systematically evaluates the reliability and expressive power of MMD in graph generation benchmarking. It demonstrates how current evaluation choices fail to provide fair or consistent model comparisons and establishes a principled framework to guide future model assessments.

To test MMD's behavior, the authors analyzed three prominent generative models across four standard benchmark datasets. They also applied controlled synthetic perturbations—including edge additions, removals, rewirings, and node additions—to simulate increasing levels of structural difference. Across hundreds of kernel, hyperparameter, and descriptor combinations, the authors tracked how the calculated MMD distances responded to these perturbations and evaluated the resulting computational costs.

The analysis reveals several critical vulnerabilities in the current evaluation pipeline. First, model rankings under MMD are highly unstable; merely switching the kernel function or altering histogram bin sizes and bandwidth parameters completely flips which model appears to be the top performer. Second, MMD frequently fails to capture actual differences: as graphs are increasingly corrupted with synthetic noise, MMD values often remain flat or paradoxically decrease, signaling greater similarity when the distributions are actually diverging. Third, existing literature frequently uses invalid non-positive semi-definite kernels (such as total variation Gaussian kernels) or computationally prohibitive options. For instance, computing the Earth Mover's Distance kernel took 27 minutes on 1,000 graphs compared to just 6 to 21 seconds for linear and standard Gaussian kernels. Finally, raw MMD distances lack an inherent baseline scale, making it impossible to judge whether small numerical differences between models are meaningful.

These findings mean that reported performance benchmarks in graph generative modeling are often arbitrary artifacts of unprincipled parameter selection rather than genuine algorithmic superiority. For organizations investing in machine learning research or deploying generative models into production, relying on flawed evaluations creates significant risk of selecting suboptimal architectures and misallocating engineering resources.

To mitigate these pitfalls, the article recommends a clear set of practices: benchmark against a baseline scale by calculating MMD between training and test sets to define indistinguishable distributions; avoid computationally expensive Earth Mover's kernels and invalid total variation kernels in favor of efficient, positive semi-definite alternatives like Gaussian, Laplacian, or parameter-free linear kernels; and select kernel bandwidths and histogram parameters via controlled perturbation experiments by choosing the configurations that maximize the correlation between MMD and controlled structural noise. Future efforts should also explore direct graph kernels and alternative multivariate goodness-of-fit tests to eliminate vectorization entirely.

The findings provide high confidence regarding the sensitivity and computational trade-offs of MMD across standard synthetic benchmarks. However, the study focuses strictly on structural graph properties. Teams applying generative models to complex real-world graphs with domain-specific node or edge attributes should exercise caution and validate these evaluation procedures within their specific application domains.

ETH Zurich Helmholtz Munich Swiss Institute of Bioinformatics Technical University of Munich bipartite graphs generative model machine learning graph generative models evaluation metrics graph distributions

arXiv: 2106.01098

Paper: A Kernel Two-Sample Test, Arthur Gretton et al. (2012). This foundational text establishes the Maximum Mean Discrepancy (MMD) two-sample testing framework and universal kernel conditions that the source paper critically evaluates in the context of graph generation.
Paper: A Kernel Method for the Two-Sample Problem, Arthur Gretton et al. (2006). This seminal paper introduces the theoretical formulations and asymptotic properties of kernel MMD for comparing complex, high-dimensional distributions, forming the core statistical methodology scrutinized in the source.
Paper: Demystifying MMD GANs, Mikołaj Bińkowski et al. (2018). This work analyzes kernel selection, estimator bias, and evaluation metrics for generative models using MMD, providing essential context on MMD's practical behavior in generative modeling pipelines.
Paper: Weisfeiler-Lehman Graph Kernels, Nino Shervashidze et al. (2011). This paper establishes classic Weisfeiler-Lehman graph kernels and subtree feature extraction methods that are foundational to comparing graph distributions and direct graph similarity metrics.
Paper: Pitfalls of Graph Neural Network Evaluation, Oleksandr Shchur et al. (2018). This study exposes benchmarking vulnerabilities, parameter sensitivity, and evaluation pitfalls in graph learning, setting the stage for evaluating metric instability across graph models.

Paper: On Evaluation Metrics for Graph Generative Models, Rylee Thompson et al. (2022). This work directly extends the critique of graph generative model evaluation by demonstrating how randomly initialized graph neural networks overcome the blind spots and computational bottlenecks of traditional graph statistics.

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

Abstract

Graph generative models are a highly active branch of machine learning. Given the steady development of new models of ever-increasing complexity, it is necessary to provide a principled way to evaluate and compare them. In this paper, we enumerate the desirable criteria for such a comparison metric and provide an overview of the status quo of graph generative model comparison in use today, which predominantly relies on the maximum mean discrepancy (MMD). We perform a systematic evaluation of MMD in the context of graph generative model comparison, highlighting some of the challenges and pitfalls researchers inadvertently may encounter. After conducting a thorough analysis of the behaviour of MMD on synthetically-generated perturbed graphs as well as on recently-proposed graph generative models, we are able to provide a suitable procedure to mitigate these challenges and pitfalls. We aggregate our findings into a list of practical recommendations for researchers to use when evaluating graph generative models.

Topics

bipartite graphs generative model machine learning recommendation directed graphs weighted graph general graph

Keywords

graph generative models evaluation metrics graph distributions graph kernels Wasserstein distance graph perturbations Watts-Strogatz graphs Laplacian spectrum histogram model criticism

1 Introduction
2 Comparing graph distributions
3 Current state of graph generative model evaluation: MMD
3.1 Kernels & Descriptor functions
4 Issues with the current practice
4.1 Nuances of using MMD for graph generative model evaluation
4.2 Consequences of the choice of kernel
4.3 Effect of the choice of hyperparameters
5 How to use MMD for graph generative model evaluation
5.1 Selecting an appropriate kernel and hyperparameters
6 Conclusion
References
A Appendix
A.1 Kernels based on total variation distance
A.2 Experimental setup
A.3 Details on graph perturbations
A.4 Implementation details
A.5 Speed up trick
A.6 Experimental results
A.7 Alternative measures of correlation
A.8 Computational runtime of different kernels

Knowls

Knowl 1 — Perturbation-Based Kernel and Hyperparameter Selection for Graph Generative Model Evaluation
algorithm
To select a valid kernel $k$ , descriptor function $f$ , and hyperparameters (such as kernel bandwidth $\sigma$ and histogram bin count $n_{\text{bin}}$ ) without leaking information from candidate generative models, practitioners can optimize the correlation between MMD distance and synthetic perturbation intensity on the ground-truth graph set $\mathcal{G}^*$ .
Input: Reference graph set $\mathcal{G}^*$ , candidate kernels $\mathcal{K}$ , descriptor functions $\mathcal{F}$ , hyperparameter grid $\Theta$ , perturbation types $\mathcal{P}$ , perturbation parameter grids $A_P$ for each $P \in \mathcal{P}$
Output: Selected kernel $k^*$ , descriptor $f^*$ , and hyperparameter set $\theta^*$
for each perturbation type $P \in \mathcal{P}$ do
    for each perturbation intensity $\alpha \in A_P$ do
        Generate perturbed graph sample $\mathcal{G}_{P,\alpha} = P(\mathcal{G}^*, \alpha)$
    end for
    for each descriptor $f \in \mathcal{F}$ , kernel $k \in \mathcal{K}$ , and hyperparameter configuration $\theta \in \Theta$ do
        for each $\alpha \in A_P$ do
             $d_{\alpha} = \text{MMD}(f(\mathcal{G}^*), f(\mathcal{G}_{P,\alpha}); k, \theta)$
        end for
        Compute Pearson correlation $r(P, f, k, \theta) = \text{Corr}(\alpha, d_{\alpha})$
    end for
end for
Identify $(k^*, f^*, \theta^*) = \arg\max_{k, f, \theta} \frac{1}{|\mathcal{P}|}\sum_{P \in \mathcal{P}} r(P, f, k, \theta)$
return $k^*, f^*, \theta^*$
If domain knowledge indicates that a specific graph alteration is most critical (for instance, edge rewiring or node addition), $(k^*, f^*, \theta^*)$ can instead be chosen by maximizing the correlation for that single perturbation type.
Knowl 2 — Non-Positive Definiteness of the Total Variation Gaussian Kernel
theoretical result
Let $X = (x_1, \dots, x_d)$ and $Y = (y_1, \dots, y_d)$ be normalized histograms in $\mathbb{R}^d$ . The total variation distance between them is: $d_{\text{TV}}(X, Y) := \frac{1}{2} \sum_{i=1}^d |x_i - y_i|$ The metric space $\mathcal{X}_{\text{TV}}$ induced by $d_{\text{TV}}$ is not in $\text{CAT}(k)$ for any $k > 0$ , because geodesics between distinct points are non-unique. For example, between $x_1 = (1, 0, \dots, 0)$ and $x_2 = (0, 1, 0, \dots, 0)$ , multiple distinct shortest paths of length 1 exist.

Because every flat metric space is $\text{CAT}(0)$ and every $\text{CAT}(k)$ space is $\text{CAT}(l)$ for all $l > k$ , $\mathcal{X}_{\text{TV}}$ is non-flat. Consequently, the associated geodesic Gaussian kernel: $k(X, Y) := \exp\left(-\frac{d_{\text{TV}}(X, Y)^2}{2\sigma^2}\right)$ is not positive semi-definite (it is indefinite) and yields ill-defined results when employed within Maximum Mean Discrepancy (MMD).

A mathematically valid positive semi-definite kernel under the total variation distance is obtained by switching to the Laplacian formulation: $k_{\text{Lap}}(X, Y) := \exp\left(-\lambda d_{\text{TV}}(X, Y)\right)$ where $\lambda > 0$ .
Knowl 3 — Model Ranking Instability under Kernel and Hyperparameter Variation in MMD
empirical result
Evaluating graph generative models using Maximum Mean Discrepancy (MMD) on fixed descriptors produces unstable model rankings that change arbitrarily based on the choice of kernel and hyperparameters.

In empirical evaluations on standard benchmarks (Barabási-Albert, Community, Erdös-Rényi, Watts-Strogatz) using three popular models (GraphRNN, GRAN, and Graph Score Matching):
- Switching the kernel from Earth Mover's Distance (EMD) to a Radial Basis Function (RBF) kernel while holding kernel bandwidth $\sigma$ constant changes which model is ranked first on the Community dataset using degree distribution histograms.
- Varying the kernel bandwidth $\sigma$ across $10^{-5}$ to $10^5$ causes the best-performing model to switch across different ranges of $\sigma$ . Fixed $\sigma$ values reported in prior literature often lie far outside the peak discriminative region of the MMD curve.
- Jointly varying the descriptor histogram bin count $n_{\text{bin}}$ and kernel bandwidth $\sigma$ over a 2D grid allows any of the evaluated models to rank first depending on the specific $(n_{\text{bin}}, \sigma)$ combination chosen.
Knowl 4 — Failure of MMD to Monotonically Detect Graph Distribution Dissimilarity
empirical result
When reference graph datasets (Barabási-Albert, Community, Erdös-Rényi, and Watts-Strogatz) are subjected to systematically increasing levels of structural perturbation (random edge insertion, deletion, rewiring, and node addition), MMD fails to monotonically increase under default or uncalibrated kernel and parameter choices.

Across multiple evaluated configurations:
- MMD distances frequently remain flat across low-to-moderate perturbation magnitudes, only registering non-zero distance when the perturbation reaches extreme levels (e.g., above 80% modification).
- For specific descriptor functions like the clustering coefficient histogram, MMD distances can decrease as the perturbation magnitude increases, yielding a negative Pearson correlation between actual graph dissimilarity and computed MMD distance.
- The response profile of MMD as a function of perturbation magnitude varies drastically in shape across different bandwidths $\sigma$ and kernels (EMD, TV, RBF), confirming that MMD cannot be assumed to measure structural divergence reliably without explicit parameter selection.
Knowl 5 — Empirical Baseline Calibration for MMD Scale Using Training-to-Test Graph Distances
model/method
Because raw Maximum Mean Discrepancy (MMD) values have no inherent, absolute scale, small numerical values (e.g., $5.2 \times 10^{-8}$ ) cannot be interpreted in isolation or compared directly across different kernels, descriptors, or bandwidths.

To establish an interpretable reference scale:
1. Compute the empirical MMD between the ground-truth training graph split $\mathcal{G}_{\text{train}}$ and the held-out test graph split $\mathcal{G}_{\text{test}}$ : $\text{MMD}_{\text{baseline}} = \text{MMD}(f(\mathcal{G}_{\text{train}}), f(\mathcal{G}_{\text{test}}))$
2. Report $\text{MMD}_{\text{baseline}}$ alongside the generative model evaluation scores $\text{MMD}(f(\mathcal{G}_{\text{gen}}), f(\mathcal{G}_{\text{test}}))$ .
This training-to-test baseline represents the expected MMD distance between two indistinguishable samples drawn from the true underlying graph distribution, providing an empirical lower bound for assessing whether a generative model's score is genuinely competitive.
Knowl 6 — Descriptor-Based Vectorial Maximum Mean Discrepancy for Graphs
definition
The standard evaluation framework for graph generative models compares an empirical set of reference graphs $\mathcal{G}^* = \{G_1^*, \dots, G_m^*\}$ and generated graphs $\mathcal{G} = \{G_1, \dots, G_n\}$ by mapping each graph $G = (V, E)$ to a vector representation in $\mathbb{R}^d$ via a descriptor function $f: G \to \mathbb{R}^d$ , followed by an MMD calculation.

Three standard descriptor functions are:
1. Degree distribution histogram: Counts of vertex degrees $\deg(v)$ for $v \in V$ , zero-padded to a maximum degree dimension $d$ and normalized to sum to 1.
2. Clustering coefficient histogram: Binned values of local clustering coefficients: $C(v) := \frac{2|\{(u, w) \in E \mid u, w \in \mathcal{N}(v)\}|}{\deg(v)(\deg(v) - 1)}$ for $v \in V$ with $\deg(v) \ge 2$ , where $C(v) \in [0, 1]$ .
3. Laplacian spectrum histogram: Binned eigenvalues $0 \le \lambda_1 \le \lambda_2 \le \dots \le \lambda_{|V|} \le 2$ of the normalized graph Laplacian matrix $\mathcal{L} := I - D^{-1/2} A D^{-1/2}$ , where $A$ is the adjacency matrix, $D$ is the degree matrix ( $D_{ii} = \deg(v_i)$ ), and $I$ is the identity matrix.
Given vector sets $X = \{f(G_1), \dots, f(G_n)\}$ and $Y = \{f(G_1^*), \dots, f(G_m^*)\}$ , the biased empirical MMD estimator with kernel $k: \mathbb{R}^d \times \mathbb{R}^d \to \mathbb{R}$ is: $\text{MMD}^2(X, Y) := \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n k(x_i, x_j) + \frac{1}{m^2} \sum_{i=1}^m \sum_{j=1}^m k(y_i, y_j) - \frac{2}{nm} \sum_{i=1}^n \sum_{j=1}^m k(x_i, y_j)$
Knowl 7 — Desiderata for Graph Generative Model Comparison Metrics
definition
A metric or pseudo-metric $d(\mathcal{G}, \mathcal{G}')$ comparing two graph distributions $\mathcal{G}$ and $\mathcal{G}'$ must satisfy three primary criteria:
1. Expressivity: If $\mathcal{G}$ and $\mathcal{G}'$ do not originate from the same distribution, the metric must be able to detect the difference. Specifically, $d(\mathcal{G}, \mathcal{G}')$ must be monotonically increasing as $\mathcal{G}$ and $\mathcal{G}'$ become progressively more dissimilar.
2. Robustness: The metric must be stable under minor perturbations to $\mathcal{G}$ . Metric fluctuations should ideally be upper-bounded by a function of the perturbation amplitude, preventing inherent training stochasticity from creating large evaluation variances.
3. Efficiency: The evaluation metric must be computationally scalable with respect to both the number of graphs in the sample sets and the size (number of vertices and edges) of individual graphs.
Knowl 8 — Distance Matrix Caching for Accelerated MMD Bandwidth Grid Search
model/method
When tuning the kernel bandwidth parameter $\sigma$ for Gaussian (RBF) kernels $k_{\text{RBF}}(x, y) = \exp(-\|x - y\|_2^2 / 2\sigma^2)$ or Laplacian kernels $k_{\text{Lap}}(x, y) = \exp(-\|x - y\|_2 / \sigma)$ over a parameter grid $\sigma \in \{10^{-5}, \dots, 10^5\}$ , direct recomputation of pairwise kernel matrices at each step is redundant.

Because both kernels share the underlying Euclidean distance matrix, pairwise distances can be precomputed and cached once:
1. Precompute pairwise distance matrices: $D_{XX} = (\|x_i - x_j\|_2)_{i,j=1}^n, \quad D_{YY} = (\|y_i - y_j\|_2)_{i,j=1}^m, \quad D_{XY} = (\|x_i - y_j\|_2)_{i=1,j=1}^{n,m}$
2. For each candidate $\sigma$ in the grid, compute the kernel matrices via vectorized point-wise operations directly on the cached matrices (e.g., $K_{XY} = \exp(-D_{XY}^2 / 2\sigma^2)$ ) and sum their entries to obtain MMD.
This eliminates repeated distance calculations and enables rapid evaluation across hundreds of candidate bandwidths.
Knowl 9 — Synthetic Graph Perturbation Models for Metric Validation
experimental setup
To evaluate whether graph comparison metrics satisfy expressivity and robustness across controlled degrees of dissimilarity, an unperturbed graph $G = (V, E)$ is subjected to four parametric perturbation processes:
1. Random Edge Addition: For each non-adjacent vertex pair $(v_i, v_j) \notin E$ ( $v_i \neq v_j$ ), sample $x_{ij} \sim \text{Bernoulli}(p_{\text{add}})$ . If $x_{ij} = 1$ , add $(v_i, v_j)$ to $E$ .
2. Random Edge Removal: For each existing edge $e_i \in E$ , sample $x_i \sim \text{Bernoulli}(p_{\text{remove}})$ . If $x_i = 1$ , remove $e_i$ from $E$ .
3. Random Edge Rewiring: For each edge $e_i = (u, v) \in E$ , sample $x_i \sim \text{Bernoulli}(p_{\text{rewire}})$ . For edges with $x_i = 1$ , sample $y_i \sim \text{Bernoulli}(0.5)$ to choose which vertex of $e_i$ to keep, select a replacement vertex uniformly at random from $V \setminus e_i$ (avoiding self-loops and duplicate edges), remove $e_i$ , and add the new rewired edge.
4. Random Connected Node Addition: Introduce $n$ new vertices $V^* = \{v_{|V|+1}, \dots, v_{|V|+n}\}$ . For each $v_i \in V$ and $v_j \in V^*$ , sample $x_{ij} \sim \text{Bernoulli}(p_{\text{connect\_node}})$ and add edge $(v_i, v_j)$ if $x_{ij} = 1$ .
Knowl 10 — Computational Scaling and Runtime Disparity Among Graph Kernels in MMD
empirical result
Empirical runtime comparisons on Erdös-Rényi graph datasets ( $p=0.3$ ) demonstrate extreme computational disparities between Earth Mover's Distance (EMD), RBF, and linear kernels when used inside MMD over degree distribution histograms:
- At baseline settings ( $n_{\text{graphs}} = 100$ , $n_{\text{nodes}} = 100$ , $n_{\text{bins}} = 100$ ), the EMD-based kernel requires 50 to 140 times longer CPU runtime than the RBF and linear kernels, respectively.
- Increasing the number of graphs to $n_{\text{graphs}} = 1,000$ (with $n_{\text{nodes}} = 100, n_{\text{bins}} = 100$ ) increases EMD runtime to 27 minutes (1,620 seconds), compared to 21 seconds for RBF and 6 seconds for the linear kernel.
- Extrapolating to $n_{\text{graphs}} = 10,000$ , computing MMD with an EMD kernel requires an estimated 50 hours for a single parameter evaluation, making it computationally impractical for large-scale graph generative model benchmarking.

Coverage note — None was omitted; the extracted knowls fully cover the proposed evaluation desiderata, theoretical non-positive definiteness proof for TV Gaussian kernels, empirical failure modes and ranking sensitivities, runtime scaling benchmarks, caching acceleration, and perturbation-based parameter selection methodology.

References

1.Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O’Bray, and Bastian Rieck. Graph kernels: State-of-the-art and future challenges. Foundations and Trends in Machine Learning, 13 (5–6):531–712, 2020.
2.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. Bioinformatics, 22(14):e49–e57, 2006.
3.Wacha Bounliphone, Eugene Belilovsky, Matthew B. Blaschko, Ioannis Antonoglou, and Arthur Gretton. A test of relative similarity for model selection in generative models. In International Conference on Learning Representations, 2016.
4.Martin R. Bridson and André Haefliger. The model spaces $M^n_\kappa$ . In Metric Spaces of Non-Positive Curvature, pp. 15–31. Springer, Berlin, Heidelberg, 1999. ISBN 978-3-662-12494-9. doi: 10.1007/978-3-662-12494-9_2.
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.
6.Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
7.Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2302–2312. PMLR, 13–18 Jul 2020.
8.Aasa Feragen, François Lauze, and Søren Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3032–3042, 2015.
9.Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain-agnostic labeled graph generation. In Proceedings of The Web Conference 2020, WWW ’20, pp. 1253–1263. Association for Computing Machinery, 2020.
10.Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex J. Smola. A kernel method for the two-sample-problem. In B. Schölkopf, J. C. Platt, and T. Hoffman (eds.), Advances in Neural Information Processing Systems 19, pp. 513–520. MIT Press, 2007.
11.Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723–773, 2012a.
12.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 F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012b.
13.Mikhail Gromov. Hyperbolic groups. In S. M. Gersten (ed.), Essays in Group Theory, pp. 75–263. Springer, Heidelberg, Germany, 1987.
14.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. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6626–6637. Curran Associates, Inc., 2017.
15.Ana Justel, Daniel Peña, and Rubén Zamar. A multivariate Kolmogorov-Smirnov test of goodness of fit. Statistics & Probability Letters, 35(3):251–259, 1997. ISSN 0167-7152.
16.Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
17.James R Lloyd and Zoubin Ghahramani. Statistical model criticism using kernel two sample tests. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
18.Lu Mi, Hang Zhao, Charlie Nash, Xiaohan Jin, Jiyang Gao, Chen Sun, Cordelia Schmid, Nir Shavit, Yuning Chai, and Dragomir Anguelov. Hdmapgen: A hierarchical graph generative model of high definition maps. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4227–4236, June 2021.
19.Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4474–4484. PMLR, 26–28 Aug 2020. URL http://proceedings.mlr.press/v108/niu20a.html.
20.Marco Podda and Davide Bacciu. Graphgen-redux: a fast and lightweight recurrent model for labeled graph generation, 2021.
21.Allen J. Schwenk. Almost all trees are cospectral. In Frank Harary (ed.), New Directions in the Theory of Graphs, pp. 275–307. Academic Press, 1973.
22.Danica J. Sutherland, Hsiao-Yu Tung, Heiko Strathmann, Soumyajit De, Aaditya Ramdas, Alex Smola, and Arthur Gretton. Generative models and model criticism via optimized maximum mean discrepancy. In International Conference on Learning Representations, 2017.
23.Rylee Thompson, Boris Knyazev, Elahe Ghalebi, Jungtaek Kim, and Graham W. Taylor. On evaluation metrics for graph generative models. In International Conference on Learning Representations, 2022.
24.Edwing R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241–272, 2003.
25.Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. Nature, 393(6684):440–442, 1998.
26.Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5708–5717. PMLR, 2018.
27.Zhiping Zeng, Anthony K. H. Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25–36, August 2009. doi: 10.14778/1687627.1687631.
28.Liming Zhang, Liang Zhao, Shan Qin, Dieter Pfoser, and Chen Ling. Tg-gan: Continuous-time temporal graph deep generative models with time-validity constraints. In Proceedings of the Web Conference 2021, WWW ’21, pp. 2104–2116. Association for Computing Machinery, 2021.

Citation

MLA

O'Bray, L., et al. “Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions”. arXiv, 2021, http://arxiv.org/abs/2106.01098v3.

APA

O'Bray, L., Horn, M., Rieck, B., & Borgwardt, K. (2021). Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions. arXiv. http://arxiv.org/abs/2106.01098v3

Chicago

O'Bray, L., M. Horn, B. Rieck, and K. Borgwardt. 2021. “Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions”. arXiv. http://arxiv.org/abs/2106.01098v3.

Harvard

O'Bray, L. et al. (2021) “Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2106.01098v3.

Vancouver

1. O'Bray L, Horn M, Rieck B, Borgwardt K (2021) Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions. arXiv

BibTeX

@article{obray2021evaluation,
  title = {Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions},
  author = {O'Bray, Leslie and Horn, Max and Rieck, Bastian and Borgwardt, Karsten},
  year = {2021},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2106.01098v3},
  eprint = {2106.01098}
}

Metadata:arXiv

Access the Paper

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

Open PDF

License: Authors

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Perturbation-Based Kernel and Hyperparameter Selection for Graph Generative Model Evaluation

Knowl 2 — Non-Positive Definiteness of the Total Variation Gaussian Kernel

Knowl 3 — Model Ranking Instability under Kernel and Hyperparameter Variation in MMD

Knowl 4 — Failure of MMD to Monotonically Detect Graph Distribution Dissimilarity

Knowl 5 — Empirical Baseline Calibration for MMD Scale Using Training-to-Test Graph Distances

Knowl 6 — Descriptor-Based Vectorial Maximum Mean Discrepancy for Graphs

Knowl 7 — Desiderata for Graph Generative Model Comparison Metrics

Knowl 8 — Distance Matrix Caching for Accelerated MMD Bandwidth Grid Search

Knowl 9 — Synthetic Graph Perturbation Models for Metric Validation

Knowl 10 — Computational Scaling and Runtime Disparity Among Graph Kernels in MMD

References

Citation

BibTeX

Access the Paper