A Workflow for Differentially-Private Graph Synthesis
The authors present a new workflow for differentially-private publication of graph topologies. First, they produce differentially private measurements of interesting graph statistics using their new version of the PINQ programming language, Weighted PINQ, which is based on a generalization of differential privacy to weighted sets. Next, they show how to generate graphs that fit any set of measured graph statistics, even if they are inconsistent (due to noise), or if they are only indirectly related to actual statistics that they want their synthetic graph to preserve. They combine the answers to Weighted PINQ queries with an incremental evaluator (Markov Chain Monte Carlo (MCMC)) to synthesize graphs where the statistic of interest aligns with that of the protected graph.