TY - JOUR
T1 - On the Fundamental Limits of Matrix Completion
T2 - Leveraging Hierarchical Similarity Graphs
AU - Ahn, Junhyung
AU - Elmahdy, Adel
AU - Mohajer, Soheil
AU - Suh, Changho
N1 - Publisher Copyright:
© 1963-2012 IEEE.
PY - 2024/3/1
Y1 - 2024/3/1
N2 - We study a matrix completion problem which 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 hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. 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. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.
AB - We study a matrix completion problem which 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 hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. 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. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. We empirically demonstrate through extensive experiments that the proposed algorithm achieves the optimal sample complexity.
KW - Recommender systems
KW - graph side information
KW - matrix completion problem
UR - http://www.scopus.com/inward/record.url?scp=85181555409&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85181555409&partnerID=8YFLogxK
U2 - 10.1109/TIT.2023.3345902
DO - 10.1109/TIT.2023.3345902
M3 - Article
AN - SCOPUS:85181555409
SN - 0018-9448
VL - 70
SP - 2039
EP - 2075
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 3
ER -