The Library
Private release of graph statistics using ladder functions
Tools
Tools
Tools
Zhang, Jun, Cormode, Graham, Procopiuc, Cecilia, Srivastava, Divesh and Xiao, Xiaokui (2015) Private release of graph statistics using ladder functions. In: ACM SIGMOD 2015, Melbourne, Australia, 1-4 Jun 2015. Published in: SIGMOD '15 Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data pp. 731-745. ISBN 9781450327589. doi:10.1145/2723372.2737785
|
PDF
WRAP_Cormode.pdf - Accepted Version - Requires a PDF viewer. Download (800Kb) | Preview |
Official URL: http://doi.org/10.1145/2723372.2737785
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 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.
| Item Type: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Data protection, Computer security, Statistics, Bayesian statistical decision theory, Data encryption (Computer science) | ||||
| Series Name: | MOD: International Conference on Management of Data | ||||
| Journal or Publication Title: | SIGMOD '15 Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data | ||||
| Publisher: | ACM | ||||
| ISBN: | 9781450327589 | ||||
| Official Date: | 5 May 2015 | ||||
| Dates: |
|
||||
| Page Range: | pp. 731-745 | ||||
| DOI: | 10.1145/2723372.2737785 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Date of first compliant deposit: | 27 February 2016 | ||||
| Date of first compliant Open Access: | 27 February 2016 | ||||
| Funder: | Marie Skłodowska-Curie actions, AT&T, Nanyang Technological University, Microsoft Research Asia, Ministry of Education (Singapore) | ||||
| Grant number: | PCIG13-GA-2013-618202 , M4080094.020 | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | ACM SIGMOD 2015 | ||||
| Type of Event: | Conference | ||||
| Location of Event: | Melbourne, Australia | ||||
| Date(s) of Event: | 1-4 Jun 2015 | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
