In recommendation systems, the "cold-start" problem is a fundamental hurdle: how do you suggest the right item to a user you have never met, or promote a new product that has no purchase history? Traditional collaborative filtering relies on a dense matrix of interactions, but for new entities, this matrix is empty.
The research direction emerging across these papers treats recommendation not as a matrix completion task, but as a signal propagation problem on a graph. By connecting sparse nodes (new users or items) to dense nodes (active users or popular items) through shared attributes, contexts, or behaviors, systems can "borrow" information to fill the gaps.
Borrowing Strength from Neighbors
The core intuition is that no user or item is a total island. Even if a user has no history, they exist within a context. Claudio Gentile, Shuai Li, and their colleagues explored this in On Context-Dependent Clustering of Bandits. Their algorithm, CAB, dynamically forms "neighborhoods" of users based on the specific item being considered.
When a user interacts with an item, the feedback doesn't just update that user's profile; it propagates to all similar users in that context-specific neighborhood. This allows the system to make informed decisions for infrequent users by leveraging the collective data of their peers. Similarly, the COFIBA algorithm adaptively clusters both users and items, creating a preference graph where interaction data flows across edges to reach "cold" nodes more quickly.
High-Order Connectivity as a Warm-Up
While simple clustering helps, modern approaches use Graph Neural Networks (GNNs) to capture "high-order" relationships—connections that are two or three steps away. Shoujin Wang and Xiangnan He describe this in their review of graph learning approaches. Information propagation allows features to flow from "high-degree" nodes (data-rich) to "low-degree" nodes (data-poor) through the topological structure of the network.
This is particularly effective for niche items or complex recommendations. For example, in Bundle Recommendation with Graph Convolutional Networks, Chen Gao and Xiangnan He show that a new "bundle" (like a themed playlist) can be "warmed up" by propagating the popularity and attributes of its constituent items through a heterogeneous graph. Even if the bundle itself is new, its parts are not.
Bridging Domains with Shared Attributes
When behavioral data is completely absent, the graph must rely on metadata to bridge the gap. This is the strategy used by LinkedIn’s LinkSAGE framework, developed by Haichao Wei, Xiaochen Hou, and others (LinkSAGE 2024, LinkSAGE 2025).
LinkSAGE uses a massive heterogeneous graph where users are connected to "attribute nodes" like skills, job titles, or locations. A new user with zero job applications can still inherit representational signals from highly active users who share the same skills. By propagating information through these shared attribute nodes, the system generates meaningful embeddings for entities with limited historical data, effectively "densifying" a sparse graph.
Multi-Modal and Reasoning-Based Expansion
The latest evolution of this idea involves using external knowledge to enrich the graph. Hao Wu and colleagues introduced MM-GEF, which fuses multi-modal content (like images and text) with behavioral graphs. If two items look similar or have similar descriptions, they are linked in the graph, allowing the system to recommend a new item based on its visual or semantic cousins.
Taking this further, the GRASPER framework by Bo Ni and Tyler Derr combines graph-based context expansion with Large Language Model (LLM) reasoning. For a cold-start user, the system uses the graph to retrieve relevant external data and then uses an LLM to "reason" about a synthetic history for that user. This ensures that the augmented information propagated through the graph is not just statistically likely, but contextually and stylistically aligned with the user.
Why It Works: The Topology of Similarity
Graph information propagation works because it replaces the requirement for direct evidence (user A bought item B) with topological evidence (user A is similar to user C, who bought item B). By treating the recommendation space as a connected network, these models ensure that no node is truly "cold" as long as it has a single connection to the rest of the world—whether that connection is a shared skill, a similar image, or a common context.