We study a matrix completion problem that leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that users are categorized into clusters, each of which comprises sub-clusters (or what we call 'groups'). We consider a low-rank matrix model for the rating matrix, and a hierarchical stochastic block model that well respects practically-relevant social graphs. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. Furthermore, we develop a matrix completion algorithm and empirically demonstrate via extensive experiments that the proposed algorithm achieves the optimal sample complexity.
|Original language||English (US)|
|Title of host publication||2022 IEEE International Symposium on Information Theory, ISIT 2022|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||6|
|State||Published - 2022|
|Event||2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland|
Duration: Jun 26 2022 → Jul 1 2022
|Name||2022 IEEE International Symposium on Information Theory (ISIT)|
|Conference||2022 IEEE International Symposium on Information Theory, ISIT 2022|
|Period||6/26/22 → 7/1/22|
Bibliographical noteFunding Information:
The work of A. Elmahdy and S. Mohajer is supported in part by the National Science Foundation under Grants CCF-1749981. A. Elmahdy and J. Ahn contributed equally to this work.
© 2022 IEEE.