An Automated Social Graph De-anonymization Technique
This addresses privacy vulnerabilities in social network anonymization, enabling quick evaluation of anonymization techniques, though it is incremental as it builds on existing de-anonymization methods.
The paper tackles the problem of re-identifying nodes in anonymized social networks by developing an automated technique using machine learning, which achieves significant true positive rates even with small false positive rates and works effectively with limited training samples.
We present a generic and automated approach to re-identifying nodes in anonymized social networks which enables novel anonymization techniques to be quickly evaluated. It uses machine learning (decision forests) to matching pairs of nodes in disparate anonymized sub-graphs. The technique uncovers artefacts and invariants of any black-box anonymization scheme from a small set of examples. Despite a high degree of automation, classification succeeds with significant true positive rates even when small false positive rates are sought. Our evaluation uses publicly available real world datasets to study the performance of our approach against real-world anonymization strategies, namely the schemes used to protect datasets of The Data for Development (D4D) Challenge. We show that the technique is effective even when only small numbers of samples are used for training. Further, since it detects weaknesses in the black-box anonymization scheme it can re-identify nodes in one social network when trained on another.