PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Reliability of Profile Matching Across Large Online Social Networks

Oana Goga, Patrick Loiseau, Robin Sommer, Renata Teixeira, Krishna P. Gummadi

arXiv:1506.02289v1cs.SI

TL;DR

The paper examines whether public profile attributes can reliably match users across large social networks, where false matches are a concern. It defines ACID properties and evaluates matching schemes under realistic conditions, finding low recall at high precision even with a special-case method.

  • Problem

    The paper asks whether public profile attributes can reliably identify users across social networks, where extreme class imbalance makes false matches a concern.

    Source: §1 · p. 1, §2 · p. 2

  • Method

    The authors define ACID properties, evaluate schemes using reliability-preserving sampling, and propose a method for cases with at most one matching profile.

    Source: §10 · p. 10

  • Results

    Traditional binary classifiers achieved 19% recall at 95% precision, while the proposed at-most-one-match scheme achieved 29% recall at 95% precision.

    Source: §10 · p. 10

  • Takeaways & Limitations

    Similar attributes across different users can cause false matches, and realistic evaluation shows that reliable matching comes with reduced recall.

    Source: §10 · p. 10

    The sampling strategy may overestimate precision because it can omit profiles with similar locations, friends, or photos unless their names or screen names are also similar.

    Source: §5 · p. 6

Abstract

from arXiv · show

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 reliably match profiles in practice, across real-world social networks, by exploiting 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. 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. 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. 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.

1. INTRODUCTION

The paper asks whether publicly available profile attributes can reliably match users across large social networks, where false matches can distort a person’s portrait and have serious consequences. It introduces ACID properties and realistic evaluation methods, finding that practical recall is far below results from small random samples and prior reports.

1. INTRODUCTION

  • Cross-network profile aggregation supports people-search and other services, but matching errors can create inaccurate user portraits with serious consequences.The authors focus on publicly available attributes because data aggregators can crawl and use them.Source: §1 · p. 1
  • The authors identify Availability, Consistency, non-Impersonability, and Discriminability (ACID) as necessary and sufficient properties for determining matching reliability.Their analysis highlights inconsistent user information, similar attributes across different users, and impersonation as practical challenges.Source: §1 · p. 1
  • Small random samples can report over 90% recall and 95% precision, but carefully selected datasets that preserve reliability in larger networks show significantly lower performance.The paper emphasizes evaluation over datasets that reflect real-world matching conditions.Source: §1 · p. 1
  • The study reports only 19% recall at 95% precision; separately, literature’s binary-classifier matching schemes achieved over 90% recall and 95% precision on small random Twitter and Facebook profile samples.Source: §1 · pp. 1–2
  • For cases with at most one matching profile, the proposed scheme reached 29% recall at 95% precision, still below the 90% recall reported in prior literature.The paper reports that AMT workers matched only 40% of profiles under similar conditions.Source: §1 · p. 2

2. PROBLEM DEFINITION

The problem is to find profiles in one social network that belong to the same user as a given profile in another network, using publicly provided attributes. The paper distinguishes individual-profile matching from whole-network matching and evaluates reliability with precision and recall under severe class imbalance.

2. PROBLEM DEFINITION

  • A profile match means two profiles belong to or are managed by the same user; the task is to find all matching profiles in a second network, if any exist.The formulation considers a profile from one network against profiles in another.Source: §2 · p. 2
  • The task matches one profile at a time and excludes using the full first network’s graph structure or other profiles’ match assignments.This differs from matching entire networks or databases and rules out methods that exploit those broader data.Source: §2 · p. 2
  • The paper studies both generic cases, where a profile may have multiple matches, and special cases, where it has at most one match, as in networks enforcing one profile per user.The formulation is motivated by services that gather information about a person across social networks.Source: §2 · p. 2
  • Matching uses similarities in public real names, screen names, locations, profile photos, and friends, which the paper treats as available profile attributes.A feature is the similarity between the attribute values of two profiles.Source: §2 · p. 2
  • Binary-classifier schemes compare profile-pair features and threshold a match probability, while the special case can rank candidate probabilities to select the likeliest profile.The generic approach tests pairs independently; the special-case approach compares candidates for a given profile.Source: §2 · p. 2
  • Because matching profiles are vastly outnumbered by non-matching ones, the paper treats true- and false-positive rates as misleading reliability measures and favors precision and recall.It defines reliability in the rest of the paper as precision higher than 95%.Source: §2 · pp. 2–3

3. THE ACID FRAMEWORK

The ACID framework identifies four attribute properties that determine matching reliability and connects them to classifier precision and recall. It also shows why estimates must reflect the scale of the full network.

3. THE ACID FRAMEWORK

  • Availability requires attribute values in both networks, while consistency requires users to provide the same or similar values across their matching profiles.An attribute available for only 5% of users across two sites has limited matching utility.Source: §3 · p. 3
  • Non-impersonability measures resistance to attribute manipulation; effective discriminability accounts for impersonators and stays close to D when impersonation is rare or attributes resist manipulation.The closeness result assumes impersonating profiles are independent of other non-matching profiles.Source: §3 · p. 3
  • Discriminability measures whether an attribute distinguishes a profile from non-matching profiles; names are likely more discriminating than gender.The framework defines the measure using the highest similarity score among non-matching profiles and a threshold.Source: §3 · p. 3
  • Recall equals C · A; with pI > 0, precision and recall both equal 1 iff A, C, nI, and D all equal 1.The theorem also gives an upper bound on precision as a function of effective discriminability.Source: §3 · p. 3
  • Discriminability depends strongly on network scale, so precision and recall estimates require datasets that capture the full network’s attribute properties.Availability, consistency, and non-impersonability are independent of network scale, unlike discriminability.Source: §3 · p. 3
  • Because attributes satisfy ACID properties to different extents, reliable matching requires combining attributes with imperfect properties.The paper next analyzes ground truth across several large social networks to examine matching limits.Source: §3 · p. 3

4. LIMITS OF MATCHING PROFILES

The section evaluates profile-matching limits by analyzing ACID properties across six social networks, using ground truth from Friend Finder and Google+ datasets. Its findings show that attribute availability and consistency vary, while large-network lookalikes and possible impersonation constrain reliable matching.

4. LIMITS OF MATCHING PROFILES

  • The analysis covers screen name, real name, location, profile photo, and friends across Facebook, Twitter, Google+, LinkedIn, Flickr, and MySpace.The section analyzes each ACID property separately after describing how matching-profile ground truth was gathered.Source: §4 · p. 3

4.1 Ground truth of matching profiles

  • Ground truth came from email-based Friend Finder matches and Google+ users’ self-listed cross-site profiles; the latter may overrepresent users who link and maintain their accounts.The paper presents Friend Finder results by default and uses Google+ occasionally for comparison.Source: §4.1 · p. 4, Table 1 · p. 4

4.2 Attribute availability

  • Screen names and real names were more available than location or friends, though location and friends were available for over 30% of Twitter–Facebook matches.Profile-photo availability in the Friend Finder dataset was 69% for Twitter users versus 96% in Google+; the authors say Google+ users were more likely to complete profiles.Source: §4.2 · p. 4

4.3 Attribute consistency

  • AMT judgments set consistency thresholds so that more than 90% of human-labeled consistent values and less than 10% of inconsistent values had high similarity.The thresholds evaluated attribute consistency; they were not used to match profiles.Source: §4.3 · pp. 4–5
  • 7% of Twitter–Facebook matching profiles had all considered public attributes inconsistent, placing the maximum possible recall at 93%.Consistency also differed by network pair: Twitter–Facebook was among the least consistent, while Facebook–LinkedIn was the most consistent.Source: §4.3 · p. 5

4.4 Attribute discriminability

  • Real names and screen names were highly discriminating in the sample, while location was not; friends were discriminating, and consistent photos rarely appeared among non-matches.For photos, few matching Facebook profiles used the same photo as their Twitter profile, but when photos were consistent, few non-matches had similar photos.Source: §4.4 · p. 5
  • 60% of Twitter profiles had a Facebook profile with exactly the same real name, and 25% had one with exactly the same screen name.Across the entire Facebook network, non-matching profiles could have names more similar than the matching profile, unlike the higher discriminability seen in sampled data.Source: §4.4 · p. 5

4.5 Attribute impersonability

  • 18,662 of 1.4 million random Twitter profiles had another profile with consistent attributes, a rough estimate that 1% could be impersonation victims.The authors note that thoroughly investigating these potential attacks is beyond the paper's scope.Source: §4.5 · p. 5

5. TRAINING & TESTING MATCHING SCHEMES

Because testing against every profile in a large network is impractical, the section develops sampling strategies that better preserve real-world matching reliability. EMULATED-LARGE samples likely false matches, but its estimated precision remains an upper bound because some lookalikes may be missed.

5. TRAINING & TESTING MATCHING SCHEMES

  • Testing each profile against every profile in a large network is impractical, so evaluation must use samples that preserve the original network’s matching reliability.The key is to include potential false matches rather than sample non-matches at random.Source: §5 · p. 6
  • RANDOM-SAMPLED preserves attribute availability and consistency but not discriminability or non-impersonability, so it does not preserve the original network’s precision.It comprises 850 matching Twitter–Facebook profiles expanded into 722,500 pairs.Source: §5 · p. 6
  • EMULATED-LARGE samples Facebook profiles with similar names or screen names; the matching profile appears in the candidate set for 70% of Twitter profiles.The set contains over 270,000 pairs, averaging 320 Facebook profiles with similar names per Twitter profile; missed false matches may have very different names.Source: §5 · p. 6
  • Because the sample may overestimate the discriminability of location, friends, and photos, its precision is an upper bound on precision in practice.The authors believe the sample gives a good estimate because false matches with very dissimilar names are likely rare.Source: §5 · p. 6
  • The dataset omits cases with multiple matching profiles, potentially treating genuine matches as false; it also omits Twitter users without a Facebook match.The authors expect few multiple-profile cases under Facebook’s one-profile policy and test the no-match scenario separately.Source: §5 · p. 6

6. GENERIC MATCHING PROBLEM

The section tests classifier-based matching on random samples and on a reliability-preserving dataset designed to better reflect large-network conditions. Classifiers perform strongly on random samples, but even optimized models achieve low recall at high precision in EMULATED-LARGE.

6.1 Evaluation over RANDOM-SAMPLED

  • Over RANDOM-SAMPLED, LINKER-NB, LINKER-SVM, and LINKER-DT achieve recall above 90% at 95% precision, while LINKER-LR reaches 85% at that precision.The classifiers were tuned using 10-fold cross-validation; Figure 2 presents their precision–recall tradeoffs.Source: §6.1 · p. 7, Figure 2 · p. 7
  • On RANDOM-SAMPLED, missed matches often lack available and consistent attributes, while non-matches with consistent names or friends can be mistaken for matches.Only 20% of missed matches have consistent names, and 53% lack any consistent and available attribute; Table 4 covers attribute availability and consistency across true, missed, and false matches.Source: §6.1 · p. 7, Table 4 · p. 7

6.2 Evaluation over EMULATED-LARGE

  • When models trained on RANDOM-SAMPLED are tested on EMULATED-LARGE, LINKER-NB reaches only 4.5% precision at 23% recall, while LINKER-SVM reaches 95% precision at 15% recall.The best-performing random-sample classifier can be among the worst in practice.Source: §6.2 · p. 7, Figure 2 · p. 7
  • Naive Bayes relies heavily on name similarity, so common names in large networks can generate false matches; SVM considers features jointly to distinguish similar-name pairs.LINKER-NB+ uses a cascade, while LINKER-SVM+ adds negative examples from EMULATED-LARGE to training.Source: §6.2 · p. 8
  • 19% recall at 95% precision: LINKER-SVM+ improves on LINKER-SVM by 4 percentage points in EMULATED-LARGE, yet optimized classifiers still miss many profiles.LINKER-NB+ reaches 23% recall at 88% precision; Figure 2 compares precision–recall tradeoffs across sampled and emulated-large evaluations.Source: Figure 2 · p. 7, §6.2 · p. 8
  • LINKER-SVM+’s precision falls from 95% to 0.02% when recall rises from 19% to 33%, as the added matches need not share friends and false matches multiply.Without friends, the classifiers achieve only 11% recall at 90% precision, underscoring the importance of discriminable features.Source: §6.2 · p. 8

7. SPECIAL MATCHING PROBLEM

For the special case where there is at most one matching profile, the section ranks candidate profiles and uses their relative probabilities to improve matching reliability. GUARD raises recall at high precision, while also limiting false matches when no match exists.

7. SPECIAL MATCHING PROBLEM

  • TOPMATCH returns the highest-probability candidate above a threshold, limiting the output to at most one false match per profile and reaching 26% recall at 95% precision.Its vulnerability to absent matches and impersonating profiles motivates GUARD.Source: §7 · p. 8
  • GUARD reaches 29% recall at 95% precision by evaluating the top two candidate probabilities, improving on TOPMATCH’s 26% recall at that precision.The method uses the first- and second-ranked probabilities to estimate whether TOPMATCH is truly the matching profile.Source: §7 · pp. 8–9
  • GUARD uses the candidate set’s structure to return nothing when attributes are too common, and produced a false match for only 1% of profiles after matching profiles were removed.Half of the returned profiles were false matches; the other half corresponded to impersonators or people with duplicate Facebook profiles.Source: §7 · p. 9

8. EVALUATION AGAINST HUMANS

The authors compare automated matching with human workers choosing among the ten most similar Facebook profiles. Humans perform better than GUARD in one setup, but still do not approach complete recall.

8. EVALUATION AGAINST HUMANS

  • The experiment used 200 held-out Twitter–Facebook matches, presenting each worker with a Twitter profile and links to the ten most similar Facebook profiles.One version omitted the matching profile when it was not in the candidate set; another always included it.Source: §8 · p. 9
  • Workers matched 40% of profiles at 96% precision when the true profile might be absent from the candidate list; even when it was included, they matched only 58%.Three workers assessed each assignment, and the reported result uses majority agreement.Source: §8 · p. 9

9. RELATED WORKS

