Inference using noisy degrees: differentially private -model and synthetic graphs
From MaRDI portal
Publication:5963517
DOI10.1214/15-AOS1358zbMATH Open1331.62114OpenAlexW3105437875MaRDI QIDQ5963517FDOQ5963517
Authors: Vishesh Karwa, Aleksandra Slavković 
Publication date: 22 February 2016
Published in: The Annals of Statistics (Search for Journal in Brave)
Abstract: The -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 -model, and show that the MLE never exists for the degree partition -model. Second, motivated by privacy problems with network data, we derive a differentially private estimator of the parameters of -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 -model.
Full work available at URL: https://arxiv.org/abs/1205.4697
Recommendations
Asymptotic properties of parametric estimators (62F12) Parametric inference under constraints (62F30) Social networks; opinion dynamics (91D30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A central limit theorem in the \(\beta \)-model for undirected random graphs with a diverging number of vertices
- A remark on the existence of finite graphs
- A sequential importance sampling algorithm for generating random graphs with prescribed degrees
- A statistical framework for differential privacy
- An Exponential Family of Probability Distributions for Directed Graphs
- Analyzing graphs with node differential privacy
- Asymptotic normality in the maximum entropy models on graphs with an increasing number of parameters
- Goodness of Fit of Social Network Models
- Graver basis for an undirected graph and its application to testing the beta model of random graphs
- How likely is an LLD degree sequence to be graphical?
- Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
- MM algorithms for generalized Bradley-Terry models.
- Maximum likelihood estimation in the \(\beta\)-model
- Measurement Error in Nonlinear Models
- Modeling social networks from sampled data
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- On the geometry of discrete exponential families with application to exponential random graph models
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Polytopes from subgraph statistics
- Random graphs with a given degree sequence
- Sampling for conditional inference on network data
- Statistical disclosure control in practice
- The polytope of degree partitions
- Theory of Cryptography
- Threshold graphs and related topics
- Universally utility-maximizing privacy mechanisms
Cited In (25)
- Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
- A note on asymptotic distributions in a directed network model with degree heterogeneity and homophily
- Structure and sensitivity in differential privacy: comparing \(K\)-norm mechanisms
- Statistical inference in a directed network model with covariates
- Exponential-family models of random graphs: inference in finite, super and infinite population scenarios
- Asymptotic in the ordered networks with a noisy degree sequence
- Providing access to confidential research data through synthesis and verification: an application to data on employees of the U.S. federal government
- Affiliation weighted networks with a differentially private degree sequence
- Confidentiality and differential privacy in the dissemination of frequency tables
- Distribution-invariant differential privacy
- Differentially private estimation in a class of bipartite graph models
- Non-asymptotic model selection for models of network data with parameter vectors of increasing dimension
- Minimax Optimal Procedures for Locally Private Estimation
- A survey of discrete methods in (algebraic) statistics for networks
- A semiparametric Bayesian approach to epidemics, with application to the spread of the coronavirus MERS in South Korea in 2015
- Detection thresholds for the \(\beta\)-model on sparse graphs
- On the efficacy of higher-order spectral clustering under weighted stochastic block models
- Asymptotic in undirected random graph models with a noisy degree sequence
- Finite sample differentially private confidence intervals
- Nonparametric density estimation for intentionally corrupted functional data
- Asymptotics in theβ-model for networks with a differentially private degree sequence
- Directed Networks with a Differentially Private Bi-degree Sequence
- Edge differentially private estimation in the \(\beta\)-model via jittering and method of moments
- Bivariate gamma model
- Weighted directed networks with a differentially private bi-degree sequence
This page was built for publication: Inference using noisy degrees: differentially private \(\beta\)-model and synthetic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963517)
