research-article

Publishing Attributed Social Graphs with Formal Privacy Guarantees

Authors:

Zach Jorgensen,

Graham CormodeAuthors Info & Claims

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

Pages 107 - 122

https://doi.org/10.1145/2882903.2915215

Published: 14 June 2016 Publication History

Abstract

Many data analysis tasks rely on the abstraction of a graph to represent relations between entities, with attributes on the nodes and edges. Since the relationships encoded are often sensitive, we seek effective ways to release representative graphs which nevertheless protect the privacy of the data subjects. Prior work on this topic has focused primarily on the graph structure in isolation, and has not provided ways to handle richer graphs with correlated attributes.

We introduce an approach to release such graphs under the strong guarantee of differential privacy. We adapt existing graph models, and introduce a new one, and show how to augment them with meaningful privacy. This provides a complete workflow, where the input is a sensitive graph, and the output is a realistic synthetic graph. Our experimental study demonstrates that our process produces useful, accurate attributed graphs.

References

[1]

J. Blocki, A. Blum, A. Datta, and O. Sheffet. Differentially private data analysis of social networks via restricted sensitivity. In ITCS, 2013.

Digital Library

[2]

I. Cantador, P. Brusilovsky, and T. Kuflik. 2nd workshop on information heterogeneity and fusion in recommender systems (hetrec). In RecSys, 2011.

Digital Library

[3]

R. Chen, B. C. Fung, S. Y. Philip, and B. C. Desai. Correlated network data publication via differential privacy. VLDB Journal, pages 1--24, 2013.

Digital Library

[4]

S. Chen and S. Zhou. Recursive mechanism: towards node differential privacy and unrestricted joins. In SIGMOD, 2013.

Digital Library

[5]

F. Chung and L. Lu. The average distances in random graphs with given expected degrees. volume 99, pages 15879--15882. National Acad Sciences, 2002.

[6]

C. Dwork. Differential privacy. ICALP, 2006.

Digital Library

[7]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography, 2006.

Digital Library

[8]

M. Hay. Enabling accurate analysis of private network data. PhD thesis, University of Massachusetts Amherst, 2010.

Digital Library

[9]

M. Hay, G. Miklau, D. Jensen, D. Towsley, and P. Weis. Resisting structural re-identification in anonymized social networks. VLDB, 1(1):102--114, 2008.

Digital Library

[10]

M. Hay, C. Li, G. Miklau, and D. Jensen. Accurate estimation of the degree distribution of private networks. In ICDM, 2009.

Digital Library

[11]

Z. Jorgensen and T. Yu. A privacy-preserving framework for personalized, social recommendations. In EDBT, 2014.

[12]

V. Karwa, S. Raskhodnikova, A. Smith, and G. Yaroslavtsev. Private analysis of graph structure. PVLDB, 2011.

Digital Library

[13]

S. P. Kasiviswanathan, K. Nissim, S. Raskhodnikova, and A. Smith. Analyzing graphs with node differential privacy. In Theory of Cryptography, 2013.

Digital Library

[14]

D. Kifer and B.-R. Lin. Towards an axiomatization of statistical privacy and utility. In PODS, 2010.

Digital Library

[15]

T. G. Kolda, A. Pinar, T. Plantenga, and C. Seshadhri. A scalable generative graph model with community structure. SIAM J. Sci. Comput., 36(5), C424--C452, 2014.

Digital Library

[16]

K. Liu and E. Terzi. Towards identity anonymization on graphs. In SIGMOD, 2008.

Digital Library

[17]

W. Lu and G. Miklau. Exponential random graph estimation under differential privacy. In KDD, 2014.

Digital Library

[18]

P. Massa and P. Avesani. Trust-aware bootstrapping of recommender systems. In Workshop on recommender systems, 2006.

Digital Library

[19]

M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: Homophily in social networks. Annual review of sociology, pages 415--444, 2001.

[20]

F. McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In SIGMOD, 2009.

Digital Library

[21]

F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, 2007.

Digital Library

[22]

D. J. Mir and R. N. Wright. A differentially private graph estimator. In ICDMW, 2009.

