Privacy-preserving sequential publishing of knowledge graphs

Knowledge graphs (KGs) are widely shared because they can model both users' attributes as well as their relationships. Unfortunately, adversaries can re-identify their victims in these KGs by using a rich background knowledge about not only the victims' attributes but also their relationships. A preliminary work to deal with this issue has been proposed in [1] which anonymizes both user attributes and relationships, but this is not enough. Indeed, adversaries can still re-identify target users if data providers publish new versions of their anonymized KGs. We remedy this problem by presenting the kw-Time-Varying Attribute Degree (kw-tad) principle that prevents adversaries from re-identifying any user appearing in w continuous anonymized KGs with a confidence higher than rac{1}{k}. Moreover, we introduce the Cluster-based Time-Varying Knowledge Graph Anonymization Algorithm to generate anonymized KGs satisfying kw-tad. Finally, we prove that even if data providers insert/re-insert/update/delete their users, the users are protected by kw-tad.