## J. Zhang, G. Cormode, M. Procopiuc, D. Srivastava, and X. Xiao.
Private release of graph statistics using ladder functions.
In *ACM SIGMOD International Conference on Management of Data
(SIGMOD)*, 2015.

Protecting the privacy of individuals in graph structured data while
making accurate versions of the data available is one of the most
challenging problems in data privacy.
Most efforts to date to perform this data
release end up mired in complexity, overwhelm the signal with noise, and
are not effective for use in practice.
In this paper, we introduce a new method which guarantees differential
privacy. It specifies a probability distribution over possible outputs
that is carefully defined to maximize the utility for the given input,
while still providing the required privacy level. The distribution is
designed to form a `ladder', so that each output achieves the highest
`rung' (maximum probability) compared to less preferable outputs. We
show how our ladder framework can be applied to problems of counting the
number of occurrences of subgraphs, a vital objective in graph analysis,
and give algorithms whose cost is comparable to that of computing the
count exactly. Our experimental study confirms that our method
outperforms existing methods for counting triangles and stars in
terms of accuracy, and provides solutions for some problems for which
no effective method was previously known.
The results of our algorithms can be used to estimate the parameters of
suitable graph models, allowing synthetic graphs to be sampled.

[ bib |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*