Session 1: Social Systems and Notifications

WPES’17, October 30, 2017, Dallas, TX, USA.

Blind De-anonymization Attacks using Social Networks
Wei-Han Lee

Princeton University
weihanl@princeton.edu

Changchang Liu

Princeton University
cl12@princeton.edu

Prateek Mittal

Ruby B. Lee

Princeton University
pmittal@princeton.edu

Princeton University
rblee@princeton.edu
have access to rich auxiliary information (also called backgroundinformation) from other channels [1, 2, 5, 7–12, 14, 15, 17, 22].
Today, many individuals have accounts in various social networks such as Facebook, Twitter, Google+, Myspace and Flickr.
Based on the inherent cross-site correlations, Narayanan et al. [15]effectively de-anonymized a Twitter dataset by utilizing a Flickr
dataset as auxiliary information. Furthermore, Nilizadeh et al. [17]exploited the community structure of a graph to de-anonymizesocial networks. Other public datasets may also contain individual
behavior information. For instance, Srivatsa et al. [22] proposed tode-anonymize a set of location traces based on a social network.
They demonstrated that a contact graph identifying meetings between anonymized users in the location traces can be structurally
correlated with the corresponding social network graph.
However, previous work on de-anonymization attacks have several limitations: 1) most previous works [14, 15, 17] rely on a seedidentification process. To obtain the useful seeds, they assume thatthe attacker possesses detailed information about a small number ofmembers of the target network. They also assume that the attacker
can determine if these members are also present in his auxiliary network (e.g., by matching user names and other contextual information). Furthermore, these methods may suffer from the imprecisionof the adversary’s background knowledge (misidentified seeds); 2)
existing seed-free de-anonymization techniques [7, 18] have limited
accuracy because they only utilize limited structural informationof the data. In this paper, we aim to solve these problems by proposing a novel blind (i.e., seed-free) de-anonymization technique andexploring fine-grained structure information of graph topologies.
Overall, we make the following contributions:

ABSTRACT
It is important to study the risks of publishing privacy-sensitive data.
Even if sensitive identities (e.g., name, social security number) were
removed and advanced data perturbation techniques were applied,
several de-anonymization attacks have been proposed to re-identify
individuals. However, existing attacks have some limitations: 1)
they are limited in de-anonymization accuracy; 2) they requireprior seed knowledge and suffer from the imprecision of such seed
information.
We propose a novel structure-based de-anonymization attack,which does not require the attacker to have prior information(e.g., seeds). Our attack is based on two key insights: using multihop neighborhood information, and optimizing the process of deanonymization by exploiting enhanced machine learning techniques. The experimental results demonstrate that our method isrobust to data perturbations and significantly outperforms the stateof-the-art de-anonymization techniques by up to 10× improvement.

KEYWORDS
De-anonymization; Graph Anonymity; Machine Learning;

1

Shouling Ji

Zhejiang University, China andGeorgia Tech, USA
sji@gatech.edu

INTRODUCTION

Privacy-sensitive data (social relationships, mobility traces, medical records, etc.) are increasingly becoming public to facilitate
data-mining researchers and applications. To protect users’ privacy,
data anonymization techniques have been the focus of extensive
investigations [6, 12, 19].
Most privacy-sensitive data are closely related to individual behavior, and thus contain rich structural/graph-theoretic characteristics. For example, social networks can be modeled as graphs ina straightforward manner. Mobility traces can also be modeled asgraph topologies [22]. However, even equipped with sophisticatedanonymization techniques, the privacy of structural data still suffers from de-anonymization attacks assuming that the adversaries• We present a novel de-anonymization technique, which does not
require adversaries to have any prior information (e.g., seeds). In
our method, 1) we propose the nK-series to incorporate multi-hop
neighbors’ information in graph structures as novel features inour de-anonymization attack; 2) we jointly optimize the matchingfor users between the anonymized graph and the auxiliary graphby leveraging a machine learning technique: pseudo relevance
feedback support vector machine (PRF-SVM).
• We show that our method is practical and effective: our attack isrobust to data perturbations and has significant de-anonymization
advantages over existing approaches with up to 10× improvement.
Our method demonstrates that structural data can be effectively
de-anonymized even without any seed information.

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from permissions@acm.org.
WPES’17, October 30, 2017, Dallas, TX, USA.
© 2017 Association for Computing Machinery.
ACM ISBN 978-1-4503-5175-1/17/10. . . $15.00
https://doi.org/10.1145/3139550.3139562

