Protecting Privacy in Knowledge Graphs With Personalized Anonymization

Knowledge graphs (KGs) are emerging data models allowing data providers to share data. This data sharing might bring new knowledge and collaborations, with evident benefits for providers. However, since KGs might contain sensitive information about users, it is of utmost importance to ensure KG anonymization before publishing. Recently, some proposals have addressed the problem of KGs' anonymization based on the k-anonymity principle. These techniques propose to anonymize the whole dataset with the same anonymization level. However, in a contest where data are collected from different users, it is crucial to consider also users' preferences on the anonymization level to adopt for their data. To cope with this requirement, this paper presents the Personalized k-Attribute Degree (p-k-ad) principle. It allows users to specify their anonymity levels (the k values) while preventing adversaries from re-identifying them with a confidence higher than 1/k with their specified k. Moreover, we design the Personalized Cluster-Based Knowledge Graph Anonymization Algorithm (PCKGA) to generate anonymized KGs satisfying p-k-ad. We conduct experiments on four real-life datasets and show that PCKGA greatly improves the quality of anonymized KGs comparing to previous algorithms.