Digital Library

[23]

A. Narayanan and V. Shmatikov. De-anonymizing social networks. In Security and Privacy, 2009.

Digital Library

[24]

Nissim, Raskhodnikova, and Smith. Smooth sensitivity and sampling in private data analysis. In STOC, 2007.

Digital Library

[25]

J. J. Pfeiffer, T. La Fond, S. Moreno, and J. Neville. Fast generation of large scale social networks while incorporating transitive closures. In (PASSAT), 2012.

Digital Library

[26]

J. J. Pfeiffer III, S. Moreno, T. La Fond, J. Neville, and B. Gallagher. Attributed graph models: modeling network structure with correlated attributes. In WWW, 2014.

Digital Library

[27]

A. Pinar, C. Seshadhri, and T. G. Kolda. The similarity between stochastic kronecker and chung-lu graph models. CoRR, abs/1110.4925, 2011.

[28]

D. Proserpio, S. Goldberg, and F. McSherry. Calibrating data to sensitivity in private data analysis. In VLDB, 2014.

Digital Library

[29]

A. Sala, X. Zhao, C. Wilson, H. Zheng, and B. Y. Zhao. Sharing graphs using differentially private graph models. In IMC, 2011.

Digital Library

[30]

C. Seshadhri, T. G. Kolda, and A. Pinar. Community structure and scale-free collections of erdos-rényi graphs. Physical Review E, 85(5):056109, 2012.

[31]

C. Seshadhri, A. Pinar, and T. G. Kolda. An in-depth study of stochastic kronecker graphs. In ICDM, 2011.

Digital Library

[32]

E. Shen and T. Yu. Mining frequent graph patterns with differential privacy. In KDD, 2013.

Digital Library

[33]

Y. Wang and X. Wu. Preserving differential privacy in degree-correlation based graph generation. Transactions on data privacy, 6(2):127, 2013.

Digital Library

[34]

Y. Wang, X. Wu, J. Zhu, and Y. Xiang. On learning cluster coefficient of private networks. Social Network Analysis and Mining (3), pages 925--938, 2013.

[35]

Q. Xiao, R. Chen, and K.-L. Tan. Differentially private network data release via structural inference. In KDD, 2014.

Digital Library

[36]

J. Zhang, G. Cormode, C. M. Procopiuc, D. Srivastava, and X. Xiao. Private release of graph statistics using ladder functions. In SIGMOD, 2015.

Digital Library

[37]

B. Zhou and J. Pei. Preserving privacy in social networks against neighborhood attacks. In ICDE, 2008.

Digital Library

[38]

L. Zou, L. Chen, and M. T. Özsu. K-automorphism: A general framework for privacy preserving network publication. PVLDB (2), 946--957, 2009.

Digital Library

Cited By

Zhang QLee HMa JLou JYang CXiong LChua TNgo CKa-Wei Lee RKumar RLauw H(2024)DPAR: Decoupled Graph Neural Networks with Node-Level Differential PrivacyProceedings of the ACM on Web Conference 202410.1145/3589334.3645531(1170-1181)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645531
Guan YLu RZhang SZheng YShao JWei G(2024)Efficient and Privacy-Preserving Aggregate Query Over Public Property GraphsIEEE Transactions on Big Data10.1109/TBDATA.2023.334262310:2(146-157)Online publication date: Apr-2024
https://doi.org/10.1109/TBDATA.2023.3342623
Fahrenkrog-Petersen Svan der Aa HWeidlich M(2024)Privacy-Aware Analysis based on Data Series2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00406(5365-5370)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00406
Show More Cited By

Index Terms

Publishing Attributed Social Graphs with Formal Privacy Guarantees
1. Security and privacy
  1. Software and application security
    1. Social network security and privacy

Recommendations

