Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper proposes a novel statistical procedure to evaluate and interpret implicit graph generators based on approximate graph Stein statistics.
strengths_and_weaknesses: Strengths:

- The paper is well-motivated and well-written. It is also timely, as it echoes the efforts of the community towards more explainable machine learning models. 
- The numerical results comparing AggraSSt with other methods are convincing, and show that AgraSST outperforms them empirically.

Weaknesses:

- The fact that AgraSSt depends on the chosen summary statistic $t(x)$ is not necessarily a weakness, but it requires expert selection. This should be more stressed throughout the paper. The effects of a specific (good or poor) choice of $t(x)$ should also be illustrated.
- It is not clear whether AgraSSt does better than, e.g., only comparing sums of degrees for vertex pairs $s$ (Sum_deg in Figure 1), simply because $t(x)$ encompasses more summary statistics. In other words, does AgraSSt bring any intrinsic advantages, or do they only come for the fact that it allows to simultaneously consider multiple summary statistics?
- It would have been interesting to see numerical experiments in graphs with variable sparsity levels (e.g., power law, expander graphs), and possible failure cases for AgraSSt (perhaps related to the choice of $t(x)$).
questions: Questions:

- What is the effect of $\beta_2$ (equation (11)) in sparsity? Does sparsity grow or decrease from left to right in Figures 1a-1c?
- How was the hyperparameter selection done for the GraphRNN, NetGAN, and CELL in Table 1?

Minor comments:

- Typo in line 72 (comma before For).
- The authors should explicitly write the assumptions/conditions necessary for stating Lemma 3.1 in the body of the lemma (instead of writing "In this setting, ...").
- For readability, the update equations in lines 137-138 and equation 8 should be included in Algorithm 1. "be" missing in instruction 2 of Algorithm 1.
- Line 162 should be an equation.
- Better explain the axes of Figures 1a-1c.
- Include a more precise description of the key (colors) of Figure 1c.

limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a statistical procedure for assessing the quality of graph generators. The procedure, namely, AgraSSt, approximates the Stein operator on implicit graph generators. This is done inspired by to the graph kernel Stein statistic (gKSS) for goodness-of-fit test on random graphs. The key step in this process is to estimate the conditional probability of an edge $s$ being present conditional on $t(x_{−s})=k$ by an estimator $\hat g_t (s; k)$; where t(x) denotes a statistic on graphs. AgraSSt is evaluated using synthetic data ERGM (specifically the Edge- 2Star-Triangle (E2ST) model) and compared with 5 possible graph characteristics (degree, total variation, Mahalanobis distance between degree distributions, via a parametric model, and gKSS). AgraSSt was also evaluated on real datasets to test the goodness-of-fit of various graph generators trained using Zachary’s Karate Club  network. The generators considered were: GraphRNN, NetGAN, CELL, and Monte Carlo network sampling. 
strengths_and_weaknesses: In summary, the paper is somewhat clear but more could be added to make it self-contained. The organization is not bad. The originality is mostly about the specific equality constrain considered during sampling. The quality of the work is theoretically good and experimentally reasonable. Some specific details include:

Strengths:
The significance of a possible solution to the problem of quality assessment of implicit graph generators is profound. This could have impact to validate models in various domains in science where GNN models are used to capture relational structure in data.
The theoretical analysis seems sound and can justify the consistency of the AgraSSt estimator.
The paper presents validation of the estimator using various graph statistic (not just one) using synthetic data and compares the graph assesment using various graph generators. 


Weaknesses:
The paper relies in concepts that are not thoroughly introduced in the paper and thus, the paper lack self-containment. For instance what is the effect of exchangeability, why is this important in non-implicit graph generators? 
The experiments are interesting but only provide an exploratory perspective of the graph generator assessment tool. Since there are no other alternatives to compare with, it may important to use some basic naive baselines to do so. For instance, by modifying an existing generator to build empirical distributions that could be used for hypothesis testing.
questions: Using graph statistics to define AgraSSt provides flexibility. However, how can this technique provide adequate assessment for graph communities? 
These are statistics that many degrees of freedom not easily solved by techniques driven by graph-statistics. How can AgraSSt deal with this situations?

