More Web Proxy on the site http://driver.im/

research-article

Free access

Just Accepted

Time-Aware Anonymization of Knowledge Graphs

Authors:

Barbara Carminati,

Elena FerrariAuthors Info & Claims

ACM Transactions on Privacy and Security

Accepted on 06 September 2022

https://doi.org/10.1145/3563694

Online AM: 23 September 2022 Publication History

Abstract

Knowledge graphs (KGs) play an essential role in data sharing because they can model both users’ attributes and their relationships. KGs can tailor many data analyses, such as classification where a sensitive attribute is selected and the analyst analyzes the associations between users and the sensitive attribute’s values (aka sensitive values). Data providers anonymize their KGs and share the anonymized versions to protect users’ privacy. Unfortunately, an adversary can exploit these attributes and relationships to infer sensitive information by monitoring either one or many snapshots of a KG. To cope with this issue, in this paper, we introduce (k, l)-Sequential Attribute Degree ((k, l)-sad), an extension of the k^w-tad principle[10], to ensure that sensitive values of re-identified users are diverse enough to prevent them from being inferred with a confidence higher than \(\frac{1}{l}\) even though adversaries monitor all published KGs. In addition, we develop the Time-Aware Knowledge Graph Anonymization Algorithm to anonymize KGs such that all published anonymized versions of a KG satisfy the (k, l)-sad principle, by, at the same time, preserving the utility of the anonymized data. We conduct experiments on four real-life datasets to show the effectiveness of our proposal and compare it with k^w-tad.

References

[1]

Adeel Anjum, Guillaume Raschia, Marc Gelgon, Abid Khan, Naveed Ahmad, Mansoor Ahmed, Sabah Suhail, M Masoom Alam, et al. 2017. τ-safety: A privacy model for sequential publication with arbitrary updates. Computers & Security 66(2017), 20–39. https://doi.org/10.1016/j.cose.2016.12.014

Digital Library

[2]

Kurt Bollacker, Colin Evans, et al. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM, New York, NY, USA, 1247–1250. https://doi.org/10.1145/1376616.1376746

Digital Library

[3]

Ricardo JGB Campello, Davoud Moulavi, et al. 2015. Hierarchical density estimates for data clustering, visualization, and outlier detection. ACM Transactions on Knowledge Discovery from Data (TKDD) 10, 1, Article 5 (2015), 51 pages. https://doi.org/10.1145/2733381

[4]

Jordi Casas-Roma, Julián Salas, Fragkiskos D Malliaros, and Michalis Vazirgiannis. 2019. k-Degree anonymity on directed networks. Knowledge and Information Systems 61, 3 (2019), 1743–1768. https://doi.org/10.1007/s10115-018-1251-5

Digital Library

[5]

Xihui Chen, Sjouke Mauw, and Yunior Ramírez-Cruz. 2020. Publishing Community-Preserving Attributed Social Graphs with a Differential Privacy Guarantee. Proceedings on Privacy Enhancing Technologies 2020, 4(2020), 131–152.

[6]

Wei-Yen Day, Ninghui Li, and Min Lyu. 2016. Publishing Graph Degree Distribution with Node Differential Privacy. In Proceedings of the International Conference on Management of Data. ACM, New York, NY, USA, 123–138. https://doi.org/10.1145/2882903.2926745

Digital Library

[7]

A. Fahad, N. Alshatri, et al. 2014. A Survey of Clustering Algorithms for Big Data: Taxonomy and Empirical Analysis. IEEE Transactions on Emerging Topics in Computing 2, 3 (2014), 267–279. https://doi.org/10.1109/TETC.2014.2330519

[8]

Benjamin CM Fung, Ke Wang, and Philip S Yu. 2005. Top-down specialization for information and privacy preservation. In 21st international conference on data engineering (ICDE’05). IEEE, 205–216.

Digital Library

[9]

Alberto García-Durán, Sebastijan Dumancic, and Mathias Niepert. 2018. Learning Sequence Encoders for Temporal Knowledge Graph Completion. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Belgium, 4816–4821.

[10]

Anh-Tu Hoang, Barbara Carminati, and Elena Ferrari. 2021. Privacy-Preserving Sequential Publishing of Knowledge Graphs. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 2021–2026. https://doi.org/10.1109/ICDE51399.2021.00194

[11]

Anh-Tu Hoang, Barbara Carminati, and Elena Ferrari. 2020. Cluster-based Anonymization of Knowledge Graphs. In 18th International Conference on Applied Cryptography and Network Security. Springer International Publishing, Cham, 104–123. https://doi.org/10.1007/978-3-030-57878-7_6

[12]

Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally Differentially Private Analysis of Graph Statistics. In 30th USENIX Security Symposium, USENIX Security 2021, August 11-13, 2021, Michael Bailey and Rachel Greenstadt (Eds.). USENIX Association, 983–1000.

[13]

S. Ji, P. Mittal, et al. 2017. Graph Data Anonymization, De-Anonymization Attacks, and De-Anonymizability Quantification: A Survey. IEEE Communications Surveys Tutorials 19, 2 (2017), 1305–1326. https://doi.org/10.1109/COMST.2016.2633620

Digital Library

[14]

