Skip to content

When Graphs Whisper: Graph Structure Serialization for Embedding Alignment in Cold-Start Recommendation

Conference: EMNLP 2026
Paper: ACL Anthology
Area: LLM Reasoning
Keywords: Cold-Start Recommendation, Graph Structure Serialization, Behavior-Content Alignment, Large Language Models, Collaborative Filtering

TL;DR

To tackle cold-start recommendation where new items lack interaction history and text prompts fail to capture higher-order graph topologies, GraphSEA serializes interaction graphs into structured token sequences for LLMs to learn behavior embeddings, aligning them with text-derived content embeddings across interaction probability, preference order, and item distinction while preserving ultra-fast dot-product inference.

Background & Motivation

In modern commercial recommender systems, thousands of newly listed items are launched every day. Delivering accurate recommendations for these newly introduced cold-start items is pivotal for sustaining recommendation diversity and platform vitality. Mainstream solutions generally adopt two paradigms: either fine-tuning Large Language Models (LLMs) on textual metadata prompts to simulate interaction inclinations, or learning neural mapping functions to project item text representations into the collaborative behavior space derived from warm items. While LLMs bring unprecedented zero-shot semantic understanding, existing prompt-based formulations are structurally bounded to first-order text descriptions, failing to exploit the rich higher-order topological connectivity and collaborative signals hidden in the bipartite interaction graph.

Furthermore, flattening complex graph structures into natural language sentences inevitably leads to severe information loss and distorted relational paths. More critically, an intrinsic distributional discrepancy separates collaborative behavior embeddings from descriptive content embeddings. Empirical t-SNE analysis reveals that behavior embeddings form compact, cluster-oriented manifolds driven by user interaction histories, whereas content embeddings derived from text descriptions are dispersed and noisy. Prior alignment strategies that rely solely on predicting matching probabilities or optimizing scalar MSE losses fail to reconcile these manifold divergences, often collapsing inter-item discriminative geometries in the cold-start regime.

To reconcile these fundamental limitations, the authors make an essential observation: although graphs are not natural language, random walk paths across bipartite interaction graphs possess sequential topologies that are structurally equivalent to linguistic sequences. By serializing graph paths into structured token sequences, the latent collaborative topology can be exposed to pre-trained LLMs without losing structural properties. Core idea: serialize bipartite interaction graphs into structured token sequences to extract high-order behavior embeddings using a shared LLM, and bridge the behavior-content manifold gap via dynamic masking and a multi-faceted alignment module optimizing score reconstruction, preference order, and item distinction.

Method

Overall Architecture

The GraphSEA framework comprises two primary components: LLM-Based Embedding Generation and Cold Embedding Alignment. In the generation phase, random walks on the bipartite interaction graph produce tokenized sequence corpora to optimize a behavior LoRA adapter on a frozen LLM backbone via next-token prediction, while a parallel content LoRA adapter processes structured prompt templates to produce dense content embeddings via mean pooling. In the alignment phase, behavior and content embeddings are concatenated, and Bernoulli random masking is applied to warm-item behavior vectors to dynamically simulate cold-start conditions. The model optimizes three complementary losses: score reconstruction, preference gap preservation, and discriminative consistency. At test time, cold items have their behavior vectors zero-masked and are mapped into the shared recommendation space to compute preference scores with lightweight dot products.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Bipartite Interaction Graph & Metadata Input"] --> B["Graph Structure Serialization & Dual Embedding Generation<br/>Random Walk Sampling with Behavior/Content LoRA"]
    B --> C["Dynamic Masking & Dimension Concatenation<br/>Simulating Missing Behavior Embeddings"]
    C --> D["Multi-Faceted Embedding Alignment<br/>Joint Reconstruction, Preference Gap & Discriminative Losses"]
    D --> E["Lightweight Dot-Product Inference & Cold-Start Ranking"]

Key Designs

