Abstract
Graph knowledge has been proven effective in enhancing item rankings in recommender systems (RecSys), particularly during the retrieval stage. However, its application in the ranking stage, especially when richer contextual information in user-item interactions is available, remains underexplored. A major challenge lies in the substantial computational cost associated with repeatedly retrieving neighborhood information from billions of items stored in distributed systems. This resource-intensive requirement makes it difficult to scale graph-based methods in practical RecSys. To bridge this gap, we first demonstrate that incorporating graphs in the ranking stage improves ranking qualities. Notably, while the improvement is evident, we show that the substantial computational overheads entailed by graphs are prohibitively expensive for real-world recommendations. In light of this, we propose a non-parametric strategy that utilizes graph convolution for re-ranking only during test time. Our strategy circumvents the notorious computational overheads from graph convolution during training, and utilizes structural knowledge hidden in graphs on-the-fly during testing. It can be used as a plug-and-play module and easily employed to enhance the ranking ability of various ranking layers of a real-world RecSys with significantly reduced computational overhead. Through comprehensive experiments across four benchmark datasets with varying levels of sparsity, we demonstrate that our strategy yields noticeable improvements (i.e., 8.1% on average) during testing time with little to no additional computational overheads (i.e., 0.5% on average).
Introduction: The Challenge of Graph-Based Ranking
Modern recommendation systems typically operate in two stages: retrieval, where billions of items are filtered down to a few thousand, and ranking, where those candidates are sorted using complex models and rich contextual features. While Graph Neural Networks (GNNs) have revolutionized retrieval by capturing high-order relationships, they face a significant bottleneck in the ranking stage: prohibitive computational cost.
In production environments, repeatedly fetching neighborhood information during the training of complex ranking models requires massive communication bandwidth between distributed machines. This quadratic complexity makes standard GNN-based ranking impractical for large-scale deployment. This research addresses the question: How can we benefit from the structural knowledge of graphs in the ranking stage without the massive training and engineering overhead?
Proposed Method: Test-Time Augmentation
We introduce a non-parametric graph convolution strategy that injects graph-based structural knowledge only at test-time. Instead of training a model directly on a graph, we use a well-trained "base" ranking model (such as DCN or DeepFM) and refine its predictions using the graph structure during inference.
As illustrated in Figure 1, the process follows four distinct steps:
- Construct Similarity Matrices: Pre-compute user-user and item-item similarity matrices based on the interaction graph.
- Retrieve Candidates: For a specific query (User $u$, Item $i$), identify the top-$n_k$ most similar users and items.
- Construct Augmented Pairs: Form a set of $n_k^2$ relevant user-item pairs (e.g., "similar user" + "similar item").
- Label Aggregation: Query the base ranking model for these pairs and aggregate scores using a pair-wise weighted fusion.
This approach is "non-parametric" because the graph component lacks learnable weights; it simply leverages existing topology to "smooth" a black-box model's output with signals from its neighbors.
Experimental Results
We evaluated this strategy on four benchmark datasets: Yelp2018 (very sparse), Amazon-Books (sparse), MovieLens-1M (dense), and Anime (dense).
Performance and Efficiency
The strategy consistently improved ranking metrics (NDCG and Recall) across all models and datasets, with an average performance boost of 8.1%. Crucially, as shown in Figure 3, our method achieves these gains with negligible overhead. Compared to a naive GNN ranking approach—which can increase training time by ~480% and inference by ~600%—the proposed method introduces zero additional training time and only a 0.5% increase in total time (training + inference).
Key Insights
- Sparsity Compensation: The largest gains were observed on sparse datasets (Yelp and Amazon). By "borrowing" signals from neighbors at test time, the system compensates for the lack of training data in the base model.
- Plug-and-Play Versatility: Because the method treats the ranking model as a black box, it can be applied to almost any existing architecture (e.g., DCN, DeepFM, AutoInt) without re-training.
- Robustness: The pair-wise aggregation mechanism ensures the original prediction remains the primary signal, preventing neighbor noise from overwhelming the output.
Conclusion and Future Work
This work demonstrates that graph-based collaborative signals can be effectively captured at the inference stage, bypassing the distributed computing bottlenecks of industrial GNNs. While highly efficient, future work could further optimize inference latency for ultra-low-latency environments and explore dynamic similarity updates for real-time systems where user interests shift rapidly.
Summary updated