Limits of Reliably Matching Profiles Across Large-Scale Online Social Networks
% 1st. author \hspace{-10mm
paper-arxiv.tex
\documentclass[letter]{sig-alternate}
\usepackage{xspace}
\usepackage{graphicx}
%\usepackage{hyperref}
\usepackage[usenames,dvipsnames]{color}
\usepackage[normalem]{ulem}
\usepackage{subfig}
\usepackage{times}
\newcommand{\subparagraph}{}


%\usepackage{natbib}
\usepackage{ulem}
\newcommand{\xref}[1]{\S\ref{#1}}
\newcommand{\minisec}[1]{\textbf{#1:}}

\newcommand{\perc}{\,\%\xspace}
\newcommand{\first}{\emph{(i)}~}
\newcommand{\second}{\emph{(ii)}~}
\newcommand{\third}{\emph{(iii)}~}
\newcommand{\fourth}{\emph{(iv)}~}
\newcommand{\fifth}{\emph{(v)}~}
\newcommand{\sixth}{\emph{(vi)}~}

\newcommand{\match}{a^{2}\textrm{-match-}a^{1}}
\newcommand{\nonmatch}{a^{2}\textrm{-non-match-}a^{1}}
\newcommand{\matchs}{\textrm{match}}
\newcommand{\nonmatchs}{\textrm{non-match}}
\newcommand{\impers}{a^{2}\textrm{-impersonate-}a^{1}}
\newcommand{\nonimpers}{a^{2}\textrm{-non-imperso-}a^{1}}


\newcommand{\old}[1]{{\sout{#1}}}
\newcommand{\new}[1     ]{{\color{blue} #1}}
\newcommand{\change}[1]{{\emph{\color{red}#1}}}
\newcommand{\move}[1]{{\sout{#1}}}
\newcommand{\comment}[1]{{\color{red}\textit{(#1)}}}
\newcommand{\oana}[1]{{\emph{\color{red}#1 --Oana }}}
\newcommand{\rt}[1]{{\emph{\color{red}#1 --Renata }}}
%\newcommand{\oana}[1]{}
\newcommand{\update}[1     ]{{\color{MidnightBlue} #1}}
\newcommand{\remove}[1     ]{{\color{PineGreen} #1}}
\newcommand{\red}[1]{{\color{red}(#1)}}
\newcommand{\todo}[1]{{ \color{red}(  #1)}}
\newcommand{\forrobin}[1]{{ \color{magenta}( For Robin: #1)}}

\newcommand{\question}[1]{{\color{magenta}( Question: #1)}}
\newcommand{\robin}[1]{{\color{magenta}\emph{#1 -Robin}}}
\newcommand{\toremove}[1]{{\sout{#1}}}
%\newcommand{\toremove}[1]{{}}

\newcommand{\nb}{850\xspace}
\newcommand{\smallscale}{\textsc{Random-Sampled}\xspace}
\newcommand{\largescale}{\textsc{Emulated-Large}\xspace}

\newcommand{\linkernb}{\textsc{Linker-NB}\xspace}
\newcommand{\linkersvm}{\textsc{Linker-SVM}\xspace}
\newcommand{\hybridsvm}{\textsc{Linker-SVM+}\xspace}
\newcommand{\hybridnb}{\textsc{Linker-NB+}\xspace}

%\newcommand{\positivetest}{\textsc{Positive-SmallScale-Test}\xspace}
%\newcommand{\negativetest}{\textsc{Negative-SmallScaleTest}\xspace}
%\newcommand{\negativelargescale}{\textsc{Negative-LargeScale-Test}\xspace}
%\newcommand{\positivelargescale}{\textsc{Positive-LargeScale-Test}\xspace}
%
%\newcommand{\positivetrain}{\textsc{Positive-Train}\xspace}
%\newcommand{\negativetrain}{\textsc{Negative-Train}\xspace}
%\newcommand{\negativelargescaletrain}{\textsc{Negative-LargeScale-Train}\xspace}

\newcommand{\profile}{profile\xspace}
\newcommand{\profiles}{profiles\xspace}
\newcommand{\matching}{matching\xspace}
\newcommand{\nonmatching}{non-matching\xspace}
\newcommand{\nonmatchingprofile}{non-matching profile\xspace}
\newcommand{\nonmatchingprofiles}{non-matching profiles\xspace}
\newcommand{\matchingprofile}{matching profile\xspace}
\newcommand{\matchingprofiles}{matching profiles\xspace}
\newcommand{\tname}{\textsc{ACID}\xspace}
\newcommand{\sysname}{\textsc{Linker}\xspace}
\newcommand{\filter}{\textsc{Filter}\xspace}
\newcommand{\disambiguator}{\textsc{Disambiguator}\xspace}
\newcommand{\confidence}{\textsc{Guard}\xspace} 
\newcommand{\psysname}{\textsc{topmatch}\xspace}
\newcommand{\sysnameS}{\textsc{Scalable-Linker}\xspace}
\newcommand{\sysnameD}{\textsc{Disambiguator}\xspace}
\newcommand{\datasetFF}{\textsc{Dataset~FF}\xspace}
\newcommand{\datasetG}{\textsc{Dataset~G+}\xspace}
\newcommand{\datasetAMT}{\textsc{Dataset~AMT}\xspace}
\newcommand{\candlist}{$L$}


%\setlength{\bibsep}{0pt plus 0.3ex}
%\parskip 1pt



%\newfont{\mycrnotice}{ptmr8t at 7pt}
%\newfont{\myconfname}{ptmri8t at 7pt}
%\let\crnotice\mycrnotice%
%\let\confname\myconfname%
%
%\permission{Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on 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 a fee. Request permissions from Permissions@acm.org.}
%\conferenceinfo{KDD'15,}{August 10-13, 2015, Sydney, NSW, Australia.} 
%\copyrightetc{\copyright~2015 ACM. ISBN \the\acmcopyr}
%\crdata{978-1-4503-3664-2/15/08\ ...\$15.00.\\
%DOI: http://dx.doi.org/10.1145/2783258.2788601}
%
%\clubpenalty=10000 
%\widowpenalty = 10000
%


\begin{document}
%
\makeatletter
\def\@copyrightspace{\relax}
\makeatother

\title{On the Reliability of Profile Matching\\ Across Large Online Social Networks}
%\title{Limits of Reliably Matching Profiles Across Large-Scale Online Social Networks}


\numberofauthors{4} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.

\author{
% 1st. author
\hspace{-10mm}
\alignauthor
Oana Goga\\
	\affaddr{MPI-SWS}
	\alignauthor
Patrick Loiseau\\
	\affaddr{EURECOM}
% 2nd. author
\alignauthor
Robin Sommer\\\
       \affaddr{ICSI}
       \and
\alignauthor Renata Teixeira\\
       \affaddr{Inria}
%\alignauthor  % use '\and' if you need 'another row' of author names
% 4th. author
%\and
\alignauthor Krishna P. Gummadi\\
      \affaddr{MPI-SWS}
}

\maketitle



Matching  the profiles of a user across multiple online social networks brings opportunities for new services and applications as well as new insights on user online behavior, yet it raises serious privacy concerns. 
Prior literature has proposed methods to match profiles and showed that it is possible to do it accurately, but using evaluations that focused on sampled datasets only. 
In this paper, we study the extent to which we can \emph{reliably} match profiles \emph{in practice}, across real-world social networks, by exploiting \emph{public attributes}, i.e., information users publicly provide about themselves. 
Today's social networks have hundreds of millions of users, which brings completely new challenges as a reliable matching scheme must identify the correct matching profile out of the millions of possible profiles. 
% while limiting false matches. 
We first define a set of properties for profile attributes--Availability, Consistency, non-Impersonability, and Discriminability (ACID)--that are both necessary and sufficient to determine the reliability of a matching scheme. 
Using these properties, we propose a method to evaluate the accuracy of matching schemes in real practical cases. Our results show that the accuracy in practice is significantly lower than the one reported in prior literature. % and uncover a fundamental limitation in matching profiles in the real world. 
When considering entire social networks, there is a non-negligible number of profiles that belong to different users but have similar attributes, which leads to many false matches.  
%We also propose methods to improve the accuracy in practice. 
Our paper sheds light on the limits of matching profiles in the real world and illustrates the correct methodology to evaluate matching schemes  in realistic scenarios. 





\section{Introduction}\label{sec:intro}

\noindent Internet users are increasingly revealing information about
different aspects of their personal life on different social
networking sites. Consequently, there is a growing interest in the
potential for aggregating user information across multiple sites, by
matching user accounts across the sites, to develop a more complete
profile of individual users than the profile provided by any single
site.  For instance, companies like PeekYou~\cite{peekyou} and
Spokeo~\cite{spokeo} offer {\em ``people search''} services that can
be used to retrieve publicly visible information about specific users
that is aggregated from across a multitude of websites. Some companies
are mining data posted by job applicants on different social
networking sites as part of background
checks~\cite{SocialIntelligence}, while others allow call centers to
pull up social profiles when their customers
call~\cite{salesforce}. The many applications of matching profiles
across social networking sites also raise many legitimate and serious
concerns about the privacy of users.  A debate on the relative merits
of leveraging profile matching techniques for specific applications is
out of the scope of this paper.

In this paper, our goal is to investigate the \emph{reliability} of
techniques for matching profiles across \emph{large real-world} online
social networks, such as Facebook and Twitter, using only {\it
  publicly} available profile attributes, such as names, usernames, location,
photos, and friends.
%  In this paper, our goal is {\it to better understand the {\tt
%    reliability} of profile matching techniques, that exploit information in the {\tt public} 
%  profiles of users, in large real-world online social networks such as
%  Facebook and Twitter}.
  Reliability refers to the extent to which different profiles belonging to the same user can be matched across
social networks, while avoiding mistakenly matching profiles belonging
to different users. Matching schemes need to be highly reliable
because incorrectly matched profiles communicate an inaccurate
portrait of a user and could have seriously negative consequences for
the user in many application scenarios. For example, Spokeo has been
recently sued over providing inaccurate information about a person
which caused ``actual harm'' to the person employment
prospects~\cite{spokeolawsuit}.
%Our work here is motivated by the following high-level question: {\it
%  To what extent, could {\tt publicly} available profiles drawn from
%  two large real-world social networking sites like Twitter and
%  Facebook be {\tt reliably} matched?} 
We focus on publicly available profile attributes because data
aggregators today can crawl and leverage such information for matching
profiles.

Recently, a number of schemes have been proposed for \matching
\profiles across different social networks
~\cite{Motoyama,PeritoCKM11,socialsearch,mywww,MishariT12,IofciuFAB11}
(we review them in~\xref{sec:existing_schemes}.) The potential of
these schemes to reliably match profiles in practice, however, has not
been {\it systematically} studied. Specifically, it is not clear how
or what properties of profile attributes affect the reliability of the
matching schemes. Furthermore, the training and testing datasets for
evaluating the matching schemes are often opportunistically generated
and they constitute only a small subset of all user profiles in social
networks.  It is unclear whether the reliability results obtained over
such datasets would hold over all user profiles in real-world social
networks, where there are orders of magnitude more non-matching
profiles than matching profiles (i.e., there is a huge class
imbalance).

Our first contribution lies in 
%an evaluation method: we gather extensive
%ground truth on matching profiles on six popular social networks
%(\xref{sec:data}) and 
defining a set of properties for profile attributes--Availability,
Consistency, non-Impersonability, and Discriminability (ACID)--that are
both necessary and sufficient to determine the reliability of a
matching scheme (\xref{sec:acid}).
%We then
%analyze the extent to which public profiles drawn from popular
%real-world social networks satisfy these properties. 
Analyzing the ACID properties of profile attributes reveals the
significant challenges associated with matching profiles reliably in
practice~(\xref{sec:acid_test}).
%Estimating the potential for reliably matching profiles across
%real-world social networks is challenging. 
First, data in real-world social networks is often {\it noisy} --
users do not consistently provide the same information across
different sites. Second, with hundreds of millions of \profiles, there
is a non-trivial chance that there exist multiple \profiles with very
similar attributes (e.g., same name, same location) leading to
false matches. Finally, attackers create \profiles attempting to
impersonate other users, fundamentally limiting the reliability of any
profile matching scheme.



Another key contribution lies in our method for carefully selecting
the training and testing datasets for matching profiles~(\xref{sec:training}). When we
evaluate the main types of matching schemes in the literature (based
on binary classifiers) 
%trained to distinguish between
%\matchingprofiles and \nonmatchingprofiles. Our evaluation using small
%using opportunistically-created datasets from Twitter and Facebook
using a small random sample of Twitter and Facebook profiles (similar
to how these schemes were evaluated originally), the schemes achieve
over 90\% recall and 95\% precision
(\xref{sec:linker_small}). Unfortunately, when we evaluate these
schemes over datasets sampled carefully to preserve the reliability
that the schemes would have achieved over the larger datasets (full
Facebook database),
%to match
%a set of Twitter profiles against any Facebook profile, however, the
their performance drops significantly (\xref{sec:nary_linker}).  We
could obtain only a 19\% recall for a 95\% precision. 

We then investigate if we could improve the reliability of matching
schemes in scenarios where we know that there is \emph{at most one
  matching profile} (see~\xref{sec:3step}). In such scenarios, we propose a new matching scheme 
and show that it is indeed possible to improve the recall to 29\% at 95\% precision. This is still considerably lower
than the high recall (90\%) reported in the literature.

Thus, we discover a fundamental limitation in matching profiles across
existing social networks using public attributes. To further confirm the inherent limits of reliably matching profiles in practice, we compare the
reliability of automated matching schemes with that of human Amazon
Mechanical Turk (AMT) workers. Under similar conditions, AMT workers
are able to match only 40\% of the profiles with a 95\% precision.
Our analysis is the first to highlight that achieving high reliability
in \matching profiles across large real-world social networks comes at
a significant cost (in terms of reduced recall).






\section{Problem definition}
\label{sec:problem_definition}

\noindent In this section, we define the problem of matching profiles, we present the constraints we have to consider and discuss how we approach the problem.

 \vspace{2mm}
 \noindent \minisec{The profile matching problem}
 \noindent We consider that two profiles in two social networks match if they belong to/are managed by the same user. 
 The profile matching problem is: given a profile $a^{1}$ in one large social network $SN_1$, find all its \emph{\matchingprofiles} in another  large
social network $SN_2$, if at least one exists. We will denote by $a^{2}$ generic profiles in $SN_2$ and by $\hat{a}^2$ \matchingprofiles of $a^{1}$. For conciseness, we will also write $\match$ if $a^{2}$ is a \matchingprofile of $a^{1}$ and $\nonmatch$ otherwise. 

% The profile matching problem is: given a profile in one  large social network, $a^{1} \in SN_1$, find its \emph{\matchingprofile} in another  large social network, $a_{2} \in SN_2$, if one exists. For conciseness, we will use the notation $\match$ if $a_{2}$ is a \matchingprofile of $a^{1}$ and $\nonmatch$ otherwise. 

Note that we address here the problem of matching \emph{individual} profiles, which is  different from the problem of matching two entire social networks or databases. The difference is that we do not assume that we have access to all the data in  $SN_1$ but  only to one profile. 
For example, we cannot match profiles by exploiting patterns in the graph structure of $SN_1$ and $SN_2$, and we cannot optimize the matching of a profile in $SN_1$  based on the matchings of other profiles in $SN_1$. %, \remove{i.e.,  the decision to match two profiles is independent of the decision to match other profiles. }
Thus, we cannot take advantage of some methods proposed for de-anonymizing social graphs~\cite{narayanan09osn,DBLP:journals/pvldb/KorulaL14} and entity matching~\cite{books/daglib/0030287}. 
 
Our problem formulation is motivated by practical scenarios.  There are many people search engines such as Spokeo that allow users to search for data about a particular person. These services gather data about a person by matching the profiles a person has on multiple social networks. 

We are particularly interested in two instantiations of the problem that are motivated by practical scenarios: (1) the \emph{generic  case} -- a profile can have multiple matching profiles in $SN_2$; and (2) the \emph{special case} -- a profile can have \emph{at most one} matching profile. This case is suited for matching social networks such as Facebook or LinkedIn that enforce users to have only one profile. 

%about what profiles the person has on different social networks by using data that is publicly available trough the APIs of the social networks. Such APIs limit the amount of data that one can gather and it is impossible to reconstruct the entire social network. 
 \vspace{2mm}
 \noindent \minisec{Features}
\noindent In this paper, we investigate the extent to which we can match profiles by exploiting the \emph{attributes} users publicly provide in their profiles such as their \emph{real names, screen names}  (aka. username -- name that appears in the URL of the profile), \emph{location, profile photos,} and \emph{friends}.  
Using this information we can ideally match any person that maintains the same persona on different social networks. Also, we choose these attributes because they are essential to find people online and they are present and usually remain public across different social networks even if users make all their other content, such as their posts and photos, private. 
For profile $a^{1}$ (resp. $a^{2}$), we denote by $v^{1}$ (resp. $v^{2}$) the value of a considered attribute. From attribute values, we define a \emph{feature} as the similarity between the values of profiles in $SN_1$ and $SN_2$: $s(v^{1},v^{2})$.

 \vspace{2mm}
  \noindent \minisec{Matching scheme as a binary classifier}
%\noindent Most of previous work reduced the matching problem to a \emph{binary matching problem}: given two profiles on two social networks, $a_1$ and $a^{2}$, determine whether $a_1$ and $a^{2}$ are \matching or not.  The traditional way to solve this problem is trough binary classifiers. 
\noindent Most previous works solved the matching problem by building binary classifiers that, given two profiles $a^{1}$ and $a^{2}$, determine whether $a^{1}$ and $a^{2}$ are \matching or not~\cite{MishariT12,5636108,5272173,conf/socialcom/PeledFRE13,socialsearch,Motoyama,jain:Iseekfbme:2013:wole,malhotra1}.
%\paragraph{Features}
%\noindent The reliability of a matching scheme depends on the \emph{features} we consider for matching profiles. 
% that determines whether two profiles on different social networks, $a \in
%SN_1$ and $b \in SN_2$, belong to the same user or not.  
The binary classifier takes as input a feature vector $f(a^{1}, a^{2})$ that captures the similarity
between each attribute of a pair of profiles $(a^{1},a^{2})$; and then outputs the probability $p$ of $a^{1}$ and
$a^{2}$ to match. By selecting a cut-off threshold for $p$  the classifier  returns 1 (i.e.,
\matchingprofiles) if $p$ is larger than the threshold; and 0
otherwise. We say that a matching scheme outputs a \emph{true match} when the matched profiles  belong to the same user and outputs a \emph{false match} when the matched profiles  belong to different users. The threshold's choice constitutes the standard tradeoff between increasing the number of true match and decreasing the number of false matches.

This solution works well for the generic case of our matching problem. Given a profile $a^{1}$, we can use the binary classifier to check, for every pair of profiles $(a^{1},a^{2})$ such that $a^{2} \in SN_2$,  whether it is matching or not. We can then output any profile 
$a^{2}$ that the binary classifier declares as \matching.  In this paper, we test such approach when we represent $(a^{1},a^{2})$ with five features, each corresponding to the similarity score between $a^{1}$ and $a^{2}$ for each of the five profile attributes: real name, screen name, location, photo, and friends. %Although some existing matching schemes considered just a sub set of these features~\cite{}, we choose to evaluate matching schemes in the best case when they use all available profile attributes. \rt{check whether this last sentence makes sense. mostly i want to emphasize that what we test is the best for existing schemes.}
%Given a pair of profiles $(a^{1},a^{2})$, the classifier outpusts
%the probability, $p$, that $a^{1}$ and $a^{2}$ are \matching.  




% \update{There are a number of matching schemes proposed by previous works that combine different features together to match profiles~\cite{XX}. Most of the matching schemes reduce the problem to a binary classifier that distinguishes between matching and non-matching profiles.  The primary difference between different previous matching schemes is that they use different datasets and different features, however, they all basically use traditional classifiers such as SVM or Naive Bayes. Our goal is to see how the reliability of these matching schemes changes if we vary the underlying datasets.}

%We can use the binary classification problem to solve our initial matching problem, given a profile $a^{1}$, we can use the binary classifier to check, for every pair of profiles $(a^{1},a^{2})$ such
%that $a^{2} \in SN_2$,  whether it is matching or not. We can then return any profile 
%$a^{2}$ that the binary classifier declares as \matching as the result of our general profile matching problem. 
%This approach is well suited for cases where we expect to have more than one matching profile in $SN_2$, but is vulnerable to output many false matches in case we only have one matching profile.  


For the special case of our matching problem, the previous approach is vulnerable to output many false matches.  For this case, instead of independently judging whether \emph{each} pair $(a^{1},a^{2})$ is a match or not, we can compare (for a given $a^{1}$) the probabilities $p$ for \emph{all} pairs $(a^{1},a^{2})$ to judge which profile is most likely the \matchingprofile of $a^{1}$. We discuss this case in more detail in~\xref{sec:3step}. 

%Alternatively, for this case, instead of independently judging whether \emph{each} $(a^{1},a^{2})$ is matching or not, we can take the probabilities $p$ for \emph{all} $(a^{1},a^{2})$ and compare them to judge who is the most likely matching profile.


 \vspace{2mm}
 \noindent \minisec{Reliability of a  profile matching scheme} 
\label{sec:evaluation}
\noindent  In this paper our focus is on the reliability of matching schemes.  A \emph{reliable matching scheme}
should ensure that the \profile it finds indeed matches with 
high probability, i.e., the matching scheme does not have many false matches.  
If there is no clear matching profile in $SN_2$ for $a^1$, then the scheme should return nothing.
%It is crucial for a  \matching scheme to be reliable because  incorrect matches could erode even more the privacy of users  and additionally make the matching service provider liable for lawsuits~\cite{spokeolawsuit}.

 
Many previous studies used the true and the false positive rate to evaluate their matching schemes. The true positive rate is the percentage of matching profiles that are identified, while the false positive rate is the percentage of non-matching profiles that are false matches. The goal is to have a high true positive rate and a low false positive rate. 
These metrics are, however, a misleading indicator of the reliability of a matching scheme because they are not suited for scenarios with high class imbalance, i.e., the number of matching profiles is much lower than the number of non-matching profiles. 
%
%To illustrate the problem, we take a toy scenario where we have 1,000 profiles in $SN_1$ and their 1,000 matching profiles in $SN_2$.  The job of the matching scheme is to distinguish the 1,000 matching profiles out of 1 million possible combinations of profiles. 
%A matching scheme with a 90\% true positive rate for a 1\% false positive rate might seem reliable, however, in the toy scenario, the matching scheme would output 900 true matches and 9,990 false matches, which is clearly unreliable. In real-world social networks, the class imbalance is even higher (e.g., for each matching profile we have over 1 billion non-matching profiles in Facebook) thus the scheme would output even more false matches. 
For example,  a matching scheme with a 90\% true positive rate for a 1\% false positive rate might seem reliable, however, if we use it in a scenario where we have 1,000 matching and 999,000 non-matching profiles,  the matching scheme would output 900 true matches and 9,990 false matches, which is clearly unreliable. In real-world social networks, the class imbalance is even higher (e.g., for each matching profile we have over 1 billion non-matching profiles in Facebook) thus the scheme would output even more false matches. 

This paper argues that better metrics to evaluate the reliability of a matching scheme are the precision and recall. The recall is the percentage of matching profiles that are identified, while the precision the percentage of all pairs returned by the matching scheme which are true matches. The goal is to have a high recall and a high precision.  In the previous example, we would have
%the equivalent of a 90\% true positive rate for a 1\% false positive rate is a 
90\% recall for a 8\% precision, which shows the low reliability of the scheme (out of all matched profiles only 8\% are true matches).
% The precision and recall clearly show that the reliability of the matching scheme is low because only 8\% of the profiles linked by the matching scheme are actually true matches and 92\% are false matches.  
Thus, the best way to show the reliability of a matching scheme is to evaluate its precision and recall with realistic class imbalance. In the rest of the paper, by \emph{reliable} we mean a precision higher than 95\%. 

\if 0
% which makes the precision even lower. 
%when we evaluate the matching scheme over a dataset that contains 1,000 positive examples and 999,000 negative examples (i.e., all pairwise combinations of 1,000 matching profiles), 

To measure the accuracy of a scheme we can use two pairs of metrics: true and false positive rates, and precision and recall (or combinations of these metrics such as the F1 score). The recall and the true positive rate represent the proportion of \matchingprofiles the scheme links out of all the \matchingprofiles tested. The false positive rate is the proportion of \nonmatchingprofiles the scheme links out of all the \nonmatchingprofiles tested. The precision is the number of true matches divided by the sum of true and false matches the scheme returns. An accurate matching scheme has a high true positive rate and a low false positive rate, or else, a high recall and precision.

Most previous work on this problem showed the true and false positive rates of their matching schemes.
However, even if the pairs of metrics are related,  when dealing with imbalanced classes (i.e., the number of \nonmatchingprofiles is much higher than the number of \matchingprofiles), the precision/recall is a much better indicator of the accuracy of a matching scheme than the true/false positive rate. 
%
For example, if a matching schemes operates at a 90\% true positive rate for a 1\% false positive rate, we could assume that it has a great accuracy.  However, if we consider the scenario where we have 1,000 profiles in $SN_1$ and their 1,000 matching profiles in $SN_2$, the job of the matching scheme is to distinguish the 1,000 matching profiles out of 1 million possible combinations of profiles. 
%when we evaluate the matching scheme over a dataset that contains 1,000 positive examples and 999,000 negative examples (i.e., all pairwise combinations of 1,000 matching profiles), 
In this scenario, the previous true and false positive rate translates to a 90\% recall for a 8\% precision, i.e., only in 8\% of the profiles linked by the matching scheme are actually true matches and 92\% are false matches. This  reveals that the accuracy of the matching scheme is actually very unsatisfying. Note that, in real-world social networks, the class imbalance is even higher (e.g. we have one matching profile for over 1 billion non-matching profiles in Facebook) which makes the precision even lower. Thus,  we claim that the best metrics to illustrate the accuracy of matching schemes are the precision and recall when evaluating the matching scheme at scale. 

%Previously, we talked about building matching schemes that are reliable at an abstract level, from now on 

In the rest of the paper, by \emph{reliable} we mean that a scheme has a precision higher than 95\%. %Also, by high accuracy we specifically mean a high precision and recall.
%\update{So far, we talked about building reliable matching schemes at an abstract level, what we practically mean by a reliable matching scheme is a scheme that has a precision higher than 95\%.}
\fi 



\section{The ACID framework}
  \label{sec:acid}

\noindent   The natural question that arises when investigating the reliability of matching schemes is: what does the reliability depends on?  Undoubtedly,  the reliability depends on the attributes we consider for matching and on their properties. Thus, given an attribute, what properties should the attribute have in order to enable a reliable profile matching?
We propose a set of four properties to help capture the quality of different attributes to match profiles: {\it Availability, Consistency, non-Impersonability, and Discriminability (ACID)}.  


%\begin{trivlist}
% \topsep 0pt
%\itemsep 1pt
%\item 
\noindent \textbf{Availability:}  At first, to enable finding the \matchingprofile, an attribute should have its value available in both social networks. 
%To match many profiles, the selected attribute should be available for a large fraction of users across the different sites. 
If only 5\% of users provided information about their ``age'' across two sites, then ``age'' has limited utility in matching profiles. 
%Formally, we define the availability of an attribute as:  
To formalize this notion, we model the attribute values of $a^{1}$ and each $a^{2} \in SN_2$ as random variables and we define the availability of an attribute as:  
$$A = Pr \left(v^{1} \textrm{ and }   v^{2} \textrm{ available} \big| \match\right).$$ 
  %$A_f = P(f_1^{(1)} available  \cap f_1^{(2)} available )$  where  $f_1^{(1)}$ and $f_1^{(3)}$ are the values of a feature $f$ for the matching profiles $a^{1}^{(1)}$ and $a^{1}^{(2)}$. 

%\update{$A = Pr (v^{(1)} \textrm{ available and }   v^{(2)} \textrm{ available}| a^{(1)} \textrm{ and } a^{(2)} \textrm{ are \matchingprofiles} ).$  }

\noindent \textbf{Consistency:} It is crucial that the selected attribute is
  consistent across \matchingprofiles, i.e., users provide
  the same or similar attribute values across the different profiles they manage. 
  %\remove{If users provided different values for their ``location'' across
 % the different sites, then ``location'' would not be useful in
 % matching profiles.}   
% More formally we  define the consistency of a feature as: $C_f = P(s(f_1^{(1)}, f_1^{(2)}) > th)$, where $s(f_1^{(1)}, f_1^{(2)})$ is a measure of the similarity between the values of a feature  of the matching  profiles $a^{1}^{(1)}$ and $a^{1}^{(2)}$ and  $th$ is a threshold above which two values can be considered consistent. 
 Formally, we define the consistency of an attribute as: 
 $$C = Pr\left(s(v^{1}, v^{2}) > th \big| \match, v^{1} \textrm{ and } v^{2} \textrm{ available}\right),$$ where $th$ is a threshold parameter.  

\noindent \textbf{non-Impersonability:} If an attribute can be easily impersonated,
  i.e., faked, then attackers can compromise the reliability of the
  matching by creating fake profiles that appear to be matching with
  the victim's profiles on other sites. Some public attributes like
  ``name'' and ``profile photo'' are easier to copy 
  than others such as ``friends''.
  To formalize this notion, we introduce the notation $\impers$ to denote that profile $a^{2}$ has been created by an attacker impersonating profile $a^{1}$. We denote the probability that there exists at least one profile $a^{2}$ impersonating $a^{1}$ by $p_{I} = Pr (a^{1} \textrm{ is impersonated})$ and the probability that there is no profile impersonating $a^{1}$ by $p_{nI} = 1 - p_{I}$. The difficulty to manipulate an attribute is characterized by its non-Impersonability defined as: 
  $$
  nI = Pr \Big(\max_{a^{2}: \impers} s(v^{1},v^{2}) <  th \Big).
  $$
  
  
%  More formally, we say that profile $a^{(1)}$ is impersonated if a profile $a^{(2)}$ (which is not a \matchingprofile of $a^{(1)}$) was created in $SN_2$ such that $s(v^{(1)}, v^{(2)}) > th$. Then we define the impersonability $I$ of an attribute as $I = Pr(\textrm{profile } a^{(1)} \textrm{ was impersonated})$ and $nI = 1-I$. Note that these definitions are again indexed by a threshold parameter $th\in [0, 1]$. 
%  More formally we  define the impersonability of an attribute as:  $nI_f =  1 - P(s(f_1^{(1)}, f_1^{(2)}) > th | a_1^{(2)} controlled\ by\ U_{i\neq1}^{(2)})$, i.e., one minus the  probability the similarity between two attribute values is higher than a threshold $th$ if $a_1^{(2)}$  is controlled by an impersonator.  

%\update{ $I = Pr(s(v^{(1)},v^{(2)}) >   th | a^{(2)} \textrm{ is impersonating }  a^{(1)}   )$}

\noindent \textbf{Discriminability:} %The discriminability of a feature refers to
  %the extent to which the feature can be used to distinguish a
% \matchingprofile from a \nonmatchingprofile. 
Even without impersonations, in order to enable finding the \matchingprofile, an attribute needs to uniquely identify a profile in $SN_2$. 
 A highly discriminating attribute would have a unique and different value for each profile, while a less discriminating attribute would have similar values for many profiles. For example, ``name'' is likely to be more discriminating than  ``gender''. 
  %\remove{The more
  %discriminable a feature, the lower the chances of a false match with
  %other \nonmatchingprofiles and the higher the reliability of
  %matching.} 
  Formally, we define the discriminability of an attribute as:  
$$D = Pr\Big(\max_{a^{2}: \nonmatch} s(v^{1},v^{2}) <  th  \big| a^{1} \textrm{ not impersonated}\Big).$$  
%  $D = Pr(\max_{a^{(2)} \textrm{ non-matching } a^{(1)}}$ $s(a^{(1)},a^{(2)}) <  th | a^{(1)} \textrm{ was not impersonated})$. 
  In practice, it is impossible to estimate $D$ unless we are able to identify impersonating profiles. Instead, we estimate: 
  %$\tilde{D} = Pr(\max_{a^{(2)} \textrm{ non-matching } a^{(1)}}$ $s(a^{(1)},a^{(2)}) <  th)$. 
$$\tilde{D} = Pr\Big(\max_{a^{2}: \nonmatch} s(v^{1},v^{2}) <  th\Big).$$
$\tilde{D}$ represents the ``effective discriminability'' taking into account possible impersonations.     
Since impersonators create non-matching profiles as similar as possible to the original profile, it is reasonable to assume that $\tilde{D}\le D$. 
Moreover, by application of Bayes formula, we can show that $D \le \tilde{D}/p_{nI}$ so that, if $p_{I}$ is not too large, $\tilde{D}$ gives a good estimate of $D$. If we assume that the impersonating profiles are independent from the other non-matching profiles, we can also prove that $\tilde{D} = D \cdot (p_{nI} + nI \cdot p_{I})$. This clearly shows that $\tilde{D}$ is close to $D$ if either the attribute is hard to impersonate ($nI$ close to one) or the proportion of impersonator is small ($p_I$ small). 


%By application of Bayes formula, we also find that $D \le \tilde{D}/p_{nI}$ so that, if $p_{I}$ is not too large, $\tilde{D}$ gives a good estimate of $D$. Moreover, if we assume that the impersonating profiles are independent from the other non-matching profiles, we have more specifically that $\tilde{D} = D \cdot (p_{nI} + nI \cdot p_{I})$.
%  Clearly, $\tilde{D}\le D$ since impersonators create non-matching profiles similar to the matching profile. However, straightforward application of Bayes rule also shows that $D \le \tilde{D}/nI$ so that, if $I$ is not too large, $\tilde{D}$ gives a good estimate of $D$. 
  
%\update{$D = 1 - Pr(\max s(v^{(1)},v^{(2)}) >  th  | a^{(2)} \textrm{ non-matching and not impersonating } a^{(1)} )$}
  
%$D_f = P(max\ s(f_1^{(1)},f_{i\neq1}^{(2)}) >  th)$, i.e., the probability that there is a non-matching profile that has a higher similarity than the matching profile. 

%\end{trivlist}



%The availability and consistency determine how many profiles we can match (i.e. the recall), while the impersonability and discriminability of attributes determine the extent to which we can uniquely identify a profile in a social network (i.e. the precision).
%Ideally, if an attribute has high availability, consistency and discriminability and low impersonability this attribute could alone guarantee a reliable matching.  We claim that the ACID properties are a necessary and sufficient condition to guarantee a matching at 100\% precision and 100\% recall:


The ACID properties are clear and intuitive properties that help understand the potential of an attribute to perform reliable matching, as the following theorem formalizes.~\footnote{\small{The proof can be found in the Appendix~\ref{ap:proof}.}}

\newtheorem{mydef}{Theorem}
%%\begin{mydef} 
%%%If a feature has all the ACID properties it is guaranteed that we have a perfect matching (100\% precision 100\% recall).
%%If A=1, C=1, D=1, nI=1 then we can match at 100\% precision and 100\% recall.
%%\end{mydef}
%\begin{mydef}
%With a given attribute $f$, we can achieve a matching at 100\% precision and 100\% recall\ iif $A_f$=1 and there exists  a threshold  th s.t.  $C_f$=1 \& $D_f$=1 \& $nI_f$=1.
%\end{mydef}
 \begin{mydef}
 \vspace{-2mm}
\label{theorem}
Consider a classifier based on a given attribute that classifies as matching profiles if $s(v^{1}, v^{2})>th$. The performance of the classifier is characterized by the following results. 
\vspace{-2mm}
\begin{trivlist}
\item[\hspace{1mm} \textit{(i)}] We have\\[-6mm] $$recall = C \cdot A.$$ 
\item[\hspace{1mm}  \textit{(ii)}] Assume that, for each profile $a^{1}\in SN_1$, there is at most one matching profile in $SN_2$. Then, $$precision \le \frac{recall}{recall + 1 - \tilde{D}}.$$
\item[\hspace{1mm}  \textit{(iii)}] Assume that $p_{I}>0$. Then, $precision = recall =1$ iif $A = C = nI = D = 1.$
\end{trivlist}
\vspace{-4mm}
\end{mydef}
%\begin{proof}
%proof of the theorem
%\end{proof}
%

In Theorem~\ref{theorem}, the threshold parameter $th$ must be the same as the one in the definitions of $C$, $nI$ and $D$. 
Theorem~\ref{theorem}-\textit{(i)} shows that the classifier's recall is simply the product of consistency and availability. Theorem~\ref{theorem}-\textit{(ii)} gives a simple upper bound of the precision as a function of the effective discriminability (which itself is a function of the discriminability and of the impersonability, see above). This upper bound gives a good order of magnitude for the precision; moreover, for high precision (which is what we aim), given the small number of false positives, the true precision should be close to the bound. Finally, Theorem~\ref{theorem}-\textit{(iii)} confirms that a high value of all four ACID properties is \emph{necessary} and \emph{sufficient} to obtain high precision \emph{and} recall. 


Properties $A$, $C$ and $nI$ are independent of the network scale, however,  the discriminability very largely depends on the network scale since having more non-matching pairs decreases the probability that none of them has a high similarity score. This implies that we must estimate the precision and the recall of a matching scheme using datasets that accurately capture the ACID properties of profile attributes of the entire social network. Otherwise, the precision and the recall will be incorrect.
%This implies that, in order to correctly estimate the precision and recall of a matching scheme in practice through sampling of a small number profiles in the social network, it is crucial that the sampling process conserves the ACID properties, otherwise the precision and recall will be badly estimated. 
%The sampling used in previous studies which takes non-matching pairs uniformly at random severely over-estimates the discriminability and therefore the precision at scale. On the other hand, as we shall see, the method proposed in this paper corresponds to sampling the non-matching pairs with highest similarity, which preserves the discriminability and therefore allows us to obtain a good estimation of the precision at scale. 

In practice different attributes satisfy the properties to different extent and the challenge is to combine different attributes with imperfect properties to achieve a reliable matching. The next section analyzes the ground truth for several large social networks to understand the limits of matching profiles across different sites. 

%In~\xref{sec:acid_test} we analyze the extent to which public attributes  satisfy the \tname properties and, in practice, there are no features that exhibit all the four desired \tname properties. Different  features satisfy the properties to
%different extent. 
%Thus, in~\xref{sec:linker} and~\xref{sec:boosted_cl} we investigate the extent to which it is possible to  leverage multiple features with imperfect \tname properties to achieve a reliable matching.
%
 %We perform this analysis for several large social networks to understand the potential of matching profiles across different sites. %Later we will evaluate our schemes for Twitter/Facebook only.  %We focus on five attributes that are supported by all sites: screen name, real name, location, profile photo, and friends.  

\if 0
\paragraph{Formalization}
\noindent To formalize the fact that the ACID properties are necessary and sufficient for an attribute to have in order to guarantee a reliable matching we introduce formal definitions for the ACID properties.  
%To formalize this, we introduce formal definitions for ACID, and present theorem 1
%helpful to define operational definitions and measure the ACID properties in real data.
%Consider that we have two social networks $SN_1$ and $SN_2$. 
Given a profile $a_1^{(1)}$ in $SN_1$ owned by the user  $U_1^{(1)}$ and its matching profile $a_1^{(2)}$ in $SN_2$ owned by $U_1^{(2)}$ ($U_1^{(1)}$ and $U_1^{(2)}$ is the same user), we note  $f_1^{(1)}$ the  value of an attribute $f$ for the account $a_1^{(1)}$ and  $s(f_1^{(1)}, f_1^{(2)})$ the similarity between the values of an attribute of profiles $a_1^{(1)}$ and $a_1^{(2)}$.
%Given a user $U_1^{(1)}$ in $SN_1$ that has an account $a_1^{(1)}$ and the same user in $SN_2$, $U_1^{(2)}$, has an account $a_1^{(2)}$.  
We compute the availability, consistency, non-impersonability and discriminability of an attribute $f$ probabilistically:
\begin{flalign*}
& A_f = P(f_1^{(1)} available  \cap f_1^{(2)} available ) &\\
& C_f = P(s(f_1^{(1)}, f_1^{(2)}) > th ) &\\
%&nI = 1 - P( f_1^{(2)} | A_1^{(2)} controlled\ by\ U_{i\neq1}^{(2)}) \cdot P(A_1^{(2)} controlled\ by\ U_{i\neq1}^{(2)})& \\
&nI_f = 1 - P(s(f_1^{(1)}, f_1^{(2)}) > th | a_1^{(2)} controlled\ by\ U_{i\neq1}^{(2)}) &\\
&D_f = P(max\ s(f_1^{(1)},f_{i\neq1}^{(2)}) < th) & 
\end{flalign*}

The availability is different than the product of availabilities in $SN_1$ and $SN_2$ $A \neq A_1 \cdot A_2$ because the availability in one social network is not independent of the availability in another social network. Given these definitions, here is the ACID theorem. 
\fi 

%Theorem 1 is an extreme case
%These four properties can be seen as a way to estimate the noisiness and evaluate the quality of features to match profiles.

%theorem 1 is extreme, cas particular, dans la vie reel on peut pas avoir ca, on peut avoir dans la vrai vie. formalizer de facon que une feature ACID c'est cool
%dans le case reelle on a pas toutes qui sont 1 mais ca aide de comprendre la qualit� du match
%These definitions will also be helpful to define operational definitions to measure the ACID properties of features in current social networks.  

\if 0
\subsection{Challenges}
There are many challenges imposed by matching \profiles in real-world social networks that are essential to  be considered in order to build reliable matching schemes:

\noindent \minisec{Real-world social networks}  First, there might not be a matching \profile or there might be multiple impersonating \profiles on the second social network. A reliable matching scheme has to mitigate such scenarios.  Second, we are dealing with really large datasets, Facebook has over 1 billion users while Twitter and LinkedIn have over 300 million users. This rises questions about the best strategy to evaluate matching schemes: 1) what dataset we need for evaluation, would the evaluation over a sampled dataset be indicative of the accuracy over the entire social network?;  2) what metrics portray best the accuracy of the scheme at scale.  Finally,  we have to deal with a huge class imbalance, i.e. the number of possible matching \profiles is 1 billion orders of magnitude smaller than the number of possible non-matching \profiles. Thus, we need classification techniques that are able to handle such class imbalance. 

\noindent \minisec{Access to data} We do not have access to entire social networks data, thus we have to exploit the APIs provided by social networks to gather data to build and evaluate matching schemes.  The questions are how can we exploit such APIs, and what is the impact of using such APIs on the accuracy of matching schemes. Furthermore, since we take a supervised approach to match \profiles we need a method to gather representative ground truth of matching \profiles. 

\noindent \minisec{Features} As the information users provide in their \profiles is often noisy, this poses several challenges for the matching scheme. 
Firstly, users might not provide the same kind of information on different social networks, for example one user might choose to show his location on Facebook while he keeps his location private on Flickr. Furthermore, even if the users provide the same kind of information across different social networks, they might not be consistent. For example, one user that moved, might update his location only on Facebook while leaving his old location on Twitter. Therefor, it is important to understand the quality of different features, and understand how many users we can actually match using public attributes.  
Finally, since profile attribute values can be unavailable, we need classifiers that are robust to missing data. 

Most previous work focused on building matching schemes with good accuracy over sampled small scale datasets.  Since most challenges come when considering real-world social networks, most of the matching schemes proposed previously are not optimal when evaluated in real-world social networks. We will tackle all these challenges in the next sections. 
\fi 

\if 0
\subsection{Challenges}
To match \profiles across social networks, we are going to exploit the information users publicly provide in their profiles such as their real names, screen names, location, profile photos or friends.  As the information users provide in their \profiles is often noisy, this poses several challenges for the matching scheme. 
Firstly, users might not provide the same kind of information on different social networks, for example one user might choose to show his location on Facebook while he keeps his location private on Flickr. Furthermore, even if the users provide the same kind of information across different social networks, they might not be consistent. For example, one user that moved, might update his location only on Facebook while leaving his old location on Twitter.
Beside problems linked to the quality of data provided by users, when matching at scale, \profiles start to look similar. While in a small dataset there might be just one Jennifer Clark in San Francisco if we consider all the profiles in a social network there might be tens or hundreds such users. On top of this, attackers and spammers create profiles attempting to impersonate other users, which makes the design of  a reliable and scalable matching scheme challenging. 
\change{maybe add API limits as challenge}
\fi


\if 0
Renata's version
\noindent Intuitively, the matching accuracy depends on how well the features we use 
for the matching identify a profile in a social network. To evaluate the quality of features available in
existing social networks, we propose a set of four properties that capture the quality of features for 
matching profiles:  {\it Availability, Consistency, Impersonability, and Discriminability (ACID)}.  

\begin{trivlist}
% \topsep 0pt
%\itemsep 1pt
\item \textbf{Availability:}  To match many profiles, the selected
  features should be available for a large
  fraction of users across the different sites. If only 5\% of users provided information about their ``age'' across
  two sites, then ``age'' has limited utility in matching
  profiles.

\item \textbf{Consistency:} It is crucial that the selected feature is
  consistent across different \matchingprofiles, i.e., users provide
  the same feature values across the different profiles they manage. 
%  If users provided different values for their ``location'' across
%  the different sites, then ``location'' would not be useful in
%  matching profiles.

\item \textbf{Impersonability:} If a feature can be easily impersonated,
  i.e., faked, then attackers can compromise the reliability of the
  matching by creating fake profiles that appear to be matching with
  the victim's profiles on other sites. 
%  Some public features like
%  ``name'' and ``profile photo'' are easier to copy 
%  than others such as ``friends''.


\item \textbf{Discriminability:} %The discriminability of a feature refers to
  %the extent to which the feature can be used to distinguish a
% \matchingprofile from a \nonmatchingprofile. 
 A highly
  discriminating feature would have a unique and different value for
  each profile, while a less discriminating feature would have similar
  values for many profiles. For example, ``name'' is likely to be more
  discriminable than ``location'' and ``gender''. 
%  The more
%  discriminable a feature, the lower the chances of a false match with
%  other \nonmatchingprofiles and the higher the reliability of
%  matching.


\end{trivlist}

The availability and consistency of features will determine how many profiles we can match (i.e. the recall), while the impersonability and discriminability of features will determine the extent to which we can uniquely identify a profile in a social network (i.e. the precision).
%
%These four properties can be seen as a way to estimate the noisiness and evaluate the quality of features to match profiles.
Ideally, if a feature has high availability, consistency and discriminability and low impersonability this feature could alone guarantee a reliable matching. In practice, different profile attributes satisfy the properties to
different extent. The rest of this section analyzes the ground truth for several large social networks to understand 
the potential of matching profiles across different sites.  We focus on five attributes that are supported by all sites: screen name, real name, location, profile photo, and friends.  


\fi

%\section{Quality of Available Features}
%\section{Helpers and hinderers of matching profiles}
%\section{Promises and perils to match profiles}
%\section{Potential and dangers when matching profiles}
%\section{The Potential of matching profiles: promises and perils}
\section{Limits of matching profiles}
%\section{Matching Profiles: potential and perils}
\label{sec:acid_test}


%\rt{the intro of this section talks about features and the rest attributes. sec 2 also talked about features.
 %you should make the terminology consistent}

\noindent To understand the limits of matching profiles, we analyze the ACID properties of profile attributes (screen name, real name, location, profile photo, and friends) across six popular social networks (Facebook, Twitter, Google+, LinkedIn, Flickr, and MySpace). 
%\remove{The availability and consistency limit the recall  while the discriminability and impressionability limit the precision we can achieve.}  
First we present our method to gather ground truth of matching profiles and we then analyze each property separately.  


\subsection{Ground truth of matching profiles}
\label{sec:gt}
\noindent %To conduct our analysis, we first need to gather ground truth data of  \matchingprofiles. %, i.e., profiles belonging to the same user across different social networks.  
%We gather matching profiles across six popular social networks: Facebook, Twitter, Google+, LinkedIn, Flickr, and MySpace.
%Using these profiles we build two datasets to train and evaluate matching schemes.
Gathering ground truth of
\matchingprofiles spanning multiple social networks is challenging and many previous works manually labeled profiles~\cite{Liu:2013:WNU:2433396.2433457,5272173,conf/socialcom/PeledFRE13}. Below we describe two automatic methods that we used to obtain our ground truth. 

We  first obtained ground truth data by exploiting ``Friend Finder''
mechanisms on many social networks that allow a user to find
her friends by their emails. We used a list of
%10 million
email addresses collected by colleagues for an earlier study analyzing
spam email~\cite{Kreibich:2009:SIL:1855676.1855680}.\footnote{\small{The local IRB approved the collection.}}  These
email addresses were collected on a machine instructed to send spam by
a large bot network.  Since
spammers target the public at large we believe that this list of
emails catch a representative set of users. To combat abuse, some social networks limit the
number of queries one can make with their ``Friend Finder'' mechanism
and employ techniques to make an automated matching of an email to a
profile ID impossible. Hence, we were only able to collect the
email-to-profile ID matching for Twitter, Facebook, LinkedIn and Flickr.
%Hence, we were only able to collect the
%email-to-profile ID matching for Twitter and Flickr. In addition, we
%obtained from colleagues pairs of \matchingprofiles among Twitter,
%Facebook, and LinkedIn, which they collected for an earlier study
%using the same technique~\cite{balduzzi09osnProfiling}.
Table~\ref{tab:data:GT} summarizes the number of \matchingprofiles we
obtained using the Friend Finder mechanism (\datasetFF).\footnote{\small{To test the representativeness  of \datasetFF, we compare the distribution of properties  such as account creation date, number of followers, and number of tweets of Twitter 
profiles in our dataset with the same properties of random Twitter profiles. We found that the pairs of distributions for each property matched fairly closely.}}
%\footnote{\update{\small{We checked the representatives of these users by comparing the CDFs for different statistics (e.g. account creation date, nb of followers, nb or tweets) of random Twitter users and Twitter users in \datasetFF and the CDFs are close to each other.}}}

Some previous works obtained ground truth from users that willingly provide links to their profiles in different social networks.  Such users might not represent users in general because they want their profiles to be linked and probably expend the effort to keep their profiles synced.  
%
%To be able to compare our results against previous works we also obtained such dataset. We exploit the fact that Google+ allows users to explicitly
%list profiles they have on \emph{other} social networks on their Google+ profile pages. We randomly crawled about 3 million Google+ profiles and arrived at the ground truth set summarized in column \datasetG of Table~\ref{tab:data:GT}.
%
To be able to compare our results against previous works we collected \datasetG (see Table~\ref{tab:data:GT}) by exploiting the fact that Google+ allows users to explicitly
list their profiles in \emph{other} social networks on their profile pages.
% We randomly crawled about 3 million Google+ profiles and arrived at the ground truth set summarized in column \datasetG of Table~\ref{tab:data:GT}.
%, which reports the number of \matchingprofiles
%for different combinations of social networks.
%\footnote{Google+ proves
 %easy to crawl as it provides an initial starting point in the form
 % of a comprehensive directory of all profiles, and does not block  crawlers.} 
%Intuitively, Google+ users, who voluntarily reveal their profiles on other sites, might not represent users in general because they are users who (1) want their profiles to be linked and (2) probably care more about their online image and expend the effort to keep their profiles synced. 
%Indeed, our results show that profiles attributes for users in \datasetG are more available and consistent than the ones in \datasetFF and that the matching accuracy is higher. Thus, as most of previous works used this kind of users as ground truth, they overestimated the accuracy of the matching. 
Due to space constraints, for the rest of the paper, we show by default the results for profiles in \datasetFF and occasionally, for comparison, we show   the results are for \datasetG.

%We complement the \datasetFF with a second, orthogonal set that contains more social networks.  
%we can use these users to extend our study to other social networks and to a  larger dataset. 



%In the rest of the paper by default, we show the values for profiles in \datasetFF -- we use values for profiles in \datasetG only
%when we lacked the data in \datasetFF. Even if the comparison between the two datasets is interesting in its own, due to space constraints we will mostly focus on results using \datasetFF as it is more representative. Generally the matching accuracy for users in \datasetG is higher than users in \datasetFF. We will pinpoint throughout the paper some of the differences.

%\oana{I think we should remove all the discussions about the \datasetG, we can just say that we checked this kind of ground truth and the availability and consistency is much higher than for \datasetFF and thus the previous works overestimated the accuracy. Also remove entries form tables corresponding to \datasetG.}


\begin{table}[t]
\scriptsize{
%\space{-8mm}
\caption{\small{Number of ground truth \matchingprofiles obtained with Friend Finder (\datasetFF) and Google+ (\datasetG) for different combinations of social networks.}}
%\selectfont
\vspace{-3mm}
\label{table:avbw}
{\centering
%\tabcolsep1.5mm
\begin{tabular}{l|c|c}
 & \textbf{\datasetFF} & \textbf{\datasetG} \\
\hline
\hline
\textbf{\textsc{Twitter - Facebook}} & 4,182 & 76,332  \\
\textbf{\textsc{LinkedIn - Facebook}} & 2,561 & 20,145 \\
\textbf{\textsc{Twitter - Flickr}} & 18,953 & 35,208 \\
\textbf{\textsc{LinkedIn - Twitter}} & 2,515 & 20,439 \\
%\textbf{\textsc{LinkedIn - Flickr}} & - & 8,503 \\
%\textbf{\textsc{Twitter - Google+}} & - & 205,709  \\
%\textbf{\textsc{Twitter - Myspace}} & - & 9,015  \\
%\textbf{\textsc{Facebook - Google+}} & -  & 164,333 \\
%\textbf{\textsc{Facebook - Myspace}} & - & 9,610  \\
%\textbf{\textsc{LinkedIn - Google+}} & - & 32,827 \\
%\textbf{\textsc{LinkedIn - Myspace}} & - & 2,283 \\
%\textbf{\textsc{Myspace - Google+}} & - & 36,440 \\
%\hline
%\hline
%\textbf{Twitter - Facebook - Google+}    & 76,600  & -\\
%\textbf{Twitter - Facebook - Myspace}    & 4,207 & - \\
%\textbf{Twitter - Google+ - Myspace}    & 9,015 & - \\
%\textbf{Facebook - Google+ - Myspace}    & 9,610 & - \\
%\textbf{Facebook - Twitter - LinkedIn}    & \change{?} & \change{?}\\
\end{tabular}

}
\label{tab:data:GT}
\vspace{-1\baselineskip}
%\vspace{-3mm}
}
\end{table}
%




\subsection{Attribute availability}
\label{sec:avail}
\noindent %We begin by examining the availability of public attributes
%across the six social networks in our ground truth. 
The availability of attributes depends on the social network, for example Twitter does not ask users about their age while Facebook does. The availability also depends on whether users  choose to input the information and make it public.  Users might choose to let their location public on Twitter while make it private on Facebook.  % \update{Finally, the availability of attributes does not vary with the scale of the dataset  and does only depend on whether users provide or not a value.}


Table~\ref{tab:avail} shows the breakdown of attribute availability per social network and pairs of social networks. The availability per social network characterizes the behavior of users, while the availability for pairs of social networks corresponds to the definition of $A$ in~\xref{sec:acid}.
% the previous section.
% that implies a bound on the recall we can achieve using the attribute. %The more available attributes are the higher the recall we can achieve when matching profiles based on the attribute. 
%The availability of attributes in different social networks is not independent.
%\comment{some notation to say it is an upper bound ? and not independent ?s}



\begin{table}[t]
\scriptsize{
%\vspace{-8mm}
{\centering
\caption{\small{Availability of attributes for \datasetFF. \\ \uline{Legend:} Tw~=~Twitter, Fb~=~Facebook, Fl~=~Flickr, Lnk~=~LinkedIn.}}
\vspace{-3mm}
\setlength{\tabcolsep}{2pt}
\begin{tabular}{l|c|c|c|c|c}
&  \textbf{Screen Name}   & \textbf{Real Name} & \textbf{Profile Photo} & \textbf{Location} & \textbf{Friends} \\
\hline
\hline
\textbf{\textsc{Tw}} & 100\% & 100\% & 69\% &  54\% & 86\% \\
%&  &  &  (88\%/59\%)$\ddagger$ &  \\
\textbf{\textsc{Fb}}  & 100\% & 100\% & 98\% &52\%  & 60\% \\
%&  &  & (53\%/52\%) &  \\
\textbf{\textsc{Fl}}  & 100\% & 30\% &29\%& 11\% & 40\% \\
%&  &  &  (55\%/11\%) &  \\
\textbf{\textsc{Lnk}}  & 100\% & 100\% & 57\% &99\% & 0\%\\
%&  &  &  (100\%/100\%)  \\
\hline
\hline
\textbf{\textsc{Fb - Tw}}  & 100\% & 100\% & 69\% & 30\% & 43\%\\
\textbf{\textsc{Fb - Lnk}} & 100\% & 100\% & 56\% & 54\% & 0\%\\
\textbf{\textsc{Tw - Fl}} & 100\% & 30\% & 24\% & 8\% & 32\% \\
\textbf{\textsc{Lnk- Tw}}  & 100\% & 100\% & 44\% & 54\% & 0\%\\
\if 0
\textbf{\textsc{G+}~$\dagger$} & 100\% & 100\% & 80\% & 72\%  & 75\%\\
\textbf{\textsc{M}~$\dagger$}  & 100\% &  20\% & 98\% & 26\%  & 89\%\\
\fi 
\if 0
\hline
\hline
\textbf{\textsc{Fl - Tw}} & 76\%/31\% & 88\%/24\% & 46\%/8\% & 72\%/35\% \\
\textbf{\textsc{Fb - Lnk}} & 100\%/100\% & 53\%/56\% & 53\%/54\% & -\\
\textbf{\textsc{Fb - Tw}}  & 100\%/100\% & 94\%/69\% & 44\%/30\% & 38\%/48\%\\
\textbf{\textsc{Lnk- Tw}}  & 100\%/100\% & 52\%/44\% & 84\%/54\% & -\\
\textbf{\textsc{Fb - G+}}  & 100\% & 91\% & 40\% & -\\
\textbf{\textsc{Fb - Fl}}  & 77\% & 88\% & 29\% & 20\% \\
\textbf{\textsc{Fb - M}}  & 17\% & 89\% & 12\% & -\\
\textbf{\textsc{Tw - G+}}  & 100\% & 90\% & 55\% & -\\
\textbf{\textsc{Tw - M}}  & 16\% & 85\% & 23\% & -\\
\textbf{\textsc{Lnk - Fl}}  & 79\% & 47\% & 56\% & -\\
\textbf{\textsc{Lnk - G+}}  & 100\% & 52\% & 74\% & -\\
\textbf{\textsc{Lnk - M}}  & 16\% & 40\% & 37\% & -\\
\textbf{\textsc{Fl - G+}}  & 76\% & 87\% & 39\% & -\\
\textbf{\textsc{Fl - M}}  & 12\% & 81\% & 21\% & -\\
\textbf{\textsc{G+ - M}}  & 20\% & 75\% & 22\%& -\\
\fi
\end{tabular}
\label{tab:avail}

}
\vspace{-2\baselineskip}
}
\end{table}%

First, we find that the availability of the attributes varies
considerably across the different social networks. For
example, users are more likely to provide their location information
on LinkedIn than they are on Facebook or Twitter. The differences in
availability are presumably due to the different ways in which users
use these sites. For our purposes, it highlights the additional
information one could learn about a user by linking her profiles on
different sites. %Our observation also hints at the potential for
%iteratively matching profiles across different sites, i.e., build a
%more complete profile of a user by matching her profiles across some
%sites and use the resulting profile with more attributes to match her
%profiles on other sites.


Second, we find that screen name and real name are
considerably more available than location or
friends.  %The more available attributes are the higher the recall we can achieve when matching profiles based on the attribute. 
However, the availability of the less available attributes is not negligible -- for example, location and
friends are available for more than 30\% of matching profiles in Twitter and Facebook. 

Third, when we compare the availability using \datasetFF and \datasetG (not shown), we observe that the availability of attributes for profiles in the \datasetFF is much lower than the availability for profiles in the \datasetG (e.g., profile photo is available for only 69\% of Twitter users in \datasetFF while it is available for 96\% of users \datasetG).\footnote{\small{For more results on \datasetG, we refer the reader to~\cite{Goga}.}} 
Thus, users in \datasetG are more likely to complete their profiles and consequently there is a higher bound on the recall to match them.

%and the reliability of previous matching schemes evaluated over such ground truth is not indicative of the reliability of matching random users.


\subsection{Attribute consistency}\label{sec:features}
\label{sec:consistency}

\noindent We now study the extent to which users
provide consistent attribute values for their profiles on different
social networks. Some users deliberately provide different
attribute values either out of concerns for privacy or out of a desire
to assume online personas different from their offline persona. It
would be very hard to match \profiles of such users by
exploiting their public attributes. %\remove{As the availability, the consistency of a attributes does not vary with the scale of the dataset and it only depends whether users provide or not consistent values for an attribute.}

Other users may input slightly different values for an attribute across sites. For example, a user might
specify her work place as International Business Machines on one site and
International Business Machines Corporation on another site. 
%To profile for such scenarios
%where attribute matching is not exact, we first propose metrics
%for estimating similarity between two attribute values and find thresholds for determining when two values are consistent. 


 \vspace{2mm}
 \noindent \minisec{Similarity metrics for profile attributes}
%\noindent We borrow a set of standard metrics from prior work in
%security, information retrieval, and vision communities to compute
%similarity between values of the following attributes.
\noindent We borrow a set of standard metrics from prior work in
security, information retrieval, and vision communities to compute
similarity between the values of  attributes:  the Jaro distance~\cite{Cohen03acomparison} to measure the similarity between names and screen names; the geodesic distance to measure the similarity between locations; the phash~\cite{phash} and SIFT~\cite{SIFT} algorithms to detect whether two photos are the same; and the number of common friends between two profiles. Please check our Appendix~\ref{ap:sim} for a full description of these metrics.
%\comment{refer to appendix for a more detailed description of similarity metrics}


\if 0
\begin{table}[htdp]
\footnotesize{
\caption{Similarity thresholds for matching attributes obtained using the AMT experiment, corresponding to a 10\% false positive rate.}
\begin{center}
%\scalebox{0.9}{
\begin{tabular}{c|c|c}
\textbf{Attribute} &   \textbf{ \parbox[t]{0.20\columnwidth}{Similarity threshold }} &  \textbf{Correctly detected matches}\\
\hline
\hline
Real Name & 0.66 & 98\%  \\
%& {\bf0.79} & {\bf 91\%} & {\bf2\%} \\
% & 0.66 & 98\% & 10\% \\
%\hline
 Screen Name  &0.82 &  80\%  \\
%& 0.61 & 90\% & 20\% \\
% &{\bf0.82} & {\bf 80\%} & {\bf10\%} \\
 %\hline
 Location  & 70Km  &  83\% \\
%& 1000Km & 92\% & 33\% \\
% &{\bf 70Km}  & {\bf 83\%} & {\bf10\%} \\
 %\hline
 Photo - Phash  & 0.60 &  72\%  \\
%& 0.49 & 94\% & 50\% \\
% & {\bf0.60} & {\bf 72\%} &{\bf 10\%} \\
 %\hline
  Photo - SIFT & 0.09 & 87\%  \\
%& {\bf 0.11} & {\bf 87\%} & {\bf 2\%} \\
% & 0.09 & 87\% & 10\% \\
\end{tabular}
%}
\end{center}
\label{tab:amt_tresh}
}
\end{table}%
\fi

 \vspace{2mm}
 \noindent \minisec{Similarity thresholds for attribute consistency}
\noindent 
Clearly the more similar two values of an attribute, the
greater the chance that the values are consistent, i.e., they refer to
the same entity, be it a name or photo or location. 
%However, The choice of threshold for attribute similarity for the classifier results from a trade-off between precision and recall (or consistency and discriminability) which we discuss in the next section. 
Here, we want to show consistency results for a ``reasonable'' threshold beyond which we can declare with high confidence that the attribute values are consistent (irrespective of the tradeoff between consistency and discriminability in~\xref{sec:acid}). The best to judge whether two attribute values are consistent are humans.
%We want to identify a threshold for attribute similarity beyond which we can declare 
%with high confidence that the attribute values are consistent.
%, i.e. choose threshold to catch more than 90\% of the consistent values and less than 10\% inconsistent  values.
%
%Our goal is to select thresholds for attribute similarity beyond which we can . 
%
%The best to judge whether two attribute values are consistent are humans.  
Thus, we gathered ground truth 
data by asking Amazon Mechanical Turk (AMT) users to evaluate whether pairs of attribute
values are consistent or not.  We randomly select 100 pairs each of
matching and \nonmatching Twitter and Facebook profiles from
\datasetFF and asked AMT users to annotate which attribute values are consistent and which are not. We followed the guidelines to ensure 
good quality results from AMT workers~\cite{AMT_guidelines}.  
%For each pair of attribute values, workers had to choose
%between 3 answers: (i) {\it Yes, they match}; (ii) {\it No, they do
 % not match}; and (iii) {\it Cannot say, the information is not
 % available}. 
%For each attribute value pair, we ask the opinion of
%three different AMT workers and consider that the values are
%consistent if there is a majority agreement.

For each attribute, we leverage the AMT experiment to select the similarity thresholds to declare two values as consistent. 
Specifically, we select similarity thresholds, such that more than 90\% of the consistent values, as identified by AMT workers, and less than 10\% of the inconsistent values have high similarities.
%\old{Table~\ref{tab:amt_tresh} shows the selected similarity threshold values for different attributes. }
Note that, we only use these thresholds to evaluate whether attribute values in \matchingprofiles are consistent and we do not use them to actually match profiles. Thus, while it is important that the majority of  consistent values pass the threshold,  it is not critical if some inconsistent  values also pass the threshold.
%Note that, we only use thresholds to study the consistency of attributes across social networks and we do not use the thresholds for building the matching schemes. The matching algorithms directly use the similarity scores between attributes.
Incidentally, this experiment also shows that the similarity metrics we choose are consistent with what humans think it is similar.
Note that, it is unpractical to use AMT workers to estimate the threshold for friends, thus we manually choose it  be at least two friends in common to avoid noise. 

%
%\if 0
%To choose a similarity threshold to decide if two values of an
%attribute match or not, we pick the similarity threshold that
%corresponds to correctly detecting 90\% of the attributes that match
%(true positives), as detected by AMT workers.  If the fraction of
%incorrectly detected matches (false positives) is higher than 10\%
%then we choose the threshold corresponding to a 10\% false positive.
%With a threshold of 0.79 we can identify 91\% of the matching real
%names with only a 2\% false positive rate. The 9\% of matching real
%names that we cannot detect correspond to either cases when someone
%uses a nickname in one social networks and not in another (e.g Liz
%Bower vs. Elizabeth Bower ) or they use their given name on one social
%network and their full name on another (e.g ellen vs. Ellen Rosenfeld
%Sall). Nicknames are easily detectable by humans because they have an
%a priori knowledge of what nickname corresponds to what name, however
%it is much harder for humans.  With a threshold of 0.82 we can catch
%80\% of the matching screen names. The 20\% of the screen names we
%cannot match correspond to cases where one scree name is somehow part
%of the other. Examples of matching screen names that we miss:
%SomethingSoSam and SoSam; zimmee1 and emily.zimmer.509.  This screen
%names appear similar to a human while they look not similar to a
%machine because they have many characters that are not in common.  For
%location, with a threshold of 70 Km we can identify 80\% of the
%matching locations. The 20\% that are not detectable correspond to
%profiles that have a specific city in a profile while they have a
%region in another (e.g San Diego vs South California) and the distance
%between their exact latitude and longitudes will be higher than
%70Km. In some cases the current locations in the two profiles do not
%match however past locations match, i.e place of birth in one social
%networks corresponds to the current location in another. Since our
%similarity only compares current locations we miss this cases.
%Finally, we miss a few cases because the Bing API that transforms a
%location string to an exact latitude and longitude fails to give good
%coordinates. A typical example of this is when the location string
%contains multiple locations (e.g "I live in Italy and Brazil").
%Finally with a threshold of 0.60 we can catch 80\% of the photo
%matches using the Phash algorithm and with a threshold of 0.11 we can
%catch 87\% of the photo matches using the SIFT algorithm. Many of the
%photos that are not detected by Phash are cropped while the photos
%that are not identified by SIFT are either graphics or very small
%photos. While both the Phash and the SIFT algorithms fail to detect
%some types of photos, they fail on different ones, thus the two
%algorithms can be complementary used together. A few of the photos not
%identified correspond to the cover photo in one social networks
%matching the profile photo in another, we did not collect cover
%photos.
%\fi

%select
%t.screen_name,f.screen_name,twitter_id,facebook_id,sim_name,sim_screen_name,agreement_screen_name
%from amt inner join twitter_users as t on t.uid=twitter_id inner join
%facebook_users as f on f.uid=facebook_id where
%agg_choice_screen_name='screen_name_yes' and matching='YES' and
%(agreement_screen_name='partial' or agreement_screen_name='full') and
%sim_screen_name < 0.82;

%\if 0
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\subfloat[Screen name]{\label{fig:hist_u}\includegraphics[width=0.20\textwidth]{plots/cdf_attribute_match_U.eps}}
%\subfloat[Real name]{\label{fig:hist_n}\includegraphics[width=0.20\textwidth]{plots/cdf_attribute_match_N.eps}}
%
%\subfloat[Photo - Phash]{\label{fig:hist_p}\includegraphics[width=0.20\textwidth]{plots/cdf_attribute_match_P.eps}}
%\subfloat[Photo - SIFT]{\label{fig:hist_p}\includegraphics[width=0.20\textwidth]{plots/cdf_attribute_match_S.eps}}
%
%\subfloat[Location]{\label{fig:hist_l}\includegraphics[width=0.20\textwidth]{plots/cdf_attribute_match_L.eps}}
%%\vspace{-2mm}
%\caption{CDFs of similarity scores for attributes that match and do not match as identified by the AMT workers.}
%\label{fig:cdf_attribute_match}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%\fi 




%\noindent We now use the similarity metrics and thresholds defined in
%the previous section to evaluate whether attribute values in
%\matchingprofiles are consistent. 

%\begin{table}[t]
%\footnotesize{
%%\vspace{-8mm}
%\begin{center}
%\setlength{\tabcolsep}{2pt}
%\caption{Consistency of attributes for \datasetFF ; }
%%\\ \uline{Legend:} Tw~=~Twitter, Fb~=~Facebook, G+~=~Google+, M~=~Myspace, Fl~=~Flickr, Lnk~=~LinkedIn; 
%%}
%\vspace{-3mm}
%\begin{tabular}{l||c|c|c|c}
%  & \textbf{Screen Name}  & \textbf{Real Name} & \textbf{Location} & \textbf{Profile Photo}  \\
%\hline
%\hline 
%Fb - Tw  & 40\% & 84\% & 77\% & 19\%   \\ 
%Fb - Lnk  & 71\% & 97\%  & 83\% & 23\%  \\ 
%Tw - Fl & 40\%  & 84\%  & 67\% & 22\%  \\ 
%Tw - Lnk & 36\% & 83\% & 71\% & 31\% \\ 
%\if 0
%Fb - Tw  & 40\% & 84\% & 22\% & 19\%   \\ 
%Fb - Lnk  & 71\% & 97\%  & 17\% & 23\%  \\ 
%Tw - Fl & 40\%  & 84\%  & 32\% & 22\%  \\ 
%Tw - Lnk & 36\% & 83\% & 28\% & 31\% \\ 
%Fb - Fl~$\dagger$  & 48\% & 94\% & 30\%& 20\%  \\ 
%Fb - G+~$\dagger$  & 59\% & 94\% & 65\% & 20\%  \\ 
%Fb -  M~$\dagger$   & 46\% & 77\% & 43\% & 13\% \\ 
%Tw - G~$\dagger$   & 50\% & 85\% & 62\% & 31\% \\ 
%Tw - Lnk~$\dagger$   & 57\% & 89\% & 29\% & 36\%  \\ 
%Lnk - Fl~$\dagger$   & 48\% & 95\% & 33\% & 29\%  \\ 
%Lnk - G~$\dagger$   & 65\% & 97\% & 67\% & 35\%  \\ 
%Lnk -  M~$\dagger$   & 54\% & 76\% & 56\% & 23\% \\ 
%Fl - G~$\dagger$   & 42\% & 94\% & 63\% & 31\% \\ 
%Fl -  M~$\dagger$   & 43\% & 78\% & 49\% & 27\% \\ 
%G -  M~$\dagger$   & 44\% & 70\% & 51\% & 20\% \\ 
%\fi
%\end{tabular}
%\label{tab:consistency}
%\end{center}
%\vspace{-3\baselineskip}
%}
%\end{table}%



\begin{table}[t]
\scriptsize{

{\centering
\setlength{\tabcolsep}{2pt}
\caption{\small{Consistency of attributes for users in \datasetFF ; $\dagger$ in parenthesis, the consistency only when information is available in both social networks.}}
%\\ \uline{Legend:} Tw~=~Twitter, Fb~=~Facebook, G+~=~Google+, M~=~Myspace, Fl~=~Flickr, Lnk~=~LinkedIn; 

%}
\vspace{-3mm}
\begin{tabular}{l||c|c|c|c|c}
  & \textbf{Screen Name}  & \textbf{Real Name} & \textbf{Location} & \textbf{Profile Photo}  &  \textbf{Friends}  \\
\hline
\hline 
Fb - Tw  & 38\% & 77\% & 23\% (77\%$\dagger$)  & 8\% (12\%) & 34\% (79\%) \\ 
Fb - Lnk  & 71\%  & 97\%  & 44\%  (83\%) & 11\% (23\%) & 0\%  \\ 
Tw - Fl & 40\%  & 25\%  (84\%)  & 5\% (67\%) & 5\% (22\%)  & 13\% (42\%)\\ 
Tw - Lnk & 36\%  & 83\% & 39\% (71\%) & 13\% (31\%) & 0\%\\ 

\end{tabular}
\label{tab:consistency}

}
\vspace{-2\baselineskip}
}
\end{table}%

 \vspace{2mm}
 \noindent \minisec{Attribute consistency in \matchingprofiles}\label{sec:consistency}
\label{sec:prop}
\noindent Table~\ref{tab:consistency} shows the proportion  of users who provide consistent values for an attribute in a pair of social networks out of all users.This proportion corresponds to the recall we can achieve using the attribute given the threshold used, as shown in the previous section.  In parenthesis, we also provide the equivalent proportion of users with consistent values only when the attribute value is available in both social networks (corresponding to the definition of $C$). This proportion better illustrates  how likely users are to provide consistent values, i.e., shows the users's attempt to maintain synched profiles. %We highlight three implications of our consistency analysis for matching profiles.


%By default, we show the values for profiles in \datasetFF-
%we use values for profiles in \datasetG only when we lacked the
%corresponding data in \datasetFF.  
%\update{Whenever attributes values are not available we consider them as inconsistent. }


First, we find that a large fraction of users provides similar {\it real names} across different social networks. Put differently, most users are not attempting to maintain distinct personas on different sites. This trend bodes well
for our ability to match the profiles of a user. %Note that even if real names have such high consistency, we will see that they cannot be used alone to match profiles in practice because there can be multiple people sharing the same name.  
%Thus, we need to combine real names with other attributes that have much lower consistency such as location or profile photo to be able to reliably match profiles at scale. Consequently, the number of profiles we can match will be smaller. 

Second, we  computed the percentage of \matchingprofiles in Twitter and Facebook
for which all public attributes in Table~\ref{tab:consistency} are
inconsistent. We find that there are 7\% of such users. These
users are likely assuming different personas on different sites and it
is very hard, if not impossible, to match their profiles using only the
public attributes that we consider in this paper. Thus, we can at most
hope to match profiles for 93\% of users. This percentage 
represents an upper bound on the recall for matching profiles based on public attributes.


%Third, some attributes like real name are considerably more consistent than others like location and profile photo. %The more consistent attributes
%are the more useful they are compared with less consistent attributes for
%matching profiles.

Third, the consistency differs between different social networks. Twitter and Facebook have one of the lowest consistency for each attribute while Facebook and LinkedIn have the highest consistency. Thus, users are more likely to maintain synched profiles across Facebook and LinkedIn than other pairs of social networks. 

%\update{\noindent \minisec{Implication on matching reliability}
%Both the availability and consistency of an attribute fundamentally limit the recall we can achieve to match profiles using the attribute.  For a given level of precision, as for the availability, if the consistency of a feature decreases then the recall will also decrease. The consistency of a feature does not vary with the scale of the dataset and it only depends whether users provide or not consistent values for an attribute. 
%}

%\if 0
%We use the thresholds obtained in the previous section to
%detect if an attribute is consistent or not.  Generally, about
%40\%-50\% of users have matching \emph{screen names} across different
%social networks.  Users in the \datasetG tend to be more consistent
%than users in the \datasetFF. \emph{Real names} are more consistent
%than scree
%n names, and their consistency varies between 40\% to 90\%.
%The consistency is higher between profiles on social networks that
%demand the usage of real names: Facebook, LinkedIn, and Google+.
%LinkedIn and Twitter as well as LinkedIn and Google+ have the highest
%photo consistency, around 30\%. Pairs of social networks that contain
%Facebook have the lowest consistency, probably because users change
%more often their profile photo on Facebook than in the other social
%networks.  For \emph{location} we show pairs of profiles that come
%with latitude/longitude tuples less than 70 Km apart.  There is a fair
%number of profiles that are geographically close~(between 40\% and
%70\%).  For \emph{friends}, Table~\ref{tab:consistency} presents the
%percentage of \matchingprofiles that have at least one common friend
%on two social networks. The friends consistency is high for pairs of
%profiles in the \datasetG. It ranges from 60\% to 90\%. In the
%\datasetFF, there are fewer profiles that share a friend: there are
%30\% between Flickr and Twitter and 64\% between Facebook and Twitter.
%\fi

%\if 0
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\subfloat[Screen name]{\label{fig:hist_u}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_avail_U.eps}}
%\subfloat[Real name]{\label{fig:hist_n}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_N.eps}}
%%\vspace{-3mm}
%
%\subfloat[Photo - Phash]{\label{fig:hist_p}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_avail_P.eps}}
%\subfloat[Photo - SIFT]{\label{fig:hist_p}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_avail_S.eps}}
%
%\subfloat[Location]{\label{fig:hist_l}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_avail_L.eps}}
%\subfloat[Friends]{\label{fig:hist_g}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_avail_G.eps}}
%%\vspace{-2mm}
%
%\caption{CDFs of similarity scores for matching and unmatching Twitter and Facebook profiles from \datasetFF including unavailability.}
%\label{fig:cdf_matching_vs_nonmatching_avail}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%\fi

\subsection{Attribute discriminability}
\label{sec:discr}

%\if 0
%\begin{figure*}[!htbp]
%%\vspace{-8mm}
%\begin{center}
%\subfloat[Real name]{\label{fig:cdf_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_N.eps}}
%\subfloat[Screen name]{\label{fig:cdf_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_U.eps}}
%%\subfloat[Photo - Phash]{\label{fig:cdf_m_nm_p}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_P.eps}}
%\subfloat[Photo (SIFT)]{\label{fig:cdf_m_nm_s}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_S.eps}}
%\subfloat[Location]{\label{fig:cdf_m_nm_l}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_L.eps}}
%\subfloat[Friends]{\label{fig:cdf_m_nm_f}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_F.eps}}
%
%%\subfloat[Real name]{\label{fig:cdf_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_N.eps}}
%%\subfloat[Screen name]{\label{fig:cdf_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_U.eps}}
%
%%\vspace{-2mm}
%\caption{Discriminability of attributes: CDFs of similarity scores between Twitter and Facebook \matchingprofiles and \nonmatchingprofiles from \smallscale.}
%\label{fig:cdf_m_nm}
%\end{center}
%\vspace{-2.5\baselineskip}
%\end{figure*}
%\fi 


\begin{figure*}[!htbp]
\vspace{-2mm}
{\centering
\subfloat[\small{Real name}]{\label{fig:cdf_new_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{cdf_new_M_NM_N.eps}}
\subfloat[\small{Screen name}]{\label{fig:cdf_new_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{cdf_new_M_NM_U.eps}}
%\subfloat[Photo - Phash]{\label{fig:cdf_m_nm_p}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_M_NM_pure_P.eps}}
\subfloat[\small{Photo (SIFT)}]{\label{fig:cdf_new_m_nm_s}\includegraphics[width=0.20\textwidth,height=2.5cm]{cdf_new_M_NM_S.eps}}
\subfloat[\small{Location}]{\label{fig:cdf_new_m_nm_l}\includegraphics[width=0.20\textwidth,height=2.5cm]{cdf_new_M_NM_L.eps}}
\subfloat[\small{Friends}]{\label{fig:cdf_new_m_nm_f}\includegraphics[width=0.20\textwidth,height=2.5cm]{cdf_new_M_NM_F.eps}}

%\subfloat[Real name]{\label{fig:cdf_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_N.eps}}
%\subfloat[Screen name]{\label{fig:cdf_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_U.eps}}

\vspace{-2mm}
%\caption{Discriminability of attributes: CDFs of similarity scores between Twitter and Facebook \matchingprofiles and \nonmatchingprofiles from \smallscale.}
\caption{\small{CDF of similarity scores for the matching Facebook profiles and for the most similar non-matching Facebook profile  in \datasetFF(sample) and the entire  Facebook (entire).}}
\label{fig:cdf_new_m_nm}
}
\vspace{-1.5\baselineskip}
\end{figure*}

\noindent The previous section showed that a large fraction of  users have consistent attribute values between their profiles. However, the number of profiles that we can match reliably is smaller because attribute values might not uniquely identify a single person.
%Thus, in this section we investigate the {\it discriminability} of attributes, i.e.  the extent to which the different values of an attribute can uniquely identify the matching profile in the target network.   The discriminability of attributes depends on the size of the dataset, while in a small dataset names might uniquely identity profiles, in a large dataset  they might not.  



To evaluate the discriminability of attributes, for each Twitter profile we compare the similarity of the matching Facebook profile with  the similarity of the most similar non-matching Facebook profile. 
Figure~\ref{fig:cdf_new_m_nm} shows the CDF of similarity scores in \datasetFF (sample). Zero means no similarity and
one means perfect similarity; except for location, where zero means perfect similarity
because it corresponds to the distance between locations. 
%For friends, zero similarity means no friends in common.  
The vertical lines represent the similarity thresholds for consistent attribute values used in the previous subsection. Given a threshold, we have perfect discriminability if there are no non-matching profiles with higher similarities. 
%Concretely, the y value corresponding to the similarity threshold in the distribution for the most similar non-matching profile represents an estimate of the (effective) discriminability $\tilde{D}$, whereas the value corresponding to the threshold for distribution of matching profiles represents the complementary of the consistency $1-C\cdot A$.
Concretely, for a given similarity threshold (x value), the y value for the distribution for the most similar non-matching profile represents an estimate of the (effective) discriminability $\tilde{D}$, whereas the y value for the distribution of matching profiles represents the complementary of the recall $1-C\cdot A$.

%Given a threshold, we have perfect discriminability if there are no non-matching profiles with higher similarities.

For the \emph{real name} and \emph{screen name} we see a clear
distinction between distributions of  matching and \nonmatching profiles in Figure~\ref{fig:cdf_new_m_nm}. The highest similarity of non-matching profiles is around 0.75 while a number matching profiles have similarities around 1.  This suggests that these attributes have a high discriminability. %  \rt{I don't fully understand the next sentence. I think that we should either elaborate or (probably best) just remove it. You'll study recall of the schemes later.} In practice, for real name for instance, it is possible to have a discriminability of 0.99 for a threshold giving a 0.6 recall.
For \emph{photo}, the two distributions are generally similar. The photo does not appear to have a very good overall discriminability because there are not many Facebook \matchingprofiles that use the same profile photo with the Twitter profile. However, for similarities large than 0.10,  when the profile photos are consistent, there are not many non-matching profiles. 
As expected, the \emph{location} does not have a good discriminability; even in a small dataset there are Facebook non-matching profiles with the same location as the Twitter profile. 
Finally,  \emph{friends} have a good discriminability between matching and \nonmatching profiles, i.e., it is uncommon to have non-matching profiles with many common friends.


%\comment{For a given threshold, the discriminability gives the lower bound of the number of false matches. The  discriminability can be used to compute the highest precision we can achieve using an attribute.}


%According to our definition in~\xref{sec:acid} if there exists a similarity threshold that splits all the matching profiles from non-matching profiles, then we can achieve a 100\% precision and 100\% recall. Figure~\ref{fig:cdf_new_m_nm_n}  shows that no such threshold exists for any of the attributes.}


%While the availability and consistency of attributes do not depend on the size of the dataset, the discriminability does, i.e., there is a much higher chance in a large dataset that there are non-matching profiles . 

%While, the availability and consistency of an attribute depend on the willingness of users to provide the information, the discriminability depends on the properties of all users in a social network.
%We specifically focus on evaluating (1) how discriminable are different attributes, and (2) how the discriminability of an attribute varies with the dataset we consider.  %Intuitively, the discriminability of names in a sampled small dataset is much higher than the discriminability in an entire social network.}

%\noindent We now investigate the {\it discriminability} of attributes,
%by which we refer to the extent to which different values of an attribute can be
%used to distinguish a single profile from all other profiles in a
%social network. 


%For a given Twitter profile, to evaluate whether an attribute value can uniquely identify the matching Facebook profile, we can simply check whether there are non-matching profiles that have the same or higher similarities with the Twitter profile than the matching Facebook profile. If such profiles exist, it means that the attribute value does not uniquely identify the matching profile. To evaluate the discriminability of an attribute, for each Twitter profile in \textsc{Twitter-Test} we compare the similarity in attribute values of the matching Facebook profile with the highest  similarity obtained for a non-matching profile. We analyze the non-matching profiles separately from  \textsc{Pairs-SmallScale-Data} in Figure~\ref{fig:cdf_new_m_nm} and  \textsc{Pairs-LargeScale-Data} in Figure~\ref{fig:cdf_new_ls_m_nm}, in order to assess how the discriminability varies with the dataset we consider. An attribute is highly discriminable if the similarity between matching profiles is high while the similarity between non-matching profiles is low. 

%\begin{figure}[!htbp]
%%\vspace{-8mm}
%{\centering
%\subfloat[Real name]{\label{fig:cdf_new_ls_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_ls_M_NM_N.eps}}
%\subfloat[Screen name]{\label{fig:cdf_new_ls_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_ls_M_NM_U.eps}}
%
%%\subfloat[Photo - Phash]{\label{fig:cdf_m_nm_p}\includegraphics[width=0.24\textwidth,height=2.9cm]{plots/cdf_new_M_NM_P.eps}}
%%\subfloat[Photo (SIFT)]{\label{fig:cdf_m_nm_s}\includegraphics[width=0.24\textwidth,height=2.9cm]{plots/cdf_new_M_NM_S.eps}}
%%\subfloat[Location]{\label{fig:cdf_m_nm_l}\includegraphics[width=0.24\textwidth,height=2.9cm]{plots/cdf_new_M_NM_L.eps}}
%
%%\subfloat[Friends]{\label{fig:cdf_m_nm_f}\includegraphics[width=0.24\textwidth,height=2.9cm]{plots/cdf_new_M_NM_F.eps}}
%%\vspace{-2mm}
%\caption{CDF of similarity scores for the matching Facebook profiles and for the most similar non-matching Facebook profile in all Facebook.}
%%\caption{ CDF of similarity scores for the matching Facebook profiles and for the most similar non-matching Facebook profile in all Facebook.}
%%\caption{CDFs of similarity scores between Twitter and Facebook \matchingprofiles and \nonmatchingprofiles over the entire social network.}
%\label{fig:cdf_new_ls_m_nm}
%
%}
%%\vspace{-1.5\baselineskip}
%\end{figure}


We do not have access to the whole Facebook dataset to evaluate the discriminability of all attributes over an entire social network, however, we exploit the Facebook Graph Search to estimate the discriminability of real names and screen names. For each Twitter profile we use Facebook Graph Search to retrieve all the profiles with the same or similar names and screen names. This procedure samples the non-matching profiles with the highest similarity; therefore it preserves the discriminability of the entire social network.
%
%Even if the discriminability of real names seems very high in a small scale dataset, it is lower over an entire social network.  Since we do not have access to the whole Facebook dataset we use the
%Facebook Graph Search to gather all the profiles that have the same or similar names with the Twitter profile. 
Figure~\ref{fig:cdf_new_m_nm_n} and~\ref{fig:cdf_new_m_nm_u} also presents the discriminability of real names and screen names over the entire Facebook (entire). As expected, the CDF of similarity score for non-matching profiles is much lower than it was at small scale.
Furthermore, for 60\% of the Twitter profiles, there is a non-matching Facebook profile that has \emph{exactly} the same real name and for 25\% exactly the same screen name. Even worse, the CDFs of Figure~\ref{fig:cdf_new_m_nm_n} for non-matching profiles are even below the CDFs for matching profiles which means that in many cases there are non-matching profiles that have even more similar names  with the Twitter profile than the matching profile.  These results show that names and screen names are actually not so discriminating in practice  and consequently shows the difficulty of reliably finding the matching profile in real-world social network. This also shows the risk of evaluating matching scheme over a sampled dataset because attributes have a much higher discriminability than over entire social networks.




























%\update{We evaluate the discriminability of an attribute by comparing the similarity in
%attribute values between profiles that belong to the same user with the similarity in attribute values between profiles that belong to different users. 
%More precisely, for each Twitter profile in \textsc{Twitter-Test} we compare the similarity in attributes values of the matching Facebook profile with the highest obtained similarity to non-matching profiles.  By comparing these similarities we can see whether there are any non-matching profiles in the target network that have similar attribute values with the Twitter profile other than the matching profile, i.e., whether the attribute value does or doesn not uniquely identify the matching profile.   
%To study how the discriminability of an attribute varies with the dataset we consider, we analyze the non-matching profiles separately from  \textsc{Pairs-SmallScale-Data} in Figure~\ref{fig:cdf_new_m_nm} and  \textsc{Pairs-LargeScale-Data} in Figure~\ref{fig:cdf_new_ls_m_nm}.
%An attribute is highly discriminable, if the similarity between matching profiles is high while the similarity between non-matching profiles is low.  }

% \update{More precisely, for each Twitter profile in \textsc{Twitter-Test} we compare three similarities: (1) the similarity in attributes values of the matching Facebook profile; (2) the highest obtained similarity to non-matching profiles in \smallscale; (3) the highest obtained similarity to non-matching profiles in \largescale.  By comparing these similarities we can see whether there are any non-matching profiles in the target network that have consistent values with the Twitter profile, i.e., the attribute value does not uniquely identify the matching profile.   
%To study how the discriminability of an attribute varies with the dataset we consider, we analyze the non-matching profiles separately from  \textsc{Pairs-SmallScale-Data} and  \textsc{Pairs-LargeScale-Data}.}

%We  compute the similarity scores between all attributes of the matching and non-matching profiles in \smallscale.
 

%Figure~\ref{fig:cdf_new_m_nm_n} shows the CDF of real name similarity scores for matching and \nonmatching profiles between Twitter and Facebook. The X-axis represents the similarity scores, where zero means no similarity and
%one means perfect similarity. Figures~\ref{fig:cdf_new_m_nm_u}~to~\ref{fig:cdf_new_m_nm_f} show the
%CDFs for other attributes.   For location, zero means perfect similarity
%because it corresponds to locations that have the same latitudes and
%longitudes. For friends, zero similarity means no friends in common. 
%% \update{To help the analysis, the vertical line represents the consistency threshold identified in the previous section. To analyze discriminability we are mainly interested in the part of the plot that is above the threshold (bellow for location) as we want to see how often there are non-matching profiles with consistent values.}
%Results for other pairs of social networks are similar, but we omit them due to space limitations.

%\update{For the \emph{real name} and \emph{screen name} there are many matching profiles that are above the consistency threshold, while there are only few non-matching profiles above for profiles in \smallscale, which would suggest a very good discriminability.  However, in \largescale 
%for a significant portion of Twitter profiles, there is a non-matching profile with consistent names.  There are actually more non-matching profiles with consistent names that matching profiles. This suggests that even if these attributes have a high discriminability, i.e., are efficient
%at separating matching and \nonmatching profiles in small datasets, they are not so discriminative at scale.}
%
%\update{For location and friends, the discriminability over \largescale is higher than the discriminability over \smallscale. This result is intuitive as there can be many people that live in the same place, however there are less people that have similar names and live in the same place.}
% \comment{add discussion about photo}


%For the \emph{real name} and \emph{screen name} we see a clear
%distinction between distributions of  matching and \nonmatching profiles. Non-matching profiles systematically have similarities around
%0.5 while \matchingprofiles have similarities around 1.  This suggests
%that these features have a high discriminability, i.e., are efficient
%at separating matching and \nonmatching profiles. 
%For \emph{photo},
%the two distributions are generally similar, with many scores around
%0.5 for Phash algorithm (this is a typical score returned by the
%perceptual hashing method for unrelated photos).  The photo does not
%have a very good overall discriminability because there are not many
%\matchingprofiles that use the same profile photo.  \emph{Location}
%and \emph{friends} also have a good discriminability between
%matching and \nonmatching profiles although it is lower than the
%discriminability of real names and screen names.



%Even if the discriminability of real names seems very high in \smallscale, it is lower over an entire social network as there are non-matching profiles with the same name as we see in  Figure~\ref{fig:cdf_new_ls_m_nm}.
%% presents the discriminability of
%%real names and screen names at scale when we consider the non-matching profiles from \largescale. As expected, 
%The CDF of similarity score for
%\nonmatchingprofiles is much closer to the CDF of matching profiles than in the \smallscale.  Furthermore, the CDFs of Figure~\ref{fig:cdf_new_ls_m_nm} for non-matching profiles are even below the CDFs for matching profiles. It means that, in many cases there are non-matching profiles that have even more similar names  with the Twitter profile than the matching profile.  These results show that names and screen names are actually not so discriminating at scale and consequently shows the difficulty of reliably finding the matching profile in large social networks. 
%Also, it shows the the risk of evaluating matching scheme over a sampled dataset because attributes have a much higher discriminability than over entire social networks.}
%
%\if 0
%A highly discriminating attribute would assume
%a unique value for each profile in a social network, while a less
%discriminating attribute would assume the same value for many
%different profiles in the social network.
%
%Discriminability, like consistency, is an important property for
%reliable profile matching. While consistency ensures that the
%attribute values of the \matchingprofiles match well the target profiles, the discriminability ensures that attribute values of all the
%other \nonmatchingprofiles in the site would be very different and
%inconsistent with the target profile. 
%
%Note that the discriminability of an attribute depends on the set of
%all profiles in a social network. Since it is hard to gather data
%about all profiles in a large social network like Facebook, we
%evaluate the discriminability of the attributes within a randomly
%drawn sample of 1000 profiles and a set of profiles that have
%
%Intuitively, the discriminability of an attribute is determined by the extent to
%which \matchingprofiles have very similar values while not matching
%profiles have very different values.  The extent to which matching
%profiles have very similar values is determined by the consistency of
%the attribute in \matchingprofiles while the extent to which
%not \matchingprofiles have very different values is determine by how
%unique are the values of an attribute in a dataset.  For example, if
%we consider the gender attribute even if \matchingprofiles mention
%the same gender there are also many \nonmatchingprofiles that have
%the same gender which makes the gender an attribute with low
%discriminability.
%
%We first study the discriminability of all the attributes into a
%random sampled dataset and we then study how the discriminability of
%attributes changes when considering a large-scale dataset.  The
%discriminability in the random sampled dataset shows how well an
%attribute is able to discriminate between correlated profiles and
%\nonmatchingprofiles picked at random.  However, since we focus on
%\matchingprofiles at large-scale the attributes will be used to
%discriminate between correlated profiles and very similar uncorrelated
%profiles. For this reason we also study their discriminability in a
%large-scale dataset.  \change{is the motivation ok to study 2
%  datasets?  --Oana}
%\fi
%
%\if 0
%\noindent {\bf 1. Discriminability within a random sampled dataset:}
%
%
%Figure~\ref{fig:cdf_matching_vs_nonmatching_avail} presents the same CDFs of similarity scores for each attribute but it includes the unavailability aspect of attributes. To show the unavailability, for photo -1 represents cases where one or both profiles did not have a photo, for location -1000 represents cases where the  location is unavailable and for friends  -100 represents cases when the friend lists are not available. 
%
%For the \emph{real name} and \emph{screen name} we see a clear
%distinction between distributions of  matching and \nonmatching profiles. Non-matching profiles systematically have similarities around
%0.5 while \matchingprofiles have similarities around 1.  This suggests
%that these attributes have a high discriminability, i.e., are efficient
%at separating matching and \nonmatching profiles.  Note that, even if the discriminability of real names is very high, when considering entire social networks, there can be a non negligible number of users with the same name.
%For \emph{photo},
%the two distributions are generally similar, with many scores around
%0.5 for Phash algorithm (this is a typical score returned by the
%perceptual hashing method for unrelated photos).  The photo does not
%have a very good overall discriminability because there are not many
%\matchingprofiles that use the same profile photo.  \emph{Location}
%and \emph{friends} also have a good discriminability between
%matching and \nonmatching profiles although it is lower than the
%discriminability of real names and screen names.
%%The more discriminable attributes are, the more useful they are to accurately match profiles. 
%
%% \begin{table}[htdp]
%%\caption{Percentage of Twitter profiles that have none, one or more Facebook profiles with matching attributes.}
%%\begin{center}
%%\begin{tabular}{c||c|c}
%%
%%& None matching   & More than \\
%%&  &   one matching \\
%%\hline
%%\hline
%%Real Name & 71\% &   29\% \\ 
%% Screen Name & 83\% &   17\% \\ 
%% Location & 58\% &   42\% \\ 
%% Photo - Phash & 32\% &   68\% \\ 
%% Photo - SIFT & \change{99\%} &   \change{ 1\%} \\ 
%% Friends & 74\% &   26\% \\ 
%% \hline
%% Real Name & 10\%  &  90\% \\ 
%% Screen Name & 32\%  &  68\% \\ 
%%% Location & 81\%  &  19\% \\ 
%%% Photo - Phash & 49\%  &  51\% \\ 
%%% Photo - SIFT & 82\%  &  18\% \\ 
%%% Friends & 96\%  &   4\% \\ 
%%\end{tabular}
%%\end{center}
%%\label{fig:matching_attr}
%%\end{table}%
%
%\change{I would introduce again this paragraph in the paper. It shows well some of the challenges when going to large scale.}
%
%
%To shows the extent to which the values of an attribute are unique to
%a user we investigate for each Twitter profile how many uncorrelated
%Facebook profiles have a matching attribute.  We use the thresholds
%from the previous section to decide if two values of an attribute
%match.  For friends we do not have thresholds inferred from AMT
%experiments so we choose a threshold of 2, i.e., if two profiles have
%more than 2 friends in common we consider that the friend attribute
%matches.
% 
%There are 71\% of Twitter profiles that have real names that do not
%match with any uncorrelated profile; the percentage is 82\% for screen
%names and 74\% for friends.  This shows that screen names, real names
%and friends have unique values, in the given dataset, for most of the
%users in the dataset.  The location of 58\% Twitter profiles does not
%match with any location of \nonmatchingprofiles and \change{XX\%} of
%Twitter profiles have a photo that does not match any photo of
%\nonmatchingprofiles.
%
%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.7\columnwidth]{plots/matching_sample_enire.eps}
%%\vspace{-2mm}
%\caption{CDF of the number of profiles with matching attributes for each attribute in part.}
%\label{fig:cdf_matching_all}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%
%
%%Figure~\ref{fig:cdf_matching_all} shows the CDF of the number of profiles that have a matching attribute with each Twitter profile. The X-axis is in log scale.  
%%Indeed, it is possible to find a threshold such that most correlated profiles have a
%%higher similarity score \emph{and} most \nonmatchingprofiles have a
%%lower similarity score. For a threshold of 1 for instance, we capture
%%no \nonmatchingprofiles, whereas there is still a significant
%%proportion of correlated profiles with a similarity score of 1.% (the
%%right end of the blue full line histograms, corresponding also to the
%%consistency numbers of Table~\ref{tab:consistency})
%%%
%%However there is no \nonmatchingprofiles with similarity score higher than 0.75 for the Phash algorithm and 0.11 for the SIFT algorithm while there are a some correlated profiles with such scores (about $10-15\%$). 
%%However the location is unavailable for more than 60\% of correlated profiles, which makes the overall discriminability of the attribute to be lower. 
%
%\noindent {\bf 2. Discriminability within a large-scale dataset:}
%
%
%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\subfloat[Real name]{\label{fig:hist_n}\includegraphics[width=0.25\textwidth]{plots/matching_sample_enire_N.eps}}
%\subfloat[Screen name]{\label{fig:hist_u}\includegraphics[width=0.25\textwidth]{plots/matching_sample_enire_U.eps}}
%%\vspace{-3mm}
%\caption{Difference between the discriminability of real names and screen names in a small random dataset and in a large-scale dataset.}
%\label{}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%
%The previous subsection showed that the real names and screen names
%have a very high discriminability, however when we consider an entire
%social network, the discriminability will be lower because more
%\nonmatchingprofiles will have similar values as the uniqueness of
%real names and screen names will decrease in a larger dataset.
%
%Since we do not have access to the whole Facebook dataset, to evaluate the discriminability of attributes over an entire social network  we use the Facebook Graph Search.   We limit ourselves to real
%names and screen names because we cannot estimate the uniqueness of
%other attributes using the Facebook Graph Search.  For each Twitter
%profile in the \datasetFF we follow the next methodology to find as
%many possible Facebook profiles with the same or similar real names or
%screen names.
%%
%First, we use the Facebook Graph Search service to obtain profiles
%with the same or similar real names as the Twitter profile. Facebook
%returns all the profiles with the same real name but also some
%profiles with similar real names. To get even more profiles with
%similar names, we apply a number of heuristics to the real name and
%the screen name so that we can find profiles with simple variations of
%the name (for example, if the real name is Barack Hussein Obama, we'll
%search for Barack Hussein, Barack Obama, and Hussein Obama; if there
%is only one name as BarackObama, we will try to split it). Finally, we
%test whether there is a Facebook profile with the exact same screen
%name as the Twitter profile. When the real name of the Twitter profile
%is a single word, we also check whether it is a screen name in
%Facebook.
%
%This method gives us for each Twitter profile a list of Facebook
%profiles with very similar real names and screen names so we now can
%estimate their uniqueness at large scale.  We consider again the
%thresholds for matching attributes from the previous section and check
%for each Twitter profile how many uncorrelated Facebook profiles have
%a matching attribute in the list of Facebook profiles. There are only
%10\% (compare with 71\% in the random dataset) of Twitter profiles
%that do not have a matching real name with an uncorrelated profile and
%32\% (compare with 83\% in the random dataset) that do not have a
%matching screen name. Thus, the uniqueness of real names and screen
%names is considerably lower in a large-scale dataset.  Note that this
%is an upper bound of the uniqueness since there might be other
%profiles with matching real names and screen names that we were not
%able to get with the Facebook Graph Search.
%
%
%Figure~\ref{fig:cdf_m_nm_largescale} presents the discriminability of
%real names and screen names at large-scale when we consider only the
%profiles with similar real names and screen names. The figure presents
%the CDF of similarity scores for correlated profiles an for
%\nonmatchingprofiles from the lists of Facebook profiles we
%previously obtained.  As expected, the CDF of similarity score for
%\nonmatchingprofiles it is much closer to the CDF of correlated
%profile than in the random dataset.  However, there is still a
%significant difference between correlated and uncorrelated profile
%that are similar.
%\fi

%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\subfloat[Real name]{\label{fig:cdf_m_nm_n_cs}\includegraphics[width=0.25\textwidth,height=3cm]{plots/cdf_candidateset_M_NM_N.eps}}
%\subfloat[Screen name]{\label{fig:cdf_m_nm_u_cs}\includegraphics[width=0.25\textwidth,height=3cm]{plots/cdf_candidateset_M_NM_U.eps}}
%\caption{Discriminability of attributes in a large-scale dataset: CDFs of similarity scores for correlated and uncorrelated Twitter and Facebook profiles.}
%\label{fig:cdf_m_nm_largescale}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%%\fi 


%
%
%\if 0
%\subsection{Summary}
%\begin{table}[htdp]
%\caption{The ACID properties of attributes used for matching identities. $\dagger$ due to the high false positive rate of face detection algorithms; $\ast$ depending on the specific attribute and social network.}
%\begin{center}
%\begin{tabular}{c|c|c|c|c}
%& A & C & I & D \\
%\hline
%\hline
%Screen name & high & high & medium & medium \\
%Real name & high & high & high & medium \\
%Photo & high & high & high & low$\dagger$ \\
%%Bio & high & medium & high & high \\
%%Writing style & high & high & low & low \\
%Location & low & medium & low & high \\
%%Tags & low & medium & high & high \\
%%Group membership & low & medium & high & high \\
%Graph structure & medium & medium & low & high \\
%\end{tabular}
%\end{center}
%\label{tab:acid}
%\end{table}%
%\fi


%\if 0

\subsection{Attribute  impersonability}
\noindent In most social networks a user is not required to prove that her online identity matches her offline person. 
%\noindent Users sign on into most social networks via weak identities, i.e., identities that are not verified and do not require users to prove that their online identities match their offline personalities. 
Since there is a lot of  personal data  publicly available,  it is very easy for attackers to create fake profiles that impersonate honest  users.  %For example, attackers can easily copy most of the profile attributes such as the real name, bio, location and profile photo. 
%Impersonation is another source of unreliability when matching accounts because there is a risk to match the profile of a honest user with an impersonating profile.
%Matching schemes that do not handle such cases risk to match the profile of a honest user with an impersonating profile.
Because such attacks could be a very big source of unreliability for matching schemes, we show evidence that such attacks indeed exist and they are more frequent than previously assumed. 

 To search for potential cases of impersonation we start with an initial set of 1.4 million random profiles in Twitter.  %\footnote{We obtained the initial set of Twitter profiles by starting with a seed profile that was impersonating a researcher and we did a breath first search crawl on the followers of the seed profile.}
%To be conservative we only search for other profiles in Twitter that have consistent names or screen names and also consistent bios or profile photos. %We use the previously proposed similarity metrics to check whether profile attributes are similar.  
 We find that, strikingly, a large fraction of profiles could be \emph{potential} victims of impersonation attacks:  18,662 Twitter profiles have at least another Twitter profile with consistent profile attributes. This gives a rough estimate of $p_{I}$ of 1\%.
 %Note that some of these profiles might actually correspond to users that maintain multiple profiles on Twitter.\footnote{Twitter allows users to have multiple profiles.} After three months, however, we revisited these profiles and we observed that 4,054 pairs of profiles with similar profile attributes had one profile suspended.  The suspended profiles were likely impersonating profiles which surprisingly shows that such attacks indeed exists and that they are quite  spread. 
 It is beyond the scope of this paper to thoroughly investigate such attacks but in~\xref{sec:3step} we propose a way to make matching schemes less vulnerable to impersonation attacks. 




% While some attributes are easy to copy, other are harder. For example, it is hard for an attacker to obtain the same list of friends as the honest user, because for an attacker is very hard to establish links to good users~\cite{Cao}.
%
%There is an emerging trend of malicious attackers and spammers that create fake profiles to impersonate honest users. Since one can use any values to fill the profile information when creating a profile on a social network, it is very easy to impersonate users.  Attributes such as real name, location, bio or profile photo are all very easy to copy. 
%Screen names are harder to impersonate because they are unique in a social network, so the impersonator cannot have the same screen name with the honest user. 
%Finally, friends are the hardest attribute to impersonate, out of the ones we consider, because for an attacker is very hard to establish links to good users~\cite{Cao}. 
%
%\change{add experiment discussion}
%A recent study showed that in fact there are many impersonators online and that they target not only celebrities but also random unpopular users~\cite{Goga}. Matching schemes that do not handle the existence of impersonators are vulnerable to match the wrong profile. 

% The harder the attribute is to impersonate the more reliable the matching scheme is. 
 %\fi

\section{Training \& Testing Matching \\  Schemes}\label{sec:data}
\label{sec:training}
\noindent In this section, we focus our attention on the datasets used
to train and evaluate (test) matching schemes. 
%When sampling datasets for training or
%testing, it is important to ensure that the ACID properties of
%features found in the real-world large datasets are preserved. 
To estimate well the precision and recall in practice, we should test for each profile $a^{1}$ the accuracy of finding the \matchingprofiles $\hat{a}^{2}$ out of all the
profiles $a^{2} \in SN_2$.  If we consider large social networks like
Facebook, Twitter, or Google+, $SN_{2}$ has hundreds of millions of
profiles.   Obtaining such complete datasets is impractical, thus, we have to sample a number of profiles in the network.

%The sampling used in previous studies which takes non-matching pairs uniformly at random severely over-estimates the discriminability and therefore the precision at scale. 
Most previous studies sampled datasets by picking matching and non-matching profiles at random.  
%We argue that such random sampling
%fails to preserve the ACID properties of features found in the
%original large datasets.
Such random sampling fails to capture the precision and recall of matching schemes in practice because  it severely over-estimates the discriminability of attributes found in the original social network (as seen in~\xref{sec:discr}) and therefore it severely over-estimates precision. 
%For instance, our analysis in the previous section shows that discriminability of an attribute increases in a small random sample of user profiles, consequently, allowing matching schemes to
%achieve higher (misleading) reliability when they are evaluated over
%small random samples of real-world social networks.
%because it is very unlikely to have non-matching profiles that look
%similar in such small datasets, the evaluation over a small dataset is
%a misleading indicator of the accuracy of a matching scheme in
%real-world social networks.  
%To estimate well the precision and recall of a matching scheme in practice, when sampling datasets for training or testing, the key is to ensure that the datasets includes \emph{all potential} false matches, all profiles that could be mistakenly matched by the matching scheme. 
%To estimate well the precision and recall of a matching scheme in practice, the sampled dataset needs to preserve the precision and recall of original social network. 
To estimate well the reliability of a matching scheme in practice, the sampled dataset needs to preserve the precision and recall of the original social network at least for high values of precision.
The key to ensure this is to sample \emph{all potential} false matches, i.e., all profiles that could be mistakenly matched by the matching scheme. 
%
Thus, we build two datasets: (1) a \emph{reliability non-preserving sampled dataset} for
comparison with previous techniques (as this is the standard
evaluation method); and (2) a \emph{reliability preserving sampled dataset} that strives  to capture all possible false matches in a social network to better estimate the reliability of matching schemes in practice. 

We generate a reliability preserving sampled dataset for
matching Twitter and Facebook. Although building such
dataset for other social networks is possible, the process is
strenuous. Instead, we take two of the most popular
social networks to show the limitations for matching
profiles across real-world social networks.  

%that is able to better estimate the reliability of matching schemes in real-world social networks.
%On the other hand, as we shall see, the method proposed in this paper corresponds to sampling the non-matching pairs with highest similarity, which preserves the discriminability and therefore allows us to obtain a good estimation of the precision at scale. 
%The intuition behind building the emulated large-scale dataset is
%that, even if we cannot collect all profiles in a social network, we
%can collect a subset of profiles that are the most similar with the
%profile we want to match. Our assumption is that if a matching scheme
%is able to disambiguate the \matchingprofile out of a small set of
%very similar profiles, most likely it is able to disambiguate the
%\matchingprofile out of a larger set of less similar profiles. Thus,
%the accuracy of a matching scheme over the emulated large scale
%dataset is a reliable indicator of the accuracy in real-world social
%networks. We detail next how we gathered the ground truth data and
%build the two datasets.



%\if 0
%\noindent To design a solution to the reliable profile matching
%problem described in~\xref{sec:problem_definition} we leverage the
%five public attributes we studied in the previous section.  We propose
%two schemes to combine the public attributes to match profiles. We
%first present a scheme that matches profiles in one step, this
%approach is similar with what previous works have done and we show
%that the scheme does not scale well. We then propose an approach in
%three steps that is able to reliably match profiles at scale, i.e.,
%across entire social networks.  
%\fi




%\paragraph{Random sampled dataset}



 \vspace{2mm}
 \noindent \minisec{Reliability-non-preserving sampling}
%\move{Note that the previous section shows that Twitter and Facebook
%have the lowest attribute availability and consistency; thus the
%accuracy of schemes in other social networks should be higher than
%what we obtain for Twitter and Facebook.}
\noindent %We build small-scale datasets similar to what was used to
%evaluate previous matching schemes for comparison.  
We randomly sample 850 matching Twitter-Facebook profiles from \datasetFF 
%(we call them the
%\textsc{Twitter-Test} profiles) and their 1,000 matching Facebook
%profiles. 
%Using these profiles 
and we use them to build 722,500  pairwise
combinations of Twitter-Facebook profiles (850 positive  and 721,650 negative examples). We call the resulting dataset the \smallscale.
The \smallscale dataset preserves the availability and consistency of attributes in the original social network, but it does not preserve the discriminability and non-impersonability. Thus, the dataset does not preserve the precision of the original social network.  Note that,  datasets such as \datasetG, which have been used in previous work, do not even preserve the availability and consistency of attributes because they are biased towards a particular kind of users (as seen in~\xref{sec:avail}); hence they do not preserve recall.


%contains 1,000 pairs of matching profiles and 990,000 pairs of random
%non-matching profiles.  With these profiles we build a dataset that
%contains 1 million pairs of Twitter-Facebook profiles out of which
%1,000 are matching profiles. We call this dataset the .
%\remove{The typical way to evaluate a matching scheme is to
%measure how well it can detect the 1,000 Twitter-Facebook matching
%profiles out of all pairs of profiles.}



%\if 0
%
%We select 1,000 random Twitter profiles from \datasetFF (the
%\textsc{Twitter-Test}) for which we know their corresponding 1,000
%Facebook profiles (the \textsc{Facebook-Test}). To evaluate the scheme
%at small scale we can evaluate the accuracy of the matching scheme to
%detect the 1,000 $(a,\hat{a})$ profile pairs where $a \in
%\textsc{Twitter-Test}$ and $b \in \textsc{Facebook-Test}$ and
%$user(a)=user(\hat{a})$ (the \positivetest) and the 999,000 $(a,b)$
%profile pairs where $a \in \textsc{Twitter-Test}$ and $b \in
%\textsc{Facebook-Test}$ and $user(a) \neq user(\hat{a})$ (the
%\negativetest).
%
%\fi 

%\paragraph{Emulated large sampled dataset}

 \vspace{2mm}
 \noindent \minisec{Reliability-preserving sampling}
%The specific precision
%and recall obtained for other social networks depend on their ACID
%properties.
%Our findings are not specific to these social networks. \rt{Maybe we can say how our 
%findings should vary for other pairs of social networks. Based on the ACID analysis we can speculate no?}
%To estimate well the precision and recall in practice, we should test for each profile $a^{1}$ the accuracy of finding the matching profile $\hat{a}^{2}$ out of all the
%profiles $b \in SN_2$.  If we consider large social networks like
%Facebook, Twitter, or Google+, $SN_{2}$ has hundreds of millions of
%profiles.  Obtaining such complete datasets is impractical. 
\noindent To preserve the reliability over the original social network, our sampling strategy is to sample non-matching profiles that have a reasonably high similarity to $a^{1}$ and ignore non-matching profiles that have a very small chance of matching. We note the set of most similar profiles to $a^{1}$ in $SN_2$  as $C(a^{1}) \subset SN_2$. A  comprehensive $C(a^{1})$ includes all the Facebook profiles which could be potential false matches. 

Given that our analysis
in~\xref{sec:consistency} shows that  most Twitter-Facebook
\matchingprofiles have consistent real names or 
screen names, we hope to build a comprehensive $C(a^{1})$ by
exploiting the Facebook search API, which allows searching for people by name. 
%\move{Our assumption is that if a matching scheme is able to
%disambiguate the \matchingprofile out of a small set of very similar
%profiles, most likely it is able to disambiguate the \matchingprofile
%out of a larger set of less similar profiles. }
%We can generate the candidate set leveraging the search APIs social
%networks provide.
%\footnote{Facebook actually allows to search for people in a
 % particular location but the number of results returned is limited to
 % a few hundreds.}
%1,000 Twitter profiles from \datasetFF (the same we choose for the
%small dataset) Specifically, in this section, we focus on finding
%\matchingprofiles from the Facebook social network for profiles drawn
%from the Twitter social network.
%
For each Twitter profile, $a^{1}$ (we sample the same Twitter profiles from \smallscale), we generate $C(a^{1})$ using the Facebook search API to find
profiles with the same or similar real name or screen name as $a^{1}$.
%The Facebook search API allows to search for people by name, however,
%it is not possible to search by other attributes.\footnote{Facebook
%actually allows to search for people in a particular location but the
%number of results returned is limited to a few hundreds.}
%For each profile, we collect their publicly visible attributes. 
The resulting dataset, which we call \largescale, contains over 270,000
combinations of profiles $(a^{1},a^{2})$ where  $a^{2} \in C(a^{1})$. Thus, for each Twitter profile the dataset contains in average 320 Facebook profiles with similar names.
%We evaluate the precision and recall of matching schemes to find $\hat{a}^{2} $ in $C(a^{1})$ instead of in $SN_2$.
%we evaluate the accuracy of the matching scheme to detect the
%Facebook \matchingprofile $\hat{a}$ of a given Twitter profile $a$
%out of the candidate set, $C(a)$. \update{Or, To evaluate the
%matching schemes at scale we evaluate the accuracy of the schemes to
%detect the matching Twitter-Facebook profiles out of the 320,000
%combinations of profiles.
%\remove{Note that, even if the dataset does not contain all hundreds of
%millions of possible pairs, it contains for each Twitter profile the
%hardest Facebook profiles to distinguish from, emulating this way the
%evaluation over an entire social network.}
%Note that since for 30\% of Twitter profiles the matching Facebook
%profile is not in $C(a)$ we will underestimate the recall of matching
%schemes at scale by up to 30\%.

Our analysis shows that the \matchingprofile of $a^{1}$ is in $C(a^{1})$ (i.e., $\hat{a}^{2} \in C(a^{1})$) for 70\% of Twitter profiles.
%\footnote{\small{This percentage is lower than the 77\% of Facebook-Twitter \matchingprofiles with consistent real names, because of Facebook's algorithm to return profiles with similar names and the fact that Facebook users can choose for their profiles not to appear in name searches. This limitation is out of our control and affects any profile matching system that uses the Facebook search API and implies. In \datasetG, for 82\% Twitter profiles $\hat{a}^{2} \subset C(a^{1})$.}} 
This implies that for 70\% of cases we selected at least all non-matching profiles with higher name similarity than the matching profile.  Additionally, the median similarity of the least similar real name in $C(a^{1})$ is 0.5, while the median similarity of matching profiles is 0.97.  This means that we also catch many Facebook profiles with lower name similarity than the matching profiles.  Thus, the only possible false matches that we miss are the ones that have very different names.  %We believe their number should be very small as there are only 7\% matching profiles that have a name similarity lower than 0.5. \comment{is the last argument is more confusing than helping?}

Note that the reliability preserving sampling does not sample the matching profile when there is little chance for it to match (in 30\% of the cases). We actually tried to train and test matching schemes with or without including the unsampled matching profiles in the \largescale and the reliability did not differ significantly.

Our sampling strategy ensures that the discriminability and impersonability of real names and screen names found in the real-world datasets are preserved.  It might over-estimate, however, the discriminability of location, friends, and profile photos since we do not sample in $C(a^{1})$ profiles with similar location, friends or photos if they do not also have similar names or screen names. 
%Evaluating matching schemes over $C(a^{1})$ rather than the set of all
%Facebook profiles leads to an under-estimation of both the true
%matches (when the \matchingprofile, $\hat{a}^{2}$, is not in $C(a^{1})$) and
%the false matches (when one or more \nonmatchingprofiles that are
%similar to $a^{1}$ are not in $C(a^{1})$).  
Evaluating matching schemes over $C(a^{1})$ rather than all $SN_2$ could lead to an under-estimation of 
the false matches. Thus, the precision we obtain over this dataset is an upper bound on the precision in practice.  This implies that the limits of reliably matching schemes in practice can only be worse than what we show in this paper. 
%We believe, however, that the limits will not be far from the ones we measure because there will be few false matches with very dissimilar names. 
We believe, however, that our sampling strategy gives a very good idea of the precision and recall in the real-world datasets because there will be very few false matches (if any) with very dissimilar names even if they have similar location, photo or friends. 

Another limitation of the dataset is that it does not contain cases where a profile $a^{1}$ has multiple  matching profiles in $SN_2$. This is a consequence of our method to gather ground truth~(\xref{sec:gt}) that only gives a single matching profile in $SN_2$ for each $a^{1}$. The implications of this limitation on our evaluation is that there might be some matching profiles that we consider as false matches whereas they are not. Since Facebook enforces the policy that users should only have one profile, we believe there are not many such cases and the reliability we measure is likely close to the real-world reliability.

In practice, there are Twitter users that do not have a matching Facebook profile, but our datasets do not contain such cases. To evaluate how matching schemes perform in such scenarios, we test  in~\xref{sec:3step} the reliability of matching schemes when we remove the matching profile from \largescale. 
%Next section evaluates matching schemes when we know there is a matching profile in $SN_2$, however, in~\xref{sec:3step}, we will also evaluate how matching schemes perform when there is no matching profile in $SN_2$.  

%
%\paragraph{Emulated large dataset}\label{sec:evalscale}
%
%\noindent We generate an emulated large dataset for
%matching Twitter and Facebook. Although building such
%dataset for other social networks is possible, the process is
%strenuous. Instead, we take the example of two of the most popular
%social networks to show the limitations for matching
%profiles across real-world social networks.  
%%The specific precision
%%and recall obtained for other social networks depend on their ACID
%%properties.
%%Our findings are not specific to these social networks. \rt{Maybe we can say how our 
%%findings should vary for other pairs of social networks. Based on the ACID analysis we can speculate no?}
%
%The ideal method to evaluate a matching scheme in real-world social
%networks is to test for each account $a \in SN_1$ the accuracy of
%finding the matching account $\hat{a} \in SN_2$ out of all the
%accounts $b \in SN_2$.  If we consider large social networks like
%Facebook, Twitter, or Google+, $SN_{2}$ has hundreds of millions of
%profiles.  Obtaining such complete datasets is impractical. Instead,
%we resort to an optimization. For a given profile in $a \in SN_1$, we
%preselect a {\it candidate set} of profiles that are the most similar
%to $a$, $C(a) \subset SN_2$. Then, we evaluate the accuracy of
%matching schemes to find $\hat{a} $ in $C(a)$ instead of in $SN_2$.
%%\move{Our assumption is that if a matching scheme is able to
%%disambiguate the \matchingprofile out of a small set of very similar
%%profiles, most likely it is able to disambiguate the \matchingprofile
%%out of a larger set of less similar profiles. }
%
%
%%We can generate the candidate set leveraging the search APIs social
%%networks provide.
%A perfect candidate set would include the Facebook \matchingprofile,
%$\hat{a}$, as well as all the Facebook profiles that are similar with
%the target Twitter profile, $a$. Given that our analysis
%in~\xref{sec:consistency} shows that 77\% of Twitter-Facebook
%\matchingprofiles have consistent real names and 38\% have consistent
%screen names we hope to build a comprehensive candidate set by
%exploiting the Facebook search API, which allows searching people by
%name.\footnote{Facebook actually allows to search for people in a
%  particular location but the number of results returned is limited to
%  a few hundreds.}
%%1,000 Twitter profiles from \datasetFF (the same we choose for the
%%small dataset) Specifically, in this section, we focus on finding
%%\matchingprofiles from the Facebook social network for profiles drawn
%%from the Twitter social network.
%For each Twitter profile, $a$, in the set of \textsc{Twitter-Test}
%profiles, we generate $C(a)$ using the Facebook search API to find
%profiles with the same or similar real name or screen name as $a$.
%%The Facebook search API allows to search for people by name, however,
%%it is not possible to search by other attributes.\footnote{Facebook
%%actually allows to search for people in a particular location but the
%%number of results returned is limited to a few hundreds.}
%For each profile, we collect their publicly visible attributes.  The
%resulting dataset, which we call \largescale, contains over 320,000
%combinations of profiles $(a,b)$ where $a \in \textsc{Twitter-Test}$
%and $b \in C(a)$.
%%we evaluate the accuracy of the matching scheme to detect the
%%Facebook \matchingprofile $\hat{a}$ of a given Twitter profile $a$
%%out of the candidate set, $C(a)$. \update{Or, To evaluate the
%%matching schemes at scale we evaluate the accuracy of the schemes to
%%detect the matching Twitter-Facebook profiles out of the 320,000
%%combinations of profiles.
%Note that even if the dataset does not contain all hundreds of
%millions of possible pairs, it contains for each Twitter profile the
%hardest Facebook profiles to distinguish from, emulating this way the
%evaluation over an entire social network.
%%Note that since for 30\% of Twitter profiles the matching Facebook
%%profile is not in $C(a)$ we will underestimate the recall of matching
%%schemes at scale by up to 30\%.
%
%
%Evaluating matching schemes over $C(a)$ rather than the set of all
%Facebook profiles leads to an under-estimation of both the true
%matches (when the \matchingprofile, $\hat{a}$, is not in $C(a)$) and
%the false matches (when one or more \nonmatchingprofiles that are
%similar to $a$ are not in $C(a)$).  Our analysis shows that the
%Facebook \matchingprofile belongs to the candidate set for 70\%
%Twitter profiles.\footnote{This percentage is 82\% for profiles in
%  \datasetG.} This percentage is lower than the 77\% of
%Facebook-Twitter \matchingprofiles with consistent real names, because
%of Facebook's algorithm to return profiles with similar names. This
%limitation is out of our control and would affect any real system that
%uses the Facebook API and implies that we underestimate the true
%positive rate/recall by 30\% when using this dataset.
%
%
%\comment{include matching when not there}


%Our aim in this paper is to (1) analyze to which extent we can match
%profiles across social networks; (2) understand and mitigate the
%challenges of matching profiles at scale.


%\if 0
%
%\footnote{Note that for 30\% of Twitter profiles the matching Facebook
%  profiles are not in $C(a)$, thus the maximum achievable recall is
%  70\%.} (the \positivelargescale) and the non-matching pairs of
%profiles $(a,b)$ where $a \in \textsc{Twitter-Test}$ and $b \in C(a)$
%(the \negativelargescale).
%
%To evaluate the matching schemes at scale, we generate the dataset of
%all possible pairs of profiles $(a,b)$ where $a \in$ the 1,000 Twitter
%profiles from \datasetFF (the same we choose for the small dataset)
%and $b \in C(a)$. The dataset contains over 320,000 pairs of profiles.
%%we evaluate the accuracy of the matching scheme to detect the Facebook \matchingprofile $\hat{a}$ of a given Twitter profile $a$ out of the candidate set, $C(a)$. \update{Or, 
%We evaluate the accuracy of the matching scheme to detect the 1,000 matching Twitter-Facebook profiles (the \positivelargescale) and the non-matching pairs of profiles $(a,b)$ where $a \in$ Twitter  and $b \in C(a)$ (we call this dataset \negativelargescale). 
%
%\fi 



%
%\if 0
%
%\oana{give example why is not good, just say prec/rec is better than
%  tpr/fpr showing the accuracy of matching schemes. explain what
%  precision means in practice}
%
%\oana{At a first glance, these results are promising. However, at a
%  closer look, these results translate into a 89\% recall for a 8\%
%  precision, i.e. only in 8\% of the profiles linked by the \sysname
%  are actually \matchingprofiles.  This is due to the fact that the
%  number of possible \nonmatchingprofiles ($\sim$ 1 million) is much
%  higher than the number of \matchingprofiles 1,000.  Thus, even for a
%  small dataset we have to choose a threshold for $p$ that corresponds
%  to smaller false positive rates. For a threshold corresponding to a
%  $10^{-3}$ false positive rate, we get a 85\% true positive rate and
%  a 45\% precision while for a $10^{-4}$ false positive rate, we get a
%  83\% true positive rate and a 89\% precision. Thus, even for small
%  datasets, to obtain an accurate matching we need to focus on very
%  small false positive rates. }
%
%\oana{Unfortunately in large social networks like Facebook, Twitter,
%  and Google+, where the number of users is larger than 500 million,
%  even a low false positive rate of $10^{-4}$ would link several
%  hundred profiles on the other site, most of which are not
%  \matching. Since profiles have a single \matching profile on another
%  site, distinguishing this single profile from the haystack of
%  hundreds of millions of profiles poses a serious scalability
%  challenge.}  
%\fi





%\section{Evaluation Method}


%\noindent Before presenting our  schemes to match profiles, we present the data and the methods we use to evaluate them. %We first present our method to gather ground truth data of matching profiles. 
%First, we present a method to evaluate matching schemes over a sampled small dataset. This evaluation method was used by most previous studies. The evaluation over a small dataset, however, is a misleading indicator of the accuracy over real-world social networks. Thus, we also present a method to evaluate the matching schemes at scale over entire social networks. 

\if 0
\noindent To design a solution to the reliable profile matching problem described in~\xref{sec:problem_definition} we leverage the five public attributes we studied in the previous section. 
We propose two schemes to combine the public attributes to match profiles. We first present a scheme that matches profiles in one step, this approach is similar with what previous works have done and we show that the scheme does not scale well. We then propose an approach in three steps that is able to reliably match profiles at scale, i.e., across entire social networks.
\fi


\if 0
\subsection{Evaluation against human workers}
\label{sec:eval_amt}

The evaluation over a small dataset and at scale measure the accuracy of the matching schemes against the ground truth, which is the standard way to evaluate such schemes. However, we can obtain a more interesting and different perspective by evaluating their accuracy against human workers. The practice of employing  human workers to do simple tasks such as detecting fake or spam profiles is becoming more and more popular and is used by companies like Facebook and Twitter. Humans are particularly good at such tasks and are often much better than machines~\cite{WangMWWMZZ13}. We can consider human workers as a gold standard for matching profiles because they are very good at identifying persons. Thus, in this evaluation we focus on understanding: 1) how well humans can detect matching profiles; and 2) what are the cases when the matching scheme performs worst than humans and when it performs better. 

%Humans are usually very good at recognizing persons, so we can consider them as a gold standard for matching profiles. }

Here, we investigate the extent to which Human Intelligence Tasks (HITs) can detect profiles that belong to the same user using only publicly visible attributes.  Later, we will consider more complex scenarios where AMT workers have to choose the matching-profile out of a list of similar profiles, to allow a better comparison with our evaluation at scale.



%We continue by investigating the extent to which Human Intelligence Tasks (HITs) can detect profiles that belong to the same user using only publicly visible attributes. 
%\new{We start by showing a simple experiments, where the only goal is to check how well human workers can detect if two \matchingprofiles belong to the same person.} 
%\new{Later, we will study harder scenarios  where AMT workers have to choose the \matchingprofile out of a list of similar profiles. }
\fi 


\if 0
\paragraph{Testing linkability using HITs}

\if 0
{\bf In this section, we try to understand the extent to which \matching
  profiles can be linked as belonging to the same user using Human
  Intelligence Tasks (HITs). -- KG}

{\bf We quantify the accuracy with which \matching and \nonmatching
  profiles can be {\it linked} using only publicly visible
  attributes. We use dataset 1 for this evaluation and randomly select
  100 \matching and 100 \nonmatchingprofiles. -- KG}

{\bf Take-away: AMT users are able to link a large fraction of
  profiles wuth high accuracy -- suggesting that many users are not
  attempting to maintain unlinkability between their profiles and
  hinting at ways to scale profile matching. Motivated by this
  observation, in the rest of this section we design automated
  techniques for inferring linability accurately relying only on
  publicly available profile attributes. We also compare the accuracy
  of the proposed techniques with that of AMT users. -- KG}

{\bf Also list the attributes that users found helpful for linking or
  unlinking profiles. We pick from these attributes in the later
  sections. -- KG}

\fi

\if 0
{\bf Take-away: We also analyze the different features that were used
  by AMT workers to identify \matchingprofiles. How frequently the
  features were used. -- KG}
\fi



  
%\minisec{Methodology to evaluate linkability} 


\noindent To investigate the detectability of \matchingprofiles by
humans we set up an Amazon Mechanical Turk (AMT) experiment where we
ask AMT workers if they think that a Twitter and a Facebook profile
belong to the same individual or not.   We randomly select 100 pairs of
\matching and \nonmatching Twitter and Facebook profiles from
\datasetFF.  In each assignment, we give AMT workers a link to
a Facebook and a link to a Twitter profile and we ask them to choose
between three options: \emph{'the profiles belong to the same individual'}, \emph{'the
profiles do not belong to the same individual'}, and \emph{'cannot say'}.
% In
%addition to choosing one of this three options, we also ask AMT
%workers to provide a brief description about why they think the
%profiles belong to the same individual. %We asked them for a free form
%description to see what
%profile attributes they intuitively check without biasing or limiting them to a predefined set.   
For each assignment
we ask the opinion of three different AMT workers.  
%To ensure
%good quality results we only grant master workers to participate in
%the assignment and we mix assignments with \matching and \nonmatchingprofiles to
%avoid any bias of workers leaning that all the assignments correspond
%to one of the two categories.
We say that we have a \emph{full agreement} when all the AMT
workers chose the same answer, a \emph{majority agreement} when at
least two AMT workers chose the same answer, and \emph{no consensus}
when all workers chose different answers or at least two AMT workers were unable to say if
the profiles belong to the same individual.

\begin{table}[t]

\footnotesize{
\caption{Fraction of \matching and \nonmatching profiles detected by AMT workers out of the true \matching and \nonmatching profiles; $\dagger$ $X\%$($Y\%$) = fraction of profiles detected with majority agreement (fraction of profiles with full agreement).}
\vspace{-6mm}
\begin{center}
\begin{tabular}{c|c|c}
&  \textbf{True} & \textbf{True}\\
&  \textbf{\matching} &  \textbf{\nonmatching}\\
\hline
\hline
\textbf{Detected \matching} &  58\% (45\%)$\dagger$ & 0\%(0\%)  \\
\textbf{Detected \nonmatching} & 15\% (7\%) & 85\% (67\%) \\
\textbf{No Consensus} & 27\% & 15\% \\

\end{tabular}
\end{center}
\label{tab:amt_results}
}
\vspace{-2.5\baselineskip}
\end{table}%

%To investigate the detectability of \matching  profiles by humans we set up an Amazon Mechanical Turk
%(AMT) experiment where we ask AMT workers if they think that a Twitter
%and a Facebook profile belong to the same individual or not. We use \datasetFF for this evaluation and randomly select
%  100 \matching and 100 \nonmatching Twitter and Facebook profiles, we will refer to this sample dataset as \datasetAMT.  In each assignment, we show AMT workers
%a Facebook and a Twitter profile and we ask them to choose between
%three options: the profiles belong to the same individual, the
%profiles do not belong to the same individual and cannot say. Beside
%choosing one of this three options, we also ask AMT workers to provide
%a brief description about why they think the profiles represent the
%same individual. We asked them for a free form description to see what
%profile attributes they intuitively check without biasing or limiting them to a predefined set.   For each assignment
%we ask the opinion of three different AMT workers.  To ensure
%good quality results we only grant master workers to participate in
%the assignment and we mix assignments with \matching and \nonmatchingprofiles to
%avoid any bias of workers leaning that all the assignments correspond
%to one of the two categories.
%
%\minisec{Results} For each pair of \matching and \nonmatchingprofiles we have three
%answers. We say that we have a \emph{full agreement} when all the AMT
%workers chose the same answer, a \emph{majority agreement} when at
%least two AMT workers chose the same answer, and \emph{no consensus}
%when all workers chose different answers or at least two AMT workers were unable to say if
%the profiles belong or not to the same individual.

Table~\ref{tab:amt_results} shows the fractions of profiles matched by humans out of the tested matching and \nonmatching profiles.  
The AMT workers were able to detect with a majority agreement 58\% of the \matchingprofiles and 45\% with full agreement. For 27\% of the \matchingprofiles the AMT workers are not able to detect if they belong or not to the same individual, and for 15\% of the \matchingprofiles AMT workers said that they belong to different individuals. We manually investigated the latter cases and the profiles indeed correspond to different identities of the same user (i.e, either the profiles correspond to different personas, or one corresponds to a person and the other to an organization or interest group). 
The AMT workers were also able to detect with a very high accuracy the \nonmatchingprofiles: 85\% are detected with a majority agreement; no profiles are mistakenly identified as belonging to the same individual; and for 15\% there was no consensus.  We can conclude that humans can achieve a 58\% true positive rate for a 0\% false positive rate (100\% precision). 
We will see later in the paper, that in more complex scenarios where AMT workers  have to choose the \matchingprofile out of a list of similar looking profiles, they sometimes choose the wrong profile (i.e. they have a lower precision).
%\new{Note that, later in the paper, when we do an AMT experiment where we ask workers to decide if \nonmatching profiles that are similar belong to the same person, instead of randomly picking \nonmatching profiles, they have a lower precision.}


Humans are not able to obtain a higher true positive rate not because they are doing a bad job but because the \matchingprofiles that are not detected do not have enough available information to make the AMT workers confident that the profiles correspond to the same person.  To ensure the quality of their work, AMT workers where asked to describe in free text the reasons they think the profiles correspond to the same person. They gave very detailed
descriptions showing they are doing a thorough job. Furthermore, the average time an AMT worker took to decide if two profiles correspond to the same person is 6 minutes and 49 seconds. 

%\noindent \textbf{Takeaway I:} Human workers are able to detect 58\% of the \matchingprofiles without mistakenly mis-detecting any \nonmatchingprofile.  

%\noindent  \textbf{Takeaway II:} Not all the \matchingprofiles in the ground truth dataset correspond to the same person even if they are managed by the same person.

%\noindent  \textbf{Takeaway III:}  
These results suggest that a true positive rate of 58\% is more indicative of the expected fraction of profiles a matching scheme could detect instead of 100\% of the ground truth.

\fi


\if 0
We further analyze how often these attributes are mentioned in their
descriptions. Since AMT workers were allowed to input whatever they
wanted in the description sometimes they mentioned that the profiles
have the same profile photo and not mention anything else, however
this does not mean that the names or locations are not also the same.
In 30\% of the descriptions they said that the real name is a match,
in 6\% that the screen name is a match and, in 26\% that the location
is a match and in 31\% that the profile photo is the same.
Furthermore, in 31\% of the descriptions they said that the profiles
photos are not the same however the same person appears in both
photos; in 13\% of the descriptions they mentioned that there was some
common information in the profiles bios such as job, or university; in
10\% of descriptions mentioned that profiles show the same interests
and in 9\% that they link to the same sites. This fractions must not
be interpreted as an absolute value of the number of profiles that
have the same attribute value, however they show that users often
follow a set of common practices when creating profiles on different
social networks, such as maintaining the same screen name or using the
same photo. 

Another interesting insight given by these description is the amount of information people need to convince themselves that two profiles correspond to the same individual. Out of the 20 times the name is mentioned, only once is mentioned alone and the rest is mentioned with other attributes; screen name is mentioned alone 0/4, location 4/18 (22\%), photo 8/21(38\%), face 10/20 (50\%),  bio 3/7(43\%), interests/other 1/9(11\%) and links 3/6(50\%). 
This suggests that AMT workers feel confident that the two profiles are \matching whenever they see the same photo, face or links to the same site and they generally do not need additional information. However if  these attributes do not match they will need a combination of other attributes to match to feel confident.

\fi




\if 0
Results in this section suggest that many users are not attempting to maintain unlinkability between their profiles and hinting at ways to scale profile matching. Motivated by this observation, in the rest of this section we design automated  techniques for inferring linkability accurately relying only on publicly available profile attributes.
This results support our intuition that matching performance depend on
three main characteristics of the data users provide in their
profiles: the \emph{availability} of the attributes we consider and
the user \emph{consistency} in providing the same information across
social networks for a given attribute, and the \emph{discriminability}
of a feature to separate \matching and \nonmatchingprofiles.  We
quantify these proportions for the six social networks we study using
our \datasetFF and \datasetG.
\fi


\section{Generic matching problem}
\label{sec:linker}

%
%there are a bunch of papers that did matching
%why are there so many paper, is because they used either different datasets either different features
%however when it came to  the techniques they all used are all the same, 
%their fault was that they did not evaluated the matching scheme over a dataset with the same acid properties as the initial dataset. 




%\noindent The majority of previous works combined different features together to match profiles by using binary classifiers such as  SVM or Naive Bayes. As the techniques do not have anything fancy, In this section we build classifiers that are conceptually similar with what previous works have done.  
%
%In this section, we evaluate  matching scheme based on binary classifiers that combine all attributes together to match profiles in small scale datasets. \update{The matching schemes we evaluate are conceptually similar with what previous works have done.} \comment{insert here more about previous works} 

\noindent This section evaluates the reliability of matching schemes based on classifiers aimed at solving the generic case of the matching problem (see~\xref{sec:problem_definition}). %
We build classifiers that are conceptually similar to what previous works have done.  The primary difference between different previous matching schemes is the features and the datasets they used to train and test classifiers, however, they all use traditional classifier such as SVM and Naive Bayes. 
The goal of this section is not to build a matching scheme that is  better than previous ones but to investigate the limits of such schemes in practice.  


We first emulate the methodology employed by previous works: we train and test matching schemes with \smallscale, using all attributes.  Since some profile attributes have a high discriminability in the dataset, it is straightforward to build a matching scheme with high reliability. On top of this, there is little difference between the reliability of naive classification techniques and more sophisticated ones. 

%Furthermore, trying to optimize classifiers is useless as the difference between naive and more sophisticated classification techniques is not visible when tested over \smallscale. 
%In the next section, however, when we evaluate the schemes in practice, we will see the benefit  of having more sophisticated classification techniques.


We then investigating the reliability of matching schemes in practice by testing them over \largescale.
As expected, the precision of the previously built matching schemes drastically decreases to a point that makes them unusable.  Thereafter, we investigate the reasons behind such poor reliability and we evaluate different strategies to increase the precision and recall in practice. 
The resulting schemes are able to achieve a good precision, but the recall is still low. These results show the inherent difficulty of matching profiles reliably in today's large social networks.

%\update{In the next section, we will show that matching profiles at scale is much more challenging and that we need more sophisticated classification techniques to achieve a satisfying reliability. }

%
%The most straightforward way to build a matching scheme that combines multiple attributes is to treat the matching as a binary classification problem and use the similarity between different profile attributes as input values.  In this section, we first show a naive approach to train different binary classifiers to distinguish \profiles that match and that do not match. This approach mimics the strategy used by previous studies. Our experiments show that even if this approach achieves a good reliability when evaluated over a small scale dataset (as was also shown by previous work) the reliability actually drastically decreases when we  evaluate it at scale. We then investigate ways to optimize the training of the binary classifiers to improve the reliability of such matching schemes at scale. 

%\move{We evaluate the reliability of matching schemes to find the matching Facebook profile for a given Twitter profile. The matching method as well as the evaluation are not specific to these social networks. Note that the previous section shows that Twitter and Facebook have the lowest attribute availability and consistency; thus the reliability of schemes in other social networks should be higher than what we obtain for Twitter and Facebook.}


%\if 0
%\noindent \new{We present two matching schemes, one that is based on a binary classifier and mimics most of previous proposed methods which we will show it is not reliable at large scale and, a second method that can achieve high reliability even at large scale. }
%Before we describe these methods we present our evaluation methodology. 
%\fi 
%
%\if 0
%The ACID test, introduced in~\xref{sec:problem_definition}, helps us understand the quality, from a matching point of view, of public attributes. None of the public attributes satisfy all the ACID properties, however each property is satisfied by at least one attribute. 
%In this section, we make a first attempt to build a solution to our matching problem by combining all the attributes together so that we can obtain a matching scheme that satisfies all the ACID properties.
%\fi


\subsection{Evaluation over \smallscale}
\label{sec:linker_small}

%Ideally, for a given profile, the \sysname should correctly identify a single \matchingprofile and reject  all the other profiles. 

%\if 0
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.4\textwidth]{prec_rec_small_scale.eps}
%\vspace{-2mm}
%\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles using different techniques over a small scale dataset.}
%\label{fig:prec_rec_smallscale}
%\end{center}
%\vspace{-2\baselineskip}
%\end{figure}
%\fi

%\subsection{The \sysname}

%\noindent 



%\if 0
%\noindent \textbf{Input:} A profile   $a \in SN_1$ and a profile $b \in SN_2$. 
%\noindent \textbf{Output:} A binary answer whether $a$ and $b$ are \matchingprofiles or not, and the probability they are \matchingprofiles.
%\noindent \textbf{Objective:} Correctly link 
%\matchingprofiles without mistakenly linking \nonmatchingprofiles, i.e., maximize true positive rate while keeping  false positive rates very low.
%\noindent \textbf{Conception:} 
%\fi 


%\vspace{5mm}
%\noindent \textbf{Realization:} 
%\datasetFF contains ground truth on \matchingprofiles, which we can use to train the binary classifiers.  
%We select 1,000 random Twitter profiles from \datasetFF (the \textsc{Twitter-Train}) and their matching 1,000 Facebook profiles (the \textsc{Facebook-Train}). The Twitter and Facebook profiles used for training are different than the profiles used for evaluating the matching schemes (i.e, profiles used for testing).  Using these profiles we build a training dataset composed of 1,000 Twitter-Facebook matching profiles (the \positivetrain) and 999,000 non-matching Twitter-Facebook profiles (the \negativetrain). 

\noindent We use the \smallscale dataset to train and test four classification techniques  to match profiles: Naive Bayes, Decision Trees, Logistic Regression, and SVM. We split \smallscale in two: 70\% for training and 30\% for testing. 

%\minisec{Classification method} 
There are two important aspects to handle when training classifiers to match profiles:  ($1$) \emph{classes are very imbalanced} -- there are much more non-matching \profiles than matching \profiles.  Previous works handled this problem by balancing  the training instances by under-sampling the majority class~\cite{He:2009:LID:1591901.1592322}. We also adopt this technique and we randomly sample 850 non-matching profiles from the \smallscale;  ($2$) \emph{features have missing values} -- some attribute values may be unavailable hence the similarity value is missing (e.g., users may choose to omit their location or photo). %user profiles may be incomplete (users may choose to omit their location or photo).  
Thus, we must either work with classification techniques that are robust to missing
values (e.g., Naive Bayes) or identify methods to impute the missing values.  

We use 10-fold cross validation on the training data to evaluate the four classifiers with different combinations of parameters and different methods for imputing the missing feature values. We call the four resulting classifiers with the best optimized parameters the \linkernb, \linkersvm, \textsc{Linker-LR} and \textsc{Linker-DT}. 


%\if 0
%\toremove{We use 10-fold cross validation on the training set to analyze the tradeoff. 
%There is a clear distinction between \matchingprofiles and \nonmatchingprofiles:
%$p$ is close to one for most \matchingprofiles, whereas $p$
%is close to zero for the vast majority of \nonmatchingprofiles.  If
%we use a threshold of 0.94 for $p$ and we  consider all the pairs of profiles that have a probability higher than 0.94 as being \matchingprofiles and all the rest as \nonmatchingprofiles we detect 89\% of the \matchingprofiles with a false positive rate of 1\%. We choose this operational point because most of the previous works focused on false positive rates at this scale.}  
%\fi 







\begin{figure}[t]
\vspace{-2mm}
{\centering
\subfloat[\small{\smallscale}]{\label{fig:prec_rec_random}\includegraphics[width=0.22\textwidth, height=2.7cm]{prec_rec_random.eps}}
\subfloat[\small{\largescale}]{\label{fig:prec_rec_scale}\includegraphics[width=0.22\textwidth, height=2.7cm]{prec_rec_all_random_api.eps}}
\hspace{3mm}

\vspace{-3mm}
\subfloat[\small{\largescale: optimized classifiers}]{\label{fig:prec_rec_scale_retrained}\includegraphics[width=0.22\textwidth, height=2.7cm]{prec_rec_all_both_bis_api.eps}}
%\subfloat[Special cases: large scale]{\label{fig:prec_rec_scale_topmatch}\includegraphics[width=0.20\textwidth]{plots/prec_rec_topmatch.eps}}
\subfloat[\small{\largescale: special case}]{\label{fig:prec_rec_scale_topmatch}\includegraphics[width=0.22\textwidth, height=2.7cm]{prec_rec_top.eps}}
%\subfloat[Real name]{\label{fig:cdf_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_N.eps}}
%\subfloat[Screen name]{\label{fig:cdf_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_U.eps}}

\vspace{-2mm}
%\caption{Discriminability of attributes: CDFs of similarity scores between Twitter and Facebook \matchingprofiles and \nonmatchingprofiles from \smallscale.}
\caption{\small{Precision and recall tradeoff for matching Twitter to Facebook profiles using different classifiers when evaluated over \smallscale and \largescale.}} %\protect\rt{I think that we should change the legends in the figures to put maybe the name of the dataset. We also need to change the names of these datasets. These long names are clunky. Could maybe just say small and large. Also Pairs is not helping, would be better to name the social networks, something like TwFB-small and TwFB-large.} 

\label{fig:cdf_prec_rec}

}
\vspace{-0.5\baselineskip}
\end{figure}

%
%\begin{figure}[t]
%%\vspace{-8mm}
%{\centering
%\subfloat[\smallscale]{\label{fig:prec_rec_random}\includegraphics[width=0.22\textwidth, height=2.5cm]{plots/prec_rec_random_10fold.eps}}
%\subfloat[\largescale]{\label{fig:prec_rec_scale}\includegraphics[width=0.22\textwidth, height=2.5cm]{plots/prec_rec_all_random_10fold.eps}}
%\hspace{3mm}
%
%\subfloat[\largescale: optimized classifiers]{\label{fig:prec_rec_scale_retrained}\includegraphics[width=0.22\textwidth, height=2.3cm]{plots/prec_rec_all_both_bis_10fold.eps}}
%%\subfloat[Special cases: large scale]{\label{fig:prec_rec_scale_topmatch}\includegraphics[width=0.20\textwidth]{plots/prec_rec_topmatch.eps}}
%\subfloat[\largescale: special cases]{\label{fig:prec_rec_scale_topmatch}\includegraphics[width=0.22\textwidth, height=2.3cm]{plots/prec_rec_top.eps}}
%%\subfloat[Real name]{\label{fig:cdf_m_nm_n}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_N.eps}}
%%\subfloat[Screen name]{\label{fig:cdf_m_nm_u}\includegraphics[width=0.20\textwidth,height=2.5cm]{plots/cdf_new_M_NM_U.eps}}
%
%%\vspace{-2mm}
%%\caption{Discriminability of attributes: CDFs of similarity scores between Twitter and Facebook \matchingprofiles and \nonmatchingprofiles from \smallscale.}
%\caption{\update{Precision and recall tradeoff for matching Twitter to Facebook profiles using different classifiers when evaluated over \smallscale and \largescale.} %\protect\rt{I think that we should change the legends in the figures to put maybe the name of the dataset. We also need to change the names of these datasets. These long names are clunky. Could maybe just say small and large. Also Pairs is not helping, would be better to name the social networks, something like TwFB-small and TwFB-large.} 
%}
%\label{fig:cdf_prec_rec}
%
%}
%\vspace{-1\baselineskip}
%\end{figure}




%{plots/prec_rec_top.eps}


%
%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.35\textwidth, height=40mm]{plots/prec_rec_random.eps}
%%\vspace{-2mm}
%\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles using different classifiers over the small scale dataset.}
%\label{fig:prec_rec_random}
%\end{center}
%%\vspace{-2\baselineskip}
%\end{figure}
%

%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.35\textwidth]{plots/prec_rec_random_bis.eps}
%%\vspace{-2mm}
%\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles using different classifiers over the small scale dataset.}
%\label{fig:prec_rec_random}
%\end{center}
%%\vspace{-2\baselineskip}
%\end{figure}

%\noindent To test the matching scheme on the small dataset we use the classifiers to get the probability that each Twitter-Facebook profile in \textsc{Pairs-SmallScale-Test} is matching or not.  

%Appendix~\ref{sec:appendix} describes in more detail the
%classification techniques and how each handles missing values.
%, and their reliability. 
%
 

  We investigate the  tradeoff between  precision and recall for the different classifiers in Figure~\ref{fig:prec_rec_random}. Our results show that \linkernb out of the box, without imputing the missing values and \linkersvm and \textsc{Linker-DT} when we replace missing values with -1 achieve the highest reliability with a recall over 90\% for a 95\% precision. 
%SVM usually performs better than Naive Bayes in scenarios where all values are available, however its reliability decreases probably due to missing values.  
\textsc{Linker-LR} achieves  a lower recall, only 85\% for the same precision. 
Thus, as expected, even out of the box classification techniques such as Naive Bayes are able to achieve a high precision and recall over \smallscale. 

% from~\xref{sec:consistency} that there are 7\% of matching profiles that do not have any attribute available and consistent
 
 
 \vspace{2mm}
 \noindent \minisec{Analysis of matched pairs}
\label{sec:linker_small}
\noindent To understand what pairs of profiles the classifiers are matching, we analyze in Table~\ref{tab:av_cons_small_scale} the availability and consistency of attributes for the \emph{true matches},  the \emph{false matches},  and the \emph{missed matches} (the pairs of matching profiles that are \emph{not} detected by the classifier). 
We use \linkersvm with a threshold on the probability $p$ (outputted by the classifier) corresponding to a 95\% precision (and 90\% recall) to select the true, missed and false matches. 
%For each class of matches we analyze the fraction of profiles that have attributes that are both available and consistent (see Table~\ref{tab:av_cons_small_scale}).  %For computing the fraction of consistent attributes, we consider all the profiles with either available or not available attributes. %From the Table~\ref{tab:av_cons_small_scale} in the missed matches column, 
The table shows that the only matching profiles the \linkersvm is not able to identify are the ones that do not have available and consistent attributes: only 20\% of the missed matches have consistent names and 53\% of missed matches do not have \emph{any} consistent and available attribute (not shown in the table). %Thus, over small datasets such as \smallscale, the \linkersvm can reliably match profiles if they have available and consistent attributes. 
%This is coherent with our findings from~\xref{sec:consistency} that there are 7\%  of matching profiles that do not have any attribute available and consistent. 
The table also shows that the \linkersvm easily mistakes non-matching profiles form matching profiles if they have either consistent names or friends. While in this dataset this is not problematic, in practice this will lead to many false matches. 


 %Furthermore, the table shows the false matches only have consistent real names and friends while the other attributes are not consistent. \comment{what does this mean?}


%\begin{table}[htdp]
%\scriptsize{
%\caption{Fraction of true, missed and false matches  that have available and consistent attributes. We split the pairs of profiles in \smallscale in true, missed and false matches using the \linkersvm with a similarity threshold corresponding to a 95\% precision (and a 90\% recall).}
%\begin{center}
%\begin{tabular}{c|c|c|c|c|c|c}
% & \multicolumn{3}{c|}{Availability} & \multicolumn{3}{c}{Consistency} \\
%Feature & True  & Missed  & False  &  True  & Missed  & False  \\
% & Matches  & Matches  & Matches  &  Matches  & Matches  & Matches  \\
%\hline
%\hline
%Real Name  & 1.00 &  1.00 &  1.00 &  0.91 & 0.20 & 0.62 \\
%Screen Name  & 1.00 &  1.00 &  1.00 &  0.46 & 0.07 & 0.09 \\
%Location & 0.31 &  0.24 &  0.09 &  0.25 & 0.14 & 0.00 \\
%Photo& 0.63 &  0.57 &  0.62 &  0.10 & 0.01 & 0.00 \\
%Friends  & 0.45 &  0.35 &  0.65 &  0.34 & 0.22 & 0.38 \\
%\end{tabular}
%\end{center}
%\label{tab:av_cons_small_scale}
%}
%\end{table}%

\begin{table}[t]
%\vspace{-1mm}
\scriptsize{
\caption{\small{Fraction of true, missed and false matches  that have available and consistent attributes in \smallscale}. %We split the pairs of profiles in \smallscale in true, missed and false matches using the \linkersvm with a similarity threshold corresponding to a 95\% precision (and a 90\% recall).
}
\vspace{-3mm}
{\centering
\begin{tabular}{l|c|c|c|c}
& \multicolumn{4}{c}{Fraction of available and consistent attributes} \\
Feature   & All &  True  & Missed  & False  \\
 &  Matches   &  Matches  & Matches  & Matches  \\
\hline
\hline
Real Name   & 0.77 &  0.91 & 0.20 & 0.62 \\
Screen Name  & 0.38 &  0.46 & 0.07 & 0.09 \\
Location & 0.23 &  0.25 & 0.14 & 0.00 \\
Profile Photo & 0.08 &0.10 & 0.01 & 0.00 \\
Friends & 0.34 & 0.34 & 0.22 & 0.38 \\
\end{tabular}

}
\label{tab:av_cons_small_scale}
}
\vspace{-2\baselineskip}
\end{table}%

%
%\if 0
%\update{
%[11/13/14, 11:54:46 PM] Krishna Phani Gummadi: Compare table V and VII
%[11/13/14, 11:54:58 PM] Krishna Phani Gummadi: The recall went from 19% --> 33%
%[11/13/14, 11:55:11 PM] Krishna Phani Gummadi: The precision went from 95% --> 0.001%
%[11/13/14, 11:55:35 PM] Krishna Phani Gummadi: Look at "True Matches" Availability and Consistency values in these two tables
%[11/13/14, 11:55:44 PM] Krishna Phani Gummadi: The only difference is in "Friends"
%
%11/13/14, 11:56:36 PM] Krishna Phani Gummadi: Put differently, to increase recall from 19% to 33%, we started allowing matches based on other fields than friends
%[11/13/14, 11:57:00 PM] Krishna Phani Gummadi: But, the moment you do that you get a huge number of false matches.
%[11/13/14, 11:57:35 PM] Krishna Phani Gummadi: Compare the "false matches" Consistency values in Table V and Table VII
%[11/13/14, 11:58:09 PM] Krishna Phani Gummadi: Table V, even for false matches we require "friends" to match 0.57, for Table VII it can be zero
%[11/13/14, 11:58:39 PM] Krishna Phani Gummadi: Clearly, we have orders of magnitude more false matches in Table VII than Table V (given the steep drop in precision)
%[11/13/14, 11:59:08 PM] Krishna Phani Gummadi: And the one primary difference between false matches in Table V and Table VII is in terms of their "friends" consistency
%[11/14/14, 12:00:28 AM] Oana Goga: i tried a classifier without the friends feature
%[11/14/14, 12:00:32 AM] Oana Goga: and the performance is very small
%[11/14/14, 12:00:54 AM] Oana Goga: we can only achieve a 2-3% recall for a 80% precision
%[11/14/14, 12:15:33 AM] Krishna Phani Gummadi: it may not be that meaningful to say whether we can match an profile without considering false matches
%[11/14/14, 12:15:53 AM] Krishna Phani Gummadi: We were able to match 90% of profiles in small-scale
%[11/14/14, 12:15:59 AM] Krishna Phani Gummadi: These are the same profiles
%[11/14/14, 12:16:15 AM] Krishna Phani Gummadi: that we failed to match at large-scale
%[11/14/14, 12:16:51 AM] Krishna Phani Gummadi: Why? Because if we tried to match them, we would have to largely rely on features other than "friends" and this would introduce lots of false matches.
%[11/14/14, 12:17:11 AM] Krishna Phani Gummadi: Put differently, I am NOT disagreeing with what you are saying
%[11/14/14, 12:17:24 AM] Krishna Phani Gummadi: But, we should not say -- we need friends to match
%[11/14/14, 12:17:30 AM] Krishna Phani Gummadi: We need friends to discriminate
%The equivalent would be picking the best matching profile about the threshold with Linker-SVM+
%[11/14/14, 12:24:48 AM] Krishna Phani Gummadi: So that I get this -- currently Linker-SVM+ has 10^-4 or so precision at 50%
%[11/14/14, 12:25:06 AM] Krishna Phani Gummadi: But, if we only took the "TOP MATCH", the precision jumps to 50%
%[11/14/14, 12:45:43 AM] Oana Goga: worker1: 55 true matches, 34 cannot say, 11 missmatches
%[11/14/14, 12:46:02 AM] Oana Goga: worker2: 47 true matches, 33 cannot say, 20 missmatches
%[11/14/14, 12:46:17 AM] Oana Goga: worker3: 53 true matches, 36 cannot say, 11 missmatches
%}
%\fi
%
%\if 0
%\begin{table}[htdp]
%\small{
%\caption{Fraction of available and consistent pairs of matching profiles that are matched and not matched by the LINKER-SVM+ in the large scale dataset 90\% recall.}
%\begin{center}
%\begin{tabular}{c|c|c|c|c|c|c}
%Feature & \multicolumn{3}{c}{Availability} & \multicolumn{3}{c}{Consistency} \\
%& True  & Missed  & False  &  True  & Missed  & False  \\
%& Matches  & Matches  & Matches  &  Matches  & Matches  & Matches  \\
%\hline
%\hline
%%Real Name & 1.00 &  1.00 &  1.00 &  0.68 & 0.88 & 0.63 \\
%%Screen Name & 1.00 &  1.00 &  1.00 &  0.41 & 0.60 & 0.36 \\
%%Location & 0.30 &  0.43 &  0.26 &  0.23 & 0.34 & 0.20 \\
%%Photo & 0.62 &  0.77 &  0.58 &  0.08 & 0.15 & 0.07 \\
%%Friends & 0.43 &  0.99 &  0.30 &  0.32 & 0.93 & 0.17 \\
%Real Name & 1.00 &  1.00 &  1.00 &  0.83 & 0.45 & 0.70 \\
%Screen Name & 1.00 &  1.00 &  1.00 &  0.45 & 0.00 & 0.07 \\
%Location & 0.33 &  0.10 &  0.07 &  0.27 & 0.01 & 0.00 \\
%Photo & 0.66 &  0.43 &  0.47 &  0.10 & 0.01 & 0.01 \\
%Friends & 0.50 &  0.11 &  0.02 &  0.36 & 0.08 & 0.00 \\
%\end{tabular}
%\end{center}
%\label{default}
%}
%\end{table}%
%\fi
%

%\comment{add results for dataset 2}
%Over the test data the \linkernb and \linkersvm are able to achieve a recall over 90\% for a precision of 95\% while \textsc{Linker-LR} achieves a 85\% recall and \textsc{Linker-DT} a \comment{XX} recall for the same precision. 
%\comment{add maybe the reliability of logistic regression and decision trees? why they perform worst? missing values ? without missing values do they perform better?}

%LR 85 recall, svm 89 recall , nb 95 recall.
%As also shown by previous work, both classifiers have a very good reliability and can achieve a recall over 80\% for a 95\% precision.  

%Figure~\ref{fig:prec_rec_smallscale} presents the tradeoff between precision and recall obtained for different probability thresholds. 


%As expected, the scheme links 89\% of the \matchingprofiles and 1\% of \nonmatchingprofiles.  
%- When applying the binary classifier in Section 3 over a large database, that is, compute the similarities between a profile in SN_1 with all the profiles in SN_2, we find that the performance of the classifier , mostly in terms of prediction and false positive rate, fall away. This is due to the fact that. when considering small databases, the probability of finding several similar profiles to the target one tends to zero, but when dealing with the all the profiles in the network we can distinguish two groups of profiles: i) a very big set of profiles that are clearly different from the target one, because they do not share any public information with the target profile (i.e., the similarities are near zero); and ii) a set of profiles that present high similarity with the objective profile in some or all of the public features we take into profile. (If possible, you can show how the performance become worse when applying the linker to the full network).


%\noindent \textbf{Takeaway:} The one-step matching scheme can link 83\% of the \matchingprofiles with a 89\% precision on a small scale dataset.
%\new{Since we cannot estimate false positive rates lower than $10^{-4}$ (because we do not have datasets large enough) we pick a threshold (0.99) that corresponds to a zero false positive rate on the training dataset.  We test next the \sysname at scale using this threshold. Even if at scale the false positive rate will not be zero,  setting a very high threshold will limit the number of false matches.}
%
%\if 0
%\toremove{Due to the small size of the dataset, it is not possible to estimate the matching scheme performance at false positive rates lower than $10^{-4}$. To evaluate the scheme at scale, we use in next section the method described in~\xref{sec:evalscale}.}
%
%\update{We set the threshold probability for \sysname to
%declare a profile as \matching at 0.99. This threshold corresponds to a zero false positive rate, on the training set when using 10-fold cross validation. We have a zero false positive rate just because we only use a sample of 1,000 \nonmatchingprofiles. Setting such a high threshold will limit at maximum the number of false matches.}
%\fi 



%
%\if 0
%\toremove{For the evaluation, we set a threshold probability for the \sysname to
%declare a profile as \matching at 0.99. For the small dataset of the previous section, this threshold corresponds to a zero false-positive rate due to the small number of non-matching-profiles. 
%Here, it will give a small number of false matches (see below). }
%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.30\textwidth,height=3.5cm]{plots/CDF_candidate_set.eps}
%\vspace{-3mm}
%\caption{CDF of the number of Facebook \matchingprofiles identified by the \sysname for each Twitter profile.}
%\label{fig:size_candidateset}
%\end{center}
%\vspace{-2.5\baselineskip}
%\end{figure}
%
%\minisec{True matches} \sysname successfully identifies 66\%
%of all \matching Facebook profiles. While this true positive rate is
%lower than the expected rate observed in ~\xref{sec:linker}, 83\%, it is
%due to the limitations in generating the candidate set as a consequence of using the Facebook Search API. 
%
%\minisec{False matches} Figure~\ref{fig:size_candidateset} shows
%the cumulative distribution of the number of Facebook profiles in the
%candidate set that \sysname identifies as \matching to the
%Twitter profiles. For more than 62\% of Twitter profiles,
%\sysname identifies 100 or more Facebook profiles as \matching. Note
%that the number of matching profiles is likely to be higher with a
%more extensive candidate set. Since only one of these profiles is
%\matching, our finding indicates that more than 99 out of 100 profiles
%identified as \matching by \sysname are false, i.e. a $\approx$ 1\% precision. The high number of
%false matches highlights the reliability problem with applying
%\sysname to match profiles at scale.
%
%
%\subsection{Evaluation against human workers}
%\label{sec:amt_sim}
%
%\noindent  To get a better understanding of the reliability of our \sysname we compare it with the reliability of human workers. 
%We use the \sysname to match the profiles used for the AMT experiment.  
%The \sysname is able to link 89\% of the \matchingprofiles without any misclassification (~\xref{sec:linker_small}) while AMT workers are able to link 58\% of the \matchingprofiles with majority agreement, suggesting that the \sysname is doing a better job than AMT workers (\xref{sec:eval_amt}). 
%
%Table~\ref{tab:detectable_amt_linker} details the proportions of \matchingprofiles that AMT workers and the \sysname detect or not: 55\% of the \matchingprofiles are detected by both;  3\% of the profiles are detected by AMT workers but not by the \sysname.  AMT workers are able to identify them because the same person appears in the photos but \sysname misses them because it does not do face recognition. 
%The 8\% of the profiles that are not detected by either AMT workers or the \sysname are profiles where the real name does not match and other attributes are not available. Note that this fraction is consistent with the 7\% fraction of profiles with  inconsistent values for all attributes we found in~\xref{sec:features}.  
%
%Finally, 34\% of the profiles are detected by the \sysname but not by AMT workers.  Most of the profiles undetected by AMT workers and detected by the \sysname have no location information nor photos however they have very similar real names or screen names.
%The \sysname  puts more weight on the similarity between real names and screen names (and less on the other attributes) when it makes a decision, and consequently it often decides that two profiles are matching only because they have similar real names. However, AMT workers are more cautious when deciding if two profiles are \matching and they check for other attributes to match besides the real name or screen name. 
%The \sysname gives such a high weight to the similarity between real names because the real name is the most discriminative, available and consistent attribute and when looking at all profiles in a social network is the attribute that alone best distinguishes \matchingprofiles.
%
%
%\begin{table}[t]
%\footnotesize{
%\caption{Proportion of detected and undetected \matchingprofiles by AMT workers and by the \sysname.}
%\begin{center}
%\vspace{-3mm}
%\begin{tabular}{cc||cc}
%\multicolumn{2}{c||}{} & \multicolumn{2}{c}{\textbf{\sysname}} \\
%\multicolumn{2}{c||}{}  & Detected & Undetected \\
%\hline
%\hline
% \multirow{2}{*}{\textbf{AMT}} & Detected & 55\% & 3\% \\
% & Undetected & 34\% & 8\% \\
%%AMT not detected \& LINKER detected & 34\% \\
%%AMT not  detected \& LINKER not detected & 8\% \\
%\end{tabular}
%\end{center}
%\vspace{-2.5\baselineskip}
%\label{tab:detectable_amt_linker}
%}
%\end{table}%
%
%\minisec{\matchingprofile detectability by AMT workers} We detail
%next what makes the AMT workers confident that two profiles are
%\matching or not.  Table~\ref{tab:avail_amt} shows the availability
%of attributes for the detectable and undetectable \matchingprofiles
%in \datasetAMT. As expected, the availability of attributes is much
%lower for undetectable than detectable \matchingprofiles.
%
%Figure~\ref{fig:cdf_overall_sim_amt} compares the CDFs of similarity
%scores for detectable and undetectable \matchingprofiles.  All the
%undetectable \matchingprofiles do not have matching locations,
%photos or friends as the CDF of undetectable \matchingprofiles is
%very close to the CDF of \nonmatchingprofiles.  Undetectable
%\matchingprofiles also have less similar real names and screen
%names.
%
%\begin{table}[htdp]
%\footnotesize{
%%\vspace{-8mm}
%\begin{center}
%\caption{Availability of attributes for the detectable and undetectable \matchingprofiles in \datasetAMT.}
%\vspace{-3mm}
%\setlength{\tabcolsep}{2pt}
%\begin{tabular}{l|c|c|c}
%  & \textbf{Profile Photo} & \textbf{Location} & \textbf{Bio} \\
%\hline
%\hline
%Detectable corr.  & 95\% & 53\% & 42\% \\
%Undetectable corr.  & 67\% & 15\% & 26\% \\
%\end{tabular}
%\label{tab:avail_amt}
%\end{center}
%}
%\vspace{-2.5\baselineskip}
%\end{table}%
%
%
%To further understand the importance of each attribute in the
%classifier, we compute the Pearson correlation coefficient between all
%the attributes and the output classes (e.g. \matching and
%\nonmatching).  The Pearson correlation coefficient takes all the
%values of an attribute and computes the linear correlation between the
%values and the classes. In our setting values might be missing (i.e,
%when the attributes are not available for a pair of profiles), thus we
%compute for each attribute two Pearson correlation coefficient, one in
%which we ignore the missing values and one where we replace missing
%values with -1. While the first coefficient shows the
%possible/\change{theoretical?} importance of attributes in the
%classifier, the second coefficient shows the real importance of
%attributes in the classifier by considering their availability.
%Table~\ref{fig:pearson} shows the Pearson correlation coefficients for
%each attribute: first row when ignoring the missing values and the
%second row when replacing missing values with -1.  Real name, screen
%names, location and friends have the a very high correlation with the
%classes 0.78, 0.65, 0.68 and 0.63 respectively. Photos have a lower
%correlation, 0.16 for the Phash algorithm and 0.24 for the SIFT
%algorithm. In the second row the coefficient is the same for screen
%names and real names as their availability is high however it is much
%lower for the rest of the attributes. Location and friends drop to
%0.10 and 0.11 respectively, while photos drop to 0.03 and 0.04. This
%explains the low improvement in the true positive rate when adding
%more features.
%
%\begin{table}[htdp]
%
%\caption{Pearson correlation coefficient between attribute values and the classifier classes (i.e, \matching and \nonmatching). First row corresponds to Pearson coefficient when we ignore the missing values and the second row when we replace missing values with -1. }
%\begin{center}
%\scriptsize{
%\begin{tabular}{c|c|c|c|c|c|c}
% & Real N.& Screen N. & Loc. & P. Phash & P. SIFT & Friends \\
%\hline
% Without & 0.78 & 0.65 & 0.68 & 0.16 & 0.24 & 0.63 \\
% With & 0.78 & 0.65 & 0.10 & 0.03 & 0.04 & 0.11 \\
%\end{tabular}
%}
%\end{center}
%\label{fig:pearson}
%\end{table}%
%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\subfloat[Screen name]{\label{fig:cdf_u}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_detectable_U.eps}}
%\subfloat[Real name]{\label{fig:hist_n}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_detectable_N.eps}}
%
%\subfloat[Photo - Phash]{\label{fig:cdf_p}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_detectable_P.eps}}
%\subfloat[Photo - SIFT]{\label{fig:cdf_p}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_detectable_S.eps}}
%
%\subfloat[Location]{\label{fig:cdf_l}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_detectable_L.eps}}
%\subfloat[Friends]{\label{fig:cdf_l}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_detectable_G.eps}}
%%\subfloat[Friends (\todo{update})]{\label{fig:hist_p}\includegraphics[width=0.20\textwidth]{plots/cdf_M_NM_graph_exact.eps}}
%
%%\subfloat[All]{\label{fig:hist_p}\includegraphics[width=0.20\textwidth]{plots/cdf_candidateset_M_NM_detectablenaivebayes.eps}}
%%\vspace{-2mm}
%\caption{CDFs of similarity scores for detectable and undetectable \matchingprofiles by AMT workers.}
%\label{fig:cdf_detectable}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.20\textwidth]{plots/cdf_overall_similarity_amt_random.eps}
%%\vspace{-2mm}
%\caption{CDFs of the probability to be \matching for detectable and undetectable \matchingprofiles by AMT workers.}
%\label{fig:cdf_overall_sim_amt}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}
%
%
%\new{\noindent \textbf{Takeaway I:} The \sysname is apparently doing a better job than AMT workers because it often decides that two profiles are matching only because they have similar real names while AMT workers need other attributes beside real names to match. }
%
%\update{\noindent \textbf{Takeaway II:} AMT workers are not able to link a higher percentage of \matchingprofile because, other than real names, the profiles have a low availability of attributes and/or low consistency. }
%
%has such high true and false positive rates  because it often decides that two profiles are matching only because they have similar real names.  AMT workers have a better precision because they check for other attributes beside real names to match to declare that two profiles belong to the same person.
%\fi 
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Matching profiles in practice}
%\label{sec:boosted_cl}




%\noindent In this section we investigate whether we can improve the reliability of the \linkernb and \linkersvm at scale. 

\subsection{Evaluation over \largescale}
\label{sec:nary_linker}

%
%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.35\textwidth]{plots/prec_rec_all_random.eps}
%%\vspace{-2mm}
%\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles using different classifiers over the large scale dataset.}
%\label{fig:prec_rec_random}
%\end{center}
%%\vspace{-2\baselineskip}
%\end{figure}





\noindent Figure~\ref{fig:prec_rec_scale} presents the tradeoff between precision and recall when we evaluate using \largescale the four \sysname classifiers trained on \smallscale.   The figure shows that when matching profiles in practice the reliability of all four classifiers drops significantly compared to \smallscale (presented in Figure~\ref{fig:prec_rec_random}). 
The best classifier on the \smallscale, \linkernb,  achieve only a 4.5\% precision for a 23\% recall when tested on \largescale. The only classifier that achieves a satisfying 95\% precision is \linkersvm, however, the recall is only  15\%.  

These results confirm our intuition that the reliability of a matching scheme over \smallscale fails to capture the reliability of the matching scheme in practice. Worse, the matching scheme that has the best reliability when testing with \smallscale (i.e., the \linkernb) can be amongst the worst in practice.
%This shows that schemes previously proposed that use similar approaches have a much lower reliability when evaluated over real-world social networks than stated. 




%\toremove{The problem with this approach is that  \emph{names} have much better availability, consistency, and discriminability than any other feature. Thus, the binary classifier gives a lot of weight to the similarity between the names of two profiles and considerable lower weight to the similarity between other features when computing the probability of two profiles to match.  Consequently, the \sysname often decides that two profiles match if they have similar names but no other feature is matching. Because at large scale there can be multiple profiles with the same name that do not belong to the same user, the \sysname returns many false positives. }

%\toremove{We next inspire from the entity matching literature and propose a matching scheme in two steps: first filter out obvious non-matching profiles and then use a classifier, the \disambiguator, to distinguish the matching profile out of similar looking non-matching profiles.  The \disambiguator is solving a harder problem than the \sysname, because it is trying to distinguish among profiles that are highly similar. This approach achieves a higher precision than the \sysname over entire social networks (a 23\% precision for a  30\% recall) however the precision is still unsatisfying. }





 \vspace{2mm}
 \noindent \textbf{Optimizing the binary classifiers}

\noindent\minisec{\linkernb{}}
\noindent We investigate the reasons for the low precision of \linkernb in \largescale. The results in Figure~\ref{fig:cdf_new_m_nm}
show that matching \profiles often have consistent names whereas non-matching \profiles (from sample) most often do not; there is no such clear distinction for the other attributes.  Since Naive Bayes assumes that features are independent, the probability that two profiles match will be mainly determined by their name similarity. In a large social network, however, multiple users can have the same name, which will cause \linkernb to output many false matches.




%Thus, since Naive Bayes  is a generative classifier it learns that the likelihood of two non-matching profiles to have similar names is very small. \update{Even if this is actually true, it makes the classifier have too many false positives. A better approach in this case is to use a discriminative classifier that instead of modeling the probability of the attribute similarity given the class, it models the probability of the class given the attribute similarity. Such classifier can better perceive that there are, in fact, still many non-matching profiles with similar names~\cite{NIPS2001_2020}. } \comment{ask patrick to check paragraph}

One way to make the classification more accurate is to use two classifiers in cascade instead of one. The first classifier weeds out profiles that are clear non-matches (most of which have different names). Then, the second classifier takes the output of the first and disambiguates the matching profiles out of profiles with similar names. We call this improved classifier \textsc{Linker-NB+}. For more details about this approach please refer to~\cite{Goga}.  

Another approach to make the classification more accurate is to use methods based on joint probabilities such as quadratic discriminant analysis. We prefer to move to SVM which also considers features jointly and is not restricted to quadratic boundaries. 

%
%\if 0
%
%To improve the reliability of the \linkernb, we inspire from the entity matching community and instead of trying to match profiles in one step, we adopt a two-step procedure. We call the two steps the \filter and the \disambiguator. 
%Given a candidate set of profiles, the \filter weeds out profiles that are clear non-matches.  Then, the \disambiguator takes the output of the \filter and further disambiguates the \matchingprofile.   
%
%
% %that do not model the distribution of similarities in the positive and negative class but model the difference between classes.}
%
%% computes the probability of two profiles to match by modeling  the attribute similarity distribution in the positive and the negative class, whenever the \linkernb sees a paris of profiles with similar names, it always computes a high likelihood to be matching profiles. 
%
%%gives a very high weight to the similarity between names and much lower weights to the similarity between other profile attributes. 
%
%%T
%%Furthermore, since real names have much more availability, consistency and discriminability  than the rest of the features they split the best matching from non-matching profiles. 
%
%%\begin{figure}[htbp]
%%\begin{center}
%%\includegraphics[width=0.90\columnwidth]{2step.png}
%%%\vspace{-3.5mm}
%%\caption{Two-step approach.}
%%\label{fig:3steps}
%%\end{center}
%%%\vspace{-1.5\baselineskip}
%%\end{figure}
%
%%To achieve a better precision the \linkernb needs to give a lower weight to  names and higher weights to other features.  However, modifying the  \linkernb  to give more weight to other features will potentially result in disastrous reliability because it could match, for example, people that live in the same place but have nothing else in common. 
%
%To improve the reliability of the \linkernb, we inspire from the entity matching community and instead of trying to match profiles in one step, we adopt a two-step procedure. We call the two steps the \filter and the \disambiguator. 
%Given a candidate set of profiles, the \filter weeds out profiles that are clear non-matches.  Then, the \disambiguator takes the output of the \filter and further disambiguates the \matchingprofile.   
%%The \filter takes as input a target \profile  $a \in SN_1$ and \emph{all} the \profiles in $SN_2$ and returns a small candidate set $C(a)$ of \profiles in $SN_2$ that are similar to $a$.\footnote{Note that in~\xref{sec:evaluation} we were interested to build $C(a)$ such that we can exploit existing APIs and evaluate our matching schemes at scale. Here we are interested in more fundamental ways we can  build $C(a)$ and build matching schemes that can otherwise be applied if we have access to entire social networks data.} The \disambiguator takes the output of the \filter and further disambiguates the \matchingprofile out of the candidate set.   
%The intuition is that, the \filter will weed out most of the non-matching profiles with different names, thus the \disambiguator will give a smaller weight to names than the \linkernb. We present next in more detail the two components of the matching scheme. 
%
%
%
%\noindent \minisec{\textbf{The \filter}}
%
%\noindent The \filter weeds out obvious \nonmatchingprofiles and returns a small candidate set of possible \matchingprofile, $C(a)$.  The objective of the filter is to minimize the size of $C(a)$ while keeping a high probability that the \matchingprofile $\hat{a} \in C(a)$. Several techniques are possible to build the \filter: 
%
%%\noindent \textbf{Input:} A target profile $a \in SN_1$ and all the \profiles in $SN_2$. 
%%\noindent \textbf{Output:} A candidate set $C(a)$ of \profiles in $SN_2$ similar with $a$. 
%%\noindent \textbf{Conception:} 
%
%%\begin{enumerate}[noitemsep,topsep=0pt]
%\begin{trivlist}
% \topsep 0pt
% \itemsep 1pt
%\item \emph{Indexing:} We can opportunistically use the Facebook search API to find \profiles with the same or similar names to the target profile. Indexing techniques are often used for such tasks~\cite{books/daglib/0030287}. 
%These techniques are computationally light and scalable however they are limited to using names to find similar profiles. 
%    
%\item \emph{Supervised approach:} We can use the \linkernb to build the candidate set. 
%%Note that for this purpose, we can use either all or only a subset of attributes. \change{is this important to say here? --Oana}
%The drawback of such approach is that it needs to compute the similarity between the target profile and \emph{all} the profiles on $SN_2$, which is inefficient.
%However, this approach is able to use multiple attributes to find similar profiles.
%%\change{The previous section showed that names and screen names have the highest weights in the similarity computation. } 
%\item \emph{Unsupervised approach:} We could map all the \profiles in an unsupervised way so that we can cluster similar \profiles without the need of computing the similarities among all the \profiles. Such an approach is not straightforward and we leave it as future work.
%\end{trivlist}
%%\end{enumerate}
%
%%\noindent \textbf{Realization:}
%We opt for a combination between the first and the second approach because this is what we can practically do. 
%We use the \largescale and we apply the \linkernb to weed out non-matching profiles.
%%\move{Since we do not have access to all the profiles on Facebook we use the Facebook search API to generate a candidate set, $C_{Fb}(a)$ (as described in~\xref{sec:linker}), and then we apply the \linkernb (with a threshold corresponding to 1\% false positive rate) on $C_{Fb}(a)$ to weed out profiles that are not similar enough to build $C(a)$. Recall from~\xref{sec:evaluation} that for 30\% of Twitter profiles $\hat{a} \notin C_{Fb}(a)$. The \filter achieves a 69\% recall with a precision lower than 1\%.  }
%
%
%\noindent \minisec{\textbf{The \disambiguator}}
%
%\noindent The goal of the \disambiguator is to find the \matchingprofile in the candidate set of \profiles returned by the \filter. Similar to building the \linkernb, we train another probabilistic classifier to do this job. 
%We use the same positive examples, however, the key distinction is that instead of training the classifier with negative examples from the \smallscale we train it with negative examples from \largescale that passed the \filter. 
%
%%\noindent \textbf{Input:} A target \profile $a \in SN_1$ and $C(a)$. 
%%\noindent \textbf{Output:} The profile in $C(a)$ most similar to $a$. We call this profile the \psysname.
%%\noindent \textbf{Objective:} Maximize the probability  $\hat{a} $ is the most similar \profile in $C(a)$ to $a$. 
%%\noindent \textbf{Conception:} 
%
%%\noindent \textbf{Realization:} 
%%\noinden The goal of the \disambiguator is to distinguish between the correlated and uncorrelated\profiles. 
%%To build a training dataset, we take 1,000 Twitter \profiles from \datasetFF (different from the ones used for testing the matching schemes) and for each Twitter \profile, $a$, we generate the candidate set, $C(a)$, using the \filter.  Since we know the Facebook \matchingprofiles for all the Twitter \profiles we can train the classifier with \matchingprofiles $(a,\hat{a})$ where $\hat{a} \in C(a)$ and \nonmatchingprofiles $(a,b)$ where $b \in C(a)$ and $b  \neq \hat{a}$ (the \textsc{Negative-Similar-Train}).
%
%%Similar to the \linkernb, given two profiles $(a,b)$ the \disambiguator outputs the probability, $p$, that they are \matchingprofiles. 
%Note that \disambiguator probability estimates would be different from
%\linkernb as the training sets and the discriminability of the public
%attributes within the training sets are very different. For example,
%real name and screen name attributes have high discriminating power in
%the training sets used for \linkernb (see Figure~\ref{fig:cdf_m_nm_n},~\ref{fig:cdf_m_nm_u}), while they have limited discriminating power in the training set used by the \disambiguator. Thus, contrary to the \linkernb, the \disambiguator gives higher weights to the similarity between other attributes beside the real names.
%%Note that, the key distinction between the \linkernb and the \disambiguator is the negative examples in the training set. 
%%We train the \sysname with random non-matching profiles which will be more different from $a$ than profiles in $C(a)$ which already have similar names. 
%
%
%% Similar with the evaluation of the \linkernb at scale in~\xref{sec:linker} the \filter is able to attain a recall of 69\% for a precision of 1\%. \update{Remember,  the candidate sets we generated contains the \matchingprofile only 70\% of the time thus the maximum recall we can achieve is 70\%. With a more extensive candidate set containing a larger fraction of \matchingprofiles, the recall would likely improve.}
%
%\subsubsection{Evaluation at scale}
%\noindent Figure~\ref{fig:prec_rec_scale} shows the tradeoff between precision and recall the \filter and the \disambiguator can achieve together at scale for different thresholds over the probability $p$ returned by the \disambiguator.  This reliability is much better than the reliability of the \linkernb alone and is able to achieve a 23\% recall for a 88\% precision. Such an reliability cannot be achieved in one step using Naive Bayes. 
%
%\fi 
%
%\if 0
%\toremove{Put differently, it declares that a profile $b$ is a match even if $b$ is not distinguishable/discriminable enough from the set of candidate profiles $C(a)$. 
%To build a reliable \sysname we would like the matching scheme to declare that $b$ is a match only if it is significantly more similar than other profiles in $C(a)$ with $a$.  Let's call the GUARD the step that outputs a match only if it pops out of the candidate set.   
%The problem with the \sysname is that since it gives to much weight to names, and consequently gives a very small weight to the other profiles, none of the profiles in the candidate set pop out, they all have close similarities according to the \sysname. Thus we need a classifier that gives a higher weight to other features to be able to observe profiles that pop out.}
%\fi 

%\subsection{Improving \linkersvm}

\noindent \minisec{\linkersvm{}}
\noindent \linkersvm has a much higher precision in \largescale than \linkernb. Intuitively, this is because, as 
opposed to Naive Bayes, SVM considers the features jointly and hence can distinguish between pairs of profiles 
with high name similarity that match and pairs of profiles with high name similarity that do not match based on 
other features.  
%As a result, SVM can return as positive only pairs of profiles that have similarity in both names and other features, hence reducing considerably the false positives. 
Nevertheless, previous work has shown that SVM performs suboptimally when using under-sampling to deal with imbalanced datasets~\cite{conf/ecml/AkbaniKJ04}.  By under-sampling the majority class, we are missing informative data points close to the decision boundary. 

To improve the reliability of \linkersvm, we take advantage of the fact that \largescale contains negative examples close to the decision boundary, to enrich our training set. We build a training set that contains \nb positive examples,  \nb negative examples from \smallscale plus \nb negative examples from \largescale. We call the resulting classifier the \hybridsvm. 
Note that if we only use for training negative examples from  \largescale and not from  \smallscale, the resulting classifier will only be able to distinguish the matching profiles out of profiles that look similar and will not be able to distinguish the matching profile out of profiles that are clearly not similar, i.e., it will only work on datasets such as \largescale and not in practice.
%
For \textsc{Linker-LR}  and \textsc{Linker-DT}  we apply the same retraining technique. 
%For this we select a sample of 1,000 non-matching profiles (the same we use to train the \disambiguator).  We train a new classifier, the \hybridsvm, with 1,000 positive examples from \textsc{Positive-Train}, as the \linkersvm, but with both 1,000 random non-matching profiles from \textsc{Negative-Train} and 1,000 similar non-matching profiles from \textsc{Negative-Similar-Train}. 

%\begin{figure}[t]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.35\textwidth]{plots/prec_rec_all_both.eps}
%%\vspace{-2mm}
%\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles using retrained classifiers over the large scale dataset.}
%\label{fig:prec_rec_random}
%\end{center}
%%\vspace{-2\baselineskip}
%\end{figure}

 \vspace{2mm}
 \noindent \minisec{Evaluation of optimized classifiers}
%\noindent \minisec{Evaluation at scale}
\noindent Figure~\ref{fig:prec_rec_scale_retrained} shows the tradeoff between precision and recall when using \hybridsvm, \textsc{Linker-NB+}, \textsc{Linker-LR+}, \textsc{Linker-DT+}   on \largescale.  % \rt{Figure 3c says Linker-NB and Linker-SVM. Shouldn't it say the improved versions? Also, make sure that the lines for a given classifier have the same color for all figures. Why does this figure still shows LR and DT? have you changed those? Maybe better to skip. Also, maybe better to have a separate figure with c and d. this figure is too small it is hard to read.} 
We can see that \hybridsvm is able to achieve a 19\% recall (4\% improvement over the \linkersvm) for a 95\% precision.\footnote{\small{In \datasetG, \hybridsvm has 50\% recall and 95\% precision.}} % and is able to achieve a recall similar with the \filter + \disambiguator but with a better precision. The \hybridsvm can do the matching in one step, however it needs an iterative process to train the classifier. 
%
Also, \textsc{Linker-NB+} achieves a 23\% recall for a 88\% precision, considerably better than \linkernb. Nevertheless, the recall is significantly lower compared with the recall obtained when testing with \smallscale. Thus,  even more sophisticated techniques trained to match profiles in real-word settings fail to match a large fraction of profiles.

 %\comment{should i keep this explanation or is only frustrating?} 



 \vspace{2mm}
 \noindent \minisec{Analysis of matched pairs}
\noindent To understand the low recall we obtain in \largescale, we analyze again the availability and consistency of attributes. The precision of \hybridsvm has a sudden drop, to go from a recall of 19\% to 33\%, the precision goes from 95\% to 0.02\%. 
To analyze the drop, we split the pairs of profiles in \largescale in true, missed, and false matches using first a threshold corresponding to a 95\% precision (and a 19\% recall) and then with a threshold corresponding to a 0.02\% precision (and a 33\% recall), see Table~\ref{tab:av_cons_large_scale_95}.  

Contrarily to our expectation, for most attributes but friends, the availability and consistency of  true matches at 0.02\% precision is actually slightly higher than the one at 95\% precision. Only the availability and consistency  of friends  decreases from 91\% at 95\% precision to 68\% at 0.02\% precision. 
%For most attributes the availability and consistency of the  true matches at 0.02\% precision is slightly higher than the one at 95\% precision. The most striking difference, however,  is that at 95\% precision, 91\% of true matches have friends in common, whereas this percentage is only
%68\% at 0.02\% precision. 
This means that, to go from 19\% to 33\% recall we mainly started to match profiles that do not have friends in common. The consequence is that while at 95\% precision, the false matches needed to have friends in common, at 0.02\% precision, false matches no longer need to have  friends in common.  This makes the matching scheme have orders of magnitude more false matches at 33\% recall than at 19\% recall.
Thus, even if the features are highly available and consistent, if they are not discriminable enough, they will allow for many false matches which limits the precision and recall we can achieve in practice.

% \rt{I cannot parse the next sentence.} This means that, at large scale, to maintain a high precision, matching profiles need to have common friends in order to be detected.  Friends is the most discriminative feature we consider. Furthermore, most of the false matches have similar available and consistent attributes as the true matches (i.e. consistent names, locations, photos). This means that, at large scale, there is a large number of pairs of profiles that  have consistent and available attributes but are not true matches. 
% 
%This result means that to increase recall the classifiers will output many false matches. 
%\rt{Could maybe summarize this next paragraph without going too much in detail. This point is somewhat similar to what you are saying in the previous paragraph.}



%To analyze why there is a sudden  drop in precision we also analyze  in Table~\ref{tab:av_cons_large_scale_95} the fraction of  true, missed and false matches that have attributes available and consistent using \hybridsvm with a threshold corresponding to a 33\% recall (and a 0.001\% precision).  Table~\ref{tab:av_cons_large_scale_95}  shows that to allow for a higher recall the \hybridsvm started to match profiles that do not have friends in common but have other consistent features.  And the one primary difference between false matches at 95\% precision and 0.001\% precision is in terms of their friends consistency,  at 95\% precision we require the friends to be consistent, while for 0.001\% it can be zero.  
% Clearly, this determined  to  have orders of magnitude more false matches in at 0.001\% precision than 95\%  (given the steep drop in precision).

The results suggest that when matching profiles in practice, to maintain a high precision, we need features that are highly discriminable. Indeed, if we exclude friends (one of the most discriminable attributes) from the features we use for the classification, we can only achieve a 11\% recall for a 90\% precision. 


%
%\rt{this takeaway seems a bit obvious and it is just repeating what you said in the previous paragraph. maybe need to rephrase it.}
%\noindent \minisec{Takeaways} At large scale, to maintain high precision, we need features that are able to discriminate well the matching profiles. It is not enough for features to be available and consistent. 
% 
% \if 0 
%\begin{table}[htdp]
%\scriptsize{
%\caption{Fraction of true, missed and false matches  that have available and consistent attributes. We split the pairs of profiles in \largescale in true, missed and false matches using the \hybridsvm with a similarity threshold corresponding to a 95\% precision (and a 19\% recall).}
%\begin{center}
%\begin{tabular}{c|c|c|c|c|c|c}
% & \multicolumn{3}{c|}{Availability} & \multicolumn{3}{c}{Consistency} \\
%Feature & True  & Missed  & False  &  True  & Missed  & False  \\
%& Matches  & Matches  & Matches  &  Matches  & Matches  & Matches  \\
%\hline
%\hline
%%Real Name & 1.00 &  1.00 &  1.00 &  0.68 & 0.88 & 0.63 \\
%%Screen Name & 1.00 &  1.00 &  1.00 &  0.41 & 0.60 & 0.36 \\
%%Location & 0.30 &  0.43 &  0.26 &  0.23 & 0.34 & 0.20 \\
%%Photo & 0.62 &  0.77 &  0.58 &  0.08 & 0.15 & 0.07 \\
%%Friends & 0.43 &  0.99 &  0.30 &  0.32 & 0.93 & 0.17 \\
%Real Name & 1.00 &  1.00 &  1.00 &  0.94 & 0.73 & 0.86 \\
%Screen Name & 1.00 &  1.00 &  1.00 &  0.60 & 0.33 & 0.57 \\
%Location & 0.40 &  0.27 &  0.14 &  0.32 & 0.21 & 0.14 \\
%Photo & 0.77 &  0.58 &  0.86 &  0.14 & 0.07 & 0.57 \\
%Friends & 0.98 &  0.30 &  0.86 &  0.91 & 0.17 & 0.57 \\
%\end{tabular}
%\end{center}
%\label{tab:av_cons_large_scale_95}
%}
%\end{table}%
%\fi 




%\begin{table}[htdp]
%\scriptsize{
%\caption{Fraction of true, missed and false matches  that have available and consistent attributes. We split the pairs of profiles in \largescale in true, missed and false matches using the \hybridsvm with a similarity threshold corresponding to a 33\% recall (and a 0.001\% precision).}
%\begin{center}
%\begin{tabular}{c|c|c|c|c|c|c}
%Feature & \multicolumn{3}{c}{Availability} & \multicolumn{3}{c}{Consistency} \\
%& True  & Missed  & False  &  True  & Missed  & False  \\
%& Matches  & Matches  & Matches  &  Matches  & Matches  & Matches  \\
%\hline
%\hline
%Real Name & 1.00 &  1.00 &  1.00 &  0.94 & 0.69 & 1.00 \\
%Screen Name & 1.00 &  1.00 &  1.00 &  0.64 & 0.26 & 0.89 \\
%Location & 0.48 &  0.21 &  0.02 &  0.41 & 0.15 & 0.01 \\
%Photo & 0.75 &  0.56 &  0.59 &  0.16 & 0.04 & 0.07 \\
%Friends & 0.79 &  0.26 &  0.05 &  0.68 & 0.14 & 0.00 \\
%\end{tabular}
%\end{center}
%\label{tab:av_cons_large_scale_33}
%}
%\end{table}%

\begin{table}[t]
%\vspace{-3mm}
\scriptsize{
\caption{\small{Fraction of true, missed and false matches  that have available and consistent attributes in \largescale.}} 
%We split the pairs of profiles in \largescale in true, missed and false matches using the \hybridsvm with a similarity threshold corresponding to a 95\% precision (and a 19\% recall) and  similarity threshold corresponding to a 33\% recall (and a 0.001\% precision).}
\vspace{-3mm}

{\centering
\begin{tabular}{l|c|c|c|c|c|c}
\setlength{\tabcolsep}{1pt}
 & \multicolumn{6}{c}{Fraction of available and consistent attributes} \\

  & \multicolumn{3}{c|}{95\% precision and 19\% recall }  & \multicolumn{3}{c}{0.02\% precision and 33\% recall } \\
Feature  & True  & Missed  & False & True  & Missed  & False   \\
 &  Matches  & Matches  & Matches  &  Matches  & Matches  & Matches  \\
\hline
\hline
%Real Name & 1.00 &  1.00 &  1.00 &  0.68 & 0.88 & 0.63 \\
%Screen Name & 1.00 &  1.00 &  1.00 &  0.41 & 0.60 & 0.36 \\
%Location & 0.30 &  0.43 &  0.26 &  0.23 & 0.34 & 0.20 \\
%Photo & 0.62 &  0.77 &  0.58 &  0.08 & 0.15 & 0.07 \\
%Friends & 0.43 &  0.99 &  0.30 &  0.32 & 0.93 & 0.17 \\
Real Name &  0.94 & 0.73 & 0.86 &  0.94 & 0.69 & 1.00 \\
Screen Name &   0.60 & 0.33 & 0.57 &  0.64 & 0.26 & 0.89 \\
Location & 0.32 & 0.21 & 0.14 &  0.41 & 0.15 & 0.01 \\
Profile Photo &    0.14 & 0.07 & 0.57 &  0.16 & 0.04 & 0.07 \\
Friends &  0.91 & 0.17 & 0.57 &  0.68 & 0.14 & 0.00 \\
\end{tabular}

}
\label{tab:av_cons_large_scale_95}
}
\vspace{-2\baselineskip}
\end{table}%
%
%\if 0
%\begin{table}[htdp]
%\scriptsize{
%\caption{Fraction of true, missed and false matches  that have available and consistent attributes. We split the pairs of profiles in \largescale in true, missed and false matches using the \hybridsvm with a similarity threshold corresponding to a 33\% recall (and a 0.001\% precision).}
%\begin{center}
%\begin{tabular}{c|c|c|c}
%& \multicolumn{3}{c}{Fraction of available and consistent attributes} \\
%Feature   &  True  & Missed  & False  \\
% &  Matches  & Matches  & Matches  \\
%\hline
%\hline
%Real Name &  0.94 & 0.69 & 1.00 \\
%Screen Name  &  0.64 & 0.26 & 0.89 \\
%Location  &  0.41 & 0.15 & 0.01 \\
%Photo &  0.16 & 0.04 & 0.07 \\
%Friends  &  0.68 & 0.14 & 0.00 \\
%\end{tabular}
%\end{center}
%\label{tab:av_cons_large_scale_33}
%}
%\end{table}%
%\fi 

\section{Special matching problem}
\label{sec:3step}


\noindent The previous section showed that even fine tuned classifiers are vulnerable to output many false matches in practice. Worse, previous matching schemes are not able to protect against impersonation attacks. In this section, we propose ways to mitigate both of these problems in the special case where we know that there exists \emph{at most one matching profile} in $SN_2$.

%\noindent The previous section showed  the limits of matching \profiles across social networks even if we use fine tuned  classifiers. This section studies whether we can improve matching recall in the special case where we know that there exists \emph{at most one matching profile} in $SN_2$. 

%Furthermore, contrary to the matching schemes previously proposed, our method is also reliable to impersonation attacks.


\if 0
\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
\includegraphics[width=0.20\textwidth]{plots/cdf_nb_false_matches.eps}
%\vspace{-2mm}
\caption{Number of false matches per profile 90\% recall.}
\label{fig:cdf_nb}
\end{center}
%\vspace{-2\baselineskip}
\end{figure}
\fi 



\if 0

However, the previous matching schemes did not exploit two interesting particularities of the scenario:  ($1$) in some social networks there can only be \emph{one matching profile}; and ($2$) some attribute values are more \emph{unique} that others. %Furthermore, the matching schemes proposed in~\xref{sec:linker} are \emph{not reliable to impersonation attacks}. 
In this section, we take advantage of this observations and we design a novel method that is able to achieve a better recall.
Furthermore, contrary to the matching schemes previously proposed, our method is also reliable to impersonation attacks. 

\noindent The previous section showed some important limits of matching \profiles across social networks.
However, the previous matching schemes did not exploit one interesting particularity of the scenario: in some social networks there can only be \emph{one matching profile}. In this section, we take advantage of this observations and we design a novel method that is able to achieve a better recall.
\fi 

% The matching schemes based on the \hybridsvm  work by selecting a cut-off threshold for the probability $p$ of two profiles to match.
%, and the matching scheme returns 1 (i.e.,
%\matchingprofiles) if $p$ is larger than the threshold; and 0
%otherwise. 
%The threshold's choice is the standard tradeoff between precision and recall. 
\vspace{2mm}
\noindent \minisec{The \psysname}
%\noindent The straw man approach is, for each profile $a^{1}$, to simply return the \profile in $C(a^{1})$ with the highest $p$, i.e., the highest probability to be the matching profile given by \hybridsvm. 
%%\update{Note that, the assumption that there is always a matching profile it is not realistic and this approach is susceptible to have a low precision if the assumption does not help as it always returns a match. }
%This approach increases the recall because even if the matching profile $\hat{a}^{2}$ does not cross the probability threshold, it might still be the most similar profile.  Moreover, it increase the precision, because, the matching scheme outputs at most one false match. We call the most similar profile the \psysname. 
%Figure~\ref{fig:prec_rec_scale_topmatch} shows the tradeoff between precision and recall obtained for different probability thresholds on the $p$ of the \psysname.  \psysname in \largescale achieves to a 26\% recall for a 95\% precision. 
%%Figure~\ref{fig:cdf_nb} plots the CDF of the number of false matches detected by the \linkersvm with a threshold corresponding to the 0.001\% precision. 
%
%
\noindent The straw man approach is, for each profile $a^{1}$, to simply return the \profile in $C(a^{1})$ with the highest probability $p$ to be the matching profile given by \hybridsvm, provided that $p$ is larger than a threshold. We call the most similar profile the \psysname. This approach reduces the number of false matches since the matching scheme outputs at most one false match. Figure~\ref{fig:prec_rec_scale_topmatch} displays the tradeoff between precision and recall obtained for different probability thresholds on the $p$ of the \psysname. It shows that \psysname largely improves recall for a given precision: \psysname in \largescale achieves to a 26\% recall for a 95\% precision. 
%\update{Note that, the assumption that there is always a matching profile it is not realistic and this approach is susceptible to have a low precision if the assumption does not help as it always returns a match. }




%\move{Figure~\ref{fig:prec_rec_scale_topmatch} shows the tradeoff between precision and recall using the probability to be the matching profile of the \psysname. For a 95\% precision we can achieve a 25\% recall.}


% \noindent \minisec{Takeaways}  We can increase the precision and recall at large scale if we take advantages of the particularities of the scenario.
 
 


% that uses the previously developed classifiers and adds an extra step 
%In this section, we propose a simple but efficient matching scheme  that uses the previously developed binary classifiers, the \hybridsvm or the \filter + \disambiguator, and adds an extra step that is able to nicely take advantage of the particularities of the matching setting and makes the matching more accurate. 


\if 0
\toremove{Our analysis reveals reliability
issues with the one-step matching scheme when is applied at scale. This section designs a three-step matching scheme to address this issue. We combine three classifiers that together
find \matchingprofiles with very high accuracy and abstains when its confidence in the output is low.}
\fi



%\comment{say something that it also handles the fact that some attribute values are more unique than the others and impressionability.}
%\noindent The matching schemes based on the \hybridsvm  work by selecting a cut-off threshold for the probability $p$ of two profiles to match, and the matching scheme returns 1 (i.e.,
%\matchingprofiles) if $p$ is larger than the threshold; and 0
%otherwise. The threshold's choice is the standard tradeoff between precision and recall. 

%Alternatively, since we know that there can only be one matching \profile on the second social network, for each Twitter profile $a$,  we can return instead only the Facebook \profile with the highest probability of being a match. 
%The intuition is that while some Facebook \profiles might cross the probability threshold, the Facebook \matchingprofile would match the Twitter \profile better than other \profiles. This can increase the precision because it enforces the \hybridsvm to only output one matching profile, thus it limits the number of possible false matches. Also, even if the Facebook \matchingprofile does not cross the probability threshold, it might still be the most similar \profile. This can potentially increase the recall. We call the most similar account the \psysname. 

%\if 0
%To design a scalable and reliable matching scheme, we leverage four observations: 
%1) the \sysname is not able to accurately link \matchingprofiles at scale, however it is very good at weeding out \nonmatchingprofiles while retaining a small set of possible \matchingprofiles that contains with high probability the (real) \matchingprofile; 2) the \sysname often decides that two profiles are matching only because they have similar real names; 3) however, humans need multiple attributes to match between \profiles beside real names to be confident that they correspond to the same person; and 4) an impersonator can copy most of the public attributes of a \profile, and trick the matching scheme to link the impersonator \profile instead of the \matchingprofile.
%\fi

%Even if we can improve the recall, the disadvantage of such approach is that in practice, not all Twitter users have a Facebook profile, 

%it always returns a matching profile and in most realistic scenarios it is hard to know for sure that there is a matching profile in the second social network.
\vspace{2mm}
\noindent \minisec{The \confidence}
\noindent The strategy of outputting the \psysname considerably increases the recall compared to approaches in~\xref{sec:linker}. However,  it is still vulnerable to output false matches in practice when Twitter users who do not have a Facebook profile. 
%the disadvantage of this approach is that, in practice, not all Twitter users have a Facebook profile; which can lead in practice to many false matches and consequently a low precision.  
Worse, the \psysname is vulnerable to impersonation attacks that also hinder the reliability of the matching scheme. 
% If we assume that  there is at most one matching profile in $SN_2$ then we can mitigate some of the false matches. 
We propose next a simple solution that mitigates both of these problems by comparing the probability to be the matching profile of the most similar profile in $C(a^{1})$, $p_{1st}$, and the probability of the second most similar profile, $p_{2nd}$.  
The high level idea is that, to be sure that the most similar profile in $C(a^{1})$ is the matching profile, $p_{1st}$ should be much higher than the probability $p$ of any profile in $C(a^{1})$, i.e., $p_{1st} \gg p_{2nd}$. 

Intuitively, there are two possible scenarios where the \psysname is a false match:
%\begin{enumerate} 
%\trivlist
% \topsep 0pt
% \itemsep 1pt
%
%
%\item
The first is if an attacker creates an impersonating profile on $SN_2$ that is more similar than the true \matchingprofile. It might be possible to detect these cases as both $p_{1st}$ and $p_{2nd}$ will be high and $(p_{1st} - p_{2nd})$ will be very small.
 %It might be possible to detect these cases as there will be two
%\profiles (the real and the impersonator) that both have high
%similarities to $a^{1}$, and the difference between their similarity is small; 
The second is when the true \matchingprofile $\hat{a}^{2}$ is in $C(a^{1})$
  but a non-matching profile $a^{2} \in C(a^{1})$ is chosen as output
  because the classifier assigns it a higher probability $p$ of being the matching profile (due to the lack of attribute availability and/or consistency).  
%  the probability $p$ of $a^{2}$ is larger than $p$ of $\hat{a}^{2}$ (due to the lack of attribute availability and/or consistency).  
  Another case is when $\hat{a}^{2}$ does not exist, forcing the scheme to choose the \nonmatching \profile that is the most  similar to $a^{1}$ as the output. We might detect these cases as $p_{1st}$ and $p_{2nd}$ will not be very high (none of the profiles in $C(a^{1})$ are very similar to $a^{1}$) and $(p_{1st} - p_{2nd})$ will be again very small (none of the profiles in $C(a^{1})$ is much more similar than the rest).
  
%attributes of the \psysname might be less similar to those of  the given Twitter \profile compared to scenarios where the true  \matchingprofile is the \psysname. Furthermore,  there might be multiple Facebook \profiles with relatively high similarities to the given Twitter \profile and the most similar profiles is not much more similar than the rest. 
%   
%  ntuitively, it might be possible to
%  detect these cases, as there would be multiple Facebook \profiles
%  with not so high similarities to the given Twitter \profile and the most similar profile will not be much more similar than the rest. 
  
%\item $3$. When the true matching Facebook \profile does not exist, forcing the scheme to choose the \nonmatching \profile that is most
%  similar to the given Twitter \profile as the output.
%  Intuitively, we might be able to detect this case, as the
%  attributes of the \psysname might be less similar to those of 
%  the given Twitter \profile compared to scenarios where the true
%  \matchingprofile is the \psysname.




%To reason wheter the \psysname is a true or false match, we can simply look at the probabilities of the two most similar profiles. %s and only output the \psysname if it is significantly more similar than the second most similar profile. 
 
%\move{The \confidence ensures a reliable matching by distinguishing between the scenarios where the \psysname is a true match versus a false match and abstain from producing an output in the latter case.}




%
%Thus, we build the \confidence to add a second level of confidence and checks if the most similar \profile, as retuned by the \disambiguator, and returns the \profile only if it is very confident that is indeed the true \matchingprofile and abstains otherwise. Part of the \confidence's job is to detect impersonator attacks.

 %For a given Twitter \profile a, the \confidence takes as input the probabilities of profiles on Facebook to be matching profile. 
 
%\noindent \textbf{Input:} The two most similar \profiles in $C(a)$, i.e. the profiles with the highest probabilities to be \matchingprofiles as computed by the \disambiguator.
%\noindent \textbf{Output:} The \matchingprofile on $SN_2$ or nothing. 
%\noindent \textbf{Objective:} Minimize the number of false matches while maximizing the number of true matches returned by the matching scheme. 
%\noindent \textbf{Conception:} 
%\noindent You  can refer to the Appendix~\ref{app:guard} for evidence that supports these intuitions.

%\noindent \textbf{Realization:} 

%\if 0
%Since in the \disambiguator assumes that all the input in the \disambiguator are independent, i.e., it does not take into account neither that we have a set of input all dependent of on of the target profiles nor  how similar are the profiles in the candidate set. Then, we include this third step to \profile for this structure in the data. In this step we build a binary classifier in which the inputs are the outputs of the \hybridsvm for the two profiles with higher probability of being correlated and the similarities among the profiles in the $SN_2$... (I do not remember exactly what the input is, but I have the idea in mind, so fill it up with the truth).
%\fi


%We now show how \confidence can be leveraged to estimate with
%high confidence when the output from \sysnameD is correct and when it is not. 
%Given a Twitter \profile $a$, we use \sysname{} to rank
%Facebook \profiles based on the probabilities that they are correlated
%to $a$. 

To incorporate the above logic, we design the \confidence which is a binary classifier that takes as input $p_{1st}$ and $p_{2nd}$ and outputs the probability that the \psysname is the \matchingprofile. 
%We apply \hybridsvm to the training data in \largescale to obtain the probabilities to be matching profiles of all combinations of pairs. We then train the \confidence with the probabilities $p$ of being \matchingprofiles of the two most similar profile in $C(a)$ when \psysname is a true match and when it is a false match.  
Figure~\ref{fig:prec_rec_scale_topmatch} shows that  the \confidence  increases the recall of the matching scheme to  29\%  for a 95\% precision.  %This result means that, whenever the \confidence returns a profile, 95\% of times it will be the true match and only 5\% of times will be a false march. 
Although 29\% recall is a big improvement over the recall previously obtained, the recall is still low. This shows that in practice, it is hard to achieve a high recall if we want to have a high precision. 

% to only output the \psysname if it is much more similar with the target Twitter profile than any other Facebook profile. 
%We design the \confidence to incorporate all the above logic and only output a match when there is a Facebook profile that is much more similar with the Twitter profile than the rest of Facebook profiles. 

The matching schemes in~\xref{sec:linker} decide independently for each pair ($a^{1},a^{2}$) where $a^{2} \in C(a^{1})$ whether it is a match or not. In contrast, the strength of the \confidence is that it exploits the structure of $C(a^{1})$ for a given $a^{1}$. In particular, since $C(a^{1})$ depends on $a^{1}$, for a given probability $p$ to be the matching profile of $a^{1}$, the \psysname profile $a^{2}$ will be declared a match for some $a^{1}$ if its attribute values are sufficiently unique, whereas the scheme will return nothing for other $a^{1}$ if the attribute values are too common (e.g., Jennifer Clark that lives in New York). This reduces considerably the false matches and, as we have shown, increases a lot the matching recall for a given precision. 



%The matching schemes in~\xref{sec:linker} decide whether each pair of profiles ($a^{1},a^{2}$) where $a^{2} \in C(a^{1})$ is matching or not independently.  The \confidence takes into account the fact that the profiles are actually dependent on $a^{1}$ and exploits the structure in $C(a^{1})$. Put differently, the \confidence exploits the uniqueness of attribute values of the \psysname. For example, if the attributes values  are unique there will be no other \profile in $C(a^{1})$ that is as similar as the \psysname, while if the attribute values are not unique (e.g. Jennifer Clark that lives in New York) there will be a bunch of profiles with similarities close to each other.


%\vspace{4mm}
%\noindent \minisec{Realization}
%\label{sec:guard}

%For training the classifier, we again select 1,000 Twitter profiles from \datasetFF (that are not used for testing the matching schemes or for training the \filter and \disambiguator) and we apply, as described, the \filter and \disambiguator to find the \psysname. We train the classifier with the probabilities $p$ of being \matchingprofiles of the two most similar accounts in $C(a)$ when \psysname is a true match and when it is a false match. 

%\oana{maybe add plots with similarity i previously had}
%
%The \confidence outputs the probability, $p$, the \psysname is the \matchingprofile. We select a
%cut-off threshold for $p$ and the \confidence returns 1 (i.e., \psysname is the \matchingprofile) if $p$ is larger than the
%threshold; and 0 otherwise. %The threshold's choice constitutes the
%standard tradeoff between true and false positive rates. 
\if 0
\toremove{The  \confidence is able to detect 42\% of the cases when the \psysname is the \matchingprofile while it only misclassifies 1\% of the cases when the \psysname is \nonmatchingprofile. It can also operate at a 60\% true positive rate for a 5\% false positive rate.}
\fi 

%Because we want the \sysnameS to return the \matchingprofile with high confidence we pick a threshold corresponding to a 1\% false positive rate. This threshold gives a  40\% true positive rate. 

%The confidence in the correlation is computed as the number of true positive divided by the number of positives (true and false) returned by \sysnameS.  


%Figure~\ref{fig:confidence}
%shows the ROC curve: we have a 40\% TPR for 1\% FPR, and 62\% TPR for
%5\% FPR and a 78\% TPR for a 10\% FPR. 

%We interpret this probability as an overall confidence score. We train this classifier
%using our ground truth datasets with samples where the \profile ranked
%first is the \matchingprofile and samples where the \profile ranked
%first is not the \matchingprofile. We select a cut-off threshold for
%this probability and the classifier returns 1 (i.e., correlated
%\profile) if the probability is larger than the threshold; and 0
%otherwise. The threshold's choice constitutes the standard tradeoff
%between the true and false positive rates.

%We train and test the classifier using 10-fold cross validation with
%1000 Twitter-Facebook \profile pairs, where the Facebook \profile
%selected is the most similar to the Twitter \profile (in 500 of these
%pairs, the Facebook \profile is the \matchingprofile, and in the
%other 500 it is not correlated).
%These results suggest that we
%can identify confidently a large fraction of \matchingprofile with
%only a small fraction of misidentification.
%We chose the threshold corresponding the 40\%TPR and to 1\% FPR to decide whether an \profile is correlated with. 
%Probability to be positive knowing that I say it is positive is 97\%. Since there are half correlated and half font \matchingprofile. 
%

%Figure~\ref{fig:confidence_linker} shows the ROC curve when we use the \sysname and Figure~\ref{fig:confidence} shows the ROC curve when we use the new classifier.
%\begin{figure}[htbp]
%%\vspace{-8mm}
%\begin{center}
%\includegraphics[width=0.5\columnwidth]{plots/prediction_rank_1_random_svm.eps}
%%\vspace{-2mm}
%\caption{True positive rate vs False positive rate when predicting if the most similar \profile is the \matchingprofile with \sysname.}
%\label{fig:confidence_linker}
%\end{center}
%%\vspace{-2.5\baselineskip}
%\end{figure}

\if 0
\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
\includegraphics[width=0.3\textwidth,height=3.5cm]{plots/prediction_rank_1_dis_svm.eps}
%\vspace{-2mm}
\caption{ROC curve to detect \psysname when it is correlated and when it is uncorrelated.}
\label{fig:confidence}
\end{center}
%\vspace{-2.5\baselineskip}
\end{figure}
\fi

%\paragraph{Evaluation at scale}

 %To stress the inherent difficulty of matching profiles at scale, the next section will show that even humans cannot match profiles much better. 
%it is almost as good as what humans can do.

%\paragraph{Testing the reliability of the matching scheme}
%\label{sec:reliability}

\if 0
To ensure that the three-step matching scheme is indeed reliable we test how well it performs when there is no \matchingprofile on the second social network, and when there is an impersonator.
\fi


\noindent \minisec{Reliability in the absence of a \matchingprofile}
% In practice a Twitter user may not have a Facebook \profile. Ideally the matching scheme should return no profile in this case. 
\noindent To test the reliability of the matching scheme  in the absence of a matching profile, we 
take the \largescale and we remove the matching profiles from the dataset.
Then, we  evaluate the \confidence over the resulting dataset. Ideally, the \confidence should not return any profile as there is no matching profile in the dataset.  Indeed, the \confidence only returns a false match for 1\% of the Twitter \profiles. 
We manually investigate the 1\% cases: in half the returned profile is a false match;  in the other half it is actually a \profile that corresponds to the same person (the returned profiles are either impersonators or people that maintain duplicate \profiles on Facebook).
Thus, the \confidence is reliable when there is no matching \profile in $SN_2$. 


%\noindent We again take 1,000 Twitter \profiles in \datasetFF and 1,000
%in \datasetG and we check the percentage of cases when we are
%confident that the \profile ranked first is the \matchingprofile. For
%the \datasetFF we can match 24\% of \profiles with a 99\% confidence
%and 35\% of \profiles with a 95\% confidence.  This results agree with
%previous results, in 50\% of the cases the \matchingprofile is in
%the first position and we have a 40\% TPR for a 1\% FPR of the
%confidence. For the \datasetG we can match 33\% of the \profiles with a
%99\% confidence and 45\% with a 95\% confidence.



\if 0
 \noindent We sort the Facebook \profiles in $C(a)$ according to $p$. 
We define the \emph{rank} as the position of the \matchingprofile in the sorted list of candidate \profiles. The best case is when the \matchingprofile has a rank of one. Figure~\ref{fig:rank} shows the CDF of the rank of the \matchingprofile. The X-axis is in log scale to focus on small ranks. When the \matchingprofile is not in $C(a)$ we put the rank to be 10,000.
\fi 

\if 0
The \disambiguator yields the Facebook \matchingprofile for 50\% of the
Twitter \profiles. For the remaining Twitter \profiles, the \psysname is {\it not}
the \matchingprofile. While 50\% might sound low, note that for 30\% of the
Twitter \profiles, the candidate set does not contain the \matchingprofile and thus, it cannot yield a true match. Excluding such
cases, the percentage of Twitter \profiles for which \disambiguator
yields a true match is as high as 75\%.
While the recall of the \disambiguator might be acceptable at 50\%
(or higher), the precision of the \disambiguator is quite low at
50\%. Any reliable
matching scheme would require the precision to be substantially higher a challenge that it will be solved by the \confidence. 

If instead of selecting the \psysname we used a threshold for the probability to be matching $p$, as we did for the \sysname, the \filter and the \disambiguator would achieve a 30\% recall for a 23\% precision.  This accuracy is better than the accuracy of the \sysname alone.
However, perhaps the most important asset of the \disambiguator is in increasing the gap between the true and false matches to make the \sysname more accurate. Indeed, the \disambiguator separates very well the \matchingprofile (giving a high probability) from other profiles in $C(a)$ (giving a low probability). On the contrary, the \sysname gives very close probabilities to be matching to all profiles in the candidate set (i.e., all profiles with similar real names).
\fi 


%\noindent The \disambiguator returns the same number of true and false matches (on average 50\% of the \psysname \profiles are true matches and 50\% are not).  When we test the \confidence we obtain a 21\% recall for a 98\% precision or a 30\% recall for a 92\% precision.

\if 0
\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
\includegraphics[width=0.35\textwidth]{plots/prec_rec_scale.eps}
%\vspace{-2mm}
\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles using different techniques at scale.}
\label{fig:prec_rec_scale}
\end{center}
%\vspace{-2\baselineskip}
\end{figure}
\fi 

\if 0
\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
\includegraphics[width=0.35\textwidth]{plots/prec_rec_top.eps}
%\vspace{-2mm}
\caption{Precision and recall tradeoff for matching Twitter to Facebook profiles by returning the top match at scale.}
\label{fig:prec_rec_scale}
\end{center}
%\vspace{-2\baselineskip}
\end{figure}
\fi

\if 0
\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
\includegraphics[width=0.3\textwidth,height=3.5cm]{plots/CDF_rank_exact_match.eps}
\vspace{-2mm}
\caption{CDF of the rank of the \matchingprofile for matching Twitter to Facebook profiles using the \filter and the \disambiguator.}
\label{fig:rank}
\end{center}
\vspace{-2\baselineskip}
\end{figure}
\fi 



%Thus, the new matching scheme can link 21\% of the Twitter \profiles to their corresponding Facebook \profiles with a very high precision.



%\noindent \textbf{Takeaway:} The three-step matching scheme can match 21\% of Twitter \profiles to their corresponding Facebook \profiles with 98\% precision. To increase the precision the scheme has to trade off recall.  



\section{Evaluation against humans}
\noindent In this section, we confirm the inherent difficulty to obtain a high recall in matching profiles in practice by comparing our results with results obtained by asking human workers to match profiles.
%We also compare the accuracy of the matching scheme that uses the \hybridsvm and the \confidence with that of humans.  

For this we designed an AMT experiment. We randomly select 200 Twitter-Facebook matching profiles from \datasetFF (that are not used for training the matching schemes).
%For each Twitter \profile we collect the candidate set and we rank the
%Facebook \profiles according to their similarity to the Twitter
%\profile.  
In each assignment, we give AMT workers a link to a Twitter
\profile as well as links to the 10 most similar Facebook \profiles (we shuffle their position) and we ask AMT workers to choose the matching \profile. We allow  workers to choose that they are unable to identify the \matchingprofile. For each assignment we ask the opinion of three different  workers.  We present the results for majority agreement (two out of three workers decided on the same answer).
We design two versions of the experiment: in the first one if the \matchingprofile is not in $C(a^{1})$,  the \matchingprofile will not be in the list of 10 Facebook \profiles; and a second version, where we always put the matching profile the list of 10 Facebook profiles. %The first version of the experiment gives AMT workers similar conditions with the matching scheme while the second version gives them perfect conditions, i.e., there are no limitation introduced by the Facebook search API. 

In the first version of the experiment, AMT workers were able to match 40\% of the Twitter \profiles to their matching profiles and 4\% are matched to the wrong Facebook profile. This means that AMT workers achieve a 40\% recall for a 96\% precision, which is better than the \confidence, but far from a 100\% recall.  In the second version of the experiment, AMT workers were able to match 58\% of Twitter \profiles. Thus, even humans cannot achieve a recall close to 100\% to match profiles in practice.  
%  Because human users can be considered as a golden standard for identifying people, their matching accuracy shows the limits a matching scheme could potentially achieve.

%To understand the limitations of our matching scheme we compare the \profiles AMT workers detect vs. the \profiles the matching scheme detects. 
%About 40\% of the \matchingprofile  detected by AMT workers are also detected by the matching scheme. To understand why the matching scheme does not link the rest we manually checked the descriptions AMT workers gave in the assignments. About 58\% of the missed profiles are detected by AMT workers because they have the same person in the photos, 15\% have some matching bio information and the rest have some sort of content, interests that match. These results hint at ways we can improve the matching. 
%
%The matching scheme is able to detect 5\% of \matchingprofiles that AMT workers do not detect. 
%These \profiles have friends in common which AMT workers do not check.
%These results suggest that if we combine AMT workers with the matching scheme we can potentially attain a 45\% recall (40\%+5\%) for a 96\% precision.












% \change{Including the \matchingprofile in the 10 most
 % similar \profiles will give an unfair advantage to AMT workers. Also
 % giving them 10 \profiles already simplifies their work.} 

%To ensure good quality results we only grant master workers to
%participate in the assignment. Workers took in average 10 minutes for
%each assignment.
%\change{we can say that this does not mean than workers are better than an automatic algorithm, if they were not aided by our matching scheme would be much complicated we are just testing their ability to identify matching profiles so that we can understand the performances of the matching scheme better.}


%Table~\ref{tab:detectable_amt_scalable_linker} compares the \profiles AMT workers
%detect versus the \profiles the three-step matching scheme detects. For the AMT experiment,
%we consider the type of agreement as a proxy for the confidence in the
%detection. Only if there is a full agreement among AMT workers we consider that the detection has a high confidence.
%Out of 200 \profiles, AMT workers detected with high confidence 45 \matchingprofile while the \sysnameS detected
%41 \matchingprofile.   
%\old{
%Half of the \matchingprofile  detected by the matching scheme
%are also detected by AMT workers with full agreement. Most of the 21 \profiles that the matching scheme detects but that AMT workers do not correspond to pairs of \profiles that have friends in common which AMT workers did not check.  The 25 \profiles that AMT workers detect but the matching scheme does not correspond to pairs of \profiles that have the same person in the photos, but not the exact same photo. For most of the \matchingprofile that the
%matching scheme was not able to detect, the AMT workers are also unable to detect with high confidence.
%}

%\noindent \textbf{Takeaway:} Under similar conditions, the AMT workers do not detect much more accounts than the three-step matching scheme, AMT workers can achieve a 25\% recall for a 98\% precision.


%The 10 \profiles
%that AMT workers could not match but the \sysnameS matched with
%confidence correspond to \matchingprofile that have friends in
%common.  22 out of 53 \profiles ranked first but without confidence are
%matched with full agreement by AMT workers. They correspond to
%\profiles that have the same person in the photos, however they do not
%have exactly the same photo.  For most of the \profiles where the
%\sysnameS was not able to match, the AMT workers are not able to match
%either (38 out of 47 \profiles with ranks higher than one).  


%There are
%a few cases where the \sysnameS did not ranked the \matchingprofile
%first or the \matchingprofile was not in the candidate set and where
%AMT workers matched an \nonmatchingprofile. \change{explain this.}
%There are no \nonmatchingprofiles matched by the \sysnameS with
%confidence.

\if 0
\begin{table}[htdp]
\caption{Number of profiles detected and undetected by the matching scheme and detected by AMT workers with full of  majority agreement.}
\begin{center}
\begin{tabular}{c||c|c}
&  \multicolumn{2}{c}{AMT}     \\
& Full Agreement  & Majority Agreement \\
\hline
\hline
Matched & 20 & 29  \\
Rank=1 & 22 & 36  \\
Rank>1 & 3 & 8 \\
\end{tabular}
\end{center}
\label{tab:amt_dis}
\end{table}%
\fi


\if 0
\begin{table}[htdp]
\footnotesize{
\caption{Number of detected and undetected \matchingprofiles by AMT workers with full agreement and by the three-step matching scheme.}
\begin{center}
\begin{tabular}{cc||cc}
\multicolumn{2}{c||}{} & \multicolumn{2}{c}{\textbf{\sysnameS}} \\
\multicolumn{2}{c||}{}  & Detected & Undetected \\
\hline
\hline
 \multirow{2}{*}{\textbf{AMT}} & Detected & 20 & 25 \\
 & Undetected & 21 & 134 \\
%AMT not detected \& LINKER detected & 34\% \\
%AMT not  detected \& LINKER not detected & 8\% \\
\end{tabular}
\end{center}
\label{tab:detectable_amt_scalable_linker}
}
\end{table}%
\fi 


\if 0
\subsubsection{Reliability to impersonation}

%{\bf Analyze the vulnerability of \sysnameS{} to impersonation attacks
%  in the absence of a \matchingprofile. Point out what \profile
%  attributes the attacker's \profile would have to mimic to fool
%  \sysnameS{} and the difficulty of obtaining this info from existing
%  sources on the Web. -- KG}
%
%{\bf Analyze the vulnerability of \sysnameS{} to impersonation attacks
%  in the presence of a \matchingprofile. When a \matchingprofile
%  is already present, the task of impersonation becomes much
%  harder. \sysnameS{} would declare that it cannot distinguish between
%  the impersonated \profile and the \matchingprofile. -- KG}
%
%{\bf In fact, the robustness of \sysnameS{} to impersonation can be
%  used to study if spammers and malicious attackers are impersonating
%  \profiles today. Discuss whether such attacks are able to fool end
%  (human) users today. -- KG}



\noindent We now study the vulnerability of the matching scheme to
impersonation attacks.  
We distinguish two different scenarios when
impersonation attacks occur: (1) when a user does not have a
\matchingprofile on the second social network and (2) when a user
has a \matchingprofile on the second social network.

In the case where there is no \matchingprofile on the second social
network the matching scheme is vulnerable to impersonation attacks. The
matching scheme  is based only on public attributes. So an
attacker can easily gather the attributes of the public profile of the
victim in one social network and create a cloned profile on the second
social network. If the impersonator creates an \profile that has the
same real name, similar screen name and has the same profile photo or
location, she would be able to fool the matching scheme into marking the
impersonated \profile as the \matchingprofile.

In the case where the user has a \profile on the second social
network, the task of impersonation becomes much harder.  Recall
from~\xref{sec:3step} that \confidence is designed to be resilient to impersonation attacks. If the attacker creates
a cloned \profile on the second social network then there will be two
\profiles (the real and the impersonated one) that have high
similarities and there is a good chance that the difference between
their high similarity scores will be small. 
In this case, the \confidence
will not return a \matchingprofile, avoiding a false match.
The only scenario when the attacker can trick the matching scheme is when the
\matchingprofile does not have a good similarity with the target \profile.

In fact, we ca use the robustness of the matching scheme to impersonation to study if spammers and malicious attackers are impersonating \profiles today. To search for impersonators we check Twitter \profiles in \datasetFF that have two Facebook \profiles with probabilities to be matching (as returned by the \disambiguator) higher than 0.95 that are rejected by the \confidence. The intuition is that one of the profiles might be an impersonator. 
We collected 16 such \profiles. For each of the 16 Twitter \profiles, we take the \profile which is not the \matchingprofile and we ask AMT workers whether the Twitter and this Facebook \profile belong to the same person.  If someone is trying to impersonate the AMT workers should think the accounts belong to the same person. AMT workers said that four \profiles out of 16 belong to the same person. This shows that the design
of the matching scheme makes it resilient to impersonation attacks in cases
where the victim has created a \profile on both sites and that it can be used as a tool to find impersonators.

\fi 
%\noindent \textbf{Takeaway:} The three-step matching scheme is reliable both when there is an impersonator on the second social networks and when there is no corresponding \profile.

\if 0
In fact, the robustness of \sysnameS{} to impersonation can be used to study if spammers and malicious attackers are impersonating \profiles today.  To search for impersonators we check all the \profiles in the \datasetFF and \datasetG that have a good similarity score ($>$0.95) but are ranked second. The intuition is that the \profile ranked first might be an impersonator.  We have 16 such \profiles.
For each of the 16 Twitter \profiles, we take the most similar \profile (which is not the \matchingprofile) and we ask AMT workers whether the Twitter and the Facebook \profile ranked first belong to the same person, we call this \profile \textsc{dataset imp. rank 2}. For each pair of \profiles we asked three workers.  Table~\ref{tab:amt_impersonators} shows the number of \profiles AMT workers said that they correspond to the same person or not. AMT workers said that four \profiles out of 16 belong to the same person, and for another four they disagree (i.e, one worker said that they belong to the same person, one that it does not belong and one that it cannot say). 
Other \profiles we can study for impersonation attacks, are the Twitter \profiles for which we have a high confidence that the \profile ranked one is the \matchingprofile but we are wrong (i.e. false positives). We study 30 \profiles of this type which we call \textsc{dataset imp. conf.} 
Table~\ref{tab:amt_impersonators} shows that AMT workers  identified 15 out of 30 \profiles as belonging to the same person, and for 8 there is no agreement. There are two explanation why there are so many \nonmatchingprofiles for which AMT workers think they belong to the same individual: 1) the users maintain multiple \profiles on Facebook, 2) there is an impersonation attack.
Out of the \profiles in \textsc{dataset imp. conf.}, 23  did not have the \matchingprofile in the candidate set.  Which incidentally shows that whenever a user does not have an \profile on a second social network it is more vulnerable to impersonation attacks. \change{In this case it is not really that he does not have an \profile but is that we couldn't catch it in the candidate set because maybe it has a very different name.}


\begin{table}[t]
\footnotesize{
\caption{Impersonator detection. $\dagger$ $X\%$($Y\%$) = fraction of \profiles with majority agreement (fraction of \profiles with full agreement).}
\begin{center}
\begin{tabular}{c|c|c}
&  \textbf{\textsc{dataset imp rank 2} } & \textbf{ \textsc{dataset imp. conf.} }\\
&  \textbf{16 \profiles} & \textbf{30 \profiles}\\
\hline
\hline
\textbf{Detected Correlated} & 4(3) $\dagger$ & 15(9)  \\
\textbf{Detected Uncorrelated} & 8(8) & 9(5) \\
\textbf{No Consensus} & 5 & 8 \\
\end{tabular}
\end{center}
\label{tab:amt_impersonators}
}
\end{table}%

\fi




 
\section{Related Works}
\label{sec:existing_schemes}
%\update{ Finally, we review the strengths
%and weaknesses of prior work according to these requirements
%and discuss the contributions of this paper.}

%\rt{I think that this section still reads a lot like a related work. You should 
%try to come up with some categories of
%how the matching schemes work. The goal is to convince the readers that you are evaluating
%these schemes later. I think you can remove (at least from here) the part about 
%deanonymization, unless you can frame it as a matching scheme. You can have a small
%related work section later perhaps. The part on
%matching schemes using private info can go to related work if you do one or can stay here and
%you can dismiss this quickly. The bulk of this section should be the part on schemes based on 
%public attributes. It would be nice to have some taxonomy that would allow the reader to get convinced that
%you are covering everything in your analysis later.}

\noindent We review three primary lines of related research: one
proposing schemes to match user profiles across different social
networks; one focusing on how anonymized user graphs or databases
can be deanonymized to infer user identities; and another about matching entities across databases.

%Firstly there are studies that propose schemes to match users
%profiles across different social networks by exploiting different
%features extracted from their profiles.  We also include studies that
%do not necessarily match profiles across social networks but they
%match identities. Such studies de-anonymize databases and graph data
%by matching nodes to known identities. This kind of studies assume a
%much more adversial environment than our work as the nodes in a graph
%do not have any identifiable information attached to them.



%We use our ACID framework to study them. Remember that the
%scalability of a specific technique depends on the number and
%quantity of the ACID properties it has.

%\subsection{matching user profiles across social sites}

%\vspace{2mm}
\noindent \minisec{Matching profiles using private user data} 
Balduzzi et al.~\cite{balduzzi09osnProfiling} match
profiles on different social networks using the ``Friend
Finder'' mechanism that social networks provide for users
to find their friends using their email addresses. 
%The study attempted
%to match profiles with a list of 10 million \emph{e-mail}
%addresses.  
%As e-mail addresses satisfy all the four \tname
%properties, 
%This is a simple yet powerful technique for matching
%profiles. 
In fact, this is what we use for obtaining our ground truth.
Many sites, however, view Friend Finder as leaking users'
private data and have since limited the number of 
queries a user can make which severely limits the number of profiles one can match.
%In contrast, sites tend to be less
%concerned over matching user profiles using users' public data
%(even if the privacy threats remain the same). 
%In this paper, we focus on matching profiles using only public attributes.
In contrast, we are interested in understanding the limits of matching profiles by only using public attributes that anyone can access without assuming that we have access to more private data such as the emails of users.

%same screen name ~\cite{LabitzkeSebastian,IofciuFAB11}
%google+ equivalent ~\cite{jain:Iseekfbme:2013:wole,malhotra1,PeritoCKM11,Zafarani:2013:CUA:2487575.2487648}
%manual ~\cite{Liu:2013:WNU:2433396.2433457,5272173,conf/socialcom/PeledFRE13}
 
%\vspace{2mm}
\noindent \minisec{Matching profiles using public user data}
A number of previous studies proposed matching schemes that leveraged different attributes of public user data to match profiles, but without systematically understanding their limitations in real-world social networks. 
%As a result, previous works have a number of methodological issues: 
As a result, previous works overlooked a number of methodological aspects: 
($1$) Most works did not train and test their matching schemes on sampled datasets that preserve the reliability of the original social network. Consequently, the reliability of these schemes drops significantly when evaluated in real-world social networks~\cite{PeritoCKM11,Motoyama,5636108,5272173,conf/socialcom/PeledFRE13,Liu:2013:WNU:2433396.2433457,Zafarani:2013:CUA:2487575.2487648,conf/icwsm/ZafaraniL09}; ($2$) Most works used attributes without analyzing their properties and their  limits to match profiles in practice, consequently, some of these studies use attributes with low availability and thus can only match a small fraction of profiles across a limited number of social networks~\cite{mywww,IofciuFAB11} or use attributes that are prone to give many false matches in practice~\cite{MishariT12}. On the contrary, we propose a framework to analyze attributes and evaluate their potential to match profiles in practice. ($3$) Most studies used biased sets of ground truth users that willingly publish links to their profiles on different social networks. Our analysis reveals that such datasets have attributes that are more available and consistent, consequently, the reliability results of such schemes are overly optimistic~\cite{jain:Iseekfbme:2013:wole,malhotra1,PeritoCKM11,Zafarani:2013:CUA:2487575.2487648}. Other studies assume that all profiles that have the same screen name are matching~\cite{LabitzkeSebastian,IofciuFAB11}. In~\xref{sec:discr} we showed that 20\% of profiles with the same screen name in Twitter and Facebook  are actually not matching.
%Most works used features without understanding  their properties and their potential to match profiles at scale, consequently, some of these studies use features with low availability and thus can only match a small fraction of profiles across a limited number of social networks. 
We further split these studies according to the type of attributes used. % they use. 

The closest to our work are a number of schemes that leverage information in the \emph{profiles of users} similar to the attributes we use in this paper~\cite{Motoyama,PeritoCKM11,malhotra1,jain:Iseekfbme:2013:wole,Acquisti,socialsearch,5272173,5636108,northernunsupervised,conf/socialcom/PeledFRE13,Liu:2013:WNU:2433396.2433457,Zafarani:2013:CUA:2487575.2487648,conf/icwsm/ZafaraniL09,socialsearch, LabitzkeSebastian}. 
%The work by Motoyama et al.~\cite{Motoyama} is one of the earliest
%studies that showed the potential of matching profiles using
%\emph{profiles attributes} (e.g. location, occupation, university,
%gender) aiming to assist users to find their friends when they join a
%new social network.  
%
%These techniques~\cite{PeritoCKM11,Motoyama,5636108,5272173,conf/socialcom/PeledFRE13,Liu:2013:WNU:2433396.2433457,Zafarani:2013:CUA:2487575.2487648,conf/icwsm/ZafaraniL09} have only been evaluated using small-scale datasets.  
%The techniques proposed by Perito et al.~\cite{PeritoCKM11} and Motoyama et al.~\cite{Motoyama} have only been evaluated using small-scale datasets. 
Most schemes work by training classifiers to distinguish between matching and non-matching profiles.  We simulated these approaches in~\xref{sec:linker} and we saw that, because they did not consider the problems that come with matching in practice, the matching schemes are very unreliable when evaluated in real-world social networks. 
 %
%As discussed in \xref{sec:linker}, it is unclear whether they would work at the scale of hundreds of millions of profiles. 
%First, at large scale, a user might not provide some attributes or might provide
%inconsistent attribute values across sites. Hence, these schemes would have
%to relax their criterion for matching attribute values. Second, there would be hundreds of profiles that
%would match any given attribute value. 
A few studies attempted to perform profile matching in practice~\cite{malhotra1,jain:Iseekfbme:2013:wole,Acquisti}. 
%Similar to our work, Malhotra et al.~\cite{malhotra1} and Jain
%et al.~\cite{jain:Iseekfbme:2013:wole,Acquisti} attempted to match profiles
%using profile attributes. Acquisti et al. studied the power of
%\emph{face} recognition algorithms to match profiles in a dating site
%to Facebook profiles~\cite{Acquisti}. Even though the study showed
%that 10\% of the profiles can be matched, it also acknowledged that
%face detection algorithms need to lower their false positives to be
%usable at large scale.  
These studies, however, just pointed out that profile
matching in practice yields a large number of false matches. %They do not, however, investigate the reasons behind the low reliability of their schemes. 
In contrast, we conduct a systematic analysis of the causes of such false matches and possible ways to eliminate them.
%You et al.~\cite{socialsearch} proposed the only scheme that has a notion of confidence 
%in the match. However, the algorithm only works for people with sufficiently notable
%web presence, which limits its scalability. In contrast, our work attempts to find
%matching profiles for arbitrary users.
%\todo{describe how these matching schemes work}

%A number of other studies matched profiles by exploiting \emph{friends lists} of social networks~\cite{,}\todo{problem with citations}.  Our results confirm that friendship overlap is one of the most important features for detecting matching profiles at scale.  \todo{merge with previous paragraph}
% and we use it to complement the other features extracted from user profiles. 




%To give more relevant information when searching people on the web,
%You et al.~\cite{socialsearch} proposed a scheme to link people's names
%to their social identities. Their scheme discriminates between candidate social
%identities by matching the \emph{relational graph} of co-occurrences of
%names, extracted from EntityCube\footnote{http://entitycube.research.microsoft.com/}, to the \emph{friends graph}. 
%Similar with our matching scheme, they propose a notion of confidence in the match. 
%The algorithm, however, only works for people with notable web presence that have an
%entry in the relational graph thus the scalability is limited. In contrast, our scheme in Chapter~\ref{chap4}  finds matching accounts for arbitrary users.

%You et al.~\cite{socialsearch} proposed the only scheme that has a notion of confidence 
%in the match. However, the algorithm only works for people with sufficiently notable
%web presence, which limits its scalability. In contrast, our work attempts to find
%matching accounts for arbitrary users.


% to 
%Labitzke et al.~\cite{LabitzkeSebastian} showed that the overlap between friends can be used to match accounts on social networks. Our results confirm that friendship overlap is an important feature for detecting matching accounts and we use it to complement the other features extracted from user accounts. Similar with efforts in de-anonymizing graphs, Korula and Lattanzi mathematically formalize the problem of matching accounts across social networks and propose an algorithm that uses the friendship graph to match accounts~\cite{DBLP:journals/pvldb/KorulaL14}. 
%As we discussed in~\xref{rw:sn:i}, researchers have propose algorithms to jointly predict links and infer attributes in social networks.  Bartunov et al.~\cite{sergey} took this approach further and proposed a \emph{joint link-attribute} algorithm to match two social networks. The structure of the networks can be used to infer missing attributes; while profile attributes can be used to link matching nodes. The authors, however, only evaluated the algorithm on one-hop neighbors. As we already discussed, the structure of the social graph is certainly a powerful feature and, combined with other features, it might improve the overall matching accuracy. Nevertheless, we leave this for future work. 


%To give more relevant information when searching the web for people
%You et al.~\cite{socialsearch} proposed a scheme to link peoples names
%to their social identities. To discriminate between candidate social
%identities they match the \emph{relational graph} of co-occurrences of
%names, extracted from EntityCube, to the \emph{friends graph}.  It is
%the only scheme that proposes a notion of confidence in the match.
%However, the algorithm only works on people with sufficiently notable
%web presence that they have an entry in the relational graph, which
%limits its scalability. In contrast, our work attempts to find
%matchd profiles for arbitrary users.

\if 0
These
studies matchd profiles based on profiles attributes and employed
more sophisticated techniques to measure the similarity between
profile attributes than the bag of words.  Both schemes consider the
N-ary profile matching, however they do not study the reliability
of their scheme with respect to the confidence in the match and
impersonators. Moreover they use a biased dataset.
%Both of the schemes are evaluated at scale, however there is no
%notion of confidence in the match. Moreover both studies use a biased
%ground truth dataset.  Profile attributes have different levels of
%availability, while location information might be present in many
%profiles, relationship status might have a lower availability all
%this stu.
\fi

%

%


%Finally, there are many people search engines like
%PeekYou~\cite{peekyou} and Spokeo~\cite{spokeo}. Starting with basic information
%like screen names and real names, they return matching user profiles
%they collect from different social networks.  These services operate
%opaquely behind closed doors, and little is known about how they work
%or their capabilities and limitations. However, our analysis in this
%paper sheds light on the potential benefits and risks associated with
%relying only on public profile attributes for matching profiles
%across multiple social sites.

\if 0
From preliminary test we
believe that the services only return the profiles that have the same
real names and screen names without doing any other filtering. If
true, the reliability of such service is very bad.
\fi

%\noindent {\bf Leveraging user friends:}
%


\if 0
%
Other studies, such as the one by 
Bartunov et al.~\cite{sergey} proposed a \emph{joint link-attribute}
algorithm to match the friends of a given user on different social
networks; .... \change{However they all lack something.} 
%\change{The algorithm starts with a seed user and tries to
  %find as many matching profiles in his contacts on the two social
  %networks. The algorithm not scalable because it requires a seed node
  %to start and was not tested on matching more then just the first-hop
  %neighbors. } 
  
\fi
%A more refined technique would be to match the text in users profiles to named entities, and then count the number of overlapping name entities between profiles. 
% how do they compute the candidate set? 
% \change{When discriminating between users with the same name to find a friend a more straightforward technique would be to count the number of common friends and/or detect them based on facial features, humans are very good at this. Their paper is so lame...}

Other schemes use attributes extracted from \textit{user activities} (i.e., the content users generate instead of attributes of the profile)~\cite{mywww,MishariT12,IofciuFAB11}. These schemes reveal how even innocuous
activities of users can help identify a user across social networks. However, these schemes explore attributes with either low availability or low
discriminability, which makes them hard to use in practice without sacrificing reliability.

%Goga et al.~\cite{mywww} investigated how to match profiles by
%exploiting the \emph{location} from where users posts and the
%\emph{time} and the \emph{writing style} of the posts.  The matching
%is possible when the set of locations from where a user posts is 
%unique, and users post from the same locations on different social
%networks. However location metadata has a very low availability (only
%5\% of Twitter users attach geotags to their posts) thus the scheme
%only works for a small fraction of users.
%
%Mishari et al. showed that community reviews could be linked across
%different sites by exploiting the \emph{writing style} of the
%authors~\cite{MishariT12}. The writing style has a high availability
%and consistency as users post and they post on all the social networks
%they use, however the discriminability is low because the writing
%style it is not discriminating enough to accurately identify a single person.
%
%Another study that uses features with good consistency, high
%discriminability but low availability is the one by Iofciu etfalse matches
%al.~\cite{IofciuFAB11} that uses \emph{tags} to match users between
%Delicious and Flickr. The low availability of features used in
%matching limits the scalability of the scheme.


%\vspace{2mm}
\noindent \minisec{De-anonymizing user identities}
\noindent  De-anonymizing user identities and matching user profiles share common methods. 
%One could view deanonymizing user identities as matching profiles between unanonymized and anonymized user profiles. 
In fact, our work here is inspired by one of the seminal papers of Sweeney~\cite{sweeneyMedicalDeanon}, which explored the uniqueness
of attributes such as date of birth, postal code, and gender  to de-anonymize medical records of US citizens. 
%Similarly, we attempt to leverage public
%attributes for matching profiles. However, we have to deal with a
%noisier environment, where data is not always
%available or consistent and is vulnerable to impersonation.
%
%In some sense,
%de-anonymization studies assume an adversarial environment,�
%where the anonymization schemes explicitly try to strip out
%information useful for matching. Our \tname framework might be useful for
%de-anonymization studies as well. 
%
Other studies~\cite{narayanan09osn,DBLP:journals/pvldb/KorulaL14} showed the feasibility to
de-anonymize the friendship graph of a social network at large-scale
using the \emph{friendship graph} of another social network as
auxiliary information. The structure of the social graph is certainly  a powerful feature. Nevertheless, in this work, we explicitly assume that we  cannot have access to the entire graph structure of the social networks since we only use public APIs to collect data. We leave as future work how to exploit partial graphs that can be obtained trough APIs to improve matching schemes based on binary classifiers. 

%to study how to combine traditional methods to match profiles with methods that exploit partial graph structure that can be obtained trough APIs. 
%In a different scenario,
%Srivatsa et al.~\cite{srivatsa12mobility} explored how mobility traces
%can be de-anonymized by matching their contact graph with the
%friendship graph of a social network. While we use data about users'
%friends to match individual user profiles, we do not leverage the
%social network graph as a whole for matching profiles. We leave
%this for future work.



%\todo{RE: there are no references to papers in vldb. would be nice to add some.}

\noindent \minisec{Entity matching} There is a large body of research in the database and information retrieval communities on matching entities across different data sources~\cite{books/daglib/0030287}. %, they address similar problems  
%We actually inspire the design of the \filter and \disambiguator from the entity matching literature~\cite{books/daglib/0030287}.  However, the purpose of the \filter in entity matching is to make the matching scheme faster and more efficient while its purpose in our paper is mainly to identify non-matching \profiles that are hard to match. 
Conceptually there are many similarities between matching profiles across social networks and matching entities (e.g. the way we compute the similarities between attributes or the adoption of a supervised way to detect matches). However, matching profiles has some specific constraints (e.g., not being able to access all records in $SN_1$) that the entity matching community, to our knowledge,  overlooked.
%However, matching profiles has some specific constraints not yet considered in entity matching that make the entity matching techniques unusable for profile matching, most importantly the fact of not being able to access all records. % (e.g., not being able to access all records)

%However,  our contributions are in studying the limitations of these traditional matching methods and unveil the constrains we have to address when matching profiles in real-world social networks (e.g., not being able to access all records). 

%we tweak these methods to adapt them to our particular scenario. However, to our knowledge, the biggest difference is the introduction of the concept of the \confidence that is able to greatly increase the matching reliability. 




\if 0
\subsection{Our contributions}

{\bf Explain how the contributions of this paper differ from prior
  works discussed above -- KG}


Most of the previous mentioned studies hinted at ways to match profiles based on different features.
However, none of these studies had a proper evaluation of how their scheme would perform at large scale and how confident they are in the matching. Moreover, no study analyzed their scheme the case of impersonation. 

There are two main points to evaluate the scalability and reliability of a scheme. Firstly, for a scheme to be scalable it has to disambiguate the matchd profile out of a list of similar looking profiles. 
Most of the studies evaluated the performance of their schemes in terms of  true positive rates versus false positive rates by testing their classifiers with half matchd profiles and half unmatchd profiles choose at random.  
Even if the schemes are good at separating matchd profiles from random unmatchd profiles, when they have to disambiguate between similar looking profiles their performance could drop drastically as they will have a high number of false positives. 
From a reliability point of view a scheme has to differentiate between cases where it is confident that the most similar profile is the matchd profile and when it is not. Only You et al.~\cite{socialsearch} studied the confidence in the match. However their study scheme only works for people with a notable web presence with entries in EntityCube.  


Contributions: we propose better evaluation schemes for such studies that consider the scale and reliability, we propose a framework for analyzing features used for the matching (ACID), we showed the accuracy of the scheme in the wield, in a real system, considering all the limitations.
Most of the studies do not use a representative set of users, they take users that link to their other profiles.
We measured the consistency of attributes in a sound manner. 
We compare agains humans. We also evaluate how well humans are doing the matching.
\fi

%\minisec{related work conclusions from previous submission}
%\change{
%A number of previous studies exploited the similarity between social network profiles to improve the relevance of search results when searching for people. 
%Although some of these matching approaches are similar to ours, our techniques are better suited to match entire social networks.
%}
%\change{Our work is the first to investigate how to match users profiles in different social networks \emph{at scale}. However, a number of prior studies have investigated techniques  to match users profiles across social networks in different conditions.}
%\change{We extend these studies to a larger set of all major social networks and to a richer set of features which allows us to obtain a much better performance. Our analysis of very large datasets also allows us to demonstrate the feasibility of building matching tools efficient at large scale, thanks to good performance at very small false positive rates. Another originally of our study compared to these prior works is that we demonstrate that classifiers build using a dataset easily crawled from Google+ can be reliably used to match profiles from a more representative population. }

% on Flickr, Twitter and Yelp. While their method is able to link profiles even when the profile attributes in the two profiles are very different, the accuracy of the method makes it unsuitable for large scale matchings. 
%


\section{Conclusion}


\noindent In this paper, we conducted a systematic and detailed
investigation of the reliably of matching user profiles across
real-world online social networks like Twitter and Facebook. Our analysis yielded a number of methodological and measurement contributions.

To understand how profile attributes used by matching schemes affect the overall matching reliability, we proposed a framework that consist of four properties {\it -- Availability, Consistency, Impersonability, and Discriminability (\tname)}. Our analysis showed  that most people maintain the same persona across different social networks -- thus it is possible to match the profiles of many users, however, in practice  there can be a non negligible number of \profiles that belong to different users but have similar attribute values, which leads to false matches.

We showed that the reliability of matching schemes that are trained and tested on reliability non-preserving sampled datasets is not indicative of their reliability in practice.  In fact, traditional matching schemes based on binary classifiers can only achieve a 19\% recall for a 95\% precision  to match Twitter to Facebook profiles in practice.  To avoid these pitfalls we illustrated the right assumptions we can make about the matching problem and the correct methodology to evaluate matching schemes in realistic scenarios.

Finally, we proposed a matching scheme that is able to mitigate impersonation attacks and reduce the number of false matches to achieve a 29\% recall for a 95\% precision. Our matching scheme exploits a special case of the matching problem, namely that there exists at most one matching profile. %, to determine the matching profile (or the lack thereof) from a joint analysis of the potential matching profiles rather than from independent analyzes of all potential matches as all previous works did. 
% by exploiting the uniqueness of attribute values of profiles. 
 %The matching scheme is able to achieve a 29\% recall for a 95\% precision.  
 Although we cannot claim that 29\% is a high recall, humans cannot do much better (they only detect 40\% of matching profiles).

%We find, by analyzing the ACID properties of matched profiles, that only features that have a high discriminability have a significant impact on the precision and recall we can achieve to match profiles in practice. 
%\begin{trivlist}
%%\item $B.$ We made several measurement contributions: ($1$) we measure the potential to match profiles across the most popular social networks; ($2$) we measured how well humans can identify matching profiles; and ($3$) we measure to which extent we can match Twitter to Facebook profiles. 
%
%\item $3$. Our measurements show that only 7\% of users maintain different personas on Twitter and Facebook and that a large majority provide consistent values for public attributes across  different social networks, thus it is possible to match them. However, the recall is limited by the fact that there are also non-matching profiles with consistent attributes. Humans, which are considered a gold standard can match only 58\% of profiles. 
%
%%\item $1$. To achieve high reliability in practice, profile features used for matching must satisfy four important properties -- {\it Availability, Consistency, non-Impersonability,  Discriminability}
%
%%\item $A.$ We showed that the reliability of matching schemes that are trained and tested on reliability non-preserving sampled datasets is not indicative of their reliability in practice. 
%%\item $A.$ We showed that a number of previous studies made some methodological errors: ($1$) Do not evaluate their matching schemes over large-scale social networks. ($2$) Not training well the classifiers and only consider random non-matching profiles rather than hard to guess non-matching profiles.
%
%\item $C.$ We also made several methodological contributions: ($1$) we proposed a better definition for the  matching profiles method with assumptions and constraints that come from real social networks; ($2$) we proposed the ACID framework to analyze the potential of features to match profiles and analyze the reliability of matching schemes; ($3$) proposed a novel method to match profiles when we know for sure that there is at most a matching profile in the second social network; and ($4$) we used a method to gather representative sets of ground truth matching profiles.
%
%
%\item $D.$ We also had some findings: ($1$) there is a fundamental limitation when matching profiles using profile attributes due to the ACID properties profiles have in practice.  We confirm the limitation by asking humans to match profiles. ($2$) at large scale only features that have a high discriminability can contribute to the reliability of the matching scheme. 
%\end{trivlist}


%\begin{enumerate}
%\trivlist
%\item 

%\trivlist
%
%\item $1$. To achieve high reliability at scale, profile features
%  used for matching must satisfy four important
%  properties -- {\it Availability, Consistency, non-Impersonability,
%    Discriminability}
%
%\item $2$. Public attributes of profiles such as name, location, and photos,
%  satisfy these properties to different extents, though none satisfies all
%  properties.
%
%\item $3$. A large majority of users provide consistent values for public
%  attributes across the different social networks we study, which
%  enables cross-site profile matching using only public
%  attributes. Only 7\% of users maintain
%  different personas on Twitter and Facebook.
%
%\item $4$. It is easy to achieve high recall (90\% with high precision (95\%) when attempting to match profiles between datasets containing only a few thousand
%  \profiles.
%
%\item $5$. Nevertheless, maintaining a high recall without compromising precision is a challenge at the scale of today's popular social networks, which contain hundreds of millions of users. %Our scheme is able to match 29\% of profiles between Twitter and  Facebook with 95\% precision. Although we cannot claim that 29\% is a high recall, humans can not do much better (they only detect 40\% of matching profiles).  Humans cannot do much better because of the lack of availability and consistency of profile attributes. However, most of the profiles we cannot match are of users who barely use Twitter, so one can argue that it is not as interesting to match these profiles. 
%
%\item $6$. The primary take-away of our paper is that when evaluating the accuracy of profile matching schemes, between scalability, precision, and recall, we have to pick two of the three.
%
%%\item  6. We achieve this performance thanks to a combination of three learning algorithms with separate training, which better leverages the power of the different features. We believe that this approach can lead to improvements in other applications using learning. 
%
%\endtrivlist

%\change{
%\noindent 7. Even if 21\% does not seem much, we are actually mostly linking profiles that are active, i.e. the ones that is the most advantageus/dangereus from privacy perspective.  Most of the profiles we cannot link are of users who do not really use Twitter, i.e. not really worth linking. }

%\comment{the specific precision and recall for other social networks depends on their ACID properties}

\if 0
\item Achieving high reliability (1\% false positive rate) at
  large-scale, using only public attributes, requires carefully 
\fi

%\end{enumerate}

\if 0
Overall, our findings reflect the potential as well as the limits of
reliably matching profiles at scale. 

\fi
%We implemented a prototype of the matching scheme to match Twitter to Facebook profiles on demand. We deployed the prototype at http://139.19.87.58/. The online service can be used by privacy conscious users to check how well one can detect their profiles in different social networks. 
%We will make available for other researchers the similarity matrices between matching and non-matching profiles we used to train and test our matching schemes. 


\if 0
\oana{
Takeaways for spokeo:
1. names are not so unique, they give a lot of false positives - it is mandatory to exploit other features to match accounts
2. the other features are noisy - we need good algorithms to handle the noisiness
3. do not expect to link everybody, not even humans can link the accounts because of the lack of informaiton
}

\oana{
Takeaways for researchers:
1. matching accounts at large scale poses many challenges
2.  there is room for improvement: algorithms with better scalability, that handle better noisy data and that endure the reliability of the scheme
3.  is it possible to do everything in one step
}
\fi 

\if 0
\comment{even if for some communities this seems logic for other they can fall in the pitfalls}

\comment{there is starting to be a lot of works around the subject of matching profiles across social networks, our contribution is to show that there are many pitfalls that one has to consider to build matching schemes that can be used in the real-world. we show what are the assumptions we can make and what are the methodological mistakes one can make.}

\comment{
\begin{itemize}
\item pitfalls/problems with previous studies: (1) not evaluating over large scale networks; (2) not training well the classifiers
\item  measurement: measure the potential to match accounts across social networks, measure how well humans can match accounts; measure how well we can match twitter to Facebook profiles
\item methodological: (1) define the problem of matching accounts with assumptions and constraints that come from real world scenarios; (2) propose the ACID frameworks to analyze matching schemes and features; (3) novel method to match accounts in particular situation; (4) method to gather ground truth
\item findings: fundamental limitation because of the ACID properties of features - humans can confirm the limitation; at large scale only features with high discriminability count-show properties that features have to have
\end{itemize}
}
\fi

%\subsection{Limitations and Future Work}
%\update{
%Most of the accounts that are not matched by the matching scheme have a low availability and consistency. }
%
%\update{
%We can improve the matching scheme by adding a face recognition algorithm and a bio. However face recognition algorithms are not very accurate when we do not have many photos of the same person to train them, which makes them not very performant when we can only train it with the profile photo. We plan to include the bio. }
%
%\update{
%We also plan to optimize from a computational perspective the \filter by avoiding the need of computing the similarities for the full databases and build an unsupervised method to get similar profiles. }
%
%
%



{%\balance
%\itemsep 0pt
%\parskip 0pt
%\scriptsize{
%\bibliographystyle{IEEEtran}
%\bibliographystyle{IEEEabrv}
%\setlength{\bibsep}{0pt plus 0.3ex}
%\fontsize{8pt}{0pt} \selectfont 
\bibliographystyle{abbrv}
\input{paper-arxiv.bbl}
%\bibliography{paper}
}



\appendix



\section{Proofs from Section~3}
\label{ap:proof}
\subsection{Effective discriminability formula}

\noindent In this section, we justify that, if we assume that the impersonating profiles are independent from the other non-matching profiles, we have $\tilde{D} = D \cdot (p_{nI} + nI \cdot p_{I})$. We first apply the complete probability formula: 
\begin{align}
\nonumber \tilde{D} & \! = \! Pr\Big(\max_{a^{2}: \nonmatch} s(v^{1},v^{2}) <  th\Big) \\ 
\nonumber & \! = \! Pr\Big(\max_{a^{2}: \nonmatch} s(v^{1},v^{2}) <  th  \big| a^{1} \textrm{ not impersonated}\Big) p_{nI} \\ 
\label{eq1} & \! + \! Pr\Big( \! \max_{a^{2}: \nonmatch} \!\! s(v^{1},v^{2}) \! < \! th  \big| a^{1} \textrm{ impersonated}\Big) p_{I}.
\end{align}
Then, we observe that the $\max$ on all non-matching profile is smaller than $th$ iif both the $\max$ on all non-matching profile that are not impersonating $a^{1}$ and the max on the impersonators of $a^{1}$ are smaller than $th$. That is:
\begin{align}
\nonumber & Pr\Big( \max_{a^{2}: \nonmatch}  s(v^{1},v^{2})  < th  \big| a^{1} \textrm{ impersonated}\Big) \\ 
\label{eq2} & = Pr\Big( \max_{a^{2}: \nonmatch \atop \nonimpers } s(v^{1},v^{2}) < th, \\
\nonumber & \;\;\;\;\;\;\;\; \max_{a^{2}: \impers} s(v^{1},v^{2}) < th \Big|  a^{1} \textrm{ impersonated}\Big). 
\end{align}
If the impersonating profiles are independent from the other non-matching profiles, then the joint probability equals the product of probabilities: 
\begin{align*}
& Pr\Big( \max_{a^{2}: \nonmatch}  s(v^{1},v^{2})  < th  \big| a^{1} \textrm{ impersonated}\Big) \\ 
& = Pr\Big( \max_{a^{2}: \nonmatch \atop \nonimpers } s(v^{1},v^{2}) < th \Big|  a^{1} \textrm{ impersonated}\Big) \cdot \\
& \;\;\;\;\;  Pr\Big( \max_{a^{2}: \impers} s(v^{1},v^{2}) < th \big|  a^{1} \textrm{ impersonated}\Big) \\ 
& = D\cdot nI;
\end{align*}
which, given \eqref{eq1}, shows that $\tilde{D} = D \cdot (p_{nI} + nI \cdot p_{I})$. 



\subsection{Proofs of Theorem~1}

\noindent In this section, we give a proof of Theorem~\ref{theorem}. Recall that $th$ is a threshold parameter in $[0, 1]$ such that the classifier declares a match between $a^1$ and $a^2$ if $s(v^{1}, v^{2}) > th$. 

\bigskip

To show \textit{(i)}, first recall the definition of recall: 
\begin{equation*}
recall = Pr \left( s(v^{1}, v^{2}) > th | \match  \right). 
\end{equation*}
Then, we have 
\begin{align*}
recall = & Pr \left( s(v^{1}, v^{2}) > th | \match, v^{1} \textrm{ and } v^{2} \textrm{ available}  \right)\\
 & \cdot Pr (v^{1} \textrm{ and } v^{2} \textrm{ available} | \match)\\
 & +  Pr \left( s(v^{1}, v^{2}) > th | \match, v^{1} \textrm{ or } v^{2} \textrm{ not available}  \right)\\
 & \cdot Pr (v^{1} \textrm{ or } v^{2} \textrm{ not available} | \match).
\end{align*}
By convention, $s(v^{1}, v^{2}) = 0$ if $v^{1} \textrm{ or } v^{2} \textrm{ not available}$ (a pair is never declared a match by the classifier if either value is missing). Therefore, $Pr \left( s(v^{1}, v^{2}) > th | \match, v^{1} \textrm{ or } v^{2} \textrm{ not available}  \right) = 0$ and we have $recall = C\cdot A$ by definition of $C$ and $A$. 


\bigskip


To show \textit{(ii)}, first recall the definition of precision:  
\begin{equation*}
precision = Pr \left( \match | s(v^{1}, v^{2}) >th \right). 
\end{equation*}
To ease the equations reading, we simplify the notation of $\match$ into simply $\matchs$ and similarly for $\nonmatch$. By application of Bayes formula, we compute
\begin{align*}
& precision \\
& =  \frac{Pr (\matchs, s(v^{1}, v^{2}) >th) }{Pr (\matchs, s(v^{1}, v^{2}) >th) + Pr (\nonmatchs, s(v^{1}, v^{2}) >th)}\\
& = \frac{recall \cdot Pr (\matchs)}{recall \cdot Pr (\matchs) + Pr (\nonmatchs, s(v^{1}, v^{2}) >th)}. 
\end{align*}
Let $n_2$ denote the number of profiles in $SN_2$\footnote{Note that $n_2$ includes impersonating profiles and hence formally is a random variable. Rigorously, we should condition on the value of $n_2$ and then take the expectation; however the result would be unchanged hence we omit this detail for a lighter presentation.}. By the assumption of Theorem~\ref{theorem}-\textit{(ii)}, we have $Pr(\matchs) \le 1/n_2$, so that, since $Pr (\nonmatchs, s(v^{1}, v^{2}) >th)\ge 0$, we get
\begin{align*}
precision \le \frac{recall}{recall + n_2 \cdot Pr (\nonmatchs, s(v^{1}, v^{2}) >th)}. 
\end{align*}
Moreover, by definition of $\tilde{D}$, we have 
\begin{equation*}
Pr (\nonmatchs, s(v^{1}, v^{2}) >th) \ge \frac{1-\tilde{D}}{n_2},
\end{equation*}
which gives 
\begin{align*}
precision \le \frac{recall}{recall + 1-\tilde{D}}
\end{align*}
and concludes the proof of Theorem~\ref{theorem}-\textit{(ii)}. 


\bigskip


We now show \textit{(iii)}, by making three observations: 
\begin{trivlist}
\item[a.] First, observe that, from \textit{(i)}, we directly get that $recall=1$ iif $A = C = 1$. 
\item[b.] Second, observe that $precision =1$ iif $\tilde{D}=1$. Indeed, we have $precision = 1$ iif $Pr(\nonmatch, s(v^{1}, s^{2})>th) = 0$, which is equivalent to $Pr(\max_{a^{2}: \nonmatch} s(v^{1},v^{2}) >  th) = 0$ and hence to $\tilde{D}=1$. 
\item[c.] Third, observe that $D = nI = 1$ implies $\tilde{D}=1$ and that, if $p_{I}>0$, the converse holds too. We show the two separately. \\
$(\Rightarrow):$ Assume that $D = nI = 1$. The result follows from the following facts: if $D=1$ then the first term of \eqref{eq1} multiplying $p_{nI}$ is $1$; and from \eqref{eq2}, if $D=1$ and $D=1$ and $nI=1$, then the second term of \eqref{eq1} multiplying $p_{I}$ is $1$. Therefore, $\tilde{D}=1$. \\
$(\Leftarrow):$ Assume that $\tilde{D}=1$ and $p_I>0$. If $D<1$, then both terms of \eqref{eq1} multiplying $p_{nI}$ and $p_I$ are strictly smaller than one which contradicts $\tilde{D}=1$. Therefore $D=1$. If $nI<1$, the second term of \eqref{eq1} multiplying $p_{I}$ is strictly smaller than one which contradicts $\tilde{D}=1$ since $p_I>0$. Therefore $nI=1$.  \\
\end{trivlist}
The combination of these three observations implies Theorem~\ref{theorem}-\textit{(iii)}. (In fact, these three observations give more detailed results on the impact of ACID on precision and recall than what is summarized in Theorem~\ref{theorem}-\textit{(iii)}.)


%First, we assume that $precision = recall = 1$ and show that we have $A=C=nI=D=1$. From \textit{(i)}, if $recall=1$, we clearly have that $A = C = 1$. Assume by contradiction that $D<1$. Then, $\tilde{D}<1$ which implies that we have $Pr(s(v^{1}, v^{2})>th | \nonmatch) >0$ which contradicts $precision = 1$. 







\section{Attribute similarity metrics}
\label{ap:sim}
\vspace{2mm}
\noindent \minisec{Name similarity} Previous work in the record
linkage community showed that the \emph{Jaro string distance} is the
most suitable metric to compare similarity between names both in the
offline and online worlds~\cite{Cohen03acomparison, PeritoCKM11}. So
we use the Jaro distance to measure the similarity between real names
and screen names.

\vspace{2mm}
\noindent \minisec{Photo similarity} Estimating photo similarity is
tricky as the same  photo can come in different formats.  
To measure the similarity of two photos
while accounting for image transformations, we use two matching
techniques: ($i$) \emph{perceptual hashing}, a technique originally
invented for identifying illegal copies of copyrighted content that
works by reducing the image to a transformation-resilient
``fingerprint'' containing its salient characteristics ~\cite{phash}
and ($ii$) {\it SIFT}, a size invariant algorithm that detects local
features in an image and checks if two images are similar by counting
the number of local features that match between two
images~\cite{SIFT}.
% A detailed description of these techniques is out
%of the scope of the paper.
%
We use two different algorithms for robustness. The perceptual
hashing technique does not cope well with some images that are
resized, while the SIFT algorithm does not cope well with computer
generated images. 
%Thus, having two algorithms makes the detection more
%robust.

\vspace{2mm}
\noindent \minisec{Location similarity} For all profiles, we have the
textual representations of the location, like the name of a
city. Since social networks use different formats for this
information,  a simple textual comparison will be inaccurate. Instead, we
convert the location to latitude/longitude coordinates by submitting
them to the Bing API~\cite{BingMaps}.  We then compute the similarity between two locations as the actual geodesic distance between
the corresponding coordinates.

\vspace{2mm}
\noindent \minisec{Friends similarity} The similarity score is the
number of common friends between two profiles. We consider that two
profiles have a common friend if there is a profile with the same
screen name or real name in both friend lists. A more complex but potentially more
accurate method would have been to apply a matching scheme for each friend recursively 
taking other features beside screen name and real name into account. 
As we will see, however, given two small lists of profiles on different social networks, real names and screen 
names alone can accurately identify matching \profiles. Complementary, we could divide the number of common friends by the total number of friends. Preliminary results showed no particular improvement in doing so.




\if 0
\section{Appendix}
\label{sec:appendix}

\subsection{AMT workers descriptions}
\noindent AMT workers where asked to describe in free text the reasons they
think the \profiles are \matching.  They gave some very detailed
descriptions which allowed us to identify a number of attributes
AMT workers found helpful for linking or unlinking \profiles. Table~\ref{tab:amt} shows a
few examples.
There are 6 main attributes AMT workers used to identify \matching
\profiles: if the \emph{names}, \emph{screen names}, \emph{locations},
or \emph{profile photos} are the same on the two \profiles; if it
appears to be the \emph{same person} in the photos and if any
information in their \emph{bio} matches. In some cases AMT workers
went even further and said that form analyzing the posts and photos
they think that the two \profiles show the same \emph{interests} or
that they \emph{link} to the same sites.  Some of these attributes can be verified
automatically with a low effort, such as identifying if two \profiles
have the same name, screen name, location or profile photo. However,
other are much harder to check by machines. For example, it is very easy for humans
to identify that the same person appears in two photos however it is
much more harder for a machine~\cite{Acquisti}. 



\begin{table}[t]
\footnotesize{
\caption{Examples of descriptions AMT workers gave about why they think two profiles belong to the same individual or not.}
\begin{center}
\begin{tabular}{l}
\textsc{Detected Matching (True Matching)} \\
\hline
\parbox[t]{\columnwidth}{$\cdot$ \textsf{same profile picture}}\\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{It is a different picture, but he has the same look on his face, same glasses and same hairdo. }}\\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{He likes the cubs and is a pilot, picture on fb has him with a plane and hes from illinois}} \\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{Names are the same. Twitter references corkscrews as does the facebook profile under "groups". Locations are also the same.}} \\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{Both have the same name, they both have a baseball picture}} \\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{same tweet as post on Facebook.}} \\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{it is an unusual last name and for two people to have the same first name spelled in an uncomventional way and the same last name would be a rare coniciennce to me}} \\
\\
%\hline
%\hline
\textsc{Detected Non-matching (True Matching)} \\
\hline
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{Not a match, one is for music channel, other is for person.}}\\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{different name location information pictures}}\\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{No because they look totally different and have different names.}}\\
 \\
