The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs

Adel Elmahdy; Junhyung Ahn; Soheil Mohajer; Changho Suh

doi:10.1109/ISIT50566.2022.9834449

The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs

Adel Elmahdy
, Junhyung Ahn
, Soheil Mohajer
, Changho Suh

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

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	https://doi.org/10.1109/ISIT50566.2022.9834449
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.

Publisher link

10.1109/ISIT50566.2022.9834449

Find It

Find It at U of M Libraries

Cite this

Elmahdy, A., Ahn, J., Mohajer, S., & Suh, C. (2022). The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs. In 2022 IEEE International Symposium on Information Theory, ISIT 2022 (pp. 2409-2414). (2022 IEEE International Symposium on Information Theory (ISIT)). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT50566.2022.9834449

The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs. / Elmahdy, Adel; Ahn, Junhyung; Mohajer, Soheil et al.
2022 IEEE International Symposium on Information Theory, ISIT 2022. Institute of Electrical and Electronics Engineers Inc., 2022. p. 2409-2414 (2022 IEEE International Symposium on Information Theory (ISIT)).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Elmahdy, A, Ahn, J, Mohajer, S & Suh, C 2022, The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs. in 2022 IEEE International Symposium on Information Theory, ISIT 2022. 2022 IEEE International Symposium on Information Theory (ISIT), Institute of Electrical and Electronics Engineers Inc., pp. 2409-2414, 2022 IEEE International Symposium on Information Theory, ISIT 2022, Espoo, Finland, 6/26/22. https://doi.org/10.1109/ISIT50566.2022.9834449

Elmahdy A, Ahn J, Mohajer S, Suh C. The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs. In 2022 IEEE International Symposium on Information Theory, ISIT 2022. Institute of Electrical and Electronics Engineers Inc. 2022. p. 2409-2414. (2022 IEEE International Symposium on Information Theory (ISIT)). doi: 10.1109/ISIT50566.2022.9834449

@inproceedings{b57d86c6280b406f90896e2edfd5c309,

title = "The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs",

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.",

author = "Adel Elmahdy and Junhyung Ahn and Soheil Mohajer and Changho Suh",

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: {\textcopyright} 2022 IEEE.; 2022 IEEE International Symposium on Information Theory, ISIT 2022 ; Conference date: 26-06-2022 Through 01-07-2022",

year = "2022",

doi = "10.1109/ISIT50566.2022.9834449",

language = "English (US)",

series = "2022 IEEE International Symposium on Information Theory (ISIT)",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2409--2414",

booktitle = "2022 IEEE International Symposium on Information Theory, ISIT 2022",

}

TY - GEN

T1 - The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs

AU - Elmahdy, Adel

AU - Ahn, Junhyung

AU - Mohajer, Soheil

AU - Suh, Changho

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

PY - 2022

Y1 - 2022

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

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

UR - https://www.scopus.com/pages/publications/85136283139

UR - https://www.scopus.com/pages/publications/85136283139#tab=citedBy

U2 - 10.1109/ISIT50566.2022.9834449

DO - 10.1109/ISIT50566.2022.9834449

M3 - Conference contribution

AN - SCOPUS:85136283139

T3 - 2022 IEEE International Symposium on Information Theory (ISIT)

SP - 2409

EP - 2414

BT - 2022 IEEE International Symposium on Information Theory, ISIT 2022

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2022 IEEE International Symposium on Information Theory, ISIT 2022

Y2 - 26 June 2022 through 1 July 2022

ER -

The Optimal Sample Complexity of Matrix Completion with Hierarchical Similarity Graphs

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this