## 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.