PaperlayerView exact revision on arXiv

Source-linked AI summary

Where You Are Is Who You Are: User Identification by Matching Statistics

Farid M. Naini, Jayakrishnan Unnikrishnan, Patrick Thiran, Martin Vetterli

arXiv:1512.02896v1cs.LGcs.CRcs.SIstat.APstat.ML

TL;DR

The paper asks whether users can be identified from histograms when identities are hidden in one dataset and known in another. It evaluates a matching approach across datasets and scenarios, finding that histograms can fingerprint users and that simultaneous matching outperforms one-by-one matching. The optimal method also achieves higher accuracy than heuristic approaches in the reported practical scenarios.

  • Problem

    The paper studies whether users can be identified by matching behavioral histograms across datasets when identities are hidden in one dataset, a risk relevant to anonymized releases correlated with auxiliary information.

    Source: §I · p. 1

  • Method

    It evaluates a hypothesis-testing-based minimum-weight maximal matching method for linking user histograms across independent datasets.

    Source: C. Optimal solution via hypothesis… · p. 6

  • Results

    Across three diverse datasets, the algorithm outperforms heuristic methods, and simultaneous matching yields higher accuracy than one-by-one matching.

    Source: §VI · p. 14

  • Takeaways & Limitations

    User histograms can act as fingerprints, and the optimal method’s accuracy quantifies the maximum user-identification level possible in these settings.

    Source: §VI · pp. 13–14

    The proposed approach is justified when users’ habits follow stationary and ergodic probability laws across datasets.

    Source: C. Optimal solution via hypothesis… · p. 6

Abstract

from arXiv · show

Most users of online services have unique behavioral or usage patterns. These behavioral patterns can be exploited to identify and track users by using only the observed patterns in the behavior. We study the task of identifying users from statistics of their behavioral patterns. Specifically, we focus on the setting in which we are given histograms of users' data collected during two different experiments. We assume that, in the first dataset, the users' identities are anonymized or hidden and that, in the second dataset, their identities are known. We study the task of identifying the users by matching the histograms of their data in the first dataset with the histograms from the second dataset. In recent works, the optimal algorithm for this user identification task is introduced. In this paper, we evaluate the effectiveness of this method on three different types of datasets and in multiple scenarios. Using datasets such as call data records, web browsing histories, and GPS trajectories, we show that a large fraction of users can be easily identified given only histograms of their data; hence these histograms can act as users' fingerprints. We also verify that simultaneous identification of users achieves better performance compared to one-by-one user identification. We show that using the optimal method for identification gives higher identification accuracy than heuristics-based approaches in practical scenarios. The accuracy obtained under this optimal method can thus be used to quantify the maximum level of user identification that is possible in such settings. We show that the key factors affecting the accuracy of the optimal identification algorithm are the duration of the data collection, the number of users in the anonymized dataset, and the resolution of the dataset. We analyze the effectiveness of k-anonymization in resisting user identification attacks on these datasets.

I. INTRODUCTION

User matching links information about the same people across datasets when identities are hidden, including anonymized releases that may be re-identified using auxiliary information. This paper studies matching user histograms across independent experiments and frames the task as simultaneous row matching.

I. INTRODUCTION

  • When identities are hidden in one or both datasets, matching information about the same users across sources becomes non-trivial.Examples include location statistics from different periods or phone records matched to credit-card patterns.Source: §I · p. 1
  • Matching users across datasets can increase the information available about them, supporting more targeted advertisements and recommendations.Source: §I · p. 1
  • An adversary can compromise anonymized data by correlating it with auxiliary information, making de-anonymization essentially a matching task.The paper cites movie ratings matched with public IMDB reviews as an example.Source: §I · p. 1

OBJECTIVE OF THE ADVERSARY IS TO MATCH THE USERS (I.E., ROWS)

  • The paper studies matching anonymized and labeled histograms from independent experiments by identifying corresponding user rows.User habits may make the histograms similar across datasets, though behavioral randomness means they need not be identical.Source: OBJECTIVE OF THE ADVERSARY IS TO MATCH… · p. 2

II. RELATED WORK AND CONTRIBUTIONS

