PaperlayerView exact revision on arXiv

Source-linked AI summary

Link Prediction by De-anonymization: How We Won the Kaggle Social Network Challenge

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

arXiv:1102.4374v1cs.CRcs.LG

TL;DR

The paper asks whether anonymized social-network contest data can be de-anonymized using an auxiliary crawl. It combines weighted graph matching with simulated annealing, de-anonymization, and link prediction, achieving a winning test AUC of 0.981 after de-anonymizing 64.7% of the test edge set. The results highlight unresolved difficulties in preventing de-anonymization while preserving useful graph data.

  • Problem

    The paper examines how anonymized social-network contest data can be de-anonymized and used to game link-prediction evaluation.

  • Method

    The authors use weighted graph matching with simulated annealing for seed identification, then combine de-anonymization with link prediction and train on de-anonymized test portions.

  • Results

    64.7% of the test edge set was de-anonymized, and a Random Forest trained on training plus de-anonymized test data achieved a winning test AUC of 0.981.

  • Takeaways & Limitations

    The attack demonstrates that revealing the source network can enable contest gaming and that de-anonymization has consequences for future social-network competitions.

  • Takeaways & Limitations

    Ruling out de-anonymization while preserving meaningful utility remains an open question, and technical or policy restrictions may not eliminate the problem.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The Kaggle challenge anonymized a Flickr-derived social graph for probabilistic link prediction. The winning entry combined de-anonymization with link prediction, motivating new seed-identification methods and scrutiny of contest safeguards.

  • 119 teams competed, and the authors placed first by de-anonymizing much of the test set and applying machine learning to the remainder.
  • The paper identifies partial de-anonymization of real-world social-network crawls as a contribution, extending prior work on complete network snapshots.
  • Seed identification is formulated as weighted graph matching and solved with simulated annealing rather than pattern search.
  • A combined test AUC of 0.981 resulted from combining de-anonymization with standard link prediction, including training on de-anonymized test portions.
  • The authors argue that technical defenses against de-anonymization may not be foolproof and that useful, de-anonymization-resilient graph releases remain unresolved.
  • The challenge graph contained 1,133,547 nodes, 7,237,983 training edges, and 8,960 test edges split equally between true and false edges.

B. Flickr crawl dataset

The authors crawled a substantially larger Flickr graph and compared it with the competition snapshot to assess whether graph structure remained usable for de-anonymization.

  • The auxiliary Flickr crawl contained 9,124,801 nodes and 163,579,517 directed edges, substantially exceeding the competition graph.
  • Among jointly crawled origins, 6,545,560 of 7,041,554 Flickr edges matched the 6,658,755 corresponding challenge edges.
  • 95.6% cosine similarity measured agreement between the two edge sets.
  • The out-degree ratio distribution was examined for the top approximately 700 nodes by out-degree.

III. DE-ANONYMIZATION

The paper frames de-anonymization as recovering correspondence between target and auxiliary graph snapshots generated from a common underlying graph. In this Flickr setting, graph evolution and sampling introduce noise, while seed-based propagation and coverage metrics structure the attack.

  • De-anonymization seeks to recover partial node correspondence between target and auxiliary graphs derived from an underlying graph.
  • The in-degree ratio distribution was examined for the top approximately 700 nodes by in-degree.
  • The target and auxiliary Flickr snapshots differ because graph evolution, crawling, and sampling introduce noise or bias.
  • Accuracy measures the fraction of correctly de-anonymized nodes among mapped nodes, while coverage measures the fraction of nodes de-anonymized.
  • The algorithm first identifies seeds, then propagates their mappings to additional nodes using already mapped pairs as anchors.
  • Propagation can die out with too few seeds or reach many nodes when sufficiently many seeds are available.

A. Seed identification

Seed identification bootstraps de-anonymization by matching high-degree Kaggle and Flickr nodes, using neighborhood similarity and weighted graph matching rather than clique-based pattern search.

  • Seed identification bootstraps de-anonymization by identifying a small subset of corresponding Kaggle and Flickr nodes.
  • Comparison with prior approach: The proposed combinatorial optimization approach is intended to be more robust than clique-based pattern search under graph evolution, noise, and sampling information loss.The authors note that the earlier clique-search technique would also have worked in this contest setting.
  • Search space reduction: 27 of the top 30 high-in-degree nodes corresponded across the Kaggle and Flickr graphs, supporting search-space reduction.The reported correspondences were 60 among the top 80 and 84 among the top 120 nodes.
  • Similarity scores: The method compares cosine similarity between in-neighbor sets because corresponding node pairs should have roughly equal scores despite sampling error.
  • Graph matching: Candidate mappings are selected by treating cosine scores as weighted edges and minimizing differences between corresponding edge weights.This formulates seed identification as a global weighted graph matching optimization problem.
  • Seeding and automation: A manually identified mapping of 10 nodes among the top 20 was sufficient to initiate propagation, while simulated annealing offers an automated scalable alternative.The paper reports that simulated annealing handled inputs up to 100 with low false-positive and false-negative rates.