%\hline
%\hline
\textsc{Detected Non-matching (True Non-matching)} \\
\hline
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{Two different photos, names and sex.}}\\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{The Twitter profile appears to be of a woman, The Facebook profile, a man. }}\\

 \\
%\hline
%\hline
\textsc{No Consensus (True Matching and Non-matching)} \\
\hline
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{Other than the name of the profiles there is not enough information on either profile to compare them}}\\
 \parbox[t]{\columnwidth}{$\cdot$ \textsf{twitter profile has no tweets or pictures to help with identifcation}}\\
  \parbox[t]{\columnwidth}{$\cdot$ \textsf{Twitter profile belong to american, facebook to hispanic in guatemala.    }}\\
   \parbox[t]{\columnwidth}{$\cdot$ \textsf{ Twitter account does not provide much information}} \\  
\end{tabular}
\end{center}
\label{tab:amt}
}
\end{table}%





\subsection{Classifiers and missing values}
\label{app:classifiers}
\noindent \textbf{Naive Bayes} decides if two profiles match based on the
probability that each feature's similarity score belongs to the matching class,
assuming that the distribution of feature scores in each class is based on a kernel density estimation.
The Naive Bayes classifier has a natural way of handling missing values of a feature:
during training, feature instances with missing values will not be included in the 
feature-value-class probability computation. During testing, if a particular feature vector has a missing feature value, then that feature will be omitted 
from the prediction calculation. 