This work places histogram matching alongside entity resolution, de-anonymization, and supervised classification, while distinguishing its focus on time-averaged statistics and simultaneous one-to-one assignment.

A. Entity resolution

  • Unlike entity-resolution approaches often built from heuristics, this method is tailored to histogram-only information and is optimal for minimizing misclassification probability.Source: A. Entity resolution · p. 2

B. De-anonymization attacks

  • Unlike many de-anonymization studies that exploit temporal sparsity or patterns, this work uses only time-averaged histograms, which generally makes matching more difficult.The two datasets are assumed statistically independent; matching exploits stationary and ergodic user habits.Source: B. De-anonymization attacks · p. 3
  • The paper’s simultaneous matching uses information from all users together rather than matching one user at a time.Source: B. De-anonymization attacks · p. 3

C. Supervised learning

  • Unlike ordinary supervised classification, histogram matching simultaneously assigns test histograms to distinct classes, imposing a one-to-one constraint.The paper interprets its approach as constrained classification,.Source: C. Supervised learning · p. 3, Figure 1 · p. 3

D. Contributions

The paper evaluates histogram-based user identification and its matching algorithm, then formalizes the task using two datasets of per-user histograms. Its setup assumes user-specific probability laws and independent histograms across users and datasets.

D. Contributions

  • Behavioral statistics can fingerprint users, and histogram-only identification can sometimes exceed the accuracy of more complicated models such as Markov chains.Source: D. Contributions · p. 3
  • The paper evaluates a provably optimal histogram-matching algorithm on three diverse datasets and reports that it outperforms heuristic methods.It also examines distinct user sets, simultaneous matching, privacy mechanisms, and factors including user configuration and data resolution.Source: D. Contributions · p. 4

A. Problem statement

  • Each user has an unknown, unique probability law, and the task is to match that user across two datasets containing only histograms.The formulation defines each histogram as the empirical distribution of a data string and assumes distinct users’ histograms and each user’s cross-dataset histograms are independent.Source: §III · p. 4, A. Problem statement · p. 4
  • The basic problem represents the true cross-dataset matching with an unknown permutation that the adversary must estimate.Source: A. Problem statement · p. 4

B. Potential approach: Weighted bipartite matching

Histogram matching is formulated as an assignment problem on a weighted bipartite graph. Edge weights can encode histogram distances or similarities, with the matching chosen to minimize or maximize total weight accordingly.

B. Potential approach: Weighted bipartite matching

  • Under stationary user-histogram matching, each complete-graph matching pairs histograms across the two sets, and the green edges illustrate the correct permutation among N! possibilities.Each graph part represents one set of histograms; a matching cannot reuse a vertex.Source: B. Potential approach: Weighted… · pp. 4–5, Figure 2 · p. 5
  • Assigning each edge its histograms’ distance makes a minimum-weight maximal matching minimize total pairwise distance as an estimate of the correct matching.The distance measure can be chosen for the edge weights.Source: B. Potential approach: Weighted… · p. 5
  • Using the dot product as a similarity weight instead leads to a maximum-weight matching; the authors introduce another weight choice in the next subsection.Source: B. Potential approach: Weighted… · p. 5

C. Optimal solution via hypothesis testing interpretation

The paper interprets histogram matching as multi-hypothesis testing and connects its decision rule to minimum-weight bipartite matching. It uses a generalized-likelihood derivation to motivate the weight metric and reports that it outperforms several heuristic alternatives under the tested settings.

C. Optimal solution via hypothesis testing interpretation

  • With i.i.d.-generated user data, the matching is an N!-hypothesis test whose minimum-weight maximal matching with weights (7) achieves an optimal trade-off between error probabilities.Each hypothesis corresponds to a permutation of the users.Source: C. Optimal solution via hypothesis… · pp. 5–6
  • The weight in (7) ranges from 0 for identical histograms to 2 log(2) for disjoint support, and the stated optimality analysis is asymptotic as string length T increases.The maximum applies when the histograms have no bin with positive values in both.Source: C. Optimal solution via hypothesis… · p. 5
  • Because user distributions are unknown, the method maximizes generalized likelihood over possible distributions for each hypothesis and reduces the decision to minimizing a divergence-based matching cost.The derivation uses empirical distributions as maximum-likelihood estimates and removes a hypothesis-independent entropy term.Source: C. Optimal solution via hypothesis… · pp. 5–6
  • The weight metric (7) gives higher matching accuracy than (4), (5), and (6) under various settings, although its optimality result was established for i.i.d. processes.The authors argue the solution remains reasonable when user habits follow stationary and ergodic probability laws.Source: C. Optimal solution via hypothesis… · p. 6

D. Generalization to different sets of distinct users

The matching framework is extended to datasets containing different user sets, including cases where only some users overlap. The appropriate matching depends on the overlap and whether its size is known.

D. Generalization to different sets of distinct users

  • When the datasets contain different user sets, the task includes identifying their intersection as well as matching the shared users; the formulation assumes distinct user probability laws and N′ > N.N and N′ count the histograms in the unlabeled and labeled sets, respectively.Source: D. Generalization to different sets of… · p. 6
  • If every unlabeled histogram has a labeled counterpart but not vice versa, the method matches all N unlabeled histograms to N of the N′ labeled ones using a minimum-weight maximal matching.Source: D. Generalization to different sets of… · p. 6
  • For a known overlap r < N, a minimum-cost imperfect matching selects r pairs with minimum total distance; matching min{N, N′} users when r is unknown yields a larger fraction of incorrect matches.Source: D. Generalization to different sets of… · p. 6

E. Algorithms and complexity

The section maps user-overlap scenarios to weighted bipartite matching algorithms, then describes their computational costs and scalability trade-offs. Experiments compare matching weights across three datasets.

E. Algorithms and complexity

IV. EXPERIMENTAL EVALUATIONS

  • The evaluation constructs user histograms from non-overlapping periods, matches them on complete bipartite graphs, and measures the share of common users correctly matched.Source: §IV · p. 7

1) Dataset description and preprocessing:

WITH VARIOUS CHOICES FOR THE DISTANCE/SIMILARITY MEASURES

2) Matching accuracy with different metrics:

The proposed edge-weight method outperforms heuristic measures in user matching, while accuracy varies with dataset size and matching setup. Simultaneous matching can yield higher percentage accuracy than matching only a known number of shared users.

2) Matching accuracy with different metrics:

  • 21.1% accuracy matched 9,927 of 46,986 users from call histograms collected over two consecutive weeks.The proposed weight function significantly outperformed the other heuristic measures.Source: 2) Matching accuracy with different… · p. 8
  • The proposed weight function significantly outperformed heuristic measures; random matching yielded 0.002% accuracy.A random matching produced one correctly matched user on average.Source: 2) Matching accuracy with different… · p. 8

3) Effect of varying the number N of users:

  • Accuracy decreased as the number of users increased, reaching 78% for 1,000 users compared with 21.1% for 46,986 users.The experiment varied the number of users while matching the same set across both weeks.Source: 3) Effect of varying the number N of… · p. 8

4) Matching different subsets of users:

  • With all second-week users but only a first-week subset, accuracy increased with subset size; one-by-one matching had the lowest accuracy.When only 3,750 of 5,000 users were shared, matching those users yielded 36% accuracy versus 33% when matching all 5,000.Source: 4) Matching different subsets of users · pp. 8–9, Figure 6 · p. 9

5) Effect of varying the time-duration of data collection:

Matching accuracy increased with longer data-collection durations under the stated stationarity and ergodicity condition. It was also lower with aggregated locations than with antenna-level data.

5) Effect of varying the time-duration of data collection:

  • Matching accuracy increased as more days of user statistics were included, and the proposed weight function outperformed the heuristic measures.The explanation is conditional: with stationary and ergodic user habits, longer collection makes each user's histograms more similar across periods.Source: TO THE SECOND APPROACH, THE FIRST… · p. 9, Figure 7 · p. 9

TO THE SECOND APPROACH, THE FIRST APPROACH YIELDS A SMALLER

  • The Mon-to-Mon-Tue accuracy gain was smaller than gains at other plotted points, possibly because April 9 was a public holiday.Users made an average of 1.9 calls on Tuesday, compared with 7.2 calls per day on average.Source: TO THE SECOND APPROACH, THE FIRST… · p. 10

