Or Sheffet: "Privacy Preserving Graph Analysis"

It is no secret that online companies, hospitals, credit-card companies and governments hold massive datasets composed of our personal and private details. Information from such datasets is often released using some privacy preserving heuristics, which have been repeatedly shown to fail. In contrast, differentially private algorithms release information about a given dataset while satisfying a powerful and mathematical guarantee of privacy.

The focus of this talk will be on designing differentially private algorithms for releasing information for graph-datasets. After all, many of the datasets containing the sensitive details of individuals are in the form of a graph (such as social networks, "bed graphs", movie picks, etc.) We will discuss two notions of preserving privacy: for edge-level changes and for node-level changes. For edge-level changes we will focus on answering multiple cut-queries—the number of edges between a set of vertices and its complementary (e.g., "how many non-American friends do Americans have?"). For node-level changes we will focus on profile-queries—counting the number of nodes that satisfy some property involving a node and its neighbors (e.g., "how many people are friends with at least two Americans?"). We will exhibit differential private techniques for answering these types of queries, among them is the famous Johnson-Lindenstrauss transform which preserves differential privacy under certain conditions.

(Time permitting, we will draw a connection between our differentially private algorithms, that have provable guarantees only for "nice" instances, and the broader framework of non-worst-case analysis, which is relevant to many fields within computer science.)

The talk is self-contained and no prior knowledge is assumed.