You Can't See Me: Anonymizing Graphs Using the Szemerédi Regularity Lemma

Daniele Foffano, Luca Rossi, Andrea Torsello

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


Complex networks gathered from our online interactions provide a rich source of information that can be used to try to model and predict our behavior. While this has very tangible benefits that we have all grown accustomed to, there is a concrete privacy risk in sharing potentially sensitive data about ourselves and the people we interact with, especially when this data is publicly available online and unprotected from malicious attacks. k-anonymity is a technique aimed at reducing this risk by obfuscating the topological information of a graph that can be used to infer the nodes' identity. In this paper we propose a novel algorithm to enforce k-anonymity based on a well-known result in extremal graph theory, 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 almost randomly. With this partition, 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. We test the proposed approach on real-world networks extracted from Facebook. Our experimental results show that the proposed approach is able to anonymize a graph while retaining most of its structural information.

Original languageEnglish
Article number7
Pages (from-to)1-6
JournalFrontiers in Big Data
Publication statusPublished - 31 May 2019
Externally publishedYes


  • anonymity
  • graph
  • privacy
  • regularity lemma
  • social networks

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Science (miscellaneous)
  • Information Systems


Dive into the research topics of 'You Can't See Me: Anonymizing Graphs Using the Szemerédi Regularity Lemma'. Together they form a unique fingerprint.

Cite this