6) Effect of location aggregation:

  • Location aggregation reduced accuracy to 4.40% (2,070 users) from 21.1% with the original high-resolution dataset.The study used sub-prefectures rather than individual antennas; the authors attribute the drop to less distinguishable histograms.Source: 6) Effect of location aggregation · p. 10

B. Experiments on web browsing history (WBH) dataset

The WBH experiment matched users from weekly website-visit histograms, with the proposed edge weight outperforming heuristic measures. Even a restricted set of popular websites retained substantial matching accuracy.

1) Dataset description and preprocessing:

  • The two-week WBH sample contained 121 active users and 83,219 websites; website visits were represented as per-user weekly histograms.Timing information was disregarded, and favicon identifiers were used to group URLs by website.Source: 1) Dataset description and preprocessing · p. 10

2) Matching accuracy with different metrics:

3) Considering popular websites:

C. Experiments on GeoLife (GL) GPS dataset

GeoLife experiments test histogram matching on GPS traces from central Beijing, comparing metrics, spatial resolutions, and a prior de-anonymization approach. Accuracy peaks at moderate grid sizes, and the proposed method outperforms the reported prior result even when matching users one by one.

1) Dataset description and preprocessing:

  • The study uses 154 users with more than one active week, averaging 15.4 active weeks, and grids the Beijing area within the 5th ring road into 100 m squares.An active week has at least one recorded GPS position; user trajectories are split into first and second halves of their active weeks to form histograms.Source: 1) Dataset description and preprocessing · p. 11, Figure 10 · p. 11

2) Matching accuracy with different metrics:

3) Effect of spatial resolution:

4) Comparison with existing work:

  • 60% accuracy for 154 users was achieved with 300–1000 m grids, versus up to 45% for 77 users in; one-by-one matching reached 50%.The authors attribute the comparison partly to potential overfitting in the more complex Mobility Markov Chain model.Source: 4) Comparison with existing work · p. 12

D. Running time

  • For GeoLife, computing edge weights took 0.9 seconds and running (A1) took 0.2 seconds, excluding histogram preprocessing.Source: D. Running time · p. 12

V. PRIVACY ENHANCING MECHANISMS

The paper considers histogram coarsening, data suppression, and k-anonymization as privacy-enhancing mechanisms. Micro-aggregation guarantees k-anonymity by replacing each user's histogram with its cluster average, trading information loss against user-level matching accuracy.

A. Basic data coarsening and data suppression

  • Coarsening and suppression make released histograms more similar or restrict the released data, while k-anonymization is examined as another privacy mechanism.Examples include aggregating locations, limiting websites, and restricting the time period used to compute histograms.Source: §V · p. 12, A. Basic data coarsening and data… · p. 12

1) Micro-aggregation:

2) Experimental evaluations:

The experiments assess micro-aggregation's effects on matching at user and cluster levels across three datasets. As k increases, user-level accuracy drops while cluster-level accuracy changes little; the conclusion is that histogram matching can identify users and privacy enhancement may leave nonnegligible accuracy under moderate distortion.

2) Experimental evaluations:

  • The evaluation matches micro-aggregated unlabeled histograms against labeled histograms, distinguishing correct user matches from correct cluster matches.The three datasets use dataset-specific settings, including 1,000 sampled CDR users, the top 100 WBH websites, and 1,000 m GL grids.Source: 2) Experimental evaluations · p. 13
  • As k rises to about 10, user-level accuracy drops dramatically while cluster-level accuracy remains almost unchanged across the CDR, WBH, and GL datasets.Figure 12 compares both accuracy measures with normalized information loss and the normalized number of clusters.Source: 2) Experimental evaluations · p. 13, Figure 12 · p. 13

VI. CONCLUSION

  • The authors conclude that behavioral histograms can act as fingerprints that identify users across anonymized and independent datasets.Source: §VI · p. 13
  • Across three datasets, the proposed optimal matching method exceeds heuristic-based accuracy, and simultaneous matching outperforms one-by-one matching.The conclusion also reports that k-anonymization and data obfuscation reduce identification accuracy, but it remains nonnegligible under moderate distortion.Source: §VI · p. 14
Loading 1512.02896v1…