1

Session 1: Social Systems and Notifications$QRQ\PL]HGJUDSK2XWSXW

Q.VWUXFWXUH
IRUHDFKQRGH

&DOFXODWHGLYHUVLW\VFRUH
&DOFXODWHSRSXODULW\VFRUH

'HDQRQ\PL]HGVHW$X[LOLDU\ JUDSKWPES’17, October 30, 2017, Dallas, TX, USA.

35)690

&DOFXODWHSRSXODULW\VFRUH
Q.VWUXFWXUH
IRUHDFKQRGH

&DOFXODWHGLYHUVLW\VFRUH

&DOFXODWHVWUXFWXUHVFRUH

&DOFXODWHVLPLODULW\VFRUH)RUP*URXSSDLU

&DOFXODWHVWUXFWXUHVFRUH

Figure 1: Mechanism for our blind de-anonymization attack.

2

BLIND DE-ANONYMIZATION ATTACKS

Next, we start de-anonymizing the anonymized data in an iterative manner.
Step 3: For each round, we calculate the popularity score foreach node, which evaluates its relationships with the set of deanonymized nodes in the previous round (the set of de-anonymized
nodes is empty in the initial round). We denote N t as the set ofnodes that have been de-anonymized after the t-th iteration, whereN t is an empty set for the first round. We define the popularity
score of node a, PS(a), as the Jaccard similarity [21] between theset of neighbors N (a) for each node a and N t as:Previous works on structure-based de-anonymization do not fully
utilize fine-grained graph-theoretic information. For instance, only
one-hop neighbors have been utilized in [14], and very limited structural information has been leveraged in [7]. Also, most existing
work rely on assumptions that the adversary has prior information
or some ground truth (e.g., the seed information in [15]). However,seed-based de-anonymization attacks have some issues in practice:1) the seed identification process usually requires heavy computational complexity [15]; 2) misidentified seeds may seriously decrease
the de-anonymization capability.
We propose a general, blind (seed-free) de-anonymization attack.
Figure 1 outlines our method, which consists of the following key
steps on each of the anonymized graph, G a , and the auxiliary graph,
Gu . Our proposed nK-series aims to capture fine-grained structural information of each node, and the PRF-SVM aims to jointly
de-anonymize the nodes. By exploring richer and finer-grained
structural information of the graphs, our method can achieve betterde-anonymization performance without requiring the adversaries
to have any prior information (e.g., seeds).
Step 1: We first explore multi-hop neighbor information byproposing our new nK-series structural features for each node.
nK-series: Inspired by the idea of the dK-series [13] for characterizing structural statistics of a graph, we propose the nK-series to
describe structural features of each node in a fine-grained manner,by incorporating the structural information of its multi-hop neighbors. nK0 represents the degree of the node, i.e., the number of its
neighbors. nK1 captures the degree histogram of its neighbors andnK2 captures the degree histogram of its 2-hop neighbors. Here, we
focus our research on nK0, nK1, and nK2 to construct the nK structural features of each node a as v(a) = [nK0(a), nK1(a), nK2(a)]T .
Step 2: Based on the nK structural features, we calculate thediversity score for each node a, which measures the richness of thestructuralcharacteristics of this node and is defined as DS(a) =i v˜i (a) log v˜i (a)log(dim(ṽ(a))) . where ṽ(a) denotes the normalized structural fea-

