论文标题
MC2G：具有社交和项目相似图的矩阵完成的有效算法
MC2G: An Efficient Algorithm for Matrix Completion with Social and Item Similarity Graphs
论文作者
论文摘要
在本文中，我们设计和分析MC2G（使用2个图形完成矩阵完成），这是一种在存在社交和项目相似性图的情况下执行矩阵完成的算法。 MC2G在准线性时间内运行，并且不含参数。它基于光谱聚类和局部改进步骤。 MC2G成功所需的预期采样条目（即，恢复图中的簇并完成矩阵）与信息理论的下限匹配到广泛参数范围的恒定因子。我们通过对合成数据集和真实数据集进行的广泛实验显示，MC2G优于其他最先进的矩阵完成算法，这些算法利用图形侧面信息。
In this paper, we design and analyze MC2G (Matrix Completion with 2 Graphs), an algorithm that performs matrix completion in the presence of social and item similarity graphs. MC2G runs in quasilinear time and is parameter free. It is based on spectral clustering and local refinement steps. The expected number of sampled entries required for MC2G to succeed (i.e., recover the clusters in the graphs and complete the matrix) matches an information-theoretic lower bound up to a constant factor for a wide range of parameters. We show via extensive experiments on both synthetic and real datasets that MC2G outperforms other state-of-the-art matrix completion algorithms that leverage graph side information.
