🤖 AI

Bridging the Semantic-Collaborative Gap: An Asymmetric Graph Architecture for Cold-Start Item Recommendation

This paper proposes Shallow-RHS, an asymmetric graph architecture that addresses cold-start challenges in Tubi's recommendation system by training a content encoder to map intrinsic features directly into a collaborative-filtering-aware embedding space without relying on interaction history, thereby enabling immediate retrieval for new items and devices.

Original authors: Anh Truong, John Trenkle, Yuanbo Chen, Honghong Zhao, Abdullah Alchihabi, Effy Fang, Michael Tamir

Published 2026-06-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Anh Truong, John Trenkle, Yuanbo Chen, Honghong Zhao, Abdullah Alchihabi, Effy Fang, Michael Tamir

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "New Kid" on the Block

Imagine a massive library (Tubi) with millions of books (movies and shows). The library's recommendation system is like a super-smart librarian who knows exactly what you like based on what you've read before. This librarian is great at suggesting books because they know your history.

But here is the problem: What happens when a brand new book arrives?

The librarian has never seen this book before. No one has read it yet. Because the librarian relies on "who read what," they have no idea how to recommend this new book. It's a "cold start." The book sits on the shelf, invisible to everyone, because it has no "interaction history."

The same problem happens with new library members (new devices). If a new person walks in, the librarian doesn't know them yet and can't guess what they like.

The Solution: A Specialized Two-Team System

The authors at Tubi built a new system called Shallow-RHS. Think of this system as a two-person team working together to solve the "New Kid" problem.

1. The Left-Hand Side (LHS): The "Social Detective"

This team member is the expert on people.

How they work: They look at a user's history. "Oh, you watched Action Movie A and Comedy B last week. You also watched Sci-Fi C."
The Magic: They use a technique called "message passing." Imagine they are walking through the library, talking to other people who have similar tastes. They gather clues about what the crowd likes.
Result: They create a very detailed profile of the user based on their social behavior and history.

2. The Right-Hand Side (RHS): The "Shallow Observer"

This team member is the expert on content, but with a strict rule: They are not allowed to talk to the people.

The Constraint: Usually, recommendation systems try to learn about a movie by seeing who watched it. But for a new movie, no one has watched it yet! So, this team member is forced to look only at the movie's own features.
What they look at: The title, the genre, the actors, the plot summary, and even the script (using AI to understand the story).
The Goal: They must learn to describe the movie in a way that matches the "Social Detective's" understanding of what people like, even though they never saw a single person watch it.

Why is this "Asymmetric"?
It's like a dance where one partner (the User) is doing a complex routine with many steps (history), while the other partner (the New Movie) is standing still, holding a sign with their description. The system learns to make them dance together perfectly, even though the movie has no steps of its own yet.

The "Magic Bridge": Connecting the Unknown to the Known

Once the system is trained, it can handle new movies instantly. Here is how:

The Translation: When a new movie arrives, the "Shallow Observer" reads its description and turns it into a "code" (an embedding).
The Surrogate Neighbors: The system looks at this new code and asks, "Which old, popular movies look most like this new one?"
- Analogy: Imagine a new, unknown band plays a song. The system doesn't know the band, but it says, "This song sounds exactly like a hit song by a famous band from 1990."
The Recommendation: The system recommends the new song to people who loved that 1990s hit.
- This is called Implicit Graph Completion. The system pretends the new movie is connected to the old, popular ones, allowing it to get recommended immediately without waiting for real views.

Fixing New Users (Device Cold-Start)

The paper also solved the problem for new library members (new devices) who have no watch history.

The Strategy: If the librarian doesn't know you, they look at your demographics.
The Analogy: If a new person walks in wearing a red hat and carrying a soccer ball, the librarian assumes, "Ah, this person is probably a soccer fan from this neighborhood."
The system groups new users into "cohorts" (groups based on age, location, device type) and recommends content that the rest of that group usually likes.

The Results: Does it Work?

The team tested this in the real world at Tubi (which has hundreds of millions of users). They ran experiments over several months, gradually improving the system:

Phase 1: Just switching to this new "Two-Team" system made new movies get seen faster.
Phase 2: Giving the system better descriptions (more metadata like budget, ratings, and better AI summaries) made it even better.
Phase 3: Fixing missing data (making sure every movie had a full description) helped the system understand the movies even more accurately.
Phase 4: Using advanced AI to fill in the gaps for the hardest-to-describe movies (the "long tail") gave a final boost.

The Outcome:

More Watching: People watched more content overall.
Faster Promotion: New movies became popular much faster because they were recommended to the right people immediately.
Better First Impressions: New users (new devices) were happier with their first recommendations because the system guessed their interests correctly using group data.

Summary

The paper describes a smart way to recommend new movies and welcome new users by using asymmetry. One side of the system learns from human behavior, while the other side learns strictly from the content's description. By forcing the system to learn how to translate "content description" into "what people like," they can recommend brand-new items instantly, bridging the gap between what a movie is and what people want to watch.

Technical Summary: Bridging the Semantic-Collaborative Gap via Asymmetric Graph Architecture