\noindent \textbf{Decision Trees} decide if two profiles match by traversing
a tree of questions until they reach a leaf node; the leaf node then specifies
the result. In our setting each node represents a threshold for a given
feature; the classifier tests the input account against that value and takes
the appropriate branch.  The most popular way to handle missing features is at
training time to only create branches on present values, and at testing to take
all the branches of the node representing the feature whose value is missing and then select the class with the highest
frequency among the leafs.  
Decision Trees prove useful for eliminating redundant features, and they allow
to directly interpret results by following the decision process.  The drawback is that the decision boundaries are rough because Decision Trees can only make horizontal and vertical splits.

\noindent \textbf{Logistic Regression} is a linear classifier that bases its
decisions on a linear combination of all the similarity scores of each
feature. Logistic Regression does not have a native way of handling missing
values, so they must be inputted. The most common way is to replace missing values with the median, the mean of all existing feature values or a values that does not exists in the dataset (e.g. -1). We tested both methods and replacing with the median value gives higher accuracy.

\noindent \textbf{SVM} is a large margin classifier that obtains the
decision boundary with the largest distance between matching and non-matching
observations. Boundaries can either be linear or not (kernel). Missing values are inputted in the 
same way as for Logistic Regression. The imputation of missing values with -1 gives the best results.

