  Graph data is used in a wide range of applications, while analyzing graph
data without protection is prone to privacy breach risks. To mitigate the
privacy risks, we resort to the standard technique of differential privacy to
publish a synthetic graph. However, existing differentially private graph
synthesis approaches either introduce excessive noise by directly perturbing
the adjacency matrix, or suffer significant information loss during the graph
encoding process. In this paper, we propose an effective graph synthesis
algorithm PrivGraph by exploiting the community information. Concretely,
PrivGraph differentially privately partitions the private graph into
communities, extracts intra-community and inter-community information, and
reconstructs the graph from the extracted graph information. We validate the
effectiveness of PrivGraph on six real-world graph datasets and seven commonly
used graph metrics.
