TL;DR
This paper introduces a novel "non-parametric graph convolution" strategy that significantly boosts the performance of recommender systems' re-ranking stage without incurring the prohibitive computational costs of traditional graph-based methods during training. By cleverly leveraging graph structures only at test time, the approach offers a practical and scalable way to enhance recommendation quality.
What Problem Does This Paper Address?
Recommender systems (RecSys) typically operate in two stages: retrieval (quickly narrowing down a vast item catalog) and re-ranking (applying more sophisticated models to order the remaining candidates). While graph neural networks (GNNs) have shown promise in improving the retrieval stage by capturing user-item interaction patterns, their application in the re-ranking stage has been hindered by substantial computational overhead. Specifically, incorporating graph convolutions during the training of complex re-ranking models, which often deal with billions of users and items in distributed systems, becomes prohibitively expensive. This paper aims to bridge this gap by finding an efficient way to inject graph knowledge into the re-ranking process without this training bottleneck.
Methods
The core contribution is a "non-parametric graph convolution" strategy that operates exclusively at test time. This approach bypasses the need for graph-based training altogether. The strategy involves four key steps:
- Constructing Similarity Matrices: Two similarity matrices are built – one for users and one for items – based on their co-occurrence in interactions. These matrices capture collaborative filtering signals.
- Retrieving Relevant Candidates: For a given user (or item), the top-k most similar users (or items) are identified from the respective similarity matrices.
- Constructing Relevant User-Item Pairs: The retrieved similar users and items are combined to form a set of "relevant" user-item pairs. The weight assigned to each pair is a product of the user-user and item-item similarity scores.
- Label Aggregation Among Relevant Ranking Scores: The original, pre-trained re-ranking model is queried for each of these relevant user-item pairs to obtain their predicted interaction probabilities. These probabilities are then aggregated using a weighted sum, where the weights are derived from the similarity scores. A specific adjustment is made to the weight of the most similar pair to prevent it from being overly diluted.
This method is designed to be a "plug-and-play" module, meaning it can be applied to any existing, well-trained re-ranking model without requiring re-training or significant architectural changes.
Datasets
The authors evaluated their approach on four publicly available benchmark datasets:
- Yelp2018: Relatively sparse.
- Amazon-Books: Relatively sparse.
- MovieLens-1M: Relatively dense.
- Anime: Relatively dense.
These datasets were split into training, validation, and testing sets with an 80/10/10 ratio. Explicit ratings were converted to binary labels.
Key Insights and Ideas
- Test-Time Augmentation for Graphs: The most significant insight is the shift from integrating graph knowledge during training to leveraging it solely during inference. This elegantly sidesteps the computational bottleneck.
- Modularity and Scalability: The non-parametric nature of the approach makes it highly modular. It can be easily integrated into existing industrial RecSys pipelines without major overhauls, addressing a key practical challenge.
- Graph Knowledge Benefits Sparse Data More: The strategy shows more pronounced improvements on sparser datasets. This is because in sparse scenarios, user/item embeddings might be less well-trained due to fewer interactions, and the test-time graph information can effectively compensate.
- Controlled Contribution of Similar Pairs: The method carefully balances the influence of the most similar user-item pair with other relevant pairs, preventing the original prediction from being overly skewed while still giving it significant weight.
Key Results
- Performance Improvement: The proposed strategy consistently improved the ranking performance of baseline models across all four datasets. On average, they observed an 8.1% improvement in ranking metrics.
- Computational Efficiency: The most striking result is the minimal computational overhead. The strategy introduced only about 0.5% additional computational overhead on average during testing time, compared to the naive graph-enhanced approach which incurred up to a ~1000% increase in training time.
- Effectiveness Across Models: The strategy proved effective when applied to various baseline re-ranking models, including NFM, DeepFM, xDeepFM, DCN, DCNV2, AutoInt, and EulerNet.
Limitations and Future Work
- Hyperparameter Tuning (nk): The performance is sensitive to the choice of
nk(the number of neighbors considered). The paper suggests that smallernkvalues are better for dense graphs, while largernkvalues benefit sparse graphs. Further research could explore more adaptive ways to selectnk. - Pre-computation of Similarity Matrices: While the test-time inference is efficient, the initial construction of similarity matrices and retrieval of candidates might still require significant computation, especially for very large graphs. However, these can be pre-computed offline.
- Future Work: The authors suggest exploring more sophisticated aggregation mechanisms beyond weighted averaging and investigating how this strategy can be applied to other recommendation tasks beyond CTR prediction.
Summary updated