Link prediction by de-anonymization: How We Won the Kaggle Social Network Challenge

By Arvind Narayanan, Elaine Shi, Benjamin I. P. Rubinstein. 2011

180 citations recorded by the source corpus.

This paper describes the winning entry to the IJCNN 2011 Social Network Challenge run by Kaggle.com. The goal of the contest was to promote research on real-world link prediction, and the dataset was a graph obtained by crawling the popular Flickr social photo sharing website, with user identities scrubbed. By de-anonymizing much of the competition test set using our own Flickr crawl, we were able to effectively game the competition. Our attack represents a new application of de-anonymization to gaming machine learning contests, suggesting changes in how future competitions should be run. We introduce a new simulated annealing-based weighted graph matching algorithm for the seeding step of de-anonymization. We also show how to combine de-anonymization with link prediction—the latter is required to achieve good performance on the portion of the test set not de-anonymized—for example by training the predictor on the de-anonymized portion of the test set, and combining probabilistic predictions from de-anonymization and link prediction.

Subfields: Artificial Intelligence, Sociology and Political Science, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Graph Learning

Citations in the corpus

SIGMa: simple greedy matching for aligning large knowledge bases (2012, methodology): “agation’ algorithm has been used to align social network graphs in [22], though with a very different objective function (they define weights in each graphs and want to align edges which have similar weights).”
Leakage in data mining: formulation, detection, and avoidance (2011, methodology): “As another example, the pneumonia detection database in the INFORMS 2008 challenge discussed in Perlich et al. [2008] and Rosset et al. [2010] implies that a certain combination of missing diagnosis code and some other features is highly informative of the target.”
Privacy Violations Using Microtargeted Ads: A Case Study (2010, background): “This work, as well as a variety of others [5, 4, 26, 35, 34], have demonstrated that ad-hoc approaches to protecting privacy inevitably fail in the world of creative and sophisticated adversaries in possession of auxiliary information from multiple sources.”
Protecting privacy when mining and sharing user data (2012, background): “A variety of other e↵orts for sharing other types of user data illustrate the same point – an utter failure of ad-hoc anonymization techniques to adequately protect privacy [16,146,200].”