| Paper ID | D5-S2-T3.3 |
| Paper Title |
When to Use Graph Side Information in Matrix Completion |
| Authors |
Geewon Suh, Sangwoo Jeon, Changho Suh, Korea Advanced Institute of Science and Technology, Korea (South) |
| Session |
D5-S2-T3: Reconstruction on Graphs |
| Chaired Session: |
Friday, 16 July, 22:20 - 22:40 |
| Engagement Session: |
Friday, 16 July, 22:40 - 23:00 |
| Abstract |
We consider a matrix completion problem that leverages graph as side information. One common approach in recently developed efficient algorithms is to take a two-step procedure: (i) clustering communities that form the basis of the graph structure; (ii) exploiting the estimated clusters to perform matrix completion together with iterative local refinement of clustering. A major limitation of the approach is that it achieves the information-theoretic limit on the number of observed matrix entries, promised by maximum likelihood estimation, only when a sufficient amount of graph side information is provided (the quantified measure is detailed later). The contribution of this work is to develop a computationally efficient algorithm that achieves the optimal sample complexity for the entire regime of graph information. The key idea is to make a careful selection for the information employed in the first clustering step, between two types of given information: graph & matrix ratings. Our experimental results conducted both on synthetic and real data confirm the superiority of our algorithm over the prior approaches in the scarce graph information regime.
|
