  We consider a matrix completion problem that exploits social or item
similarity graphs as side information. We develop a universal, parameter-free,
and computationally efficient algorithm that starts with hierarchical graph
clustering and then iteratively refines estimates both on graph clustering and
matrix ratings. Under a hierarchical stochastic block model that well respects
practically-relevant social graphs and a low-rank rating matrix model (to be
detailed), we demonstrate that our algorithm achieves the information-theoretic
limit on the number of observed matrix entries (i.e., optimal sample
complexity) that is derived by maximum likelihood estimation together with a
lower-bound impossibility result. One consequence of this result is that
exploiting the hierarchical structure of social 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. We conduct
extensive experiments both on synthetic and real-world datasets to corroborate
our theoretical results as well as to demonstrate significant performance
improvements over other matrix completion algorithms that leverage graph side
information.
