Year: 2021

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

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

heading: 1 INTRODUCTION
text: Graph generation is 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., 2021; Jin et al., 2020) and structure generation (Bapst et al., 2019; Thompson et al., 2020). An evaluation metric that is capable of accurately measuring the distance between a 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 as orbit counts, degree coefficients, and clustering coefficients through Maximum Mean Discrepancy (MMD) (You et al., 2018; Gretton et al., 2006). While these metrics are capable of making a meaningful comparison between generated and real graphs (You 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., 2019). 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; 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’Bray et al., 2021), and they are based only on 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 are essential. This particular limitation has led to the use of the Neighborhood Subgraph Pairwise Distance kernel (NSPDK) (Costa & 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 metrics that can consistently rank GGMs.
While less popular, metrics from image generation literature have been successfully utilized in GGM evaluation. These metrics rely on the use of a task-specific neural network to extract meaningful representations of samples, enabling a more straightforward comparison between generated and reference distributions (Preuer et al., 2018; Liu et 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, Fréchet Chemnet Distance (Preuer et al., 2018) 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 a 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 (Bińkowski et al., 2018; Heusel et al., 2017; Kynkäänniemi et al., 2019; Xu et al., 2018; Naeem et al., 2020). While classifiers such as Inception v3 (Szegedy et al., 2016) are consistently used, recent works have investigated the use of randomly-initialized CNNs with no further training (hereafter referred to as a 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 et al., 2019; Xu et al., 2019). However, the applicability of random GNNs for the evaluation of GGMs remains unexplored.
In this work, we aim to identify one or more scalar metrics 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 as their sample and computational efficiency. We study three families of metrics: existing GGM evaluation metrics based on graph statistics 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-agnostic metric for evaluating and ranking GGMs? Addressing these questions enabled us to reveal several surprising findings that directly impact the future of GGM evaluation. 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 metrics 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 ideal for evaluating and ranking GGMs in certain scenarios; they are scalable, powerful, and easily incorporate continuous or discrete node and edge features. These findings enable computationally inexpensive and domain-agnostic GGM evaluation.

heading: 2 BACKGROUND & RELATED WORK
text: Evaluating generative models in any domain is a notoriously difficult task (Theis et al., 2016). However, researchers have found success through the use of sample-based evaluation metrics that estimate the distance ρ between real and generated distributions Pr and Pg by drawing random samples (Heusel et al., 2017; You et al., 2018; Bińkowski et al., 2018). That is, they compute ρ̂(Sg,Sr) ≈ ρ(Pg, Pr), with Sr = {xr1, . . . ,xrm} ∼ Pr and Sg = {x g 1, . . . ,x g n} ∼ Pg , where xi is defined as some feature vector extracted from a corresponding graph Gi. These metrics are model agnostic and therefore applicable to all generative models.

heading: 2.1 CLASSICAL METRICS
text: Metrics based on graph statistics (You et al., 2018) are standard in evaluating GGMs (Liao et al., 2019; Dai et al., 2020). These metrics require extracting the clustering coefficient, node degree, and
4-node orbit count histograms1 that are then used to compute the empirical MMD between generated and reference sets Sg,Sr (Gretton et al., 2006):
MMD(Sg,Sr) := 1
m2 m∑ i,j=1 k(xri ,x r j) + 1 n2 n∑ i,j=1 k(xgi ,x g j )− 2 nm n∑ i=1 m∑ j=1 k(xgi ,x r j), (1)
where k(·, ·) is a general kernel function. You et al. (2018) proposed a form of the RBF kernel:
k(xi,xj) = exp
( −d(xi,xj)
2σ2
) , (2)
where d(·, ·) computes pairwise distance, and in that work was chosen to 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 1 (Liao et al., 2019). However, this change leads to an indefinite kernel and undefined behaviour (O’Bray et al., 2021). 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 k(·, ·) 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 as node degree, clustering coefficient, and geodesic distance. However, these properties are then combined into a scalar metric through the KolmorogovSmirnov (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 domain-specific metrics such as “percentage of valid graphs” exist. Our goal is not to incorporate, eliminate, or evaluate such metrics; they are properties of generated graphs, and unlike the metrics described above do not provide a comparison to a reference distribution. We believe that such metrics can still provide valuable information in GGM evaluation.

heading: 2.2 GRAPH NEURAL NETWORKS
text: We denote a graph as G = (V, E) with n vertices V and edges E = {(i, j) | i, j ∈ {1, . . . , n}}. GNNs allow the extraction of a fixed size representation xi of an arbitrary graph Gi. While many GNN formulations exist (Wu et al., 2020), we consider Graph Isomorphism Networks (GINs) (Xu et al., 2019) as a common GNN. GINs consist of L propagation layers followed by a graph readout layer to obtain xi. For node v ∈ V, the node embeddings h(l)v at layer l ∈ [1, L] are computed as:
h(l)v = MLP (l) ( h(l−1)v + f (l) ( {h(l−1)u : u ∈ N (v)} )) , (3)
where h(0)v is the input feature of node v, h (l) v ∈ Rd ∀ l > 0 denotes a d-dimensional embedding of node v after the l-th graph propagation layer; N (v) denotes the neighbors of node v; MLP(l) is a fully-connected neural network; f (l) 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 l ∈ [1, L] and concatenates them into a single L · d dimensional vector xi (Xu et al., 2019):
xi = CONCAT ( READOUT ( {h(l)v | v ∈ V} ) | l ∈ 1, 2, ..., L ) , (4)
where READOUT is similar to f (l) and is often chosen as the mean, max, or sum operation.

heading: 2.3 NEURAL-NETWORK-BASED METRICS
text: NN-based metrics utilize a task-specific network to extract meaningful multidimensional embeddings of the input data. In image generation evaluation, the activations of a hidden layer in Inception v3 (Szegedy et al., 2016) are frequently used as vectorial 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 metrics 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 1).
Fréchet Distance (FD) (Heusel et al., 2017) is one of the most popular generative metrics. FD approximates the graph embeddings as continuous multivariate Gaussians with sample mean and covariance µ,C. The distance between distributions is computed as an approximate measure of sample quality: FD(Sr,Sg) = ‖µr − µg‖22 + Tr(Cr + Cg − 2(CrCg)1/2). Improved Precision & Recall (P&R) (Kynkäänniemi et al., 2019) decouples the quality of a generator into two separate values to aid in the detection of mode collapse and mode dropping. Mode dropping refers to the case wherein modes of Pr are underrepresented by Pg , while mode collapse describes a lack of diversity within the modes of Pg . Manifolds are constructed by extending a radius from each embedded sample in a set to its kth nearest neighbour to form a hypersphere, with the union of all hyperspheres representing a 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 a scalar metric that can be decomposed into more meaningful values in experiments (Lucic et al., 2018).
Density & Coverage (D&C) (Naeem et al., 2020) have recently been introduced as robust alternatives for Precision and Recall, respectively. Density is calculated as the average number of real examples within whose manifold radius each generated sample falls. Coverage is described as the percentage of real examples that have a generated sample fall within their manifold radius. The manifolds used are found using the kth 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 1) can also be used to measure the dissimilarity between graph embedding distributions. The original Kernel Inception Distance (KID) (Bińkowski et al., 2018) proposed a polynomial kernel with MMD, k(xi,xj) = ( 1dx > i xj + 1)
3, where d is the embedding dimension. The linear kernel k(xi,xj) = xi · xj is another parameter-free kernel used with MMD to evaluate generative models (O’Bray et al., 2021). In addition, the RBF kernel (Equation 2) with d(·, ·) as the Euclidean distance is widely used (Xu et al., 2018; Gretton et al., 2006). The choice of σ in Equation 2 has a significant impact on 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 et al., 2012a;b). A common strategy is to select σ as the median pairwise distance between the two comparison sets (Garreau et al., 2018; Gretton et al., 2006; Schölkopf et al., 1998). Another strategy is to evaluate MMD using a small set of σ values and select the value that maximizes MMD: σ = arg maxσ∈Σ MMD(Sg,Sr;σ) (Sriperumbudur et al., 2009). We combine these ideas in our σ selection process, and more details are available in Appendix A. We refer to these metrics as “KD,” “MMD Linear,” and “MMD RBF.”

heading: 2.4 BENCHMARKING EVALUATION METRICS
text: Our work is closely related to other works benchmarking evaluation metrics of generative models (O’Bray et al., 2021; Xu et al., 2018). A consistent method for assessing evaluation metrics is to start with the creation of “reference” and “generated” sets Sr and Sg that originate from the same real distribution Pr. Then, one gradually increases distortion to the generated set while recording each metric’s response to the distortion. In the image domain, Xu et al. (2018) develop multiple experiments to test metrics for key properties. The metrics are then subjectively evaluated for these properties by manually analyzing each metric’s response across experiments. In concurrent work, O’Bray et al. (2021) introduced additional GGM evaluation metrics. Similar to Xu et al.
1While any set of graph statistics can be compared using MMD, these three are the most common and hence are evaluated in this work.
(2018), the metrics are validated through experiments that slowly increase the level of perturbation in each graph in the generated set. However, O’Bray et al. (2021) incorporated an objective evaluation score by computing 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.

heading: 3 THE EFFECTIVENESS OF RANDOM GNNS
text: While Inception v3 (Szegedy et al., 2016) has found widespread use in evaluation of generated samples (Salimans et al., 2016; Cai et al., 2018; Lunz et al., 2020), there is no analogue in graph-based tasks. This prevents a standardized analysis of GGMs. To tackle this, a single GNN may be pretrained 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, degrading 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., 2019; Xu et al., 2019).2 Thus, avoiding pretraining and instead utilizing random GNNs may be a viable strategy to bypass these issues. To test this approach, we apply permutations to Grid graphs by randomly rewiring edges with probability p. Therefore, as we increase p, the dissimilarity between the original graphs and permuted graphs increases. Thus, if a GNN is capable of extracting strong representations from graphs, the graph embeddings should also increase in dissimilarity with p. We visualize the embeddings extracted from a pretrained GIN (Xu et al., 2019) and a random GIN in Figure 2, 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., 2019), however, we also provide a comparison to other common GNNs in Appendix C.6.

