Evaluation Metrics for Graph Generative Models: Problems, Pitfalls, and Practical Solutions
Authors: Leslie O'Bray
Max Horn
Bastian Rieck
Karsten Borgwardt
Venue: ICLR 2022 Spotlight (2022)
Keywords: graph generative models
model evaluation

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.

Published as a conference paper at ICLR 2022
EVALUATION METRICS FOR GRAPH GENERATIVE MODELS: PROBLEMS, PITFALLS, AND PRACTICAL SOLUTIONS
Lestie O'Bray-.21, Max Horm Bastian Ricck1.2.3.4. and Karsten Borgwardt
l DDpartment of Biosystems Science and Engineering, ETH Zürich, Switzerland SIB Swiss Institute of Bioinformatics, Switzerland IInttitute AI for Health, Helmholtz Munich, Germany
"Technical University of Munich, Germany
These authors contributed equally. These authors jointly supervised this work.
ABSTRACT
Graph generative models are highly active branch of machine learning. Given the steady development of new models of ever-increasing complexity, it is nec- essary to provide a principled way to evaluate and compare them. In this paper, we enumerate the desirable criteria for such comparison metric and provide an overview the status quo of graph generative model comparison in use today, which predominantly relies on the maximum mean discrepancy (MMD). We per- form a systematic evaluation of MMD in the context of graph generative model comparison, highlighting some of the challenges and pitfalls researchers inadver- tently may encounter. After conducting a thorough analysis of the behaviour of MMD on wynthetically-geeeaaie
perturbed graphs as well as on recently- proppssed 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.
1 INTRODUCTION
Graph generative models have become active research branch, making it possible to generalise structural patterns inherent to graphs from certain domains such as chemoinformatics and actively synthesise new graphs (Liao et al., 2019). Next to the development of improved models, their evaluation is crucial. This is a well-studied issue in other domains, leading to metrics such as the 'Fréchet Inception Distance' (Heusel et al., 2017) for comparing image-based based generative models. Graphs, however, pose their own challenges, foremost among them being that an evaluation based on visualisations, i.e. on perceived differences, is often not possible. In addition, virtually all relevant structural properties of graphs exhibit spatial invariances, e.g. connected components and cycles are invariant with respect to rotations- that have be taken into account by comparison metric.
While the community has largely gravitated towards a single comparison metric, the maximum mean discrepancy (MMD) (Chen al., 2021; Dai al., 2020: Goyal et al., 2020; Liao al., 2019; Mi et al., 2021; Niu et al., 2020; Podda & Bacciu, 2021; You et al., 2018; Zhang et al., 2021), neither its expressive power nor its other properties have been systematically investigated in the context of graph generative model comparison. The goal of this paper is to provide such an investigation, starting from first principles by describing the desired properties an overview of what is done in practice today, and systemically assessing MMD's behaviour using recent graph generative models. We highlight some of the caveats and shortcomings of the existing status quo, and provide researchers with practical recommendations to address these issues. We note here that our investigations focus on assessing the structural similarity of graphs, which is a necessary first step before can jointly assess graphs based structural and attribute similarity. This paper purposefully refrains from developing its own graph generative model to avoid any bias in the comparison.
such comparison metric, providing

---

