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

Giorgia Minello, Luca Rossi, Andrea Torsello

Abstract

Graph anonymization aims at reducing the ability of an attacker to identify the nodes of a graph by obfuscating its structural information. In <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -anonymity, this means making each node indistinguishable from at least other <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k-1$</tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$k$</tex-math></inline-formula> -anonymization technique demonstrating the effectiveness of our approach.
BibTeX
@article{minello2021k,
  author = {Giorgia Minello and Luca Rossi and Andrea Torsello},
  title = {{k-Anonymity on Graphs Using the Szemerédi Regularity Lemma}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2021},
  doi = {10.1109/tnse.2020.3020329},
}

Loading related content...

Figure