Change of Guard: The Next Generation of Social Graph De-anonymization Attacks


Past decade has seen active research in social graph de-anonymization with a variety of algorithms proposed. Previous algorithms used handcrafted tricks and were locked in a co-evolution of attack and defense with design of anonymization systems. We present a radically improved algorithm for re-identifying social network data. We use a machine learning system based on random forests to identify nodes using their structural features. The algorithm can handle a variety of threat models and is agnostic to the de-anonymization scheme employed. This is substantiated by our evaluation using three real-world social graph datasets under four threat models. Our algorithm is consistently better than the previous generation of algorithms as confirmed by comparison with seven seed-based and seedless attacks based on two real-world social networks. It is time for attacks based on heuristics to be replaced by learning models.



author = {Sharad, Kumar},
title = {Change of Guard: The Next Generation of Social Graph De-anonymization Attacks},
booktitle = {Proceedings of the 2016 ACM Workshop on Artificial Intelligence and Security},
series = {AISec '16},
year = {2016},
isbn = {978-1-4503-4573-6},
location = {Vienna, Austria},
pages = {105--116},
numpages = {12},
url = {},
doi = {10.1145/2996758.2996763},
acmid = {2996763},
publisher = {ACM},
address = {New York, NY, USA},
keywords = {de-anonymization, machine learning, privacy, social networks},