Binary Rating Estimation with Graph Side Information

NeurIPS (2018)


Rich experimental evidences show that one can better estimate users’ unknown ratings with the aid of graph side information such as social graphs. However, the gain is not theoretically quantified. In this work, we study the binary rating estimation problem to understand the fundamental value of graph side information. Considering a simple correlation model between a rating matrix and a graph, we characterize the sharp threshold on the number of observed entries required to recover the rating matrix (called the optimal sample complexity) as a function of the quality of graph side information (to be detailed). To the best of our knowledge, we are the first to reveal how much the graph side information reduces sample complexity. Further, we propose a computationally efficient algorithm that achieves the limit. Our experimental results demonstrate that the algorithm performs well even with real-world graphs.


안광준(KATUSA), 이강욱(KAIST), 차현승(카카오브레인), 서창호(KAIST)


recommender systems information theory

발행 날짜