2018/10/04 by Christian Borgs, Borgs, Christian, Jennifer Chayes +5
Computer Science · Mathematics · #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Privacy-Preserving Technologies in Data #Probability (math.PR) #Random Matrices and Applications #Statistics Theory (math.ST) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.1810.02183
openalex publication_date 2018/10/04 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
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\nG(n,m)), node-private algorithms can be qualitatively more accurate than for\nmore complex models---converging at a rate of frac1\ε2 n3\ninstead of \(1)/(\ε2 n2). This result uses a new extension lemma\nfor differentially private algorithms that we hope will be broadly useful.\n