On Evaluation Metrics for Graph Generative Models
Authors: Rylee Thompson
Boris Knyazev
Elahe Ghalebi
Jungtaek Kim
Graham W. Taylor
Venue: ICLR 2022 Poster (2022)

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

Published as a conference paper at ICLR 2022
ON EVALUATION METRICS FOR GRAPH GENERATIVE MODELS
Rylee Thompson' 2 Boris Knyazev Elahe Ghalebi", Jungtaek Kim', Graham W. Taylor! 1 University of Guelph, 2 Vector Institute. 3 Samsung, SAIT AI Lab, Montreal, POSSEEC {rylee, bknyazev, gwtaylor] ai, jtkimm@ostech.ac..
e w
ABSTRACT
In image generation, generative models can be evaluated naturally by visually in- specting model outputs. However, this is not always the case for graph generative models (GGMs), making their evaluation challenging. Currently, the standard pro- cess for evaluating GGMs suffers from three critical limitations: i) it does not pro- duce single score which makes model selection challenging, ii) in many cases it fails to consider underlying edge and node features, and iii) it is prohibitively slow to perform. In this work, we mitigate these issues by searching for sealar, domain- agnostic, and scalable metrics for evaluating and ranking GGMs. To this end, we metries emerging from
study existing GGM metries and ceural-network-bassee generative models of images that use embeddings extracted from a task-specific network. Motivated by the power Graph Neural Networks (GNNs) to extract meaningful graph representations without any training, we introduce several met- rics based on the features extracted by an untrained random GNN. We design ex- periments to thoroughly test and objectively score metrics their ability mea- sure the diversity and fidelity of generated graphs, as well as their sample and com- putational efficiency. Depending on the quantity of samples, metrics. We show these
recommend one
of two metrics from our collection of two metrics to be more expressive than pre-existing and alternative random-GNN: based metrics using our objective scoring. While we focus on applying these met- rics to GGM evaluation, in practice this enables the ability to easily compute the dissimilarity between any two sets of graphs regardless of domain. Our code is released at: https:: //ttts//////b.////// wtt.wwwb.coom/o/uueeeecc.ccc.. mlrg/ mlrgg/GMM- 20///GGM-mette. metrics
INTRODUCTION
Graph generation a key problem in a wide range of domains such as molecule generation (Samanta
et al. 2020 Popova et al. 2019 Li et al. 2018 Kong et al.] 202T Jin et al.) (020) and structure generation (Bapst et al. [019 Thompson et al. 2020). An evaluation metric that is capable of accurately measuring the distance between set of generated and reference graphs is critical for advancing research on graph generative models (GGMs). This is frequently done by comparing empirical distributions of graph statistics such orbit counts, degree coefficients, and clustering coefficients through Maximum Mean Discrepancy (MMD) (You et al.) 2018 Gretton et al., 20066) While these metrics are capable of making meaningful comparison between generated and real graphs YYou et al., 2018), this evaluation method yields a metric for each individual statistic. In addition, recent works have further increased the number of metrics by performing MMD directly with node and edge feature distributions (Goyal et al. 2020), or on alternative graph statistics such as graph spectra (Liao et al. 2001)) While this is not an issue provided there is a primary statistic of interest, all metrics are frequently displayed together to approximate generation quality and evaluate GGMs (You et al., 2018 8 Liao et al., 2019). This process makes it challenging to measure progress as the ranking of generative models may vary between metrics. In addition, the computation of the metrics from You et al. (2018) can be prohibitively slow (Liao et al., 2019 O Braa et al.) 2022). and they are based only graph structure, meaning they do not incorporate edge and node features. Therefore, they are less applicable in specific domains such as molecule generation where such features essential, This particular limitation has led to the of the Neighborhood Subgraph

---

Published as a conference paper at ICLR 2022
Pairwise Distance kernel (NSPDK) (Cssta & Grave 2010 in GGM evaluation (Goyal et al. 2020 Podda & Bacciu 2021 Kawai et al. 2019) as it naturally incorporates edge and node features. However, this metric is still unable to incorporate continuous features in evaluation (Costa & Grave, 2010). Faced with a wide array of metrics and ambiguity regarding when each should be the focus, the community needs robust and scalable standalone metries that can consistently rank GGMs.
While less popular, metrics from image generation literature have been successfully utilized in GGM evaluation. These metries rely on the use of a task-specific neural network extract meaningful representations of samples, enabling a more straightforward comparison between generated and reference distributions (Preuer et al. 2018 Liu al., 2019; Thompson et al.. 2020). Although these metrics have been validated empirically in the image domain, they are not universally applicable to GGMs. For example, Fréchet Chemnet Distance (Preuer et al., (0018) uses a language model trained on SMILES strings, rendering it unusable for evaluation of GGMs in other domains. Furthermore, a pretrained GNN cannot be applied to datasets with a different number of edge or node labels. Pretraining GNN for every dataset can be prohibitive, making the use of such metrics in GGM evaluation less appealing than in the more established and standardized image domain.
In image generation evaluation, classifiers trained on ImageNet (Deng et al. 2009) are frequently used to extract image embeddings [Binkowski et al., 2018 Heusel et al., 2017
K Kynkääänniemi et al, 2019 Xu et al., 2018 Naeem et al., (020). While classifiers such as Inception v3 (Szegedy et al, 2016 are consistently used, recent works have investigated the use of randomly-initializze CNNs with further training (hereafter referred to random network) in generative model evaluation. Xu et al. (2018); Naeem et al.] (2020) found that a random CNN performs similarly to ImageNet classifiers on natural images and is superior outside of the natural image domain. In the graph domain, random GNNs have been shown to extract meaningful features to solve downstream graph tasks without training (Kipf & Welling 2017 Morris al., 2019 Xu et al. 2019)) However, the applicability of random GNNs for the evaluation of GGMs remains unexplored.
In this work, we aim identify one or more scalar metries that accurately measures the dissimilarity between two sets of graphs to simplify the ranking of GGMs regardless of domain. We tackle this problem by exploring the use of random GNNs in the evaluation of GGMs using metrics that were developed in the image domain. In addition, we perform objective evaluation of a large number of possible evaluation metrics. We design experiments to thoroughly test each metric on its ability to measure the diversity and fidelity (realism) of generated graphs, as well their sample and computational efficiency. We study three families of metrics: existing GGM evaluation metrics based on graph statisties and graph kernels, which we call classical metrics; image domain metrics using a random GNN; and image domain metrics using a pretrained GNN. We aim to answer the following questions empirically: (Q1) What are the strengths and limitations of each metric? (Q2) Is pretraining a GNN necessary to accurately evaluate GGMs with image domain metrics? (Q3) Is there a strong scalar and domain domain-agnostic agnostic metric for evaluating and ranking GGMs? Addressing these questions enabled us to reveal several surprising findings that have implications for GGM evaluation in practice. For example, regarding Q1, we identify a failure mode in the classical metrics in that they are poor at measuring the diversity of generated graphs. Consequently, we find several metries that are more expressive. In terms of Q2, we determine that pretraining is unnecessary to utilize neural-network-based (NN-based) metrics. Regarding Q3, we find two scalar metrics that are appropriate for evaluating and ranking GGMs in certain scenarios; they are scalable, powerful, and can easily incorporate continuous or discrete node and edge features. These findings enable computationally inexpensive and dagain-agnostic GGM evaluation.
2 BACKGROUND & RELATED WORK
Evaluating generative models in any domain is notoriously difficult task (Theis et al. 2016). Pre- vious work on generative models has typically relied on two families of evaluation metrics: sample- based (Heusel et al., 2017) and likelihood-based (Thii et al.) 2016). However, comparing the log-likelihood of autoregressive GGMs is intractable as it requires marginalizing over all possible node orderings (Chen et al. 2021). While recent work learns an optimal ordering and estimates this marginal Chen et al. (202 lb. it has been shown previously that likelihood may not be indicative of generation quality (Theis et al. 2016)..
hample-based evaluation metrics estimate the distance between real and generated distributions P, and Pg by drawing random samples (Heusel et al.) You et al. 2018; Binkkwski et al. 2018). That is, they compute p(S,,S,) S,) RJ p(P,, Pr). with x
2017
P. and 8y xx .......
xX] Pg. where x; is defined as some feature
2

---

