2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | L.1.1 | ||
| Paper Title | Achievability Bounds for Community Detection and Matrix Completion with Two-Sided Graph Side-Information | ||
| Authors | Qiaosheng Zhang, Vincent Y. F. Tan, National University of Singapore, Singapore; Changho Suh, Korea Advanced Institute of Science and Technology, Korea (South) | ||
| Session | L.1: Application-Specific Learning | ||
| Presentation | Lecture | ||
| Track | Statistics and Learning Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | We consider the problem of recovering communities of users and communities of items (such as movies) based on a partially observed rating matrix as well as side-information in the form of similarity graphs of the users and items. The user-to-user and item-to-item similarity graphs are generated according to the celebrated stochastic block model (SBM). We develop a lower bound on the minimum expected number of observed ratings (also known as the sample complexity) needed for this recovery task, which is a function of various parameters including the quality of the graph side-information manifested in the intra- and inter-cluster probabilities of the SBMs. Our information-theoretic results quantify the benefits of the two-sided graph side-information for recovery, and further analysis reveals that the two pieces of graph side information produce an interesting synergistic effect under certain scenarios. This means that if one observes only one of the two graphs, then the required sample complexity worsens to the case in which none of the graphs is observed. Thus both graphs are strictly needed to reduce the sample complexity. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