heading: 4 EXPERIMENTS
text: In this section, we describe many properties of a 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 characteristics of a strong evaluation metric and enables reliable ranking of GGMs. In many cases, we adapt the experiment design of Xu et al. (2018) to the graph domain.
Datasets. We experiment using a variety of datasets with varying sizes and characteristics to test each metric’s ability to evaluate GGMs across domains. In particular, we include common GGM
2In the image domain, random CNNs are also beneficial in certain cases, such as large distribution shifts (Naeem et al., 2020).
datasets such as Lobster, Grid, Proteins, Community, and Ego (You et al., 2018; Liao et al., 2019; Dai et al., 2020). In addition, we utilize the molecular dataset ZINC (Irwin et al., 2012) strictly to demonstrate the ability of each metric to detect changes in node and edge feature distributions with no graph structure manipulation. We provide a brief overview of each dataset in Table 1, and thorough descriptions in Appendix B.
Table 1: A summary of the datasets used throughout.
DATASET #SAMPLES |V| |E| NODE/EDGE FEATURES
Grid 100 100-400 360-1368 7 Lobster 100 10-100 10-100 7 Proteins 918 100-500 186-1575 7 Ego 757 50-399 57-1071 7 Community 500 60-160 300-1800 7 ZINC 1000 10-50 22-82 3 GNN feature extractor. As the GGM literature frequently 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 statistic-based metrics in Section 2.3, there is a bias towards minimizing the length of x while retaining discriminability. As seen in Equation 4, 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 3 and 4) with L ∈ [2, 3, . . . , 7], 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 B. Results for metrics computed using a pretrained GIN in individual experiments are left to Appendix C.1. However, we summarize these results in Table 3 in Section 5 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.
Evaluating the evaluation metrics. All experiments are designed to begin with Pg ≈ Pr, and to have a monotonically increasing degree of perturbation t ∈ [0, 1] that is a measure of the dissimilarity between Sg and Sr. We evaluate each metric objectively by computing the Spearman rank correlation between the metric scores and the degree of perturbation. Spearman rank correlation is preferable to Pearson correlation as it avoids any bias towards a linear relationship. All metrics are normalized such that ρ̂ = 0 if Pr = Pg meaning a strong metric will increase with t and a rank correlation of 1.0 is assumed to be ideal. We test each metric and GIN architecture combination 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 single random seed (which varies model weights and perturbations applied, if applicable), experiment (e.g. edge rewiring), dataset (e.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.

heading: 4.1 MEASURING FIDELITY
text: One of the most important properties of a 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., 2021). Each of these experiments begin with Sg as a copy of Sr, which is itself a copy of the dataset.
In the first experiment, we utilize random graphs to impact the quality of Sg . To decrease the similarity between Sr and Sg , we slowly mix random graphs by increasing the ratio t of random graphs to real graphs in Sg(t). The random graphs are Erdős-Rényi (E-R) graphs (Erdős & Rényi, 1960) with sizes and p values chosen to resemble Sr: for every Gr ∈ Sr, there is a corresponding E-R graph Gg with |V|g = |V|r and p = |E|r|V|2r , which is the sparsity of the adjacency matrix of Gr.
The second experiment increases distance between Pr and Pg by randomly rewiring edges in Sg . Here, the degree of perturbation t is the probability of rewiring each edge (i, j) ∈ E. For each G ∈ Sg and each (i, j) ∈ E, a sample xi,j ∼ Bernoulli(t) is drawn. Edges with xi,j = 1 are rewired, another sample yi,j ∼ Bernoulli(0.5) is drawn to decide which node {i, j} of the edge is kept, and a new connection for this edge is chosen uniformly from V.
With the exception of Recall and Orbits MMD, the majority of tested metrics excel in these experiments as indicated by a rank correlation close to 1.0 (Figure 3, top). However, Recall is specifically designed to measure diversity of Sg rather than fidelity, and its low sensitivity to fidelity here is expected. Surprisingly, Coverage demonstrates strong sensitivity to the fidelity of Sg although it is also designed to measure the diversity of Sg . In addition, we repeat the mixing experiment with graphs generated by GRAN (Li et al., 2018) and obtain very similar results (see Appendix C.4).