1. Graph Structure Serialization & Dual Embedding Generation: Converting Topologies into Language Sequences for High-Order Collaborative Modeling
Traditional natural language prompts only articulate local neighborhood metadata and struggle to convey multi-hop relational dependencies. GraphSEA introduces a random walk sampling mechanism over the interaction graph \(G=(V, E, D)\) with transition probability \(P(v_{i+1}|v_i) = \frac{1}{|\Gamma(v_i)|}\) to generate path sequences \(s_i = \{u_1, i_4, u_4, i_2\}\) of length 4, treating each graph node directly as a unique token in the sequence corpus \(S\). By the Law of Large Numbers, the empirical transition frequency converges almost surely to the true graph transition probability as sampling proceeds (formalized in Theorem 1), rigorously preserving higher-order collaborative structures. The framework deploys two independent LoRA adapters on a shared frozen LLaMA backbone: the behavior adapter \(\theta_{\text{LoRA}}^{(B)}\) is fine-tuned on \(S\) via causal language modeling: $\(L_{\text{pre}} = - \sum_{i=1}^{|S|} \sum_{j=1}^{|s_i|} \log P(s_{i,j} \mid s_{i,<j})\)$ with behavior representations \(E_U^{(B)}, E_{I_w}^{(B)}\) formed by aggregating contextualized hidden states across all sequence occurrences. Concurrently, the content adapter \(\theta_{\text{LoRA}}^{(C)}\) encodes natural language prompt templates describing user demographics and item attributes, yielding content representations \(E_U^{(C)}, E_I^{(C)}\) via mean pooling over final-layer Transformer activations.

2. Dynamic Masking & Dimension Concatenation: Low-Overhead Cold-Start State Simulation
Rather than resorting to complex cross-attention or variational re-parameterization networks that incur heavy training latencies, GraphSEA adopts direct feature dimension concatenation: \(E_U = E_U^{(B)} \oplus E_U^{(C)}\) and \(E_{I_w} = E_{I_w}^{(B)} \oplus E_{I_w}^{(C)}\). To train the model to infer collaborative intent when collaborative histories are entirely absent, a dynamic Bernoulli masking vector \(M_i \sim \text{Bernoulli}(1-r)\) is applied to the behavior dimensions of warm items, generating \(\bar{E}_{I_w} = (M \odot E_{I_w}^{(B)}) \oplus E_{I_w}^{(C)}\). During inference for cold items \(i \in I_c\), the missing behavior embedding is replaced with an exact zero vector: \(\bar{E}_i = \mathbf{0} \oplus E_i^{(C)}\). This dynamic masking during training precisely simulates the representation format encountered by unseen items at inference time, conditioning the linear mapping layers to extract collaborative cues from textual content.

3. Multi-Faceted Embedding Alignment: Bridging Manifold Discrepancy Across Probabilities, Preference Ranks, and Geometric Separability
Directly minimizing prediction error on cold items fails because behavior embeddings form dense clusters while content embeddings are widely dispersed. GraphSEA rectifies this manifold divergence through three complementary alignment objectives. First, the Score Reconstruction Loss grounds predictions to warm collaborative signals: $\(L_{\text{rec}} = \frac{1}{|N|} \sum_{i=1}^{|N|} (r_t - r_p)^2\)$ where target score \(r_t = E_U^{(B)} \cdot E_{I_w}^{(B)}\) denotes historical interaction truth, and \(r_p = f_U(E_U) \cdot f_I(\bar{E}_{I_w})\) denotes the prediction from mapped concatenated vectors. Second, recognizing that recommendation performance hinges on relative ranking rather than absolute scores, the Preference Gap Loss preserves the margin between positive and negative candidates. Using normalized margins \(g_t = \sigma(r_{t,+} - r_{t,-})\) and \(g_p = \sigma(r_{p,+} - r_{p,-})\), it minimizes cross-entropy: $\(L_{\text{gap}} = - \frac{1}{|N|} \sum_{i=1}^{|N|} \left[ g_t^{(i)} \ln g_p^{(i)} + (1 - g_t^{(i)}) \ln(1 - g_p^{(i)}) \right]\)$ Third, to prevent the alignment from collapsing all item representations into an indiscriminate centroid, the Discriminative Consistency Loss enforces positive-negative geometric separation using projection terms \(d_t = \sigma({E_{I,+}^{(B)}}^\top (E_{I,+}^{(B)} - E_{I,-}^{(B)}))\) and its predicted counterpart \(d_p\): $\(L_{\text{disc}} = - \frac{1}{|N|} \sum_{i=1}^{|N|} \left[ d_t^{(i)} \ln d_p^{(i)} + (1 - d_t^{(i)}) \ln(1 - d_p^{(i)}) \right]\)$ The final objective balances these facets: \(L_{\text{total}} = L_{\text{rec}} + \alpha \cdot L_{\text{gap}} + \beta \cdot L_{\text{disc}}\).

