Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information
This work provides theoretical guarantees for recommender systems with graph side information, addressing limitations in prior research for more realistic scenarios.
The paper tackles the problem of estimating latent preference matrices in recommender systems with graph side information by relaxing strict assumptions to allow discrete values and multiple user clusters, achieving optimal sample complexity and improved prediction performance on synthetic and real data.
Incorporating graph side information into recommender systems has been widely used to better predict ratings, but relatively few works have focused on theoretical guarantees. Ahn et al. (2018) firstly characterized the optimal sample complexity in the presence of graph side information, but the results are limited due to strict, unrealistic assumptions made on the unknown latent preference matrix and the structure of user clusters. In this work, we propose a new model in which 1) the unknown latent preference matrix can have any discrete values, and 2) users can be clustered into multiple clusters, thereby relaxing the assumptions made in prior work. Under this new model, we fully characterize the optimal sample complexity and develop a computationally-efficient algorithm that matches the optimal sample complexity. Our algorithm is robust to model errors and outperforms the existing algorithms in terms of prediction performance on both synthetic and real data.