论文链接：https://www.ijcai.org/Proceedings/2019/0592.pdf
代码链接：https://github.com/jennyzhang0215/STAR-GCN
论文来源：IJCAI 2019

摘要

文章针对推荐系统提出了一种新的堆叠和重构图卷积网络(STAR-GCN)结构来学习节点的表征，提高推荐系统的效率，特别是在冷启动场景。STAR-GCN采用一堆GCN编码器/解码器与中间监督相结合，以提高最终预测性能。同图卷积矩阵分解模型用one-hot节点作为输入不同，STAR-GCN学习低维的user、item 隐表征作为输入来限制模型的空间复杂度。STAR-GCN可以通过重建屏蔽的输入节点表征来为新节点生成节点表征，这本质上解决了冷启动问题 。文章在为链接预测任务训练基于GCN的模型时发现标签泄漏问题，并提出了避免该问题的训练策略。 多个评级预测基准的经验结果表明，我们的模型在五个真实数据集中的四个中获得了最先进的性能，并且在冷启动场景中预测评级方面取得了显着改进。

1、简介

推荐系统中核心的数学问题就是矩阵分解，假设有$N$N 个user，$M$M 个item，推荐算法的目的是根据这个矩阵已有的值去填充未知的值。

经典的解决方法是基于矩阵分解(MF)，每一个已知的得分是通过用户和item的隐因子表征相乘得到的。近年来，深度学习的发展尤其是图卷积对这个问题带来了一些新的思路。GCN将卷积的定义从规则网格推广到不规则网格，像图结构。GCN通过一个局部共享参数算子来生成节点表示。一个图卷积算子通过转换或者聚合某个节点的局部领域节点的特征来生成该节点的表征。通过堆砌多个图卷积算子和非线性函数，我们构建了一个深度神经网络，可以抽取这个图远处的特征。因为局部邻域集可以看作卷积核的接收场，这类领域聚合方法称为图卷积。

Monti等人针对推荐系统首次提出了基于GCN的方法，在他们的方法里，GCN用于将user-user和item-item的两个图信息聚合，user和item的隐因子在每次聚合的时候更新，GCN和MF的目标函数通过组合用在了这个模型里。此后，Berg等人提出了图卷积矩阵完成模型(GC-MC)，GC-MC模型直接将user和item的关系描述为一个二部图。两个多连接卷积层用于聚合user和item的特征。通过预测边的标签来估计得分。GC-MC模型取得了很不错的成绩。

虽然很强大，但GC-MC模型有两个明显的限制，为了区分每一个节点，GC-MC模型使用one-hot向量作为节点输入，这使得对于大规模的图使用受到了限制；另外，模型不能预测训练过程中没有出现过的item和user，因为不能用one-hot表示没出现过的节点。这类任务就是我们熟知的冷启动。

本文提出了新的架构，堆积重构图卷积网络(STAR-GCN)来解决这些问题，不同于GC-MC，STAR-GCN作为一个端到端的模式直接学习user和item的低维表征，为了提升模型能力，另外也针对冷启动问题，STAR-GCN盖住了部分或者整个user和item的表征，在训练阶段通过一小块图的编码解码器来重构盖住的部分。这个想法灵感来源于NLP里的 masked language model，我们结合特定于任务的中间监督构建了一组编码器-解码器块，以提高最终性能。 在实施过程中，我们发现训练基于GCN的模型进行评级预测时会遇到标签泄漏问题，这会导致过拟合问题并严重降低最终性能。 为避免泄漏问题，我们提供了一个采样-丢弃训练策略，并通过经验证明了其有效性。

文章创新点：

1. 我们为推荐系统提出了一种新的体系结构，以便在转导和归纳环境中学习用户和项目的潜在因素
2. 第一个在评分预测任务中实施基于GCN的模型时明确指出培训标签泄漏问题的人，并提出了一种避免该问题的训练策略，从而显着改善了性能
3. STAR-GCN模型在转换环境中的五个真实世界推荐数据集中有四个实现了最先进的性能，并且在归纳环境中明显优于其他模型

2、前言

2.1、打分预测任务

基于GCN的模型将推荐环境当做一个无向二部图，由user $\mathcal{U}$U 和item $\mathcal{V}$V 两部分组成。打分集合 $\mathcal{R}=\{1,2,...,R\}$R={1,2,...,R}，每个打分都代表二部图里的一个连接，我们聚焦于两种类型的打分预测任务：转导式打分预测和归纳式打分预测。

转导式打分预测

如上图a所示，是针对已经存在的 user 和 item 之间的。

归纳式打分预测

对新来的user或者item预测，说白了就是冷启动。

对比CDL和DropoutNet，STAR-GCN不仅利用节点的内容信息，而且结合了结构信息来学习新节点的表征。

2.2、图卷积

