We study a matrix completion problem that leverages a hierarchical structure of social similarity graphs as side information in the context of recommender systems. We assume that the users are categorized into clusters, each of which comprises sub-clusters (or what we call “groups”). We consider a hierarchical stochastic block model that well respects practically-relevant social graphs and follows a low-rank rating matrix model. Under this setting, we characterize the information-theoretic limit on the number of observed matrix entries (i.e., optimal sample complexity) as a function of the quality of graph side information (to be detailed) by proving sharp upper and lower bounds on the sample complexity. One important consequence of this result is that leveraging the hierarchical structure of similarity graphs yields a substantial gain in sample complexity relative to the one that simply identifies different groups without resorting to the relational structure across them. Another implication of the result is when the graph information is rich, the optimal sample complexity is proportional to the number of clusters, while it nearly stays constant as the number of groups in a cluster increases. Furthermore, we also develop a matrix completion algorithm that consists of three stages: (i) initial estimates of clusters and groups; (ii) recovery of ratings; and (iii) iterative local refinement of groups. We empirically demonstrate via extensive experiments that the proposed algorithm achieves the optimal sample complexity.
추천시스템은 사용자가 선호할 것 같은 아이템을 추천해주는 시스템으로 머신러닝 및 데이터마이닝 분야에서 많은 주목을 받고 있다. 이 시스템은 사용자의 과거 정보(예: 사용자가 영화에 매긴 평점)를 분석하여 사용자의 성향을 파악, 아이템을 추천해주는 방식으로 작동하는데, 이는 행렬채움 문제와 유사하다. 하지만, 추천시스템에는 문제점이 존재하는데 이는 관측가능한 정보가 매우 적을 때 관측 데이터로부터 사용자의 성향을 파악하기가 어렵다는 것이다. 이를 해결하기 위해 기존 연구들은 소셜그래프를 활용하여 더욱 정확히 사용자의 성향을 파악하는 방안을 제시하였다. 하지만, 이에 관한 이론적인 연구는 아직 부족한 상황이다. 본 논문에서는 완벽한 행렬채움을 위해 필요한 최소한의 정보량을 규명하였고, 이 과정에서 소셜그래프가 미치는 영향을 파악하였다. 또한, 최소한의 정보량을 활용하는 행렬채움 알고리즘을 고안하였고, 실제 데이터셋에 대해 다른 행렬채움 알고리즘보다 성능이 좋은 것을 보였다.
