  Differentially private graph analysis is a powerful tool for deriving
insights from diverse graph data while protecting individual information.
Designing private analytic algorithms for different graph queries often
requires starting from scratch. In contrast, differentially private synthetic
graph generation offers a general paradigm that supports one-time generation
for multiple queries. Although a rich set of differentially private graph
generation algorithms has been proposed, comparing them effectively remains
challenging due to various factors, including differing privacy definitions,
diverse graph datasets, varied privacy requirements, and multiple utility
metrics.
  To this end, we propose PGB (Private Graph Benchmark), a comprehensive
benchmark designed to enable researchers to compare differentially private
graph generation algorithms fairly. We begin by identifying four essential
elements of existing works as a 4-tuple: mechanisms, graph datasets, privacy
requirements, and utility metrics. We discuss principles regarding these
elements to ensure the comprehensiveness of a benchmark. Next, we present a
benchmark instantiation that adheres to all principles, establishing a new
method to evaluate existing and newly proposed graph generation algorithms.
Through extensive theoretical and empirical analysis, we gain valuable insights
into the strengths and weaknesses of prior algorithms. Our results indicate
that there is no universal solution for all possible cases. Finally, we provide
guidelines to help researchers select appropriate mechanisms for various
scenarios.
