PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian inference for exponential random graph models

Alberto Caimo, Nial Friel

arXiv:1007.5192v2stat.AP

TL;DR

ERGMs are difficult to estimate because parameter-dependent normalising constants are generally unavailable, while classical methods can be inadequate. The paper uses Bayesian inference with an exchange algorithm and population-based MCMC, reporting good performance and parameter estimates consistent with observed network data. The discussion identifies thin, correlated posterior support and practical limitations of classical alternatives as important boundaries.

  • Problem

    ERGMs have intractable normalising constants, and classical MPLE and MC-MLE methods can yield inadequate or unreasonable parameter estimates.

  • Method

    The paper adapts the exchange algorithm to ERGMs and uses population-based MCMC to improve exploration of thin, correlated posterior regions.

  • Results

    The Bayesian approach gives very good performance, with estimates consistent with observed data and chains that can quickly converge to high posterior-density regions.

  • Takeaways & Limitations

    Networks simulated from the posterior had topologies similar to the observed networks, supporting the approach for ERGM analysis.

  • Takeaways & Limitations

    ERGMs’ high posterior-density regions are typically thin and correlated, making posterior exploration with MCMC difficult; population MCMC is presented as a useful first step.

Abstract

from arXiv · show

Exponential random graph models are extremely difficult models to handle from a statistical viewpoint, since their normalising constant, which depends on model parameters, is available only in very trivial cases. We show how inference can be carried out in a Bayesian framework using a MCMC algorithm, which circumvents the need to calculate the normalising constants. We use a population MCMC approach which accelerates convergence and improves mixing of the Markov chain. This approach improves performance with respect to the Monte Carlo maximum likelihood method of Geyer and Thompson (1992).

1 Introduction

The paper develops Bayesian inference for ERGMs, addressing intractable normalising constants and limitations of classical estimation through an exchange-algorithm-based population MCMC framework.

  • Motivation: ERGMs are important models for social networks, physics, and biology, but parameter estimation is hindered by intractable normalising constants and degeneracy.Existing MC-MLE and MPLE methods can produce unreasonable results or have difficult-to-understand approximation properties.
  • Motivation: Bayesian inference enables posterior exploration of parameter uncertainty and formal comparison of competing models using posterior probabilities.
  • Contribution: The paper contributes a Bayesian-based methodology for inference in ERGMs.
  • Contribution: The exchange algorithm adapts to network graphs to avoid evaluating both model and posterior normalisation terms.Because the posterior is doubly intractable, the method uses an auxiliary network simulation step.
  • Contribution: Population-based MCMC is proposed because high posterior density regions are typically thin and highly correlated, making local exploration difficult.The approach is intended to improve mixing and reduce chain autocorrelation.
  • Paper organization: The paper evaluates models on three benchmark network datasets after reviewing ERGMs and classical likelihood methods.

2 Exponential random graph models

ERGMs represent graph structure through dependent edges and network configurations, but their normalising constants are computationally difficult and degeneracy can undermine inference.

  • Network representation: Networks represent relational data as graphs whose nodes are actors and edges are relationships.Graphs may be directed or undirected, and their topology can be represented by an adjacency matrix.
  • ERGMs: ERGMs use sufficient statistics such as edges, degree statistics, and triangles to represent graph structure through a discrete linear exponential family.
  • ERGMs: The normalising constant is extremely difficult to evaluate except for trivially small graphs, despite ERGMs’ flexibility in representing complex dependence through configurations.Positive parameters increase the tendency for corresponding configurations to appear relative to chance.
  • Degeneracy: Degeneracy occurs when a parameter value places most probability mass on a small number of graph topologies, such as empty or complete graphs.
  • Degeneracy: As expected sufficient statistics approach the convex-hull boundary, probability mass concentrates on a small set of graphs associated with that boundary.
  • Degeneracy: Near degeneracy can cause MCMC methods to miss the MLE and produce estimates whose simulated networks poorly resemble the observed graph.Degenerate parameter values can generate full or empty networks during simulation and disrupt convergence.
  • Related methods: Snijders et al.’s specifications can often mitigate degeneracy and provide reasonable data fit.

3 Classical inference

Classical inference approximates ERGM likelihoods through pseudolikelihood or Monte Carlo methods because normalising constants are intractable. These approaches are sensitive to dependence structure and the choice of reference parameters, as illustrated by the Florentine example.

  • Maximum pseudolikelihood estimation: Maximum pseudolikelihood estimation approximates the likelihood with a product of easily normalised full-conditional distributions.It assumes weak dependence among graph variables, enabling fast estimation.
  • Maximum pseudolikelihood estimation: Global graph interactions can make pseudolikelihood estimates inefficient because the approximation uses only local information.The graph structure may be governed by global interaction rather than weak local dependence.
  • Monte Carlo maximum likelihood estimation: Monte Carlo maximum likelihood estimates normalising-constant ratios using MCMC-sampled graphs and importance sampling.The function wθ0(θ) is maximised to obtain a Monte Carlo estimate of the MLE.
  • A pedagogical example: In the Florentine family business graph, both MPLE and MC-MLE failed to produce parameter estimates consistent with the observed network.The model captured observed edges and two-stars, but the MC-MLE standard errors provided evidence of degeneracy.

