Abstract
Traditional inference for Exponential Random Graph Models (ERGMs), or $p^*$ models, is often hindered by the intractable normalizing constant and the instability of simulation-based methods. This paper presents two deterministic alternatives: Maximum Block-Pseudolikelihood (MBPLE) and the Relaxed Dependence Approximation (RDA). By utilizing a grid-based Bayesian framework, these methods provide stable, accurate parameter estimates and facilitate model selection without the computational burden or degeneracy risks associated with Markov chain Monte Carlo (MCMC) techniques.
Introduction
In the study of social networks, $p^*$ models are essential for identifying the structural drivers of tie formation, such as reciprocity, transitivity (triangles), and popularity (stars). Despite their utility, these models face a significant mathematical challenge: the likelihood function includes a normalizing constant that requires summing over all possible graph configurations. For a network with $m$ nodes, this involves $2^{m(m-1)/2}$ states, a number that becomes computationally impossible even for small networks.
Historically, researchers have turned to Pseudolikelihood (MPLE) or Monte Carlo Maximum Likelihood Estimation (MC-MLE). While MPLE is fast, it often yields biased estimates by assuming edge independence. Conversely, MC-MLE is more accurate but prone to "model degeneracy"—a state where simulations produce only extreme (empty or full) graphs—making it difficult to tune and apply reliably.
Methodology
The authors propose a deterministic Bayesian approach that bypasses MCMC entirely. Given that most $p^*$ models involve a limited number of parameters (typically $\le 5$), the posterior distribution can be evaluated over a fine grid in the parameter space. The core innovation lies in two new likelihood approximations:
- Maximum Block-Pseudolikelihood (MBPLE): This method extends standard pseudolikelihood by partitioning edges into "blocks" of up to 20 dyads. By calculating the conditional probability of these blocks rather than individual edges, MBPLE captures more complex dependencies within the network.
- Relaxed Dependence Approximation (RDA): This approach further refines the joint distribution approximation by relaxing specific dependencies, offering a more flexible alternative to MBPLE.
These approximations allow for the direct calculation of posterior means, variances, and marginal likelihoods from the grid, enabling robust Bayesian model comparison.
Datasets and Experimental Setup
The proposed methods were validated using two benchmark social network datasets: the Molecule Dataset (20 nodes) and the Karate Club Graph (34 nodes).
Key Insights and Results
A primary finding of the study is the "Block Advantage." As the block size in MBPLE and RDA increases, the resulting parameter estimates converge toward those produced by the computationally intensive MC-MLE "gold standard."
Accuracy and Stability
Both RDA and MBPLE provided estimates significantly more accurate than standard MPLE. Crucially, these methods remained stable even in the larger Karate Club graph, where traditional simulation-based methods often fail due to degeneracy. Parameters derived from these deterministic methods produced realistic simulated graphs, confirming their inferential validity.
Model Selection
The grid-based approach facilitates the calculation of marginal likelihoods, allowing for formal Bayesian model choice. In both the Molecule and Karate Club datasets, "saturated" models—those incorporating all considered structural statistics—were found to have the highest posterior probabilities (0.64 and 0.705, respectively).
Conclusion
MBPLE and RDA offer a powerful middle ground between the speed of pseudolikelihood and the accuracy of simulation-based MLE. By providing a stable, deterministic path for Bayesian inference, these methods allow researchers to analyze network structures more reliably. While the grid-based approach is currently limited by the "curse of dimensionality" to models with few parameters, it represents a significant step forward in making complex social network analysis more accessible and robust.
Summary updated