Published as a conference paper at ICLR 2022
Rd
Clustering
Degree distribution
Laplacian spectrum
Graphs
Descriptor functions
Representations
Evaluator function
Figure I: An overview of the workflow used to evaluate graph generative models, as used, e.g., in Liao et al. (2019); Niu et al. (2020); You al. (2018): given distribution of graphs, set of descriptor functions is employed to map each graph to a nigh-dimensional representation These representations are then compared (with reference distribution with each other) using an evaluator function called the maximum mean discrepancy (MMD). In principle, MMD does not require the vectorial representation, but find that this is the predominant in the context of graph generative model evaluation.
R
2 COMPARING GRAPH DISTRIBUTIONS
In the following, we will deal with undirected graphs. We denote such graph as G = (V, E) with vertices V and edges E. We treat graph generative models as black-box models, each of which results in set of graphs G. The original empirical distribution of graphs is denoted as g". Given models M2M,.M...... with generated sets of graphs assess which model is better fit, i.c. which distribution is closer to G*, This requires the use of a (pseudo- metrrc dl..,)) :) to assess the dissimilarity between G and generated graphs. We argue that the desiderata of any such comparison metric are as follows:
}. the goal of generative model evaluation
1. Expressivity: if G and g' do not arise from the same distribution, a suitable metric should be able detect this. Specifically, dgg, g*) should be monotonically increasing as G and G' become increasingly dissimilar.
2. Robustness: if a distribution G is subject to a perturbation, a suitable metric should be robust to small perturbations. Changes the metric should be ideally upper-bounded by function of the amplitude of the perturbation. Robust metrics are preferable because of the inherent stochasticity of training generative models.
3. Efficiency: model comparison metrics should be reasonably fast to calculate; though model evaluation a post hoc analysis, a metric should scale well with an increasing number graphs and an increasing size of said graphs.
While there are many ways to compare two distributions, ranging from statistical divergence measures to proper metrics in the mathematical sense, the comparison of distributions of graphs exacerbated by the fact that individual graphs typically differ in their cardinalities and are only described up to permutation. With distances such as the graph edit distance being NP-hard general (Zeng al., 2009), which precludes using them an efficient metric, potential alternative is provided by using descriptor functions. descriptor function. f maps a graph G to an auxiliary representation in some space Z. The problem of comparing generated distribution & (G1,...,G,, to the original distribution g' = {Gi..... G thus boils down to comparing the images f(G) := C Z and f(g*) C Z by any preferred statistical distance in 2 (see Figure 1).
CURRENT STATE OF GRAPH GENERATIVE MODEL EVALUATION: MMD
Of particular interest in previous literature is the case of 2 Rd and using the maximum mean discrepancy dMMD(:s)) as a metric. MMD is one the most versatile and expressive options available for comparing distributions of structured objects such graphs (Borgwardt al., 2006;
Formally, the output also be multiset, because graphs allowed to be duplicated.
2

---

Published as a conference paper at ICLR 2022
Table 1: The kernels & parameters chosen by three graph generative models for the MMD calculation.
Model
Kernel
Parameter choice and Clustering
Degree
Laplacian
Model A
EMD exp (W 22)))/220
I, Tibia maxdegree a = 0.1, Abbi = 100
N/A
Model B
TV
exp
20 exp(
dry (1aa)
1. Bbin
maxdegree a 0.1. 100 1.
200
Model C
RBF
||=- v1f 1/20))
1, Tiin maxdegroe
a = 0.1, Abin 100
= 200
Gretton et al., 2007), providing also a principled way to perform two-sample tests (Bounliphone et al., 2016; Gretton et al., 2012a 12:: Lloyd & Ghahramani, 2015). It enables the comparison of two statistical distributions by means of kernels, i.e. similarity measures for structured objects. Letting X' refer to a non-empty set, function k: X x X - R is a kernel if k(2;, zÿ} k(r,. xx)) for I;, E X and Ei, 0 x,) 2 0 for r,, 2, E X' and C, R. MMD uses such a kernel function to assess the distance between two distributions. Given n2 samples X = {xi...... In } S X' and m samples y (u1,-.., Ym S X, the biased empirical estimate of the MMD between X and Y is obtained as
m
2 7LT
MMD?
(X,Y) MMD3(X,Y)
n2 Σ k(s, 23)
k(y,, )1)
k(z,, (1)
m
Since MMD is known to be a metric on the space of probability distributions under certain conditions, Eq. is often treated metric as well (Liao al., 2019; Niu et al., 2020; You al., 2018). We use the unbiased empirical estimate of MMD (Gretton et al., 2012a, Lemma 6) in our experiments, which removes the self-com comparisnn terms in Equation MMD has been adopted by the community and the current workflow includes two steps: (i) choosing a descriptor function f as described above, and (ii) choosing a kernel on Rd such as an RBF kernel. One then evaluates (9M 9*) == MMD (G)) f("")) for sample of graphs G. Given multiple distributions (91, G2... h. the values dMMD (G., 9*) can be used to rank models: smaller values are assumed to indicate a larger agreement with the original distribution G*. We will now describe this procedure in more detail and highlight some its pitfalls.
3.1 KERNELS& & DESCRIPTOR FUNCTIONS
Before calculating the MMD distance between two samples of graphs, we need to define both the kernel function k and the descriptor function f that will convert a graph G to a representation in Z Rd, for use in the MMD calculation in Eq. We observed variety of kernel choices in the existing literature. In fact, in three of the most popular graph generative models in use today, which we explore detail this paper, different kernel was chosen for each one. These include a kernel using the first Wasserstein distance (EMD), total variation distance (TV), and the radial basis function kernel (RBF), and are listed in Table 1. In the current use of MMD, a descriptor function f is used to create vectorial representation of graph for use in the kernel computation. We find that several descriptor functions are commonly employed, either based on summary statistics of a graph, such as degree distribution histogram and clustering coefficient histogram, the graph, such as the Laplacian spectrum histogram. While several papers also consider the orbit as descriptor function, do not consider it in depth here due to its computational complexity, which violates the "efficiency" property from our desiderata. We will now provide brief explanations of these prominent descriptor functions.
based on spectral properties of
Degree distribution histogram. Given a graph G = (V, E), we obtain a histogram by evaluating deg(v) for V. where position i of the resulting histogram is the number of vertices with degree i. Assuming a maximum degree d and extending the histogram with zeros whenever necessary, we obtain a mapping f: G - Rd. This representation has the advantage of being easy to calculate and easy to compare; by normalising it (so that it sums to 1), we obtain a size-invariant descriptor.
We will follow this convention in this paper and refer Eq. as distance.
3

---

Published as a conference paper at ICLR 2022
Clustering coefficient. The (local) clustering coefficient of vertex is defined as the fraction of edges within its neighbourhood divided by the number of all possible edges between neighbours, i.e.
C(u) = 2 ( vj)) E vs E N(e) V E EN()H
(2)
(cg())(deg()) -
The value of C(v) E [0. measures to what extent vertex e forms clique (Watts & Strogatz, 1998). The collection of all clustering coefficients of a graph can be binned and converted into a histogram in order to obtain a graph-level descriptor. This function is also easy to calculate but is inherently local; graph consisting of disconnected cliques or a fully-connected graph cannot be distinguished, for example.
Laplacian spectrum histogram. Spectral methods involve assigning a matrix to a graph G. whose spectrum, i.e. its eigenvalues and eigenvectors, is subsequently used characterisation of G. Let A refer to the adjacency matrix of G, with A, = 1 if and only if vertices v; and vy are connected by an edge in G (since G is undirected, A is symmetricc. The normalised graph Laplacian is defined as f I D AD- 2, where I denotes the identity matrix and D refers to the degree matrix, i.e. D = (eg( ) for a vertex U and Dig = 0 for * j. The matrix L is real-valued and symmetric, so is diagonalisable with full set of cigenvalues and eigenvectors. Letting À S A2 S ... refer to the eigenvalues of L, we have 0 < X S 2 (Chung, 1997, Chapter 1, Lemma 1.7). This boundedness lends itself naturally to a histogram representation (regardless of the size of G), making it possible to bin the eigenvalues and use the resulting histogram as simplified descriptor of a graph. The expressivity of such a representation determined by their spectrum is still open (van Dam & Haemers, 2003) and has only been partially answered in the negative for certain classes of graphs (Schwenk, 1973).
not clear a priori; the question of whether graphs are fully
4 ISSUES WITH THE CURRENT PRACTICE
Common practice in graph generative model papers is MMD by fixing a kernel and parameter values for the descriptor functions and kernel, and then assessing the newly-proposed model as well as its competitor models using said kernel and parameters. Authors chose different values of for the different descriptor functions, but to the best of our knowledge, all parameters are set to fixed value a priori without any selection procedure. MMD were able to give results and rank different models in stable way across different kernel and parameter choices, this would be inconsequential. However, as our experiments will demonstrate, the results of MMD are highly sensitive to such choices and can therefore lead to an arbitrary ranking of models.
Subsequently, we use three current real-world models, GraphRNN (You et al., 2018), GRAN (Liao et al.. 2019), and Graph Score Matching (Niu et al., 2020). We ran the models using the author- provided implementations to generate new graphs on the Community, Barabási-Alleet Rényi, and Watts-Strogatz graph datasets, and then calculated the MMD distance between the generated graphs and the test graphs, using the different (i) kernels that they used (EMD, TV, RBF), (ii) descriptor functions (degree histogram, clustering coefficient histogram, and Laplacian spectrum), 10y) }). For simplicity, we will refer to the parameter in
Erdös-
and (iii) parameter ranges (a, À E (10-5 all kernels as a. We purposefully refrained from using model names, preferring instead 'A. B, C' in order to focus on the issues imposed by such an evaluation, rather than providing a commentary on the performance of specific model.
In the following, we will delve deeper into issues originating from the individual components of the graph generative model comparison in use today. Due to space constraints, examples are provided on individual datasets; full results across datasets are available in Appendix A.6.
4.1 NUANCES OF USING MMD FOR GRAPH GENERATIVE MODEL EVALUATION
While MMD may seem like a reasonable first choice as a metric for comparing distributions of graphs, it is worth mentioning two peculiarities of such a choice and how authors are currently applying it in this context. First, MMD was originally developed as an approach to perform two-sample testing on structured objects such as graphs. As such, its suitability was investigated in that context, and not in that of evaluating graph generative models. This warrants an investigation of the implications of "porting" such method from one context another.
4

---

Published as a conference paper at ICLR 2022
MMD Distance Original Graphs
MMD Distance to Original Cimphe
10
190
Model
Number of Bins
370
550
Model
750
910
15 8e 7c62 5e-00 5e-02
4e104
Perturatton
Perturbation
(a)
(b)
(C)
Figure 2: Figure 2a shows the ideal behaviour of graph generative model evaluator: as two distributions of graphs become increasingly dissimilar, e.g. via perturbations, the metric should grow proportionally. Figure 2b shows the behaviour of the current choices in reality; each line represents the normalized MMD for a given kernel and parameter combination. A cautious choice of kernel and parameters is needed in order obtain metric with behaviour similar to Figure 2a. Each square in Figure 2c shows which model performs best (out of A, B, and C) over grid of hyperparameter combinations of and number of bins in the histogram. Any model can rank first with an appropriate hyperparameter selection, showcasing the sensitivity of MMD to the hyperparameter choice.
The second peculiarity worth mentioning is that MMD was groundbreaking for its ability to compare distributions of structured objects by means of kernel, thus bypassing the need to employ an intermediate vector representation. Yet, in its current application, the graphs are first being vectorised, and then MMD is used compare the vectors. MMD is not technically required in this case: any statistical method for comparing vector distributions could be employed, such as Optimal Transport (OT). While the use of different evaluators besides MMD for assessing graph generative models is an interesting area for future research, we focus specifically on MMD, since this is what is use today, and now highlight two practical issues that can arise from using MMD in this context.
MMD's ability to capture differences between distributions is kernel- and parameter- dependent. As two distributions become sufficiently dissimilar, we find that their distance should monotonically increase as function of their dissimilarity. While can construct specific scenarios in which two distributions become farther apart but the distance does not monotonically increase (e.g.. removing edges from a triangle-free graph, and using the clustering coefficient as the descriptor func- tion), in such cases, the specific choice of descriptor function f is crucial to ensure that f can capture differences in distribution. However, not guaranteed that MMD will monotonically increase as two distributions become increasingly dissimilar. Figure 2b depicts this behaviour when focusing on a single descriptor function, the clustering coefficient, with each line representing unique kernel and parameter choice (see Appendix A.6 for the full results for other datasets and descriptor functions). We subject an original set of graphs to perturbations of increasing magnitude and then measured the MMD distance to the original distribution. Despite both distributions becoming progressively dissimilar by experimental design, a large number of kermel/paramette configurations fail to capture this, showing that MMD is highly sensitive to this choice. In many instances, the distance remains nearly constant, despite the increased level of perturbation, until the magnitude the perturbation reaches extraordinarily high level. In some cases, observe that the distance the degree of perturbation increases, suggesting that the original data set and its perturbed variant more similar. We also find that the MMD values function of the degree of perturbation highly sensitive to the kernel and parameter selection, as evidenced by the wide range of different curve shapes observed in Figure 2b.
decreases as
MMD has no inherent scale. Another challenge with MMD is that since current practice works with the raw MMD distance, as opposed to p-values, as originally proposed Gretton et al. (2012a), there is inherent scale of the MMD values. It is therefore difficult to assess whether the smaller MMD distance of one model is substantially improved when compared to the MMD distance of another model. For instance, suppose that the MMD distance of one model is 5.2 x 10-8, Is this
5

---

Published as a conference paper at ICLR 2022
ModdA MradiC
MadiA
MaldA
MaldA
MMD
MMD
MMDD
0,0
800
15
10
37 102
13
10
37
102
13
35
09
(a) EMD, degree
(b) RBF, degree
(c) EMD, clust. cocf.
(d) RBF, clust. coef.
Figure 3: This shows the MMD distance to the test set of graphs for three recent graph generative models (whose names we intentionally omitted) on the Community Graphs dataset for different descriptor functions and kernels. MMD) requires the choice of kernel and kernel parameters. Each subfigure shows MMD (lower is better) along a range of values of a (reported on a log scale), with the bar underneath indicating which model ranks first for the given value of a. The grey line indicates the a chosen by the authors. Subfigures 3a and 3b show how simply switching from the EMD to the RBF kernel (holding constant) can change which model performs best; Subfigures 3e and 3d show how the choice of a by the authors misses the area of maximum discrimination of MMD.
meaningfully better model than one whose MMD distance is 4.6 x 10- This is further compounded by the choice of kernel and parameter, which also affects the scale MMD. Since common heuristics can lead to a suboptimal choice of for MMD (Sutherland et al., 2017), authors may obtain an arbitrarily low value of MMD, as seen in Figure 3c and 3d. As MMD results are typically reported just in table, the lack of a scale hinders the reader's ability to effectively assess model's performance.
4.2 CONSEQUENCES OF THE CHOICE OF KERNEL
MMD requires the choice of a kernel function, yet there is no agreed-upon method to select one. We find that each of the three models considered in this paper choose different kernel for its evaluation, as evidenced in Table 1. There are several potential issues with the current practice, which we will subsequently discuss, namely (i) the selected kernel might be computationally inefficient to compute, as is the case for the previously-used Earth Mover's 's Distance (EMD) kernel function, (ii) the use of positive definite kernel functions is limitation, with previous work employing functions that are nor valid kernels, and (iii) finally, the kernel choice may result in arbitrary rankings, and there is currently little attention paid to this choice.
Computational cost of kernel computation. Issue (i) might prevent evaluation metric to be used in practice, thus stymieing graph generative model development. While the choice of a kernel using the first Wasserstein distance is valid choice, it is extremely slow compute, as noted by Liao et al. (2019). From this perspective, it violates the third quality of our desiderata: efficiency.
Kernels need to be p.s.d. To reduce the aforementioned computational costs, previous work (Liao et al., 2019) used a kernel based on the total variation distance between histograms, which has since been used in subsequent publications as one of the ways to evaluate different models. As we show in Appendix A. this approach leads to an indefinite kernel (i.e. the kernel is neither positive definite nor negative definite), whose behaviour in the context of MMD is not well-defined. MMD necessitates the use of p.s.d. kernels, and care must be taken when it comes to interpreting the respective results.
Arbitrary ranking based on kernel choice. Issue (iii) relates to the fact that changing the kernel can lead to different results of model evaluation, which is problematic since each paper we considered used a different kernel. For instance, with the degree distribution as the graph descriptor function, simply changing the choice of kernel from EMD to RBF (while holding the parameters constant) leads to a different ranking of the models, which can be seen in Figure 3a- Figure 3b, where the best performing model changes merely by changing the kernel choice (!). This type of behaviour is highly undesired and problematic, as it implies that model performance (in terms of the evaluation) can be improved by choosing different kernel.

---

Published as a conference paper at ICLR 2022
4.3 EFFECT OF THE CHOICE OF HYPERPARAMETERS
While the choice of which kernel to use in the MMD calculation is itself an priori design choice without clear justification, it is further exacerbated by the fact that many kernels require picking parameters, without any clear process by which to choose them. To the best of our knowledge, this selection of parameters glossed over in publications at present." For instance, Table shows how authors are setting the value of a differently for different descriptor functions, yet there is no discussion nor established best practice of how such parameters were or should be set. Hyperparameter selection is known to be crucial issue in machine learning that mandates clear selection algorithms in order to avoid biasing the results. the choice of parameters- similar to the choice of kernel- no bearing the outcome, this would not be problematic, but our empirical experiments prove that drastic differences in model evaluation performance can occur.
Arbitrary ranking based on parameter choice. The small colour bars underneath each plot of Figure 3 show the model that achieves the lowest MMD for a given value of o. Changes in colour highlight a sensitivity to specific parameter values. Even though the plots showing MMD seem to have a general trend of which model is best in the peak of the curves, in the other regions of o, the ranking switches, with the effect that a different model would be declared "best." " This is particularly the case in Subfigures 3a, 3c, and 3d, where Model B appears to be the best, yet for much of a, different model ranks first. This sensitivity is further exacerbated by the fact that some descriptor functions require parameter choice well, such as the bin size, Rhin- for histogram. Figure 2c shows how the best-ranking model on the Barabási-A Alberr Graphs is entirely dependent upon the choice of parameters (Abin 0). The colour in each grid cell corresponds to the best-ranking model for given a and Mbai; we find that this is wildly unstable across both Abin and σ. The consequence of this alarming: any model could rank first if the right parameters are chosen.
Choice of a by authors does not align with maximum discrimination in MMD. Figures 3c and 3d show MMD for different values of a with the clustering coefficient descriptor function in the Community Graphs dataset for Models A, B and C. The value of a as selected by the authors (without justification or discussion) is indicated by the grey line; however, this choice corresponds to regions of low activity in the MMD curve, suggesting a poor parameter choice. While Model seems to be the clear winner, the choice of a by the authors resulted in Model A having the best performance. Furthermore, is not clear that choosing the same a across different kernels, as is currently done, makes sense; whereas = 10 would be sensible for EMD in Figure 3c, for the Gaussian kernel in Figure 3d, such a choice too far beyond the discriminative peak.
5 HOW TO USE MMD FOR GRAPH GENERATIVE MODEL EVALUATION
Having understood the potential pitfalls of using MMD, we now turn to suggestions on how to better leverage MMD for graph generative model evaluation.
Provide a sense of scale. As mentioned in Section 4.1, MMD does not have an inherent scale, making it difficult to assess what is 'good,' To endow their results with some meaning, practitioners should calculate MMD between the test and training graphs, and then include this in the results table/figures alongside the other MMD results. This will provide a meaningful bound on what two "indistinguishable" sets of graphs look like in given dataset (see Figures 10-13 in Appendix A.6).
Choose valid and efficient kernel candidates. We recommend to avoid the EMD- kernel due to the computational burden (see Appendix A.8), and the total variation kernel for its non-p.s.d nature. Instead, we suggest using either an RBF kernel, since it is universal kemnl,, a Laplacian kernel, or a linear kernel, i.e. the canonical inner product on Rd. since it is parameter-free. As all of these kernels are p.s.d.. and are fast to compute, they satisfy the efficiency desiderata criteria, and thus only require analysis of their expressivity and robustness.
i We remark that literature outside the graph generative modelling domain deserihes such choices, for example the context two-sample tests (Gretton et al., 2012b) or general model criticism (Sutherland et al., 2017). We will subsequently discuss to what extent the suggested parameter selection strategies may be transferred. II the case of the Laplacian kemel, the TV distance in lieu of the Fuclidean distance leads valid kemel.
7

---

Published as a conference paper at ICLR 2022
Utilize meaningful descriptor functions. Different descriptor functions measure different aspects of the graph and are often domain- speciffc.. As a general recommendation, we propose using previously -dsscrred (Liao et al., 2019; You et al., 2018) graph-level descriptor functions, namely (i) the degree distribution, (ii) the clustering coefficient, and (iii) the Laplacian spectrum histograms, and recommend that the practitioner make domain-specific adjustments based what is appropriate.
5.1 SELECTING AN APPROPRIATE KERNEL AND HYPERPARAMETERS
The kernel choice and descriptor functions require hyperparameter selection. We recommend assessing the performance of MMD in a controlled setting to elucidate some of the properties specific to the dataset and the descriptor functions of interest to a given application. In doing so, becomes possible to choose a kernel and parameter combination that will yield informative results. Notice that in contrast to images, where visualisation provides meaningful evaluation of whether two images are similar or not, graphs cannot be assessed in this manner. It is thus necessary to have a principled approach where the degree of difference between two distributions can be controlled. We subject a set of graphs to perturbations (edge insertions, removals, etc.) of increasing magnitude, thus enabling us to assess the expected degree of difference to the original graphs.
We ideally want an evaluation metric to effectively reflect the degree of perturbations. Hence, with an increasing degree of perturbation of graphs, the distance to the original distribution G of unperturbed graphs should increase. We can therefore assess both the expressivity of the evaluation metric, i.e., its ability to distinguish two distributions when they are different, and its robustness (or stability) based on how rapidly such metric changes when subject small perturbations. Succinctly, would like to see a clear correlation of the metric with the degree of perturbation, thus indicating both robustness and expressivity. Perturbation experiments are particularly appealing because they do not require access to other models but rather only an initial distribution G*. This procedure therefore does not leak any information from models and is unbiased. Moreover, researchers have more control over the ground truth in this scenario, as they can adjust the desired degree of dissimilarity. While there are many perturbations that we will consider (adding edges, removing edges, rewiring edges, and adding connected nodes), we focus primarily on progressively adding or removing edges. This is the graph analogue to adding "salt-and--epppr"" noise to an image, and in its most extreme form (100% perturbation) corresponds to fulle-connected graph and disconneeed graph, respectively.
Creating dissimilarity via perturbations. For each perturbation type, i.e., (i) random edge inser- tions, (ii) random edge deletions, (iii) random rewiring operations ('swapping' edges), (iv) random node additions, we progressively perturb the set of graphs, using the relevant perturbation parameters, in order to obtain multiple sets of graphs that are increasingly dissimilar from the original set of graphs. Each perturbation is parametrised by at least one parameter. When removing edges, for instance, the parameter is the probability of removing an edge in the graph. Thus for a graph with 100 edges and Premove 0.1 parametrisations apply for the other perturbations, i.e. the probability of adding an edge for edge insertions, the probability of rewiring an edge for edge rewiring, and the number of nodes to add to graph, as well as the probability of an edge between the new node and the other nodes in the graph for adding connected nodes. We provide formal description of each process in Appendix A.2 and A.3.
would expect on average 90 edges to remain in the graph. Similar
Correlation analysis to choose kernel and hyperparameters. For each of the aforementioned perturbation types, we compared the graph distribution of the perturbed graphs with the original graphs using the MMD. We repeated this for different scenarios, comprising different kernels, different descriptor functions, and where applicable, parameters. For a speed up trick to efficiently calculate MMD over range of o, please see Appendix A.5. Since these experiments resulted in hundreds of configurations, due to the choice of kernel, descriptor function, and parameter choices, we relegated most of the visualisations to the Appendix (see Section A.6). To compare the different configurations effectively, we needed a way to condense the multitude of results into more interpretable and comparable visualisation. We therefore calculated Pearson's correlation coefficient between the degree of perturbation and the resulting MMD distance, obtaining two heatmaps. The first one shows the best parameter choice, the second one shows the worst parameter choice, both measured in terms of Pearson's 's correlation coefficient (Figure 4). In the absence of an agreed-upon upon procedure to choose such parameters, the heatmaps effectively depict the extremes of what will happen if one is particularly "lucky" or ""unlucky" in the choice of parameters. A robust combination of descriptor function and
8

---

Published as a conference paper at ICLR 2022
Canzan))
Couoady
1R
ER.
9.2
-.00
10
BR
W5
Pepmo
Depin
Ogane
Digin
1.000
(a) AddEdges
(b) RemoveEdges
(c) RewireEdges
(d) AddeeonnecteNNodes
Figure 4: The correlation of MMD with the degree of perturbation in the graph, assessed for different descriptor functions and datasets (BA: verabási-Albeen ER: Erdös-Rényi, WS: Watts- Satts-Strogatz). For an ideal metric, the distance would increase with the degree of perturbation, resulting in values 1. The upper row shows the best proper kernel and parameter selection leads to strong correlation to the perturbation, but a bad choice can lead to inverse correlation, highlighting the importance of good kernel/parameter combination.
combination; the bottom row shows the worst. A
comparison function is characterised by both heatmaps exhibiting high correlation with the degree of perturbation. In the bottom row, the MMD distance in many cases no longer shows any correlation with the degree of perturbation, and in the case of the clustering coefficient (CC), is negatively correlated with the degree of perturbation. Such behaviour is undesired, showcasing a potential pitfall for authors if they inadvertently fail pick a "good" parameter or kernel combination. While chose the Pearson correlation coefficient for its simplicity and interpretability. other measures of dependence could be used instead if they are camaainapppprritte (see Appendix A.7). To choose kernel and parameter combination, we suggest picking the parameters with the highest correlation for the perturbation that is most meaningful the given domain. Lacking this, the practitioner could choose the combination that has the highest average correlation across perturbations.
6 CONCLUSION
We provided thorough analysis of how graph generative models are being currently assessed by means of MMD. While MMD itself is powerful and expressive, its use has certain idiosyncratic issues that need to be avoided in order to obtain fair and reproducible comparisons. We highlighted some of these issues, most critical of which are that the choice of kernel and parameters can result in different rankings of different models, and that MMD may not monotonically increase two graph distributions become increasingly dissimilar. As a mitigation strategy, we propose running perturbation experiment described in this paper select kernel and parameter combination that is highly correlated with the degree of perturbation. This way, the choice of parameters does not depend on the candidate models but only on the initial distribution of graphs.
Future work. This work gives an overview of the current situation, illuminates some issues with the status quo, and provides practical solutions. We hope that this will serve as a starting point for the community to further develop methods to assess graph generative models, and it is encouraging that some efforts to do so are already underway (Thompson et al., 2022). Future work could investigate the use of efficient graph kernels in combination with MMD, as described in recent review (Borgwardt et al., 2020). This would reduce the comparison pipeline in that graph kernels can be directly used with MMD, making graph descriptor functions unnecessary. Another approach could be to investigate alternative or new descriptor functions, such as the geodesic distance, or alternative evaluation methods, such the multivariate Dolmogoroy-Smima test (Justel al., 1997). or even develop totally novel evaluation strategies, preferably those that go beyond the eurrentl--emlooeed vectorial representations of graphs.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
We have provided the code for our experiments in order to make our work fully reproducible. Details can be found in Appendix A.2-A.4, which includes a link our GitHub repository. During the review process our code is available as Supplementary Material, in order to preserve anonymity.
ACKNOWLEDGMENTS
This work was supported in part by the Alfried Krupp Prize for Young University Teachers of the Alfried Krupp von Bohlen und Halbach-Stiftung (K.B.).
REFERENCES
Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-Lóópz, Leslie O' O'Bray, and Bastian Rieck. Graph kernels: State-of-the-an and future challenges. Foundations and Trends in Machine Learning, 13 (5-6):531-712, 2020.
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, 22114)e49-e57,, 2006.
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.
Martin R. Bridson and André Haefliger. The model spaces M. In Metric Spaces of Non-Positive Curvature, pp. 15-31. Springer, Berlin, Heidelberg, 1999. ISBN 978-3-662-12494-9 doi: 10. (007/978-3-6622 12494-9_22
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.), Pro- ceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp. 1630-1639. PMLR, 18 24 Jul 2021.
Fan R. K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional Conference Series in Mathematics. American Mathematical Society, 1997.
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- 2312. PMLR, 13-18 Jul 2020.
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.
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. 12531263. Association for Computing Machinery. 2020.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex J. Smola. A kernl method for the two-sampleproobeen In B. Schölkopf, J. C. Platt, and T. Hoffman (eds.), Advances in Neural Information Processing Systems 19, pp. 513-520. MIT Press, 2007.
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.
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.
10