4 Bayesian inference

Bayesian inference for ERGMs uses the exchange algorithm to avoid evaluating intractable normalising constants, with population MCMC added to improve mixing in correlated, thin posterior regions.

  • 4.1 The exchange algorithm: The exchange algorithm samples from an augmented distribution whose marginal distribution for θ is the posterior of interest.It introduces auxiliary parameters and networks, with θ′ proposed from h(·|θ) and y′ drawn from π(·|θ′).
  • 4.1 The exchange algorithm: The exchange move cancels all intractable normalising constants in its acceptance ratio.The auxiliary-network draw can be approximated using a long MCMC run when perfect sampling is unavailable.
  • 4.2 MCMC simulation from ERGMs: The TNT sampler selects an edge or empty-dyad set before choosing a dyad, reducing proposals for new edges in sparse networks.This sampler is used throughout the paper to improve mixing during network simulation.
  • 4.3 Implementing the algorithm: The implementation uses a flat multivariate normal prior, componentwise parameter proposals, 1,000 auxiliary iterations, and 30,000 main-chain iterations.Proposal tuning targets an overall acceptance rate of 18%.
  • 4.4 Convergence of the Markov chain: Exchange-algorithm estimates differ substantially from MC-MLE and MPLE, with autocorrelations negligible after lag 150.The reported posterior estimates appear in Table 2.
  • 4.5 Population MCMC can improve mixing: Population MCMC uses interacting chains and parallel adaptive-direction sampling to address slow mixing from parameter correlation and thin high-density regions.The parallel ADS updater reaches negligible autocorrelation around lag 50, compared with lag 150 for single-site updates.
  • 4.5 Population MCMC can improve mixing: The parallel ADS implementation took about 6 minutes with 6,000 iterations per chain, versus about 13 minutes for 30,000 single-site iterations.The comparison concerns estimation of model (9).

5 Examples

Across three benchmark networks, population MCMC was used to estimate Bayesian ERGMs, assess posterior fit, and examine mixing relative to single-chain samplers.

  • Benchmark setup: Population MCMC was applied to three benchmark networks, using twice as many chains as model parameters.The benchmarks comprised two undirected and one directed network.
  • Molecule network: Autocorrelations for the molecule model decayed around lag 200, versus around lag 1,000 with single-site updating.The single-site sampler therefore required about five times more iterations for comparable effectively independent draws.
  • Dolphins network: The dolphins model showed reasonable mixing across six chains and a reasonable Bayesian goodness-of-fit to the observed network.The negative edge parameter was balanced by positive parameters for local clustering and shared neighbors.
  • Dolphins network: The dolphins model’s autocorrelations were negligible around lag 200, compared with lag 1,500 for single-chain MCMC.This represented roughly a sevenfold increase in the decay lag for the single-chain version.
  • Sampson’s Monk network: For the monks model, autocorrelations were negligible around lag 60, compared with lag 400 for an equivalent single-chain run.The population sampler consequently reduced autocorrelation decay by roughly six or seven times.
  • Sampson’s Monk network: The monks model fit was judged reasonable using in-degree and out-degree statistics, appropriate for its directed edges.The cyclic-triads parameter was nonsignificant, while low edge density was balanced by high reciprocity.

6 Discussion

The paper presents Bayesian ERGM inference based on the exchange algorithm and reports parameter estimates consistent with observed network topologies where classical approaches failed. It also identifies thin, correlated posterior support and increasing computational cost as important boundaries.

  • Conclusions: The Bayesian approach produced parameter estimates consistent with observed data when MPLE and MC-MLE failed to give reasonable estimates.Networks simulated from the posterior had topologies similar to the observed networks.
  • Conclusions: The proposed method can quickly converge to high-posterior-density regions even when initialized in a degenerate region.This is supported by empirical evidence presented in the paper.
  • Limitations and future work: ERGMs typically have thin, highly correlated high-posterior-density support, making posterior exploration difficult for MCMC methods.Population MCMC is presented as a useful first step toward addressing this exploration problem.
  • Limitations and future work: Larger-network estimation is feasible but requires increased computational time, with auxiliary-chain iterations expected to scale with the number of dyads, n^2.The auxiliary chain is identified as the algorithm’s computational bottleneck, while population MCMC is suited to parallel computing.
Loading 1007.5192v2…