# An Automated Social Graph De-anonymization Technique

arXiv: https://arxiv.org/abs/1408.1276 · HTML: https://mlsanity.com/paper/1408.1276/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Aug 2014.

## Built on by (most cited first, 1 of 1)

- ["I'm not for sale" -- Perceptions and limited awareness of privacy risks by digital natives about location data](https://mlsanity.com/paper/2502.11658/) (2025)

## Abstract (arXiv)

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.