A Stein Goodness of fit Test for Exponential Random Graph Models

Wenkai Xu, Gesine ReinertarXiv 2021 · DOI · arXiv

Abstract: We propose and analyse a novel nonparametric goodness of fit testing procedure for exchangeable exponential random graph models (ERGMs) when a single network realisation is observed. The test determines how likely it is that the observation is generated from a target unnormalised ERGM density. Our test statistics are derived from a kernel Stein discrepancy, a divergence constructed via Steins method using functions in a reproducing kernel Hilbert space, combined with a discrete Stein operator for ERGMs. The test is a Monte Carlo test based on simulated networks from the target ERGM. We show theoretical properties for the testing procedure for a class of ERGMs. Simulation studies and real network applications are presented.

Introduction

Exponential Random Graph Models (ERGMs) are fundamental tools in social network analysis, used to model how local tie formations—such as transitivity or reciprocity—aggregate into global network structures. However, statistical inference for ERGMs is notoriously difficult due to the intractability of the normalization constant in their probability densities. Furthermore, researchers often face the "N=1" problem, where only a single network realization is available for testing. Traditional goodness-of-fit (GoF) approaches typically rely on comparing a few manually selected summary statistics (e.g., degree distribution), which may fail to detect structural mismatches not captured by those specific metrics.

Methodology

This paper introduces the Graph Kernel Stein Statistic (gKSS), a non-parametric GoF test that bypasses the need for normalization constants by leveraging Stein’s Method. The approach involves two key components:

  1. ERGM Stein Operator: A discrete operator based on Glauber dynamics is defined, examining how the model probability shifts when a single edge is toggled. This allows for a comparison between the observed data and the model without computing the partition function.
  2. Kernel Discrepancy: By applying this operator within a Reproducing Kernel Hilbert Space (RKHS) using graph kernels (such as the Weisfeiler-Lehman kernel), the test can detect complex topological discrepancies.

To ensure scalability for larger networks, the authors propose a randomized version of the test that evaluates a subset of edges (re-sampling size $B$) rather than all possible pairs. The final test is conducted via a Monte Carlo procedure, comparing the observed gKSS against a null distribution generated from MCMC-simulated networks.

Experimental Results

Statistical Power and Scalability

In synthetic benchmarks, the gKSS consistently outperformed traditional summary-statistic-based tests in detecting subtle model perturbations. A critical finding is the relationship between the re-sampling size $B$ and the test's power.

The rejection rate as a function of coefficient perturbation (left) and edge re-sampling size (right).

As illustrated in Figure 1, the gKSS maintains high rejection rates even with relatively small re-sampling sizes, confirming that the randomized approach provides a significant signal while reducing the computational burden.

Computational Efficiency

The efficiency of the gKSS is a major advantage over existing non-parametric methods like Modified Graphical Tests (mGra).

Table comparing execution times (in seconds) for gKSS and competing GoF methods across different network sizes.

As shown in the table above, for a network of size $n=50$, the gKSS with $B=50$ takes approximately 21.54 seconds, whereas the mGraDegree method requires over 5,100 seconds. This orders-of-magnitude improvement makes the gKSS a viable tool for modern, larger-scale network datasets.

Conclusion

The gKSS offers a robust, theoretically grounded, and computationally efficient framework for testing the goodness-of-fit of ERGMs. By moving beyond simple summary statistics and utilizing the power of graph kernels and Stein’s method, it provides a more sensitive diagnostic tool for network modeling. Future research will focus on automated kernel selection and further reducing the reliance on MCMC simulations for the Monte Carlo step.

Summary updated

Abstract

We propose and analyse a novel nonparametric goodness of fit testing procedure for exchangeable exponential random graph models (ERGMs) when a single network realisation is observed. The test determines how likely it is that the observation is generated from a target unnormalised ERGM density. Our test statistics are derived from a kernel Stein discrepancy, a divergence constructed via Steins method using functions in a reproducing kernel Hilbert space, combined with a discrete Stein operator for ERGMs. The test is a Monte Carlo test based on simulated networks from the target ERGM. We show theoretical properties for the testing procedure for a class of ERGMs. Simulation studies and real network applications are presented.
BibTeX
@misc{xu2021stein,
  author = {Wenkai Xu and Gesine Reinert},
  title = {{A Stein Goodness of fit Test for Exponential Random Graph Models}},
  year = {2021},
  eprint = {2103.00580},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.00580},
}
Figure