We are happy to co-host the talk by Prof. Ravi Tandon as a part of Trust Lab Colloquium.

Community detection is a fundamental problem arising in graph mining and machine learning, with numerous interesting applications in social networks, image segmentation and biological networks. The goal of community detection over graphs is to recover underlying labels/attributes of users (e.g., political affiliation) given the connectivity between users (represented by adjacency matrix of the graph). There has been significant recent progress on understanding the fundamental limits of community detection when the graph is generated from a stochastic block model (SBM). Specifically, sharp information theoretic limits and efficient algorithms have been obtained for SBMs as a function of p and q, which represent the intra-community and inter-community connection probabilities. In this talk, we will give an overview of our recent work on differentially private community detection. In many problem scenarios, one may wishto perform clustering/community detection while protecting privacy of sensitive information (such as connectivity between two users which could be sensitive information). SBMs provide a fertile ground to design and study such privacy preserving mechanisms while facilitating utility analysis. Focusing on the notion of edge-differential privacy (edge-DP), we seek to understand the fundamental tradeoffs between SBMs network connectivity (p, q), privacy budget and computational efficiency for the recovery of community labels.  To this end, I will discuss and present the associated information-theoretic tradeoffs for three broad classes of differentially private community recovery mechanisms: a) stability based mechanism; b) sampling based mechanisms; and c) graph perturbation mechanisms. Our main findings are that stability and sampling based mechanisms lead to a superior privacy-recovery tradeoff however this comes at the expense of higher computational complexity. On the other hand, albeit low complexity, graph perturbation mechanisms require the privacy budget to scale logarithmically with the graph size for exact recovery. I will conclude with several open problems and challenges in this topic. This talk is based on joint work with Mohamed Seif, Dung Nguyen and Anil Vullikanti and was presented at ICML.