Figure~\ref{fig:classifiers} presents ROC curves to compare the performance of different classifiers using the Google+ dataset. The Naive Bayes and SVM classifiers (both linear and kernel) perform the best, Logistic Regression is close to the first two while Decision Trees
exhibit the lowest performance for small false positive rates because of its rough decision boundaries to split matches and non-matches. Since Naive
Bayes takes much less time to compute than SVM on our large data set, we use
Naive Bayes for computing all results in this paper.


\begin{figure}[t]
%\vspace{-2mm}
\begin{center}
\includegraphics[width=0.30\textwidth]{plots/ROC_all_classifiers_6_UNCLPM_attributes.eps}
\caption{Comparison of the performance of different classifiers (matching Flickr to Twitter with combination of all features).}
\label{fig:classifiers}
\end{center}
%\vspace{-2.5\baselineskip}
\end{figure}

\if 0
\subsection{Probability to match}
\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
\includegraphics[width=0.30\textwidth,height=3.5cm]{plots/cdf_overall_simialrity_random.eps}
\hfill
%\vspace{-2mm}
\caption{CDFs of the probability of two profiles to be \matching, as returned by the \sysname, for \matching and \nonmatchingprofiles.}
\label{fig:cdf_overall_sim}
\end{center}
%\vspace{-2.5\baselineskip}
\end{figure}

