Abstract
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. |
| Pages | 2409-2414 |
| Number of pages | 6 |
| ISBN (Electronic) | 9781665421591 |
| DOIs | |
| State | Published - 2022 |
| Event | 2022 IEEE International Symposium on Information Theory, ISIT 2022 - Espoo, Finland Duration: Jun 26 2022 → Jul 1 2022 |
Publication series
| Name | 2022 IEEE International Symposium on Information Theory (ISIT) |
|---|
Conference
| Conference | 2022 IEEE International Symposium on Information Theory, ISIT 2022 |
|---|---|
| Country/Territory | Finland |
| City | Espoo |
| Period | 6/26/22 → 7/1/22 |
Bibliographical note
Funding 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.
Publisher Copyright:
© 2022 IEEE.