Elastic Session Privacy: Protecting Listening Histories Without Pushing Niche Users Toward the Mainstream

Session-based recommenders, which suggest the next song or product from a user's short recent history, usually require the user to send that raw history to a server. A listening session can be very revealing. This is especially true for people with niche taste, because a sequence of rarely played tracks can come close to identifying a person. The simplest privacy fix is local noise: the phone sends a perturbed or substituted session instead of the real one. That fix has a hidden cost. A substitute drawn from "nearby" sessions will tend to be more mainstream than the original, because mainstream sessions are where the data is dense. Privacy noise therefore quietly amplifies popularity bias, the tendency of recommenders to over-serve popular items, and it hurts most the users who are hardest to protect.

We propose a local privacy mechanism that addresses both problems. The mechanism is built on the elastic metric idea from location privacy. In Constructing elastic distinguishability metrics for location privacy, the distance used to calibrate location noise is stretched in sparse areas and compressed in dense ones. We transfer that construction from map coordinates to listening sessions. Similarity between sessions is measured with dynamic time warping (DTW, an alignment algorithm that compares two sequences while allowing one to locally speed up or slow down relative to the other). Density is measured by how many public sessions lie nearby. A user then receives exactly as much obfuscation as their local neighborhood requires. A mainstream session gets a near-identical substitute. A niche session gets a substitute chosen from a wider but still structurally similar region, rather than being collapsed toward the popular center.

Core Claim

Uniform-noise local privacy for session recommenders worsens popularity bias in a measurable way that depends on the user's taste profile. Measuring session closeness with DTW, and stretching the privacy metric according to local session density, recovers most of the lost tail utility at the same empirical re-identification risk. The two ingredients address different failures. DTW keeps substitutes behaviorally faithful when sessions differ in length, repeats, or pacing. Elasticity keeps niche users from being either unprotected or flattened toward head items.

To our knowledge, no prior work has measured whether local privacy noise on sessions shifts recommendations toward head items. The first experiment is designed to test that premise, and the rest of the program depends on its outcome.

Relation to Prior Work

The method is borrowed from location privacy. Palamidessi et al. build a proper metric by taking shortest paths over a graph of 560,000 locations, with edge lengths scaled by OpenStreetMap "privacy mass." They then use that metric in a distance-based privacy guarantee. They report that the uniform Planar Laplace mechanism added 50% more noise than necessary in roughly 10% of central-Paris locations, while under-protecting sparse suburbs. They explicitly leave temporal sequences to future work. We reuse their shortest-path construction almost unchanged. What is new is the space it operates on (sessions rather than places) and the source of mass (session density rather than buildings).

That construction also solves a technical problem. DTW is not a metric, because it violates the triangle inequality, and the privacy guarantee needs one. Shortest-path closure over a DTW-weighted graph turns DTW into a valid metric.

The use of DTW to factor out pacing is established in behavioral profiling. Kang et al. show that it groups household routines that are shifted in time. Decomposing Activities of Daily Living to Discover Routine Clusters combines it with factorization to find routine personas. We apply the same reasoning to listening sessions, which differ in length and in how often items are replayed.

The popularity-bias work motivates the problem and supplies the server side. Long-Tail Session-based Recommendation from Calibration (CSBR) shows that tail appetite varies by session. It matches the popularity mix of recommendations to the session's own mix and reports an 18.83% increase in recommended tail items on Last.fm. That design creates our concern: if the session the server sees has already been made more mainstream by noise, calibration faithfully calibrates to the wrong target. CSBR assumes the server sees raw sessions. We do not.

Fairness Through Domain Awareness (BOOST) regularizes against static acoustic descriptors and has no privacy component. It also reports Flow = 0.999 on Last.fm, a saturated coherence score. That is a warning against relying on it to detect subtle quality loss.

The perceptual-objective literature acts as an evaluation constraint. ViSQOL v3, SongEval, and CMI-RewardBench all document cases where objective scores and human judgment diverge. CMI-RewardBench additionally notes that learned judges favor mainstream genres. We therefore do not trust hit-rate alone to say whether niche users were served well, and we add a small human check.

Research Program

The system has three parts.

Public session pool and graph. First, we build a public pool of sessions from an earlier time period or from consenting donors. We embed each item with a model trained only on that public data. We connect each pool session to its $k$ nearest neighbors, with edge length given by DTW over the item-embedding sequences under a Sakoe-Chiba band. The band is a limit on how far the alignment may drift from the diagonal. It prevents degenerate alignments and keeps cost manageable for short sessions.

Elastic edge scaling. Following Palamidessi et al., we rescale edge lengths so that the ball of radius $r$ around any session contains at least $M$ pool sessions. The result is that sparse, tail-heavy regions are stretched and dense mainstream regions are compressed. The privacy metric $d(s,s')$ is then the shortest-path distance on this rescaled graph.

Release. Next, the user's device maps the true session $s$ into the graph. Mapping uses DTW to the nearest pool nodes; the true session is never added to the pool. The device then releases a substitute $s'$ drawn with probability

$$ P(s' \mid s) \propto \exp\big(-\epsilon\, d(s, s')\big), $$

