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.