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

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.