Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation

Motivated by growing concerns over ensuring privacy on social networks, we\ndevelop new algorithms and impossibility results for fitting complex\nstatistical models to network data subject to rigorous privacy guarantees. We\nconsider the so-called node-differentially private algorithms, which compute\ninformation about a graph or network while provably revealing almost no\ninformation about the presence or absence of a particular node in the graph.\n We provide new algorithms for node-differentially private estimation for a\npopular and expressive family of network models: stochastic block models and\ntheir generalization, graphons. Our algorithms improve on prior work, reducing\ntheir error quadratically and matching, in many regimes, the optimal nonprivate\nalgorithm. We also show that for the simplest random graph models ($G(n,p)$ and\n$G(n,m)$), node-private algorithms can be qualitatively more accurate than for\nmore complex models---converging at a rate of $\\frac{1}{\\epsilon^2 n^{3}}$\ninstead of $\\frac{1}{\\epsilon^2 n^2}$. This result uses a new extension lemma\nfor differentially private algorithms that we hope will be broadly useful.\n