Oluwasanmi Koyejo, Nagarajan Natarajan, Pradeep Ravikumar, and Inderjit S. Dhillon. 2015. Consistent Multilabel Classification. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, Corinna Cortes, Neil D. Lawrence, Daniel D. Lee, Masashi Sugiyama, and Roman Garnett (Eds.). 3321–3329. https://proceedings.neurips.cc/paper/2015/hash/85f007f8c50dd25f5a45fca73cad64bd-Abstract.html

[15]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[16]

Kamalkumar Macwan and Sankita Patel. 2019. Privacy Preserving Approach in Dynamic Social Network Data Publishing. In International Conference on Information Security Practice and Experience. Springer, Springer International Publishing, Cham, 381–398.

[17]

Keiichiro Oishi, Yuichi Sei, Yasuyuki Tahara, and Akihiko Ohsuga. 2020. Semantic diversity: Privacy considering distance between values of sensitive attribute. Comput. Secur. 94(July 2020), 101823. https://doi.org/10.1016/j.cose.2020.101823

[18]

Hao Peng, Haoran Li, Yangqiu Song, Vincent Zheng, and Jianxin Li. 2021. Differentially Private Federated Knowledge Graphs Embedding. In Proceedings of the 30th ACM International Conference on Information and Knowledge Management. ACM, New York, NY, USA, 1416–1425.

Digital Library

[19]

Michael Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018. Modeling Relational Data with Graph Convolutional Networks. In The Semantic Web, Aldo Gangemi, Roberto Navigli, Maria-Esther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mehwish Alam (Eds.). Springer International Publishing, Cham, 593–607.

[20]

Yuichi Sei, Hiroshi Okumura, Takao Takenouchi, and Akihiko Ohsuga. 2019. Anonymization of Sensitive Quasi-Identifiers for l-Diversity and t-Closeness. IEEE Trans. Dependable Secur. Comput. 16, 4 (2019), 580–593. https://doi.org/10.1109/TDSC.2017.2698472

Digital Library

[21]

Chih-Hua Tai, Peng-Jui Tseng, S Yu Philip, and Ming-Syan Chen. 2013. Identity protection in sequential releases of dynamic networks. IEEE transactions on Knowledge and Data Engineering 26, 3(2013), 635–651. https://doi.org/10.1109/TKDE.2013.12

[22]

Maxime Thouvenot, Olivier Curé, and Philippe Calvez. 2020. Knowledge Graph Anonymization using Semantic Anatomization. In 2020 IEEE International Conference on Big Data (Big Data). IEEE, 4065–4074. https://doi.org/10.1109/BigData50022.2020.9377824

[23]

Yang Ye, Yu Liu, Chi Wang, Dapeng Lv, and Jianhua Feng. 2009. Decomposition: Privacy Preservation for Multiple Sensitive Attributes. In Database Systems for Advanced Applications, 14th International Conference, DASFAA 2009, Brisbane, Australia, April 21-23, 2009. Proceedings(Lecture Notes in Computer Science, Vol. 5463), Xiaofang Zhou, Haruo Yokota, Ke Deng, and Qing Liu (Eds.). Springer, 486–490. https://doi.org/10.1007/978-3-642-00887-0_42

[24]

Mingxuan Yuan, Lei Chen, Philip S. Yu, and Ting Yu. 2013. Protecting Sensitive Labels in Social Network Data Anonymization. IEEE Transactions on Knowledge and Data Engineering 25, 3(2013), 633–647. https://doi.org/10.1109/TKDE.2011.259

Digital Library

Cited By

Hao YLi LChang LGu T(2023)MLDA: a multi-level k-degree anonymity scheme on directed social network graphsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-023-2759-818:2Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/s11704-023-2759-8

Index Terms

Time-Aware Anonymization of Knowledge Graphs
1. Security and privacy
  1. Database and storage security
    1. Data anonymization and sanitization

Recommendations

Cluster-Based Anonymization of Knowledge Graphs
Applied Cryptography and Network Security
Abstract
While knowledge graphs (KGs) are getting popular as they can formalize many types of users’ data in social networks, sharing these data may reveal users’ identities. Although many protection models have been presented to protect users in ...
IMR based Anonymization for Privacy Preservation in Data Mining
KMO '16: Proceedings of the The 11th International Knowledge Management in Organizations Conference on The changing face of Knowledge Management Impacting Society

Privacy Preserving Data Mining (PPDM) is a data mining research area that aims to protect individual's personal information from unsolicited or unauthorized disclosure. Privacy relates to personal information that a person would not wish others to know ...
An evolutionary feature set decomposition based anonymization for classification workloads: Privacy Preserving Data Mining

Privacy has become an important concern while publishing micro data about a population. The emerging area called privacy preserving data mining (PPDM) focus on individual privacy without compromising data mining results. An adversarial exploitation of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Privacy and Security

ACM Transactions on Privacy and Security Just Accepted

EISSN:2471-2574

Table of Contents

Copyright © 2022 Association for Computing Machinery.

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 ACM 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].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Online AM: 23 September 2022

Accepted: 06 September 2022

Revised: 02 August 2022

Received: 28 March 2022

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
648
Total Downloads

Downloads (Last 12 months)433
Downloads (Last 6 weeks)190

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hao YLi LChang LGu T(2023)MLDA: a multi-level k-degree anonymity scheme on directed social network graphsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-023-2759-818:2Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/s11704-023-2759-8

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables