A common way to make trajectory search fast is to learn a vector for every trip, so that "find the trips most like this one" becomes a nearest-neighbor lookup instead of millions of slow curve-to-curve alignments. One recent family of methods learns these vectors by treating each trajectory as a node in a graph and linking trips whose shapes are close. It then runs a graph neural network, a model that updates each node by averaging in its neighbors. VeTraSS builds this graph at several scales by doubling a distance threshold at each level. We argue that this schedule is the wrong axis. In a downtown core, doubling the radius pulls in thousands of near-duplicate trips at once. In the suburbs, it may add none. Because averaging over many neighbors washes out the differences between nodes (over-smoothing), a distance schedule makes dense-region trips blur together within one or two scales while sparse-region trips barely aggregate at all.
The proposal is to grow each trip's neighborhood by neighbor count rather than by distance. Concretely, scale $s$ gives each node roughly $k_0 2^s$ effective neighbors. Every node then smooths at about the same rate regardless of how crowded its part of the city is. We also build these neighborhoods without computing all pairwise curve distances, using the lower-bound pruning tools that trajectory indexing already provides. The testable claim is that over-smoothing in trajectory graphs is density-dependent, that retrieval errors concentrate where it is strongest, and that equalizing neighbor count across density removes both effects. We expect this to be cheaper than learned anti-smoothing machinery.
Core Claim
Under a distance-doubling schedule, the per-node rate at which representations lose distinctiveness grows with local trajectory density. Retrieval failures, meaning missed true neighbors at small $k$, concentrate in the densest density deciles. Replacing the schedule with a count-based one should flatten this dependence and improve top-1 and top-10 hit ratios in dense regions without hurting sparse ones.
A count-based schedule can be written as a per-node radius $r_i^{(s)}$, chosen so that
$$2^{H\left(P_i^{(s)}\right)} = k_0\, 2^{s},$$
Here $P_i^{(s)}$ is a Gaussian-weighted distribution over trajectory $i$'s candidate neighbors at bandwidth $r_i^{(s)}$, $H$ is its Shannon entropy, and $k_0$ is the base neighbor count. This is the perplexity calibration of Stochastic Neighbor Embedding, which shrinks the kernel in dense regions and widens it in sparse ones. Its hard limit is simply a $k$-nearest-neighbor graph with $k$ doubling per scale.
We deliberately treat the hard version as a first-class arm rather than a strawman. The claim is about the schedule axis (count versus distance), not about the softness of the kernel. The soft version is expected to help only at density boundaries. There, Proximity Graphs for Clustering and Manifold Learning shows that fixed-$k$ graphs make sparse points reach across gaps into unrelated regions, while fixed-radius graphs fragment sparse areas and saturate dense ones.
Research Program
The work has three parts.
The first is a diagnosis. We reimplement the VeTraSS pipeline on Porto and GeoLife and measure, per node and per scale, the local Dirichlet energy, which is the summed squared difference between a node's vector and its neighbors' vectors. We bin nodes by local trajectory density and test whether energy decay and retrieval misses rise with density.
Raw energy can be misleading. Are we measuring oversmoothing in graph neural networks correctly? argues that distance-based measures cannot separate useful alignment from harmful collapse. We therefore also report a task-aligned ratio. Its numerator is the embedding distance between a query and its true top-10 Fréchet neighbors. Its denominator is the embedding distance between the query and same-density non-neighbors. This ratio falls toward one exactly when smoothing destroys discriminability.
The second part is the construction. Count-based neighborhoods need only each node's nearest candidates, not all pairs. We obtain them with a candidate-generation-then-verify loop. Cheap geometric lower bounds discard most candidates before any exact Fréchet or Dynamic Time Warping distance is computed. We use the bounding-box lower bounds of LB-Warp, which combines piecewise averaging with minimum bounding rectangles to prune elastic-distance candidates, and the linear-space metric tree of A Practical Index Structure Supporting Fréchet Proximity Queries among Trajectories. The binary search over $r_i^{(s)}$ is the known cost bottleneck of perplexity calibration. It runs only over the verified candidate list, so its cost scales with $k_0 2^{S}$ per node, where $S$ is the number of scales, rather than with $N$. These papers supply the method; our contribution is pointing them at graph construction rather than at query answering.
The third part is the learning stage. We keep the VeTraSS attention encoder and its training objective fixed, and change only the graph. Any gain is then attributable to neighborhood construction.
Baselines
The naive reference point uses no graph: a sequence encoder over each trajectory's own points, indexed for nearest-neighbor search. We use KGTS, which embeds a spatial grid with a knowledge-graph objective and trains a graph convolution plus recurrent encoder contrastively, without distance labels. It reports HR@1 of 0.5244 on Porto and 0.5123 on GeoLife. It is the strongest label-free competitor. If inter-trajectory graphs cannot beat it, the whole line is moot.
The strongest graph-based competitor is VeTraSS itself, which reports HR@10 of 0.4968 under Fréchet distance on Porto, against 0.4801 for NEUTRAJ. VeTraSS reports no GeoLife number. For Chengdu and Xi'an, Jointly Contrastive Representation Learning on Road Network and Trajectory reports similarity-search HR@10 of 0.928 and 0.912. That method uses a road-network attention encoder plus a trajectory Transformer, but under its own ground-truth definition, so it serves only as a reference within those cities.
Published numbers use different ground truths and query protocols, so every method is re-run under one protocol. Ground truth is the top-$k$ Fréchet neighbors for a held-out query set. All methods use the same training split and embedding width. Each method gets the same hyperparameter search budget in GPU-hours, and all methods use the same approximate-nearest-neighbor index at query time.
The key ablations isolate the schedule. The first is a hard $k$-doubling graph. The second is the soft perplexity-doubling graph. The third is distance doubling with a per-city tuned base threshold, which tests whether a better $\delta$ alone fixes the problem. Beating VeTraSS means a higher HR@1 and HR@10 averaged over three seeds, with the gain concentrated in the top density deciles as the claim predicts. Beating KGTS means a higher HR@1 at equal or lower total preprocessing-plus-training time.
Why not just…?
Why not just tune the distance threshold? A single global $\delta$ cannot be right for both the center and the fringe. That is the core argument of Proximity Graphs for Clustering and Manifold Learning. The tuned-$\delta$ ablation tests this directly. If it matches the count-based schedule across density deciles, our diagnosis is wrong and we will say so.
Why not just add PairNorm? PairNorm re-centers and rescales all embeddings so that their total pairwise spread stays constant. It kept a simple graph convolution usable to 60 layers on Cora. But it is a global constraint: it can restore overall spread while dense-region trips remain collapsed relative to each other, with sparse trips absorbing the variance. Its own finding that depth helps mainly when features are missing also suggests limited upside on feature-rich graphs. We run VeTraSS with PairNorm and check whether the dense-decile retrieval gap survives. We predict it does.
Why not just learn per-node gates? This is the most serious threat. ALaGCN learns a per-node gate from neighborhood entropy and center-neighbor similarity, and stops aggregation when neighbors are redundant or mixed. On Cora with 1% labels it reaches 73.3% against 59.2% for a plain graph convolution. Adaptive Message Passing learns soft per-node message filters and a variational depth distribution. Either could learn to throttle dense-region aggregation on the original distance-doubling graph.
Our design differs in fixing the problem at construction time, with no learned gate. That also shrinks the dense cliques that make distance-doubling graphs expensive to store and to run message passing over. We run both gated models on the distance-doubling graph. If they match our retrieval accuracy, the remaining contribution is purely the construction cost and memory saving, which we measure explicitly.
Proposed Experiments
The datasets are Porto (1.7 million taxi trips), GeoLife, and the Chengdu and Xi'an Didi traces. The metrics are HR@1 and HR@10 against Fréchet ground truth, reported overall and per density decile. We also report graph construction wall-clock time, the fraction of candidate pairs needing exact distance computation, and edge count and memory per scale.
The first decisive check is diagnostic. Under distance doubling, the task-aligned smoothing ratio and the miss rate should both increase monotonically with density. Under count-based schedules, both should be roughly flat. If the distance-doubling graph shows no density dependence, the proposal fails at its premise.
The second check is the head-to-head comparison against the tuned-$\delta$, PairNorm, ALaGCN, and Adaptive Message Passing variants on identical encoders.
The third check is scaling. We grow Porto subsets from 10,000 to 1 million trips and test whether pruned construction stays near-linear, while all-pairs distance doubling grows quadratically. The KGTS observation that exact distance labels cost about an hour per 5,000 trajectories gives a reference for what avoiding all-pairs computation must beat.
Finally, a soft-versus-hard comparison restricted to nodes at density boundaries tells us whether perplexity calibration earns its extra cost or whether plain $k$-doubling is the method to recommend.
References
- VeTraSS: Vehicle Trajectory Similarity Search Through Graph Modeling and Representation Learning
- Stochastic Neighbor Embedding
- Proximity Graphs for Clustering and Manifold Learning
- Are we measuring oversmoothing in graph neural networks correctly?
- Rotation invariant distance measures for trajectories
- A Practical Index Structure Supporting Fréchet Proximity Queries among Trajectories
- KGTS: Contrastive Trajectory Similarity Learning over Prompt Knowledge Graph Embedding
- Jointly Contrastive Representation Learning on Road Network and Trajectory
- PairNorm: Tackling Oversmoothing in GNNs
- When Do GNNs Work: Understanding and Improving Neighborhood Aggregation
- Adaptive Message Passing: A General Framework to Mitigate Oversmoothing, Oversquashing, and Underreaching