B. Propagation

Propagation extends a partial Kaggle-to-Flickr mapping by comparing already-mapped neighborhoods, while thresholds and candidate handling are adjusted across two stages.

  • Propagation procedure: Propagation repeatedly extends the partial mapping by matching each unmapped Kaggle node to the most similar Flickr node when similarity is sufficient.
  • Similarity computation: Similarity is computed as cosine similarity between already-mapped Kaggle and Flickr neighbors, treating mapped node pairs as identical.
  • Incomplete graph handling: The algorithm accounts for directed edges and incomplete crawls by ignoring out-edges unless both compared nodes were crawled.Algorithm 1 combines mapped in- and out-neighborhood information when the relevant nodes are in the crawled sets.
  • Sources of imperfection: Similarity scores can fall below 100% because the contest and later Flickr graphs differ and because mappings may contain inaccuracies.The algorithm revisits mapped nodes occasionally to correct errors using additional data.
  • Two-stage propagation: Stage 1 de-anonymizes high-degree nodes with high confidence, while stage 2 targets remaining test nodes using relaxed thresholds and up to three candidates.Stage 2 sets k = 3, removes the best-versus-second-best margin requirement, and reports the best three candidates when multiple matches exceed 0.5.

C. Results

The two-stage implementation produced approximately 120,000 mappings, with high stage-1 accuracy and substantial test-set node and edge coverage.

  • Scale and runtime: Approximately 120,000 mappings were produced after processing about 34,000 out-degree and 100,000 in-degree high-degree nodes.The first stage took a few hours, and the second stage took about 20 minutes.
  • Stage-1 accuracy: 99.3% of the 120,000 stage-1 mappings were correct.
  • Test-set results: 79.7% node coverage and 97.8% top-match accuracy were achieved on the test set.Mappings covered about 14,000 of approximately 17,600 test nodes, with multiple candidates for about 7.5% of nodes.
  • Edge results: 64.7% edge coverage and 95.2% edge accuracy were obtained across 8,960 test edges.

IV. GRAPH MATCHING VIA SIMULATED ANNEALING

The paper formulates seed identification as weighted graph matching and uses simulated annealing to search partial mappings between evolving graphs. Experiments show performance depends on dummy-node choice and can be bimodal, while runtime generalization remains data-dependent.

  • Graph matching formulation: Seed identification is formulated as weighted graph matching that minimizes differences between corresponding edge weights.The approach seeks a mapping between two weighted graphs rather than using pattern search.
  • Evaluation and partial mappings: The method is evaluated directly against ground truth because the global optimum is unknown.Dummy nodes convert the desired partial mapping into a mapping of size n − k.
  • Simulated annealing: Simulated annealing searches bijective mappings, including dummy nodes, by swapping mapped images and accepting higher-potential states probabilistically.Lower-potential transitions are always accepted, while other transitions can be accepted according to temperature and potential change.
  • Performance: For n = 20, the algorithm matches ideal performance; for n = 40, it makes no more than three errors, while n = 80 requires at least 8 dummies for good median performance.The reported observations are medians over at least 30 trials, and outcomes are often bimodal.
  • Parameters and scope: Best results occur when the selected dummy count is roughly n − m, although the application can try multiple seed sets until propagation succeeds.Automatically determining the correct dummy count may matter in other combinatorial optimization applications.
  • Limitations: The authors caution that runtime behavior should not be generalized because equivalent-error runtimes depend heavily on the data.They also do not claim simulated annealing is necessarily better than alternatives such as genetic algorithms.

A. Use of voting to increase edge coverage

The submission combines deterministic de-anonymization, unanimous voting over candidate mappings, and machine learning to predict test edges. De-anonymization and voting provide broad coverage, while the remaining machine-learning subset is substantially harder.

  • De-anonymization and voting: 64.7% of test cases were covered by de-anonymization, with additional cases handled through candidate voting.The method prunes de-anonymization outputs and reruns propagation before applying the combined procedure.
  • Coverage: 96.0% node coverage and 92.6% edge coverage were achieved; 57.0% of edges had unique candidates and voting was applied to 35.6%.Voting produced unanimous results for 18.7% of the 35.6% of edges.
  • Voting behavior: Voting uncovered only non-edges, 98.1% of which were true non-edges, because higher-degree coverage and unanimity favor confident non-edge predictions.The authors explain that random node pairs are more likely not to have an edge, making unanimous non-edge votes more likely.
  • Combination procedure: The combined procedure outputs de-anonymization predictions for uniquely mapped nodes, unanimous vote predictions for candidate sets, and machine-learning scores otherwise.Voting returns an edge or non-edge only when all candidate pairs agree; otherwise the machine-learning score is used.
  • Machine learning: The Random Forest uses 25 neighborhood features, including localized random walks, and is trained using de-anonymization-derived ground truth.Training sets contain 3,000–4,200 examples, while validation sets contain roughly 1,000–2,000 examples.
  • Machine-learning results: The Random Forest achieved AUC 0.935 to 0.945 on validation, AUC 0.953 on the full test set, and AUC 0.881 on the uncovered ML set.The full-test figure is qualified because part of the test set was used for training; the ML set is difficult for both de-anonymization and prediction.

