Skip to main content

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

Author(s): Ji, Shouling; Wang, Ting; Chen, Jianhai; Li, Weiqing; Mittal, Prateek; et al

To refer to this page use:
Abstract: 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.
Publication Date: 5-Jun-2017
Citation: Ji, Shouling, Wang, Ting, Chen, Jianhai, Li, Weiqing, Mittal, Prateek, Beyah, Raheem. (2019). De-SAG: On the De-Anonymization of Structure-Attribute Graph Data. IEEE Transactions on Dependable and Secure Computing, 16 (4), 594 - 607. doi:10.1109/tdsc.2017.2712150
DOI: doi:10.1109/tdsc.2017.2712150
ISSN: 1545-5971
EISSN: 1941-0018
Pages: 594 - 607
Type of Material: Journal Article
Journal/Proceeding Title: IEEE Transactions on Dependable and Secure Computing
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.