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.

研究了利用社交或项目相似性图作为辅助信息的矩阵完成问题，开发了一种通用、无参数、计算效率高的算法，该算法从分层图聚类开始，然后迭代地在图聚类和矩阵评级上进行估计。在考虑社交图和低秩评级矩阵模型下，我们证明了我们的算法达到了最大似然估计推导的观察矩阵条目数量的信息熵界限（即最优的样本复杂度）。利用社交图的分层结构相对于仅仅识别不同群体而不诉诸它们之间的关系结构可以获得显著的样本复杂度增益。我们在合成和实际数据集上进行了广泛的实验，以验证我们的理论结果，并证明相对于利用图侧信息的其他矩阵完成算法，我们的算法具有显著的性能改进。

使用分层图侧面信息的矩阵补全

Matrix Completion with Hierarchical Graph Side Information

As a fundamental tool in hierarchical graph clustering, computing connected
components has been a central problem in large-scale data mining. While many
known algorithms have been developed for this problem, they are either not
scalable in practice or lack strong theoretical guarantees on the parallel
running time, that is, the number of communication rounds. So far, the best
proven guarantee is $\Oh(\log n)$, which matches the running time in the PRAM
model.
In this paper, we aim to design a distributed algorithm for this problem that
works well in theory and practice. In particular, we present a simple algorithm
based on contractions and provide a scalable implementation of it in MapReduce.
On the theoretical side, in addition to showing $\Oh(\log n)$ convergence for
all graphs, we prove an $\Oh(\log \log n)$ parallel running time with high
probability for a certain class of random graphs. We work in the MPC model that
captures popular parallel computing frameworks, such as MapReduce, Hadoop or
Spark.
On the practical side, we show that our algorithm outperforms the
state-of-the-art MapReduce algorithms. To confirm its scalability, we report
empirical results on graphs with several trillions of edges.

该研究设计了一个分布式算法用于计算连接组件问题，并在 MapReduce 中提供了可扩展的实现。该算法在所有图形上显示 O (log n) 收敛，并对某些随机图形类具有高概率 O (log log n) 并行运行时间。在实践方面，该算法优于现有的 MapReduce 算法，并且在拥有数万亿边缘的图形上具有可扩展性。