Density-Matched Surrogate Populations Against Trajectory Recovery from Aggregates

Cities and phone operators often publish mobility data only as aggregates: how many people were in each cell-tower zone or road segment in each hour. This is assumed to be safe, but it is not. An attack has rebuilt individual week-long trajectories from such counts with 73–91% accuracy on 100,000 users, and knowing a recovered trajectory's two most frequent places identifies over 95% of them (Trajectory Recovery From Ash). We borrow one idea from density functional theory (DFT), the standard method in quantum chemistry. DFT replaces an intractable many-particle description with a simple population of independent "stand-in" particles built to reproduce exactly the same particle density. We propose to do the same for mobility. We release a synthetic population of interchangeable walkers whose hour-by-hour density matches a differentially private (DP) version of the real counts. Differential privacy is a formal guarantee that the output barely changes when any one person's data is removed. The walkers' movement rule is fitted only to these noisy counts, so every person-level link the attack exploits is absent by construction. Analysts still get trajectory-shaped data.

The core claim has a diagnostic part and a constructive part. The diagnostic claim is that recovery from aggregates splits into two sources. One is what any population of interchangeable walkers sharing the same density and movement rules would already reveal. The other is the persistence of individuals across days: the same person sleeping in the same place. This split can be measured directly. The constructive claim is that a movement rule fitted to the noisy counts, with an explicit crowding term learned in the style of dynamical density functional theory, recovers usable flows from heavily noised person-level DP counts better than generic smoothing or interaction-free transport. The whole release remains a post-processing of DP counts, so it inherits their formal guarantee.

Why DFT, and what is borrowed

In DFT, the Hohenberg–Kohn theorem says the one-particle density determines the system's external potential. The Kohn–Sham construction then builds non-interacting particles that reproduce that density, with all many-body correlation pushed into one correction term. Its classical, time-dependent version, dynamical DFT, evolves a density by

$$\partial_t \rho(x,t) = \nabla\cdot\big[\Gamma\,\rho(x,t)\,\nabla\,\tfrac{\delta F[\rho]}{\delta\rho(x,t)}\big].$$

Here $\rho(x,t)$ is the density at location $x$ and time $t$, $\Gamma$ is a mobility constant, and $F[\rho]$ is a free-energy functional. $F$ combines an external term (attractiveness of places by time of day) with an excess term $F_{\text{ex}}$ capturing how particles affect each other. Learned Free-Energy Functionals from Pair-Correlation Matching supplies the method for learning $F_{\text{ex}}$ from data in soft-matter systems. We reuse that technique on a road or tower graph, replacing the gradient by graph differences. The excess term then models crowding, such as people avoiding saturated corridors.

The mapping to privacy is direct. Interchangeable walkers carry no identity across time, so the walker population cannot leak cross-day persistence. The Ash attack works through exactly this persistence: it locates nighttime home anchors and links days by information gain. We do not claim a literal Hohenberg–Kohn theorem for humans. We use the construction as an engineering recipe and test empirically where it breaks.

Relation to prior work

Three works motivate the gap. Ash shows that aggregation alone fails but offers no formal defense. It also does not ask how much of its success comes from shared flow structure rather than individual persistence. Not So Unique in the Crowd and There goes Wally show that two to four points single out most people, even under 1-hour and 125 km coarsening. This is why any release that preserves per-person links is fragile.

Two works are the closest constructive neighbors. Private Continuous-Time Synthetic Trajectory Generation via Mean-Field Langevin Dynamics also builds trajectories from per-time snapshots under DP, using entropic optimal transport. Its guarantees assume convex continuous space, it has no interaction term, and it is evaluated on MNIST strokes rather than against re-identification attacks. We work on mobility graphs, add a learned crowding functional, and evaluate against Ash and trajectory-user linking. DP-ANI adapts noise to local road density but treats 1-hour windows independently. It also perturbs origin–destination pairs rather than modeling continuous density flow.

Three works constrain the design. Generative releases such as SynMob and LSTM-TrajGAN produce realistic traces but carry no formal guarantee and train on raw individual trajectories. PateGAIL++ adds DP but needs per-user trajectories in a federated setup. Our pipeline never touches individual trajectories after the counting step.

Research Program

The first component is measurement. We reimplement the Ash attack: nighttime anchors, velocity-bounded Hungarian matching, and cross-day information-gain linking. We run it on real aggregates and on a "shuffled" twin. The twin keeps every hour-to-hour transition count but randomly reassigns identities each day, destroying cross-day persistence while preserving density and one-step flows exactly. The gap in recovery accuracy between the two is the persistence share of the risk. We expect most of the cross-day linking accuracy to vanish on the twin. We also expect within-day matching to survive partly, because velocity constraints remain.

