Privacy Preserving Adjacency Spectral Embedding on Stochastic Blockmodels
This work addresses privacy risks for users of sensitive graph data, but it is incremental as it adapts an existing method with differential privacy.
The authors tackled the problem of privacy leakage in graph analysis by proposing a differentially private adjacency spectral embedding algorithm for stochastic blockmodels, achieving latent position estimates close to non-private methods with comparable accuracy at desired privacy parameters in simulations and real-world networks.
For graphs generated from stochastic blockmodels, adjacency spectral embedding is asymptotically consistent. Further, adjacency spectral embedding composed with universally consistent classifiers is universally consistent to achieve the Bayes error. However when the graph contains private or sensitive information, treating the data as non-private can potentially leak privacy and incur disclosure risks. In this paper, we propose a differentially private adjacency spectral embedding algorithm for stochastic blockmodels. We demonstrate that our proposed methodology can estimate the latent positions close to, in Frobenius norm, the latent positions by adjacency spectral embedding and achieve comparable accuracy at desired privacy parameters in simulated and real world networks.