Differential Privacy in Aggregated Mobility Networks: Balancing Privacy and Utility

Ammar Haydari, Michael Zhang, Chen‐Nee Chuah, Jane Macfarlane, Sean Peisert

Abstract

Location data is collected from users continuously to understand their mobility patterns. Releasing the user trajectories may compromise user privacy. Therefore, the general practice is to release aggregated location datasets. However, private information may still be inferred from an aggregated version of location trajectories. Differential privacy (DP) protects the query output against inference attacks regardless of background knowledge. This paper presents a differential privacy-based privacy model that protects the user's origins and destinations from being inferred from aggregated mobility datasets. This is achieved by injecting Planar Laplace noise to the user origin and destination GPS points. The noisy GPS points are then transformed into a link representation using a link-matching algorithm. Finally, the link trajectories form an aggregated mobility network. The injected noise level is selected using the Sparse Vector Mechanism. This DP selection mechanism considers the link density of the location and the functional category of the localized links. Compared to the different baseline models, including a k-anonymity method, our differential privacy-based aggregation model offers query responses that are close to the raw data in terms of aggregate statistics at both the network and trajectory-levels with maximum 9% deviation from the baseline in terms of network length.

Introduction

City planners and researchers rely on mobility data—GPS trajectories from phones and vehicles—to optimize infrastructure and manage congestion. However, this data is a privacy minefield. Even when data is "aggregated" (e.g., showing total flows between zones), clever attackers can often re-identify individuals by looking at unique movement patterns or "home-to-work" trajectories.

Traditional privacy methods like k-anonymity often destroy the data's utility for transportation studies. Conversely, "naive" noise injection—simply adding random distance to GPS points—fails in complex urban environments. For example, moving a GPS point just one block might place it on a one-way street going the opposite direction or on the other side of a highway, rendering the resulting "private" trajectory physically impossible or useless for analysis.

The DP-ANI Framework

The authors propose DP-ANI (Differentially Private Adaptive Noise Injection). The framework follows a three-step pipeline designed to balance privacy and geospatial utility.

Overview of the DP-ANI framework pipeline from raw GPS trajectories to a differentially private aggregated road network.
  1. Adaptive Range Selection: Instead of adding the same amount of noise everywhere, the model uses the Sparse Vector Technique (SVT) to privately determine the "bounding range" ($R$) for noise. In dense urban areas with many road segments, a small amount of noise is enough to hide a user among neighbors. In sparse rural areas, more noise is needed. SVT allows the system to pick this range without "leaking" information about the local density itself.
  2. Planar Laplace Noise: The model injects noise into the origin and destination GPS points using a 2D (planar) Laplace distribution. This ensures "geo-indistinguishability," meaning an attacker cannot certainly distinguish a user's actual location from other nearby points.
  3. Network-Aware Link Matching: After adding noise, the "noisy" GPS points are mapped back to the actual road network using a link-matching algorithm. This ensures the resulting trajectories are constrained by geospatial reality (e.g., they stay on actual roads) and maintain the functional category of the road.

Experimental Evaluation

The study evaluated the model using a real-world dataset of fleet and consumer GPS trajectories collected in the San Francisco Bay Area between January and February 2019. The researchers focused on a subset of data from the Berkeley area, specifically looking at 1-hour windows to capture temporal correlations like rush hour patterns.

Key Results

  • High Fidelity: The DP-ANI model resulted in a maximum of 9% deviation in total network length compared to the raw, non-privatized baseline. As shown in the performance analysis, DP-ANI maintains stable network length metrics across various privacy budgets (epsilon values).
Comparison of network length metrics for DP-ANI against various baseline models across different epsilon noise values.
  • Superior to Baselines: It significantly outperformed standard DP methods (which use fixed or worst-case noise) and k-anonymity methods in terms of preserving the statistical characteristics of the network.
  • Link Preservation: At a privacy budget of $\epsilon = 0.1$, the model preserved more than 75% of the original road links in the aggregated output, meaning the "private" map still closely resembles the real traffic flow.
  • Distributional Accuracy: Using the Wasserstein distance metric, the authors showed that the distribution of road types (highways vs. local streets) remained highly consistent after privatization.

Discussion and Future Work

The core insight of this work is that privacy is relative to the environment. A 50-meter error in a crowded city square provides more anonymity than a 50-meter error on a lonely country road. DP-ANI’s ability to adapt the noise level to the local "link density" is what preserves utility. Furthermore, by focusing noise on the most sensitive parts—the origins and destinations—the framework protects user home/work locations while keeping the middle of the trip (the "flow") relatively accurate.

However, limitations remain. In very sparse datasets (e.g., late-night hours), the required noise level can still degrade utility. Future work will explore aggregating data over multiple days to mitigate this and testing the model on larger geographical scales to assess the scalability of adaptive noise injection.

Summary updated

Abstract

Location data is collected from users continuously to understand their mobility patterns. Releasing the user trajectories may compromise user privacy. Therefore, the general practice is to release aggregated location datasets. However, private information may still be inferred from an aggregated version of location trajectories. Differential privacy (DP) protects the query output against inference attacks regardless of background knowledge. This paper presents a differential privacy-based privacy model that protects the user's origins and destinations from being inferred from aggregated mobility datasets. This is achieved by injecting Planar Laplace noise to the user origin and destination GPS points. The noisy GPS points are then transformed into a link representation using a link-matching algorithm. Finally, the link trajectories form an aggregated mobility network. The injected noise level is selected using the Sparse Vector Mechanism. This DP selection mechanism considers the link density of the location and the functional category of the localized links. Compared to the different baseline models, including a k-anonymity method, our differential privacy-based aggregation model offers query responses that are close to the raw data in terms of aggregate statistics at both the network and trajectory-levels with maximum 9% deviation from the baseline in terms of network length.
BibTeX
@misc{haydari2021differential,
  author = {Ammar Haydari and Michael Zhang and Chen‐Nee Chuah and Jane Macfarlane and Sean Peisert},
  title = {{Differential Privacy in Aggregated Mobility Networks: Balancing Privacy and Utility}},
  year = {2021},
  eprint = {2112.08487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.08487},
}
Figure