Timezone: »

 
Poster
On Differentially Private Graph Sparsification and Applications
Raman Arora · Jalaj Upadhyay

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #95
in Applications -- Privacy, Anonymity, and Security »

In this paper, we study private sparsification of graphs. In particular, we give an algorithm that given an input graph, returns a sparse graph which approximates the spectrum of the input graph while ensuring differential privacy. This allows one to solve many graph problems privately yet efficiently and accurately. This is exemplified with application of the proposed meta-algorithm to graph algorithms for privately answering cut-queries, as well as practical algorithms for computing {\scshape MAX-CUT} and {\scshape SPARSEST-CUT} with better accuracy than previously known. We also give the first efficient private algorithm to learn Laplacian eigenmap on a graph.

Keywords: Privacy, Anonymity, and Security · Applications
[ Paper]  [ Slides] 

Author Information

Raman Arora (Johns Hopkins University)
Jalaj Upadhyay (Apple)

More from the Same Authors