When a new item enters a recommender system, nobody has clicked on it yet, so methods that learn from past clicks have nothing to work with. The usual fallback is to match the item's description against descriptions of things a user liked before. That fails when the new item and the user's past items describe the same interest in different words, which is the vocabulary-mismatch problem familiar from search. We propose a training-free fix built from two cheap parts. First, we average the word vectors of the new item's description and use the result to find a handful of textually similar items that do have click history. Second, we start a personalized random walk from those items over the existing user–item click graph. A personalized random walk, or random walk with restart, wanders along edges but jumps back to a chosen set of starting nodes with fixed probability at every step, so it stays near them. Users who receive a lot of walk probability are the ones we recommend the new item to.
Because the walk moves along co-consumption edges, it can reach users whose history shares no vocabulary with the new item. The description only has to match one warm "entry point" item; the click graph does the rest.
The design choice that matters, and the one we test, is where the text enters. Earlier work added text or attributes as extra nodes in the graph. That creates high-degree hub nodes that leak probability everywhere, and it measurably hurt random-walk recommendation on implicit-feedback data. We put text only into the restart distribution and leave the edges purely behavioral.
Core Claim
Text-derived side information helps random-walk recommendation for cold items if it decides where the walk restarts and does not add edges. Under that placement, a plain averaged static embedding is enough. The advantage over pure content matching should grow as lexical overlap shrinks between a cold item and the histories of the users who actually adopt it.
The second half of the claim is what makes the idea falsifiable. If the walk's gain over direct text matching does not depend on that overlap, the collaborative graph is not bridging any vocabulary gap, and the method reduces to a slower content-based recommender.
Background and Positioning
The negative result that motivates this work is from A Comparative Study of Matrix Factorization and Random Walk with Restart in Recommender Systems. It compares random walks with matrix factorization under identical conditions and reaches two findings. Random walks clearly win on implicit feedback (Spearman's ρ of 0.558 versus 0.428 on Lastfm). Yet adding user and item attributes as graph nodes ("RWR-Side") degraded implicit-feedback performance. We read this as a statement about placement rather than about side information as such, and our ablation tests that reading directly.
The hub explanation draws on SynsetRank: Degree-adjusted Random Walk for Relation Identification. That paper shows that a node's 1/degree transition split distorts influence in semantic graphs, and that reweighting the starting probabilities by degree corrects it (AUC rising from 0.6665 for PageRank to 0.7162). We reuse its degree-adjustment idea on the restart vector, but in the opposite direction: we damp popular entry items rather than boost hubs.
The restart mechanism itself, a geometric decay over path length that keeps probability near the seeds, is standard from Finding local communities in protein networks and Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks. Biased Random Walk based Social Regularization for Word Embeddings already combines biased restart walks with word embeddings. It does so to learn user-specific word vectors for sentiment classification, whereas we use fixed word vectors to seed a walk for recommendation.
On the text side, Saarland: Vector-based models of semantic textual similarity shows that averaging word vectors works well on short, keyword-dense text and loses to string overlap on long, syntactically complex sentences. Static Embeddings as Efficient Knowledge Bases? shows that averaged fastText vectors beat BERT on LAMA (41.2% vs 39.6% precision at 1) at about 0.3% of the energy, but only when a candidate set is supplied, and they degrade as multi-word subjects get longer. Both findings constrain us. Item descriptions are keyword-dense, which favors averaging. The need for a candidate set is exactly what our top-k restart restriction supplies, and the length sensitivity tells us to test averaging over short metadata fields separately from full descriptions.
WikiQA: A Challenge Dataset for Open-Domain Question Answering supplies the evaluation lens. It measures the lexical gap (20.3% of correct answers share no content words with the question) and shows word-count matching dropping from 0.5919 to 0.4891 MAP. We build the analogous stratification for recommendation.
The closest existing cold-start methods differ in where they put the text. Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods finds "virtual neighbors" for isolated nodes by feature similarity. That is close to our entry-point step, but it is trained, aimed at node classification, and passes messages from those neighbors rather than restarting a walk. It also reports underperforming on dense head nodes, a weakness our method avoids by leaving warm items untouched.
MARec: Metadata Alignment for cold-start Recommendation aligns a metadata item–item similarity with interaction similarity in closed form on top of the linear EASE model. It is the most direct competitor: equally cheap, equally text-driven, but single-hop in item space. Contrastive Learning for Cold-Start Recommendation (CLCRec) and DisCo learn joint content–behavior spaces with contrastive or mutual-information objectives. DisCo's argument that forcing semantic and collaborative spaces to coincide distorts both is compatible with our design, which never aligns the two spaces and only lets text choose starting points. FilterLLM predicts user distributions from item text with a 7B-parameter LLM whose vocabulary grows with the number of users. It is the high-compute reference point.
Method
Let $c_i$ be the averaged fastText vector of item $i$'s description, optionally with frequency-based down-weighting of common words. For a cold item $q$, we take the $k$ warm items $j$ with the highest cosine similarity to $c_q$ and form a restart vector over them. That vector is then divided by $d_j^{\beta}$, where $d_j$ is item $j$'s click degree and $\beta$ is a popularity-damping exponent ($\beta=0$ means no adjustment):
$$s_j \propto \frac{\max(0,\cos(c_q,c_j))^{1/\tau}}{d_j^{\beta}}, \qquad r = \alpha s + (1-\alpha) P^{\top} r .$$
Here $\tau$ is a temperature that controls how peaked the restart is, $P$ is the row-normalized transition matrix of the bipartite user–item click graph with no text nodes, $\alpha$ is the restart probability, and $r$ is the stationary walk distribution. We rank users by their entries of $r$. Large $\alpha$ keeps the walk next to the text neighbors, which approaches content matching. Small $\alpha$ lets collaborative structure dominate. The single parameter therefore traces a measurable path between "trust the words" and "trust the clicks."
We compute $r$ with sparse power iteration, or with local push approximations. Because the restart makes path weights decay geometrically, the cost per cold item is bounded and needs no gradient training. Warm items are scored by an unchanged standard random walk, so warm-start accuracy cannot degrade by construction.
Research Program
The work has three parts.
The first is the placement study. On identical graphs and identical text vectors, we compare text-as-restart against text-as-nodes (word or attribute nodes, as in RWR-Side) and against text-as-edges (Cold Brew-style virtual links from the cold item to its $k$ text neighbors, followed by an ordinary walk from each user).
The second is the lexical-gap stratification. For each test cold item, we compute the content-word overlap, by Jaccard similarity and by the fraction of zero-overlap cases, between its description and the descriptions of items in its true adopters' histories. We then bin cold items by that overlap.
The third is the encoder study. We swap averaged fastText for a sentence-transformer encoder inside the same walk. This shows how much of any gap to LLM-based methods comes from the encoder rather than from the propagation step.
Baselines
The naive reference is popularity: recommend the cold item to the most active users. This is what an unaided system effectively does. Any method failing to beat it on Recall@20 and NDCG@20 is uninformative.
The direct content baseline averages each user's history vectors into a user centroid and ranks users by cosine similarity to $c_q$, using the same fastText vectors and the same weighting. This is the strongest "no graph" competitor and isolates what the walk adds.
RWR-Side, from the comparative study, places each description word or attribute as a node linked to its items, which lets cold items join the graph. We give it the same vocabulary filtering and tune its α over the same grid as ours. Beating it is the core placement claim.
The text-as-edges ablation connects the cold item to its top-$k$ text neighbors with similarity-weighted edges and walks from users. It holds everything fixed except whether text enters as restart or as edges, so it isolates our key ingredient.
The strongest existing method under comparable compute is MARec with an EASE backbone (MARec). We run it twice, once with our fastText centroids and once with sentence-transformer embeddings, using its released closed-form procedure and the same hyperparameter budget (equal number of grid points) as our method. The file reports only relative numbers: MARec improves cold NDCG and Hit Rate by +8.4% to +53.8% over prior methods, and switching from bag-of-words to sentence-transformer metadata improved cold metrics by +46% and +105%. No reported absolute cold-start Recall or NDCG for MARec was found on Lacuna for MovieLens-10M or CiteULike, so we reproduce it. Beating it means higher cold-item Recall@20 with matched embeddings, by more than the across-seed standard deviation, on at least two of the three datasets.
CLCRec (Contrastive Learning for Cold-Start Recommendation) is the trained contrastive reference. It is reported only as +96.24% cold Recall@10 on Amazon, relative to its baselines, with no absolute value found on Lacuna. We run it with its recommended negative pool of 256 or fewer, given its reported overfitting beyond about 256.
FilterLLM (FilterLLM) reports +13.28% Recall and +20.08% NDCG on CiteULike over its baselines, again relative, with no absolute values on Lacuna. Because its cost is of a different order, we cite it as an upper reference on CiteULike only if we can reproduce it. We report accuracy against inference cost rather than claiming parity.
Ablations within our method switch off degree adjustment ($\beta=0$), replace the soft restart with a hard top-1 restart, and sweep α from near 1 (pure content) to small values.
Why not just…?
Why not just rank users by cosine between their history centroid and the cold item's centroid? This is the most serious threat. When descriptions share vocabulary with adopters' histories, it may match the walk. The lexical-gap stratification settles the question. If our gain over this baseline is flat across overlap bins, or appears only in high-overlap bins, the walk adds nothing and we drop the claim. The method is justified only if the gain concentrates in low- and zero-overlap bins, where averaging cannot reach the user's vocabulary. The WikiQA analysis (WikiQA) gives reason to expect such bins to be large.
Why not just use MARec, which is already closed-form and fast? MARec propagates text similarity one step in item–item space. The walk follows multi-hop user–item paths, and the comparative study found these paths matter most on implicit feedback (comparative study). That is an argument, not evidence. MARec could plausibly tie us on MovieLens, where metadata is genre-heavy and overlap is high. We therefore expect any advantage to show up on CiteULike, Amazon, and Lastfm-style implicit data, and we treat a tie on matched embeddings as an honest negative.
Why not just put text into the graph, or swap in an LLM encoder? Text-as-nodes is exactly what degraded implicit-feedback walks in the comparative study, and our placement study tests whether restart placement avoids that degradation. On encoders, MARec's +46% to +105% gain from sentence transformers suggests static averaging may leave accuracy on the table. Running both encoders inside the same walk measures this directly. If the LLM encoder helps the walk about as much as it helps MARec, the propagation contribution and the encoder contribution are separable, and practitioners can pick their cost point. The fastText energy result in Static Embeddings as Efficient Knowledge Bases? is why we keep static averaging as the default.
Proposed Experiments
We use three implicit-feedback, text-rich benchmarks from the file: CiteULike (strict item cold start, as in FilterLLM), MovieLens-10M with plot or genre text (as in MARec), and Amazon product data with descriptions (as in CLCRec and DisCo). Lastfm is a secondary graph-only check of the walk itself, where the comparative study reports a warm ρ of 0.558 for RWR. For each dataset we hold out 20% of items entirely as cold, with all their interactions removed from training, and evaluate Recall@20 and NDCG@20 over users. We use five random cold splits and report means with standard deviations. Warm accuracy is reported to confirm it is unchanged.
Three checks decide the outcome. First, text-as-restart should beat both text-as-nodes and text-as-edges on cold Recall@20 with identical embeddings; otherwise placement is not the explanation for RWR-Side's failure. Second, the gain over the content-centroid baseline should rise monotonically as adopter-history lexical overlap falls, with the largest gain in the zero-overlap bin. Third, plotted against α, accuracy should peak at intermediate values, not at α near 1 (which would mean pure content) or near 0 (which would mean the text adds nothing). If all three hold and the method matches MARec with matched embeddings at comparable wall-clock cost, the case for collaborative propagation as a lexical-gap bridge is established. If the second check fails, we report the method as a cheap content recommender and nothing more.
References
- A comparative study of matrix factorization and random walk with restart in recommender systems
- SynsetRank: Degree-adjusted Random Walk for Relation Identification
- Finding local communities in protein networks
- Weakly-Supervised Acquisition of Labeled Class Instances using Graph Random Walks
- Biased Random Walk based Social Regularization for Word Embeddings
- Saarland: Vector-based models of semantic textual similarity
- Static Embeddings as Efficient Knowledge Bases?
- WikiQA: A Challenge Dataset for Open-Domain Question Answering
- Cold Brew: Distilling Graph Node Representations with Incomplete or Missing Neighborhoods
- MARec: Metadata Alignment for cold-start Recommendation
- Contrastive Learning for Cold-Start Recommendation
- DisCo: Towards Harmonious Disentanglement and Collaboration between Tabular and Semantic Space for Recommendation
- FilterLLM: Text-To-Distribution LLM for Billion-Scale Cold-Start Recommendation