Timezone: »

 
Poster
Binary Rating Estimation with Graph Side Information
Kwangjun Ahn · Kangwook Lee · Hyunseung Cha · Changho Suh

Wed Dec 05 07:45 AM -- 09:45 AM (PST) @ Room 210 #64
in Wed Poster Session A »

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.

Keywords: Clustering · Spectral Methods · Information Theory · Large Deviations and Asymptotic Analysis · Collaborative Filtering
[ Paper] 

Author Information

Kwangjun Ahn (Korean Augmentation To the United States Army (KATUSA))
Kangwook Lee (KAIST)

I am a Research Assistant Professor at Information and Electronics Research Institute of KAIST, working with Prof. Changho Suh. Before that, I was a postdoctoral scholar at the same institute. I received my PhD in May 2016 from the Electrical Engineering and Computer Science department at UC Berkeley and my Master of Science degree from the same department in December 2012, both under the supervision of Prof. Kannan Ramchandran. I was a member of Berkeley Laboratory of Information and System Sciences (BLISS, aka Wireless Foundation) and BASiCS Group. I received my Bachelor of Science degree in Electrical Engineering from Korea Advanced Institute of Science and Technology (KAIST) in May 2010.

Hyunseung Cha (Kakao Brain)
Changho Suh (KAIST)

Changho Suh is an Ewon Associate Professor in the School of Electrical Engineering at Korea Advanced Institute of Science and Technology (KAIST). He recevied the B.S. and M.S. degrees in Electrical Engineering from KAIST in 2000 and 2002 respectively, and the Ph.D. degree in Electrical Engineering and Computer Sciences from UC-Berkeley in 2011, under the supervision of Prof. David Tse. From 2011 to 2012, he was a postdoctoral associate at the Research Laboratory of Electronics in MIT. From 2002 to 2006, he had been with the Telecommunication R&D Center, Samsung Electronics. Dr. Suh received the 2015 IEIE Hadong Young Engineer Award, a 2015 Bell Labs Prize finalist, the 2013 IEEE Communications Society Stephen O. Rice Prize, the 2011 David J. Sakrison Memorial Prize (top research award in the UC-Berkeley EECS Department), and the 2009 IEEE ISIT Best Student Paper Award.

More from the Same Authors