先简单回顾一下GC-MC，GC-MC 利用一个多连接图卷积编码器来生成节点表征，每一个连接类型 $r$r 赋值为一种特殊的转化。信息按如下方式从 item 传到 user ：$y_{u_i}^r=\sum_{v_j\in\mathcal{N}^r{(u_i)}}\frac{1}{c_{ij}}W_a^rx_{v_j} \tag{1}$yui​r​=vj​∈Nr(ui​)∑​cij​1​War​xvj​​(1)$h_{u_i}=\alpha\left(W_h\alpha\left(\sum_{r=1}^Ry_{u_i}^r\right)\right)$hui​​=α(Wh​α(r=1∑R​yui​r​))其中， $\mathrm{y}_{u_i}^{r}$yui​r​一个连接类型 $r$r 的聚合结果，$\mathrm{x}_{v_j}\in\mathbb{R}^{d_{in}}$xvj​​∈Rdin​是 item $v_j$vj​的初始化向量，$\mathrm{W}_{a}^{r}$War​是对打分$r$r 的一个 $d_a * d_{in}$da​∗din​的权重矩阵，将 $d_{in}$din​维的向量转为 $d_a$da​维，$c_{ij}=\sqrt{|\mathcal{N}_{r}(u_i)||\mathcal{N}_{r}(v_j)|}$cij​=∣Nr​(ui​)∣∣Nr​(vj​)∣​是标准化常数，$\mathcal{N}(\cdot)$N(⋅)是由边值$r$r 连接的邻域。

解释一下上面两个式子，对于每个 user，会有多个不同的打分$r$r，首先将打分都为 $r$r 的聚合到一起，得到$\mathrm{y}_{u_i}^{r}$yui​r​，然后再将不同打分经过两次非线性变换得到 user 的表征 $\mathrm{h}_{u_i}$hui​​

3、模型

STAR-GCN通过堆叠或循环支持两个连续块之间的两种不同类型的组合。 主要区别在于是否在块之间共享参数。 通过堆叠，我们可以连续放置带有单独参数集的多个编码器-解码器块。 通过循环，我们展开单个编码器-解码器块，因此在所有块之间共享同一组参数，这减少了总的内存使用量。 此外，我们的STAR-GCN是一个通用框架

图2(a)为模型的通用框架，包含了多个(编码-解码)块，多个编码块可以堆叠(Stacked, 参数不共享)也可以重构(Reconstructed, 参数共享)。图2(b)和图2©是(a)的两种特例，(b)表示每个编码块可以包含多个GCN层，©表示可以不解码重构直接用于下游任务。

其中$x^{(0)}$x(0)是初始节点向量。 $h^{(l)}$h(l)是第$l$l个图编码器的输出，$\hat{x}^{(l)}$x^(l)是解码器的输出节点向量。 $L_t$Lt​是用于具体任务的损失函数，$L_r$Lr​是重建的损失函数。

3.1、输入节点表征

为了让网络扩展到大型图，本文用查表 lookup 将每个节点映射到一个低维的向量，$\mathrm{X}_e\in \mathbb{R}^{d_e *|M+N|}$Xe​∈Rde​∗∣M+N∣，$\mathrm{X}_e$Xe​在网络中通过端到端训练得到。但是简单的替换one-hot类型向量还是没法解决冷启动问题，因为新节点的embedding不在训练数据里。我们采取了一种方法，即随机掩盖一定百分比的输入节点，然后重建新的节点的表征。在每一个batch训练中，会盖住20%的节点，然后重建这部分节点的表征，对于这部分盖住的节点，做以下操作：(1)、以概率 $p_z$pz​将节点表征初始化为0，(2)、以1-$p_z$pz​概率保持不变。

训练这个 masked 表征机制有两个优势。第一，在训练过程中，它可以学习到没被观测到的节点，在冷启动场景，我们初始化新节点为0，通过多个GCN编码器/解码器块逐步完善估计的表征。例如，第一个块通过利用邻域数据（或节点属性，如果可用）来预测新节点的表征。 然后，将预测的表征内容馈送到第二个块，以预测评分和精确的表征内容。 评级和表征预测损失是共同优化的。 因此，STAR-GCN可以通过迭代优化嵌入来解决冷启动问题，并且与GC-MC根本不同。 其次，STAR-GCN导致转导环境的改善。 在训练阶段，部分节点嵌入被掩盖，并要求网络重构这些掩盖的嵌入，这要求网络有效地编码用户和项目之间的关系。 因此，重建损失充当提高基本评级预测任务的性能的多任务正则器。其次，STAR-GCN导致转导环境的改善。 在训练阶段，部分节点表征被掩盖，并要求网络重构这些掩盖的表征，这要求网络有效地编码 user 和 item 之间的关系。 因此，重建损失充当了多任务调整器，可提高主要评级预测任务的性能.。

