矩阵补全的算法矩阵补全原理 _云知道

本文介绍的是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)对目标节点的贡献程度并不相同。