矩阵补全的算法（矩阵补全原理）
本文介绍的是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” ：
http://papers.nips.cc/paper/7763-link-prediction-based-on-graph-neural-networks.pdf
ICLR 2020 系列论文解读
0、ICLR 2020 会议动态报道
疫情严重，ICLR2020 将举办虚拟会议，非洲首次 AI 国际顶会就此泡汤
疫情影响，ICLR 突然改为线上模式，2020年将成为顶会变革之年吗？
火爆的图机器学习，ICLR 2020上有哪些研究趋势？
1、直播
回放 | 华为诺亚方舟ICLR满分论文：基于强化学习的因果发现
2、Oral
01. Oral | 一种镜像生成式机器翻译模型：MGNMT
02. Oral | 额外高斯先验目标，缓解负多样性无知
03. Oral | 引入额外门控运算，LSTM稍做修改，性能便堪比Transformer-XL
04. Oral | 并行蒙卡树搜索，性能无损，线性加速，勇闯「消消乐」1000关！
05. Oral | 元强化学习迎来一盆冷水：不比元Q学习好多少
06. Oral | 用群卷积建立深度、等变的胶囊网络
07. Oral | 谷歌推出分布式强化学习框架SEED，性能“完爆”IMPALA，可扩展数千台机器，还很便宜
3、Spotlight
01. Spotlight | 模型参数这么多，泛化能力为什么还能这么强？
02. Spotlight | 公平与精确同样重要！CMU提出学习公平表征方法，实现算法公平
03. Spotlight | 组合泛化能力太差？用深度学习融合组合求解器试试
04. Spotlight | 加速NAS，仅用0.1秒完成搜索
05. Spotlight | 华盛顿大学：图像分类中对可实现攻击的防御（视频解读）
4、Poster
01. Poster | 华为诺亚：巧妙思想，NAS与「对抗」结合，速率提高11倍
02. Poster | 抛开卷积，多头自注意力能够表达任何卷积操作
03. Poster | NAS 太难了，搜索结果堪比随机采样！华为给出 6 条建议
04. Poster | 清华提 NExT 框架，用「神经元执行树」学习可解释性
05. Poster | 谷歌最新研究：用“复合散度”量化模型合成泛化能力
06. Poster | 完胜 BERT，谷歌最佳 NLP 预训练模型开源，单卡训练仅需 4 天
07. Poster | FSNet：利用卷积核概要进行深度卷积神经网络的压缩
08. Poster | “同步平均教学”框架为无监督学习提供更鲁棒的伪标签
09. Poster | 快速神经网络自适应技术