  The application of graph analytics to various domains has yielded tremendous
societal and economical benefits in recent years. However, the increasingly
widespread adoption of graph analytics comes with a commensurate increase in
the need to protect private information in graph data, especially in light of
the many privacy breaches in real-world graph data that was supposed to
preserve sensitive information. This paper provides a comprehensive survey of
private graph data release algorithms that seek to achieve the fine balance
between privacy and utility, with a specific focus on provably private
mechanisms. Many of these mechanisms are natural extensions of the Differential
Privacy framework to graph data, but we also investigate more general privacy
formulations like Pufferfish Privacy that address some of the limitations of
Differential Privacy. We also provide a wide-ranging survey of the applications
of private graph data release mechanisms to social networks, finance, supply
chain, and health care. This survey paper and the taxonomy it provides should
benefit practitioners and researchers alike in the increasingly important area
of private analytics and data release.
