Speaker: Jalaj Upadhyay
Affiliation: JHU

Title: Differentially Private Spectral Sparsification of Graphs
Abstract:
In this talk, we will discuss differentially private spectral sparsification of graphs. We argue that traditional spectral sparsification where the output graph is a subgraph of the input graph is not possible with differential privacy. This motivates us to define a relaxed version of spectral sparsification of graphs.

We consider edge-level privacy, i.e., neighboring graphs differs in one edge with weight one. We give efficient $(\alpha,\beta)$-differentially private algorithms that, on input a dense graph G, construct a spectral sparsification of G. Our output graphs has $ O(n/\eps^2)$ weighted edges, which matches the best known non-private algorithms.

We can use our private sparse graph to solve various combinatorial and learning problems on graphs efficiently while preserving differential privacy. Some examples include all possible cut queries, Max-Cut, Sparse-Cut, Edge-Expansion, Laplacian eigenmaps, etc.

This talk is based on a joint work with Raman Arora and Vladimir Braverman.