PS(a) = J (N t , N (a)) = |N t ∩ N (a)|/|N t ∪ N (a)|(1)|A∩B |

where J (A, B) is the Jaccard similarity, J (A, B) = |A∪B | , and PS(a) ∈[0, 1]. A higher popularity score represents a closer relationship between this anonymized node and those previously de-anonymized
nodes. In addition to the diversity score, the popularity score canalso be leveraged to evaluate the structural characteristics of eachanonymized node.
Step 4: Subsequently, we compute the structure score (SS) for
each node a as SS(a) = DS(a) + c · PS(a). where c is a pre-definedparameter to balance the diversity score and the popularity score.
Step 5: Next, we group the nodes in the anonymized graphand the auxiliary graph according to their structure scores. Ourgrouping process works as follows: for the t-th iteration, we selectNдr oup nodes with higher SS from the anonymized graph and theauxiliary graph to form the group pair Cat (for the anonymized
graph) and Cut (for the auxiliary graph). Note that for the first
iteration, we select those nodes with higher DS (since PS = 0 for
the initial round).
Step 6: For each group pair, we rank each potential pair of nodes
according to the similarities between their nK structural features.
For each node a in Cat and node b in Cut , we evaluate the similarity between their nK structural features by computing the cosine
v(a),v(b)
similarity [4] between v(a) and v(b) as Sim(a, b) = v(a)  v(b)  .
22
Larger cosine similarity score means two nodes are more similar.
Furthermore, to emphasize the differences between node pairs andthus to improve the node matching performance, we can transformthe above similarity linearly asv(a)ture vector of a, i.e., ṽ(a) = v(a)  . dim(ṽ(a)) denotes the dimen2
sion for ṽ(a). Here, i v˜i (a) log v˜i (a) is actually similar to entropy
in information theory [3], which evaluates the amount of information stored in v˜i (a), and log(dim(ṽ(a))) is just for normalizing thediversity score so that DS(a) ∈ [0, 1]. A higher diversity score meansthat this node has more distinguishable structural characteristics.

max (Sim(a, d)) − Sim(a, b)

S(a, b) = max (Sim(a, d)) −d ∈Cut2d ∈Cutvar (Sim(a, :))(2)

Session 1: Social Systems and Notifications

WPES’17, October 30, 2017, Dallas, TX, USA.

