Dung Nguyen: Differentially private exact recovery for stochastic block models

UMD Capital Area Theory Seminar - Fall 2024
Speaker: Dung Nguyen
Title: Differentially private exact recovery for stochastic block models
Date: September 19, 2024
Abstract: The goal of community detection in graphs is to recover the underlying labels/attributes of nodes (e.g., political affiliation) based on their connectivity. Stochastic block models (SBMs) are widely studied network models for community detection algorithms. In the standard form of an SBM, the n vertices (or nodes) of a graph are divided into multiple pre-determined communities (or clusters). Connections between pairs of vertices are generated randomly and independently with pre-defined probabilities, depending on the communities to which the two endpoints belong.
A fundamental problem is the recovery of the community structure of a graph generated from an SBM. There has been significant recent progress in understanding the limits of community detection for SBMs. Sharp information-theoretic bounds for recoverability have been established for many versions of SBMs.
Our focus here is on the recoverability problem in SBMs when the connections of the input network are private. We aim to understand the fundamental trade-offs between intra-community and inter-community connection probabilities (p, q), differential privacy (DP) budget (ϵ, δ), and computational efficiency for exact recovery of community structure.
In this talk, I will focus on one of our proposed techniques called "stability analysis". This technique applies the Stability mechanism to a non-private estimator and leverages the estimator's stability to maintain the high utility of the private output. We first construct a semidefinite program (SDP) estimator that relaxes the maximum likelihood estimator (MLE) for the communities. Then, we prove that the optimal solution of the SDP is highly stable, i.e., it remains unchanged when the input is slightly perturbed, by providing a stable dual certificate for the SDP under edge perturbation.
The stability analysis has successfully derived the conditions for exact recovery in symmetric SBMs (where communities are of equal size) (ICML '22), which was also the first exact recovery result achieved under DP. Recently, we have designed efficient algorithms and established conditions for exact recovery in three different versions of SBMs: Asymmetric SBM (where communities have non-uniform sizes), General Structure SBM (with outliers), and Censored SBM (with edge features) (ICML '24).