VI. RELATED WORK

The related work situates the paper at the intersection of graph-based link prediction, social-network de-anonymization, and graph matching. Prior methods include structural features, pattern search, and exact or approximate matching techniques.

  • Link prediction: Prior link-prediction work uses graph structural analysis, including features from Liben-Nowell and Kleinberg, but the graph size limited feature use on commodity hardware.The paper’s link-prediction method also draws on these structural features.
  • Link prediction: A competing team achieved AUC 0.969 using Random Forests over 94 selected features with pure link prediction.This result provides a comparison point for the contest’s non-de-anonymization approaches.
  • Social-network de-anonymization: Earlier de-anonymization studies targeted specific nodes and edges through small-subgraph pattern search or used another social network as auxiliary data.The paper extends this line of work to contest gaming through an auxiliary Flickr crawl.
  • Graph matching: Inexact graph matching has been addressed with approaches including genetic algorithms, simulated annealing, expectation maximization, decision trees, and neural networks.The paper positions simulated annealing within this broader algorithmic literature.
  • Graph matching: Prior weighted graph-matching work sought optimal solutions whose techniques were limited to small numbers of nodes.The paper instead studies a scalable approximate approach.

VII. DISCUSSION

The discussion argues that de-anonymization can undermine contest goals and create privacy concerns, while restrictions and technical defenses have important limitations. The authors therefore emphasize rule design, verification, and the unresolved challenge of releasing useful but resilient graph data.

  • Contest implications: The authors’ primary goal was to expose the possibility of de-anonymization in machine-learning contests and the tension between outside information and cheating prevention.They frame this as a broader question about contest policy and data use.
  • Privacy and data access: Public underlying data reduces privacy risk but provides high-quality material for gaming, whereas nonpublic data can still be cross-referenced with a related public dataset.Imperfect correlation between datasets leaves the resulting threat to contest fidelity unclear.
  • Contest safeguards: Restricting external data is necessary but arguably insufficient because contestants may still attempt de-anonymization.The paper discusses source-code and human-readable algorithm verification as one possible additional safeguard.
  • Verification limitations: Source-code verification can catch de-anonymization used alone, but may miss de-anonymization used to bridge a small gap before machine-learning training.The authors identify overfitting as a loophole in this verification approach.
  • Technical defenses: Preventing de-anonymization is difficult because prior research demonstrates feasibility across datasets, while graph anonymization methods often exclude globally structured auxiliary information.The authors therefore do not consider existing graph k-anonymity techniques effective for social-network graphs.
  • Alternative privacy approach: Differential privacy could avoid relying on anonymization, but it would restrict supported algorithms and may require moving beyond a release-and-forget model.The paper presents this as a potential alternative rather than an implemented solution.

VIII. CONCLUSIONS & OPEN PROBLEMS

The paper presents de-anonymization as an effective attack on anonymized link-prediction contests and combines it with link prediction to win the Flickr-based challenge. It also identifies open questions about preventing de-anonymization while preserving useful graph data and about exploiting web information more broadly.

  • Conclusions: The authors describe a de-anonymization attack that won Kaggle’s IJCNN 2011 Social Network Challenge.The competition dataset had scrubbed user identities, but identifying Flickr as its source enabled the attack.
  • Conclusions: 64.7% of the test edge-set was de-anonymized, and a Random Forest trained on training plus de-anonymized test data achieved a winning test AUC of 0.981.The entry combined de-anonymization with standard link-prediction features.
  • Conclusions: The attack combines augmented link-prediction training with probabilistic predictions from de-anonymization and link prediction.This combination is presented as a technical contribution beyond the attack itself.
  • Open Problems: Forbidding outside data sources and requiring source-code submissions may not eliminate contest gaming through de-anonymization.The authors argue that ruling out de-anonymization while preserving meaningful utility remains an open question.
  • Open Problems: The paper points to web-derived statistical, aggregate, semantic, and node- or edge-attached information as broader directions for link prediction.The de-anonymization attack is characterized as an extreme case of incorporating information publicly available on the web.
Loading 1102.4374v1…