## 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 language | English (US) |
---|---|

Title of host publication | Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |

Publisher | IEEE Computer Society |

Pages | 495-504 |

Number of pages | 10 |

ISBN (Electronic) | 9781509039333 |

DOIs | |

State | Published - Dec 14 2016 |

Event | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States Duration: Oct 9 2016 → Oct 11 2016 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2016-December |

ISSN (Print) | 0272-5428 |

### Other

Other | 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 |
---|---|

Country/Territory | United States |

City | New Brunswick |

Period | 10/9/16 → 10/11/16 |

## All Science Journal Classification (ASJC) codes

- Computer Science(all)