where $\epsilon$ is the privacy parameter. This construction gives the standard distance-based guarantee: the likelihood ratio of any output under two true sessions $s_1, s_2$ is at most $e^{\epsilon\, d(s_1,s_2)}$.

Client-side correction. The server runs a session recommender, such as NARM or SR-GNN with or without CSBR's calibration module, on $s'$ and returns a candidate list. The device re-ranks that list against the true session's tail ratio, again with a KL calibration term. This step uses only private local information and costs nothing in privacy.

Analysis. The analysis has three steps. First, we quantify how much each mechanism shifts recommended popularity, stratified by user tail appetite. Second, we measure re-identification risk empirically. The adversary holds the full public pool plus a linkage database of other sessions from each user and must link a released substitute to its user. Third, we trace utility–risk curves rather than comparing at a nominal $\epsilon$, because $\epsilon$ means different things under different metrics.

Baselines

Upper reference (no privacy). The server receives raw sessions and runs CSBR. CSBR is the strongest published method for tail-aware session recommendation in this file. It reports +18.83% recommended tail items on Last.fm, and on YOOCHOOSE +14.01% TailCoverage@20 and +4.67% Tail@20 over its best baseline. We will retrain it with its two-stage curriculum on our splits so that all comparisons use the same backbone, data, and tuning budget.

Naive private reference. Each item in the session is replaced by a uniformly random item with fixed probability (randomized response), calibrated to the same empirical re-identification rate as our method.

Strongest competitor (uniform metric privacy). This is the direct analog of Planar Laplace: the same exponential release, using Euclidean distance between mean-pooled session embeddings with no elastic scaling. No result is reported on Lacuna for any local privacy mechanism on session recommendation. Its strength therefore has to be established in our own runs.

Ablations. Two ablations isolate the two ingredients. "DTW, no elasticity" uses the shortest-path metric over raw DTW edges. "Elastic, no DTW" uses rescaled edges built from mean-pooled Euclidean distances. Every mechanism gets the same pool, the same server model, and an equal hyperparameter search over $k$, $M$, the band width, and $\epsilon$.

What beating them means. Our method must do two things at matched adversarial linkage accuracy. It must achieve higher Tail@20 and TailCoverage@20 for the top tail-appetite tercile of users. It must also show no more than a small, pre-registered drop in HR@20 for head-appetite users compared with the uniform competitor.

Why not just…?

Why not just train the recommender with DP-SGD instead? DP-SGD (differentially private gradient descent) protects the trained model against leaking training data. It does nothing about the server observing each user's raw session at query time, which is the exposure we target. These are different threat models. We will report DP-SGD only as a complementary layer, not as a competitor.

Why not just use Euclidean distance on mean-pooled session embeddings? This is the most serious threat, because mean pooling is cheap and may already capture taste. The "elastic, no DTW" ablation tests it directly. If that ablation matches the full method, we will report that DTW is unnecessary and keep only the elastic construction. Our expectation that DTW matters rests on its documented advantage when sequences differ in pacing and length (Kang et al.). Sessions with heavy replay are where we predict the gap will show. We will stratify results by replay rate to check that prediction.

Why not just apply uniform noise and let CSBR's calibration fix the popularity skew? CSBR calibrates to the popularity ratio of the session it sees. If noise has already made that session more mainstream, calibration locks in the error. The "uniform metric + CSBR" arm tests this directly. A finding that it closes the tail gap would undercut the core claim, and we would report it as such.

Why not just add more noise to everyone, so tail users are protected too? The location-privacy evidence argues against this. A uniform mechanism tuned for sparse regions over-perturbs dense ones by large margins (Palamidessi et al.). We will show the session analog on the utility–risk curve: head-user HR@20 at the noise level a uniform mechanism needs to match our tail-user linkage risk.

Proposed Experiments

We use Last.fm and YOOCHOOSE following the CSBR protocol, plus the Million Playlist Dataset as a music benchmark with richer item metadata. On all three, we split time so that the public pool strictly precedes the evaluation sessions.

Premise test. The first and decisive check asks whether uniform metric privacy reduces Tail@20 for high-tail-appetite users by more than it reduces it for head users, at matched linkage risk. If it does not, the popularity-amplification premise fails and the program should stop there.

Main comparison. The second check compares utility–risk curves across all baselines and ablations. Metrics are HR@20, MRR@20, Tail@20, and TailCoverage@20, together with adversarial linkage accuracy, stratified by tail-appetite tercile and by replay rate.

Client-side re-ranking. The third check measures how much of the remaining gap the local re-ranking step recovers.

Human check. Because offline metrics are known to diverge from perceived quality, and BOOST's Flow already saturates at 0.999, we will run a modest blind study on MPD tracks. Listeners hear a session's last tracks via previews and rate how well each recommendation list fits the session. We will test whether differences in offline Tail@20 and HR@20 between mechanisms predict listener preference among niche users. If they do not, our conclusions rest on the human judgments, and we will say so.