An Efficient Neighborhood-based Interaction Model for Recommendation on Heterogeneous Graph
1 引言
本文论文作者来自上海交通大学，与亚马逊 aws部门合作，发表于KDD2020，提出了一种基于元路径模型和注意力机制的异质图神经网络的推荐系统模型，并在多个公开数据集上进行实验分析。
什么是异质网络
我们现实生活中的好友关系链网络其实是一种同质的图结构，即图中只有“人”这一种类型的节点，而每条边代表两端的“人”存在这一种关系。然而现实生活中异质图的存在却更为广泛，比如人会购买商品，或者观看电影，在这些行为中会构成异构图。在这些图中，节点类型超过一种，边表示的关系也超过一种，那么此图就称为异构图。
为了清晰地捕获异质网络中节点以及边的语义信息，定义了一种由特定类型的节点连接起来的路径，成为元路径。例如可以定义 Actor – Movie Director 元路径。
当前挑战
1. 以前的大多数方法在学习 user-item关系之前，是汇总 user/item 的邻域信息，而不考虑可能的邻居间交互。这种问题作者称为 early summarization。
2. 在异构信息网络中扩展交互，当关系未知时，系统有望将用户模式与噪声区分开来。
对于第一个问题，作者举了一个例子：
例如，上图是一个推荐系统正在向用户推荐电影。其中用户已经五星好评了爱乐之城和星际穿越，电影有两种类型，爱情片和科幻片。
我们知道，爱乐之城是爱情电影，星际穿越是科幻电影，因此，爱乐之城和爱情片之间的联系可能有助于推荐。
同时，爱乐之城和科幻片之间的联系是无稽之谈，并且是不被期望的，这在以前的方法中，通常被视为噪音。
作者认为，局部结构信息是隐藏的，在以前的方法中没有充分利用。作者将致力于找到节点之间的这些相互作用，例如爱乐之城与科幻片之间的联系 ...
本文也是在异构图上做文章，主要工作有三点：
1. 探索了解决 early summarization 的方案
2. 使用了基于卷积的节点交互方法
3. 采用了快速傅里叶变化进行算法提速
2 方法
随机游走
随机游走听起来是个很厉害的名词，但是实际上比我们所学过的DFS、BFS都要简单。原理很简单，步骤如下：
1. 随机指定一个起点
2. 按照一定概率分布选择下一个节点作为目标
3. 一直循环第二步直至满足终止条件
那么所说的概率是如何定义的？
简单来说就是所有当前节点的邻居节点都有可能被采样，而且概率均等。
设立的满足条件一般为路径长度满足预设长度。
以下是简单的代码实现：
预定义一张异构图
使用dgl提供的api进行随机采样
这里的metapath是预定义的元路径，以电影数据集为例，UMDM则表示采样要依照“User Movie Director Movie” 的顺序进行采样。
交互模块
交互模块是将采样得到的节点路径进行交互操作，原理和卷积网络差不多。主要步骤有三个
1. Shift
2. Product
3. Sum
以下是部分步骤的示意图
在上例中，长度为4 和4的路径交互，应该会得到 长度为7的卷积结果。
接下来我们看看实际代码是如何编写的。
其中一个是采用了原始的卷积操作，另一个是作者提出用 FFT来加速卷积操作。
作者在文中指出，原始卷积操作的时间复杂度为 O(I2)，而采用了FFT的方法能缩减为O(Ilog(I))
但是实际上我做实验发现这两个方法得到的结果并不一致，速度的差别也并不是很大。
在知乎上有人提过这个问题，可以参考。
为什么很少人用FFT加速CNN卷积层的运算？ https://www.zhihu.com/question/264307400
王晋玮：
1. 傅里叶变换是逐通道进行的，因此每个输入通道的变换实际上会被多个输出通道复用，均摊了输入的变换开销。
2. 傅里叶变换是线性变换，因此每个输出通道的逆变换可以在累加每个输入通道之后做，均摊了输出的逆变换开销。
3. 部署模型时，可以预先做好权值的变换。
山里人：
我们做过对比，主要是因为现在流行小卷积核，比如3x3。FFT只有在卷积核超过大约9x9x9的时候，才有速度优势。这是在CPU上用MKL做的测试。
立党：
等kernel提高到1024*1024的时候，inference的时间复杂度从o（N^2）降到o（NlogN）的优势才有可能体现出来
注意力
注意力机制是一个很常用的方法了。本文使用了Node level 和path level的注意力机制。
Node attention 是对卷积结果做attention，和NLP中的attention并无二致。
Path attention 是对采样路径进行attention。
在路径采样前，需要定义metapath，作者在此定义了五种metapath，每种metapath会随机采样16条路径，共计80条路径。
以上两处attention可以为模型带来可解释性。
3 实验
实验做的非常充分，以下是各个模型在几个数据集上的性能对比。
可以看出作者的方法是最好的。
其中有一个NIRecCNN NIRecGCN是作者做消融实验来验证交互模块的有效性的，这两个模型分别用CNN 和GCN来代替作者提出的交互模块
所以可以看出，交互模块虽然看起来和卷积差不多，但是实际上还是能提升性能的，至于具体原因，可以看下面的可视化分析。
以用户692为例，预测出该用户对电影805 和电影920会有兴趣。
在path attention 处可以看到，用户对 电影920 的兴趣主要依赖于 UMGM 这条路径，G在路径中是Genre 流派/体彩的意思，可以理解为电影的类型。通过查看数据集进行分析， 692用户最喜欢的类型就是 g3，也就是 电影920的类型。
Node attention那张图的横纵坐标是 i开头的，因为代码没有这个部分，我只复现出了path attention，所以目前我也不敢轻易评价。
总结
1. 传统的基于图和元路径的模型通常在最终预测之前将用户/项目信息编码为单个嵌入向量。
2. 探索邻域结构对于缓解数据稀疏和冷启动问题非常有帮助。
3. 基于邻域的交互式推荐是异构图上的一个有效框架。