# AgraSSt: Approximate Graph Stein Statistics for Interpretable Assessment of Implicit Graph Generators

arXiv: https://arxiv.org/abs/2203.03673 · HTML: https://mlsanity.com/paper/2203.03673/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 69 references that are in the map.
- First posted on arXiv 7 Mar 2022.

## Builds on (most cited first, 23 of 23)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [NetGAN: Generating Graphs via Random Walks](https://mlsanity.com/paper/1803.00816/) (2018)
- [Learning Deep Kernels for Non-Parametric Two-Sample Tests](https://mlsanity.com/paper/2002.09116/) (2020)
- [Measuring Sample Quality with Stein's Method](https://mlsanity.com/paper/1506.03039/) (2015)
- [Scalable Deep Generative Modeling for Sparse Graphs](https://mlsanity.com/paper/2006.15502/) (2020)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Minimum Stein Discrepancy Estimators](https://mlsanity.com/paper/1906.08283/) (2019)
- [A Linear-Time Kernel Goodness-of-Fit Test](https://mlsanity.com/paper/1705.07673/) (2017)
- [Stochastic Stein Discrepancies](https://mlsanity.com/paper/2007.02857/) (2020)
- [A Wild Bootstrap for Degenerate Kernel Tests](https://mlsanity.com/paper/1408.5404/) (2014)
- [Meta Two-Sample Testing: Learning Kernels for Testing with Limited Data](https://mlsanity.com/paper/2106.07636/) (2021)
- [A Stein Goodness-of-fit Test for Directional Distributions](https://mlsanity.com/paper/2002.06843/) (2020)
- [Interpretable Stein Goodness-of-fit Tests on Riemannian Manifolds](https://mlsanity.com/paper/2103.00895/) (2021)
- [Exponential random graphs behave like mixtures of stochastic block models](https://mlsanity.com/paper/1707.01227/) (2017)
- [Optimal Single Sample Tests for Structured versus Unstructured Network Data](https://mlsanity.com/paper/1802.06186/) (2018)
- [Convergence of Contrastive Divergence Algorithm in Exponential Family](https://mlsanity.com/paper/1603.05729/) (2016)
- [Bayesian exponential random graph models for populations of networks](https://mlsanity.com/paper/2104.05110/) (2021)

## Built on by (most cited first, 3 of 3)

- [On RKHS Choices for Assessing Graph Generators via Kernel Stein Statistics](https://mlsanity.com/paper/2210.05746/) (2022)
- [A Kernelised Stein Statistic for Assessing Implicit Generative Models](https://mlsanity.com/paper/2206.00149/) (2022)
- [SteinGen: Generating Fidelitous and Diverse Graph Samples](https://mlsanity.com/paper/2403.18578/) (2024)

## Abstract (arXiv)

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.