Figure~\ref{fig:cdf_overall_sim} compares the cumulative
distributions of the probability $p$ the classifier returns for
\matchingprofiles and \nonmatchingprofiles (using all the attributes). 

\fi 

\if 0
\subsection{Relative importance of attributes}

\begin{figure}[t]
%\vspace{-8mm}
\begin{center}

\includegraphics[width=0.30\textwidth,height=3.5cm]{plots/ROC_linker_features.eps}
%\vspace{-2mm}
\caption{ROC curves for different combinations of attributes; RN = Real Name, SN = Screen Name, L - Location, P - Photo, F - Friends.}
\label{fig:roc_features}
\end{center}
%\vspace{-2.5\baselineskip}
\end{figure}


\noindent We are interested in understanding the contributions of each
attribute brings to the performance of the classifier.  We use ROC
curves to examine the true positive rate versus the false positive
rate for different combinations of
attributes. Figure~\ref{fig:roc_features} compares the ROC curves for
real name alone and real name in combination with other attributes.
The plot shows that even alone real names discriminate very well
between \matching and \nonmatchingprofiles. When we add screen names
or friends we observe a slight improvement in the true positive
rate. Adding more attributes such as the location and photos, however,
does not improve the true positive rate significantly.
%79\% 84\% name
%87\% 89\% name+username
%89\% 92\% all
For a 1\% FPR, we have a 89\% TPR if we use all the attributes, a 86\%
TPR if we only use real names and screen names and a 79\% TPR if we
only use real names.  There are two reasons why adding more attributes
to the real name and screen name has such a small impact on the true
positive rate: (1) the rest of attributes have a lower availability
and consistency, thus the attribute can actually improve the overall
similarity scores in just a few cases; (2) if the real names and
screen names match, adding more attributes, even if they increase
the overall similarity score, will not increase the true positive
rate. The true positive rate increases only when the points that are
misclassified (i.e, on the wrong part of the decision boundary) are
classified correctly when adding new attributes.
%, however for the points
%that are already well classified (i.e, are in the good part of the
%decision boundary) increasing their similarity when adding more
%features will not result in an increase in the true positive rate.
\fi 
\if 0
Although attributes other than the real names and screen names have
little impact on the true positive rate, we will see in the next
section that other attributes help to get a better confidence in the
match.
\fi