---

Published as a conference paper at ICLR 2022
Mikhail Gromov. Hyperbolic groups. In S. M. Gersten (ed.), Essays in Group Theory, pp. 75-263.
Springer, Heidelberg. Germany, 1987.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge 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.
Ana Justel, Daniel Peña, and Rubén Zamar. A multivariate Kolmogorov-Smimat test of goodness of fit. Statistics & Probability Letters, 35(3):251-255 1997. ISSN 0167-7152.
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.
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.
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.
Chenhao Niu, Yang Song. Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permuta- tion invariant graph generation via acore-based generative modeling. In Silvia Chiappa and Roberto Calandra (eds.), Proceedings the Twentyy Third International Conference on Artificial Intellignnce and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4474-4484, PMLR, 26-28 Aug 2020. URL http::tpt http//pooeeenngg//e/ .ow.mnrss..........mmmmmmmmmmmm. mlr. press svress/vii /v10vvl 08 //n//nnl/ a html.
Marco Podda and Davide Bacciu. Graphgen-redux: a fast and lightweight recurrent model for labeled graph generation, 2021.
Allen Schwenk. Almost trees are cospectral. Frank Harary (ed.), New Directions in the Theory of Graphs, pp. 275-307. Academic Press, 1973.
Danica J. Sutherland, Hsiao-Yi 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.
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.
Edwing R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications, 373:241-272, 2003.
Duncan J. Watts and Steven H. Strogatz. Collective dynamics of wsolll-world" networks. Nature, 393 1998.
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
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.4477816677771167777
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. 21042116. 16. Association for Computing Machinery, 2021.
11

