  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.
