A workflow for differentially-private graph synthesis

By Davide Proserpio, Sharon Goldberg, Frank McSherry. 2012

59 citations recorded by the source corpus.

We present a new workflow for differentially-private publication of graph topologies. First, we produce differentially-private measurements of interesting graph statistics using our new version of the PINQ programming language, Weighted PINQ, which is based on a generalization of differential privacy to weighted sets. Next, we 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 we want our synthetic graph to preserve. We 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. This paper presents our preliminary results; we show how to cast a few graph statistics (degree distribution, edge multiplicity, joint degree distribution) as queries in Weighted PINQ, and then present experimental results synthesizing graphs generated from answers to these queries.

Subfields: Artificial Intelligence, Sociology and Political Science

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

Citations in the corpus

Correlated network data publication via differential privacy (2013, methodology): “[31] present a new workflow for differentially private graph synthesis.”
EKTELO: A Framework for Defining Differentially-Private Computations (2018, methodology): “The use of inference appears in many di↵erentially private algorithms [3, 5, 7, 18, 22, 23, 25, 31, 36, 37, 43].”
A Guide to Differential Privacy Theory in Social Network Analysis (2012, background): “The Stochastic Kronecker graph model has been privatized under edge-privacy [14], and several other groups have developed their own models that satisfy differential edge privacy, [15], [16], [17].”