Rating Prediction via Graph Signal Processing

Abstract

This paper develops new designs for recommendation systems inspired by recent advances in graph signal processing. Recommendation systems aim to predict unknown ratings by exploiting the information revealed in a subset of user-item observed ratings. Leveraging the notions of graph frequency and graph filters, we demonstrate that classical collaborative filtering methods, such as k -nearest neighbors (NN), can be modeled as a specific band-stop graph filter on networks describing similarities between users or items. We also demonstrate that linear latent factor (LF) models, such as low-rank matrix completion, can be viewed as bandlimited interpolation algorithms that operate in a frequency domain given by the spectrum of a joint user and item network. These new interpretations pave the way to new methods for enhanced rating prediction. For NN-based collaborative filtering, we develop more general band-stop graph filters, and present a novel predictor, called mirror filtering (MiFi), that filters jointly across user and item networks. For LF, we propose a low complexity method by exploiting the eigenvector of correlation matrices constructed from known ratings. The performance of our algorithms is assessed in the MovieLens 100 k dataset, showing that our designs reduce the root mean-squared error (up to a 6.85% for MiFi) compared to one incurred by the benchmark collaborative filtering approach.