Prior work proposed profile-matching schemes but often evaluated them with samples and ground truth that do not reflect real-world networks. This paper contrasts public-attribute matching with related approaches and systematically examines false matches.

Matching profiles using private user data

  • Unlike private-data approaches using Friend Finder and email, this work evaluates public attributes accessible without users’ private data.Friend Finder query limits also restrict how many profiles can be matched.Source: §9 · p. 9

Matching profiles using public user data

  • Prior public-attribute studies often used reliability-non-preserving samples, overlooked attribute limits, or relied on biased ground-truth users, making reported reliability overly optimistic.Some studies also assumed identical screen names meant matching, although 20% of same-screen-name Twitter and Facebook profiles were not matches.Source: §9 · p. 9
  • The paper analyzes why profile-matching schemes produce false matches and how they might be eliminated, beyond prior reports that false matches occur.Source: §9 · pp. 9–10

De-anonymizing user identities; Entity matching

  • Related work also covers graph deanonymization and database entity matching; this study assumes no access to the full social graph and notes profile matching has distinct record-access constraints.Source: §9 · p. 10

Matching profiles using public user data

  • Some activity-based schemes use content rather than profile attributes, but their attributes can have low availability or discriminability.Source: §9 · p. 10

10. CONCLUSION

The conclusion presents a framework for analyzing profile attributes and finds that matching reliability in real-world networks is limited. It reports modest recall at high precision, including for the proposed scheme.

10. CONCLUSION

  • The ACID framework analyzes profile attributes through Availability, Consistency, Impersonability, and Discriminability.Source: §10 · p. 10
  • Many people maintain the same persona across social networks, yet distinct users can have similar attributes, producing false matches.Source: §10 · p. 10
  • Traditional binary-classifier schemes achieve only 19% recall at 95% precision for matching Twitter to Facebook profiles in practice.Reliability measured on samples that do not preserve network reliability is not indicative of practice.Source: §10 · p. 10
  • 29% recall at 95% precision is achieved by the proposed scheme, which mitigates impersonation attacks and reduces false matches; humans detect 40% of matching profiles.The scheme exploits the special case in which at most one profile matches.Source: §10 · p. 10

A. PROOFS FROM SECTION 3

The appendix derives effective discriminability while accounting for impersonating profiles. Its formula assumes impersonators are independent of other nonmatching profiles.

A.1 Effective discriminability formula

  • Under independence between impersonating and other nonmatching profiles, effective discriminability is ˜D = D · (pnI + nI · pI).Source: §A.1 · p. 11
  • All nonmatching profiles score below the threshold exactly when both non-impersonating nonmatches and impersonators score below it.Source: §3 · p. 3, §A.1 · p. 11
  • The derivation applies the complete probability formula before combining the two nonmatching-profile groups.Source: §A.1 · p. 11

A.2 Proofs of Theorem 1

The proof relates recall and precision to the matching threshold and attribute properties. It also derives conditions for perfect precision and recall.

A.2 Proofs of Theorem 1

  • The classifier declares a match when profile similarity exceeds threshold th, which lies in [0, 1].Source: §A.2 · p. 11
  • When either profile attribute is unavailable, its similarity is set to zero, so the classifier never declares that pair a match.Source: §A.2 · p. 11
  • Recall equals C · A by the definitions of Consistency and Availability.Source: §A.2 · p. 11
  • Precision equals 1 exactly when no nonmatching profile scores above the threshold, equivalently when effective discriminability is 1.Source: §A.2 · p. 12
  • When pI > 0, effective discriminability equals 1 if and only if D = nI = 1.Source: §A.2 · p. 12

B. ATTRIBUTE SIMILARITY METRICS

The paper defines separate similarity measures for names, photos, locations, and friends, adapting each comparison to the attribute’s representation. Friend similarity counts shared profiles identified by matching real or screen names.

B. ATTRIBUTE SIMILARITY METRICS

  • Name similarity uses Jaro distance to compare real names and screen names, following prior work that found it suitable for both offline and online settings.Source: B. ATTRIBUTE SIMILARITY METRICS · p. 12
  • Photo similarity combines perceptual hashing and SIFT to account for image transformations and improve robustness to their different weaknesses.Perceptual hashing can struggle with some resized images, while SIFT can struggle with computer-generated images.Source: B. ATTRIBUTE SIMILARITY METRICS · p. 12
  • Location similarity converts textual locations to latitude/longitude coordinates and compares them using geodesic distance.The coordinates are obtained through the Bing API.Source: B. ATTRIBUTE SIMILARITY METRICS · p. 12
  • Friend similarity counts common profiles identified by matching real names or screen names across friend lists.Dividing the count by total friends showed no particular improvement in preliminary results.Source: B. ATTRIBUTE SIMILARITY METRICS · p. 12
Loading 1506.02289v1…