  We consider the problem of generating private synthetic versions of
real-world graphs containing private information while maintaining the utility
of generated graphs. Differential privacy is a gold standard for data privacy,
and the introduction of the differentially private stochastic gradient descent
(DP-SGD) algorithm has facilitated the training of private neural models in a
number of domains. Recent advances in graph generation via deep generative
networks have produced several high performing models. We evaluate and compare
state-of-the-art models including adjacency matrix based models and edge based
models, and show a practical implementation that favours the edge-list approach
utilizing the Gaussian noise mechanism when evaluated on commonly used graph
datasets. Based on our findings, we propose a generative model that can
reproduce the properties of real-world networks while maintaining
edge-differential privacy. The proposed model is based on a stochastic neural
network that generates discrete edge-list samples and is trained using the
Wasserstein GAN objective with the DP-SGD optimizer. Being the first approach
to combine these beneficial properties, our model contributes to further
research on graph data privacy.
