Technical Summary: RankGraph-2

Problem Statement

Deploying graph-based retrieval at the billion-node scale for recommendation systems requires solving three tightly coupled problems: graph construction, representation learning, and real-time serving. Existing work typically addresses these stages in isolation. Academic research often optimizes model architectures on small, static graphs, while industrial systems advance training infrastructure but assume the input graph is given and ignore serving costs. This siloed approach creates bottlenecks:

• Construction: Naively constructing full co-engagement graphs for billion-node systems results in hundreds of trillions of edges, making storage and processing infeasible.
• Training: Training on such massive graphs often requires expensive online graph infrastructure (e.g., distributed sampling engines) to handle neighborhood extraction in real-time.
• Serving: Serving embeddings via online Approximate Nearest Neighbor (KNN) search for dynamic user pools (e.g., active users in the last 15 minutes) requires thousands of machines, creating prohibitive latency and cost.

The paper argues that optimizing any single stage without considering the constraints of the others leads to suboptimal outcomes. The core challenge is how to co-design construction, training, and serving when the graph has billions of nodes and hundreds of trillions of potential edges.

Methodology: Lifecycle Co-Design

RankGraph-2 is a unified framework that co-designs all three lifecycle stages for similarity-based retrieval (User-to-User-to-Item [U2U2I] and User-to-Item-to-Item [U2I2I]). The system operates on the principle that requirements from downstream stages (serving, training) should shape upstream stages (construction).

1. Graph Construction (Upstream)

To satisfy the needs of training (self-contained data) and serving (hour-level freshness), the construction pipeline performs the following:

• Heterogeneous Graph Schema: Constructs a graph with three edge types derived solely from engagement data (clicks, likes, shares, purchases): User-Item (U-I), User-User (U-U), and Item-Item (I-I).
• Popularity Bias Correction: Adjusts I-I edge weights to prevent popular items from dominating representations. The weight is scaled by a factor inversely proportional to the target item's popularity, ensuring tail items are not overshadowed.
• Edge Subsampling: Reduces the graph from hundreds of trillions of edges to hundreds of billions. This involves retaining high-value nodes for U-U edges and keeping the top-weighted edges ($K_{CAP}$) for each node.
• Pre-computed Neighborhoods: Instead of online sampling, the system uses Personalized PageRank (PPR) on the "backbone" graph to pre-compute the $K_{IMP}$ most important multi-hop neighbors for each node. For nodes lacking same-type neighbors, KNN on previous embeddings is used as a fallback.
• Output: The pipeline produces "edge-centric" data where each record contains the edge, node features, and pre-computed neighbors, ready for direct ingestion without online graph storage. The entire pipeline completes within one hour, enabling a 3-hour refresh cycle.

2. Model Training (Midstream)

The training phase ingests the pre-computed, self-contained data, eliminating the need for online graph infrastructure (no graph storage or distributed sampling engines).

• Architecture: Uses a simple heterogeneous aggregator with multi-head encoders for users and items. It generalizes to unseen nodes (inductive setting).
• Objective: Combines margin ranking loss and InfoNCE loss for contrastive link prediction.
• Co-Learning: Crucially, the training process co-learns a cluster index alongside the embeddings. The model optimizes not just for embedding quality but also for the quality of the reconstructed embedding via a residual quantization objective.
• Regularization: To prevent "codebook collapse" (where a few codes are overused) during continuous training, the system employs:
  • Regularization Loss: Penalizes the current batch for reinforcing frequently used codes based on an empirical distribution from past batches.
  • Biased Code Selection: Selects codes that favor underused entries, acting as an exploration mechanism.

3. Real-Time Serving (Downstream)

The serving strategy replaces expensive online KNN with a cluster-based approach driven by the co-learned index.

• Cluster Assignment: Each user is assigned a hierarchical cluster code via residual quantization.
• U2U2I Retrieval: Instead of searching for similar users, the system reads the latest items from the cluster queue of the target user's assigned cluster. This queue is maintained by recently active members of that cluster.
• Efficiency: This reduces U2U2I retrieval to a simple lookup, eliminating the need for online KNN over dynamic user pools.

Key Contributions

1. Lifecycle Co-Design Framework: Identifies and implements a framework where serving, training, and construction requirements cascade across stages, unlocking performance unattainable by independent optimization.
2. Graph-Infra-Free Training: Demonstrates that similarity-based retrieval does not require online graph infrastructure. Pre-computed neighborhoods (via PPR) yield quality comparable to online sampling, allowing training on standard ML infrastructure.
3. Heterogeneous Graph Construction: Proposes a graph derived entirely from engagement data with three edge types (U-U, I-I, U-I), featuring popularity bias correction and PPR-based neighbor pre-computation.
4. Co-Learned Cluster Index: Develops a residual-quantization index with novel regularization and biased code selection to prevent codebook collapse, reducing serving costs by 83%.
5. Performance Gains: Shows that a simple architecture, when co-designed, significantly outperforms complex baselines (GAT + Deep Graph Infomax and PyTorch-BigGraph) in recall and online metrics.

Results

The system was deployed across multiple surfaces at Meta, serving billions of users.

• Offline Recall:
  • User Embeddings: RankGraph-2 achieved 3.8× higher Recall@5 than a GAT + Deep Graph Infomax model (which used a more complex architecture but a simpler bipartite graph).
  • Item Embeddings: Achieved 2.1× higher Recall@100 than PyTorch-BigGraph on item retrieval.
• Online A/B Tests (14-day):
  • Delivered up to +0.96% CTR and +2.75% CVR for U2I2I retrieval.
  • Showed consistent improvements for U2U2I retrieval.
• Infrastructure Cost:
  • Reduced U2U serving infrastructure cost by 83% by replacing online KNN with the co-learned cluster index.
• Deployment: Powered 20+ retrieval launches across major Meta surfaces.

Significance and Claims

The paper claims that the primary driver of performance is lifecycle co-design, not model complexity. By moving neighborhood computation offline, the system unlocks operations (multi-hop PPR, popularity correction, heterogeneous edge construction) that are infeasible in online settings due to latency and infrastructure constraints.

The authors argue that for similarity-based retrieval, the conventional approach of investing in online graph infrastructure to support complex GNNs may be the wrong trade-off. Instead, investing in high-quality offline graph construction on standard ML infrastructure yields both superior retrieval quality and lower operational costs. The paper positions RankGraph-2 not as a competitor to generative foundation models, but as a complementary structural prior that captures global collaborative structure, which can be combined with temporal intent models for downstream ranking.