More Like this

1. Highly scalable maximum likelihood and conjugate Bayesian inference for ERGMs on graph sets with equivalent vertices

   https://doi.org/10.1371/journal.pone.0273039  

   Yin, Fan ; Butts, Carter T. ( August 2022 , PLOS ONE)

   De Vico Fallani, Fabrizio (Ed.)

   The exponential family random graph modeling (ERGM) framework provides a highly flexible approach for the statistical analysis of networks (i.e., graphs). As ERGMs with dyadic dependence involve normalizing factors that are extremely costly to compute, practical strategies for ERGMs inference generally employ a variety of approximations or other workarounds. Markov Chain Monte Carlo maximum likelihood (MCMC MLE) provides a powerful tool to approximate the maximum likelihood estimator (MLE) of ERGM parameters, and is generally feasible for typical models on single networks with as many as a few thousand nodes. MCMC-based algorithms for Bayesian analysis are more expensive, and high-quality answers are challenging to obtain on large graphs. For both strategies, extension to the pooled case—in which we observe multiple networks from a common generative process—adds further computational cost, with both time and memory scaling linearly in the number of graphs. This becomes prohibitive for large networks, or cases in which large numbers of graph observations are available. Here, we exploit some basic properties of the discrete exponential families to develop an approach for ERGM inference in the pooled case that (where applicable) allows an arbitrarily large number of graph observations to be fit at no additional computational cost beyond preprocessing the data itself. Moreover, a variant of our approach can also be used to perform Bayesian inference under conjugate priors, again with no additional computational cost in the estimation phase. The latter can be employed either for single graph observations, or for observations from graph sets. As we show, the conjugate prior is easily specified, and is well-suited to applications such as regularization. Simulation studies show that the pooled method leads to estimates with good frequentist properties, and posterior estimates under the conjugate prior are well-behaved. We demonstrate the usefulness of our approach with applications to pooled analysis of brain functional connectivity networks and to replicated x-ray crystal structures of hen egg-white lysozyme. 

   more » « less
2. Sharing Social Network Data: Differentially Private Estimation of Exponential Family Random-Graph Models

   https://doi.org/10.1111/rssc.12185  

   Karwa, Vishesh ; Krivitsky, Pavel N. ; Slavković, Aleksandra B. ( October 2016 , Journal of the Royal Statistical Society Series C: Applied Statistics)

   Motivated by a real life problem of sharing social network data that contain sensitive personal information, we propose a novel approach to release and analyse synthetic graphs to protect privacy of individual relationships captured by the social network while maintaining the validity of statistical results. A case-study using a version of the Enron e-mail corpus data set demonstrates the application and usefulness of the proposed techniques in solving the challenging problem of maintaining privacy and supporting open access to network data to ensure reproducibility of existing studies and discovering new scientific insights that can be obtained by analysing such data. We use a simple yet effective randomized response mechanism to generate synthetic networks under ε-edge differential privacy and then use likelihood-based inference for missing data and Markov chain Monte Carlo techniques to fit exponential family random-graph models to the generated synthetic networks.

    

   more » « less
3. Distributed Bayesian Inference in Linear Mixed-Effects Models

   Srivastava, S ; Xu, Y. ( March 2021 , Journal of computational and graphical statistics)

   null (Ed.)

   Linear mixed-effects models play a fundamental role in statistical methodology. A variety of Markov chain Monte Carlo (MCMC) algorithms exist for fitting these models, but they are inefficient in massive data settings because every iteration of any such MCMC algorithm passes through the full data. Many divide-and-conquer methods have been proposed to solve this problem, but they lack theoretical guarantees, impose restrictive assumptions, or have complex computational algorithms. Our focus is one such method called the Wasserstein Posterior (WASP), which has become popular due to its optimal theoretical properties under general assumptions. Unfortunately, practical implementation of the WASP either requires solving a complex linear program or is limited to one-dimensional parameters. The former method is inefficient and the latter method fails to capture the joint posterior dependence structure of multivariate parameters. We develop a new algorithm for computing the WASP of multivariate parameters that is easy to implement and is useful for computing the WASP in any model where the posterior distribution of parameter belongs to a location-scatter family of probability measures. The algorithm is introduced for linear mixed-effects models with both implementation details and theoretical properties. Our algorithm outperforms the current state-of-the-art method in inference on the functions of the covariance matrix of the random effects across diverse numerical comparisons. 

   more » « less
4. Structure recovery and trend estimation for dynamic network analysis

   https://doi.org/10.1002/sta4.593  

   Jiang, Xiwen ; Margarita Livas, Selena ; Yin, Fan ; Banerjee, Sayantan ; Butts, Carter T. ; Shen, Weining ( June 2023 , Stat)

   Low‐dimensional parametric models for network dynamics have been successful as inferentially efficient and interpretable tools for modelling network evolution but have difficulty in settings with strong time inhomogeneity (particularly when sharp variation in parameters is possible and covariates are limited). Here, we propose to address this problem via a novel family of block‐structured dynamic exponential‐family random graph models (ERGMs), where the time domain is divided into consecutive blocks and the network parameters are assumed to evolve smoothly within each block. In particular, we let the latent ERGM parameters follow a piecewise polynomial model with an unknown block structure (e.g., change points). We propose an iterative estimation procedure that involves estimating the block structure using trend filtering and fitting ERGMs for networks belonging to the same time block. We demonstrate the utility of the proposed approach using simulation studies and applications to interbank transaction networks and citations among political blogs over the course of an electoral cycle.

    

   more » « less
5. Metastable Mixing of Markov Chains: Efficiently Sampling Low Temperature Exponential Random Graphs

   Guy Bresler, Dheeraj Mysore ( April 2023 , The Annals of applied probability)

   In this paper we consider the problem of sampling from the low-temperature exponential random graph model (ERGM). The usual approach is via Markov chain Monte Carlo, but Bhamidi et al. showed that any local Markov chain suffers from an exponentially large mixing time due to metastable states. We instead consider metastable mixing, a notion of approximate mixing relative to the stationary distribution, for which it turns out to suffice to mix only within a collection of metastable states. We show that the Glauber dynamics for the ERGM at any temperature -- except at a lower-dimensional critical set of parameters -- when initialized at G(n,p) for the right choice of p has a metastable mixing time of O(n^2logn) to within total variation distance exp(−Ω(n)). 

   more » « less