k-Anonymity on Graphs Using the Szemerédi Regularity Lemma

This is the authors' abstract. We don't add key points for this paper.

Graph anonymization aims at reducing the ability of an attacker to identify the nodes of a graph by obfuscating its structural information. In k-anonymity, this means making each node indistinguishable from at least other k-1 nodes. Simply stripping the nodes of a graph of their identifying label is insufficient, as with enough structural knowledge an attacker can still recover the nodes identities. We propose an algorithm to enforce k-anonymity based on the Szemerédi regularity lemma. Given a graph, we start by computing a regular partition of its nodes. The Szemerédi regularity lemma ensures that such a partition exists and that the edges between the sets of nodes behave quasi-randomly. With this partition to hand, we anonymize the graph by randomizing the edges within each set, obtaining a graph that is structurally similar to the original one yet the nodes within each set are structurally indistinguishable. Unlike other k-anonymization methods, our approach does not consider a single type of attack, but instead it aims to prevent any structure-based de-anonymization attempt. We test our framework on a wide range of real-world networks and we compare it against another simple yet widely used k-anonymization technique demonstrating the effectiveness of our approach.