Forgetting by Distance Traveled: Graph-Geometric Discounting for Preference Drift

Systems that learn from user histories have to decide how much old behavior to trust. The usual answer is to discount by the calendar: an interaction from last year counts less than one from yesterday, at a rate set by one global knob. That knob is wrong for most users. Some users stay inside one taste community for years, so their old data stays valid. Others jump across communities in a week. Users who return to an old interest are hurt most, because recency discounting has already thrown away the evidence that would have helped them. We propose to discount history by how far a user's preferences have moved rather than by how much time has passed. Movement is measured in the geometry of the item interaction graph, using effective resistance. Effective resistance treats the graph as an electrical network and asks how hard current flows between two items, so it counts all connecting paths, not just the shortest one.

The enabling fact comes from the scalable-centrality literature. Resistance distances can be written as Euclidean distances between low-dimensional node vectors, and those vectors can be built with a few dozen fast Laplacian linear-system solves followed by a random projection. Recomputing them on every snapshot of a million-edge graph is therefore cheap. Each user's history becomes a trajectory in a space whose distances are fixed by the graph rather than learned by the recommender. We weight each training example by how far the user has traveled from it in that space. The claim to test is that one displacement scale, tuned once, works across users whose drift speeds differ by orders of magnitude. A single time-decay rate cannot do this.

Core Claim

Non-stationary training methods such as Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift (NS-DPO) weight a sample with timestamp $t_i$ by $\gamma^{T-t_i-1}$. Here $T$ is the present and $\gamma\in(0,1]$ is a global discount. That paper itself notes two weaknesses. Choosing $\gamma$ requires knowing the drift rate in advance, and all samples with the same timestamp get the same weight. Our replacement weights the example that user $u$ produced at time $t_i$ by

$$w_{u,i} = \exp\!\big(-\lambda\,\lVert p_u(t_i) - p_u(T)\rVert^2\big),$$

where $p_u(t)$ is the user's position at time $t$ and $\lambda$ is a single global scale. The position $p_u(t)$ is the mean, over the items $u$ touched in a short window around $t$, of their resistance-embedding vectors. Those vectors are computed on the item co-interaction graph of the trailing window.

The embedding follows the standard construction. With $B$ the edge-node incidence matrix, $W$ the diagonal edge-weight matrix, $L$ the graph Laplacian, and $Q$ a random $\pm 1$ matrix with $k=O(\epsilon^{-2}\log n)$ rows, set $Z = Q W^{1/2} B L^{\dagger}$. Then the resistance between items $a$ and $b$ is approximately $\lVert Z(e_a-e_b)\rVert^2$ to within a factor $1\pm\epsilon$. The $\epsilon^{-2}\log n$ dimension comes from the Johnson–Lindenstrauss lemma, which says random projections to that dimension preserve pairwise distances. Each row of $Z$ needs one Laplacian solve, so no inverse is ever formed.

Three behaviors follow, and each can be tested. A user who stays in one community keeps long history. A user who crosses a structural bridge forgets quickly. A user who returns to an old region gets that region's old data back. The new part is the training-sample weighting rule and the claim that $\lambda$ transfers across heterogeneous users. The embedding machinery is reused.

Research Program

The method side reuses established components. Liren Shan and coauthors use Johnson–Lindenstrauss projection of $L^{\dagger}$ to compute marginal gains for group closeness in near-linear time, in Current Flow Group Closeness Centrality for Complex Networks?. They extend the same trick to edge centralities in Biharmonic Distance Related Centrality for Edges in Weighted Networks. Both papers work on static graphs, and both use the vectors to answer centrality queries. We use the vectors as a coordinate system for user trajectories over time.

Feasibility at scale is supported by two results. Fast Evaluation for Relevant Quantities of Opinion Dynamics solves Laplacian-type systems on the 4-million-node LiveJournal graph in about 80 seconds, with relative error below $10^{-7}$. FastGAT, in Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification, computes resistances on a 57-million-edge Reddit graph, but only once as preprocessing.

We do not use the index-based approach in Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach. That approach is very fast on low-treewidth road networks. The same paper reports that its index build becomes infeasible on scale-free graphs such as Youtube, and user–item graphs are scale-free. This negative result constrains the design toward solver-based sketches.

The dynamic setting is the open problem on the centrality side. We will not claim provable incremental maintenance. Instead we warm-start each snapshot's solves from the previous snapshot's solutions and measure how many solver iterations this saves as the graph drifts. One practical detail needs attention: projections must be consistent across snapshots, or trajectories will jump because the coordinates changed rather than the user. We will reuse the same random matrix $Q$ across snapshots. We will then quantify embedding jitter on users whose interactions did not change, and use that jitter as a noise floor.

The application side is training-time reweighting of a sequential recommender. The backbone is Self-Attentive Sequential Recommendation (SASRec), which predicts the next item with self-attention over a user's ordered history. We leave the architecture alone and change only the per-example loss weights.

This placement matters because of what SASRec's attention already does. Attention reweights past inputs by learned similarity. It does not decide which past training targets should shape the parameters. That decision is where NS-DPO's discount operates, and it is the slot our weight occupies. The motivating evidence that drift has long-range structure comes from Beyond Markovian Drifts: Action-Biased Geometric Walks with Memory for Personalized Summarization. That paper models user steps as magnitude-and-direction walks with click and skip memories, and it shows that one-step Markovian models of drift fail. Its decay kernels are fixed and its semantic space is local. Our displacement is measured on global graph structure and drives the discount directly.

