att_abstract={{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 defines 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 algorithms can be used to estimate the parameters
of suitable graph models, allowing synthetic graphs to be
	att_categories={C_BB.1, C_NSS.2},
	att_copyright_notice={{(c) ACM, 2015. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in 2015 {{, 2015-05-31}}.
	author={Divesh Srivastava and Jun Zhang and Graham Cormode and Cecilia M. Procopiuc and Xiaokui Xiao},
	institution={{ACM SIGMOD International Conference on Management of Data}},
	title={{Private Release of Graph Statistics using Ladder Functions}},