More than by Stein operators for random graphs (as stated in the abstract), AgraSSt is inspired by graph kernel Stein statistics (gKSS). What is the main take-away you can describe from AgraSSt that is not present in gKSS?
limitations: Limitations are discussed with respect to the type of interpretations due to multiple-test correction that can affect areas such as personal health. Limitations of the technique presented are also discussed from a methodological perspective in Section 6.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This manuscript proposed a novel statistical procedure coined AgraSSt to assess the quality of implicit graph generators. AgraSSt provides interpretable criticisms for a graph generator training procedure. The manuscript gives theoretical guarantees and provide extensive empirical evaluations.
strengths_and_weaknesses: Strength: The idea of using Stein Statistics to construct rejection region for implicit models that widely presents in the literature is novel. The reviewer believed this idea has further implications that has also been well addressed in the future work part of the manuscript. The extensive empirical evaluation justified that the AgraSST is meritable on the real-world data application. Since the major contribution is the methodology, I believed the theoretical analysis is sufficient.

Weakness: Minor weakness which is discussed in the next section.
questions: How is the consistency of $\widehat q_t$ in theorem 3.2 verified ? The reviewer didn't find out results addressing the algorithm for estimating $\widehat q_t$.
limitations: The author adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The authors propose AgraSSt, a method that can be used to compare graphs generated by (e.g., deep) models to the single reference graph that the model was trained on. The method evaluates a chosen set of graph statistics (e.g., edge density, triangle count) on the generated graphs and compares their statistics with those on the reference graph. The method can reject the null hypothesis that the generated graphs come from the same distribution as the reference graph. 
strengths_and_weaknesses: Strengths:
* The approach proposed by the authors appears to be theoretically well justified, sound, and novel.
* The approach is general-purpose and is not limited to certain types of graph generators.
* The authors study recent deep-learning-based graph generators.

Weaknesses:
* It is not sufficiently clear which graph statistics are used in AgraSSt for which experiments; relatedly, it is not clear how the test could pick up high-level graph features such as power law exponent or the existence of communities.
* The method is only run on synthetic and very small toy-like real-world graphs. Possibly relatedly, there is no mentioning of the computational complexity of their method (or runtimes). This means that the real-world applicability and thus significance of the approach is not clear.
* The method description is quite dense and suffers from mathiness, making it hard to follow at times.
questions: * Eq. (4), what is $t(x_s)$? Should this be $t(x_{-s})$?
* Are there any constraints on what are valid graph statistics to include in AgraSSt?
* In Section 5.2.3, which set of graph statistics was used for the karate club experiments? 

> GraphRNN and NetGAN samples exhibit a single large component rather than two fairly separated communities in the Karate Club network. This difference is picked up by AgraSSt, Deg and TV_deg [...]

I wonder how this difference between a single large component and two mostly separated community is picked up by the models. The statistics in the text (edge count, triangle count, degree statistics, ...) do not seem to be sensitive to such a high-level feature of the graph. 

* Relatedly, (how) do different choices of graph statistics affect AgraSSt's ability to distinguish graphs from a different distribution than the reference graph which are specifically tailored to reproduce specific statistics? For instance, the authors mention that NetGAN produces graphs with similar densities but very different triangle counts compared to the reference graph. How can we be confident that we have not missed important graph statistics?

* The conclusion mentions Appendix E, but there are only appendices up to the letter D in the supplementary material.
limitations: * The authors do not discuss limitations of their method. The most important (potential) limitations I have in mind are:
  * What is the complexity of the approach? What is the typical runtime in practice, depending on the graph size?
  * To rephrase my point from the "questions" section: it appears that the network statistics used by the authors are mostly simple or "low-level" (e.g., number of triangles, edge density). What kind of graphs/ samples cannot be distinguished by the test used in the paper?
review_title: null

Meta-review: metareview: After the author response period, the reviewer ratings were all positive. The reviewers felt that the paper tackles an important problem in assessing the quality of graph generators and proposes a novel, general purpose, and effective approach.

The reviewers pointed out several points for clarification in their reviews, which we hope that the authors will address in the final version of the paper. Many of these have been addressed during the author response period.
confidence: Certain
Decision: Accept