Quantifying Graph Anonymity, Utility, and De-anonymity

Shouling Ji, Tianyu Du, Zhen Hong, Ting Wang, Raheem Beyah

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations


In this paper, we study the correlation of graph da-ta's anonymity, utility, and de-anonymity. Our main contributions include four perspectives. First, to the best of our knowledge, we conduct the first Anonymity-Utility-De-anonymity (AUD) correlation quantification for graph data and obtain close-forms for such correlation under both a preliminary mathematical model and a general data model. Second, we integrate our AUD quantification to SecGraph [31], a recently published Secure Graph data sharing/publishing system, and extend it to Sec-Graph+. Compared to SecGraph, SecGraph+ is an improved and enhanced uniform and open-source system for comprehensively studying graph anonymization, de-anonymization, and utility evaluation. Third, based on our AUD quantification, we evaluate the anonymity, utility, and de-anonymity of 12 real world graph datasets which are generated from various computer systems and services. The results show that the achievable anonymity/de-anonymity depends on multiple factors, e.g., the preserved data utility, the quality of the employed auxiliary data. Finally, we apply our AUD quantification to evaluate the performance of state-of-the-art anonymization and de-anonymization techniques. Interestingly, we find that there is still significant space to improve state-of-the-art de-anonymization attacks. We also explicitly and quantitatively demonstrate such possible improvement space.

Original languageEnglish (US)
Title of host publicationINFOCOM 2018 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Electronic)9781538641286
StatePublished - Oct 8 2018
Event2018 IEEE Conference on Computer Communications, INFOCOM 2018 - Honolulu, United States
Duration: Apr 15 2018Apr 19 2018

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other2018 IEEE Conference on Computer Communications, INFOCOM 2018
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Quantifying Graph Anonymity, Utility, and De-anonymity'. Together they form a unique fingerprint.

Cite this