Technical Program

Paper Detail

Paper IDL.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

Visit Website!