Non-parametric Graph Convolution for Re-ranking in Recommendation Systems

Zhongyu Ouyang, Mingxuan Ju, Soroush Vosoughi, Yanfang Ye

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:

  1. 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.
  2. Retrieving Relevant Candidates: For a given user (or item), the top-k most similar users (or items) are identified from the respective similarity matrices.
  3. 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.
  4. 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 smaller nk values are better for dense graphs, while larger nk values benefit sparse graphs. Further research could explore more adaptive ways to select nk.
  • 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

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). Code: https://github.com/zyouyang/RecSys2025_NonParamGC.git
BibTeX
@inproceedings{ouyang2025non,
  author = {Zhongyu Ouyang and Mingxuan Ju and Soroush Vosoughi and Yanfang Ye},
  title = {{Non-parametric Graph Convolution for Re-ranking in Recommendation Systems}},
  booktitle = {RecSys},
  year = {2025},
  doi = {10.1145/3705328.3748058},
}

Loading related content...

Figure