Edge differentially private estimation in the $\beta$-model via jittering and method of moments

Abstract

A standing challenge in data privacy is the trade-off between the level of privacy and the efficiency of statistical inference. Here we conduct an in-depth study of this trade-off for parameter estimation in the $\beta$-model (Chatterjee, Diaconis and Sly, 2011) for edge differentially private network data released via jittering (Karwa, Krivitsky and Slavković, 2017). Unlike most previous approaches based on maximum likelihood estimation for this network model, we proceed via method-of-moments. This choice facilitates our exploration of a substantially broader range of privacy levels - corresponding to stricter privacy - than has been to date. Over this new range we discover our proposed estimator for the parameters exhibits an interesting phase transition, with both its convergence rate and asymptotic variance following one of three different regimes of behavior depending on the level of privacy. Because identification of the operable regime is difficult if not impossible in practice, we devise a novel adaptive bootstrap procedure to construct uniform inference across different phases. In fact, leveraging this bootstrap we are able to provide for simultaneous inference of all parameters in the $\beta$-model (i.e., equal to the number of nodes), which, to our best knowledge, is the first result of its kind. Numerical experiments confirm the competitive and reliable finite sample performance of the proposed inference methods, next to a comparable maximum likelihood method, as well as significant advantages in terms of computational speed and memory.

References in corpus (12)

• Gaussian approximations and multiplier bootstrap for maxima of sums of high-dimensional random vectors
• Random graphs with a given degree sequence
• Exponential and moment inequalities for U-statistics
• Maximum lilkelihood estimation in the $\beta$-model
• A central limit theorem in the $\beta$-model for undirected random graphs with a diverging number of vertices
• Inference using noisy degrees: Differentially private $\beta$-model and synthetic graphs
• Simulation-Based Hypothesis Testing of High Dimensional Means Under Covariance Heterogeneity
• Confidence regions for entries of a large precision matrix
• Estimation of subgraph density in noisy networks
• Central limit theorems for high dimensional dependent data
• Applications of Differential Privacy in Social Network Analysis: A Survey
• Asymptotic Theory for Differentially Private Generalized $\beta$-models with Parameters Increasing