eduzhai > Applied Sciences > Engineering >

MC2G An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs

  • Save

... pages left unread,continue reading

Document pages: 41 pages

Abstract: We consider a discrete-valued matrix completion problem for recommendersystems in which both the social and item similarity graphs are available asside information. We develop and analyze MC2G (Matrix Completion with 2Graphs), a quasilinear-time algorithm which is based on spectral clustering andlocal refinement steps. We show that the sample complexity of MC2G meets aninformation-theoretic limit that is derived using maximum likelihood estimationand is also order-optimal. We demonstrate that having both graphs as sideinformation outperforms having just a single graph, thus the availability oftwo graphs results in a synergistic effect. Experiments on synthetic datasetscorroborate our theoretical results. Finally, experiments on a sub-sampledversion of the Netflix dataset show that MC2G significantly outperforms otherstate-of-the-art matrix completion algorithms that leverage graph sideinformation.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...