TL;DR
This paper demonstrates that publishing aggregated mobility data (like the number of users at a cell tower per hour) does not protect individual privacy as previously assumed. By exploiting the inherent regularity and uniqueness of human movement, the authors developed an unsupervised attack that recovers individual trajectories with 73% to 91% accuracy, even in datasets containing 100,000 users.
What Problem Does This Paper Address?
For years, data owners like cellular operators and app developers have released "aggregated" mobility datasets for research and commercial use. Instead of individual paths, they provide statistics: "At 10:00 AM, 50 people were at Tower A." The prevailing wisdom was that this "statistical mask" preserves privacy because individual records are indistinguishable.
The authors challenge this assumption. They argue that these aggregated counts are like the "ash" of original trajectories—seemingly chaotic, but containing enough structure to be reconstructed. The core problem is that human mobility is not random; it is highly regular (we go to the same places) and highly unique (our set of frequent locations rarely matches anyone else's).
Methods
The authors developed an unsupervised attack framework that requires no prior knowledge of the users. The system works by iteratively linking masked mobility records across time slots using the Hungarian algorithm to solve a Linear Sum Assignment Problem (LSAP). The attack consists of three specialized modules:
- Nighttime Recovery: Leverages the "natural sleeping cycle." Since most users stay in one location at night, the system links records by simply minimizing the physical distance between consecutive time slots.
- Daytime Recovery: Uses a velocity model to predict a user's next location based on their current position and previous displacement: $\hat{l}^{t+1}_i = q^t_i + (q^t_i - q^{t-1}_i)$. It then associates unassigned location points with these predictions by minimizing estimation error.
- Cross-day Recovery: Connects daily sub-trajectories by measuring their similarity. It uses Information Gain based on entropy to determine if two sub-trajectories from different days likely belong to the same person.
Datasets
The study evaluated the attack on two large-scale, real-world datasets collected in a major Chinese city with over 8,000 base stations:
- Operator Dataset: Cellular network records for 100,000 users over one week (average 261 records per user).
- Application Dataset: Mobile app location data for 15,500 users over two weeks (average 496 records per user).
Key Insights and Ideas
-
The Regularity Trap: Human movement is incredibly predictable. As shown in the paper's analysis, users spend the vast majority of their time at just a few locations (home, work). Mobility trajectories of five randomly selected users showing high coherence across two days.
-
Uniqueness as a Fingerprint: Even if a user's path is coarse, it remains unique. The authors found that for the operator dataset, 95% of users can be uniquely distinguished by just their top 5 most visited towers. Percentage of mobility records occurring in a user's most frequently visited towers.
-
The Resolution Paradox: Counter-intuitively, reducing spatial resolution (e.g., grouping towers into districts) actually increased the recovery accuracy (from 73% to 89%). While coarse data makes users slightly less unique, it makes their movement much more predictable, aiding the recovery algorithm.
Key Results
- High Recovery Accuracy: The system successfully recovered 91% of trajectories in the application dataset and 73% in the much larger operator dataset.
- Scalability: The attack remains effective even as the number of users increases. While accuracy drops as the "crowd" gets thicker, the system still achieved ~50% accuracy at a scale of 100,000 users.
- Re-identification Risk: Once a trajectory is recovered, it is highly vulnerable. If an attacker knows just two frequent locations of a victim (like home and work), they can uniquely identify that victim's recovered trajectory with over 95% certainty.
Limitations and Future Work
The primary limitation is computational; the Hungarian algorithm has a complexity of $O(n^3)$, which makes attacking extremely large datasets (millions of users) computationally expensive, though the authors implemented a suboptimal speed-up to mitigate this.
The authors suggest that to truly protect privacy, data owners must move beyond simple aggregation. They propose two directions:
- Generalization: Further coarsening spatiotemporal data to reduce uniqueness.
- Perturbation: Adding noise to the most frequent locations to break the regularity that the attack exploits.
Finally, they raise a chilling question: if mobility trajectories can be recovered from "ash," can other types of human-generated statistical data (like credit card or web browsing aggregates) be similarly compromised? This remains an open area for future research.
Summary updated