Problem Formulation
The paper addresses the cold-start challenge in large-scale streaming recommendation systems, specifically within Tubi's production environment. The core issue is that collaborative filtering (CF) models rely on observed user-item interactions to learn representations, leaving newly added content (zero-edge nodes) and newly activated devices without meaningful embeddings. Standard graph-based models fail here because they cannot propagate signals to nodes lacking interaction history.

The authors frame this as an inductive graph-completion problem on a temporal bipartite graph of devices ( $D$ ) and content ( $C$ ). The system faces strict serving constraints:

New content must receive a standalone embedding immediately upon ingestion, without waiting for interaction history.
Embeddings must be suitable for approximate nearest-neighbor (ANN) retrieval.
The solution cannot rely on pairwise similarity scoring or constructing subgraphs for cold items, as these require observed edges.

The goal is to learn a feature-based mapping that aligns intrinsic content semantics with the collaborative structure of the embedding space, effectively bridging the "semantic-collaborative gap."

Methodology: Shallow-RHS Architecture
The authors propose Shallow-RHS, an asymmetric two-tower architecture designed for temporal link prediction. The architecture enforces a strict asymmetry to ensure generalization to cold-start items:

Left-Hand Side (LHS) - Device Tower: This tower encodes the querying device using a combination of intrinsic device features (e.g., device type, country, demographics) and temporally valid message passing over the device's historical watch context ( $N_{<t}(d)$ ). It aggregates information from neighboring content nodes to capture high-order collaborative signals.
Right-Hand Side (RHS) - Content Tower: This tower is intentionally shallow regarding the graph. It encodes target content using only intrinsic features (metadata, taxonomy, LLM-derived semantic embeddings from scripts/synopses). Crucially, it excludes:
- ID-based embeddings.
- Content-side subgraphs.
- Neighbor aggregation.
- Any interaction-derived representations.

This constraint forces the content encoder ( $f_{\theta_c}$ ) to learn a function that maps intrinsic features directly into a CF-aware embedding space. Because the function depends solely on features, it is applicable to both "warm" content (with history) and "cold" content (zero history).

Implicit Graph Completion via Surrogate Neighbors
After training, the system performs an implicit graph completion procedure for cold content:

The learned content encoder generates embeddings for newly ingested cold titles.
An approximate nearest-neighbor index is built over the embeddings of "warm" content.
For each cold title, the system retrieves top- $M$ "warm surrogate neighbors" based on cosine similarity in the learned space.
These surrogates act as behavioral proxies, allowing cold titles to be promoted alongside warm titles without modifying the observed interaction graph.

Device Cold-Start Extension
The same representation-completion principle is applied to new devices. Since new devices lack watch history, the system clusters warm devices into demographic cohorts. For a new device, the system infers its cohort assignment from demographic features and assigns the cohort-level average embedding as the device's initial representation. This enables immediate retrieval against the CF-aware content index.

Key Contributions

Inductive Graph-Completion Formulation: The paper reframes cold-start recommendation as learning a feature-based embedding function for zero-edge nodes, rather than relying on observed graph structure.
Shallow-RHS Architecture: An asymmetric link-prediction model where the content tower is decoupled from the interaction graph, ensuring the encoder generalizes to new items.
Implicit Graph Completion: A retrieval-time procedure that connects cold content to warm surrogate neighbors, operationalizing missing neighborhoods without synthetic edges.
Device Cold-Start via Priors: Extending the representation completion principle to devices using demographic cohort priors.
Production Validation: Large-scale online experiments demonstrating the efficacy of the approach in a real-world streaming environment.

Experimental Results
The authors conducted a series of progressive online A/B tests within Tubi's production system, measuring Total View Time (TVT) and cold-start specific metrics:

Phase 1 (Semantic-to-CF Replacement): Replacing a pure semantic baseline with Shallow-RHS yielded a +0.10% global TVT lift and a 13% increase in cold-title promotion speed.
Phase 2 (Metadata & Calibration): Enriching feature coverage (genre, budget, popularity signals) and calibrating promotion logic resulted in a +0.16% TVT lift.
Phase 3 (Feature Completion): Further reducing missing values in key attributes led to the highest gain, a +0.42% global TVT lift, highlighting the importance of feature quality for zero-edge generalization.
Phase 4 (Surrogate Completion): Adding target-audience descriptors and using LLM embeddings as a fallback for long-tail titles provided an additional +0.17% lift.
Device Cold-Start: The cohort-based device retrieval strategy improved qualified view days by +0.29%, daily TVT by +0.39%, and homepage conversion by +0.43%.

Similarity distribution analysis confirmed that Shallow-RHS shifts cold-start item similarities from a low-similarity regime (typical of pure CF) or a neutral regime (pure semantic) to a right-skewed, higher-similarity distribution, indicating successful alignment with collaborative behavior.

Significance
The paper claims that cold-start recommendation can be effectively treated as an implicit graph completion task. By learning a CF-aware semantic embedding function from warm interactions, the system can immediately generate valid representations for new content and devices. The significance lies in the practical framework provided for reconstructing missing graph representations using side-information priors, enabling immediate, high-quality retrieval for cold-start entities in a production-scale system without waiting for interaction data to accumulate.