heading: 4.2 MEASURING DIVERSITY
text: The next property we investigate is a metric’s ability to measure the diversity of generated samples in Sg . 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, 2007) to identify the modes of Pr. Both of these experiments begin with Sr and Sg as disjoint halves of the dataset.
To simulate mode collapse, we progressively replace each datapoint with its cluster centre. The degree of perturbation t represents the ratio of clusters that have been collapsed in this manner. To simulate mode dropping, we progressively remove clusters from Sg . To keep |Sg| constant, we randomly select samples from the remaining clusters to duplicate. In this experiment, the degree of perturbation t is the ratio of clusters that have been deleted from Sg .
In the mode collapse experiment, all classical metrics (You 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 Sg , while Precision and Density are negatively correlated. In addition, several scalar metrics such as MMD RBF and F1 PR exhibit strong correlation with the diversity of Sg across both experiments.

heading: 4.3 SENSITIVITY TO NODE AND EDGE FEATURES
text: In this experiment, we measure the sensitivity of each metric to changes in node or edge feature distributions 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 provide more thorough descriptions of these experiments in Appendix B. We exclude metrics from You
et al. (2018) in these experiments as they are unable to incorporate both edge and node features in evaluation. We find all NN-based metrics and NSPDK MMD are sensitive to these perturbations, and a summary is provided in Table 3.

heading: 4.4 SAMPLE EFFICIENCY
text: Small datasets are frequently used in the GGM literature so the notion of sample efficiency is important. In this experiment, we determine the sample efficiency of each metric by finding the minimum number of samples to discriminate a set of random graphs Sg from real samples Sr. 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′r and S′′r from Sr, and a set of random graphs S′g from Sg with |S′r| = |S′′r | = |S′g| = n and small n. A metric with high sample efficiency should measure ρ̂(S′r,S′′r ) < ρ̂(S′r,S′g) with a small n. Rather than using rank correlation, in this experiment we record the sample efficiency of each metric as the smallest n where ρ̂(S′r,S′′r ) < ρ̂(S′r,S′g) ∀i ≥ n. All of the metrics based on K-nearest neighbours and many of the classical metrics exhibit high sample efficiency and require a minimal number of samples to correctly score S′′r and S′g (Table 3).

heading: 4.5 COMPUTATIONAL EFFICIENCY
text: 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 number 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 us to independently scale graphs in each dimension. The results highlighting each metric’s computational efficiency as dataset size increases to 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 to compute as the number of samples increase, while the NN-based metrics are faster by several orders of magnitude and are inexpensive to compute at any scale.

heading: 4.6 GGM SELECTION
text: While NN-based metrics such as MMD RBF and F1 PR have performed consistently in our experiments, this does not necessarily mean they are suited for evaluating GGMs. With the lack of an Inception v3 (Szegedy et 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 et al., 2019) and GraphRNN (You et al., 2018) on the Grid dataset. To measure the variance induced by changing model paramterizations, we compute ρ̂(Sg,Sr) across 10 different random GINs. We use the strongest GIN configuration along with a strong NN-based metric, MMD RBF, both of which we identify in Section 5. We simulate the model selection process by evaluating models at various stages of training and find that metrics from You et al. (2018) are unable to unanimously rank GGMs (Table 2). As GGMs are frequently evaluated by considering all of these metrics together, this highlights the difficulty that may arise during model selection with this evaluation 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 F1 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 an 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.

heading: 5 DISCUSSION
text: We aggregate the results across experiments for a high-level overview of each metric’s strengths and weaknesses in Table 3. Metrics computed using a pretrained GIN are nearly indistinguishable from those using a 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 a simple random initialization (Table 12 in Appendix C.8). Similar to Table 3, we aggregate the results across all experiments and metrics for a specific GIN configuration in Table 4b in Appendix C. We find that the mean rank correlation taken across NN-based metrics and all experiments is approximately 10× higher variance than the mean taken across GIN configurations (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 feature space used to extract graph embeddings. Table 2: Evaluation of different GGMs at various percentages
of total epochs trained on the Grid dataset. Cells are colored according to their rank in a given column.
GGM MMD RBF Clus. Deg. Orbit
50/50 split 0.042 0.0 6.51e−5 0.018 GraphRNN-100% 0.184± 5e−5 4.59e−8 0.032 0.252 GraphRNN-66% 0.154± 7e−5 1.69e−6 0.015 0.169 GRAN-100% 0.063± 0.001 1.24e−6 1.68e−4 0.037 GRAN-66% 0.061± 0.001 3.15e−6 3.20e−5 0.047 In practice, to measure the distance between two sets of graphs we recommend the use of either the MMD RBF or F1 PR metrics. 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.3 To highlight this, we provide results for individual datasets in Appendix B.1 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, F1 PR has superior sample and computational efficiency. Thus, we suggest the use of F1 PR in cases where there are less samples than the measured sample size of MMD RBF (i.e., 42) or MMD RBF is extremely prohibitive to compute, otherwise, we suggest MMD RBF.

heading: 6 CONCLUSION
text: 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 to provide theoretical justification supporting the use of random GINs, as well as the exploration of more sophisticated GNNs to improve sample efficiency.
3This 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 a reference set based on a singular graph statistic, the metrics from You et al. (2018) are still invaluable.

heading: Appendices

heading: A Additional metric details 13

heading: B Additional experimental details 14
text: B.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
B.2 Measuring diversity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
B.3 Randomizing edge features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
B.4 Randomizing node features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
B.5 Computational efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
B.6 GGM selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
B.7 GNN pretraining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

heading: C Additional results 15
text: C.1 Individual experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
C.2 All experiments grouped by GIN configuration . . . . . . . . . . . . . . . . . . . 18
C.3 All results grouped by dataset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
C.4 Mixing generated graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
C.5 Computational efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
C.6 Comparing other GNNs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
C.7 Comparing σ selection strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
C.8 GGM model selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

heading: A ADDITIONAL METRIC DETAILS
text: For Precision, Recall, Density, and Coverage, we set k = 5 for all experiments (Naeem et al., 2020). For the MMD RBF metric, we compute MMD as MMD(Sg,Sr) = max{MMD(Sg,Sr;σ) | σ ∈ Σ}, where the values of Σ are multiplied by the mean pairwise distance of Sg and Sr. While the median pairwise distance is the heuristic (Garreau et al., 2018), we 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 et al. (2018), we use the hyperparameters chosen in their open-source code. For the NSPDK MMD metric we use the open-source code from Goyal et al. (2020)

heading: B ADDITIONAL EXPERIMENTAL DETAILS
text: Following Section 2.2, we denote a graph as G = (V, E) with n vertices V and edges E = {(i, j) | i, j ∈ {1, . . . , n}}. Node features for node i ∈ V are denoted as hi ∈ Rb (h(0)i in Section 2.2). Similarly, A ∈ Rn×n×a stores edge information, with the (i, j)th entry corresponding to the edge features for edge (i, j). Unless otherwise specified in Appendix B.1, A is not utilized and we set hi to the degree of node i expressed as an integer as an inexpensive way to improve discriminability. We handle edge features by concatenating Ai,j,: to messages from node i to node j at each round of graph propagation (Hu et al., 2020).

heading: B.1 DATASETS
text: We perform experiments using a variety of datasets with varying sizes and characteristics to thoroughly test each metric’s ability to evaluate GGMs across domains. We place a slight emphasis on 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 a backbone path. We generate lobster graphs with 10 ≤ |V| ≤ 100 (Dai et al., 2020). Grid. 100 2D grid graphs generated with 100 ≤ |V| ≤ 400 (Dai et al., 2020; You et al., 2018; Liao et al., 2019).
Proteins. 918 protein graphs where nodes are amino acids and two nodes are connected by an edge if they are less than 6 Angstroms away (Dobson & Doig, 2003). We select graphs with 100 ≤ |V| ≤ 500 (You et al., 2018; Liao et al., 2019; Dai et al., 2020).
Ego. 757 3-hop ego networks with 50 ≤ |V| ≤ 399 (You et al., 2018). Graphs are extracted from the CiteSeer network where nodes represent documents and edges represent citation relationships (Sen et al., 2008).
Community. 500 two-community graphs with 60 ≤ |V| ≤ 160. Each community is generated by the Erdős-Rényi model (E-R) (Erdős & Rényi, 1960) with n = |V|/2 and p = 0.3. We then add 0.05|V| inter-community edges with uniform probability (You et al., 2018). ZINC. 250k real-world molecular graphs (Irwin et al., 2012) of which we randomly select 1000 samples for efficiency with 10 ≤ |V| ≤ 50. We set hi to be a one-hot encoding of the element of node i, and Ai,j,: to be a one-hot encoding a ∈ Ra of the bond type between nodes i and j. This dataset is unique in that it is the only one to naturally contain node and edge features. Thus, we can use this dataset to determine a metric’s sensitivity to changes in the edge and node feature distributions without generating artificial labels.

heading: B.2 MEASURING DIVERSITY
text: We employ Affinity Propagation (Frey & Dueck, 2007) to automatically determine the number of clusters, and set the similarity between graphs to be the value obtained from the WL-subtree kernel (Shervashidze et al., 2011) 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.

heading: B.3 RANDOMIZING EDGE FEATURES
text: This experiment is performed exclusively on the ZINC dataset as it naturally contains edge features. Here, the degree of perturbation t is the probability of randomizing each edge feature Ai,j,:,∀(i, j) ∈ E. For each G ∈ Sg and each edge (i, j) ∈ E, a sample xi,j ∼ Bernoulli(t) is drawn. Edges with xi,j = 1 have their edge feature randomized. As these features are a one-hot encoding, we sample the new edge feature uniformly from the set of valid edge features. The results of this experiment are shown in Figure 9.

heading: B.4 RANDOMIZING NODE FEATURES
text: This experiment is performed exclusively on the ZINC dataset as it naturally contains node features. Here, the degree of perturbation t is the probability of randomizing each node feature hi,∀i ∈ V. For each G ∈ Sg and each node i ∈ V, a sample xi ∼ Bernoulli(t) is drawn. Nodes with xi = 1 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 are shown in Figure 9.

heading: B.5 COMPUTATIONAL EFFICIENCY
text: All experiments in this section were conducted on an Intel Platinum 8160F Skylake @ 2.1Ghz with 4 CPU cores. We benchmark NN-based metrics using the most expensive GIN configuration tested in our experiments. This was a configuration with 7 propagation layers and a node embedding size of 20. The results for this experiment on CPU are shown in Figure 10 and on GPU in Figure 11. In addition, the approximate RAM usage for each metric throughout these experiments are shown in Figure 12 and Table 9.
Scaling number of samples. We generate various sets of E-R graphs (Erdős & Rényi, 1960) to scale the number of 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 |V| = 50 for all graphs. We choose p = |E|avg|V|2avg 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 p in [0.01, 0.1, 0.2, . . . , 1.0]. Scaling number of nodes. We generate 50 graphs of a constant size per set with |V| in [1000, 10k, 20k, . . . , 100k]. For each set, we use p = 10000|V|2 to generate graphs with approximately 10000 edges per graph.

heading: B.6 GGM SELECTION
text: We train GRAN (Liao et al., 2019) and GraphRNN (You 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 n graphs from each model where n is the size of the dataset, and use the remaining 20% of graphs as Sr.

heading: B.7 GNN PRETRAINING
text: 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 Gr in the remaining datasets, we generate an E-R graph (Erdős & Rényi, 1960) Gg with |V|g = |V|r and p = |E|r|V|2r . These E-R graphs have separate labels, thereby doubling the number of classes present. We use the same 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.

heading: C ADDITIONAL RESULTS
text: Here we provide a variety of supplementary experiments that were not included in the main body due to page limits. Unless otherwise specified, results for all GIN-based metrics utilize a random GIN, are aggregated across all GIN configurations, and all GIN configurations use summation aggregation.
C.1 INDIVIDUAL EXPERIMENTS
We provide violin plots for each individual experiment in Figures 4 through 8.

heading: C.2 ALL EXPERIMENTS GROUPED BY GIN CONFIGURATION
text: We aggregate results by GIN configuration across all experiments in Tables 4. In addition, we aggregate results by GIN configuration and metric combination and highlight the top 20 results in Table 5.

heading: C.3 ALL RESULTS GROUPED BY DATASET
text: For a 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, all of our conclusions drawn in Section 5 still 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 of the Community dataset all baseline metrics (You et al., 2018) are poor at measuring the diversity of generated graphs. Notably, the performance of Clustering MMD on diversity experiments is affected by the Lobster and Grid datasets; these graphs are triangle-free and thus all nodes have a clustering coefficient of zero. However, even if these datasets are excluded from the analysis, Clustering MMD is still suboptimal on the remainder of the datasets.

heading: GIN CONFIG. FIDELITY DIVERSITY FIDELITY & DIVERSITY SAMPLE EFF.

heading: GIN CONFIG. FIDELITY DIVERSITY FIDELITY & DIVERSITY SAMPLE EFF.

heading: GIN CONFIG., METRIC FIDELITY DIVERSITY FIDELITY & DIVERSITY SAMPLE EFF.

heading: GIN CONFIG., METRIC FIDELITY DIVERSITY FIDELITY & DIVERSITY SAMPLE EFF.

heading: METRIC MIXING RANDOM MIXING GENERATED

heading: C.4 MIXING GENERATED GRAPHS
text: 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 are a better representation of the dataset of interest, this represents a much harder problem. However, as seen in Table 8, the results across metrics are fairly consistent regardless of the type of graph used.

heading: C.5 COMPUTATIONAL EFFICIENCY
text: 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 imperfect and slightly noisy, it provides an 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 specific 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 9.

heading: C.6 COMPARING OTHER GNNS
text: In the main article, all experiments were performed using GIN with summation neighborhood aggregation 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 neighborhood aggregation. With minor architecture differences, the former is equivalent to random GCN (Kipf & Welling, 2017), while the latter is equivalent to random GraphSAGE (Hamilton et al.,

heading: METRIC FIDELITY DIVERSITY FIDELITY & DIVERSITY NODE/EDGE FEATS. SAMPLE EFF.

heading: METRIC FIDELITY DIVERSITY FIDELITY & DIVERSITY NODE/EDGE FEATS. SAMPLE EFF.
text: 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 at graph propagation round L. We find that while GIN is superior across the presented metrics, it is in many cases only by a very narrow margin (Table 10). The performance of MMD RBF appears to be relatively constant across GNNs, while the performance of F1 PR has higher variance.
C.7 COMPARING σ 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 a static σ = 1 using a 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 metrics. Note that we 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.

heading: C.8 GGM MODEL SELECTION
text: Here we evaluate GGMs at various stages of training on Grid, Lobster and Proteins datasets using classical metrics (You et al., 2018), NN-based metrics using a random GIN, and NN-based metrics using a pretrained GIN. The results are shown in Table 12.

Review summaries:
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.

The paper shows a detailed comparison of different graph generative model evaluation metrics and highlights that current approaches for the evaluation of GGMs are insufficient and perform poorly in terms of assessing diversity and fidelity of generated samples. The paper pinpoints these issues to the reliance of many metrics on a predefined set of features extracted from the generated graphs. It claims that the efficacy of prior approaches is typically dependent on the graph featurization and that this leads to inconsistencies in the ranking of models when using different feature representations. It proposes to instead use features from randomly initialized Graph Neural Networks as a basis for the analysis and shows that this represents a competitive evaluation approach.

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.