Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: 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.
main_review: The paper is well written and the claims are well backed with experimental
evidence. As it shows strong analogies to previous works in how the evaluation
metrics were evaluated and which aspects of the evaluation it focuses on, the
technical novelty of this study is limited to the suggestion of using random
GNNs for extracting features from generated graphs and the evaluation of sample
efficiency. The empirical novelty is high (assuming other works on the
evaluation of graph generative models are considered concurrent) as it is
important to show the community the pitfalls of current GGM evaluation
approaches in order to ensure that research progresses in an unbiased manner.

I did find some aspects of the paper that could see some improvements though:
 - An exploration on the suitability of different GNNs would be extremely
   useful to the community. Particularly, interesting would be how important
   the concatenation of the layer readouts is. Here I imagine this to be of
   high necessity for the approach to work one would otherwise expect
   oversmoothing problems (especially for randomly initialized NNs).
 - The evaluation with regard to graph distribution perturbations only
   considers a single type of graph perturbation -- mixing with random ER
   graphs and edges being rewired to represent ER graphs. This gives rise to
   the question if the model considered (GIN with sum aggregation) is biased
   towards recognizing these types of distribution shift. I could imagine that
   a randomly initialized GIN computes something similar to higher order node
   degree statistics, which would be particularly suited for this task.
 - The parameter selection for MMD might have some complications to my
   understanding: Here the scale parameter of the RBF kernel is selected to
   maximally differentiate the two distributions, yet this criterion does not
   include to which degree samples that are actually from the same distribution
   get lower discrepancy compared to the samples which are OOD. While there is
   some evidence that this should statistically not be the case for
   characteristic kernels, these statistics would require a large sample size
   for this to be true with very high probability which is not the case in all
   the experiments.
 - Finally, I wonder how fair the comparison between the static graph
   featurizations and the newly proposed approach is. The static approaches
   using graph statistics rely on a non-parametric earth movers distance kernel
   and thus do not undergo any additional selection of the hyperparameters
   compared to the proposed approach of the paper. This is especially critical
   in Table 2 where the approaches are compared directly using their MMD values
   and rankings. I am not sure if this difference would manifest in changes to
   the rank correlations in Figure 3 though.

summary_of_the_review: The paper is well written and contributes some new thoughts and approaches for
the evaluation of GGMs in an unbiased manner.  I solely have minor
considerations with regard to the types of graph perturbations selected and the
selection of the MMD hyperparameters. Further, I question whether the
comparison classical evaluation approaches to the GNN based approaches is
completely fair.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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. 

One 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. 

There 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). 

Besides, 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? 

The 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_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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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).

1) The paper is confusing and makes some incorrect claims.
In 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.

2) 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_review: I recommend rejection for now, for the motivations above. I will however await for the authors response and will update my claim accordingly.

EDIT 1
Raised my score to 5 after the first round of review and a first discussion with the authors.

EDIT 2
Raised 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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

Strengths: 
1. 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.

2. 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.

Weakness:
1. 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.

2. 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?

3. In Fig3, what is $\hat{\rho}(S_g, S_r)$?

4. 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_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.
review_title: null

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)