SIGIR'21 快手 | 基于图神经网络的序列推荐，兴趣的挖掘与动态变化

文章内容有点多，需要一丢丢耐心哦

Sequential Recommendation with Graph Neural Networks https://dl.acm.org/doi/pdf/10.1145/3404835.3462968

1. 背景

首先这里涉及到序列推荐的概念：序列推荐就是根据用户的历史行为来预测用户的后续交互。现存两个挑战：

• 在丰富的历史序列中，用户的行为是隐式（点击、观看）的并且有噪声信号在里面，从而导致无法充分的反应用户的偏好。噪声：用户可能点击了该item，但是后续没有和相似的其他item发生交互，那么用户可能对该item并不感兴趣。
• 用户的偏好是动态变化的，从历史数据中难以挖掘用户是模式。

本文提出 SeqUential Recommendation with Graph neural nEtworks （SURGE）来解决上述问题。

2. 方法

如图所示，本文所提的SURGE模型主要包含四部分，分别为：

• 兴趣图构建（Interest Graph Construction）：基于度量学习将松散的项目序列重新构建为紧密的项目-项目兴趣图，明确地整合和区分了长期用户行为中不同类型的偏好。
• 兴趣融合图卷积层（Interest-fusion Graph Convolutional Layer）：通过在兴趣图上进行图卷积，动态融合用户兴趣，强化重要的行为，弱化噪声行为。
• 兴趣提取图池化层（Interest-extraction Graph Pooling Layer）：采用动态池化的方式对用户不同时间动态变化的兴趣进行提取。
• 预测层（Predict Layer）：对后续可能交互的item进行预测。

2.1 兴趣图构建

通常可以采用共现关系来构图，但是共现关系的稀疏性导致不足以为每一个用户构建图。本文结合度量学习进行构图。

2.1.1 原始图构建

为每一个交互序列构建无向图。其中表示边的集合，表示邻接矩阵，表示交互的item，item对应的embedding为。目标是学习到邻接矩阵A反应item i与item j之间是否相关。通过该图反映用户的核心兴趣和边缘兴趣，所谓核心兴趣就是具有更高的度（degree），连接更多的相似兴趣节点。相似兴趣的频率越高，子图就越密集。如何计算相似兴趣节点，在下一节介绍。

2.1.2 相似度度量

上述构建了基本图后，需要判断哪些item之间时相似的。本文采用加权余弦相似度来度量相似关系，公式如下，其中可学习参数w和item的embedding h做哈达玛积，然后计算余弦相似度。

M_{i j}=cos left(overrightarrow{mathbf{w}} odot vec{h}_{i}, overrightarrow{mathbf{w}} odot vec{h}_{j}right)

为了提高表达能力和稳定性，这里将上式扩展为多头度量，公式如下，就是计算多次取平均。

M_{i j}^{delta}=cos left(overrightarrow{mathbf{w}}_{delta} odot vec{h}_{i}, overrightarrow{mathbf{w}}_{delta} odot vec{h}_{j}right), quad M_{i j}=frac{1}{delta} sum_{delta=1}^{phi} M_{i j}^{delta}

2.1.3 图稀疏化

之前通过计算两两item之间的相似度得到了一个n*n的矩阵，如果把这个矩阵作为邻接矩阵，那么这个邻接矩阵里每一个位置都有值，相当于都是邻接的，这在计算上代价高昂，并且可能引入噪声。同时图卷积无法专注于最相关的部分，因此需要对当前的图稀疏化，只提取其中最重要的关系。稀疏化的公式如下，其中表示从M中选出第大的值，n为矩阵大小，控制稀疏性。简单理解就是，大于某个阈值的就都为1，表示强关系；小于某个阈值的，都为0。只保留个强关系，从而控制了稀疏性。