\subsection{Analysis of \psysname}
\label{app:guard}
\noindent We analyze cases when the \psysname is a true match and when it is a false match. We investigate a dataset containing 500 \psysname profiles that are true matches and 500 that are false matches.
Figure~\ref{fig:cdf_matching_vs_nonmatching} confirms our intuitions in~\xref{sec:guard}. It presents the cumulative distributions of attribute
similarity scores between the given Twitter \profile and the \psysname. We show two distributions per plot, one when the \psysname is the \matchingprofile and another it is not. Matching-profiles are in general more similar to the Twitter \profile across the different attributes than \nonmatchingprofiles.  Thus, we can leverage the differences to distinguish the cases when the \psysname is a true match vs. a false match.

\begin{figure}[t]
%\vspace{-8mm}
\begin{center}

%\subfloat[Real name]{\label{fig:hist_n}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-name.random.email.eps}}
\subfloat[Real name]{\label{fig:hist_n}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-name.dis.email.eps}}
\subfloat[Screen name]{\label{fig:hist_u}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-screen-name.dis.email.eps}}

\subfloat[Location]{\label{fig:hist_l}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-locaiton.dis.email.eps}}
\subfloat[Friends]{\label{fig:hist_p}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-friends.dis.email.eps}}

\subfloat[Photo - Phash]{\label{fig:hist_p}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-photo-phash.dis.email.eps}}
\subfloat[Photo - SIFT]{\label{fig:hist_p}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-photo-sift.dis.email.eps}}
%\vspace{-2mm}
\caption{CDF of similarity scores for each attribute when \psysname is the \matchingprofile and when it is not.}
% \todo{the y-axis should be fraction of pairs of \profiles, no? The legend should be correlated vs uncorrelated. same for the next figure. in this figure you could maybe label the x-axis like Real Name Similarity, Screen Name Similarity, etc. Then in the next figure, you can have Overall Similarity. I think it would help make it clear that what you are showing in the two figures are different similarity scores.}}
\label{fig:cdf_matching_vs_nonmatching}
\end{center}
%\vspace{-2.5\baselineskip}
\end{figure}



