Inference using noisy degrees: Differentially private $\beta$-model and synthetic graphs

Abstract

The $\beta$-model of random graphs is an exponential family model with the degree sequence as a sufficient statistic. In this paper, we contribute three key results. First, we characterize conditions that lead to a quadratic time algorithm to check for the existence of MLE of the $\beta$-model, and show that the MLE never exists for the degree partition $\beta$-model. Second, motivated by privacy problems with network data, we derive a differentially private estimator of the parameters of $\beta$-model, and show it is consistent and asymptotically normally distributed - it achieves the same rate of convergence as the nonprivate estimator. We present an efficient algorithm for the private estimator that can be used to release synthetic graphs. Our techniques can also be used to release degree distributions and degree partitions accurately and privately, and to perform inference from noisy degrees arising from contexts other than privacy. We evaluate the proposed estimator on real graphs and compare it with a current algorithm for releasing degree distributions and find that it does significantly better. Finally, our paper addresses shortcomings of current approaches to a fundamental problem of how to perform valid statistical inference from data released by privacy mechanisms, and lays a foundational groundwork on how to achieve optimal and private statistical inference in a principled manner by modeling the privacy mechanism; these principles should be applicable to a class of models beyond the $\beta$-model.

Published at http://dx.doi.org/10.1214/15-AOS1358 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Cooperative Game Theory Approaches for Network Partitioning
• Modeling social networks from sampled data
• Efficient, Differentially Private Point Estimators
• Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters
• How likely is an i.i.d. degree sequence to be graphical?
• Statistical Models for Degree Distributions of Networks

Cited by in corpus (6)

• Context-Aware Generative Adversarial Privacy
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Differential Privacy for Government Agencies -- Are We There Yet?
• The $\beta$-model for Random Graphs --- Regression, Cramér-Rao Bounds, and Hypothesis Testing
• Edge differentially private estimation in the $\beta$-model via jittering and method of moments
• Approximating faces of marginal polytopes in discrete hierarchical models