Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guarantee
This addresses privacy concerns for social network data publishers by enabling synthetic graph release with formal privacy guarantees while maintaining key structural properties.
The authors tackled the problem of publishing attributed social graphs with differential privacy while preserving community structure, and their method outperformed existing approaches in preserving community structure, degree sequences, and clustering coefficients.
We present a novel method for publishing differentially private synthetic attributed graphs. Unlike preceding approaches, our method is able to preserve the community structure of the original graph without sacrificing the ability to capture global structural properties. Our proposal relies on C-AGM, a new community-preserving generative model for attributed graphs. We equip C-AGM with efficient methods for attributed graph sampling and parameter estimation. For the latter, we introduce differentially private computation methods, which allow us to release community-preserving synthetic attributed social graphs with a strong formal privacy guarantee. Through comprehensive experiments, we show that our new model outperforms its most relevant counterparts in synthesising differentially private attributed social graphs that preserve the community structure of the original graph, as well as degree sequences and clustering coefficients.