AgraSSt: Approximate Graph Stein Statistics for Interpretable Assessment of Implicit Graph Generators
Authors: Wenkai Xu
Gesine Reinert
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stein's method
kernel method
synthetic graph generator

Abstract: We propose and analyse a novel statistical procedure, coined AgraSSt, to assess the quality of graph generators which may not be available in explicit forms. In particular, AgraSSt can be used to determine whether a learned graph generating process is capable of generating graphs which resemble a given input graph. Inspired by Stein operators for random graphs, the key idea of AgraSSt is the construction of a kernel discrepancy based on an operator obtained from the graph generator. AgraSSt can provide interpretable criticisms for a graph generator training procedure and help identify reliable sample batches for downstream tasks. We give theoretical guarantees for a broad class of random graph models. Moreover, we provide empirical results on both synthetic input graphs with known graph generation procedures, and real-world input graphs that the state-of-the-art (deep) generative models for graphs are trained on.

AgraSSt: Approximate Graph Stein Statistics for Interpretable Assessment of Implicit Graph Generators
Wenkai Xu Department of Statistics University of Oxford wenkai. xuustats. ox. ac
Gesine Reinert Department of Statistics University of Oxford and Alan Turing Institute re reinert@stats. ox ac uk
Abstract
We propose and analyse novel statistical procedure, coined AgraSSt, to assess the quality of graph generators which may not be available in explicit forms. In particular, AgraSSt can be used to determine whether a learned graph generat- ing process is capable of generating graphs which resemble given input graph. Inspired by Stein operators for random graphs, the key idea of AgraSSt is the construction of kernel discrepancy based generator. AgraSSt can provide interpretable criticisms for a graph generator train- ing procedure and help identify reliable sample batches for downstream tasks. We give theoretical guarantees for a broad class of random graph models. Moreover, we provide empirical results both synthetic input graphs with known graph generation procedures, and real-world input graphs that the state-of-the-art (deep) generative models for graphs are trained on.
operator obtained from the graph
Introduction
Generative models for graphs have received increasing attention in the statistics and machine learning communities. Recently, deep neural networks have been utilised to learn rich representations from graph structures and generate graphs (Dai al. 2020 Li al. 2018 Liao al., 2019 You et al. 2018). However, due to the often opaque deep learning procedures, these deep generative models are usually implicit, which hinders theoretical analysis assess how close the generated samples are in their distributional properties to the graph distribution they are meant to be sampled from.
Learning instead parametric models from explicit pre-specified probability distribution class would allow to use the learned parameters for model assessment. However, parametric models may only capture fraction of the graph features and have restricted modelling power. Parameter estimation can be inconsistent [Shalizi and Rinaldo] [2013] even for well-specified models, and may lead to wrong conclusions in model assessments. Using instead deep generative models for graphs may surpass some of these issues by learning rich graph representations, but methods to assess the quality such implicit graph generators are lacking. In principle, nonparametric hypothesis tests be useful to assess complex models, such as kernel-based tests procedures that utilise functions kernel Hilbert space (RKHS) [Berlinet and Thomas 2004). When the models are described in the form of explicit probabilities, goodness-of-fhe tests [Chwialkowski et al. 2016 Liu et al. 20166] may apply; however, goodness-of-fit testing procedures are generally not applicable for implicit models. Instead, if a large set of samples from the target distribution is observed, one may generate samples from the implicit model and perform a two-sample test such maximum mean discrepancy (MMD)
reproducing
test Gretton et al. 2007] for model assessment Ditkrittum et al,, (007 Xu and Matsuda 2020 2021
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

G
Training Samples
?
generate
Figure 1: Illustration for the assessment task: graph generator G, which learned from training samples, generates set of network samples (vertices in blue), and is assessed against the target graph, which here Padgett's 's Florentine marriage network (with vertices in red labelled as family names).
Yet, in real-world applications, often only a single graph from the target distribution observed (Bresler and Nagaraj 2018 Reinert and Ross 2019]. In this case, the MMD methods for model assessment via two-sample testing procedures cannot be used to assess implicit graph generators. To knowledge, beyond simple Monte Carlo tests with often poor power, principled test is available for assessing the quality of implicit graph generators. Figure illustrates the task: a given graph generator G which is learned from set of training samples can generate samples of user-defined size. The task is to assess whether G can generate samples from the same distribution that generates the observed graph, for example, Padgett's s Florentine marriage network [Padgett and Ansell [993]. The samples in Figure I are generated by Cross-Entropy Low-rank Logit (CELL) model [Rendsburg al. 2020 trained on Padgett's s Florentine marriage network, but any graph generator could be used.
This paper makes three main contributions. (1) We introduce Approximate graph Stein Statistics (AgraSSt) in Section 3] which opens up principled way understand implicit graph generators. AgraSSt is a variant of a kernel Stein discrepancy based on an empirical Stein operator for conditional distributions of general random graph models. The testing procedure is inspired by gKSS, goodness- of-fit testing procedure for explicit exponential random graph models (ERGMs) [Xu and Reinert
2021]. (2) We provide theoretical guarantees for AgraSSt (Section 3). (3) We propose interpretable model criticisms when there is a model misfit, and we identifly representative synthetic sample batches review gKSS. We provide empirical results in Section 3 and discussion in Section 6 Proof details, more background, theoretical and empirical results, and implementation details are found in the Supplementary Information (Sh).The code for the experiments is available at http:///ggataab..oo///naaaall/l/
when the model is good fit (Section 4.. Further, in Section
com wttp/wwwwwaa///ee/ee/eee/aa aeeekkaiil/ggrastt agrasst. http://ooo/ooeaii//aaaaaaaa
2 Backkround: graph kernel Stein statistics
In [uu and Reinert 2021] a goodness-of-fit testing procedure called gKSS for exponential random graph models is introduced, which assumes that only single network may be observed in the sample. As AgraSSt is inspired by gKSS, and gKSS serves as comparison method when the observed network known to be generated from exponential random graph model (ERGM), we briefly review gKSS. The notation introduced in this section is used throughout the paper.
ERGMs are extensively used for social network analysis Wasserman and Faust 1994 Holland and Leinhardt 1981 Frank and Strauss 1986); a special case are Bernoulli random graphs. ERGMs model random graphs via Gibbs measure with respect to chosen set of network statistics, such as number edges, 2-stars, and triangles. Denote by glub, the set of vertex-labeled graphs on n vertices, with N n(n 1)/2 possible undirected edges. Encode
Glah by an ordered collection (z(15)) I<isisnn {0, 1 where (i1) 1 and only if there is an edge between i and j. We denote an (ordered) vertex-pair index = (i.j) j) by E [M] :- {1,.... ........1 N}. Let t (z) count the number of edges in x and let fz(z).... &x (x) count other small graphs on at most vertices in (possibly scaled; for details including a precise definition, Definition/A.3 see AI For 3 (St..... 8x) R and t(x) (t1( .... (x))
of (0, 1)-vllud variables
R* we say that X Glab
follows the exponential random graph model X ~ FRGM((, 1) if for Vo E gleb.
1 (B)
exp Σ Att(())
q(X = x)

---

Here (5) is a normalisation constant. In this model, tg, = 1,...,k, k, are sufficient statistics. Parameter estimation Br for B1 is only possible when the sufficient statistics are specified priori; SI for estimation details. In modern graph learning procedures, e.g. deep generative learning, the sufficient statistics to of T may not be obtained explicitly.
In [Reinert and Ross 2019] the exponential random graph distribution in Eq. ① is characterised by so-called Stein operalor, as follows. Let E 10, be vector with in coordinate
and O in all others; x(8.1) x + (1 Jz)e, has the s-entry replaced of x by the value 1, and (5.00) = IzC, has the s-entry of z replaced by the value O; moreover, -- is the set of edge indicators with entry removed. For function h {0, 1 + R, let A,h(x) h(z(s:))-A(((6.))) Set qx (x((:)) -),) = P(X* 1|X_, = x x_... Define the operator
As, N
Σ M(s), 1 g(x (..)).)()) + - (2) =E[N]
Then under mild conditions Reinert and Ross 2019
show that if Ep(Ag,1]] 0 for all smooth test functions f. then p must be the distribution of ERGM t). Thus, this operator characterises ERGM(3, t). For the derivation of AgraSSt it is of interest to see how this operator is obtained. is indeed the generator of so-called Glauber Markov chain Glab with transition probabilities
P(x (()))) N P(x (((00)) N 'xx (z.(5.))(zr)) (zr).
With the ERGM Stein operator in Eq. 2 and rich-enough RKHS test function class H. Xu and Reinert 2021 propose a graph kernel Stein statistics (gKSS) to perform goodness-of-fi testing on an explicil ERGM when a single network sample is observed. With the summand components in ( the Stein operator can be seen as taking expectation over vertex-pair variables S E [N] with uniform probability (SS- = s) = N independently of x, namely
(z) = Σ
P(S = s) f(x) =: EsTA f(x]]
.E[N]
For a fixed graph gKSS is defined as
g gKSS(
sup |
[ [w))]
where the function f is chosen to best distinguish q from z. For an RKHS associated with kernel K, by the reproducing property of H. the squared version of gKSS admits quadratic form representation gKSS* (q; = (As( K(r, )), [A,
(5) K (xx, )]), which be computed readily.
More background can be found in B.2
3 AgraSSt: Approximate Graph Stein Statistic
An implicit graph generator may not admit probability distribution in the form of Eq.(). However, the idea of constructing Stein operators based on Glauber dynamics using conditional probability distribution for ERGM serves motivation for us propose Stein operators for conditional graph distributions, to facilitate an (approximate) characterisation for implicit random graph models.
3.1 Stein operators for conditional graph distributions
Let (xr) P(X- .r) be any distribution with support glab Let t(x) denote a statistic on graphs which takes on finitely many values & and let (x) = P(X = x|((x) = k). We assume that (x())) > 0 for all & under consideration. For generic outcome we write qt- We introduce a Markov chain on glub which transitions from (s..1) with probability
(()()))))
((x_)) p(X* 1|((=_))) =: gr (2)(112)),
and which transitions from to (=.0) with probability (1(((..001((x=00)))))) =1 -2((x(6.1) no other transitions occur. Let
f f(x) = (((((())) + (z())) )((((1)))) - -f(x).
(5)
3

---

Algorithm Estimating the conditional probability
Input: Graph generator G; statistics t(z);
Procedure:
Generate samples fæ1...., #L from G.
2: For s E [N]. E [n], let n,,k be the number of graphs zi E [L], in which s is present and t(x-a)=
3: Estimate the conditional probability of the edge being present conditional on ((x-s) = k: by an estimator ge (s; k), using a look-up table or smoothing.
Output: ge k) that estimates q(x(()= [[((=_)) k).
For an ERGM, {(x) could taken as a sufficient vector of statistics but here we do not assume parametric network model q(x), and t(x) does not have to be sufficient statistics for q(x).
Recall that operator is Stein operator for a distribution μ if its expectation under μ is zero. The following result provides a theoretical foundation for AgraSSt and is proven in SI
Lemma 3.1. If (x)) for all l. then q,== is Stein operator for the conditional distribution of X given t(X) = K. and Σ. t(X) = k.
(1) g.1=k is a Stein operator for the conditional distribution of X given
Intuitively, if the distribution of X is close to that of X, then with Y== denoting the corresponding random graph with distribution that of X given t(X) k. it should hold that ( x O. In this way the Stein operator in Eq. (5 can be used to assess similarity between distributions.
In particular, Eq [4 ل
3.2 Approximate Stein operators
For implicit models and graph generators G, the Stein operator Agg in Eq.45) cannot be obtained without explicit knowledge of qe (z((.)))) However, given a large number for samples from the graph generator G, the conditional edge probabilities ge (x((1)) can be estimated. Here we denote by (1x(11)) an estimate of qo (1((e.1)); some estimators will suggested Section 3.3
AgraSSt performs model assessment using an operator which approximates the Stein operator (s) We define the approximate Stein operator for the conditional random graph by
4.t"
( J = (z(1).)))) (adl).))(((()))))) (z. + qe (a. [() f(x).
(6)
The vertex-pair averaged approximate Stein operator is 1
AqaS(x) N fz)
Σ (3)
SEIN]
3.3 Estimation with chosen statistics on graphs
Using the Stein operator for conditional graph distributions, we can obtain the approximate Stein operators in Eq. (6) and Eq. (7) for an implicit graph generator G by estimating qe (x(1.))), Here t(x) are user-defined statistics. In principle, any multivariate statistic t(x) can be used in this formalism. However, estimating the conditional probabilities using relative frequencies can be computationally prohibitive when the graphs are very large and specific frequencies are rarely observed. Instead, here we consider simple summary statisties, such as edge density, degree statistics or the number of neighbours connected to both vertices s. The estimation procedure presented in Algorithm T
To estimate qe (x.1) in Step 3 of Algorithm a look-up table can be used: If (x) is possibly multivariate statistic with a discrete number of outcomes, generate many independent copies from the
When conditioning on the sufficient statistics, for ERGMs the resulting Stein operator allows to establish elegant approximation results (Bresler and Nagaraj 2019 Reinert and Ross 2019

---

synthetic graph generator, and count n(k, s), the number of times that vertex-paie pair is present in the simulated graphs and + k. Consistency follows from the law of large numbers. When using smoothing to estimate the conditional probability, consistency will depend on the smoothing method. If the underlying graph has exchangeable edge indicators then (e(x(x.1) does not depend on the choice of vertex-pail Then we set set n2k) E. nlk, s), and Ng- Ei= ((tr=.)) k); if t & estimate ge (2(1))))) by
9: (k) = 7 Ng
1N 2 1).
(8)
If kmin kmaz denote the minimum and maximum values of statistics from simulated graph samples, then for k outside this set, the lookup table estimator Eq. is set to estimate g(k) = 0
If the underlying graph cannot be assumed to have exchangeable edge indicators if the statistic t is high dimensional, then any particular ( s) may not be observed very often. In such a situation we can learn ğe (s; k) using kernel ridge regression so that the conditional probabilities for similar (xx-s) are predicted provide alternative, smoother estimate for the conditional probabilities.
smooth manner. Estimating (((x,)) I k) instead of [[==]((x-s))) = k) may
The next result shows that the approximate Stein operator achieves the Stein identity asymptotically. For this result, which is proved in S we use the notation || suP. [|),
Theorem 3.2. Assume qe (x(()))) is consistent estimator for q: (x(x.1) L + Then for any such that A < oo we have Eg[Ag.((x)) + [z(A = as oc.
Proofs and additional analysis are included in SI Proposition A. in SI addresses consistent
estimation of T and
refined results for ERGMs, including a Gaussian approximation.
3.4
AgraSSt for implicit graph generators
The estimated conditional probabilities give approximate Stein operator for E5. With the appropriately defined Stein operator from an implicit model given in (6) we can define AgraSSt, kernel-based statistic analogous to gKSS in Eq. 3
AgraSSt Ag
sup |!
N
N
Σ
In S we prove the following result for edge- excehanhcaeeebee graphs, that is, graphs in which all permutations of the edge indicators have the same distribution.
Theorem 3.3. If the graph is edge-exchangeable, then AgraSSi 2 (7, 13 x)) is consistent estimator of
gKSS = N
Σ S.
(A ), A4. K K(.z))
Re-sampling Stein statistic A computationally efficient operator for large N can be derived via
re- sampling B vertex-paine sb. b 1...., B, from ( ..) chosen uniformly with replacement, independent of each other and of x. This procedure gives rise to a randomised operator; this re-sampled operator is
An.f(z) = 1
Σ bE[B]
(0) f(z). qa
where the expectation of A (x) with respect to re-sampling is
E Es4 f(x) (z)
The corresponding re-sampled AgraSSt statistic is
AgraSSt (1,1 1;
sup
Σ
A ( f(x)
B
11
be
5

---

Algorithm 2 Assessment procedures for graph generators
Input: Observed graph æ; graph generator G and generated sample size L; estimation statistic RKHS kernel K; re-sampling size B; number of simulated graphs m; confidence level or;
Procedure:
1: Estimate (( (((=))) based on Algorithm
2: Uniformly generate re-sampling index ( 8n3 from [N] with replacement.
2
3: Compute AgraSSt (Ø: x)) in Eq.(TO).
4: Simulate (z)..... zm from G.
5: Compute AgraSSt (0: z4) in Eq. 10
6: Estimate empirical quantile "1- via (T...... J
Output: Reject the null if 71-ai otherwise do not reject.
Similar to Eq. 9). the squared version of AgraSSt admits representation in quadratic form,
AgraSSt (G.t:)) B-2
Σ 6.EE[B]
(10)
where (') (4 (( A
1 ((,x)) We note that the randomised operator obtained
via re-sampling is form of stochastic Stein discrepancy introduced in Gorham et al. 20200
For fixed x, under mild conditions the consistency of AgraSSt 2 (7, 4; x) as B + oc: is ensured by the following normal approximation, which follows from Proposition in Xu and Reinert [202T]
Proposition 3.4. Assume that (s, s') in (T0 is bounded and that AgraSSt (ū. t; x) has non-zero variance o². Let Z be a normal variable with mean AgraSSt( t; x) and variance σ², Then there exists an explicitly computable constant C >> 0 such that for all 3 times continuously differentiable functions g with bounded derivatives up to order 3,
Elg( (A((ArraSS((7 (7,4) - 9(2) S CC/B.
4
Applications of AgraSSt
4.1 Assessing graph generators
AgraSSt measures the distributional difference between the underlying distribution of an implicit graph generator G' and observed graph x, in order assess the quality of the generator G. The hypothesis testing procedure for the null hypothesis that the observed graph æ comes from the same distribution that generates the samples, against the general alternative, is shown in Algorithm 2 We emphasise two features of this procedure. Firstly, for given generator G, AgraSSt directly assesses the quality of the implicit model represented via samples from G. Secondly, the generator G' can be trained on the observed graph æ, for example through a deep neural network generator. By learning deep neural network generator with training samples from the same distribution that generate æ,, AgraSSt can assess the quality of the training procedure, i.e. whether the deep neural network is capable of learning the desired distributions. Additional details discussed in SI
4.2 Interpreting trained graph generators
If the procedure in Algorithm 2 rejects the null hypothesis, the generator may not be suitable for generating samples from the distribution that generates the one observed graph. Hence, understanding where the misfit comes from can be very useful, especially for models trained from black-box deep neural networks. AgraSSt provides an interpretable model criticism by comparing the learned Te (x..))) with the underlying qe (x.(1))) when available, such as in synthetic experiments from specified ERGM. Such an interpretation can be also useful to re-calibrate training procedures.
4.3 Identifying reliable graph samples
If the procedure in Algorithm 2 does not reject the null hypothesis, there not enough evidence to reject the hypothesis that the generator is capable of generating graphs that resembles the observed

---

graph. If a generator G has passed this hurdle then it can be recommended for generating graph samples of the desired type. AgraSSt can also be put use for the task of sample batch selection. In many scientific studies, only a small batch of representative graph samples may need to be generated for downstream tasks such as privacy-preservin
methods where users only access a small number of graph data, or randomised experimental design for community interaction. To quantify the quality of sample batches via p- p-values: (1) we generate a sample batch size m, say; (2) we perform the steps in Procedure from Algorithm 2 (3) we compute the p-value m -2
Zimt 1(r >> Ti), with r as in step 3 and (TI...., Jm as in step 5, If the p-value is smaller than a pre-specified threshold, we generate another sample batch; otherwise accept the current sample batch.
5 Empirical results
We first illustrate the performance of AgraSSt on synthetic data, where the null distribution is known and we have control of the set-up; in particular we can illustrate the use of AgraSSt for interpretable model criticism. Then we show the performance AgraSSt on real-world data application to assess graph generators trained via various deep generative models.
5.1 Synthetic experiments
Only few competing approaches are available for our task and many of them are devised specifically for ERGMs. Hence here we use an ERGM, namely the Edgee2Sttar-Tiane (E2ST) model with
((x)
x exp (8) Ex(x)) + (252(x)) + (xT,
(11)
where Ex(x) denotes the number of edges of x, S2(z) denotes the 2-Star statistics and T, (z) denotes the triangle statistics. The parameter vector 3 (-200,, 0.00, 0.01) is chosen as the null model. while alternative models are constructed by perturbing the coefficient 82 in Yang al. [0018] Xu
and Reinert 2021]. This particular type of ERGM is chosen because it is the currently most complex ERGM for which a thorough theoretical analysis for parameter estimation is available, see Mukherjee
and Xu 2013
5.1.1
Related approaches for comparisons
To assess the performance of AgraSSt, we consider the following test statistics which are either tailored or modified to perform assessment for implicit graph generators:
Deg is degree- based statistics for goodness-of-fir test of exchangeable random graphs [Ouadah et al.] 2020] based on the estimated variance of the degree distribution. The statistics can be obtained from empirical degrees from samples generated from the implicit model.
TV
deg denotes the Total- Variation (TV) distance between degree distributions, |unntr 2008) proposes a simulation-based approach to construct graphical goodness-of-fh
et al.
tests.
Xu and Reinert (202T) quantifies this approach using the total- variation distance
between the distributions of chosen network statistics; see SD.4 details.
MDdeg is the Mahalanobis distance between degree distributions 2019
Lospinoso and Snijders
In the synthetic experiment where the parametric model is known (Eq. IT).. the coefficients 3 are estimated from generated samples for model assessment provide baseline approach, denoted by Param. Details can be found in BI Knowing the explicit null model in the synthetic setting, we can also compute gKSS in Eq. 33) denoted by Exact our benchmark. The Weisfeiler-Lehmal
graph kernel [Shervashidze et al. 2011 with height parameter 3 is used for kernel-base approaches.
5.1.2 Simulation results
The rejection rates for various settings are shown in Figure 2 (edge density 11.2%), the sparser alternatives are much harder to distinguish while the denser ones are
As the null model relatively sparse
'The model also satisties conditions in Theorem 1.7 in Reinert and Ross 2019 where theoretical properties studied.
7

---

Dag Agr Marum E-ASt
21. diga-10
Rejjection fion Hater
Relection Pate
Sunr pesihuia
deggm122
Jagdleo
Rejection
Cam
Txnet
-2a
-25
-GA
-64
30
-A1 00
-M1
-0.3
61
Perturb 25tar Confiicient
Perturb 25tar Coefficient
Pertusb 25tar Coefficient
(a) Different assessment approaches (b) AgraSSt: different estimations
(c) AgraSSt with re-sampling
Figure 2: Synthetic experiment on the E2ST model in Eq. with B2 varying on the æ-axis: 100 trials: 0.05; 1000. Abbreviations as in Section 5.1
easier problems. Figure 2(a) compares the AgraSSt procedure with the approaches from Section 5.1.1 shows that AgraSSt performs competitively to the benchmark Exact, which is only available when the model is known explicitly, and outperforms other assessment procedures for implicit models. TV deg is slightly less powerful than AgraSSt but outperforms Deg. For sparser alternatives (smaller (2). MDdeg and Param have much lower rejection rate and thus are less powerful. In Figure 2(b) we compare the performance of AgraSSt using different estimation methods for qr (x) the degree deg(k) k) of vertex & calculated excluding the vertex-pair s = (i.j). The estimation methods are
Sum_ deg: for s = (1, we set 1 = deg(i) + deg(i):
Cum deg: the cumulative distribution function of sum of degrees are used;
Bi deg: for (i, the 2-dimensional vector (deg(t), deg(j)) is used;
Edges: t is the edge density after removing vertex-pair
From the results, we see that Edges outperforms the other estimates, which echos the theoretical results shown in Theorem A.5 in SI, as the coefficient 3 for E2ST satisfies its assumptions. Hence this is the statistics which is used in our real-world experiments, with an exception of SI.D.3. We also see that using both vertex degrees as 2d vector predicts substantially better than using predictors based on sum of degrees of two vertices. In Figure 2[c) the comparison with re-sampg is shown. With increase in re-sampling size, the power of AgraSSt increases.
5.2 Real-world applications on deep graph generators
We now assess the performances of set of lfte-of-theeart deep generative models for graphs trained on ERGMs and the Karate Club network collected by Zachary 1977]. The Karate Club network has 34 vertices and 78 edges representing friendships. Soon after the data collection the Karate Club separated into two factions. This graph is benchmark graph for community detection. One would not expect this graph be close to G(n, pi graph to be well modelled by ERGM.
5.2.1 Graph generation methods
The graph generation methods to which we apply AgraSSt are the following.
GraphRNN You et al. 2018 is an architccture to generate graphs from learning two recurrent neural networks (RNN), one a vertex-level RNN and the other an edge-level RNN. for vertex ordering; two RNNs trained
The procedure starts from a from a sequential procedure.
NetGAN (Bojchevski et al. between a generator and a discrimiiatoo neural network on graph data.
2018 utilises adversarial approach by training interplay
CELL [Rendsburg et al. 2020) improves on the NetGAN idea by solving a low-rank approximation problem based on a cross-entropy objective.
MC is the standard Monte-Carlo network sampling in the ergm suite in and is used as baseline when the simulated network is known follow the model in Eq. I q(x:) needs to be known.
Bernoulli random graph of size n, edge probability p E [0, 1].

---

5.2.2 Generator assessment results
We first train the generative models with samples from ERGMs to assess their abil- ity to generate ERGMs. The test results are shown in [ From the result, see that for the "reliable" MC genera- tor all the assessment statistics presented have well-controleed type-I error. Samples generated from CELL deviate not too far from the test level, indicating good gen- erative model for ERGMs. NetGAN and GraphRNN both encounter high rejec- tion rate, implying that the generated sam- ples that are close the training E2ST model.
AgraSSt
Deg
MDdeg
TV_deg
GraphRNN
0.42
0.02
0.04
0.27
NetGAN
0.81
0.13
0,61
0.54
CELL
0.05
0.06
0.09
0.12
MC
0.04
0.03
0.02
0.09
Table 1: Rejection rates on various assessment ap- proaches, with L 1000; 200 samples to simulate the null; 100 trials; = 0.05. The higher the rejection rate, the worse the model fit. MC is the baseline.
From the density based AgraSSt, taking G(n, g) model, can interpret the model misfit by checking the estimated q. For the true E2ST model used to generate training samples. we have 0.112, while CELL has q 0.116 which is close the null. GraphRNN estimates q 0.128 which is substantially higher than the null. Although GraphRNN can be powerful in learning local patterns and structures for neighbourhoods (You al. 2018 here it does not take the overall density sufficiently into account. Due to its limited "look back" and absence of "look forward" on the ordered vertex during training, the over-generation of edges may have caused this significant difference for learning ERGMs. NetGAN, on the other hand, produces a close estimate q = 0.106. However, counting triangles. it only has on average 12.6 triangles which is far less from the null with expected number of triangles 46.3. NetGAN, due to its random walk ad adversarial procedure, may not be effective in learning such clustered patterns.
5.2.3 Case study: Karate Club network
Next, we assess the performances of these generative models by training on the Karate Club network (Zachary] [977]. The p- values for different testing procedures are shown in Table From the results, we see that AgraSSt rejects samples generated from both GraphRNN and NetGAN trained with the Karate Club network. Although the edge densities generated from the trained GraphRNN (edge density 15.3%) and NetGAN (edge density 13.4%) are comparable with the Karate Club edge density of 13.9%, vi- sual inspection indicates that both GraphRNN and NetGAN samples exhibit single large component rather than two fairly separated communities the Karate Club network. This difference is picked up by AgraSSt, Deg and TV_deg which all reject both models. On the other hand, CELL generates samples that are not rejected by all tests at significance level a = 0.05. In Figure in the SI, the Karate Club network is shown in Figure 5(a) Samples from GraphRNN, NetGAN and CELL
AgraSSt
Deg
MDdeg
TV_deg
GraphRNN NetGAN CELL
0.00
0.01
0.15
0.00
0.00
0.02
0.59
0.00
0.34
0.09
0.17
0.61
Table 2: p-values for models trained on the Karate Club network; 100 samples to simulate the null distribution; rejection at a 0.05 is marked red.
shown in Figure (()) [(c) and 5(d) respeettviy.
SI D includes additional results, including on efficiency, and visualisations. A second case study
the Florentine marriage network from Padgett and Ansell [993)- is presented in D.2 additional visualisations of the reliable sample batch selection procedure described in Section 4.3 are also given.
Discussions and future directions
In this paper, we propose AgraSSt, a unique general purpose model assessment and criticism procedure for implicit random graph models. As it is based on a kernel Stein statistic, we are able to give theoretical guarantees. AgraSSt not only solves an important problem but also opens up whole set of follow-up research problems of which we list a few here. applied to undirected and unweighted graphs. Extensions to more general graphs well as to time
(i). Currently AgraSSt is only

---

series of graphs will be interesting to explore in follow-up up work. (ii). AgraSSt could be also helpful improve design and training of deep graph generative models, e.g. by regularising graph features there is misfit. (iii). ERGMs allow for exogenous features to be included in the sufficient statistics. AgraSSt can be based on a variety of statistics f(z:;; further examples are found in SI D.3 would also be possible to incorporate exogenous features in the statistics f(x)) in AgraSSt, for example using ideas from graph attention networks [Veličković et al. 2018]. Exploring this idea in more detail will
be another topic of further research.
As AgraSSt depends on the chosen summary statistic t(x). results have be interpreted with regards to the respective conditional distributions. Also multiple tests will have the p-values to be adjusted to avoid misinterpretation of tests, which could have serious consequences for example in the area of personal health. Investigating the effect of choice of tzz) will be part of future work.
Acknowledgements
The authors thank the anonymous reviewers for their constructive comments and suggestions to improve the paper. G.R. and W.X. acknowledges the support from EPSRC grant EP/T018445/1. G.R also supported in part by EPSRC grants EP/W037211/1, EP/V056883/1, and EP//018472/1.
References
Alessandro Barp, Francois-Xavice Briol, Andrew Duncan, Mark Girolami, and Lester Mackey. Minimum Stein discrepancy estimators. In Advances in Neural Information Processing Systems, pages 129666 2019.
Alain Berlinet and Christine Thomas. Reproducing Kernel Hilbert Spaces in Probability and Statistics. Kluwer Academic Publishers, 2004.
Julian Besag. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society: Series D (The Statistician), 24(3):179-199) 1975.
Shankar Bhamidi, Guy Bresler, and Allan Sly. Mixing time of exponential random graphs. The Annals of Applied Probability, 21(6):2146-2177) 2011.
Aleksandar Bojchevski, Oleksandr Shchur, Daniel Zügner, and Stephan Günnemann. NetGAN: Generating graphs via random walks. In International Conference on Machine Learning, pages 610-619. PMLR, 2018.
Guy Bresler and Dheeraj Nagaraj. Optimal single sample tests for structured versus unstructured network data. In Conference On Learning Theory, pages 1657-1690. PMLR, 2018.
Guy Bresler and Dheeraj Nagaraj. Stein's method for stationary distributions of Markov chains and application to Ising models. The Annals of Applied Probability, 29 2019.
Sourav Chatterjee and Persi Diaconis. Estimating and understanding exponential random graph models. The Annals of Statistics, 41(5):2428-246) 2013.
Kacper Chwialkowski, Heiko Strathmann, and Arthur Gretton. A kernel test of goodness of fit. In International Conference on Machine Learning, pages 2606-2615. PMLR, 2016.
Kacper P Chwialkowski, Dino Sejdinovic, and Arthur Gretton. A wild bootstrap for degenerate kernel tests. Advances in Neural Information Processing Systems, pages
2014.
Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International Conference Machine Learning, pages 2302-2312 PMLR. 2020.
Ronen Eldan and Renan Gross. Exponential random graphs behave like mixtures of stochastic block models. The Annals of Applied Probability, 286))3368-3375, 2018.
Ove Frank and David Strauss. Markov graphs. Journal of the American Statistical Association, 81 832-8223 1986.
10

---

Jackson Gorham and Lester Mackey. Measuring sample quality with Stein's method. In Advances in Neural Information Processing Systems, pages 226-234, 2015.
Jackson Gorham, Anant Raj, and Lester Mackey. Stochastic Stein discrepancies. Advances in Neural Information Processing Systems, 33:17931 1S:11711--79443 2020.
Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex J Smola. A kemnll method for the wwo-samlee-robblm. In Advances in Neural Information Processing Systems, pages 513-520, 2007.
Arthur Gretton, Dino Sejdinovic. Hciko 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, pages 1205-1213, 2012.
Geoffrey E Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14(8):1771-1800, 2002.
Paul W Holland and Samuel Leinhardt. An exponential family of probability distributions for directed graphs. Journal of the American Statistical Association, 76(373):33-50, 1981.
David R Hunter and Mark Handcock. Inference in curved exponential family models for networks.
Journal of Computational and Graphical Statistics, 15(3):565-583 2006.
David R Hunter, Steven M Goodreau, and Mark S Handcock. Goodness of fit of social network models. Journal of the American Statistical Association, (03(481):248822) -28-258, 2008
Aapo Hyvärinen. Estimation of non- normaazma statistical models by score matching. Journal of Machine Learning Research, 6(Apr):695 7000-,-77-00000 2005.
Aapo Hyvärinen. Consistency of pseudolikelihood estimation of fully visible Boltzmann machines.
Neural Computation, 18(10):2283- 2292, 2006.
Bai Jiang, Tung- Yu Wu, Yifan Jin, and Wing H Wong. Convergence of contrastive divergence algorithm in exponential family. The Annals of Statistics, 46(6A):3067-3098 2018
Wittawat Jitkrittum, Zoltán Szabó, Kacper P Chwialkowski, and Arthur Gretton. Interpretable distribution features with maximum testing power. Advances in Neural Information Processing Systems, pages 181-189, 2016.
Wittawat Jitkrittum, Wenkai Xu, Zoltán Szabó, Kenji Fukumizu, and Arthur Gretton. A linear-time kernel goodness-offff test. In Advances in Neural Information Processing Systems, pages 262-271, 2017.
Christophe Ley, Gesine Reinert, and Yvik Swan. Stein's method for comparison of univariate distributions. Probability Surveys, 14:1-52, 2017.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 1XXiv:8803.03324 2018.
Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Ffficientt graph generation with graph recurrent attention networks. Advances in Neural Information Processing Systems, 32:4255-4266 2019.
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J Sutherland. Learning deep kemelss for non-paree parameerriic two-sample tests. In International Conference on Machine Learning, pages 6316-6326 PMLR, 2020.
Feng Liu. Wenkai Xu, Jie Lu, and Danica Sutherland. Meta two-sample testing: Learning kernels for testing with limited data. Advances in Neural Information Processing Systems, 34, 2021.
Qiang Liu, Jason Lee, and Michael Jordan. A kemelized Stein discrepancy for goodness-of- fit tests. In International Conference on Machine Learning, pages 276-284, 2016.
Josh Lospinoso and Tom AB Snijders. Goodness of fit for stochastic actor-oriented models. Method- ological Innovations, 1213)2059979911988822,, 2019.

---

Guillaume Mijoule, Gesine Reinert, and Yvik Swan. Stein's 's density method for multivariate continu- ous distributions. arXiv preprint 100009200..0009,, 2021.
Sumit Mukherjee and Yuanzhe Xu. Statistics of the two-star ERGM. arXiv preprint arXiv: 1500,456, 2013.
Sarah Ouadah, Stéphane Robin, and Pierre Latouche. Degree-based goodness-of of-fit tests for hetero- geneous random graph models: Independent and exchangeable cases. Scandinavian Journal of Statistics, (7(1):156-181) 2020.
John Padgett and Christopher K Ansell. Robust Action and the Rise of the Medici, 1400-1434.
American Journal of Sociology, 98()):125-1131, 1993.
Gesine Reinert and Nathan Ross. Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs. The Annals of Applied Probability, 29 (5):3201-322) 2019.
Luca Rendsburg. Holger Heidrich, and Ulrike Von Luxburg. NetGAN without GAN: From random walks to low-rank approximations. In Proceedings of the 37th International Conference on Machine Learning, pages 8073-8082. PMLR, 2020.
Christian S Schmid and Bruce Desmarais. Exponential random graph models with big networks: Maximum pseudolikelihood estimation and the parametric bootstrap. In 2017 IEEE International Conference on Big Data, pages 116-121. IEEE, 2017.
Cosma Rohilla Shalizi and Alessandro Rinaldo. Consistency under sampling of exponential random graph models. Annals of Statistics, 41())5508, 2013.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhom, and Karsten M Borgwardt. Weisfeiler-Lehman graph kernels. Journal of Machine Learning Research, 12(Sep):
2539-2561, 2011.
Tom AB Snijders. Markov chain Monte Carlo estimation of exponential random graph models. Journal of Social Structure, 3(2):1-40, 2002.
David Strauss and Michael Ikeda. Pseudolikelihood estimation for social networks. Journal of the American Statistical Association, 85(409):204-211 212, 1990.
Marijtje AJ Van Duijn, Krista J Gile, and Mark Handcock. framework for the comparison of maximum pseudo-likelihood and maximum likelihood estimation of exponential family random graph models. Social Networks, (2())522-6,, 2009.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Stanley Wasserman and Katherine Faust, Social Network Analysis: Methods and Applications, volume 8. Cambridge University Press, 1994.
Wenkai Xu and Takeru Matsuda. Stein goodness-of-fit test for directional distributions. Interna- tional Conference on Artificial Intelligence and Statistics, 2020.
Wenkai Xu and Takeru Matsuda. Interpretable Stein goodness-of of-fit tests on Riemannian manifolds. International Conference Machine Learning, 2021.
Wenkai Xu and Gesine Reinert. A Stein goodness-of-test for exponential random graph models. In International Conference Artificial Intelligence and Statistics, pages 415-423. PMLR, 2021.
Jiasen Yang, Qiang Liu, Vinayak Rao, and Jennifer Neville. Goodness-of-fe testing for discrete distributions via Stein discrepancy. In International Conference on Machine Learning, pages 5557-5566, 2018
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep ruto-regressive models. In International conference on machine learning, pages 5708-5717, 5777. PMLR, 2018
Wayne W Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452-473 1977.
12


Reviews:
[{"review_id": "ibgVt685XYH", "reviewer": "Reviewer_dJCC", "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. ", "questions": "Using graph statistics to define AgraSSt provides flexibility. However, how can this technique provide adequate assessment for graph communities? \nThese are statistics that many degrees of freedom not easily solved by techniques driven by graph-statistics. How can AgraSSt deal with this situations?\n\nMore 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.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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:\n\nStrengths:\nThe 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.\nThe theoretical analysis seems sound and can justify the consistency of the AgraSSt estimator.\nThe 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. \n\n\nWeaknesses:\nThe 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? \nThe 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.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "QKw0HJdtvsj", "reviewer": "Reviewer_QFs7", "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. ", "questions": "* Eq. (4), what is $t(x_s)$? Should this be $t(x_{-s})$?\n* Are there any constraints on what are valid graph statistics to include in AgraSSt?\n* In Section 5.2.3, which set of graph statistics was used for the karate club experiments? \n\n> 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 [...]\n\nI 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. \n\n* 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?\n\n* 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:\n  * What is the complexity of the approach? What is the typical runtime in practice, depending on the graph size?\n  * 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?", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The approach proposed by the authors appears to be theoretically well justified, sound, and novel.\n* The approach is general-purpose and is not limited to certain types of graph generators.\n* The authors study recent deep-learning-based graph generators.\n\nWeaknesses:\n* 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.\n* 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.\n* The method description is quite dense and suffers from mathiness, making it hard to follow at times.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2t35BwGFuOT", "reviewer": "Reviewer_MKcL", "summary": "This paper proposes a novel statistical procedure to evaluate and interpret implicit graph generators based on approximate graph Stein statistics.", "questions": "Questions:\n\n- What is the effect of $\\beta_2$ (equation (11)) in sparsity? Does sparsity grow or decrease from left to right in Figures 1a-1c?\n- How was the hyperparameter selection done for the GraphRNN, NetGAN, and CELL in Table 1?\n\nMinor comments:\n\n- Typo in line 72 (comma before For).\n- 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, ...\").\n- 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.\n- Line 162 should be an equation.\n- Better explain the axes of Figures 1a-1c.\n- Include a more precise description of the key (colors) of Figure 1c.\n", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- 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. \n- The numerical results comparing AggraSSt with other methods are convincing, and show that AgraSST outperforms them empirically.\n\nWeaknesses:\n\n- 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.\n- 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?\n- 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)$).", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-hMkth2m_ij", "reviewer": "Reviewer_Rhfm", "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.", "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.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nWeakness: Minor weakness which is discussed in the next section.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept