Link inference attacks reveal hidden relations in privacy graphs
Link Inference Attack on Privacy-Preserving Knowledge Graphs
Cryptography and Security
Summary
Sometimes, people remove sensitive connections from knowledge graphs, thinking this keeps such information secret. The authors show that even hidden links leave clues in the graph's structure that can be detected. They designed an attack that uses these clues to recover the hidden links with high accuracy. This means deleting connections might not be enough to protect privacy in these graphs.
What this means in practice
- •For hospital data teams: Detect and assess risks of recovering hidden patient relationships in medical knowledge graphs after edge removal.
- •For social media platform engineers: Evaluate how removed social connections might still be inferred from public graph data to improve user privacy.
Authors
Emna Bouguerra, Ibtissam Harrouche, Ferran Alborch, Melek Önen
Abstract
Knowledge Graphs (KGs) are widely used to store and share structured information across sensitive domains such as healthcare, fi- nance, and social networks. A common privacy practice is to delete sen- sitive relations before publishing the graph, under the assumption that removing edges is sufficient to prevent their recovery. In this paper, we challenge this assumption and show that even when a relation is fully or partially hidden, its existence leaves structural traces in the public graph that can be exploited to recover it with high accuracy. To this end, we propose a link inference attack that operates on the topology of the public graph, and evaluate it under two privacy scenarios that differ in how the adversary exploits the knowledge available to him. In the first setting where the adversary exploits all topological information, the attack achieves near-perfect discrimination (AP = 0.949, ROC-AUC = 0.999), while in the more realistic one where the adversary makes use of some semantic information, it recovers up to 74% of hidden edges. Build- ing on these results, we further conduct a structural analysis to identify which topological properties of the graph drive the attack success, re- vealing that privacy risk is not uniform across entities and that certain structural patterns make specific relations significantly more vulnerable to inference than others.