前言

Recsys2018 基于图神经网络对CF进行改进的算法研究
相关研究参见基于图的推荐算法(4): Graph Convolutional Matrix Completion - 简书 (jianshu.com)

摘要

基于CF的方法仍然存在冷启动问题，这对推荐系统(RS)的用户体验有很大的负面影响。为了克服上述问题，在用户-物品交互二部图上，提出了一种新的谱域卷积运算(spectral conv)，直接在谱域中进行，在此运算中，不仅可以包含图的邻近性信息(proximity information)，还可以包含隐藏在图中的连通性信息(connectivity), 建立了一个名为谱协同过滤(SpectralCF)的深度推荐模型。从已存在的谱域中获取丰富的链接信息,SpectralCF能够发现用户和物品交互之间的深层连接信息，缓解冷启动的问题

前言

如果我们把用户和物品之间的关系表述为二部图，我们认为图的连通性信息对于解决冷启动问题可以发挥重要作用。例如，以下图为例。冷启动用户 u1只与物品 i1交互。由于用户 u2和用户 u3的 u1都交互过i1，因此基于 cf 的模型可以向 u1推荐与 u2或 u3相关的三个物品(i2、 i3和 i4)。

然而，一个自然而重要的问题出现了: 这三个物品中，哪一个是对 u1最可靠的推荐？回答这个问题的关键在于用户-物品的连接性信息(connectivity)。

事实上，如果我们看一下图的连接，很明显 u1和 i2(或 i3)之间只存在一条路径，而两条路径连接着 i4。因此，与 i2和 i3相比，i4显然是对 u1更可靠的推荐。

然而，现有的基于 cf 的方法，包括基于模型的方法和基于内存的方法，都存在连通性信息建模困难的问题。例如矩阵分解，通常利用直接关联(或近似)。然而，传统的基于模型的方法很少捕获隐藏在图结构中的间接连通性信息。
在图1中为 u1和 i4之间的路径数建模对他们来说是很难的。虽然引入了许多基于内存的方法(ItemCF/UserCF)对连通性信息进行建模，但这些方法通常依赖于预定义的相似性函数。然而，在现实世界中，定义适合于不同应用程序情况的相似性函数从来都不是一件容易的事情。

Spectral Graph Theory 谱域图理论

谱图理论研究图的组合属性和矩阵的特征值之间的联系相关的图表,如拉普拉斯算子矩阵。
一般来说,图的光谱图(spectrum)着重于图的连通性,而不是几何距离(geometrical proximity)。让我们重新回到上图,对于二部图B，我们用特定的频域直观地绘制它的顶点。虽然顶点不带有坐标，但在空间中绘制它们的一种流行方法是使用与图相关联的拉普拉斯矩阵的特征向量来提供坐标。下图显示：与i2和i3相比，i4在空间2中更接近于u1。因此，当变换到频域时，对于u1, i4比i2或i3更合适。根本原因是图的连通性信息已经在频域中被揭示了，在频域中顶点之间的关系不仅依赖于它们的接近性，还依赖于它们的连通性。因此，利用图的频谱可以帮助更好地探索和确定要推荐的物品：

为了克服直接从频谱域学习推荐的困难，我们首先提出了一种新的频谱卷积操作，该操作由一个多项式进行逼近，以动态放大或衰减每个频域。然后，我们引入了一个名为谱协同过滤(SpectralCF)的深度推荐模型，该模型由多个提出的光谱卷积层构建SpectralCF直接在谱域进行协同过滤。

模型方法

1. 图傅里叶变换(Graph Fourier Transform)

涉及比较多的谱图理论知识，需要对相关知识有一定认识

图信号(Graph Signal): 给定图 $G=\{V,\varepsilon \}$ ，对于每个节点都有一个特征值 $x_i$ ，整个图信息可以表示为向量 $\mathbf{x}\in \mathbb{R}^{|V| \times 1}$ 。经典的傅里叶变换定义如下：

那么针对图信号的图傅里叶变换可以定义为：

详细定义如下：

对于二部图，文中假设两种图信号，分别对应用户节点和物品节点：到谱域的转换方式如下：

2. Spectral Convolution Filtering 谱域卷积

在以上变换的基础上，引入卷积，增加一个卷积核，参数化为对角阵 $g_\theta(\Lambda)$ ,通过对拉普拉斯的特征值加参,对谱域上的信号进行处理：

拉普拉斯矩阵特征值如下

3. Polynomial Approximation 多项式近似

上面的卷积操作存在两个问题：

计算复杂度比较大O(N)，即节点梳理；
图信号是向量，那么每个节点被表示成为标量特征，无法满足任务需求
通过多项式近似来减少参数量

运用1阶多项式进行近似变换： GCN也是这样的推导逻辑
与GCN的推导过程相同，接着对上面参数做进一步简化，假设 $\theta'=\theta'_0=\theta_1'$ ，最终可以表示下面的形式：