dK-Microaggregation: Anonymizing Graphs with Differential Privacy Guarantees
Advances in Knowledge Discovery and Data Mining
Abstract
With the advances of graph analytics, preserving privacy in publishing graph data becomes an important task. However, graph data is highly sensitive to structural changes. Perturbing graph data for achieving differential privacy inevitably leads ...
Read More
Protecting sensitive place visits in privacy-preserving trajectory publishing
Highlights
- We propose a method for privacy-preserving trajectory publishing.
- It aims at ...
Abstract
The rise of mobile computing has generated huge amount of trajectory data. Since these data are valuable for many people, publishing them while providing adequate individual privacy protection has been a challenging task. In this paper,...
Read More
Publishing Graph Data with Subgraph Differential Privacy
WISA 2015: Revised Selected Papers of the 16th International Workshop on Information Security Applications - Volume 9503

The eruption of social networks, communication networks etc. makes them become valuable resources for the research community. However, the graph data owners hesitate to share their data due to the barrier of privacy leakage. In this work, we propose a ...
Read More

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '16: Proceedings of the 2016 International Conference on Management of Data

June 2016

2300 pages

ISBN:9781450335317

DOI:10.1145/2882903

General Chairs:
Fatma Özcan
IBM Research, USA
,
Georgia Koutrika
HP Labs, USA
,
Program Chair:
Sam Madden
Massachusetts Institute of Technology, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

European Commission Marie Curie Integration Grant
Royal Society Wolfson Research Merit Award

Conference

SIGMOD/PODS'16

Sponsor:

SIGMOD

SIGMOD/PODS'16: International Conference on Management of Data

June 26 - July 1, 2016

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
1,188
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)15

Other Metrics

View Author Metrics

Citations

Cited By

Zhang QLee HMa JLou JYang CXiong LChua TNgo CKa-Wei Lee RKumar RLauw H(2024)DPAR: Decoupled Graph Neural Networks with Node-Level Differential PrivacyProceedings of the ACM on Web Conference 202410.1145/3589334.3645531(1170-1181)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645531
Guan YLu RZhang SZheng YShao JWei G(2024)Efficient and Privacy-Preserving Aggregate Query Over Public Property GraphsIEEE Transactions on Big Data10.1109/TBDATA.2023.334262310:2(146-157)Online publication date: Apr-2024
https://doi.org/10.1109/TBDATA.2023.3342623
Fahrenkrog-Petersen Svan der Aa HWeidlich M(2024)Privacy-Aware Analysis based on Data Series2024 IEEE 40th International Conference on Data Engineering (ICDE)10.1109/ICDE60146.2024.00406(5365-5370)Online publication date: 13-May-2024
https://doi.org/10.1109/ICDE60146.2024.00406
Yuan QZhang ZDu LChen MCheng PSun MCalandrino JTroncoso C(2023)PrivGraphProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620419(3241-3258)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620419
Khokhar RFung BIqbal FAl-Hussaeni KHussain M(2023)Differentially Private Release of Heterogeneous Network for Managing Healthcare DataACM Transactions on Knowledge Discovery from Data10.1145/358036717:6(1-30)Online publication date: 18-Jan-2023
https://dl.acm.org/doi/10.1145/3580367
Li YPurcell MRakotoarivelo TSmith DRanbaduge TNg K(2023)Private Graph Data Release: A SurveyACM Computing Surveys10.1145/356908555:11(1-39)Online publication date: 22-Feb-2023
https://dl.acm.org/doi/10.1145/3569085
Zhang MZhou JZhang GCui LGao TYu S(2023)APDP: Attribute-Based Personalized Differential Privacy Data Publishing Scheme for Social NetworksIEEE Transactions on Network Science and Engineering10.1109/TNSE.2022.322473110:2(922-933)Online publication date: 1-Mar-2023
https://doi.org/10.1109/TNSE.2022.3224731
Ren WGhazinour KLian X(2023)$kt$-Safety: Graph Release via $k$-Anonymity and $t$-ClosenessIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.322133335:9(9102-9113)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TKDE.2022.3221333
Ma CYuan LHan LDing MBhaskar RLi J(2023)Data Level Privacy Preserving: A Stochastic Perturbation Approach Based on Differential PrivacyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.313704735:4(3619-3631)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TKDE.2021.3137047
Jian XWang YChen L(2023)Publishing Graphs Under Node Differential PrivacyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2021.312894635:4(4164-4177)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TKDE.2021.3128946
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents