Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism

Sofya Raskhodnikova, Adam Smith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

48 Scopus citations

Abstract

Lipschitz extensions were proposed as a tool for designing differentially private algorithms for approximating graph statistics. However, efficiently computable Lipschitz extensions were known only for 1-dimensional functions (that is, functions that output a single real value). We study efficiently computable Lipschitz extensions for multi-dimensional (that is, vector-valued) functions on graphs. We show that, unlike for 1-dimensional functions, Lipschitz extensions of higher-dimensional functions on graphs do not always exist, even with a non-unit stretch. We design Lipschitz extensions with small stretch for the sorted degree list and degree distribution of a graph, viewed as functions from the space of graphs equipped with the node distance into real space equipped with l1. Our extensions are from the space of bounded-degree graphs to the space of arbitrary graphs. The extensions use convex programming and are efficiently computable. We also develop a new tool for employing Lipschitz extensions in differentially private algorithms that operate with no prior knowledge of the graph (and, in particular, no knowledge of the degree bound). Specifically, we generalize the exponential mechanism, a widely used tool in data privacy. The exponential mechanism is given a collection of score functions that map datasets to real values. It returns the name of the function with nearly minimum value on the dataset. Our generalized exponential mechanism provides better accuracy than the standard exponential mechanism when the sensitivity of an optimal score function is much smaller than the maximum sensitivity over all score functions. We use our Lipschitz extensions and the generalized exponential mechanism to design a node differentially private algorithm for approximating the degree distribution of a sensitive graph. Our algorithm is much more accurate than those from previous work. In particular, our algorithm is accurate on all graphs whose degree distributions decay at least as fast as those of 'scale-free' graphs. Using our methodology, we also obtain more accurate node-private algorithms for 1-dimensional statistics.

Original languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages495-504
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Country/TerritoryUnited States
CityNew Brunswick
Period10/9/1610/11/16

All Science Journal Classification (ASJC) codes

  • General Computer Science

Fingerprint

Dive into the research topics of 'Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism'. Together they form a unique fingerprint.

Cite this