矩阵补全的算法矩阵补全原理

本文介绍的是ICLR2020入选论文《INDUCTIVE MATRIX COMPLETION BASED ON GRAPH NEURAL NETWORKS》（基于图神经网络的归纳矩阵补全）。文章来自华盛顿大学圣路易斯分校博士、Facebook AI 研究院研究科学家张牧涵。
文 | 张牧涵
编 | 丛末

下载链接：
https://openreview.net/pdf?id=ByxxgCEYDS
代码地址：
https://github.com/muhanzhang/IGMC
1 摘要
矩阵补全(Matrix Completion)被广泛应用于推荐系统中。传统的矩阵分解(Matrix Factorization)方法为转导推理模型(Transductive Model)，所学习到的embedding不能推广到训练集中未出现过的用户(user)和商品(item) 。而 Inductive Matrix Completion (IMC) 模型使用内容信息(content)来补全矩阵，缺点是对内容的质量要求很高，且在内容质量不好的情况下会导致远低于矩阵分解的性能。
本文提出一种新的Inductive Graph-based Matrix Completion (IGMC) 模型，在保持归纳推理(inductive reasoning)的同时，完全不借助任何内容信息。能不借助内容信息达成归纳推理的秘诀就在于子图结构。IGMC为每一个(user, item) pair提取一个包含子图(enclosing subgraph)，并用图神经网络(graph neural network)训练一个由子图结构映射到用户对商品评分(rating)的回归模型。
IGMC在多个数据集上取得了最先进的性能；它不仅能够适用于没在训练集中出现的用户和商品，更可以迁移(transfer)到新数据上。我们使用一个在MovieLens上训练的IGMC模型去预测豆瓣电影评分，取得了非常好的性能，甚至好于许多专门在豆瓣数据上训练的模型。
2 动机
只要我们把每个user或item看成一个节点(node)，每个rating看成一个边(edge)，则矩阵补全可以看成是在二分图(bipartite graph)上的链路预测(link prediction)问题。不同于传统链路预测只关注预测存在性(link existence)，这里我们要预测链路的值(link value)，也就是用户对商品的评分。
首先，我们定义包含子图(enclosing subgraph) 。对一个(user, item) pair，它们的h阶包含子图是由该user、 item，所有该user、 item的h-hop内邻接节点（包含h-hop），以及所有这些节点之间的边组成的图。这样的一个包含子图内存在大量对于预测评分有用的信息。举例来说，即使只用一阶包含子图，我们也可以获得比如用户平均评分、商品平均评分、商品累计评价次数，以及大量的基于路径(path)等的结构信息。参加图一。
一个简单的基于路径的结构特征如下，假如我们想知道用户u0对于商品v0的评分，我们可以看有多少和u0品味相似的用户u1对v0打了高分；而品味相似可以用是否这个u1和u0曾经都给某个其它的商品v1打过高分。总结下来，这样的一个路径特征即为：

我们可以通过查有多少这样的路径来估算u0是否会给v0高分。而且，所有这样的路径都被包含在一阶包含子图(1-hop enclosing subgraph)中。

我们相信类似这样的结构特征数不胜数。因此，与其手动定义大量这样的启发式特征(heuristics)，不如直接将一阶包含子图输入给一个图神经网络，用图神经网络强大的图特征学习能力来自动学习更通用的、更有表达能力的特征。我们使用图神经网络训练一个由包含子图映射到评分的回归模型，实验证明，这种新的方法可以精确地预测评分。
3 方法
提取每个包含子图后，我们首先要对其中的节点进行标注(node labeling) 。目的是为了区分子图中节点的不同角色。比如我们要区分目标节点(target user/item)和背景节点 (context nodes) 。目标节点标示出我们到底要预测子图中哪一对(user, item)之间的评分。同时，我们可以区分不同阶的邻居节点，比如一阶邻居(1-hop neighbors)和二阶邻居(2-hop neighbors)对目标节点的贡献程度并不相同。
我们采用了一个简单的做法，对目标用户(target user)，我们标注为0，对目标商品(target item)，我们标注为1；对i-hop的背景用户我们标注为2i，对i-hop的背景商品我们标注为2i+1 。之后，我们将这些标注转化为one-hot encoding vector，作为每个节点的初始特征输入给图神经网络。
在图神经网络(GNN)中，我们采用relational graph convolutional operator (R-GCN)作为卷积层，因为R-GCN可以从边类型中学习。

【矩阵补全的算法矩阵补全原理】其中，代表节点在第层的特征向量，和为可学习的参数，代表rating(一般从中选择，代表与节点以类型边相连的邻居节点。
多层卷积后，我们将每一层结果相连得到每个节点的最终表示：

最后，我们取目标用户和目标商品的相连的表示作为这个包含子图的最终表示：

并训练一个两层神经网络(MLP)从子图表示回归到目标评分(rating) 。
4 实验结果

我们仅使用一阶包含子图训练IGMC 。首先，在Table 2中我们展示了在Flixster, Douban和YahooMusic上的RMSE性能。我们的IGMC模型取得了state-of-the-art性能，超过了近期的其他基于图神经网络的模型。

在Table 3中我们展示IGMC在ML-100K 和 ML-1M上的性能。在ML-100K上，IGMC取得了最好的性能，和之前领先的一种转导模型GC-MC性能相同。但是注意，GC-MC使用了额外的内容(content)特征，而IGMC完全依靠子图结构。GC-MC在不使用content的情况下RMSE为0.910 。在ML-1M上，IGMC仍落后于其他一些转导推理的方法。我们接下来深入研究这一问题。

对于ML-1M数据集，我们分别将训练矩阵稀疏为0.2, 0.1, 0.05, 0.01和0.001倍。Figure 2比较了GC-MC和IGMC在不同稀疏程度下的性能对比。我们发现，虽然IGMC在sparsity=1时落后于GC-MC，但是此后IGMC在不同sparsity下都优于GC-MC，而且矩阵越稀疏，性能优势越明显。我们猜测，基于子图特征学习的IGMC对稀疏矩阵更鲁棒；而基于矩阵分解等的转导模型需要矩阵较为致密(dense)才能有好的性能。这也暗示了IGMC在数据稀疏的推荐系统中的潜力。

最后，我们测试IGMC的迁移学习性能。我们直接将ML-100K上训练的IGMC模型用于预测Flixster, Douban和YahooMusic 。出人意料，迁移的IGMC模型取得了极强的性能，甚至好于一些专门在这三个数据集上训练的模型。这说明，不同推荐任务共享了大量相同的子图模式。

为验证这点，我们可视化了一些真实的包含子图，见Figure 3 。可以发现，高评分和低评分对应的包含子图确实有着明显的不同；且不同数据集之间共享许多相似的子图模式。
5 总结
本文提出了一种通过子图特征进行归纳推理(inductive reasoning)的矩阵补全模型，IGMC 。
通过本文我们证明了仅从一阶包含子图学习图特征即可在许多数据集上达到领先的性能，这似乎暗示更高阶的连接关系并没有特别多的额外价值。
此外，我们也证明了不借助于内容(content)的inductive matrix completion (IMC)方法是同样可行的且大大超越了传统的借助内容的IMC方法。IGMC的许多特性，比如迁移性、稀疏鲁棒性等都暗示了它的强大潜力。我们希望IGMC能为矩阵补全和推荐系统领域带来新的想法和启发。
另外，借助子图特征的链路预测方法已经获得了巨大的成功，参见我们的另一篇文章“Link Prediction Based on Graph Neural Networks” ：

矩阵补全的算法 矩阵补全原理

矩阵补全的算法矩阵补全原理