  We propose and analyse a novel statistical procedure, coined AgraSSt, to
assess the quality of graph generators that may not be available in explicit
form. In particular, AgraSSt can be used to determine whether a learnt graph
generating process is capable of generating graphs that 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. Using Stein`s method we give theoretical guarantees for a
broad class of random graph models. 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.
