Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information

Changhun Jo, Kangwook Lee
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:5107-5117, 2021.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-jo21a, title = {Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information}, author = {Jo, Changhun and Lee, Kangwook}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {5107--5117}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/jo21a/jo21a.pdf}, url = {https://proceedings.mlr.press/v139/jo21a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information %A Changhun Jo %A Kangwook Lee %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-jo21a %I PMLR %P 5107--5117 %U https://proceedings.mlr.press/v139/jo21a.html %V 139 %X 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.
APA
Jo, C. & Lee, K.. (2021). Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:5107-5117 Available from https://proceedings.mlr.press/v139/jo21a.html.

Related Material