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

Giorgia Minello, Luca Rossi, Andrea Torsello

Research output: Journal article publicationJournal articleAcademic researchpeer-review


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.

Original languageEnglish
Article number9181421
Pages (from-to)1283-1292
Number of pages10
JournalIEEE Transactions on Network Science and Engineering
Issue number2
Publication statusPublished - 1 Apr 2021
Externally publishedYes


  • Anonymity
  • graph
  • privacy
  • regularity lemma
  • social networks.

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'K-Anonymity on Graphs Using the Szemerédi Regularity Lemma'. Together they form a unique fingerprint.

Cite this