where Sim(a, :) is a vector consisting of Sim(a, d) for d ∈ Cut andvar (·) is the variance of a vector.
Step 7: Next, we leverage machine learning techniques: pseudo
relevance feedback with support vector machine (PRF-SVM), to
re-rank these potential pairs of nodes.
Specifically, we view this node-matching process from a classification perspective, i.e., we aim to classify all the possible pairsof nodes as two categories: matched or unmatched. For each SVM
iteration, we select the top Nt r ain node pairs with the highest similarity scores and the bottom Nt r ain node pairs with the lowest
similarity scores as the training data, labeling them as matched andunmatched, respectively.
With these training node pairs, we apply SVM to classify theremaining node pairs. The SVM method would result in a classification hyperplane. Based on this hyperplane, each possible nodepair would be given a value dis(a, b) derived according to its distance from the hyperplane. We define a confidence score SVM(a, b)
for each potential node pair (a, b), which is linearly normalized as|dis(a,b) |−dmin
SVM(a, b) = d, where dmax , dmin represent the maxmax −dminimum and minimum distance from the hyperplane computed overˆ b) isall the remaining node pairs. The updated similarity score S(a,obtained by integrating the original similarity score S(a, b) in Eq. 2
with the confidence score SVM(a, b) asˆ b) = S(a, b) · SVM(a, b)αS(a,The Twitter dataset [17] captures the connections between users
who mentioned each other at least once between March 24th, 2012
and April 25th, 2012, and contains two different graphs named Twitter (small) with 9,745 users and 50,164 edges, and Twitter (large)
with 90,331 users and 358,422 edges.
The Gowalla dataset consists of a social graph and a mobility
trace dataset [20]. The social graph contains 196,591 users with
950,327 edges. The mobility trace consists of 6.44M checkins generated by these users. To better evaluate the performance of our
method, we leverage the techniques in [20] to construct four graphsfrom the mobility trace dataset with different recalls and precisions,denoted by M1, M2, M3, and M4. All the four mobility trace graphs
contain 196,591 users, and the corresponding number of edges are
659,186, 829,375, 919,671, 1,070,790, respectively.
To evaluate the performance of our de-anonymization attack,
we consider a popular perturbation method of Hay et al. [6], whichapplies a sequence of r random edge deletions followed by r random
edge insertions (a similar perturbation process has been utilized
for the de-anonymization attacks in [17]). Here, we define noise(perturbations) as the extent of edge modification, i.e., the ratior .
of altered edges r to the total number of edges M, i.e., noise = M
Note that we add the same amount of noise to the original graph of
the Collaboration, Twitter datasets to obtain the anonymized graphand the auxiliary graph, respectively. For Gowalla mobility trace,
we utilize its social network structure for de-anonymization attacks.
Furthermore, we vary the system parameters of our method andset c = 2, Nдr oup = 1000, Nt r ain = 1250, α = 1 for achieving thebest performance in our experiments.
We utilize Accuracy to evaluate the de-anonymization performance. Accuracy is the ratio of the correctly de-anonymized nodes
out of all the overlapped nodes between the anonymized graph andcor
the auxiliary graph, i.e., Accuracy = |VN∩V, where Ncor is theau|number of correctly de-anonymized nodes and Va , Vu represent thesets of nodes in the anonymized and auxiliary graph, respectively.

(3)

where α is a parameter that emphasizes the importance of theconfidence score SVM(a, b) in Eq. 3. A new ranking list is thusˆ b). This
generated based on these updated similarity scores, S(a,process of classification and re-ranking can be conducted iteratively
until a stable classification result is obtained.
Step 8: Finally, we extract the matched pairs of nodes based on
the classification result of PRF-SVM in Step 7 and then update theset of de-anonymized nodes N t . We iteratively repeat Step 3-Step 7
until we cannot de-anonymize any more nodes.
Note that although our method is seed-free, it can be directly
generalized to incorporate seed knowledge if the adversary hassuch prior information. Given a set of known seeds, these seeds
could be considered as the matched result in the first group of ouralgorithm, and the iteration for finding more matched nodes canbe implemented consequently as shown in Figure 1.

3

3.2

EXPERIMENTAL ANALYSIS

In this section, we compare our attack with the state-of-the-art deanonymization techniques [7, 17], to show the significant advantage
of our approach (up to 10× improvement in de-anonymization
accuracy). For fair comparison, we use the default parameters in
the code these authors provided or the optimal parameters theyutilized in their papers. We experiment on the collaboration dataset,the Twitter dataset and the Gowalla dataset (discussed below) for
fair comparison with the method of Ji et al. and the method of
Nilizadeh et al. since these are also the datasets they utilized [7, 17].

3.1

Comparison with Ji et al. [7]Ji et al. [7] proposed a cold-start optimization-based de-anonymization
attack. Although they utilized four structural attributes for eachnode: degree, 1-hop neighborhood, top-K reference distance andsampling closeness centrality, these attributes only represent coarsegrained structure information of the graphs.
We compare our approach with the method of Ji et al. in the
Collaboration dataset, the Twitter dataset and the Gowalla dataset
in Figure 2. We can see that our approach has much higher accuracy
than their method: we can achieve up to 10× improvement for collaboration dataset, and about 6× improvement for two Twitter graphs.
Furthermore, we utilize the Gowalla social dataset to de-anonymize
the Gowalla mobility trace dataset, in order to compare with themethod of Ji et al. for fairness (they experimented on this data in[7]). In Figure 2(d), the de-anonymization results of our method for
Gowalla mobility trace datasets (M1)(M2)(M3)(M4) are 81.3%, 84.8%,
85.3% and 89.1%, respectively. By utilizing finer-grained and richer
structural information, our method also outperforms the methodof Ji et al. for the Gowalla dataset.

Datasets and General Settings

The Collaboration dataset [16] is a network of co-authorships between scientists who have posted preprints on the Condensed Matter
E-Print Archive, which consists of 36,458 users and 171,735 edges.

3Session 1: Social Systems and Notifications

0.6
0.4

0.6
0.4

1

0.2

0.2
0
0

0.1

0.2
Noise

0.3

0.4

0
0

(a) Collaboration

1

Our method
Ji et al.

0.8
0.6

0.6

0.4

0.4

0.2
0.1

0.2
Noise

0.3

0
0

0.4

(b) Twitter: small

Our method
Ji et al.

0.8

Accuracy

Our method
Ji et al.

0.8

Accuracy

Accuracy1

Our method
Ji et al.

Accuracy1
0.8

WPES’17, October 30, 2017, Dallas, TX, USA.

0.2

0.1

0.2
Noise

0.3

0.4

0

M1

(c) Twitter: large

M2

M3

M4

(d) Gowalla

Our method
Nilizadeh et al.

0.6
0.4
0.2
0
0

0.1

0.2
Noise (%)

0.3

0.4

1

1

0.8

0.8

Accuracy (%)

Accuracy (%)

1
0.8

Accuracy (%)

Figure 2: The comparison of our approach with the method of Ji et al. [7].

0.6
0.4
0.2
0
0

(a) Collaboration

Our method
Nilizadeh et al.
0.1

Our method
Nilizadeh et al.

0.6
0.4
0.2

0.2
Noise (%)(b) Twitter: small

0.3

0.4

0
0

0.1

0.2
Noise (%)

0.3

0.4

(c) Twitter: large

Figure 3: The comparison of our approach with the method of Nilizadeh et al. [17].

3.3Comparison with Nilizadeh et al. [17][3] Thomas M Cover and Joy A Thomas. 2012. Elements of information theory. John
Wiley & Sons.
[4] E Garcia. 2006. Cosine similarity and term weight tutorial. Information retrieval
intelligence (2006).
[5] Michael Hay, Gerome Miklau, David Jensen, Don Towsley, and Philipp Weis.
2008. Resisting structural re-identification in anonymized social networks. In
VLDB.
[6] Michael Hay, Gerome Miklau, David Jensen, Philipp Weis, and Siddharth Srivastava. 2007. Anonymizing social networks. Computer Science Department Faculty
Publication Series (2007).
[7] Shouling Ji, Weiqing Li, Mudhakar Srivatsa, and Raheem Beyah. 2014. Structural
data de-anonymization: Quantification, practice, and implications. In ACM CCS.
[8] Ehsan Kazemi, S Hamed Hassani, and Matthias Grossglauser. 2015. Growing agraph matching from a handful of seeds. In VLDB.
[9] Wei-Han Lee, Changchang Liu, Shouling Ji, Prateek Mittal, and Ruby Lee. 2017.
How to Quantify Graph De-anonymization Risks. In Information Systems Security
and Privacy. Springer.
[10] Wei-Han Lee, Changchang Liu, Shouling Ji, Prateek Mittal, and Ruby B Lee. 2017.
Quantification of De-anonymization Risks in Social Networks. In Information
Systems Security and Privacy. IEEE.
[11] Hong Li, Cheng Zhang, Yunhua He, Xiuzhen Cheng, Yan Liu, and Limin Sun.
2016. An enhanced structure-based de-anonymization of online social networks.
In WASA.
[12] Kun Liu and Evimaria Terzi. 2008. Towards identity anonymization on graphs.
In SIGMOD.
[13] Priya Mahadevan, Dmitri Krioukov, Kevin Fall, and Amin Vahdat. [n. d.]. Systematic topology analysis and generation using degree correlations. In SIGCOMM.
ACM.
[14] Arvind Narayanan and Vitaly Shmatikov. 2008. Robust de-anonymization oflarge sparse datasets. In IEEE S&P.
[15] Arvind Narayanan and Vitaly Shmatikov. 2009. De-anonymizing social networks.
In IEEE S&P.
[16] Mark EJ Newman. 2001. The structure of scientific collaboration networks.
Proceedings of the National Academy of Sciences (2001).
[17] Shirin Nilizadeh, Apu Kapadia, and Yong-Yeol Ahn. 2014. Community-enhanced
de-anonymization of online social networks. In ACM CCS.
[18] Pedram Pedarsani, Daniel R Figueiredo, and Matthias Grossglauser. 2013. A
bayesian method for matching two similar graphs without seeds. In Allerton
Conference on Communication, Control, and Computing.
[19] Pedram Pedarsani and Matthias Grossglauser. 2011. On the privacy of anonymized networks. In SIGMOD.
[20] Huy Pham, Cyrus Shahabi, and Yan Liu. 2013. EBM: an entropy-based model toinfer social strength from spatiotemporal data. In SIGMOD.
[21] Raimundo Real and Juan M Vargas. 1996. The probabilistic basis of Jaccard’s
index of similarity. Systematic biology (1996).
[22] Mudhakar Srivatsa and Mike Hicks. 2012. Deanonymizing mobility traces: Usingsocial network as a side-channel. In ACM CCS.
[23] Jierui Xie, Stephen Kelley, and Boleslaw K Szymanski. 2013. Overlapping community detection in networks: The state-of-the-art and comparative study. Acm
computing surveys (csur) 45, 4 (2013), 43.

Nilizadeh et al. [17] leveraged community detection techniques
to partition the networks into separate components. Then, they
applied existing network alignment methods to the nodes inside
the communities for more seed knowledge. However, their method
has the following limitations: 1) it requires prior knowledge (seeds)
to boot up their attack, which is a strong assumption and may sufferfrom misidentified seeds; 2) their performance may be influenced by
the inconsistency problem of community detection methods [23].
We experiment on the collaboration dataset and the two Twittergraphs for fair comparison with the method of Nilizadeh et al. sincethese are also the data they used in [17].
Figure 3(a) compares our method with the approach of Nilizadeh
et al. on the collaboration dataset. Our method can de-anonymize
much more authors and is also more stable to data perturbations. For
noise = 0.4, our method significantly outperforms the method of
Nilizadeth et al. by more than 10× for de-anonymization accuracy.
Figure 3(b) and 3(c) compare our method with the method of
Nilizadeh et al. on the Twitter datasets. Our method is more robust
to noise, and has higher accuracy especially when the noise is high.
For noise = 0.4, we have almost 1.25× improvement for Twitter(small) dataset, and 9× improvement for Twitter (large) dataset.

4

CONCLUSION

We presented a novel blind (seed-free) de-anonymization methodby utilizing the nK-series that we define to capture fine-grained
structure features, and proposing a new variant of the SVM machinelearning technique called PRF-SVM to do concurrent matching of
the nodes between the anonymized graph and the auxiliary graph.
Experimental results demonstrate the significant advantages (up to
10× improvement in de-anonymization accuracy) of our method
over the state-of-the-art de-anonymization attacks.

REFERENCES[1] Lars Backstrom, Cynthia Dwork, and Jon Kleinberg. 2007. Wherefore art thour3579x?: anonymized social networks, hidden patterns, and structural steganography. In WWW.
[2] Carla-Fabiana Chiasserini, Michele Garetto, and Emilio Leonardi. 2015. Impactof Clustering on the Performance of Network De-anonymization. In COSN.

4