Overview
RankGraph-2 is a framework for graph-based retrieval, specifically designed for billion-node scale applications at Meta. The system addresses three interrelated problems: graph construction, representation learning, and real-time serving. Unlike approaches that treat these stages in isolation, RankGraph-2 employs a lifecycle co-design methodology, where the requirements of each stage influence and shape the others. This co-design is applied to similarity-based retrieval scenarios, encompassing User-to-User-to-Item (U2U2I) and User-to-Item-to-Item (U2I2I) recommendations.
Research Context
Existing work on graph-based retrieval often addresses graph construction, representation learning, and real-time serving as separate problems. However, at the billion-node scale required for platforms like Meta, these aspects are tightly coupled. The necessity for real-time serving mechanisms, particularly to avoid computationally expensive online K-Nearest Neighbor (KNN) searches, mandates specific considerations for both representation learning and graph construction. Simultaneously, the computational demands of training necessitate a design that can leverage pre-computed neighborhoods and self-contained data structures.
Approach
The RankGraph-2 framework integrates multiple design considerations across its lifecycle:
- Serving Requirements: To avoid costly online KNN computations, serving necessitates a co-learned cluster index. This requirement pushes the integration of index co-training directly into the overall training objective.
- Training Benefits: For similarity-based retrieval, the system leverages the observation that pre-computed neighborhoods are tolerable. This design choice eliminates the need for online graph infrastructure during training.
- Construction Imperatives: The graph construction process is designed to produce self-contained data, aligning with the training benefits derived from pre-computed neighborhoods. Furthermore, construction must support an hour-level refresh rate to ensure timely item coverage.
Based on these cascading requirements, RankGraph-2 implements specific technical sub-components:
- Graph Reduction and Subsampling: The framework reduces hundreds of trillions of edges to hundreds of billions through a subsampling process that includes popularity bias correction.
- Neighborhood Pre-computation: Multi-hop neighborhoods are pre-computed using a personalized PageRank algorithm.
- Index Co-learning: A residual-quantization cluster index is co-learned to reduce the computational cost of serving.
Findings
The lifecycle co-design inherent in RankGraph-2 leads to a simplified architecture and notable performance improvements:
- The system achieves 3.8 times ($3.8 \times$) higher recall compared to a GAT (Graph Attention Network) + Deep Graph Infomax model when evaluated on a bipartite graph.
- For item retrieval tasks, RankGraph-2 demonstrates 2.1 times ($2.1 \times$) higher recall than PyTorch-BigGraph.
- The framework reduces serving computational cost by 83 percent.
- Deployment within Meta has shown up to +0.96% increase in Click-Through Rate (CTR) and +2.75% increase in Conversion Rate (CVR).
Why This Matters
RankGraph-2's approach to co-designing graph construction, representation learning, and real-time serving for billion-node graphs offers a method for improving the performance and efficiency of recommendation systems. The observed increases in recall, CTR, and CVR, alongside significant reductions in serving computational costs, indicate the practical utility of integrating these stages. The framework has been deployed for over 20 retrieval launches across major surfaces at Meta, demonstrating its applicability in large-scale practical environments.