Baselines

The naive reference is SASRec trained with uniform weights under a strict temporal split: train on interactions before a cutoff and test on the period after it, which is where drift hurts. Prior numbers are not directly comparable. On MovieLens-1M, HyMoERec: Hybrid Mixture-of-Experts for Sequential Recommendation reports HR@5 of 0.2157 and on Amazon Beauty HR@5 of 0.0518. That paper adds a mixture-of-experts feed-forward block to sequential recommenders. Those figures come from its own evaluation protocol, not a temporal split. We will rerun HyMoERec under our split as a strong architecture-side reference, without treating its published numbers as targets.

The strongest competitor on the actual question is NS-DPO-style exponential time discounting. We transplant it into SASRec as per-example weights $\gamma^{T-t_i-1}$. NS-DPO reports that this discount lifts AlpacaEval 2.0 length-controlled win rate from 7.29 to 8.93 on UltraFeedback-LM, and keeps reward accuracy above 60–70% where plain DPO falls to 50–55% when preferences flip. We found no reported result on Lacuna for time-discounted sequential recommenders under temporal splits, so we will establish that number ourselves. Fairness here means that $\gamma$ and $\lambda$ each get the same validation grid size and the same number of training runs, and the backbone, data, and compute are identical. We add the hybrid $\gamma^{T-t_i-1}w_{u,i}$ so that the time discount gets every chance to absorb the gain.

Three ablations isolate the key ingredient. The first replaces resistance positions with positions from learned item embeddings, taken from a separately trained SASRec item table, with all else held fixed. The second computes resistance embeddings once on the full aggregated graph instead of per window. The third replaces net displacement with total path length, which tests whether returning users are the source of any gain.

Beating the baselines means a statistically reliable gain in NDCG@10 and HR@10 on the post-cutoff period, across seeds, over the tuned time discount. The gain should also concentrate in the user strata the theory predicts, namely users whose drift speeds are far from the population average and users who return to earlier interests. An average gain that does not appear in those strata would not support the claim.

Why not just…?

Why not just tune the time-decay rate $\gamma$ on validation data? This is the main threat. If drift speeds are fairly uniform across users, a tuned $\gamma$ will match us. NS-DPO's own limitation is that a global $\gamma$ cannot adapt to users who drift at different rates and treats all same-time data alike. That is an argument, not evidence that the effect is large in recommendation data. The stratified analysis settles it. We bin users by measured drift speed and plot the loss of each method against a per-user oracle discount. If the tuned $\gamma$ stays close to the oracle in every bin, the proposal fails on these datasets, and we will say so.

Why not just fit a separate $\gamma$ per user? Most users have too few interactions to fit a decay rate reliably. The data-scarcity argument in A Shared Low-Rank Adaptation Approach to Personalized RLHF applies here: it motivates sharing parameters across users precisely because per-user fitting is too noisy. Displacement-based weighting shares one $\lambda$ but lets each user's own trajectory set the effective decay. We will include a per-user $\gamma$ fitted on held-out recent interactions, with shrinkage toward the global value, as an extra baseline. The comparison is most informative on users with short histories.

Why not measure drift with learned item embeddings instead of graph resistance? This is also a real threat, and it is the first ablation. Learned embeddings could track the same community structure. Resistance embeddings have two properties learned ones lack. They do not depend on the model being trained, so the weights cannot chase the model's own errors. They are also defined for sparse and cold items as long as those items have edges in the graph. If learned embeddings match resistance embeddings overall but lose on long-tail items, the contribution narrows to that regime. If they match everywhere, the result is still useful but different: displacement beats time, and the geometry source does not matter.

Why not use degree or popularity shifts as the drift signal? In Improving Information Centrality of a Node in Complex Networks by Adding Edges, the authors maximize a node's information centrality by greedy edge addition using Laplacian solvers, and degree-based heuristics do substantially worse because they miss bridges between distant regions. Proxying Betweenness Centrality Rankings in Temporal Networks finds local pass-through degree competitive with temporal betweenness. That paper warns, however, that local proxies lack ranking guarantees and can be made to fail on adversarial graphs. Because the evidence points both ways, we include a degree-shift weight as a baseline rather than dismiss it.

Proposed Experiments and Decisive Checks

The datasets are the timestamped sequential benchmarks MovieLens-1M, Amazon Beauty, Amazon Games, and Steam from the SASRec and HyMoERec papers. We add PENS click and skip logs from the Walk2Pers paper, where an item graph can be built from co-reading. For each dataset we build windowed item co-interaction graphs, compute resistance embeddings with $k$ between 32 and 128, and log solver time, warm-start savings, and jitter.

The first decisive check is synthetic. We plant users who switch communities at known rates and return at known times on a real item graph. Measured displacement should recover the planted switch times, and the weighting should beat the tuned $\gamma$ precisely where planted drift rates vary.

The second check is the real-data stratification described above, split by drift speed and by returning versus non-returning users. The prediction is a gain for returners against both the time discount and the path-length ablation.

The third check is cost. Per-snapshot embedding time must stay small relative to one training epoch. To test this, we time a synthetic scale-up toward LiveJournal size, using the reported 80-second APPROXIM figure as the feasibility reference.

The proposal fails if the tuned $\gamma$ or the learned-embedding ablation matches it within noise in the drifting strata. In that case the honest conclusion is that calendar time, or the model's own embeddings, already measures drift well enough.