---

Published as a conference paper at ICLR 2022
A APPENDIX
The following sections provide additional details about the issues with existing methods. We also show additional plots from our ranking and perturbation experiments.
A.I KERNELS BASED ON TOTAL VARIATION DISTANCE
Previous work used kernels based on the total variation distance in order to compare evaluation functions via MMD. The choice of this distance, however, requires subtle changes in the selection of kernels for MMD-it turns out that the usual RBF kernel must not be used here!
We briefly recapitulate the definition of the total variation distance before explaining use in the kernel context: given two fiite-dimensional real-valued histograms X == (2), ( yn and Y = (/i....,yn. their total variation distance is defined as
drv drv(X, Y)
34
This distance induces a metric space that is not flat. In other words, the metric space induced by Eq. 3 has non-zero curvature fact that precludes certain kernels from being used together with Eq. 3). We can formalise this by showing that the induced metric space cannot have bound on its curvature.
Theorem 1. The metric space XTV induced by the total variation distance between two histograms not in CAT(K) for k > O, where CAT(k) refers to the category metric spaces with curvature bounded from above by k (Gromov, 1987).
There are at least two shhossssssssortest paths-ol of the same length, that first decreases the first coordinate and subsequently increases the second one, whereas for the second geodesic this order is switched. More precisely, the first geodesic proceeds from 21 to 21 (c, ........ 0) for infinitesimal c > 0, until Zo (0, .......)) 0) has been reached. Following this, the geodesic continues from To to æ + (0, e, .,...... 0) in infinitesimal steps until 22 has been reached. The order of these two operations
Proof. Let = (1, 0) and x2 = (0, 1...,
0).
be switched, such that the geodesic goes from Tj to (1, 1, ....... 0), from which it finally continues to 222 Both of these geodesics have a length of 1. Since geodesics Proposition 2.11, 23), XTv is not in CA)( for k > 0.
CAT(() space for
are unique (Bridson & Haefliger, 1999,
Since every CAT(k) space is also a CAT(() space for all / > k. this theorem has the consequence that XTv cannot be CAT(O) space. Moreover, every flat metric space is in particular CAT space, Xrv is not flat. According to Theorem 1 of Feragen et al. (2015), the associated geodesic Gaussian kernel, i.e. the kernel that obtain by writing
dTv (r,((X Y)2
k<z,v) v) exp
(4)
20²
is not positive definite and should therefore not be used with MMD. One potential fix for this specific distance involves using the Laplacian kernel, i.e.
k(zz, y)
(5)
The subtle difference between these kernel functions-only an exponent is being changed- demonstrate that care must be taken when selecting kernels for use with MMD.
A.2 EXPERIMENTAL SETUP
We can analyse the desiderata outlined above using an experimental setting. In the following, we will assess expressivity, robustness, and efficiency for a set of common perturbations, i.e. (i) random edge insertions, (ii) random edge deletions, (iii) random rewiring operations, i.e. 'swapping' edges, and (iv) random node additions. For each perturbation type, we will investigate how the metric changes for ever-increasing degree of perturbation, where each perturbation is parametrized by least one parameter. When removing edges, for instance, this is the probability of removing an edge in the graph. Thus for graph with 100 edges and Premave 0.1 we would expect average 90 edges to
12

---

Published as a conference paper at ICLR 2022
remain in the graph. Similar parametrizations apply for the other perturbations, for anmore detailed description we refer to Appendix A.3. All these operations are inherently small-scale (though not necessarily localised to specific regions within graph), but turn into large-scale perturbations of graph depending on the strength of the perturbation performed. We performed these perturbations using own Python-b framework for graph generative model comparison and evaluation. Our framework additionally permits the simple integration of additional descriptor functions and evaluators.
A.3 DETAILS ON GRAPH PERTURBATIONS
We describe all graph perturbations used in this work on the example of single graph G := (V, F) where V refers to the vertices of the graph and to the edges.
Add Edges For each Us, Bj V with us * vy sample from Bernoulli distribution Tay Ber(Padu) is drawn. Samples for which Tig 1 are added to the list edges such that E (())) 2ij 1}.
Remove Edges For each e, E E, sample from a Bernoulli distribution I; ~ Premovee is drawn, and samples with n; 1 are removed from the edge list, such that E' = En {es 24 + 1}.
Rewire Edges For each E E, sample from a Bernoulli distribution I; Ber is drawn, and samples with x; are rewired. For rewiring further random variable y; Ber((..5) drawn which determines which node e [3/b of the edge is kept. The node to which the edge is connected chosen uniformly from the set of vertices v; V, where v/ & c; i.e. avoiding self-loops and reconnecting the original edge. Finally the original edge is removed and the new edge eç = (ei[vi), v;)
added to the graph E' En (es x4 + 1] {el x; = 1).
Add Connected Node where n represents the number of nodes to add. For each e E V and iUy E V we draw sample from Bernoulli distribution Fij Ber(PeumeesLnot) and edge between e; and by to the graph if
We define a set of vertices to be added V for | < n).
Tij 1. Thus E' = E U {(vs, 1,) | oz E V, E VV* Tig
A.4 IMPLEMENTATION DETAILS
We used the official implementations of GraphRNN, GRAN and Graph Score Matching in our experiments. GraphRNN and GRAN both have an MIT License, and Graph Score Matching is licensed under GNU General Public License v3.0. Our code is available at (https: /www. github. com/Borg comm//ogwaarttLab/ ggge)) under BSD 3-Clause license.
rdtLab/
Compute resources. All the jobs were run on our internal cluster, comprising 64 physical cores (Intel (R) Xeon (R) CPU E5-2620 v4 2.10GHz) with 8 GeForce GTX 1080 GPUs. We stress that the main component of this paper, i.e. the evaluation itself, do not necessarily require cluster environment. The cluster was chosen because individual generative models had to be trained in order to obtain generated graphs, which we could subsequently analyse and rank.
A.5 SPEED UP TRICK
As the combination of kernels and hyperparameters yielded hundreds of combinations, it is worth mentioning worthwhile speedup trick to reduce the complexity of assessing the Gaussian and Laplacian kernel combinations. Considering they have a shared intermediate value, namely the Fuclidean distance, it is possible to return intermediate values in the MMD computation (Kxx. Kry, and KXY, prior to exponentiation, potential squaring, and scaling by a. Storing these intermediate results allows one to rapidly iterate over grid of values for without needed to recalculate MMD, leading to a worthwhile speedup.
A.6 EXPERIMENTAL RESULTS
We now provide the results presented in the paper across all the datasets.
13

---

Published as a conference paper at ICLR 2022
Hisac
9/0 TA0 56 750 000
MeaaC
Hole
Nanseer Blus
Nusteer ofBl
0.0
HalA
MaldA
MealA
Hala
1e4 1042
140 Bonn (-
(a) Barahási-Alln Albert Graphs
(b) Community Graphs
(c) Brdös-Rényi Graphs
(d) Watts-Strogaaz Graphs
Figure A heatmap of which model (from A. B. and C) ranks first in terms of MMD across different hyperparameter combinations. This uses the clustering coefficient descriptor function and the RBF kernel, where the number of bins a hyperparameter of the descriptor function, and the hyperparameter in the kernel.
fm degree
fn clustering
fn -aplacian
0.75
MMD Distance
1.0
1.0
kemel emd
0.50
0.5
0.5
0.25
0.0
0.0
0.00
10
10
10
10
-10
10
1.0
MMD Distance
0.6
0.2
zeme
0.4
0.5
Madd
Made
0.1
Made
0.2
0.0
0.0
-00
0
10
-10
10
-10
10
0.75
0.2
MMD Distance
1.0
kernel gaussian
0.50
0.5
0.25
0.0
0.00
0.0
110
10
10
10
-10
10
log(G)
log(a)
log(G)
Figure 6: Barabási-Alber Graphs. MMD calculated between the test graphs and predictions from three recent graph generative models (A, B, C) over a range of values of a on the Barabási-A Graphs dataset. Additionally, the MMD distance between the test graphs and training graphs is provided to give meaningful sense of scale to the metric. It provides an idea what value MMD signifies indistinguishable difference between the two distributions.
14

---

Published as a conference paper at ICLR 2022
degree
fn clustering
laplacian
0.3
0.10
MMD Distance
kernel = emd
0.2
0.05
0.05
0.1
0.00
0.0
0.00
10
10
10
10
10
0
10
0.06
0.06
MMD Distance
0.010
0.04
0.04
kemel
modd
0.02
0.02
0.005
Midel
0.00
0.00
0.000
10
10
-10
10
10
0.006
MMD Distance
0.04
kernl gaussian
0.04
0.004
0.02
0.02
0.002
0.00
0.00
0.000
10
10
-10
10
log(a)
log(o)
log(a)
Figure 7: Community Graphs. MMD calculated between the test graphs and predictions from three recent graph generative models (A, B, C) over range of values of a on the Community Graphs dataset. Additionally, the MMD distance between the graphs and training graphs is provided to give a meaningful sense of scale to the metric. It provides an idea of what value of MMD signifies an indistinguishable difference between the two distributions.
15

---

Published as a conference paper at ICLR 2022
fn degree
fn clustering
fn Iaplacian
0.75
0.75
MMD Distance
kernel emd
0.50
0.50
0.5
0.25
0.25
0.00
0.00
0.0
-10
10
-10
10
-10
0
10
0.6
MMD Distance
0.4
0.4
kemel
0.4
modd
0.2
0.2
0.2
Midel
Maddi
0.0
0.0
0.0
10
10
-10
10
10
0
10
0.6
0.4
kemel = gaussian
MMD Distance
0.4
0.4
0.2
0.2
0.0
0.0
0.0
10
-10
10
10
10
log(a)
log(a)
log(a)
Figure 8: Erdös-Rényí Graphs. MMD calculated between the test graphs and predictions from three recent graph generative models (A, B, C) over a range of values of on the Erdös-Rényi Graphs dataset. Additionally, the MMD distance between the graphs and training graphs is provided to give a meaningful sense of scale to the metric. It provides an idea of what value of MMD signifies an indistinguishable difference between the two distributions.
16

---

Published as a conference paper at ICLR 2022
fn degrec
fn clustering
fn Iaplacian
1.5
MMD Distance
1.0
1.0
kernel = emd
1.0
0.5
0.5
0.5
0.0
0.0
0.0
-10
10
-10
10
10
0
10
0.4
1.0
MMD Distance
1.0
modd
0.5
0.5
0.2
Midel
Maddi
0.0
0.0
0.0
10
10
10
10
MMD Distance
1.0
kemell gaussian
0.2
0.5
0.5
0.0
0.0
0.0
10
-10
10
-10
10
log(a)
log(o)
log(a)
Figure 9: Watts-Strogatz Graphs. MMD calculated between the test graphs and predictions from three recent graph generative models (A, B, C) over range of values of a on the Watts-Strogatz Graphs dataset. Additionally, the MMD distance between the test graphs and training graphs is provided to give meaningful sense of scale to the metric. It provides an idea of what value of MMD signifies an indistinguishable difference between the two distributions.
17

---

Published as a conference paper at ICLR 2022
drnecct AbastrsA
datadt tedeeeesttinos
draie Wansteggtiiizae
Doseiitee Dapcs
Dieres tetepall
6.6
6.-
3.6
64
64-
0.-
0.8
1.0
Doanec to Ongggel Craghe
Dorma Onggral Coepte
0.3
Disvibac Puzziee
3.4
E.
1.0
Dioeee 1o Drigge Grogh
Dinanos Crighta Grogbe
Dociltee Fraciios Lankaie
0.6
04-
64-
0.4
0.6
0.3
0.0
0.0
0.2
044
0.5
1.5
0.2
04
0.6
1.0
164
0.5
0.5
1.0 0.2
0.4
0.0
0.5
1.0
55 Parmibttion
Figure 10: Perturbation: adding edges. This figure shows the full results across datasets, descriptor functions and parameters when the perturbation is adding edges to the graphs. At each level of perturbation, the distance the perturbed graphs calculated to the original graph distribution using the specified evaluator function. Each line represents different parameter combination. An ideal evaluator function would monotonically increase as the degree of perturbation increases.
18

---

Published as a conference paper at ICLR 2022
10
14
18
1.0
Dioree wwggeeeetooo Cruble
Disance in Oraara Craphe
Dostione Parciin Daano
06
0.6
064
24
0.
2.4
04
Dessa Origral Ceggee
0.
0.6
Donriate Pansice
66-
8.5
0.-
0.6
0.2
63-
0.-
0.0
122
1.0
1.-
Di0eec diigee Cooghe
Donacc nn Origtel Crodh
08.
0.8
Doscipas Phaciteer Fuaatoo Laplaiin
04-
64
0.
0.6
02-
0.2
3.4
0.5
05
02
0.6
08
04
0.6 Patalodiin
6.8
1.
0.2
0.4
0.5
0.8
1.0
56 Permietii
54 Pemioidde
Figure 11: Perturbation: removing edges. This figure shows the full results across datasets, descriptor functions and parameters when the perturbation is removing edges from the graphs. At each level of perturbation, the distance of the perturbed graphs calculated to the original graph distribution using the specified evaluator function. Each line represents a different parameter combination. An ideal evaluator function would monotonically increase as the degree of perturbation increases.
19

---

Published as a conference paper at ICLR 2022
ditad Kiniins
daaud Endeetenptiinnss
ditact WezeSreppareppss
0.-
Drone Origon Coogte
-8
Do Organal Craeaa
Dosttipue Placcinn Diggts
06-
23
66-
8.4
60-
0.-
0.0-
10-
Dosiban
4.5
66-
0.
Ditmmoite
0.4
-2.
60
1013
10-
Desciipes Pasciin Loptacin
Dourze Orginal Gueet
Thoree Sooeebirrggg...o
W
Orattall
86-
-00
-20
0.6
0.6
0.8
1.0
0.2
0..6
160
1.0
042
064
0.6
1.0
0.
0.6
0.5
1.2
54 Poniriatioo
Figure 12: Perturbation: rewiring edges. This figure shows the full results across datasets, descrip- tor functions and parameters when the perturbation is rewiring edges in the graphs. At each level of perturbation, the distance the perturbed graphs calculated to the original graph distribution using the specified evaluator function. Each line represents different parameter combination. An ideal evaluator function would monotonically increase as the degree of perturbation increases.
20

---

Published as a conference paper at ICLR 2022
Goglla
WatsStopseenghl
1.3
1.2
Dieiee vergeet Cagge Cougle
Dbunee Ohggnaa Grada
Discipare Panciics Damnc
2.8
0.5
03
0.2
0.2
2.5
1:25
107
02-
Dostiane Pardiax-
100
-15-
1.8
-20
-2.5
1.0
Dosilptes Furciics Laptain
Detaxe t4 Diggir-aaalaagaaaa Oredox
2.8
0.5
8.4
3000
1.4
4300
-9000
Nodis
Nodiis
N.No66 Addid
Figure 13: Perturbation: adding connected nodes. This figure shows the full results across datasets, descriptor functions and parameters when the perturbation adding connected nodes to the graphs (for each node that is added, there is 15% chance the node will be connected to any other node in the graph). At each level perturbation, the distance the perturbed graphs is calculated the original graph distribution using the specified evaluator function. Each line represents different parameter combination. An ideal evaluator function would monotonically increase as degree of perturbation increases.
21

---

Published as a conference paper at ICLR 2022
A.7 ALTERNATIVE MEASURES OF CORRELATION
As general recommendation, we chose to use the Pearson correlation coefficient to select a good hhmerarapprrrrr combination, due to its simplicity and ease of interpretation. It reflects the behavior we expect from perturbations: as the graphs are increasingly perturbed, the distance to the original graphs should grow in a similar manner as well. However, there could be scenarios in which the distance to the original graphs should not grow linearly with the degree of perturbation, in which case the Pearson correlation coefficient would not be the best choice. We present here two plug-in alternatives for the Pearson correlation coefficient, namely the Spearman rank correlation coefficient, and mutual information, which can easily be integrated into our framework. We add one word of caution when using the mutual information, which is the fact that it does not capture the directionality of dependence. This is only an issue there are scenarios in which the MMD distance decreases as the degree of perturbation increases. Since we observed this in some of our datasets, it would not be the most appropriate to use in this specific case. We now present the results from using these measures of dependence below.
R4
Coumenty
Communy
Ovemuntty
Coerenty
6.55
6.5
WS
622
Overaely
Crerenty
0.5
0.50
W9
Deger
Parn
Pepre
Laplosee
0275
(a) AddEdges
(b) RemoveEdges
(c) RewireEdges
(d) AddConnectedNodes
The Spearman rank correlation of MMD with the degree of perturbation in the graph, assessed for different descriptor functions and datasets (BA: Barabási-Albert Graphs, ER: Erdös- Rényi Graphs, WS: Watts-Strogatt Graphs). For an ideal metrie, the distance would increase as the degree of perturbation increases; resulting in correlation close 1. The upper row shows the best combination in terms of the correlation; the bottom row shows the worst. As we can see, a proper kernel and parameter selection leads to strong correlation to the perturbation, but a bad choice can lead to inverse correlation, highlighting the importance of good kernel/parameter combination.
Figure 14:
8A
BA
D4.
14
12
95-
155
15-
W5-
-14
8A
BA
5A.
du
Cuccudity
605
45
ws
W5
Drgee
Lattsie
Pewer
Pigm
Ledeci
82
(a) AddEdges
(b) RemoveEdges
(c) RewireEdges
(d) AddConnestedNodes
Figure 15: The mutual information of MMD with the degree of perturbation in the graph, assessed for different descriptor functions and datasets (BA: Barabási- Graphs, ER: Médös-Rényí Graphs, WS: Watts-Strogatz Graphs). For an ideal metric, the distance would increase as the degree of perturbation increases: resulting in a high mutual information coefficient. The upper row shows the best Sernel-parameter combination in terms of the mutual information; the bottom row shows the worst. As we can see, a proper kernel and parameter selection leads to strong dependence on the perturbation, but bad choice can lead to no mutual information, highlighting the importance of good kernel/parameter combination.
22

---

Published as a conference paper at ICLR 2022
Licer
RBF
EMD
Time (5ec)
20-
180
Number of grephs
Number of nodes
Number bins
Figure 16: CPU runtime comparison (lower is better) of the linear, RBF, and EMD-based kernels when evaluated on ER graphs and varying the number of graphs (the dataset size), the number of nodes (the size of each graph), and histogram bin size. Each plot varies single parameter (on the x-axis), while keeping the other two fixed with values of 100. Runtimes are reported on logarithmic scale.
A.8 COMPUTATIONAL RUNTIME OF DIFFERENT KERNELS
In the following, we assess the empirical CPU runtime of the linear kernel, RBF kernel, and the EMD-based kernel in the MMD calculation. As noted by ourselves and Liao et al. (2019), the EMD-based kernel is computationally expensive, hindering its suitability for use in graph generative model evaluation. We investigate this effect in more detail by doing runtime comparison the three kernels in a simulated environment. We generate two sets of Erdös-Rdde Rényi Graphs with the probability of an edge p 0.3, and then calculate the MMD distance between the two sets using the degree distribution as the descriptor function for varying dataset size (Mgraphss), graph size (Mnodes)) and histogram bin size (rbbins). As a default, we set Ngrrahss = 100, nnodes 100, and Thins = 100. We then change one variable at a time, iterating through values (100, 200, ..... 1000} while keeping the other two variables fixed, and measured the time it took to calculate the MMD distance. We report the average runtime over ten repetitions obtain more stable results.
Our results can be seen in Figure 16. At the default setting of 100 graphs, 100 nodes per graph, and 100 bins in the histogram, observed that the EMD-based kernel took more than 50-140 times longer to compute compared to the RBF and linear kernels respectively. This difference was exacerbated when the size of the dataset (Ngraphs) increased well as when the size of the graphs in the dataset (Moodes) increased. For a dataset of 1,000 graphs, the EMD-based kernel took 27 minutes to run, whereas the linear kernel took 6 seconds and the RBF kernel took 21 seconds. Doing a simple extrapolation of the runtime of a dataset comprising 10,000 graphs, we estimate the EMD-based kernel would take 50 hours to run for single hyperparameter combination, showcasing the computational limitation of this choice of kernel for larger dataset sizes. We observed similar, albeit less extreme, increase runtime when the size of the graphs increased. While the linear time approximation of MMD (Gretton et al., 2012a) could mitigate some of the runtime challenges, in general we recommend that practitioners use efficient kernels such as the linear kernel or RBF kernel for graph generative model evaluation.
23


Reviews:
[{"review_id": "t6RHtDm2FXm", "reviewer": "Reviewer_37EN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper has several strengths. \n\n1) Presentation. The paper is well written even for people that are not related to this topic. The paper focuses on the main pitfalls of this measure.\n\n2) Reproducibility: Most of the experiments can be easily replicated. However, there is some lack of explanation in the main paper (9 pages) that could be addressed. \n\n3) Impact of ideas: The criticism of this measure could have a great impact on the current evaluation process, changing the way that GGMs must be evaluated. \n\n4) Technical quality: Most pitfalls are corroborated empirically, while others are not even necessary to check.\n\nEven though the main strengths of the paper, there are some issues that reduce the recommendation score. unfortunately, the solutions are vaguely explained, and not necessarily new. \n\n1) Perturbations are not defined in the paper (9 pages). This makes it difficult to understand some of the experiments and the effects in the final evaluation. Please include part of the appendix in the main part of the paper.\n\n2) The difference in the distributions versus perturbations is not necessarily a problem of the metric, it could be the descriptor function. The paper uses the clustering coefficient to show this problem; however, depending on the graph, the clustering coefficient does not change considerably with some type of perturbations. For example, imagine a graph with a low clustering coefficient (as many real-world networks). If we pick a node with cc=0 and we remove all of its edges, its cc will not change at all; even though it was highly perturbed. Please, change the example, using a measure affected by this issue or define that this problem is given to some descriptor functions.\n\n3) Provide a sense of scale: This idea is vaguely explained, and it does not define a procedure to follow. Please, define a procedure.\n\n4) Utilize meaningful descriptor functions: This does not show a new solution. There are several meaningful descriptor functions that are used in the evaluation of GGM that are not even included in this paper. For example, the geodesic distance. Expand the use over other meaningful descriptor functions. \n\n5) One of the main problems, interpretability, is not even solved. \n\n6) There is no comparison against other measures. For example, the multivariate Kolmogorov-Smirnov, that has been used in a previous evaluation of GGMs (A multivariate Kolmogorov-Smirnov test of goodness of fit and Tied Kronecker Product Graph Models to Capture Variance in Network Populations)", "summary_of_the_paper": "The paper criticizes Maximum Mean Discrepancy (MMD) an evaluation metric that has been used lately to evaluate Generative Graph Models (GGMs). The main problems of the MMD are: It does not capture difference upon perturbations; It does not have a scale; It requires the selection of a kernel and parameters that could lead to different results (and a high time complexity according to the kernel). Finally, the paper describes some procedures based on MMD to avoid some of these problems. While the pitfalls are clearly explained, the solutions are vague.", "summary_of_the_review": "The paper mainly focuses on the negative problems of the MMD, which are explained and in several cases empirically proved. This makes the paper strong and it should be accepted. However, the solutions are not clearly explained, decreasing the score for this paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "gt-bu4Hc58", "reviewer": "Reviewer_7gMp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths:\n- this is a much-awaited paper that clarifies many aspects related to MMD for evaluating graph generative models. It was really interesting to see how much results may vary whenever the parameters of MMD are not calibrated properly.\n- the recommendations on how to tune the MMD parameters to obtain meaningful results are really useful, and if properly incorporated into the graph generative modeling standard practices might increase the quality of the research and help establish more powerful benchmarks to evaluate graph generative models.\n\nWeaknesses:\n- while the content is extremely useful, I find the scope of the paper a bit limited. For example, node and edge features are not taken into consideration in this paper. In its current form, the paper only discusses how to use MMD to compare the structure of graphs, while in practical scenarios (e.g. for molecular generation), nodes and edge features play an equally important role. \n\nQuestions:\n- commonly, MMD is also computed using the 4-orbit count descriptor. Why wasn't this taken into account in your analysis?\n- I think a runtime comparison of the various kernels (at least between linear, EMD and RBF) would be something useful to the practitioner. Otherwise, claims such as \"the EMD kernel is slow\" remain a bit vacuous (how much slow is \"slow\"? At which point using EMD becomes to be intractable?)", "summary_of_the_paper": "The paper identifies limitations and common pitfalls that practitioners encounter when using the MMD metric to evaluate graph generative models. Moreover, it provides guidance on how to ensure that the metric is properly calibrated to avoid nonsensical results.", "summary_of_the_review": "I am inclined towards accepting the paper for its much-needed practical guidance on the use of MMD in the context of graph generation, which could have very positive implications in this research field. However, I acknowledge (and the authors should, too) that what is discussed in this paper is only one of the many aspects to consider when evaluating graph generators.\n\n----EDIT----\nI find the response of the authors to my inquiries satisfactory. For this reason, I am raising my score from 6 to 8 and vote for its acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Lr23PPj02_R", "reviewer": "Reviewer_d5fz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strengths :-\n1) The problem the authors focus on in this work is significant in graph based generative modeling community. By highlighting the potential issues with usage of the MMD metric, the authors provide valuable insight and learning which would hopefully advance the state of research. \n2) The notation and description of the paper is unambiguous and clear and the authors via rigorous empirical study highlight different facets of the problem effectively. By not deciding to include their own approach, the authors add to the clarity of the paper for which I would like to commend their work. Additionally most of the experiments are reproducible which is another reason to recommend this work.\n3) The recommendations from the authors is insightful and would be useful to researchers working in the field of graph based generative models. \n\nWeaknesses :-\n1) The current scope and focus of the paper is a bit limited. There are graph based generative models which focus on edge prediction and node classification tasks for example which focus on graph based convolutions using node and edge based features and also use common metrics like logistic loss etc. There are also other forms of graph based generative models which try to learn node and edge based embeddings via deep neural networks etc. \n2) The authors could have tried to include other metrics in common usage apart from the MMD metric which would have made this work even more beneficial. Same goes for other prevalent descriptor functions.\n3) Rather than working with correlation which focusses on linear relationships, the authors could have worked with non-linear variants such as mutual information which would potentially have been more apt.", "summary_of_the_paper": "In this work, the authors aim to provide a principled way to evaluate and compare graph generative models. The authors initially list desirable criteria an evaluation metric should possess and subsequently discuss the usage of maximum mean discrepancy (MMD) for model comparison. Subsequently they highlight issues with the usage of the MMD metric for model comparison purposes and via empirical study and analysis, list a set of practical recommendations for researchers to follow when evaluating graph based generative models.", "summary_of_the_review": "The authors focus on an important problem in the graph based generative modeling domain and provide valuable insight and learnings via carefully designed empirical results and clear and unambiguous explanations and intuitions. The recommendations from the authors is insightful and would be useful to researchers working in the field of graph based generative models. However the current scope and focus of the paper is a bit limited. The authors could have expanded this work via considering i) other metrics apart from MMD, ii) other descriptor functions as well as iii) working with non-linear variants for correlation, i.e., mutual information. I would like to congratulate the authors for this work and ideally would like to see this paper accepted. \n\n----UPDATE----\n\nAfter revisiting the updates made by the authors, I am updating my score to Accept. I would like to congratulate the authors for their excellent work which would benefit researchers working in the field of graph based generative models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4l4ruJ4844", "reviewer": "Reviewer_3VAJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This paper is generally clear and well written.  \n\nIt could be helpful to add citations in a few places to help the reader who is not already familiar enough with the graph generative models community to recognize what is considered most popular and status quo (see minor comments below for some examples). \n\nOne limitation to the robustness experiments is that there is an assumption that a greatly perturbed graph should have a much different probability than the source graph, however it is not clear why this is necessarily the case (e.g, if the graph generating distribution is uniform).\n\nThe paper also notes and makes a point in the experiments how three popular works all use different kernels, descriptors, hyperparameters, however one of the works (Niu et al., 2020) doesn’t seem to describe the kernel and hyperparameters, instead citing one of the other of the other two works (You et al., 2018) and claiming to use the same evaluation (so presumably the same kernel and hyperparameters).  In addition, all three works appear to use degree histogram, clustering coefficient histogram, as well as the number of orbits with 4 nodes (which was left out from this paper); (Liao et al, 2019) appears to uses the Lapacian spectra in addition to these.  It might be worth noting why the number of orbits was omitted in this study.\n\nMinor comments:\n- “the community has largely gravitated towards a single comparison metric, the maximum mean discrepancy (MMD)” consider adding some citations (and if there are notable exceptions)\n- “Specifically, d(G, G′) should be monotonically increasing the further apart G and G′ are from one another.” Further apart according to what measure? Presumably there are several ways to specify this and, if taken precisely, might beg the question of how to define d.\n- “if a distribution G is subject to a perturbation, a suitable metric should be robust to small perturbations” is it correct to understand this as the metric being well-conditioned?\n- rather than perturbing graphs (since the resultant graphs might still be in the set of graphs or have high probability), why not generate sets of graphs from increasing different distributions directly? \n- “depicts an overview of this approach as it is being done today.” Consider adding citation(s).\n-  \"Equation 1 is often treated as a metric as well” consider adding citations\n- “even though it would be more correct to only use it for hypothesis/two-sample testing” the original (and several subsequent) works seem to describe MMD in the hypothesis/two-sample testing context, but it might still be worth adding a brief note why treating it as a metric is \"less correct\".\n- It seems as though there’s a typo in (2)?  The numerator appears to be 2 * deg(v), when I believe it should be a count of the edges between neighbors of v (instead of v's degree)?\n- “and only require further analysis of their expressivity and robustness” given this work's nature and scope, this would be nice to address in this work\n-  The paper notes how descriptor functions are strictly necessary for MMD, and when they are used, the importance of descriptor function choice.  In the recommendations section, the suggestion appears to be to use any of the descriptors (as opposed to how to select an/the appropriate one).\n-“clustering coefficient (CC), is even negatively correlated with the degree“, the scale in Fig 4 (correlation) appears to be 0 to 1 instead of -1 to 1?", "summary_of_the_paper": "This paper describes desiderata (expressivity, robustness, and efficiency) for metrics for comparing graph generative models and details the various ways that recent work has used maximum mean discrepancy (MMD) to evaluate graph generative models.  Several limitations of MMD are described, as well as the consequences of the various choices in using MMD (kernels, descriptor functions, and hyper-parameters) and how these choices have impacted experiments in recent work.  The paper concludes with recommendations to help ameliorate several of these limitations and impacts.", "summary_of_the_review": "The paper is generally clear and well written and makes several interesting and worthwhile observations about MMD and its use in recent work.  However, there is an opportunity to better support some of the claims--like what is considered status quo (through citations) and about recent experiments (which paper used which settings and, in the case of (Niu et al., 2020), where those setting can be found--and to clarify the perturbation based desiderata and experiments/analysis.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides an overview of evaluating graph generative models (GGMs). It systematically evaluates one of the more popular metrics, maximum mean discrepancy (MMD). It highlights some challenges and pitfalls for practitioners and suggests some ways to mitigate them. The reviewers found the paper practically relevant and several reviewers upgraded their scores through the discussion process. The authors acknowledged there are still some remaining issues regarding (i) considering other metrics & descriptor functions; ii) evaluating node/edge attributes and iii) addressing molecule generation. I am satisfied that these areas are beyond the scope of the current work and that the clarification improvements in the paper are adequate. It stands well enough on its own to accept in its present form.
Decision: Accept (Spotlight)