Loss & Training

The framework follows a decoupled two-stage training scheme. In Stage 1, the behavior and content LoRA adapters are independently fine-tuned on the serialized graph corpus and text metadata corpus with learning rate 0.001 using LLaMA3.2-1B as the frozen backbone. In Stage 2, the extracted embeddings are frozen, and lightweight mapping functions \(f_U(\cdot)\) and \(f_I(\cdot)\) are optimized for up to 20 epochs under \(L_{\text{total}}\). Hyperparameters are dataset-dependent: \(\alpha=0.8, \beta=0.1\) for MovieLens-1M, and \(\alpha=0.4, \beta=0.1\) for Steam. All training is executed on a single NVIDIA Tesla V100-SXM2 (32GB) GPU.

Key Experimental Results

Main Results

GraphSEA is evaluated against 10 baselines across dropout-based models (DropoutNet, MTPR, Heater, CLCRec), generative models (DeepMusic, MetaEmb, GAR, ALDI), and LLM-based architectures (ColdLLM, FilterLLM) on MovieLens-1M and Steam with 20% items held out as cold items.

Dataset Evaluation Scenario Metric Ours (GraphSEA) Prev. SOTA (Model) Gain (%Improv.)
ML-1M Warm Item Task PRE@5 0.2539 0.2431 (CLCRec) โ†‘4.44%
ML-1M Warm Item Task NDCG@5 0.2675 0.2562 (DeepMusic) โ†‘4.41%
ML-1M Cold Item Task PRE@5 0.1095 0.0934 (FilterLLM) โ†‘17.24%
ML-1M Cold Item Task NDCG@5 0.1137 0.0928 (FilterLLM) โ†‘22.52%
ML-1M Cold Item Task NDCG@10 0.1022 0.0847 (FilterLLM) โ†‘20.66%
Steam Warm Item Task PRE@5 0.1775 0.1623 (MetaEmb/Heater) โ†‘9.37%
Steam Warm Item Task NDCG@5 0.3078 0.3063 (ColdLLM) โ†‘0.49%
Steam Cold Item Task PRE@5 0.0357 0.0281 (FilterLLM) โ†‘27.05%
Steam Cold Item Task NDCG@5 0.0389 0.0273 (FilterLLM) โ†‘42.49%
Steam Cold Item Task NDCG@10 0.0398 0.0296 (FilterLLM) โ†‘34.46%

In computational efficiency, GraphSEA completes training in 1.48 hours on ML-1M (testing: 0.10 min) compared to 3.40h for FilterLLM and 8.70h for ColdLLM; on Steam, GraphSEA finishes in 3.43 hours (testing: 0.22 min), outperforming ColdLLM (32.30h, 9.4x faster) and FilterLLM (11.05h, 3.2x faster).

Ablation Study

Systematic ablation of key architectural components on the MovieLens-1M benchmark:

Config Warm PRE@5 Warm NDCG@5 Cold PRE@5 Cold NDCG@5 Note
GraphSEA (Full model) 0.2539 0.2675 0.1095 0.1137 Full framework
w/o graph serialization ~0.246 ~0.252 0.0432 ~0.046 Removing graph serialization drops cold PRE@5 by 60.5%
w/o preference loss (\(L_{\text{gap}}\)) ~0.248 ~0.256 ~0.0625 ~0.065 Removing preference gap loss degrades cold metrics by 42.9%
w/o discriminative loss (\(L_{\text{disc}}\)) ~0.249 ~0.257 ~0.0578 ~0.060 Removing discriminative consistency degrades cold metrics by 47.2%

