Private Graphon Estimation for Sparse Graphs

Understand

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.