A_{i j}=left{begin{array}{ll} 1, & M_{i j}>=operatorname{Rank}_{varepsilon n^{2}}(M) \ 0, & text { otherwise } end{array}right.

2.2 兴趣融合图卷积层

2.2.1 通过图注意力卷积进行兴趣融合、

本节作者提出了聚类感知和查询感知的图注意力卷积层，在信息聚合过程中感知用户的核心兴趣（即位于聚类中心的item）和与查询兴趣相关的兴趣（即当前目标item）。查询（query）就是对应目标item。根据下式，可以通过聚合将原有的embedding h转换为新的能够反映用户兴趣偏好的embedding h'。其中表示对齐分数，将目标节点的重要性映射到其周围的节点，其具体计算方式和注意力机制类似，后面介绍。w为可学习参数，聚合函数Aggregate可以是sum，max，gru等等，本文采用sum。

vec{h}_{i}^{prime}=sigmaleft(mathbf{W}_{mathrm{a}} cdot text { Aggregate }left(E_{i j} * vec{h}_{j} mid j in mathcal{N}_{i}right) vec{h}_{i}right)

代码语言：javascript复制

和计算相似度一样，此处为了稳定性，也采用了多头的方式，如下式，计算多个权重$E_{ij}$然后进行加权。||表示拼接，即将多次计算得到的embedding拼接后得到最后的embedding。

vec{h}_{i}^{prime}=|_{delta=1}^{phi} sigmaleft(mathbf{W}_{mathrm{a}}^{delta} cdot text { Aggregate }left(E_{i j}^{delta} * vec{h}_{j} mid j in mathcal{N}_{i}right) vec{h}_{i}right)

2.2.2 聚类感知和查询感知的注意力机制

通过这个注意力机制得到的权重就是我们在上一小节中用到的权重。这个权重用于强化重要的型号，弱化噪声信号。首先，作者假设目标节点及其邻居会形成一个簇（聚类），并且簇的中心是。定义的k阶邻居是它的感受野，这些邻居节点的embedding的均值为该簇的平均信息。为了判断是否为中心，可以采用下式计算分数，其中是两层前馈神经网络，激活函数为LeakyReLU。W为可学习参数，||为拼接。为的embedding，表示所在簇的平均信息，就是前面所述的均值。

alpha_{i}=text { Attention }_{c}left(mathbf{W}_{mathbf{c}} vec{h}_{i}left|vec{h}_{i_{c}}right| mathbf{W}_{mathbf{c}} vec{h}_{i} odot vec{h}_{i_{c}}right)

其次，为了服务于下游的动态池化方法，学习用户兴趣对不同目标兴趣的独立演化，还应该考虑源节点嵌和目标项嵌之间的相关性。如果源节点与查询项的相关性更高，则其在对目标节点的聚合中的权重将更显着，反之亦然。由于只有相关行为才能在最终预测中发挥作用，所以我们只保留相关信息，聚合时会丢弃不相关信息。

beta_{j}=text { Attention }_{q}left(mathbf{W}_{mathbf{q}} vec{h}_{j}left|vec{h}_{t}right| mathbf{W}_{mathbf{q}} vec{h}_{j} odot vec{h}_{t}right)

上述两部分，第一个是聚类感知，第二个是查询感知。将这两部分结合可以得到注意力权重，即。其中表示节点i的邻居，包含节点i自身。α控制目标节点可以接收多少信息，β控制源节点可以发送多少信息。

E_{i j}=operatorname{softmax}_{j}left(alpha_{i} beta_{j}right)=frac{exp left(alpha_{i} beta_{j}right)}{sum_{k in mathcal{N}_{i}} exp left(alpha_{i} beta_{k}right)}

2.3 兴趣提取图池化

2.3.1 通过图池化进行兴趣提取

为了得到池化图，需要先得到聚类分配矩阵，假设存在聚类分配矩阵[1,2]，那么它就可以将节点信息池化为聚类信息。其中n是节点个数，m是超参数，表示聚类的个数。我们现在已知原始图得到的embedding和分数，可以得到粗化图的聚类embedding和分数，如下式，对前面小节得到的做softmax得到反应不同节点的重要性。通过聚类矩阵S，可以将原有的embedding转换为新的embedding。

begin{array}{l} left{vec{h}_{1}^{*}, vec{h}_{2}^{*}, ldots, vec{h}_{m}^{*}right}=S^{T}left{vec{h}_{1}^{prime}, vec{h}_{2}^{prime}, ldots, vec{h}_{n}^{prime}right} \ left{gamma_{1}^{*}, gamma_{2}^{*}, ldots, gamma_{m}^{*}right}=S^{T}left{gamma_{1}, gamma_{2}, ldots, gamma_{n}right} end{array}

这里的矩阵S确定了每一个节点属于哪一个聚类，不过这里采用soft聚类，即每一个节点可能隶属于不同的聚类，采用这种soft的形式可以使得整个个矩阵是可微的。正式因为这里可能会属于多个聚类，因此需要后续的正则项。这里得到S矩阵的方式如下，w为可学习参数，将输出的维度控制在m，即聚类个数。softmax归一化后用于计算分到不同聚类的概率。通过可以得到池化图的邻接矩阵。

S_{i:}=operatorname{softmax}left(mathbf{W}_{mathbf{p}} cdot text { Aggregate }left(A_{i j} * vec{h}_{j}^{prime} mid j in mathcal{N}_{i}right)right)

可以重复计算上式，进行兴趣的分层压缩。

2.3.2 正则项

在下游的推荐任务中的梯度下降法很难训练上述矩阵S，因为这是非凸优化问题，容易陷入局部最优。并且，h'的顺序可以反映交互的时间信息，但是聚类后得到无法反应时间信息，因此提出了三种正则项。

2.3.2.1 Same mapping regularization

该正则项使得连接强度更大的两个节点更容易映射到统一聚类。公式如下，其中表示 Frobenius 范数。A为邻接矩阵，反应节点之间的连接强度，矩阵中的元素反应两个节点划分到同一个聚类中的概率。

L_{mathrm{M}}=left|A, S S^{T}right|_{F}

2.3.2.2 Single affiliation regularization

该正则项明确定义每个聚类的从属关系，计算S矩阵中的每一行的熵来使得每一行接近one-hot向量。公式如下。最优情况为每一个节点都只映射到一个簇，这时熵为0。

L_{mathrm{A}}=frac{1}{n} sum_{i=1}^{n} Hleft(S_{i:}right)

2.3.2.3 Relative position regularization

为了维持聚类前后的时间序列关系，可以采用以下正则项，其中是位置编码向量，也是编码向量。最小化这个L2范数使得S矩阵中的非零元素的位置更接近对角线。

L_P=|P_nS,P_m|_2

2.3.3 Graph Readout

在得到了表示用户强兴趣的紧密粗化图之后，在原始图上进行加权约束每一个节点的重要性，对embedding加权得到图级别的表征，公式如下，其中γ是池化之前每个节点的分数，Readout函数可以是Mean，Sum，Max等，本文采用Sum。

vec{h}_{g}=operatorname{Readout}left(left{gamma_{i} * vec{h}_{i}^{prime}, i in mathcal{G}right}right)

得到图级别的表征后，可以将其用于后续的预测层了。

2.4 Predict Layer

2.4.1 兴趣演化模型

用户的兴趣是随着时间不断变化的，因此在这里从历史行为中考虑时间信息，进行兴趣演化。此处的兴趣演化层直接采用了DIEN中的AUGRU，利用兴趣提取层中的作为AUGRU中更新门的权重

vec{h}_{s}=operatorname{AUGRU}left(left{vec{h}_{1}^{*}, vec{h}_{2}^{*}, ldots, vec{h}_{m}^{*}right}right)

2.4.2 Prediction

将兴趣演化层的表征，图级别表征，以及目标item的表征进行拼接后进行预测。Predict函数为两层前馈神经网络。

hat{y}=operatorname{Predict}left(vec{h}_{s}left|vec{h}_{g}right| vec{h}_{t} | vec{h}_{g} odot vec{h}_{t}right)

最后损失函数采用交叉熵损失函数 L2正则项。

3. 实验结果

4. 总结

这篇文章的内容有点多，让我们来简单总结一下。本文主要针对兴趣挖掘和兴趣变化这两个方面的难点提出了SURGE。该模型主要包含四个方面：

• 第一部分，主要是构建后面需要用到的图，本文主要通过用户的历史行为，来构建item-item的图结构，然后根据加权余弦相似度计算item之间的相似度，并通过阈值控制整个图的稀疏性。
• 第二部分，通过聚类感知和查询感知计算得到两个权重，结合两个权重得到注意力分数，然后对目标item的周围邻居节点的embedding进行加权融合，使得得到的embedding是融合了周围相似item的embedding。这可以强化重要行为，弱化噪声。
• 第三部分，这部分进行兴趣提取，通过池化，对用户的兴趣进行分层提取，并且通过正则项加强模型的训练，同时考虑时序信息。
• 第四部分，这部分考虑兴趣演化，即用户兴趣随时间动态变化，采用了DIEN中的AUGRU。再结合全连接层进行预测。

关于聚类分配矩阵的文献

[1] Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. 2020. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In AAAI. 5470–5477 [2] Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. 2018. Hierarchical Graph Representation Learning with Differentiable Pooling. In NeurIPS

数据结构 正则表达式

0 人点赞