The second component is the release. We count user-level contributions with each user's weekly contribution bounded. We add Gaussian noise calibrated to person-level sensitivity over the whole week, not per hour. This is the regime where noise swamps sparse peripheral cells, the very cells the Wally study finds most identifying. We then fit the external potential and $F_{\text{ex}}$ by minimizing the discrepancy between the evolved density and the noisy counts, with the dynamics acting as a structured denoiser. Finally, we sample interchangeable walkers from the fitted dynamics. Every step after the noisy counts is post-processing, so the $(\epsilon,\delta)$ guarantee holds without further accounting.

The third component is attack and utility evaluation of the released walkers, described below.

Baselines

The naive reference point is the user-level DP counts released as they are. A second naive reference is synthetic trajectories formed by independently assigning walkers to the raw noisy counts hour by hour. Both are run at identical $\epsilon$. If our method cannot beat raw DP counts on utility, the fitted dynamics add nothing.

The first strong competitor is generic denoising: spatio-temporal Gaussian smoothing and low-rank matrix completion applied to the same noisy counts, with walkers generated by entropic transport between smoothed marginals. These get the same hyperparameter search budget, selected on a held-out week.

The strongest structured competitor is the mean-field Langevin approach of Gu et al., adapted to graphs: entropic optimal transport bridges between consecutive DP marginals, without a crowding term. Its only reported number is a 2-Wasserstein distance of 0.023 for digit '9' at $(\epsilon=2,\delta=10^{-3})$ on MNIST strokes. There is no reported result found on Lacuna for it on human mobility or under re-identification attack. We run it at matched $\epsilon$, compute, and tuning budget. Beating it means lower held-out density error and better downstream flow prediction at equal $\epsilon$. Our ablation is the same model with $F_{\text{ex}}=0$, which isolates the learned crowding functional as the key ingredient.

On the privacy side, the reference defenses are as follows. Frequency-based Randomization reports spatial linking accuracy reduced to 1.6% with a frequent-pattern-mining F-measure of 96% on T-Drive. LSTM-TrajGAN reduces trajectory-user linking accuracy from 93.8% to 45.9% on Foursquare NYC. PateGAIL++ reduces membership inference accuracy to about 0.51 on Geolife. A fair win on privacy is linking and recovery accuracy at or below these figures with a formal guarantee they partly lack. On utility, we must match or approach their reported fidelity.

Why not just…?

Why not just release DP counts and stop? This is formally safe, but at person-level sensitivity over a week the noise destroys peripheral cells and short-lived flows. Analysts also cannot run trajectory-based tools on counts. The raw-DP baseline measures exactly how much utility the dynamics restore. If smoothing alone matches us, the DFT component is unnecessary, and we will report that.

Why not just fit a DP Markov chain or optimal-transport bridge between marginals? This is the real threat, because it is the same construction minus the crowding term. The $F_{\text{ex}}=0$ ablation and the adapted Gu et al. baseline settle it directly. Our hypothesis is that crowding matters at rush hours on bottleneck links, where independent-walker transport over-concentrates flow. If the ablation ties our model everywhere, the contribution reduces to the measurement study plus a graph version of mean-field transport, and we will say so.

Why not just train a diffusion or GAN generator under DP-SGD? SynMob reaches over 90% Kolmogorov–Smirnov similarity but has no guarantee. DP generators like PateGAIL++ require per-user trajectories, which aggregate-only publishers do not hold. Where raw traces exist, we include a DP-SGD diffusion model on the synthetic benchmarks as a reference. A win for it at equal $\epsilon$ would narrow our claim to the aggregate-only setting.

Proposed Experiments

The proprietary operator datasets are unavailable, so we use the public sets in the file. We use SYN-CHENGDU and SYN-XI'AN (1M trajectories each) as ground-truth populations at city scale. T-Drive and Geolife supply real persistence structure, and Foursquare NYC supports trajectory-user linking comparisons. We aggregate each dataset to hourly zone counts.

The decisive check for the diagnostic claim is Ash recovery accuracy on real versus shuffled-twin aggregates. Ash reported 73–91% on its private data, and our reimplementation must reach a comparable regime on the real aggregates before the comparison means anything.

The decisive checks for the release are three. First, Ash, trajectory-user linking, and membership inference run against released walkers across $\epsilon\in\{0.1,1,2,8\}$. These attacks should fall to chance, since walkers carry no identities. Their failure to do so would reveal a bug. Second, utility at each $\epsilon$: held-out density error, origin–destination matrix error, trip-length and travel-time distribution distances, and downstream traffic demand prediction error. These follow SynMob's protocol, under which synthetic-trained models stayed within 6% of real-trained ones. Third, the crowding ablation, analyzed separately on bottleneck links at peak hours.

A clear result would be both diagnostic and constructive: persistence accounts for most cross-day recovery, and the crowding term yields measurable utility gains over interaction-free transport at small $\epsilon$. A null result on the ablation is still publishable as a sharp negative finding about how much physics-style structure aggregate mobility can actually use.