All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

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