\begin{figure}[t]
%\vspace{-8mm}
\begin{center}
%\subfloat[\sysname.]{\label{fig:conf_nb_cdf_calib}\includegraphics[width=0.25\textwidth]{plots/sim_confidence.sim-naivebayes-random.random.email.eps}}
\subfloat[Probability to be correlated computed by the \disambiguator .]{\label{fig:conf_nb_cdf_calib}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-naivebayes.dis.email.eps}}
%\subfloat[ROC]{\label{fig:conf_nb_roc_calib}\includegraphics[width=0.20\textwidth]{plots/prediction_rank_1_dis_lr_overallsim.eps}}
\subfloat[Difference between the similarity of the\psysname and the second most similar account.]{\label{fig:conf_dif}\includegraphics[width=0.25\textwidth,height=3cm]{plots/sim_confidence.sim-diff.dis.email.eps}}
\label{fig:cdf_matching_vs_nonmatching_calib}
\end{center}
\caption{CDFs when the \psysname is the \matchingprofile and when it is not.}
%\vspace{-2.5\baselineskip}
\end{figure}

Figure~\ref{fig:conf_nb_cdf_calib} shows the
cumulative distributions of \disambiguator probabilities for
\psysname to be a \matchingprofile. We plot two separate distributions, one when
the \psysname is the \matchingprofile and another when it is not. The graphs show that \disambiguator matching
probabilities are higher when the \psysname is the \matchingprofile than when it is
not. For example, the median probability of a \matchingprofile is 1,
whereas this value is 0.78 for \nonmatchingprofiles.