Published as a conference paper at ICLR 2022
vector extracted from corresponding graph G, We use sample-based metrics throughout they are model agnostic and therefore applicable to all GGMs.
2.1 CLASSICAL METRICS
Metrics based on graph statistics You et al. 2018 are standard in evaluating GGMs (Liao et al. 2019 Dai et al. 2020). These metrics set x; be the clustering coefficient, node degree, or 4-node orbit count histograms that are then used to compute the empirical MMD between generated and reference sets Sg. S, (retton al. 2006):
172
1
a
72
TR
MMD S S,)
k(x, x
k(
k(x xf);
n
4,j=1 where ((),)) is general kernel function. You al. (2018) proposed a form of the RBF kernel:
2,j=1
j=1
k(x,, x²) exp (-d(x,, X /)))
where d(-,-) computes pairwise distance, and in that work was chosen be the Earth Mover's
Distance (EMD). This yields three metrics, one for each graph statistic. The computational cost of
these metrics may be decreased by using the total variation distance as d(..-) in Equation [ Liao
et al. 2019). However, this change leads to an indefinite kernel and undefined behaviour ( Bray
al. 2022p. Therefore, we only compute these metrics using EMD You et al. 2018 In addition,
several works (Goyal et al. 2020, Podda & Bacciu 2021 Kawai et al. 2019) evaluate GGMs by replacing .(.,)) with the Neighborhood Subgraph Pairwise Distance graph kernel (NSPDK). This metric has the benefit of incorporating discrete edge and node features along with the underlying graph structure in evaluation. Similar to the metrics proposed by You et al. (2018), Moreno et al. (2018) extract graph structure properties such node degree, clustering coefficient, and geodesic distance. However, these properties are then combined into a scalar metric through the Kolmorogov- Smirnov (KS) multidimensional distance (Justel et al. 1997). We exclude KS from our experiments as it is unable to incorporate edge and node features, which is one of the key properties we seek. Finally, note that other -omain-specifii metries such as "percentage of valid graphs exist. Our goal is not to incorporate, climinate, or evaluate such metries; they are properties of generated graphs, and unlike the metrics described above do not provide a comparison reference distribution. We believe that such metrics can still provide valuable information in GGM evaluation.
2.2 GRAPH NEURAL NETWORKS
We denote a graph as G = (V, E') with vertices V and edges E = {(i,) i.j E (VI). GNNs allow the extraction of fixed size representation x; of an arbitrary graph G,. While many GNN formulations exist (Wu et al. (020). we consider Graph Isomorphism Networks (GINs) (Xu al. 2019) as a common GNN. GINs consist of propagation layers followed by a graph readout layer to obtain x,. For node E V, the node embeddings (!) at layer E [1, L] are computed as: h MLP(()
h 11 (()) ((h6-1) uE ((N)))))
where (o) is the input feature node v, h E Rd 4A > O denotes a d-dimensional embedding of node v after the I-th graph propagation layer; (v) denotes the neighbors of node e; MLP()) is fully-connected neural network; f(()) is some aggregation function over nodes such as mean, max or sum. A graph readout layer with skip connections aggregates features from all nodes at each layer I E [1, L] and concatenates them into a single L d dimensional vector (Xu et al. (019):
X;- CONCAT READOOU((h()) | E VJ) | 1,2, 4)).
where READOUT is similar (() and is often chosen as the mean, max, or operation.
2.3 NEURAL-NETWORK BASED METRICS
NN-based metrics utilize task-specific network to extract descriptive multidimensional embed- dings the input data. In image generation evaluation, the activations of a hidden layer in Inception
While any set of graph statisties can he compared using MMD, these three are the most common and hence evaluated this work.
3

---

Published as a conference paper at ICLR 2022
GGM training
Graph ambeddinge
ANN
i
Metric calculator:
GNN feature
Reecl KD
Generated
Figure 1: The standard process of evaluating GGMs using NN-basce metries.
v3 (Szegedy et al. 2016) are frequently used as vector representations of the input images (Heusel et al. 2017). These NN-based metrics can be applied to GGM evaluation by replacing Inception v3 with a GNN (Thompson et al., 2020; Liu et al. 2019). This prompts the use of a wide range of evaluation metries that have been studied extensively in the image domain. Computation of these metrics follow a common setup and differ only in how the distance between two sets of data are determined (Figure I.
Fréchet Distance (FD) (Heusel et al. 2017) is one of the most popular generative metrics. FD approximates the graph embeddings continuous multivariate Gaussians with sample mean and covariance fA, C. The distance between distributions is computed as an approximate measure of sample quality: FD(S,.,g) = ||, 1oll2 + Tr(C, + C. C(C,
Improved Precision & Recall (P&R) (Kynkäänniemi et al., 2019) decouples the quality of a gen- crator into two separate values to aid in the detection of mode collapse and mode dropping. Mode dropping refers the case wherein modes of P, underrepresented by Pg. while mode collapse describes a lack of diversity within the modes of Pg. Manifolds are constructed by extending a ra- dius from each embedded sample in a set to its 4tth nearest neighbour to form a hypersphere, with the union of all hyperspheres representing manifold. Precision is the percentage of generated samples that fall within the manifold of real samples, while Recall is the percentage of real samples that fall within the manifold of generated samples. The harmonic mean ("F1 PR"" of P&R is scalar metric that can be decomposed into more meaningful values in experiments (Lucic et al.) (2018).
Density & Coverage (D&C) (Nacem al., 2020 have recently been introduced robust alterna- tives for Precision and Recall, respectively. As opposed to P&R which take the union of all hyper- spheres to create a single manifold for each set, D&C operate on each samples hypersphere inde- pendently. Density is calculated as the number of real hyperspheres a generated sample falls within on average. Coverage is described as the percentage of real hyperspheres that contain a generated sample. The hyperspheres used are found using the 1:th nearest neighbour as in P&R. As with P&R, the harmonic mean ("F1 DC") of D&C can be used to create a scalar metric (Lucic et al. 2018).
MMD (Gretton et al., 2006 (Equation D can also be used to measure the dissimilarity between graph embedding distributions. The original Kernel Inception Distance (KID) (Binkkoskii et al.) 2018) proposed a polynomial kernel with MMD, A(x,, x,) (²x, x, + +))3, where d is the embed- ding dimension. The linear kernel k k(,,,,,) = x, X, is another parameter- free kernel used with MMD evaluate generative models (O Bray al. 2022). In addition, the RBF kernel (Equation 2
with .) -) as the Euclidean distance is widely used (Xu et al. 2018 Gretton et al. 2006). The
choice of a in Equation 2 has significant impact the output of the RBF kernel, and methods for
finding and selecting an optimal value is an important area of research (Bach et al.) 2004 Gretton al. 2012a b). A common strategy is select as the median pairwise distance between the two comparison sets (Garreau et al.) 20188 Gretton et al.) 2006 [Schölkopf et al. 1998). Another strat- egy is evaluate MMD using a small set of a values and select the value that maximizes MMD: = arg max,ey: MMD(S,, g S,; (Sriperumbudur et al. 2009). We combine these ideas in our o selection process, and more details are available in Appendix We refer to these metrics as "KD,"
"MMD Linear," and "MMD RBF"
2.4 BENCHMARKING EVALUATION METRICS
Our work closely related to other works benchmarking evaluation metrics of generative mod- els (0 Bray al.) 2022 Xu et al. 2018). A consistent method for assessing evaluation metrics is to start with the creation of "reference" and "generated" sets S, and Sy that originate from the same real distribution P.. Then, metric's 's response to the distortion. In the image domain, Xu et al. (2018) develop multiple experi- ments to test metrics for key properties. The metrics then subjectively evaluated for these proper-
gradually increases distortion to the generated set while recording each
4

---

Published as a conference paper at ICLR 2022
Grid graph
Edges rewired with p 0.1
Edges rewired with 0.9
0 Real Graphs
Corrupted Graphs
Pretrained
Random GIN
Figure 2: Top: Example of grid graph corrupted by rewiring edges with various probabilities p. Bottom: Principal component analysis (PCA) of embeddings obtained using the pretrained and random GINs for grid graphs with different rewiring probabilities. For strong feature extractor, diverge from the real graphs embedding space as the edge rewiring probability grows. The random GIN extracts as strong a representation as the pretrained GIN which indicates it may he useful GGM evaluation.
expect the corrupted graphs to
ties by manually analyzing each metric's response across experiments. In concurrent work, O Bray itt al. (2022) introduced additional GGM evaluation metrics. Similar Xu et al. (2018), the metrics are validated through experiments that slowly increase the level of perturbation in each graph in the generated set. However, O O'Bray et al. (2022) incorporated an objective evaluation score by com- puting the Pearson correlation of each metric with the degree of perturbation. Although objective, evaluation using Pearson correlation is biased in that the relationship between the metric and degree of perturbation need not be linear. Our work also unique in considering random embeddings.
THE EFFECTIVENESS OF RANDOM GNNS
While Inception v3 Szegedy et al. 2016) has found widespread in evaluation of generated sam- ples (Salimans et al. 2016 Cai et al.[2018 Lunz et al. 2020), there is no analogue in graph-based tasks. This prevents standardized analysis of GGMs. To tackle this, a single GNN may be pre- trained on multiple datasets such that it extracts meaningful embeddings on new datasets (Hu et al.) 2020). However, node and edge features often have incompatible dimensions across graph datasets. In addition, the distributions of graphs in the pretraining and target tasks can vary drastically, de- grading the performance of a pretrained network. However, random GNNs are capable of extracting meaningful features and solving many graph tasks (Kipf & Welling 2017] Morris et al.] [009 Xu itt al. 2019) Thus, avoiding pretraining and instead utilizing random GNNs may a viable strat- egy to bypass these issues. To preliminarily test this approach, we apply permutations to Grid graphs by randomly rewiring edges with probability p. Therefore, as we increase p, the dissimilarity be- tween the original graphs and permuted graphs increases. Thus, if GNN is capable of extracting strong representations from graphs, the dissimilarity between graph embeddings should also increase with p. We visualize the embeddings extracted from a pretrained GIN (Xu al. 2019) and random GIN in Figure [ and find that they extract very similar representations throughout this experiment. This indicates that both random and pretrained GINs may be capable of evaluating GGMs. We use GIN throughout all experiments due to its theoretical ability to detect graph isomorphism (Xu et al.) C.6
2019, however, we also provide a comparison other common GNNs in Appendix C.6
4 EXPERIMENTS
In this section, describe key properties of strong GGM evaluation metric and thoroughly test each metric for these properties. These properties include a metric's ability to correlate with the fidelity and diversity of generated graphs, its sample efficiency, and its computational efficiency. We argue that these properties capture many desired characteristies of a strong evaluation metric and enable reliable ranking of GGMs. In many cases, adapt the experiment design of Xu et al. (0188) to the graph domain.
PIn the image domain, random CNNs are also beneficial in certain cases, such large distribution shifts (Naeem et 2020
5

---

Published as a conference paper at ICLR 2022
Datasets.
We experiment using six diverse graph datasets to test each metric's ability evaluate GGMs across graph domains (Table I). In particular, we include common GGM datasets such as Lobster, Grid, Proteins, Community, and Ego (You al., 2018 Liao al. 2019 Dai et al. 2020). In addition, we utilize the molecular dataset ZINC (Irwin et al. 2012) strietly to demonstrate the ability of each metric to detect changes in node and edge feature distributions (Section 4.3 We
provide thorough descriptions of the datasets in Appendix B
GNN feature extractor. As the GGM literature fre-
Table 1: A summary of the datasets.
quently uses small datasets, the sample efficiency of each metric is extremely important. Furthermore, as the dimensionality of the graph embedding x is a key factor in many of the metrics in Section [.3 there is a bias towards minimizing the length of x while retaining discriminability. As seen in Equation + the number of propagation rounds L and the node embedding size d are directly responsible for determining the dimensionality of x. In addition, You et al. (2020) demonstrate that the choice of L is one of the most critical for performance across diverse graph tasks. Thus, in our experiments we consider GIN models (Equations and (4) with L E [2, ........ 77. and d [5, 10, ..... 40). We randomly select 20 architectures inside these ranges to test in our experiments using both randomly initialized and pretrained GINs. The pretraining process tasks each network with graph classification and the methodology is described in Appendix Results for metries computed using a pretrained GIN in individual experiments are left to Appendix C.I How- ever, we summarize these results in Table 3 jn Section to facilitate discussion. We use node degree features expressed as an integer as an inexpensive way to improve discriminability in both random and pretrained networks. In practice, we utilize orthogonal weight initialization (Saxe et al. 2014) in the random networks as it produces metrics with slightly lower variance across initializations.
NODELEDGE FEATURES
DATASIT
ASAMPLRS
[4]
[F]
Grid
100
100-400
368
Lobster
100
10-100
13-100
Proteins
918
103:500
186-1375
Ego
757
57-1071
Comounity
500
60-160
300-18000
ZINC
1000
10-50
22-82
Evaluating the evaluation metrics. All experiments are designed to begin with Pg RV Pr, and to have a monotonically increasing degree of perturbation E [0. 1] that is a measure of the dissim- ilarity between S, and S,., We evaluate each metric objectively by computing the Spearman rank correlation between the metric scores á and the degree of perturbation t. Spearman rank correlation is preferable to Pearson correlation as it avoids any bias towards a linear relationship. All metrics normalized such that and a rank correlation of 1.0 is assumed to be ideal. We test each metric and GIN architecture com- bination across 10 random seeds which affects GIN model weights (if applicable) and perturbations applied. To report the results for a given metric, we first compute the rank correlation for a sin- gle random seed (which varies model weights and perturbations applied, if applicable). experiment (e.g. edge rewiring). dataset (c.g. Grid) and GIN configuration (if applicable, e.g. L = 4, d = 25). We then aggregate the rank correlation scores across any combination of these factors of variation.
if P. Pg meaning that á should increase with for a strong metric
4.1 MEASURING FIDELITY
One of the most important properties of metric is its ability to measure the fidelity of generated samples. To test metrics for fidelity we construct two experiments. The first experiment tests the metric's ability to detect various amounts of random samples mixed with real samples (Xu et al., 2018), while the second experiment slowly decreases the quality of graphs by randomly rewiring edges (O' Bray et al. 2022). Each of these experiments begin with Sy as a copy of S,, which is itself a copy of the dataset.
In the first experiment, similarity between S, and S. we slowly mix random graphs by increasing the ratio / of random graphs real graphs in (C). We simultaneously remove real graphs such that [S,] is constant throughout. The random graphs are Erdös-Rényi Rényi (E-R) graphs (Erdös & Rényil 1960) with sizes and p values chosen to resemble S,:: for every G, E S,, there a corresponding E-R graph G, with which is the sparsity of G,.. V
utilize random graphs to impact the quality of Sy. To decrease the
|7/ = I and p
[E).
The second experiment increases distance between P, and P, by randomly rewiring edges in Sy- Here, the degree of perturbation t is the probability of rewiring each edge (i.j). E E. For each G Sy and each (i.j) E E, a sample Iijj Bernoulli(t) is drawn. Edges with Ta.j = are rewired, another sample Vi.j ~ Bernoulli (0.5) is drawn to decide which node {i.j} of the edge is kept, and new connection for this edge is chosen uniformly from V.

---

Published as a conference paper at ICLR 2022
Mixing random
Rewiring edges
Rewiring edges
1.0
1.0
Rank comelatiio
0.5
0.0
0.0
0.2
Deminn
Rocal
Oivrngge
Fl Fl
F1oC
FD-
Cluseeiigg MMO
Degren reeo
Orbis HeD
NSPDO HenO
Preciiion
Denstt
fucall
cavenger
Fl F1
Fi FloC
FD
KD
NMO Rir
Clusuriig NMO
Degras HNO
Drbas neeo
NSPOK reoo
0.0
0.2
0.4
0.8
1.0
Degree perturbation
MND
MMD
Degres HMD
Inani MMO
collapse
Mode dropping
dropping
1.0
Pank comeiation
0.8
0.0
0..4
-05
0.0
0.0
0.2
0.4
0.6
0.8
3.0
Degree of perturbation
Figure 3: Results from the fidelity (top) and diversity experiments (hottom). NN-based metrics using random GIN are highlighted in red, while classical metries are in blue. Results aggregated across all datasets and all GIN configurations (if applicable). For violin plots, white dots are the median, thick black lines are the IQR, and thin black lines are the whiskers. The plots on the right show the mean value of select metrics throughout given experiment. Fidelity: Several NN-based and classical metrics perform nearly optimally across both experiments with median rank correlations close to 1.0. Diversity: Classical metries are below average in the mode collapse experiment, and suboptimal in the mode dropping experiment. Scalar metrics such as MMD RBF have median rank correlations close to 1.0 and perform extremely well across both experiments.
Results. With the exception of Recall and Orbits MMD, the majority of tested metrics excel in these experiments as indicated by rank correlation close to 1.0 (Figure top). However, Recall is specifically designed to measure diversity of S, rather than fidelity, and its low sensitivity to fidelity here is expected. Surprisingly, Coverage demonstrates strong sensitivity to the fidelity of Sy although it is also designed to measure the diversity of Sy. In addition, we repeat the mixing experiment with graphs generated by GRAN (Li et al. 2018) and obtain similar results (see Appendix C.4)
4.2 MEASURING DIVERSITY
The next property investigate is metric's ability measure the diversity of generated samples in Sy. We focus on two common pitfalls of generative models that a strong metric must be sensitive to: mode dropping and mode collapse. We test each metric for both sensitivities independently by adapting two experiments from Xu et al. (2018) to the graph domain, both of which begin by clustering the dataset using Affinity Propagation (Frey Dueck (007)) to identify the modes of P,.. Both of these experiments begin with S, and S, as disjoint halves of the dataset.
To simulate mode collapse, we progressively replace each datapoint with its cluster centre. The degree of perturbation represents the ratio of clusters that have been collapsed in this manner. To simulate mode dropping, we progressively remove clusters from Sy. To keep [Sy] constant, we randomly select samples from the remaining clusters to duplicate. In this experiment, the degree of perturbation is the ratio of clusters that have been deleted from Sg.
Results. In the mode collapse experiment, all classical metrics Yoou et al. 2018) perform poorly with a rank correlation less than 0.5 (Figure 3 bottom). Classical metrics obtain slightly better, though still suboptimal results in the mode dropping experiment. As expected, Recall and Coverage exhibit strong positive correlation with the diversity of Sy. while Precision and Density are nega- tively correlated. In addition, several scalar metrics such as MMD RBF and F1 PR exhibit strong correlation with the diversity of Sy and outperform classical metrics across both experiments.
4.3 SENSITIVITY TO NODE AND EDGE FEATURES
In this experiment, we measure the sensitivity of each metric to changes node or edge feature dis- tributions while the underlying graph structure is static. Similar to the rewiring edges experiment, this is performed by randomizing features with a monotonically increasing probability t, and we pro- vide more thorough descriptions of these experiments in Appendix B We exclude metrics from You
7

---

Published as a conference paper at ICLR 2022
et al. (2018) in these experiments they are unable incorporate both edge and node features in evaluation. We find all NN-based metrics and NSPDK MMD are sensitive to these perturbations, and summary is provided in Table 3
4.4 SAMPLE EFFICIENCY
Small datasets are frequently used in the GGM literature so the notion of sample efficiency is impor- tant. In this experiment, we determine the sample efficiency of each metric by finding the minimum number of samples to discriminate set of random graphs S, from real samples S,.. The random graphs are E-R graphs generated using the same process described in Section 4.1 We begin this experiment by sampling two disjoint sets S and S from Sy, and a set of random graphs "g from = | = n and small n. A metric with high sample efficiency should measure with small n. Rather than using rank correlation, in this experiment we record the sample efficiency of each metric as the smallest n where p(S',, Sy) < p(S), ()) Vi 2 n. All of the metries based on K K-nearest neighbours and many of the classical metries exhibit high sample efficiency and require a minimal number of samples to correctly score S/: and S (Table
Sg with | = s
F
pSS',, S < p
4.5 COMPUTATIONA EFFICIENCY
Computational efficiency is the final property of an evaluation metric that we examine. Metrics that are efficient to compute are ideal as they can be easily used throughout training to measure progress and perform model selection. Graph datasets can scale in several dimensions: the num- ber of samples, average number of nodes, and average number of edges. We make use of E-R graphs to generate graphs with an arbitrary number of nodes and edges enabling to independently scale graphs each dimension. The results highlighting each metric's computational efficiency as dataset size increases 10,000 samples is shown in Table 3 while the results for all dimensions are presented in Figure 10 in Appendix C The classical metrics You et al. 2018) quickly become prohibitive compute the number of samples increase, while the NN-based metrics faster by several orders of magnitude and are inexpensive to compute at any scale.
4.6 GGM SELECTION
While NN-based metrics such MMD RBF and Fl PR have performed consistently in exper- iments, this does not necessarily mean they are suited for evaluating GGMs. With the lack of an Inception v3 (Szegedy al. 2016) analogue for GGM evaluation, these metrics must be consistent across model parameterizations. Thus, in this section we evaluate two popular generative models, GRAN (Liao al. 2019) and GraphRNN (You al., 2018) the Grid dataset. To measure the variance induced by changing model parameterizations. we compute p(S,, S,) across 10 different random GINs. We use the strongest GIN configuration along with strong NN-based metric. MMD RBF, both of which we identify in Section 5 We simulate the model selection process by evaluat- ing models at various stages of training and find that metrics from You al. (2018) are unable to unanimously rank GGMs (Table 2 As GGMs are frequently evaluated by considering all of these metries together, this highlights the difficulty that may arise during model selection with this evalu- ation process. Furthermore, we find that MMD RBF is extremely low variance across random GINs indicating its promise for evaluating GGMs. Additional strong NN-based metrics such as PR and F1 DC are tested in Table 12 in Appendix C.8 and are also found to be low variance. Note that we also compute all metrics using a 50/50 split of the dataset. This provides information regarding what score two sets of indistinguishable graphs may receive and represents ideal value for the given dataset. We suggest that future work also follows this process as it provides a sense of scale and improves interpretability of the results.
DISCUSSION
We aggregate the results across experiments for high-level overview of each metric's strengths and weaknesses Table 3 Metrics computed using a pretrained GIN are nearly indistinguishable from those using random GIN across rank correlation experiments (columns 3-4). Although metrics using a pretrained GIN benefit from slightly higher sample efficiency, they can have higher variance across model parameters than simple random initialization (Table 12 in Appendix C.8). Similar to
8

---

Published as a conference paper at ICLR 2022
Table Summary of each metric's 's performance across experiments. Column headings indicate the experiment across which results are aggregated. NN-based metrics are aggnegated across all GIN configurations using random networks unless otherwise stated. Computational efficiency is taken to be the maximum recorded time reported in Figure T0 Values reported are the mean + std. error, and the average in the final row is taken strictly across the NN-hased metries. Cells are colored if the results can he interpreted objectively for the given experiment (i.c., experiments that use rank correlation to measure performance).
METRIC
FIDELITY
DIVERSITY
FIDELITY DIVERSITY (RANDOM/PMETRAINED)
NODE/EDGE FEATS.
SAMPLE EPS, (RANDOMEPHTRAANNE)
CCMP. EFF. (5)
Orbiss MMD
0.37 +: 0. 0.048
0.49 +: 0.046
0.43 0.034
N/A
122 + 22
1.4e
Degree MMD
1.00 1: 000
0.51 1: 0.061
0.76 0.035
N/A
9:1:1
7.5e 3
Clustring MMD
0.98 :: 0.003
0.43 143::00 0.047
0.72 0.030
NIA
7
1. 1.1e
NSPDK MMD
0.99
0.78 0.050
0.88 0.028
382
0.98 0.002
0.013
0.71
0.008
0.74 + 0.007
0.96
0.010
58 +
4.5
0.62 0.015
0,32
0.47
0.010
0.58
0.009
0.94
0.011
89
5.1
Precision
0.82 + 0.007
0.25
0.010
0.29 = 0.011
0.29
+ 0.011
0.98 + 0.001
7 7
7 7
18
Recall
0.70 + 0.007
0.93 + 0.003
0.82 = 0.004
0.81 + 0.005
0.80 + 0.018
7+0
7
18
Donsity
0.90
-0.10 0.100:00001
0.40
0.012
I 0.001
12
Covenag
0.91 + 0. 003
0.95 0.003
0.93 0.002
0.93 + 0.003
0.99 - 0.030
7
7
12
FI PR
0.922 + U. 004
0.93 + 0.003
0.93 = 0.003
0.93 + 0.002
0.99 + 0.030
7 7
7
18
FI DCC
0.95 + 0.002
0.86 : 0.007
0.91
0.004
0.88 + 0.004
0.99 = 0.000
7
7
12
MMD Linear
0.98
0.37
0.68 0.008
0.007
0.005
57
4.5
REP
0.97
0.95 0.003
0.96
0.002
0.97 + 0.002
0.001
42
120
Average INN based)
0,039
0.54 0.144
0.71 0.078
0.72 + 0.076 0.96 0.019
10
7
Table 3 we aggregate the results across all experiments and metrics for a specific GIN configuration in Table 4bb in Appendix [ We find that the mean rank correlation taken across NN-based metrics and all experiments is approximately 10x higher variance than the mean taken across GIN config- urations (0.078 and 0.007, respectively). In general, our findings indicate that the key to strong GIN-based GGM evaluation metrics is the choice of metric rather than the specific GNN used to extract graph embeddings.
Table 2: Evaluation of different GGMs at various percentages of total epochs trained the Grid dataset. Cells are colored according to their rank in given column.
In practice, to measure the distance be- tween two sets of graphs we recommend the use of either the MMD RBF or F1 PR metries. Although we found the choice of GIN architecture to be unimportant, we suggest the use of a random GIN with 3 rounds of graph propagation and a node embedding size of 35 for consistency in future work. This is the strongest GIN configuration across all experiments (Table 4b in Appendix C.2). Both metrics have been shown to be sensitive to changes in both fidelity and diversity while having minimal variance across random initializations. In addition, they are capable of detecting changes in node and edge feature distributions, making them useful for a wide array of datasets To highlight this, we provide results for individual datasets in Appendix B. and find the performance of GNN-based metrics to be consistent across all datasets. While MMD RBF has slightly stronger correlation with the fidelity and diversity of generated graphs, Fl PR has superior sample and computational efficiency. Thus, we suggest the use of Fl PR in cases where there are fewer samples than the measured sample size of MMD RBF (i.e., 42) or MMD RBF extremely prohibitive to compute, otherwise, we suggest MMD RBF.
GGM
MMD RBF
Clas.
Deg.
Orbii
50/50 split
0.042
0.0
6.51. -b
0.018
GnphRNN- 100%
0.184 1: 5e
4.59e
0.032
0.252
GrapRRNN 66%
1.69e -
0.015
0.169
GRAN-100%
0.063 0.001
1.24c
1.68c
0.037
GRAN-669
0.061
0.001
3.15e -
3.20,
0.047
CONCLUSION
We introduced the use of an untrained random GIN in GGM evaluation, inspired by metrics popular in the image domain. We discovered that pre-existing GGM metrics fail to capture the diversity of generated graphs, and find several random GIN-based metrics that are more expressive while being domain-agnostic at a significantly reduced computational cost. An interesting direction for future work is provide theoretical justification supporting the use of random GINs, well as the exploration of more sophisticated GNNs to improve sample efficiency.
"This is not to say that they are the only metrics that should be used to evaluate GGMs. For example, in the molecular domain percent valid or druglikeness can provide valuable information that is not explicitly measured by our metrics. In addition, if the goal is for generated graphs to resemble reference set based on singular graph statistic, the metrics from You et al. 2018) still invaluable.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
BK and RT received support from NSERC. RT received funding from the Vector Scholarship in Artificial Intelligence. BK received support from the Ontario Graduate Scholarship. GWT acknowl- edges support from CIFAR and the Canada Foundation for Innovation. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Govermment of Canada through CIFAR, and companies sponsoring the Vector Institute: http://wwed wttp:w/weetrrinsoeo tute. ai @il#part.ners
REFERENCES
Francis R. Bach, Gert R. G. Lanckriet, and Michael I. Jordan. Multiple kernel learning, conic duality, and the smo algorithm. Proceedings of the International Conference on Machine Learning (ICML), 2004.
Victor Bapst, Alvaro Sanchez- Carl Doersch, Kimberly Stachenfeld, Pushmeet Kohli, Pe- ter Battaglia, and Jessica Hamrick. Structured agents for physical construction. In Proceedings of the International Conference Machine Learning (ICML., 2019.
Mikotaj Biñkkwski,, Danica Sutherland, Michael Arbel, and Arthur Gretton. Demystifying MMD GANs. arXiv preprint arXiv:1801.011 101100111111 2018.
Haoye Cai, Chunyan Bai, Yu-Wing Tai, and Chi-Keung Tang. Deep video generation, prediction and completion of human action sequences. In Proceedings of the European Conference on Computer Vision (ECCV), 2018.
Xiaohui Chen, Xu Han, Jiajing Hu, Francisco Ruiz, and Liping Liu. Order matters: Proba- bilistic modeling of node sequence for graph generation. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 1630-1639. PMLR, 18-24 Jul 2021. URL https::/pprceediin
mlr htt.eeeddd..nnnnl....eeeee///sss http:////1///hhhe21ee1 chen21i .hmml
Fabrizio Costa and Kurt De Grave. Fast neighborhood subgraph pairwise distance kernel. In Pro- ceedings of the 27th International Conference on International Conference on Machine Learning, ICML' 10, pp. 255-262, Madison, WI, USA, 2010. Omnipress. ISBN 978 175558957777.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative mod- eling for sparse graphs. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: large-scale hicrarchical image database. In Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
Paul D. Dobson and Andrew J. Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-783, 2003.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 17-60, 1960.
Brendan J. Frey and Delbert Dueck. Clustering by passing messages between data points. Science, 315(5814))922-976, 2007.
Damien Garreau, Wittawat Jitkrittum, and Motonobu Kanagawa. Large sample analysis of the median heuristic. arXiv preprint arXiv: 077669 2018.
Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain- agnostic labeled graph generation. Proceedings of The Web Conference 2020, Apr 2020. doi: 3380201
10.1145/33644233380001 Uttpttp: dx doi.
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. kernel method for the two-sample problem. In Advances in Neural Information Pro- cessing Systems (NeurIPS), volume 19, 2006.
10

---

Published as a conference paper at ICLR 2022
Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander J. Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(1):723 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 Advances in Neural Information Processing Systems (NeurIPS), volume 22, 2012b.
William I.. Hamilton, Rex Ying, and Jure Leskovec. graphs, 2018.
Inductive representation learning on large
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, Günter Klambauer, and Sepp Hochreiter. GANs trained by two time-scale update rule converge a nash equilibrium. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
John J. Irwin, Teague Sterling, Michael M. Mysinger, Erin S. Bolstad, and Ryan G. Coleman. ZINC: A free tool discover chemistry for biology. Journal of Chemical Information and Modeling, 52 (7):1757-1768, 2012.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Multi-objective molecule generation using interpretable substructures. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Ana Justel, Daniel Peña, and Ruben Zamar. A multivariate kolmogorov-smirnoy test of goodness of fit. Statistics & Probability Letters, 35:251-259, 10 1997. doi: 10. 10.1016600167-7757770000222
Wataru Kawai, Yusuke Mukuta, and Tatsuya Harada. Scalable generative models for graphs with graph attention mechanism, 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Proceedings of the International Conference Learning Representations (ICLR), 2017.
Xiangzhe Kong, Zhixing Tan, and Yang Liu. GraphPiece: Efficiently generating high-quality molec- ular graph with substructures. arXiv preprini arXiv:2106. 15098, 2021.
Tuomas Kynkäänniemi, Tero Karras, Samuli Laine, Jaakko Lehtinen, and Timo Aila. Improved precision and recall metric for assessing generative models. In Proceedings of the International Conference on Machine Learning (ICML), 2019.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv: /aoo.0332333444 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, William L Hamilton, David Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks In Advances Neural Information Processing Systems (NeurIPS), volume 32, 2019.
Chia-Cheng Liu, Harris Chan, and Kevin Luk. Auto-regressive Graph Generation Modeling with Improved Evaluation Methods. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are GANs cre- ated equal? a large-scale study. In Advances in Neural Information Processing Systems (NeurIPS), volume 31, 2018.
Sebastian Lunz, Yingzhen Li, Andrew Fizzgibbon, and Nate Kushman. Inverse graphics GAN: Learning to generate 3D shapes from unstructured 2D data. arXiv preprint arXiv:2002. 12674, 2020.
Sebastian Moreno, Jennifer Neville, and Sergey Kirshner. Tied kronecker product graph models to capture variance in network populations. ACM Trans. Knowl. Discov. Data, 12(3), mar 2018. ISSN 1556-4681. doi: 10.1145/3161888 URL. htRl.tttp:///// //otis .rg 111.1.1..11.55 885

---

Published as a conference paper at ICLR 2022
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman go neural: Higher-order graph neural networks In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2019.
Muhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh, Yunjey Choi, and Jaejun Yoo. Re- liable fidelity and diversity metries for generative models. In Proceedings of the International Conference on Machine Learning (ICML), 2020.
Lestie O' Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metrics for graph gen- erative models: Problems, pitfalls, and practical solutions. In International Conference on Learn- ing Representations, 2022. / net. wtt.://ooooommdmttttooo/ooo
Marco Podda and Davide Bacciu. Graphgen-redux: a fast and lightweight recurrent model for labeled graph generation, 2021.
Mariya Popova, Mykhailo Shvets, Junier Oliva, and Olexandr Isayev. MolecularRNN: Generating realistic molecular graphs with optimized properties. arXiv preprint arXiv:/905. 13372, 2019.
Kristina Preuer, Philipp Renz, Thomas Unterthiner, Sepp Hochreiter, and Günter Klambauer. Fréchet chemnet distance: metric for generative models for molecules in drug discovery. Journal of chemical information and modeling, 58(9):1736- 2018.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. In Advances in Neural Information Processing Systems (NeurIPS), volume 29, 2016.
Bidisha Samanta, Abir De, Gourhari Jana, Vicenç Gómez, Pratim Kumar Chattaraj. Niloy Ganguly, and Manuel Godrizzo NeVAB: A deep generative model for molecular graphs. Journal of Machine Learning Research, 21 (111144)1133 2020.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dy- namics of learning in deep linear neural networks. In Proceedings of the International Conference on Learning Representations (ICLR), 2014.
Bernhard Schölkopf, Alexander J. Smola, and Klaus Hlburt Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, (1S9:1299-1311) 1998.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad Collective classification in network data. Al Magazine, 29(3):93, Sep. 2008
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(77); 2539-2561, 2011.
Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. GraKeL: A graph kernel library in Python. Journal of Machine Learning Research, 21(54):1-5, 2020.
Bharath K. Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Gert R. G. Lanckriet, and Bernhard Schölkopf. Kernel choice and classifiability for RKHS embeddings of probability distributions. In Advances in Neural Information Processing Systems (NeurIPS), volume 22, 2009.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE International Confer- ence on Computer Vision and Pattern Recognition (CVPR), 2016.
Lucas Theis, Aäron van den Oord, and Matthias Bethge. A note the evaluation of generative models, 2016.
Rylee Thompson, Elahe Ghalebi, Terrance DeVries, and Graham W. Taylor. Building LEGO using deep generative models of graphs. In NeurlPS Workshop on Machine Learning for Engineering Modeling, Simulation, and Design (MIAFng), 2020.
12

---

Published as a conference paper at ICLR 2022
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22)) 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the International Conference on Learning Representations (ICLR), 2019.
Qiantong Xu, Gao Huang. Yang Yuan, Chuan Guo, Yu Sun, Felix Wu, and Kilian Weinberger. An empirical study on evaluation metrics of generative adversarial networks. arXiv preprint arXiv:1806.07755 2018.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovee. GraphRNN: Gen- erating realistic graphs with deep auto-regressive models. In Proceedings of the International Conference Machine Learning (ICML., 2018.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.
A Appendices
Additional metric details
14
Additional experimental details
14
Datasets
14
B.2
Measuring diversity
14
B.3
Randomizing edge features
15
B.4
Randomizing node features
15
B.5
Computational efficiency
15
B.6
GGM selection
15
B.7
GNN pretraining
15
Additional results
16
Individual experiments
16
All experiments grouped by GIN configuration
16
All results grouped by dataset
16
Mixing generated graphs)
23
Computational efficiency
23
Comparing other GNNs
24
Comparing selection strategies
25
8
GGM selection
26
C.9
Stability of GGM rankings
28
13

---

Published as a conference paper at ICLR 2022
A ADDITIONAL METRIC DETAILS
For Precision, Recall, Density, and Coverage, we set k = 5 for all experiments (Naeem et al. 2020) For the MMD RBF metric, compute MMD as MM, Σ}, where the values of Σ are multiplied by the mean pairwise distance of S, and S,- While the median pairwise distance is the heuristic (Garreau al., (018), find the mean to be more robust in our experiments. Before this scaling factor is applied, we use Σ {0.01, 0.1, 0.25, 0.5, 0.75, 1.0, 2.5, 5.0, 7.5, 10.0). For all baseline metrics from You al. (0188), we use the hyperparamettrss chosen in their open-source code. For the NSPDK MMD metric we use the open-source code from Goyal al. (2020)
maX(MMD(S S
B ADDITIONAL EXPERIMENTAL DETAILS
Following Section 2.2 we denote graph as G = E) with vertices V and edges E. {(i.5) i,j .1...... VI)..
(0) in Section 2.2 Similarly, A E R Node features for node E V are denoted as h, E R (h. stores edge information, with the (i,j)th entry corresponding to the edge features for edge (i. Unless otherwise specified in Appendix B.1] A not utilized and we set h, the degree of node expressed as an integer as an inexpensive way to improve discriminability. We handle edge features by concatenating As.j. to messages from node to node j at each round of graph propagation (Hu
al. 2020).
B. DATASETS
We perform experiments using a variety of datasets with varying sizes and characteristics to thor- oughly test each metric's ability to evaluate GGMs across domains. We place slight emphasis datasets that are frequently used in the GGM literature.
Lobster. A set of 100 stochastic graphs where each node is at most 2 hops away from backbone
path. We generate lobster graphs with 10 < |V] S 100 (Dai et al. 2020).
Grid. 100 2D grid graphs generated with 100
V S
400 (Dai al.
2020
You al.
2018
Liao
et al. 2019).
Proteins. 918 protein graphs where nodes amino acids and two nodes connected by an edge
they are less than 6 Angstroms away (Dobson & Doig 2003). We select graphs with 100 S V S
500 YYou al. 2018 [iao et al., 2019 Dai al. 2020).
Ego. 757 3-hop ego networks with 50 S [V] S 399 YYu et al. 2018). Graphs are extracted from the CiteSeer network where nodes represent documents and edges represent citation relationships (Sen)
ct al. 2008).
160. Each community is generated by the Erdös-Rényi model (E-R) (Erdōs & Rényi 1960) with n = / and = 0.3. We then add 0.05|V| inter-community edges with uniform probability You al. 2018).
Community. 500 two-community graphs with 60
V
ZINC. 250k real-world molecular graphs (Irwin et al. 2012) of which we randomly select 1000 samples for efficiency with 10- < V S 50. We h, of node i, and Aij.: to be a one-hot encoding a E IR" of the bond type between nodes i and j. This dataset is unique in that it is the only one naturally contain node and edge features. Thus, we can use this dataset to determine metric's sensitivity to changes in the edge and node feature distributions without generating artificial labels.
a one-hot encoding of the element
B.2 MEASURING DIVERSITY
We employ Affinity Propagation (rry & Dueck 2007 to automatically determine the number of clusters, and set the similarity between graphs to be the value obtained from the WL-subtree ker- nel (Shervashidze et al. 22011) using the GraKel Python library (Siglidis et al. 2020). This clustering method avoids any dependency on the GNN model architecture and ensures the clusters found are consistent across all experiments.
14

---

Published as a conference paper at ICLR 2022
B.3 RANDOMIZING EDGE FEATURES
This experiment is performed exclusively on the ZINC dataset it naturally contains edge features. Here, the degree of perturbation / is the probability of randomizing each edge feature Aijas V(i,j) E E. For each G Sy and each edge (i,j) E, sample Σı.j Bernoulli(t) is drawn. Edges with Jij = have their edge feature randomized. As these features are a one-hot encoding, we sample the new edge feature uniformly from the of valid edge features. The results of this experiment are shown in Figure
B.4 RANDOMIZING NODE FEATURES
This experiment is performed exclusively on the ZINC dataset as it naturally contains node features. Here, the degree of perturbation For each G E S and each node i V, sample have their feature randomized. As these features are a one-hot encoding, we sample the new node feature uniformly from the set of valid node features. The results of this experiment shown in Figure
the probability of randomizing each node feature h, Vi E V.
Bernoulli(t) is drawn. Nodes with
B.5 COMPUTATIONAL EFFICIENCY
All experiments in this section were conducted on an Intel Platinum 8160F Skylake @ 2. 2.1Ghz with CPU cores. We benchmark NN-based metrics using the most expensive GIN configuration tested in our experiments. This was configuration with 7 propagation layers and node embedding size of 20. The results for this experiment on CPU are shown in Figure TO and on GPU Figure [I] In addition, the approximate RAM usage for each metric throughout these experiments are shown in Figure and Table
Scaling number of samples. We generate various sets of E-R graphs (Erdós & Rényi 1960) to scale the number samples in a dataset independently from the number of nodes and number of edges per graph. We generate sets of graphs with the number of samples in [100, 1000, 2000. ... 10k] with | = 50 for all graphs. We choose p IV
|Eles for all graphs, where the averages are taken
across the Proteins dataset.
Scaling number of edges. To scale the number of edges independently, we generate 50 E-R graphs per set with V 1000. The graphs are generated with in [0.01, 0.1, 1.0].
Scaling number of nodes. We generate 50 graphs a constant size per set with [V] in [1000, 10k, 10000 edges per graph.
For each set, we use 10000 to generate graphs with approximately V
B.6 GGM SELECTION
We train GRAN (Lioo et al.) 2019) and GraphRNN (oou et al., 2018) with 80% of the graphs randomly selected for training. We use the implementations in the official GitHub repositories and train using the recommended hyperparameters. We then generate graphs from each model where n is the size of the dataset, and use the remaining 20% of graphs as S,.
B.7 GNN PRETRAINING
We isolate the comparison between randomly initialized and pretrained weights to datasets without node or edge features (i.e. excluding ZINC). The GNN is trained under the multiclass classification setting to classify a given graph into the remaining datasets. To increase the difficulty of the problem, for each graph G, in the remaining datasets, we generate an E-R graph (Erdös Rényil 1960) G,
with |V = |r, and p = EE
- These E-R graphs have separate labels, thereby doubling the
number of classes present. We use the optimizer across all experiments and select the model with the lowest validation loss. We train each configuration across 10 random seeds to perform a fair comparison with the 10 different random initializations used in our experiments.
15

---

Published as conference paper at ICLR 2022
Random weights
Pretrained weights
Baneline metrics
0.75
0.50
0.00
0.25
-1.00
Pruc Prucsion
Dansity
Racall
Couarage
F1 PM
F1 bc
rD
KD
KND Linea
Precsion
Dendity
Covarage
F1 Pa
FD
KD
KMD Limear
Degres MMO
Oreits MND
MAD
MMO
weights
Pretrained weights
Baseline (GNN-agnostic) metrics
6lsy.51 Sx)
0.4
0.2
0.0
Degree perturbation
Degree perturbation
Degree perturbation
Contrigg
Orata HPD
Dog
Figure 4: Results from the mixing random graphs experiment across all datasets and all GIN configurations (if applicable).
C ADDITIONAL RESULTS
Here we provide a variety of supplementary experiments that were not included the main body due page limits. Unless otherwise specified, results for all GIN-based metrics utilize random GIN, are aggregated across all GIN configurations, and all GIN configurations use summation ag- gregation.
C.I INDIVIDUAL EXPERIMENTS
We provide violin plots for each individual experiment in Figures through
C.2 ALL. EXPERIMENTS GROUPED BY GIN CONFIGURATION
We aggregate results by GIN configuration across all experiments in Tables 4 In addition, aggregate results by GIN configuration and metric combination and highlight the top 20 results in Table
C.3 ALL RESULTS GROUPED BY DATASET
For more in-depth comparison of metrics, here we provide results for all experiments grouped by the dataset used. The results are shown in Tables 6 and 7 We find that while the performance of each metric does fluctuate slightly across datasets, of our conclusions drawn Section 5 hold regardless of dataset and there are no obvious outliers. F1 PR and MMD RBF are consistently the highest scoring metrics, and with the exception the Community dataset all baseline metrics (You al. 2018) are poor at measuring the diversity of generated graphs. Notably, the performance of Clustering MMD on diversity experiments affected by the Lobster and Grid datasets; these graphs triangle-free and thus all nodes have clustering coefficient of zero. However, datasets are excluded from the analysis, Clustering MMD is still suboptimal on the remainder the datasets.
if these
16

---

Published as a conference paper at ICLR 2022
Random weights
Pretrained w weights
Base line metrics
1.00
correiation
0.50
0.25
-0.25
-0.50
1.00
Prodsiin
Danelyy
Recal
Coveragee
FI P9
F1 DC
KD
MND Linear
Predsion
Cove Coverage rae
FI nR
FD
KD
Degree MMD
MMO
NSPDK MMD
KMN
MMD
Random weights
Pretrained weights
Baseline (GNN-agnostic metrics
1.0
0.6
0.4
0.2
0.0
Degree perturbation
Degree perturbation
Degree perturbation
Coverage
Figure 5: Results from the rewiring edges experiment across all datasets and all GIN configurations (if applicable).
Random weights
Pretrained w weights
Baseline matrics
1.00
0.50
0.25
-0.25
-0.50
1.000
Pradsion
Danstt
Covarage
FI PM
F1 bc
KD
MID Linear
Precssio
Denstyy
Rocall
Covarage
F1 PR
FD
KD
Degree WMD
MMD
MND
MMD
Random weights
Pretrained weights
Baseline (GNN-agnostic metrics
1.0
865 Sal
0.6
0.4
0.2
0.0
1.0
Degree perturbation
Degree perturbation
Degree perturbation
Pecsion
Custering
Figure 6: Results from the mode collapse experiment across all datasets and all GIN configurations (if applicable).
17

---

Published as a conference paper at ICLR 2022
Random
Pretrained wights
1.00
0.75
corelatio
0.50
0.25
0.00
-0.75
1.00
Prediion
Danelly
Caverage
F1 Po
F1 Dc
MMD Linear
MHD RBe
Preciion
Danaity
Coverage ragrage
F1 Po
F10C
FD
KD
MHO
Degres MMD
orons MMD
NETOX (MO
MND
Random weights
Pretrained weights
Baseline (GNN-agnostic) metrics
1.0
0.8
815g S..
0.6
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Degree of perturbation
Degree of perturbation
Degree of perturbation
MND R57
Recal D0
73 P3 Piccson
Coverage
Gra NND Dog ce MND
VERRK YAN
201e by
Custering PND
Figure 7: Results from the mode dropping experiment across all datasets and all GIN configurations (if applicable).
weights
Pretrained weights
Baseline metrics
Recall
Coverage
F1 DC
TD
NMD RBF
Predzion
Denstyy
Recab
Daverage
KD
KNN RBF
Clusteinng AND
Dreits MNO
SS90K-00 MONO MND
MNI
Degree
Figure 8: Results from the sample efficiency experiment across datasets and all GIN configura- tions (if applicable).
18

---

Published as a conference paper at ICLR 2022
Table 4: Results across fidelity, diversity, and sample efficiency experiments and all datasets grouped by GIN configuration. N is the node embedding size, P the number of graph propagation rounds, and G the dimensionality of the obtained graph embedding. Configurations are sorted by their mean rank correlation across fidelity and diversity experiments.
(a) Pretrained GIN
GIN CONFIG.
FIDELITY
DIVERSITY
FIDELITY & DIVERSITY SAMPLE EFF.
N: 25, P: 3, G: 50
0.90 0.007
0.59 + 0.019
0.05
17 = 2
140
0.89
0.008
0.59 #
0.01
19
35, P. G:
0.91
0.007
0.56 0.020
0.01
19 1
N: 30, P. G: G:
0.90 = 0.008
0.019
0.73
20 +
N: P: 200
0.89 = 0.008
+
0.73
20 +
40 P: G:
0.90 0.007
0.56 0.020
0.03
22 =
P. 160
0.009
0.59 0.019
0.70
21
N: 20, 80
0.90 = 0.008
0.56 + 0.020
0.00
19
N: 15, P: 7:
0.89 + 0.008
0.56 + 0.020
0.03
20
N: 15, P: 1:
0.89 0.008
0.56 0.019
0.03
23
7, 120
0.90 0.007
0.55 0.020
0.001
+
20, P: 40
0.007
0.54 0.020
0.00I
18
N: 10, 7:
0.89 1 0.009
0.56 1 0.020
0.001
22 1
N: P. G:
0.90 1 0.00S
0.54 1 0.020
0.012
18 18:2
N: 10, P: G:
0.89 0.008
0.55 0.020
0.001
16 =
90
0.88 0.009
0.55 0.020
0.0LI
20 =
N: 25, P: 4, 7:
0.88 = 0.009
0.002
0.011
21 =
N: 5, P: 7, G: 30
0.89 0.008
0.54 0.020
22 +
N: 10, P: 2, G: 10
0.86 = 0.010
0.56 + 0.020
0.71
26 +
5, P: 2, 5:
0.86 0.009
0.51 0.019
0.69 0.011
24 +
Average
0.89 + 0.003
0.56 + 0.004
0.73 + 0.003
20 +
1
(b) Random GIN.
GIN CONFIG.
FIDELITY
DIVERSITY
FIDELITY & DIVERSITY SAMPLE EFF.
N: 35, P: 3, G: 70
0.92 0.008
0.55 f 0.019
0.03
31 +
10, P: 2:
0.92 0.008
0.55
0.019
0.001
34
25, 3, 50
0.92 = 0.008
0.51
0.73
31 3
P. 140
0.91 = 0.008
0.019
0.73
18 1842
25, P: 7:
0.91 = 0.009
0.019
0.73
26 +
20, G:
0.91 0.00S
0.020
0.021
34 3414
40, P.
0.90 0.008
0.54 0.019
0.001
20 2012
N: 30, P, 120
0.90 + 0.009
0.54 0.019
0.02
22 2
N: 15, P. G:
0.90 = 0.008
0.54 0.019
0.011
26 26
N: 40, P: 6, 200
0.90 0.008
0.53 0.020
0.001
20
P, G:
0.90
0.54 0.020
0.72
30
15, G:
0.89 0.009
0.54 0.019
0.02
26 3
N: 20, P, G: 120
0.90 + 0.007
0.53 + 0.020
0.72
22 2
N: 10, P: G: 60
0.90 + 0.008
+
0.01
25 3
P,
0.90 0.009
0.53 0.020
0.71
25 25
P. 20
0.87 0.011
0.55 0.019
0.71
36 1614
40, P: 2, G:
0.80 - 0.011
0.55
0.001
32 13
N: 15, P: G:
0.78 - 0.012
0.56
0.67
46 +
N: 10, P: 2, G: 10
0.75 - 0.014
0.02
0.013
29 +
N: P: G:
0.74 0.012
0.50 + 0.019
0.62 0.012
44 +
Average
0.88 0.013
0.54 0.003
0.71 + 0.007
29 +
19

---

Published as a conference paper at ICLR 2022
Table 5: Results across fidelity, diversity, and sample efficiency experiments and all datasets grouped by GIN configuration and metric used. N is the node embedding size, P is the number of graph propagation rounds, and G is the dimensionality of the obtained graph embedding. Configurations are sorted by their mean rank correlation across fidelity and diversity experiments and the top 20 results are shown.
(a) Pretrained GIN.
GIN CONFIG., METRIC
FIDELITY
DIVERSITY
FIDELITY & DIVERSITY SAMPLE EFF.
N: 35, P: G: 70, MMD RBF
0.99 1 0.005
0.97 1 0.005
0.98 1 0.004
9
N: P: 4, G: 75, MMD RBF
0.98 0.005
0.97 = 0.007
0.98 = 0.004
10 2
N: 20, P. G: 40, MMD RBF
0.99
0.97 = 0.013
0.98 = 0.007
9
N: P: G: 120, MMD RBF
0.000
= 0.007
0.97 = 0.005
11
N: 20, 5, G: 80, MMD RBF
0.98 0.007
0.97 + 0.010
0.97 + 0.006
9
N: 40, 2, G: 40, MMD RBF
0.99 + 0.004
0.96 + 0.014
0.97 + 0.007
12 2
N: 10, P: 7, G: 60, MMD RBF
0.98 + 0.004
0.96 + 0.014
0.97 + 0.007
12
N: 10, P: G: 10, MMD RBF
0.99 + 0.004
0.96 = 0.014
0.97 = 0.007
19
10, P: 3. G: 20, MMD RBF
0.98 1 0.006
= 0.013
+ 0.007
11
N: 25, P: 3, G: 50, MMD RBF
0.98 1 0.008
0.96 1 0.013
0.97 + 0.007
1
N: 15, P: 7, G: 90, MMD RBF
0.98 + 0.006
0.96 = 0.013
0.97 = 0.007
9
N: 20, P: 7, G: 120, MMD RBF
0.98 + 0.006
0.96 = 0.014
0.97 = 0.008
10 1
N: 40, P: 6, G: 200, MMD RBF
0.98 0.010
0.97 = 0.010
0.97 = 0.007
9
5.
20, MMD RBF
0.98 1. 0.011
0.97 1 0.012
0.97 1 0.008
11
N: 15, P: 6, G: 75, MMD RBF
0.98 1: 0.010
0.96 1 0.014
0.97 1 0.009
9
N: P. G: 30, MMD RBF
0.98 0.011
0.96 0.013
0.97 0.008
14
N: 15, P: 2, G: 15, MMD RBF
0.98
0.96 0.014
0.97 = 0.008
17
N: 35,
P: P: 5, G: 140, MMD RBF
0.96 0.015
= 0.008
= 0.008
9
N: 40, P: 5. G: 160, MMD RBF
0.97 0.010
0.96 = 0.011
0.96 = 0.007
9
N: 15, P: 2, G: 15, F1 PR
0.94 + 0.011
0.95 + 0.010
0.95 + 0.007
7 0
(b) Random GIN.
GIN CONFIG., METRIC
FIDELITY
DIVERSITY
FIDELITY & DIVERSITY SAMPLE EFF.
N: 10, P: 7, G: 60, MMD RBF
0.99 109900.0 0.002
0.95 = 0.013
0.97 = 0.007
25 + 6
N: P: 4, G: 75, MMD RBF
0.99 0.002
0.95 = 0.013
0.97 1 0.007
30 7
N: 25, P: 3, G: 50, MMD RBF
0.99 0.002
0.95 + 0.014
0.97 + 0.007
51 -
N: 20, 5, G: 80, MMD RBF
0.005
0.95 + 0.014
0.97 + 0.007
31 7
N: 3. 20, MMD RBF
0.900
0.95 = 0.014
0.97 + 0.007
56 = 11
N: 35, P. G: 70, MMD RBF
0.0003
0.95 1 0.014
0.97 1 0.007
52 1 10
N: 20, 3. G: 40, MMD RBF
0.99 0.005
0.95 1 0.014
0.97 1 0.007
52 1 11
5. P: G: 20, MMD RBF
0.99 1 0.006
1 0.013
0.97 1 0.007
41
N: 5, P: G: 30, MMD RBF
0.99 +.990
0.95 = 0.013
0.97 = 0.008
25 7
N: 30, P: G: 120, MMD RBF
0.99 + 0.008
0.95 = 0.014
0.97 = 0.008
29 6
N: 15, P: 7, G: 90, MMD RBF
0.98 + 0.008
0.96 = 0.013
0.97 = 0.008
20 4
N: 15, P: 6, G: 75, MMD RBF
0.98 + 0.008
0.96 + 0.013
0.97 + 0.008
21 2144
N: 20, P: 7, G: 120, MMD RBF
0.98 + 0.007
0.96 + 0.013
0.97 + 0.008
23
N: 35, P: 5, G: 140, MMD RBF
0.98 + 0.008
0.95 + 0.013
0.97 + 0.008
17 3
N: 40, P: 6, G: 200, MMD RBF
0.97 + 0.009
0.95 + 0.013
0.96 + 0.008
17+4 4
N: 40, P: G: 160, MMD RBF
0.97 0.010
0.95 : 0.014
0.96 = 0.008
20 0004 4
N: 35, P: 3. G: FI PR
0.98 0.005
0.94 0.011
1 0.006
7
N: 20, P: 3, G: 40, FI PR
0.98 0.005
0.94 0.010
0.96 1 0.006
7 0
N: 10, P: 3, G: 20, FI PR
0.99 0.002
0.93 = 0.011
0.96 = 0.006
7 0
N: 25, P: 4, G: 75, Coverage
0.95 + 0.005
0.96 = 0.012
0.96 = 0.007
7
20

---

Published as a conference paper at ICLR 2022
Table 6: The performance of each evaluation metric across all experiments grouped by the dataset used. Part A.
(a) Ego dataset.
METRIC
FIDMLTY
DIVERSITY
FIDELITY & DIVERSITY (RANDOMPRETRRANED)
SAMPLE EFE. (RANDOM/PHETRRIINE))
Orbits MMD
0:200 0.053
0:250 + 0.029
0,220 0.030
319. 000 + 21.000
Degree MMD
1.000
0.000
0.760 + 00.883
0,880 0.045
7,000 0.000
Clustering MMD
1.000
0.000
0.550
0.120
0.770 0.0G9
0.UD0
1.000 0.000
1.000
0.001
1,000
0.001
7:000 0.000
0.028
0.740 1: 0.016
0.910
11.000
1.000
0,990 0. 001
0.310
0.033
0.650 1 0.020
0.820 1 0.013
18.000
1.000
14.000
2.000
Precision
0,380 2: 0.009
0. 480
1 0.029
0.200 1: 0.029
0.250
0.030
7.000 :: 0,000
7.000
= 0.000
Recall
0,860 0.009
0.970
0.004
0.910 1: 0,005
0.960
0.002
7,000 1 0,000
7,000 : 0.000
Densiy
0.320 0.024
0.360
0.027
7,000
7,000
Coverage
0,910 0.005
0.990 0.004
0.950 1: 0.003
0.990
0.001
7,000 :: 0.000
7,000
0.000
FI PR
0,900 :: 0.007
0.970 1: 0.004
0.930 1: 0.004
0.960 1 0.001
7,000 : 0.000
7,000 = 0.000
FI DC
0.880 0. 007
0.950
0.005
0.920 1 0.004
0.970
0.003
7:000 1 0.000
7.000
0.000
Linear
0.990
0.026
0.700
0.017
0.860
0.010
2.000
8.000
1.000
MMD RBF
0,960
006
0.970
0.004
0.970
1 0.004
0. .8.900
002
14. 000
1. 1.000
7,000
0.000
Averae
0.920 0.019
0.540 + 0.168
0.730 + 0.986 0.810 U.086
10.300 1.484
8.300 0.803
(b) Grid datasct.
FIBLITY & DIVERSITY (RANDOMPAIITAAINU))
SAMPLE IIT: (RANDOM/PECTRANNEE)
METRIC
FIDELITY
DIVERSITY
Osbis MMD
0.200
1: 0.156
0.440 1 0.133
0.350 = 0.108
9. 0.000 1: 2,000
Degres MMD
1.000
0.000
0.290 1: 0..177
0.680 0.098
2.000 0,000
Clustering
0,000
7,000
NPSDK MMD
0.990
0.004
0.270 + 0.136
0,630 0.088
7,000 0,000
1.000 0.000
0.070 + 0.034
0.540
+ 0.023
0.550
0.023
9.000 + 0. 01.00
7,000
0.000
KD
0.970 + 0.007
0.230 + 0.0:33
0.600
+ 0.021
0.620 + 0.019
9.000
: 0. D00
7,000 = 0.000
Precision
0.960 0.003
0.000 + 0.000
0.480
+ 0.017
0.370 2 0.015
7.000
: 0.000
7,000
0. 0.000
Rocall
0.500
0.016
0.004
0.720 0.011
Density
0.960
0.004
0.180 + 0.033
0.570
+ 0.022
0.450
0.021
7.000
0.000
7,000
0.000
Coverage
0.840 + 0.012
0.930 1 0.006
0.890
+ 0.007
0.810 2 0.008
7.000
: 060
7.000
0.000
Fl PR
0.960
0.003
0.940 + 0.004
0.950
+ 0.003
0.840
0.008
7.000 2 0.060
7.000
0.000
0.950
0.00G
0.014
0.780
0.000
MMD incar
1.000
0.000
0.030 + 0.029
0.510
+ 0.023
0.520
0.022
9.000
0.000
7.000
MMD REF
0.950
+ 0.007
0.970
+ 0.004
0.960
+ 0.004
0.960
0.004
9.000
1.000
7,000
0.000
Average
0.910 1 0.048
0.510
138
0. 0.710 0.061
0.660 1 0. 00.060
7,800 1: 0 0.327
7.000 0.000
(c) Lobster dataset.
METRIC
FIDELITY
DIVERSITY
PIDELITY & DIVERSITY (RANDOM/PETRAINEE)
SAMPLE EIF. (RANDOM/PRETRAINEE)
Orbiis MMD
0.450 1: 0.037
0.150 =: 0.079
0.300 1 0.049
22 10.000 1: 5.000 7.000
Degros MMD
1,000
0.001
0.270
0.090
Clustering MMD
0.950 - 0.013
0.000
0.000
0.450 + 0.076
7,000 0.000
NPSDK MMD
1.000 1 0.000
0.920 : 0.028
0.960 1 0.015
7.000 : 0.000
ED
0.990 + 0.001
0.360
0.026
0.680
0.017
0.740 =: 0.015
11.000
1.000
7.000 =: 0.000
KD
0.9:40 1 0.007
0.240 1: 0.023
0.590
2: 0.017
0.820
0.018
12.000
: 1.000
9.000
:: 1.000
Precision
0.970 0.003
0.010
0.006
0.480
0.021
7.000
0.000
7,000
0.000
0.570 0.016
0.820
0.011
0.700
0.011
0.590
0.015
7.000
0.900
7,000
0.000
Density
0.980 1: 0.002
-0.180
0.031
0.400
0.022
0.100
0.025
7.000
0.000
7.000
0.000
Coverage
0.900
+ 0.00G
0.860
0.D13
0.880
0.007
0.880
0.007
7.000 + 0.300
7.000
0.000
FL
0.970
0.003
0.820
0.011
0.900
0.006
0.007
7.000
0.000
7.000
0.000
0.980
0.002
0.610
0.028
0.790
0.015
0.740
0.016
7.000
0.000
7.000
0.000
MMD Linzar
0.980
+ 0.002
0.260 0.025
0.620
0.018
D.590
0.016
14.000
1.000
8.000
0.0D0
MMD RBF
0.980
0.002
0.870
0.014
0.930
0.007
0.930
0.006
12,000
1.000
8,000
0.000
Average
0.930
: 0.040
0.460 1: 0.122
0,700 1: 0.057
0.890 :: 0.057
9.100 1 0.888
7.400 :: 0.221
21

---

Published as a conference paper at ICLR 2022
Table 7: The performance of each evaluation metric across all experiments grouped by the dataset used. Part B.
(a) Community datasct.
FImELITY DIVERSITY REANDOM//SUTRAINT
SAMPLE EL FRT:
METRIC
PIDELITY
DIVERSITY
(RANDOM/ (UNNDOAPPLUTRAINEL))
Orhics MMD
0.760
0.065
1,000 0. 0.000
0.880 + 0.038
0.0000 31.000
Degree MMD
1,000 1: 0.000
0.960
0.011
0.980 + 0.006
18,000 =: 7,000
Clustering MMD
1.000
0.000
0.810 0.061
0,900 1 0.034
7,000 0.000
NSPDK
0.004
11.545 3.049
0.930
0.440
0,680
0.600 + 0.018
115.000
6.000
000.000--50
6.000
0.380
0,033
0.300
0.033
0.040
0.025
0.130 + 0.021
180.000
6.000
202.000 + 5.000
Precision
0.344 0.919
0.350
0.022
-0.030
0,019
0.120 + 0.022
7.000 + 0,000
7,000
0.000
Recall
0.790 + 0.018
0.980 0.004
0.890 + 0.010
0.960 + 0.003
7,600 + 0.000
7.000 0.000
Dausiry
0.770 0.013
0.350
0.022
0.027
7,000 0.000
0.000
Coverage
0.920 0.007
0.990
0000
0.950 + 0.004
0.980 + 0.002
7.000 - 0.000
7.000 0.000
F1 PR
0.800 + 0.018
0.980 = 0.004
0.890 :: 0.009
0.980 + 0.002
7,000 + 0.000
7.000 = 0.000
F1 DC
0.960 + 0.00G
0.950
0.005
0,950 # 0.004
0. 01.9004 + 0.004
7,000 + 0.000
7,000 0.000
110.000
0.990
0.004
0.970
0.004
0.080
0.003
0.580 + 0.003
91.000 + 6.000
30.000 - 3.000
Average
0.710 0.135
0.530 1 0.170
1: 0.9
0.670 1 0.117 03.0000-5
57 20.142
105
(b) Proteins dataset.
METRIC
FIDELITY
DIVERSITY
PIDELITY & DIVERSITY (RANDOM/PSETRAINED)
SAMPLE EIV. (RANDOM/PRETRAINNE))
Orhits MMD
0:220
= 0.126
0.630 + 0.072
0,420 0.079
177.000 + 67.000
Degree MMD
1.000
00.000
0.290 4 0.9
0.640 0.089
7,000 0.000
Clastering MMD
0.046
0.000
NSPDK MMD
1.000
0. 0000
0. 0.001
0.999
0.00 00.00
7:000 0.000
0,990
0.003
0.011
0.920
0:006
0.900
0.010
13 13.000
60.900
9.000
KD
0.550
0.033
0.550
1 0.025
0.550
1 0.021
0.710
0.018
236.000
:: 15.000
63. 10.0000-0
1: 11.000
Precision
0.970
0.000
430
+ 0.029
0.270
0.029
0.255
+ 0.029
7,000
0.000
7,000
0.000
Recall
0.790
0.013
0.0U5
0.870
0.008
0.890
0.005
7,000
7,000
0.000
Density
0.990
0.000
0.020
0,031
0.500
0.024
0.370
0.027
7,000
7,000
Coverage
0.970 = 0.004
0.990
+ 0,004
0.980
+ 0.305
0.990
0.000
7,000 + 0.030
7,000 +: 0.000
F1 PR
0.980
0.005
0.930
4 0.006
0.950
0.004
0.960
0.003
7,000
0.000
7.000 0.000
FI DC
0.990
0. 2.002
0,980
0.005
0.970
0.003
0.970
0.002
7,000
0.000
7,000
0.000
MMD
0.990
D02
0.780
0.017
0.880
0.009
0.940
0.00G
145. 000
12.000
21.
4.000
MMD RBF
0.990
0. 002
0,950
0.004
0.970
0.002
0.990
0.001
86, 000
8.000
8,000
00000
Averge
0.920 - 0.046
0.680 + 0.153
0.790
0.080
0.800
0.086
65.900 26. 559
21.400 5.634
(c) Zine dataset. Note that the metries from You et al. 2018 are excluded here as they cannot incorporate node and edge features in evaluation.
METRI:
FIDELIUY
DIVIRSEIY
FIRELITY & DIVERSITY
NOBD/EDDGE FEATS.
SAMPLE HIY:
NESDK MMD
1,000
0.000
1.000 + 0.000
1.000 + 0.300
1.000
0.000
7 7
RD
0.950 = 0.006
0.680 + 0.031
0.820 4: 0.017
0.360 = 0.010
35.000 + 7.000
KD
0.910 0.010
0.540 + 0.035
0.730 + 0.020
0.940 0.011
39.000
+ 7.900
Procision
0.035
00.044
7.000
0.000
0.940 0.005
0.980
0.002
0.960
0..03
0.800
0.018
7,000
0.000
Dausity
1.000 + 0.001
0.450
+ 0.035
0.270
+: 0.033
0.990
2 0.001
7,000 + 0.000
Coverage
0.990 0.000
1.000
0.000
0.980 2 0.000
0.390
0.000
7,000 + 0.000
0.900
0.006
7.000 0.000
FI DC
1.000 0. 0.000
0.850
0.011
0.920
0.006
0.990 0. 0.000
7,000 1 0.000
MMD Linear
0.900 2 0.002
0.810 + 0.018
0.900 4: 0.010
0.990 2 0.005
16.000 1 3.000
MMD RBF
1.000
0.001
1,000 # 0.000
1.000 4 0.000
1,000
0.001
9.600 1.000
Averae
0.980 + 0.010
U.D90 + 0.177
0.780 4 D.088
0.960 0.019
14.100 + 3.928
22

---

Published as a conference paper at ICLR 2022
Randomize edges
Random ice nodes
1.0
1.
Rankk corrutation
0.0
0.0
Prudsion
Danskk
Rccal
F1
F1 F1DC
FD
HMO Unbor
MNO RDF
NSROK MOND
medson
Covenge
F1
F10C
KD
HNO Unca
MNO
1.2
1.0
0.0
0.4
Degree of perturbation
Degree of perturbal lon
M40
Seca
FLM
MMG Derty
Prealee
Figure 9: Results from the randomizing edge features (left) and randomizing node features (right) experiments on the ZINC dataset.
Table 8: Comparing the performance of metrics on the mixing experiment when the mixed graphs are random E-R graphs or graphs generated by GRAN (Liao et al. 2019).
METRIC
MIXING RANDOM
MIXING GENERATED
Orbits MMD
0.680 0.047
0.010 0.035
Degree MMD
1.000 + 0.000
1.000 + 0.001
Clustering MMD
1.000 0.000
0.980 = 0.005
NPSDK MMD
1.000 + 0.000
1.000 = 0.000
FD
0.970 0.003
0.980 0.003
KD
0.730 + 0.016
0.780 + 0.018
Precision
0.920 0.007
0.970 0.005
Recall
0.640 + 0.011
0.490 + 0.012
Density
1.000 0.001
0.990 0.002
Coverage
0.920 + 0.004
0.900 + 0.005
PR
0.960 0.006
0.970 0.005
FI DC
1.000 + 0.001
0,990 + 0.002
MMD Linear
0.970 0.003
0.960 = 0.004
MMD RBF
1.000 + 0.001
0.990 + 0.002
Average
0.910 + 0.039
0.900 + 0.050
C.4 MIXING GENERATED GRAPHS
As opposed to the E-R graphs used in Section 4.1 here we perform the mixing experiment using graphs generated by GRAN (Liao et al., 2019) for each dataset. As these graphs better rep- resentation of the dataset of interest, this represents a much harder problem. However, as seen in metrics fairly consistent regardless of the type of graph used.
Table 8 the results
C.5 COMPUTATIONAL EFFICIENCY
In Figure 12 we plot each metric's RAM usage throughout the computational efficiency experiments in Section 4.5 by tracking the memory usage of the main Python process. While this is likely imper- fect and slightly noisy, provides idea of the memory requirements of each metric. Unfortunately all classifier- based metrics are grouped into the same experiment and more in-depth breakdowns are unavailable for this experiment. However, it is likely that the bulk of the memory requirements spe-
23

---

Published as a conference paper at ICLR 2022
Wall-llock time
increasing samples
Vall clock time increasing edges per graph
Wall--loos clock time increasing nodes per graph
10"
10t4
1014
17
220
1044
1.04
1024
1040
1046
10F4
1054
10"0
2000
4000
6000
8000
10000
0.0
0.2
0.4
0.6
0.8
1.0
20000 40000 60000 80000 100000
Number samples
Avg. number of edges per graph l66
Avg. number of nodes per graph
Activations
F1 PR
HMD Linear
Orbits MMD
Degres
KD
MND RDF Chustering MMD
Figure 10: The wall-clock time of each metric as datasets scale in a single dimension. Activations the time extract graph embeddings from GIN on CPU.
increesing samples
increasing edges graph
increasing per graph
10"
1650
10t*
101-
102.0
101.
100
10t
10t
1028
1000
10-15
10.22
10-10
10
10000
20000 40000 600ce 80000 100000 number of nodes
Number samples
Avg. number edges graph leb
Activations
F1
MMD Linear
Orbits MKD
Degren
MKD RBF
Clustering MMD
Figure 11: The wall-clock time of cach metric as datasets scale in a single dimension. Activations the time to extract graph embeddings from GIN on GPU.
usage
increasing num. samples
usage
increasing edges per graph
usage increasing nodes per graph
25
12
10
usage
15
0.0
0.6
Percent complete
Percent complete Clustering
complete
Activations
Orbits
MMD
Figure 12: The estimated memory usage of each metric the dataset scales in single dimension. Activations is the memory required for all classifier- based metrics combined.
cific to these metrics come from storing the GIN parameters and extracted graph embeddings. The maximum recorded value for each metric in each experiment is recorded in Table
C.6 COMPARING OTHER GNNS
In the main article, all experiments performed using GIN with summation neighborhood ag- gregation and concatenating graph embeddings at each round of graph propagation into a final graph embedding (Equation 4). Here we also provide results for random GINs with mean and max
24

---

Published as a conference paper at ICLR 2022
Table The maximum recorded memory usage in GB of each metric during each of the computa- tional efficiency experiments.
SCALING EXPERIMENT
METRIC
Num, samples
Nodes
Edges
Degree MMD
1.20
7.20
21.88
Clustering MMD
1.26
7.20
21.85
Orbits MMD
1.19
7.20
21.80
Classifier metrics
4.01
4.08
10.40
Table 10: Comparing various GNN architectures on our experiments using all datasets. We present only the final two recommended metrics to keep this presentation concise. All models are randomly initialized and aggregated across the same underlying model architectures (number of propagation rounds, node embedding size) used in the main article.
METRIC
FIDELITY
DIVERSITY
FIDELITY & DIVERSITY
NODE/EDGE FEATS.
SAMPLE EFF.
(GrighSAAE))
0.900
FI PR (GCN)
0.870
0.005
0.310
0.005
0,890 = 0.003
0.990 4 0.000
7 7
F1 PR (GHN, no concar.)
0.790 0.007
0.920
0.004
0.8G0 0.004
0.980
0.004
7 D
PK (GIN)
0.920
0.003
0.990
D
MMD RDF GraphSAGE)
0.950
0.003
0.950
0.003
0.950
0.002
1.000
0.001
23 2:2
0.950
55
MMD (GIN, no comeat))
0.960
0.003
0.940
003
0.850
0.900 005
60 1:
MMD RDF (GIN)
0.970
0.002
0.950
0.003
0.960 0.002
1,000 0.001
42 1.
neighborhood aggregation. With minor architecture differences, the former is equivalent random GCN (Kipf & Welling, while the latter is equivalent to random GraphSAGE (Hamilton et al., 2018). In addition, we also provide a comparison to random GIN with summation neighborhood aggregation that does not use the concatenation in Equation 4 i.e. the resultant graph embedding is simply the embedding obtained graph propagation round T.. We find that while GIN is superior across the presented metrics, it is in many cases only by very narrow margin (Table I0). The performance of MMD RBF appears to be relatively constant across GNNs, while the performance of F1 PR has higher variance.
C.7 COMPARING a SELECTION STRATEGIES
In order to provide a fairer comparison to pre-existing metrics based on the RBF kernel You et al, 2018), here we include results for MMD RBF with static a using random GIN. The results are shown in Table 11 While this metric does result in a decrease in performance while measuring diversity, it is still more expressive than baseline metries. Note that could also utilize our selection process with pre-existing metrics. However, we did not experiment with this as these metrics would still suffer from computational efficiency issues and be unable to incorporate node and edge features.
Table 11: Mcasuring the impact of our selection process the MMD RBF metric. While using static a does result in a decrease in performance, it is still more expressive than pre-existing metrics that rely the RBF kernel You al. 2018).
MUTRIC
PIBLITTY
DIVERSITY
FIBELITY DiVIRSITY
Nomn/EDGat FEATS.
SAMPLD
0.430
122
Degree MMD
1.000 4 0.000
0.510
0.061
0.760
0.035
NIA
9
Clussering MMD
0.990 1 0.003
0.430 1 0.047
0.720 1 0.030
N/A
710 0
MMD RBF (o
0.970 4: 0.002
0.850 # 0.007
0.910 = 0.004
D. 8,890 E 0.009
33 2
MMD RRF
0.970 + 0.002
0.950 0.003
0.960
0.002
1.000 # 0.001
42 2
25

---

Published as a conference paper at ICLR 2022
C.8 GGM SELECTION
Here we evaluate GGMs at various stages of training on Grid, Lobster and Proteins datasets using classical metries (You et al. 2018), NN-based metrics using random GIN, and NN-based metrics using a pretrained GIN. The results are shown in Table T2
26

---

Published as a conference paper at ICLR 2022
Table 12: Evaluation of different GGMs various percentages of total epochs trained on the Grid, Lobster, and Proteins datasets. Models are evaluated using three of the strongest NN-based metrics and classical metries (You et al. 2018). All NN-based metrics are averaged across different GINs with the strongest configuration. Cells are colored according to their rank in a given column. 50/50 split represents the metric computed using a random 50/50 split of the dataset and represents the theoretical ideal score for each metric.
(a) Random GIN, Grid dataset.
MMD RBF
PR
FI DC
Clus.
Deg.
Orbii
50/50 split
0.042
0.998
0.995
0.0
6.51e
0.016
0.203 + 0.006
0.669 + 0.041
0.89 0.026
0.023
1.001
0.56
GripRRNN- 100%
0.184 1:
0.919 1e
0.896 1: 0000
4.59e -6
0.032
0,252
GraphRNN 66%
0.154 7e
0.912 0.007
0.942 4:
1.09c
0.015
0.169
GraghRNN-SSK
0.248 + Ge
0.953 + 1c 16
0.878 + 0.003
1.81c
0.022
0.134
AN- 100%
0.001
0.0
1.24
0.037
GRAN- 66%
0. 0.061 + 0.001
1.0 1::=00 0.0
1.065 :: 0.002
3.15e
3.20e
0.047
33
(b) Pretrained GIN, Grid dataset.
MMD REP
FI PK
P1 DC
Ciss.
Deg.
Orlit
50/30 split
0.05
0.997
0.969
0.0
6.51e
0.018
Erdös Rényi
1.278 0.05
0.0 1 0.0
0.0
0.023
1.001
0.58
GrapERNN- 100%
0.21 + 0.017
0.928 0.021
0.82 0.03
4.09e
0.032
0,252
GNN6
0.156
0.907
0.871
0.033
0.169
GmibRNNN199
0.6 0.009
0.951 0.015
0.848 +: 0.035
1.81e-b
0.022
0.134
100%
1.24e
GRAN 60%
0.066 0.009
0.963 0.032
0.994 à: 0.052
3.15e
3.20e
0.047
GRAN-33%
0.029
0.99
(c) Random GIN, Lobster dataset
MMD RBF
PR
DC
Clus.
Deg.
Orbet
50U50 split
0.049
0.989
0.037
Endás- Rányi
0.538 + 0.029
0.446 1 0.126
0.554 1: 0. 135
0.002
0.738
0.729
GrggkRKK 100%
0.235
0.
0.979 0.011
0.921 0.026
0.095
0.038
0.104
GruphRNN
0.244 0.006
0.008
GrighRNN-339
137 0.00
0.939 0.056
0.893
0.031
0.137
0.047
0.104
GRAN- 100%
0. 046 = 0.0009
0.932
2 0.041
0.905 1 0.022
0.101
0.048
0.098
GRAN 66%
0.161 0.011
0.956 0.007
0.942 0.022
0.103
0.045
0.094
33%
0.013
(d) Pretrained GIN, Lobster dataset
Deg.
split
0.043
Endäs Endäs-Rddyi Rényi
0.676
0.23
0.088 0.085
0.077
0.077
0.002
0.736
0.729
GraphiNNN 1001
0.193
0.026
0.7 + 0.058
0.658 4: 0.037
0.095
0.038
0.104
GrgghRNNN666%
0.222
0.039
0.06
0.104
GrugtiNNN
0.196
0.033
0.652
GRAN- 100%
0.1 = 0.02
0.698 0.04
0.661 2: 0.042
0.101
0.048
0.098
GRAN-G6S
0.186
0.025
0.68 0.051
0.602 0.032
0.103
0.045
0.094
GRAN-33%
0.194
0.035
0.053
0.099
(c) Random GIN, Proteins datasct.
DC
Clos.
Deg.
50U50 split
D.005
0.988
6.988
7.18c
8.64e
0.004
Endös Kčnyi
D.733
0.099
0.023 + 0.011
0.01 # 0.004
1.798
1.523
0.124
GRAN 100%
0.186
0.065
0.756
0.1
0.568 1: 0.114
0.28
0.512
0.099
GRAN-755
D.09
0.8G3
0.0s5
+
0.323
GRAN-S00 50%
0,226
0.071
0.66
0.109
0.474
+: 0.111
0.382
0.648
0.203
GRAN-2555
D.019
0.009
0.922 0.004
0.995 + 0.D45
0.291
0.077
0.028
(f) Pretrained GIN, Proteins dataset
MMD RHF
F1
FI DC
Clus.
Ochit
split
Eadis Stnyy
1.097
0.1022
4.34c 4 Dc
L.GSe
+ 3e
1.796
1.523
0.124
GRAN 100%
0.514
0.053
0.361
4: 0.141
0.306
+ 0.085
0.28
0.099
0.304
+ 0.074
+ 0.072
0.323
GRAN-50%
0.549
0.086
0.463
4: 0.13
0.228
+ 0.076
0.382
0.646
0.103
GRAN 25%
0.068
0.014
0.855
4: 0.022
0.83 a: 0.033
0.291
0.077
0.028
27

---

Published as a conference paper at ICLR 2022
Table 13: Evaluating GGMs various stages of training on the Proteins dataset using all 20 GIN
architectures tested in the main-body
(a) Using the MMD RBF metric. First archictectures.
50/50 split
0.004
0.005
0.005
0.005
0.005
0.005
0.005
0.004
0.005
0.005
GRAN-100%
0.593
0.238
0.127
0.365
0.122
0.161
0.303
0.427
0.161
0.447
GRAN-75%
0.334
0.126
0.066
0.073
0.063
0.071
0.203
0.245
0.19
0.195
GRAN-50%
0.62
0.152
0.172
GRAN-25%
0.068
0.037
0.013
0.034
0.012
0.026
0.042
0.054
0.042
0.044
(b) Using the MMD RBF metric. Part
10
11
14
17
50/50 split
0.005
0.005
0.005
0.005
0.005
0.005
0.005
0.005
0.004
0.005
GRAN-100%
0.474
0.131
0.307
0.358
GRAN- 75%
0.09
0.127
0.242
0.17
0.069
0.121
0.084
0.158
0.152
0.11
GRAN-50%
0.329
0.319
GRAN-255
0.019
0,031
0.053
0.037
0.013
0.033
0.026
0.033
0.04
0.028
(c) Using the F1 PR metric. Part
2
5
9
50/50 split
0.976
0.986
0.993
0.979
0.988
0.986
0.977
0.988
0.978
0.977
100%
0.313
0.714
0.539
GRAN-75%
0.564
0.814
0.841
0.74
0.774
0.862
0.699
0.714
0.691
0.749
GRAN-50%
0.254
0.637
0.719
0.577
0.329
0.737
0.459
0.571
0.48
0.585
GRAN-25'8
0.848
0.911
0.925
0.891
0.898
0.879
0.868
0.908
0.853
0.919
(d) Using the Fl PR metric. Part B.
10
11
13
14
17
19
50/50 split
0.988
0.991
0.978
0.98
0.992
0.975
0.986
0.983
0.978
0.986
GRAN-100%
0.756
0.859
0.545
0.695
0.762
0.793
0.846
0.407
0.671
0.802
GRAN-75%
0.833
0.922
0.654
0.772
0.819
0.836
0.913
0.614
0.767
0.894
GRAN-507
0.66
0.796
0.43
0.575
0.662
0.696
0.77
0.326
0.591
0.698
GRAN-25%
0.922
0.962
0.879
0.901
0.915
0.924
0.933
0.874
0.88
0.949
C.9 STABILITY OF GGM RANKINGS
Here, we investigate the stability of GGM rankings across GIN architectures. For the Grid, Lobster, and Proteins datasets, we again evaluate GGMs at various stages of training. We evaluate models using a random GIN with each of the 20 architectures we tested in the main-body using both MMD RBF and PR, and the results are shown Tables 13 through [5] We find that the rankings are extremely consistent across architectures for the Grid and Proteins datasets. However, this does not appear to be the case for the Lobster dataset. One potential explanation is that for the Lobster dataset, there is added difficulty from both small extremely sample sizes and poor generative models.
28

---

Using the MMD RBF metric. Part Published as a conference paper at ICLR 2022
Table 14: Evaluating GGMs various stages of training the Lobster dataset using all 20 GIN architectures tested in the main-body.
50/50 split
0.046
0.015
0.012
0.041
0.041
0.013
0.041
0.052
0.011
0.011
GraphRNN- -
0.219
0.188
0.232
0.12
0.252
0.251
0.241
0.275
0.222
0.232
GraphRNN 66%
0.18
0.201
0.253
0.235
0.225
0.265
0.236
0.266
0.241
0.249
GRAN- 100%
0.224
0.158
0.194
0.123
0.147
0.195
0.203
0.252
0.268
0.191
GRAN-66%
0.181
0.187
0.212
0.174
0.173
0.219
0.193
0.256
0.202
0.184
(b) Using the MMD RBF metric. Part
50/50 split
0.049
0.041
0.043
0.044
0.042
0.043
0.041
0.047
0.052
0.05
GraphRNN. 100%
0.235
0.241
0.221
0.245
0.254
0.122
0.22
0.224
0.216
0.245
GraphRNN-66%
0.244
0.308
0.191
0.244
0.247
0.209
0.197
0.254
0.26
0.236
GRAN-100%
GRAN 66%
0.161
0.246
0.203
0.215
0.206
0.174
0.189
0.192
0.207
0.186
(c) Using the Fl PR metric. Part
50/50 split
0.983
0.997
0.996
0.978
0.994
0.993
0.988
0.985
0.977
0.995
GraphRNN: 100%
0.675
0.806
0.822
0.579
0.974
0.802
0.495
0.583
0.643
0.715
GraphRNN-66 66%
0.607
0.834
0.9
0.624
0.99
0.799
0.596
0.74
0.545
0.792
100%
GRAN-66%
0.672
0.805
0.89
0.615
0.969
0.818
0.669
0.679
0.675
0.76
(d) Using the metric, Part
11
17
50/50 split
0.989
0.993
0.901
0.99
0.996
0.992
0.993
0.983
0.956
0.99
GraphRNN-1O8
0.721
0.638
0.532
0.751
0.69
0.813
0.708
0.768
GraphRNN-6G -666
0.983
0.697
0.749
0.619
0.9
0.695
0.691
0.864
0.62
0.772
GRAN-100%
0.932
0.719
0.615
0.925
0.682
0.067
0.788
0.703
0.719
GRAN-66%
0.956
0.705
0.679
0.633
0.895
0.717
0.679
0.879
0.749
0.774
29

---

Using the MMD RBF metric. Part Published as a conference paper at ICLR 2022
Table 15: Evaluating GGMs at various stages of training the Grid dataset using all 20 GIN architectures tested in the main-body.
50/50 split
0.0413
0.05
0.051
0.0117
0.043
0.017
0.054
0.043
0.013
0.011
GraphRNN -
0.195
0,206
0.238
0.202
0.211
0.175
0.149
0.215
0.199
0.174
GraphRNN 66%
0.155
0.18
0.222
0.17
0.221
0.154
0.183
0.166
0.175
0.242
GRAN- 100%
0.065
0.063
0.061
0.064
0.06
0.055
0.064
0.057
0.062
0.063
GRAN-66%
0.06
0.06
0.059
0.06
0.059
0.053
0.061
0.055
0.059
0.06
(b) Using the MMD RBF metric. Part
50/50 split
0.042
0.052
0.047
0.041
0.039
0.045
0.047
0.046
0.054
0.047
GraphRNN. 100%
0.184
0.18
0.283
0.158
0.23
0.248
0.226
0.18
0.205
0.149
GraphRNN-66%
0.154
0.164
0.285
0.17
0.181
0.191
0.154
0.146
0.145
0.231
GRAN-100%
0.073
0.065
GRAN 66%5
0.061
0.06
0.058
0.057
0.059
0.075
0.06
0.059
0.06
0.06
(c) Using the Fl PR metric. Part
50/50 split
0.995
0.996
0.997
0.998
0.997
0.997
0.997
0.998
0.997
1.0
GraphRNN: 100%
0.955
0.964
0.969
0.947
0.958
0.958
0.919
0.95
0.95
0.935
GraphRNN 66%
0.953
0.915
0.934
0.969
0.964
0.955
0.913
0.93
0.964
0.969
100%
GRAN-66%
0.995
0.995
1.0
1.0
1.0
1.0
0.953
1.0
0.985
1.0
(d) Using the metric. Part
11
17
50/50 split
0.998
0.997
1.0
0.993
0.999
0.907
0.997
0.997
1.0
1.0
GraphRNN-108
0.919
0.985
0.958
0.915
0.914
0.921
0.924
0.958
GraphRNN-6Gr -666
0.912
0.985
0.935
0.98
0.935
0.88
0.974
0.91
0.98
0.945
GRAN-100%
1.0
1.0
1.0
GRAN-66%
1.0
1.0
0.995
0.99
1.0
0.99
0.993
1.0
1.0
1.0
30


Reviews:
[{"review_id": "wTMLp72AAB-", "reviewer": "Reviewer_UXK8", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "While I appreciate the general idea (that of using untrained/pretrained GNNs to extract graph embeddings and use these representations to compare sampled vs. real graphs), this paper has, in my opinion, two major defects (the second being much more important than the first).\n\n1) The paper is confusing and makes some incorrect claims.\nIn the abstract, the authors say that they introduce _one_ scalar metric for graph evaluation, yet in the discussion, they recommend _two_. Moreover, the authors claim that current metrics ignore node and edge features. This is not true: e.g. in https://arxiv.org/abs/2001.08184 and https://arxiv.org/abs/2107.08396 the distributions of node and edge labels are compared. Unfortunately, from the reader's perspective, these two points give the impression that the authors are not sure about which metric to use and they did not check the literature very well.\n\n2) Assuming that the proposed metric is random GIN + MMD RBF on the extracted graph representations, I argue this metric is not useful in the most important application field of GGMs: molecular generation. In fact, the chemical validity of a molecule cannot be captured by the graph representation in principle. I can think of an extreme example where the generated sample is composed of invalid molecules which only differ in one atom from the real sample. This generated sample would score close to 0 with the proposed metric, while in fact, it should be as close to 1 as possible. Of course, one could think of filtering out the invalid molecules first, but that defeats the purpose of having a unique metric in the first place. In my opinion (which I'll be happy to discuss), the world of graphs is not as regular as that of images; thus, the \"one metric to rule them all\" paradigm is not convincing to me.", "summary_of_the_paper": "The paper proposes a scalar metric for evaluating Graph Generative Models (GGMs). The metric is based on computing the Maximum Mean Discrepancy (with an RBF kernel) between graph representations of the sampled and real graphs, as extracted from an untrained GIN model. In the paper, the authors analyze several metrics (some used in the literature, some similar to the proposed setup, e.g. replacing MMD), and measure their fidelity (i.e. how sensitive is the metric to random graphs), diversity (i.e. how sensitive it is to mode collapse or mode dropping), sensitivity to node/edge features, sample efficiency (minimum number of graphs necessary to discriminate noise from real samples), and computational efficiency.", "summary_of_the_review": "I recommend rejection for now, for the motivations above. I will however await for the authors response and will update my claim accordingly.\n\nEDIT 1\nRaised my score to 5 after the first round of review and a first discussion with the authors.\n\nEDIT 2\nRaised my score to 6 considering the improved quality of the paper and the effort shown by the authors to fix what was wrong in the first version of the 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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XXk9BEWK6Nk", "reviewer": "Reviewer_CNrk", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The inclusion of a new method/framework for GGM evaluation is always welcome in the literature. The paper points out the main deficiencies and creates a new metric to evaluate GGM. \n\nOne advantage of this method is its simplicity. As it is explained in the paper, a GIN is applied and then the evaluation is realized. Unfortunately, this simplicity came with a cost, there is no theoretical contribution. It will be interesting to understand from a theoretical point of view, why this metric can actually solve the problems mentioned by the authors, instead of showing everything empirically. For example, there is no analysis of the time complexity. \n\nThere is also a phrase that avoids previous advances of the GGM. \"Frequently used datasets in the GGM literature are relatively small in size\". While this phrase could be true for GGM based on GNN, there are multiple GGM (Chung-Lu, mKPGM, BTER, etc) that are able to replicate networks with millions of nodes and edges, sampling them with a time complexity proportional to the number of edges (networks with millions of nodes and edges are sampled in minutes). \n\nBesides, even though the metric is able to solve some of the problems previously described, given the use of a GGN the embedding is impossible to interpret (neither its evaluation). For example, what does it mean a value of 0.97 in some of the metrics? \n\nThe comparison is against MMD which has several flaws, but the KS-multidimensional solves the same limitations mentioned in the paper. Moreover, the final value of the KS-multidimensional metric is also interpretable. ", "summary_of_the_paper": "The paper proposes the use of an untrained graph neural network (GNN) to generate a graph embedding which is used with other measures to evaluate Generative Graph Models (GGMs). The main advantages of this evaluation process are the use of a single score, the inclusion of node and edge features, and its empirical time complexity.", "summary_of_the_review": "While the presentation of a new method/framework is important for the GGM, the paper lacks theory, and the new metric is impossible to interpret. Moreover, the three critical points mentioned in the paper have already been solved by the KS-multidimensional distance. ", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "E6qdvvxL-f-", "reviewer": "Reviewer_Ru33", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is well written and the claims are well backed with experimental\nevidence. As it shows strong analogies to previous works in how the evaluation\nmetrics were evaluated and which aspects of the evaluation it focuses on, the\ntechnical novelty of this study is limited to the suggestion of using random\nGNNs for extracting features from generated graphs and the evaluation of sample\nefficiency. The empirical novelty is high (assuming other works on the\nevaluation of graph generative models are considered concurrent) as it is\nimportant to show the community the pitfalls of current GGM evaluation\napproaches in order to ensure that research progresses in an unbiased manner.\n\nI did find some aspects of the paper that could see some improvements though:\n - An exploration on the suitability of different GNNs would be extremely\n   useful to the community. Particularly, interesting would be how important\n   the concatenation of the layer readouts is. Here I imagine this to be of\n   high necessity for the approach to work one would otherwise expect\n   oversmoothing problems (especially for randomly initialized NNs).\n - The evaluation with regard to graph distribution perturbations only\n   considers a single type of graph perturbation -- mixing with random ER\n   graphs and edges being rewired to represent ER graphs. This gives rise to\n   the question if the model considered (GIN with sum aggregation) is biased\n   towards recognizing these types of distribution shift. I could imagine that\n   a randomly initialized GIN computes something similar to higher order node\n   degree statistics, which would be particularly suited for this task.\n - The parameter selection for MMD might have some complications to my\n   understanding: Here the scale parameter of the RBF kernel is selected to\n   maximally differentiate the two distributions, yet this criterion does not\n   include to which degree samples that are actually from the same distribution\n   get lower discrepancy compared to the samples which are OOD. While there is\n   some evidence that this should statistically not be the case for\n   characteristic kernels, these statistics would require a large sample size\n   for this to be true with very high probability which is not the case in all\n   the experiments.\n - Finally, I wonder how fair the comparison between the static graph\n   featurizations and the newly proposed approach is. The static approaches\n   using graph statistics rely on a non-parametric earth movers distance kernel\n   and thus do not undergo any additional selection of the hyperparameters\n   compared to the proposed approach of the paper. This is especially critical\n   in Table 2 where the approaches are compared directly using their MMD values\n   and rankings. I am not sure if this difference would manifest in changes to\n   the rank correlations in Figure 3 though.\n", "summary_of_the_paper": "The paper shows a detailed comparison of different graph generative model\nevaluation metrics and highlights that current approaches for the evaluation of\nGGMs are insufficient and perform poorly in terms of assessing diversity and\nfidelity of generated samples. The paper pinpoints these issues to the reliance\nof many metrics on a predefined set of features extracted from the generated\ngraphs. It claims that the efficacy of prior approaches is typically dependent\non the graph featurization and that this leads to inconsistencies in the\nranking of models when using different feature representations. It proposes to\ninstead use features from randomly initialized Graph Neural Networks as a basis\nfor the analysis and shows that this represents a competitive evaluation\napproach.", "summary_of_the_review": "The paper is well written and contributes some new thoughts and approaches for\nthe evaluation of GGMs in an unbiased manner.  I solely have minor\nconsiderations with regard to the types of graph perturbations selected and the\nselection of the MMD hyperparameters. Further, I question whether the\ncomparison classical evaluation approaches to the GNN based approaches is\ncompletely fair.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and 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": "AfQlyQVcY0o", "reviewer": "Reviewer_XmrB", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "In general, I think this paper provides a systematic way of evaluating the metrics and they are reasonable. But this paper provides lots of information that distracts the readers away from the main conclusions.\n\nStrengths: \n1. Many factors have been considered. Except for fidelity, I think mode collapse and dropping are very important factors but are often neglected, and I am glad to see those factors being considered here.\n\n2. I think the randomized GIN-based metrics have some novelty there and I am surprised to see they are more robust to mode collapse and dropping.\n\nWeakness:\n1. The NN-based metrics seem to be bound to the model GIN, so it's not sure if randomized GNNs are always robust to mode collapse and dropping compared to pretrained GNNs.\n\n2. When evaluating the rank correlations, the authors also vary different architectures (e.g, number of layers). Why do we require the metric to be insensitive to the number of layers? Or in other words, in Fig.3, where does the variance come from? Does the variance come from architectural changes or other factors?\n\n3. In Fig3, what is $\\hat{\\rho}(S_g, S_r)$?\n\n4. I am wondering whether graphs of different degree distributions will affect Fig.3? The datasets provided are quite small. I am wondering if you create several kinds of synthetic graphs and see for each type of graphs if your conclusions still hold.", "summary_of_the_paper": "This paper evaluates the effectiveness of different metrics for graph generative models from many perspectives. They thoroughly study the following factors: fidelity, diversity, sensitivity to node/edge features. They find that pre-existing GGM metrics fail to capture the diversity of data and find several random GIN-based metrics that are more expressive and have low computational costs.", "summary_of_the_review": "I think the paper has evaluated different metrics extensively and they have provided abundant information. However, I feel a bit lost when I read this paper due to distractions from the details. I think authors should make their conclusions more clear before providing details. Besides, a few more concerns about this paper have been mentioned above.", "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": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper argues that existing evaluation metrics for GGMs are insufficient and perform an extensive empirical study questioning their ability to measure the diversity and fidelity of the generated graphs. To solve these limitations, they propose a new evaluation metric that computes the Maximum Mean Discrepancy (MMD) between graph representations of the sampled and real graphs, as extracted from an untrained GGM model. 

All the reviewers agreed that the research problem is interesting and the overall idea behind the proposed metric is sound and novel. While there were some concerns regarding some details/comparisons/conclusions of the experimental evaluation, the rebuttal managed to cleared up these concerns and all the reviewers eventually supported acceptance.
Decision: Accept (Poster)