De-SAG: On the De-Anonymization of Structure-Attribute Graph Data

Shouling Ji, Ting Wang, Jianhai Chen, Weiqing Li, Prateek Mittal, Raheem Beyah

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


In this paper, we study the impacts of non-Personal Identifiable Information (non-PII) on the privacy of graph data with attribute information (e.g., social networks data with users' profiles (attributes)), namely Structure-Attribute Graph (SAG) data, both theoretically and empirically. Our main contributions are two-fold: (i) we conduct the first attribute-based anonymity analysis for SAG data under both preliminary and general models. By careful quantification, we obtain the explicit correlation between the graph anonymity and the attribute information. We also validate our analysis through numerical and real world data-based evaluations and the results indicate that the non-PII can also lead to significant anonymity loss; and (ii) according to our theoretical analysis, we propose a new de-Anonymization framework for SAG data, namely De-SAG, which takes into account both the graph structure and the attribute information to the best of our knowledge. By extensive experiments, we demonstrate that De-SAG can significantly improve the performance of state-of-The-Art graph de-Anonymization attacks. Our attribute-based anonymity analysis and de-Anonymization framework are expected to provide data owners and researchers a more complete understanding on the privacy vulnerability of graph data, and thus shed light on future graph anonymization and de-Anonymization research.

Original languageEnglish (US)
Article number7938634
Pages (from-to)594-607
Number of pages14
JournalIEEE Transactions on Dependable and Secure Computing
Issue number4
StatePublished - Jul 1 2019

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'De-SAG: On the De-Anonymization of Structure-Attribute Graph Data'. Together they form a unique fingerprint.

Cite this