Figure~\ref{fig:conf_dif} shows the
cumulative distributions of the difference in \sysnameD's
probabilities between the \psysname
and the second most similar \profile. When the \psysname is the \matchingprofile, the median difference to the
second most similar \profile is 12 times more than when the \psysname is not the \matchingprofile.

\if 0

\subsection{Aditional things we can add}
\change{Question: I could add a paragraph that says that we tried to estimate the true positive rate for a false positive rate of $10^{-8}$. --Oana}
\update{A suitable false positive rate for matching entire social networks would be $10^{-9}$, $10^{-8}$. To estimate such low false positive rates we need large amounts of data.  Using the \datasetG we generate $10^9$ \nonmatchingprofiles and use the \sysname to predict whether they are matching or not. For lower false positive rates than $10^{-7}$ the true positive rate drops to zero, i.e there are at least a few \nonmatchingprofiles that have a very high probability to be \matching. Thus, a false positive rate of $10^{-8}$ cannot be achieved by the \sysname. It might be possible to achieve lower false positive rates by using a SVM classifier and optimize its parameters to reduce the number of false positives. To tune the classifier parameters we use cross-validation.  However, since we are working with large amounts of data, building and testing the classifier turned out to take too much time. There might be methods to train and test the classifier only with the points close to the decision boundary however we did not tested such methods. However the task is still very hard because of the missing values problem.}

We obtained similarly performing classifiers even when we
used training data from \datasetG. \change{TODO: Say what is the implication of this? -Oana}
\fi 

\fi
\end{document}



paper-arxiv.bbl
\begin{thebibliography}{10}

\bibitem{BingMaps}
{B}ing {M}aps {API}.
\newblock http://www.microsoft.com/maps/developers/web.aspx.

\bibitem{phash}
Phash.
\newblock http://www.phash.org.

\bibitem{spokeo}
Spokeo.
\newblock http://www.spokeo.com/.

\bibitem{spokeolawsuit}
Spokeo lawsuit.
\newblock http://www.ftc.gov/sites/default/files/documents/
  cases/2012/06/120612spokeocmpt.pdf.

\bibitem{Acquisti}
A.~Acquisti, R.~Gross, and F.~Stutzman.
\newblock Faces of facebook: Privacy in the age of augmented reality.
\newblock In {\em BlackHat}, 2011.

\bibitem{conf/ecml/AkbaniKJ04}
R.~Akbani, S.~Kwek, and N.~Japkowicz.
\newblock Applying support vector machines to imbalanced datasets.
\newblock In {\em ECML}, 2004.

\bibitem{AMT_guidelines}
{Get better results with less effort with Mechanical Turk Masters -- The
  Mechanical Turk blog}.
\newblock http://bit.ly/112GmQI.

\bibitem{balduzzi09osnProfiling}
M.~Balduzzi, C.~Platzer, T.~Holz, E.~Kirda, D.~Balzarotti, and C.~Kruegel.
\newblock Abusing social networks for automated user profiling.
\newblock In {\em RAID}, 2010.

\bibitem{books/daglib/0030287}
P.~Christen.
\newblock {\em Data Matching - Concepts and Techniques for Record Linkage,
  Entity Resolution, and Duplicate Detection.}
\newblock Data-centric systems and applications. Springer, 2012.

\bibitem{Cohen03acomparison}
W.~W. Cohen, P.~Ravikumar, and S.~E. Fienberg.
\newblock A comparison of string distance metrics for name-matching tasks.
\newblock In {\em IIWeb}, 2003.

\bibitem{Goga}
O.~Goga.
\newblock {\em Matching User Accounts Across Online Social Networks: Methods
  and Applications}.
\newblock PhD thesis, UPMC, 2014.

\bibitem{mywww}
O.~Goga, H.~Lei, S.~Parthasarathi, G.~Friedland, R.~Sommer, and R.~Teixeira.
\newblock Exploiting innocuous activity for correlating users across sites.
\newblock In {\em WWW}, 2013.

\bibitem{He:2009:LID:1591901.1592322}
H.~He and E.~A. Garcia.
\newblock Learning from imbalanced data.
\newblock {\em IEEE TKDE}, 2009.

\bibitem{IofciuFAB11}
T.~Iofciu, P.~Fankhauser, F.~Abel, and K.~Bischoff.
\newblock Identifying users across social tagging systems.
\newblock In {\em ICWSM}, 2011.

\bibitem{DBLP:journals/pvldb/KorulaL14}
N.~Korula and S.~Lattanzi.
\newblock An efficient reconciliation algorithm for social networks.
\newblock {\em PVLDB}, 2014.

\bibitem{Kreibich:2009:SIL:1855676.1855680}
C.~Kreibich, C.~Kanich, K.~Levchenko, B.~Enright, G.~M. Voelker, V.~Paxson, and
  S.~Savage.
\newblock Spamcraft: An inside look at spam campaign orchestration.
\newblock In {\em LEET}, 2009.

\bibitem{LabitzkeSebastian}
S.~Labitzke, I.~Taranu, and H.~Hartenstein.
\newblock What your friends tell others about you: Low cost linkability of
  social network profiles.
\newblock In {\em SNA-KDD}, 2011.

\bibitem{Liu:2013:WNU:2433396.2433457}
J.~Liu, F.~Zhang, X.~Song, Y.-I. Song, C.-Y. Lin, and H.-W. Hon.
\newblock What's in a name?: An unsupervised approach to link users across
  communities.
\newblock In {\em WSDM}, 2013.

\bibitem{SIFT}
D.~G. Lowe.
\newblock Distinctive image features from scale-invariant keypoints.
\newblock {\em IJCV}, 2004.

\bibitem{malhotra1}
A.~Malhotra, L.~Totti, W.~Meira, P.~Kumaraguru, and V.~Almeida.
\newblock Studying user footprints in different online social networks.
\newblock In {\em CSOSN}, 2012.

\bibitem{MishariT12}
M.~A. Mishari and G.~Tsudik.
\newblock Exploring linkability of user reviews.
\newblock In {\em ESORICS}, 2012.

\bibitem{Motoyama}
M.~Motoyama and G.~Varghese.
\newblock I seek you: searching and matching individuals in social networks.
\newblock In {\em WIDM}, 2009.

\bibitem{narayanan09osn}
A.~Narayanan and V.~Shmatikov.
\newblock De-anonymizing social networks.
\newblock In {\em IEEE S\&P}, 2009.

\bibitem{northernunsupervised}
C.~T. Northern and M.~L. Nelson.
\newblock An unsupervised approach to discovering and disambiguating social
  media profiles.
\newblock In {\em MDSW}, 2011.

\bibitem{jain:Iseekfbme:2013:wole}
P.~K. Paridhi~Jain and A.~Joshi.
\newblock @i seek 'fb.me': Identifying users across multiple online social
  networks.
\newblock In {\em WoLE}, 2013.

\bibitem{peekyou}
Peekyou.
\newblock http://www.peekyou.com/.

\bibitem{conf/socialcom/PeledFRE13}
O.~Peled, M.~Fire, L.~Rokach, and Y.~Elovici.
\newblock Entity matching in online social networks.
\newblock In {\em SocialCom}, 2013.

\bibitem{PeritoCKM11}
D.~Perito, C.~Castelluccia, M.~Ali~K{\^a}afar, and P.~Manils.
\newblock How unique and traceable are usernames?
\newblock In {\em PETS}, 2011.

\bibitem{5636108}
E.~Raad, R.~Chbeir, and A.~Dipanda.
\newblock User profile matching in social networks.
\newblock In {\em NBiS}, 2010.

\bibitem{salesforce}
R.~Schmid.
\newblock Salesforce service cloud -- featuring activision, 2012.
\newblock http://www.youtube.com/watch?v=eT6iHEdnKQ4\&feature=relmfu.

\bibitem{SocialIntelligence}
{Social Intelligence Corp.}
\newblock http://www.socialintel.com/.

\bibitem{sweeneyMedicalDeanon}
L.~Sweeney.
\newblock Weaving technology and policy together to maintain confidentiality.
\newblock {\em Journal of Law, Medicine, and Ethics}, 1997.

\bibitem{5272173}
J.~Vosecky, D.~Hong, and V.~Shen.
\newblock User identification across multiple social networks.
\newblock In {\em NDT}, 2009.

\bibitem{socialsearch}
G.-w. You, S.-w. Hwang, Z.~Nie, and J.-R. Wen.
\newblock Socialsearch: enhancing entity search with social network matching.
\newblock In {\em EDBT/ICDT}, 2011.

\bibitem{conf/icwsm/ZafaraniL09}
R.~Zafarani and H.~Liu.
\newblock Connecting corresponding identities across communities.
\newblock In {\em ICWSM}, 2009.

\bibitem{Zafarani:2013:CUA:2487575.2487648}
R.~Zafarani and H.~Liu.
\newblock Connecting users across social media sites: A behavioral-modeling
  approach.
\newblock In {\em KDD}, 2013.

\end{thebibliography}
