Reviews: Binary Rating Estimation with Graph Side Information

Summary of paper: The paper considers the problem of completing a binary rating matrix, and theoretically studies whether side information in terms of graphs among users or items aid in the matrix completion task. On a technical level, the study assumes that the users belong to two communities, and users in the same group rate all items identically (upto some noise). The community structure is further revealed by the side information in terms of a graph generated from stochastic block model. The paper derives the optimal sample complexity for rating estimation in terms of the expected number of ratings that needs to be seen to exactly recover the rating matrix. Review summary: The paper is a solid piece of theoretical work and clearly written.