Private Graphon Estimation for Sparse Graphs

Abstract

We design algorithms for fitting a high-dimensional statistical model to a large, sparse network without revealing sensitive information of individual members. Given a sparse input graph $G$, our algorithms output a node-differentially-private nonparametric block model approximation. By node-differentially-private, we mean that our output hides the insertion or removal of a vertex and all its adjacent edges. If $G$ is an instance of the network obtained from a generative nonparametric model defined in terms of a graphon $W$, our model guarantees consistency, in the sense that as the number of vertices tends to infinity, the output of our algorithm converges to $W$ in an appropriate version of the $L_2$ norm. In particular, this means we can estimate the sizes of all multi-way cuts in $G$. Our results hold as long as $W$ is bounded, the average degree of $G$ grows at least like the log of the number of vertices, and the number of blocks goes to infinity at an appropriate rate. We give explicit error bounds in terms of the parameters of the model; in several settings, our bounds improve on or match known nonprivate results.

36 pages

References in corpus (5)

• Matrix estimation by Universal Singular Value Thresholding
• Graph limits and exchangeable random graphs
• Stochastic blockmodels with growing number of classes
• Rate-optimal graphon estimation
• Community detection in general stochastic block models: fundamental limits and efficient recovery algorithms

Cited by in corpus (13)

• Sparse graphs using exchangeable random measures
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Recovering communities in the general stochastic block model without knowing the parameters
• Differentially Private Continual Release of Graph Statistics
• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• Grand canonical ensembles of sparse networks and Bayesian inference
• Node-Differentially Private Estimation of the Number of Connected Components
• Classification on Large Networks: A Quantitative Bound via Motifs and Graphons
• A Nonparametric Bayesian Model for Sparse Dynamic Multigraphs
• Private Graph Data Release: A Survey
• An Information Theoretic approach to Post Randomization Methods under Differential Privacy
• Discussions of the paper "Sparse graphs using exchangeable random measures" by F. Caron and E. B. Fox