3.2、图编码器和解码器

每次迭代，从rating pairs中采样固定数量的样本，在训练前，将这些被采样的样本（边）从训练图中移除。

图编码器通过聚合不同的打分等级的邻域信息，将输入节点向量 $\mathrm{x}\in\mathbb{R}^{d_{in}}$x∈Rdin​转换为大小为 $d_h$dh​的隐状态 $\mathrm{h}$h，例如 $\mathrm{h}=Enc(x)$h=Enc(x)，我们在GC-MC 中选择如方程（1）所示的编码器作为多连接GCN聚合器。解码器将结构编码节点表征 $\mathrm{h}$h 转成一个 $d_{in}$din​维的重构表征向量 $\hat\mathrm{x}$x^, $\hat\mathrm{x}=Dec(h)$x^=Dec(h) ，用一个两层的前向神经网络作为解码器，如 $\hat\mathrm{x}=\mathrm{W}_4\alpha(\mathrm{W_3}\mathrm{h})$x^=W4​α(W3​h)，其中输出维度都是 $d_{in}$din​。

STAR-GCN是带有一堆编码器解码器的通用型框架，任何类型的GCN，如Graph-SAGE，GAT都可以在STAR-GCN中作为编码器或解码器。

3.3、损失函数Loss

假设用 $L$L 个块，则loss function 可以表示为：
$\mathcal{L}=\sum_{l=1}^{L}(\mathcal{L}_{t}^{(l)}+\lambda^{(l)}\mathcal{L}_{r}^{(l)})\tag{2}$L=l=1∑L​(Lt(l)​+λ(l)Lr(l)​)(2)其中$\mathcal{L}_{t}^{(l)}$Lt(l)​是一个受监督的特点任务的 loss ，如打分预测 loss，$\mathcal{L}_{r}^{(l)}$Lr(l)​是第 $l$l 个块的重构 loss，在下面的描述中，为了简洁起见，我们省略了图层上标。

假设我们用一批样本边集合 $\mathcal{E}_b$Eb​和两个盖住的节点集合 $\mathcal{U}_m, \mathcal{V}_m$Um​,Vm​，则特定的loss 为
$\mathcal{L}_t=\frac{1}{|\mathcal{E}_b|}\sum_{(u_i,v_j)\in\mathcal{E}_b}(r_{i,j}-\mathrm{u}_i^{T}\mathrm{v}_j)^2$Lt​=∣Eb​∣1​(ui​,vj​)∈Eb​∑​(ri,j​−uiT​vj​)2$\mathcal{L}_r=\frac{1}{2|\mathcal{U}_m|}\sum_{u\in\mathcal{U}_m}\Vert\mathrm{x}_u-\hat\mathrm{x}_u\Vert^2+\frac{1}{2|\mathcal{V}_m|}\sum_{v\in\mathcal{V}_m}\Vert\mathrm{x}_v-\hat\mathrm{x}_v\Vert^2$Lr​=2∣Um​∣1​u∈Um​∑​∥xu​−x^u​∥2+2∣Vm​∣1​v∈Vm​∑​∥xv​−x^v​∥2
对于打分预测 loss ,$\mathrm{u}_i, \mathrm{v}_j$ui​,vj​由图形编码器输出的线性变换生成，如 $\mathrm{u}_i=\mathrm{W}_{r}^{u}\mathrm{h}_{u_i}$ui​=Wru​hui​​，$\mathrm{v}_j=\mathrm{W}_{r}^{v}\mathrm{h}_{v_j}$vj​=Wrv​hvj​​，其中，$\mathrm{W}_{r}^{u},\mathrm{W}_{r}^{v}\in\mathbb{R}^{d_r*d_o}$Wru​,Wrv​∈Rdr​∗do​。

在推断环节，一个 $L$L 块的STAR-GCN 可以输出 $L$L 个预测值，一般来说，我们选择最后一个块的结果作为最终预测结果。

实验评估指标采用均方误差 (RMSE)
$RMSE=\sqrt{\frac{\sum_{i=1}^{N}(\hat r_{i}-r_i)^2}{N}}$RMSE=N∑i=1N​(r^i​−ri​)2​​

4、实验

本文针对于Transductive Rating Prediction 和 Inductive Rating Prediction做了实验，数据集使用MovieLens(100K, 1M, and 10M), Flixster, Douban, and YahooMusic，达到SOTA精度。

数据集信息如下：

Transductive Rating Prediction：

Inductive Rating Prediction：

同时也对本文提出的框架的不同形式进行了对比实验：

5、总结

图卷积很难设置更深的层数去学习节点更好的表征形式，即使本文提出的STAR-GCN通过堆叠或重构编码解码块，也并不能设置较深的GCN层数。如何用GCN学习到更深层次的特征，是需要好好考虑的问题。