Many recommenders now get most of their benefit from graphs at serving time rather than at training time. A plain embedding model is trained once. When a request arrives, each user's vector is blended with the vectors of the items they recently touched, and each item's vector with those of its users. This blending step, called test-time message passing, was isolated by How Does Message Passing Improve Collaborative Filtering? (TAG-CF). That work showed it recovers most of the gain of graph neural recommenders at under 1% of their training cost.
In a live system the interaction graph changes with every click, and this creates two problems. Items go viral and fade, so a fixed popularity correction is wrong within hours. And recomputing every blended vector after every click, then shipping the result to serving replicas, costs too much. Nobody has studied how to keep this serving-time graph step both fresh and debiased under a stream.
This note proposes one mechanism that handles both problems. The blending step weights each neighbor by its time-decayed degree: the number of interactions it received, with older ones counting exponentially less. It also raises the item's decayed degree to a negative power, so currently hot items pull less on their neighbors. A trending item's pull on its neighborhood is damped while it is hot and recovers as it cools. This targets the failure that How Graph Convolutions Amplify Popularity Bias for Recommendation? traces to degree-driven "popularity gravity."
The second half of the idea is about updates. Exponential decay shrinks every node's degree by the same factor when nothing happens to it. So cached blended vectors only go stale when a node's degree changes relative to the rest. That lets us maintain the blended vectors with small, lazily applied deltas whose error has a proven bound, and ship only those deltas to replicas.
Core Claim
Our claim has two parts. The empirical part: under time-ordered "test-then-learn" evaluation, decay-normalized test-time smoothing beats two alternatives on tail-item accuracy and recommendation concentration without losing overall accuracy. The first alternative is static-degree smoothing, which is TAG-CF as published. The second is score-level dynamic popularity correction, which is the strongest graph-free competitor. The systems part: the same accuracy is obtained from a delta-maintained cache whose update and network cost per new interaction is amortized $O(1/\varepsilon)$, where $\varepsilon$ is a tolerance knob. The alternative is recomputing aggregates eagerly or rebuilding them periodically.
Concretely, for user $u$ at time $t$ the served vector is
$$ h_u(t) = e_u + \beta\, \tilde d_u(t)^{-a} \sum_{i \in N_u(t)} e^{-\lambda (t - t_{ui})}\, \tilde d_i(t)^{-b}\, e_i, \qquad \tilde d_i(t) = \sum_{j \in N_i(t)} e^{-\lambda (t - t_{ji})}. $$
The symbols are as follows. $e_u, e_i$ are the base matrix-factorization embeddings. $N_u(t)$ is the set of items $u$ has interacted with by time $t$, and $t_{ui}$ is the interaction time. $\lambda$ is the decay rate. $\tilde d$ is the decayed degree. $a$ and $b$ are normalization exponents, and $\beta$ is the blending weight. Items get the symmetric formula.
The exponent $b$ is the popularity lever. Setting $\lambda=0$ and $a=b=1/2$ recovers ordinary static symmetric normalization.
The maintenance rule caches $\hat d_i$ for each item. Terms involving $i$ are refreshed only when the ratio $\tilde d_i(t)/\hat d_i$ leaves $[1/(1+\varepsilon),\,1+\varepsilon]$. Both quantities decay together, so the ratio moves only when new events arrive. Each cached term is then within a factor $(1+\varepsilon)^b$ of exact. The bound comes directly from the refresh rule.
Refreshing a hub costs work proportional to its degree, but it happens only once per multiplicative change in degree. Summing that geometric series gives amortized $O(1/\varepsilon)$ refreshes per new edge. Embedding updates from incremental training are handled the same way, with a tolerance on $\|\Delta e_i\|$.
Position Relative to Prior Work
The closest works fall into three groups.
The first group motivates the problem. TAG-CF supplies the serving-time smoothing we build on, but it uses static snapshots and static degrees. Its variant TAG-CF+ restricts smoothing to low-degree users. This creates the tension our design resolves: a node that jumps from low to high degree during a trend stops benefiting from smoothing and starts distorting its neighbors, which DAP warns about. DAP corrects this by clustering and subtracting popularity vectors on frozen embeddings. GSDA (Graph-Structured Driven Dual Adaptation for Mitigating Popularity Bias) adapts its debiasing to the graph's Gini coefficient, but only on static snapshots. Neither method says what to do when degrees change by the minute.
The second group shows that popularity correction must track time. Taming Recommendation Bias with Causal Intervention on Evolving Personal Popularity (CausalEPP) forecasts item popularity and user conformity with moving averages and applies a causal adjustment that blocks the direct effect of popularity on clicks. Dynamic Popularity-Aware Contrastive Learning for Recommendation (DPA) adds back the current daily item popularity at inference. Evolution of Popularity Bias: Empirical Study and Debiasing shows a fixed penalty fails under feedback loops: Gini reaches about 0.8 for standard matrix factorization versus about 0.2 with dynamic scaling. All three correct scores or losses with centralized statistics. We put the time-varying correction inside the graph step, where it changes which neighbors shape a user's vector, and make it incrementally maintainable.
The third group supplies the systems pattern. DECK tracks modified embedding rows during the forward pass and ships only those deltas, but only for training checkpoints. Intelligent Model Update Strategy for Sequential Recommendation (IntellectReq) decides when an edge device should request a full parameter refresh and cuts requests by 90–97%. We take DECK's row-delta idea into serving and replace IntellectReq's learned trigger with a refresh condition that has an error guarantee. The lazy-consolidation lesson from dynamic indexing (The DiskANN library) constrains the design: eager per-event in-place updates are a known latency trap.
Research Program
We will build a single-writer coordinator that consumes the time-ordered interaction stream. It maintains decayed degrees in a log-time representation: values are stored at a common reference time and the shared factor $e^{\lambda t}$ is applied on read, so idle nodes cost nothing. It applies the refresh rule and emits delta records. Each record is either an edge-term addition, or a node's rescaled contribution after its degree crosses the tolerance band, or an embedding-row change. Serving replicas apply these records to their cached aggregates.
The base model is matrix factorization trained on an initial period. In one condition it stays frozen. In a second it is fine-tuned incrementally, following the incremental-update setting surveyed in A Survey on Incremental Update for Neural Recommender Systems.
On the analysis side, we will measure how degree-ratio crossings are distributed on real streams. This tells us whether the amortized bound is the operative cost or whether viral bursts dominate. We will also characterize how the tolerance $\varepsilon$ trades accuracy against bytes shipped.
Baselines
The naive reference is the base matrix-factorization model trained on the initial period, served without updates or smoothing. A second naive point is the same model with static TAG-CF smoothing computed once. Together they show how much the stream itself is worth.
The freshness reference is TAG-CF and TAG-CF+ rebuilt from scratch at fixed cadences: hourly, and daily or per-day slice depending on dataset span. This is what a practitioner would deploy. It runs on the same base embeddings, so differences isolate normalization and freshness. We beat it if we match or exceed its accuracy at equal or lower compute and bytes.
The eager-exact variant recomputes affected aggregates after every event with our decayed normalization ($\varepsilon=0$). It is the accuracy ceiling for our mechanism and the cost ceiling against which delta savings are measured.
The strongest debiasing competitors are CausalEPP and DPA, each reimplemented on the same stream and evaluated prequentially. CausalEPP reports +20.4% Recall@20 and +14.7% NDCG@20 over its best baselines on Amazon-Music, and lowers the popular-item recommendation rate from LightGCN's 75.8% to 55.5% against a 43.3% ground truth. DPA reports a 117.30% Recall@1 improvement over a DeepMatch full-softmax model on Alibaba. These are relative gains under the authors' own splits, and Lacuna reports no absolute numbers for them. We therefore rerun both under our protocol with an equal hyperparameter search budget, about fifty trials per method on a held-out early slice of each stream.
We also include LightGCN with DAP, retrained at the same cadences. DAP reports a 23.96% TR@20 gain on Gowalla over static baselines.
Beating the field means two things. On Amazon-Music, the popular-item rate must land closer to the ground-truth rate than CausalEPP's. And tail Recall@20 must improve over the best of these competitors with overall Recall@20 within one point.
Ablations isolate each ingredient. Setting $\lambda=0$ removes temporal decay. Setting $b=1/2$ removes extra popularity damping. Removing the decayed-degree gate on users isolates the TAG-CF+ interaction. Sweeping $\varepsilon$ from 0 upward isolates the lazy-delta approximation. For synchronization, we add an IntellectReq-style trigger that ships full aggregate tables when a drift score crosses a threshold, compared at matched bytes.
Why not just…?
Why not just rebuild the smoothed vectors periodically? If an hourly rebuild matches our accuracy, the systems half of the claim reduces to a cost argument, and we accept that framing. The survey documents that batch updating misses within-window interest shifts in fast domains. Globo news and Alibaba promotions are where this should show. The decisive experiment plots accuracy against compute and bytes for rebuild cadences and $\varepsilon$ values on the same axes. If rebuilds sit on the same frontier, we report that.
Why not just correct scores with current popularity, as DPA does, and skip the graph? This is the real threat. A score-level correction captures transient popularity cheaply. Our hypothesis is that it cannot help tail items whose vectors were never shaped by relevant neighbors. TAG-CF found a 39.2% NDCG@20 gain for low-degree users on ML-1M from smoothing alone. The test splits results by user and item degree. If score-level correction on unsmoothed matrix factorization matches us in the low-degree buckets, the graph component is unnecessary and we drop it.
Why not just use CausalEPP? It models per-user conformity, which our mechanism does not. Our exponent $b$ is global. If CausalEPP wins on conformity-heterogeneous data such as Douban-Movie, the natural fix is a user-specific exponent, which stays delta-maintainable. We will test that variant rather than argue around a loss.
Why not just use a learned trigger like IntellectReq? It saves calls but ships full state on each call and gives no error guarantee. The matched-bytes comparison settles whether bounded-error deltas buy accuracy per byte.
Proposed Experiments
We will use timestamped streams: Amazon-Music, Douban-Movie, Ciao, Alibaba, Globo, Gowalla, Yelp2018, and Amazon-book. Each is replayed in time order under test-then-learn evaluation.
The accuracy metrics are Recall@20 and NDCG@20, overall and by popularity tier, with tail recall. Concentration is measured by the Gini coefficient of recommendations and the popular-item recommendation rate, defined as in CausalEPP. Systems metrics are bytes shipped per interaction, refresh operations per interaction, worst-case staleness, and the measured error against eager-exact aggregates. The last checks the $(1+\varepsilon)^b$ bound empirically.
Three checks are decisive. First, decay-normalized smoothing must beat static-degree TAG-CF on tail metrics on Globo and Alibaba, where popularity turns over fastest. If it does not, the core idea fails. Second, $\varepsilon$ around 0.1 must stay within half a Recall@20 point of eager-exact while shipping at least an order of magnitude fewer bytes than hourly rebuilds. Third, in a semi-synthetic closed-loop replay on ML-1M following the feedback-loop protocol of Zhu et al., recommendation Gini under our method must stay well below the roughly 0.8 that standard matrix factorization reaches.
References
- How Does Message Passing Improve Collaborative Filtering?
- How graph convolutions amplify popularity bias for recommendation?
- Graph-Structured Driven Dual Adaptation for Mitigating Popularity Bias
- Taming Recommendation Bias with Causal Intervention on Evolving Personal Popularity
- Dynamic Popularity-Aware Contrastive Learning for Recommendation
- Evolution of Popularity Bias: Empirical Study and Debiasing
- DECK: Experiences on Delta Checkpointing for Industrial Recommendation Systems
- Intelligent Model Update Strategy for Sequential Recommendation
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search
- A Survey on Incremental Update for Neural Recommender Systems