Exposed by design: Topology-based privacy attacks and mitigations for knowledge graphs

Knowledge graphs (KGs) are data structures that have recently seen widespread adoption by industries for training powerful and accurate machine learning models. The advantages of KGs unfortunately come with a high cost in terms of security and privacy exposures because they increasingly use privacy-sensitive data. The common procedure to protect the confidentiality of such data by organizations is usually to publish their knowledge graphs, only partially, i.e., ensuring that privacy-sensitive information is not disclosed while the remaining subgraph becomes publicly accessible. In this paper, we show that this approach is vulnerable against privacy attacks and demonstrate that an adversary can easily infer the hidden part of the graph by simply exploiting the topology of the public KG (and nothing more). We investigate privacy attacks against KGs whose goal is to infer some private information from the graph. With this aim, we identify the most impactful features of KG topology on its leakage and design three attacks, incrementally: (1) a link inference attack to predict whether a node in the public graph exhibits a link in the private one; (2) a triple inference attack to concretely identify the hidden link with the actual tail node; and, finally, (3) a graph reconstruction attack to partially recover the hidden graph. Our experimental study shows that these attacks are successful across multiple knowledge graphs with diverse topology (up to 90% PR-AUC for link inference, 80% MRR for triple inference, and 45% graph recovery). Furthermore, to mitigate this vulnerability, we propose a topology-aware defense mechanism named Chameleon that offers KG privacy protection while guaranteeing an acceptable utility level. To address the privacy-utility trade-off, unlike existing defense strategies, Chameleon identifies the most impactful edges in the public graph, taking into account their topological features, and perturbs the graph to prevent the adversary identifies and exploit them. Through additional experiments, we show that with moderate graph perturbation budgets, Chameleon reduces attack accuracy from 92% to 50% while maintaining acceptable utility with MRR of 52% to 31% on the link prediction task. Our study, therefore, emphasizes that graph topology alone is a fundamental source of privacy leakage in KGs and that future privacy protection solutions should be topology-aware.