Key Findings

  • Crucial Role of Graph Serialization: Removing the serialized graph structure degrades cold-start PRE@5 from 0.1095 to 0.0432 (-60.5%), proving that natural language item descriptions alone cannot compensate for the absence of high-order collaborative topology.
  • Inverted U-Shape Walk Length and Masking Dynamics: Random walk length peaks sharply at \(l=4\) (PRE@5=0.110 vs. 0.076 at \(l=2\) and 0.087 at \(l=6\)), where shorter walks miss multi-hop context and longer walks ingest neighborhood noise. Similarly, the masking ratio exhibits an inverted U-curve peaking at \(r=0.5\), balancing feature learning pressure against information preservation.
  • Efficiency and Scalability Across LLM Backbones: Comparing LLaMA2-7B, LLaMA3.2-1B, LLaMA3.2-3B, and LLaMA3.1-8B shows that LLaMA3.2-1B achieves comparable cold-start accuracy to the 3B model (0.110 vs 0.112) and outperforms the 8B model (0.108) while operating at 1/8th the computational budget, proving small language models can effectively serve as graph token reasoners.

Highlights & Insights

  • Dual LoRA on Shared Frozen LLM: Decoupling behavior and content encoding into two distinct LoRA adapters over a single frozen LLM backbone prevents gradient conflicts between topological tokens and linguistic semantics while maintaining a common latent substrate.
  • Three-Pronged Manifold Rectification: Rather than forcing simple cosine alignment or MSE regression, the tripartite loss concurrently manages point-to-point numerical stability (\(L_{\text{rec}}\)), pairwise preference sorting (\(L_{\text{gap}}\)), and multi-item geometric distinction (\(L_{\text{disc}}\)), shrinking the centroid divergence on ML-1M from 58.44 down to 24.91.
  • Ultra-Fast Inference via Dot Product: In stark contrast to generative LLM recommenders that incur sequential token generation overheads per user-item pair, GraphSEA collapses inference into inner products between precomputed mappings, executing testing within 0.10 to 0.22 minutes.

Limitations & Future Work

  • Dependency on Descriptive Quality: The model's cold-start transfer capacity is constrained by the richness and clarity of metadata text; sparse or noisy descriptions will impede content embedding construction.
  • Absence of Dual-Cold User-Item Solution: The current design assumes warm users with historical interaction tracks. When both users and items are completely cold, the user behavior branch cannot be serialized.
  • Static Graph Assumption: The random walk corpus is pre-extracted from static snapshots, ignoring temporal session dynamics and fast-drifting item popularity.
  • vs FilterLLM (Liu et al., 2025): FilterLLM predicts probability distributions over entire user vocabularies via text-to-distribution modeling with heavy mutual information estimation. GraphSEA relies on direct random-walk tokenization to encode higher-order graph topologies, achieving 2.3x to 3.2x faster training and up to 42.5% NDCG@5 improvements on cold items.
  • vs ColdLLM (Huang et al., 2025): ColdLLM uses LLMs to simulate interaction pairs with complex candidate filtering funnels, requiring 32.3 hours of training and 13.4 minutes of testing on Steam. GraphSEA requires only 3.43 hours of training and 0.22 minutes of testing, running over 60 times faster at inference.
  • vs CLCRec (Wei et al., 2021) & ALDI (Huang et al., 2023): Conventional contrastive and distillation methods suffer from shallow embedding limitations or GNN over-smoothing. GraphSEA integrates LLM pre-trained semantics with graph serialization, consistently beating all GNN-based baselines across both warm and cold tasks.

Rating

  • Novelty: โญโญโญโญโญ Formulating graph random walks directly as token sequences for LLM causal modeling provides a fresh perspective on unifying graph learning and language models.
  • Experimental Thoroughness: โญโญโญโญโญ Comprehensive evaluation against 10 baselines, exhaustive ablations, hyperparameter sensitivity, and t-SNE centroid visualizations.
  • Writing Quality: โญโญโญโญโญ Rigorous mathematical justification with proof of convergence, structured algorithm specification, and clear narrative flow.
  • Value: โญโญโญโญโญ Bridges the gap between deep LLM reasoning and real-time millisecond inference demands in industrial cold-start recommendation systems.