Graph4Rec: 通用的图神经网络推荐工具箱, 一键下载运行~

Houye

发布于 2021-12-22 13:29:15

7660

发布于 2021-12-22 13:29:15

文章被收录于专栏：图与推荐图与推荐

https://arxiv.org/abs/2112.01035

前言

现有的基于 GNN 的推荐系统算法存在以下问题：

由于数据集和评估指标上的不同，基于 GNN 的推荐算法模型不能直接进行比较；
许多方法只适用于小数据集，因可扩展性不能应用于现实世界的推荐系统问题。

基于此，本文提出 Graph4Rec 将 GNN 用于推荐系统的训练范式统一为 graphs input、random walk generation、ego graphs generation、pairs generation 和 GNN selection 等几个部分，通过该训练 pipeline 可以很容易地建立自己的 GNN 模型同时相关配置被简化。此外还开发了支持分布式 GNN 训练的大规模图引擎和参数服务器。

作者比较了不同 GNN 模型在不同场景、不同尺度下的性能。此外还试图找出稀疏和稠密参数对 GNNs 性能的影响。最后研究了 negative sampling、ego graph construction 和 warm start strategy 等方法，以期找到一种更有效的将 GNNs 应用于推荐系统 RS 的方法。

如果大家对大图数据上高效可扩展的 GNN 和基于图的隐私计算感兴趣，欢迎关注我的 Github，之后会不断更新相关的论文和代码的学习笔记。

链接：https://github.com/XunKaiLi/Awesome-GNN-Research

1. Motivation

在基于图的推荐系统中，从复杂的图结构中学习有意义的表示在推荐系统的开发中起着至关重要的作用。目前图学习主要有两种策略：

基于随机游走的图学习策略：通过 random walk 生成一个图节点序列窗口，然后拉近同一窗口内的节点表示，并将这些节点从随机采样节点集中推远。
基于 Message-passing 的 GNN 学习策略：GNN 模型对节点表示的邻居进行迭代聚合，并利用高阶图结构信息进行优化。除了图学习策略，现有的一些图嵌入系统存在一定的局限性：

GraphVite 仅在具有多个 GPU 的服务器上现在基于 random walk 的模型。PBG 虽然支持分布式训练，但不能处理异构 GNN 模型，缺乏对推荐系统中包含的复杂结构数据建模的能力。此外，这两个系统都不能利用图中节点的辅助信息来解决冷启动问题。

基于本文提出的 Graph4Rec，通过简单的步骤就可以建立相应的 GNN 模型。此外，与传统的基于游走策略的嵌入式系统不同，GNNs 的使用使得 Graph4Rec 在为推荐系统建模复杂的用户-物品交互数据时更具优势，分布式的图计算引擎和参数服务器使得 Graph4Rec 能够处理大规模的图数据。此外，作者还进行了系统而全面的实验评估了具有代表性的用于推荐的 GNN 模型，并为 GNNs 在推荐中的发展提供一些建议。

2. Graph4Rec Preliminaries

2.1 Heterogeneous Graph Structure

图这种数据结构之所以适用于推荐系统，是因为推荐中用户和物品之间的交互可以建模成异质图 G=(\mathcal{V}, \mathcal{E}, \mathcal{R}) ，其中 \mathcal{V} 代表节点集合， \mathcal{E} 代表边，\mathcal{R} 代表边的种类。所谓异质图是因为在推荐系统中， \mathcal{V} 可以代表用户节点或者物品节点， \mathcal{R} 代表用户和物品之间不同的关系例如点击或者购买。如果两个节点之间所构成的边只具有一种关系那么就退化成同质图 (homogeneous graph) 。

2.2 Graph Neural Networks

基于 Message-passing 的第 k 层 GNN 可以表示为：

\begin{aligned} \hat{h}_{v}^{K} &=A G G R E G A T E^{k}\left(\left\{h_{u}^{k-1}: u \in \mathcal{N}_{v}\right\}\right) \\ h_{v}^{k} &=C O M B I N E\left(h_{v}^{k-1}, \hat{h}_{v}^{k}\right) \end{aligned}

简单的将上述 \mathrm{GNN} 适用于大图数据的方法是邻域抽样，即解决 K -hop 邻域引起的指数增长问题的常用方法。

2.3 Graph Representation Learning

推荐任务完成的好坏通常取决于图嵌入任务完成的情况，图推荐中的图表示学习：早期的图表示学习基于 skip-gram 策略，在图上执行预定义的 random walk。最近基于 GNN 推荐系统可以利用来自图结构的高阶信息，而不是简单的 ID 嵌入。大体上基于图的推荐系统都遵循同一策略来设计损失函数（基于 BPR loss），即拉近结构相似的积极对，远离消极对。损失函数可以表示如下：

\mathcal{L}=-\log \sigma\left(y_{v u}\right)-\sum_{m=1}^{M} \mathbb{E}_{w_{m} \sim P(w)}\left[\log \sigma\left(-y_{w_{m} u}\right)\right]

其中一种简单的计算交互结果的是计算方式为内积 { }^{}: \quad y_{v u}=h_{v}^{T} h_{u} ， P(w) 代表从 M 个物品采样出 negative node w_{m} 的分布。

3. Graph4Rec Framework

Graph4Rec pipeline 主要包含五个步骤：graphs input、random walk generation、egographs generation、pairs generation、and GNNs selection。

3.1 Heterogeneous Graph Settings

在 Graph4Rec 中，基本的数据结构是异质图，其中节点（用户、物品）和边（点击、购买）具有多种类型。一个异质图可以分解成若干个二部有向图，其中一个三元组 (u, r, v) 表示为源节点、关系和目的节点。输入图数据的通用表示方法可以处理复杂的图数据。

例如，在推荐系统中，有两种类型的节点，即用户节点和物品节点，由 u, i 表示。并且 u, i 之间的 “点击" 交互可以表示为 "u2click2i" 。为方便起见，使用 “2" 作为分隔符，将字符串拆分成三元组，当对称为真时，会自动添加 "i2click2u" 反向关系。如果只有一种类型的节点和边，异店图将退化为同店图，可以将节点类型设置为 u ，将边类型设置为 " u 2 u "。

3.2 Random Walk Generation

Random walk 产生的节点序列中的节点定义 proximity 是图表示学习的基本方法。对于异质图，Graph4Rec 采用基于元路径的随机游走生成节点序列。Metapath 可以简单地定义为一系列边类型的首尾相连（大部分情况下源路径的节点类型是对称的）以图 1 给出的例子，metapath 定义为：u2-click-2i -- i2-buy-2u。

受启发于 metapath2vec，本文提出 multi-metapaths random walk 从异质图中抽取多条元路径（也就是可以定义多条元路径）。对于同质图，可以将元路径设置为“u2u - u2u”，相当于一次 random walk。

3.3 Ego Graphs Generation

在训练过程中为降低基于 Message-passing GNN 的多跳邻域聚合的递归式计算开销增长需要进行邻域采样。本文提出通过 Ego Graphs 来规范当前训练目标节点的邻域采样过程。

Ego Graphs 由一个中心节点和其邻居节点组成。对节点v ，关系 v 的邻居为S_{v, r}=\{u: d(u, r, v) \leq K\} ，其中 d(u, r, v) 代表基于类型 r 的两节点 u, v 之间的最短路径，因此基于关系类型 r 的当前节点 v 的 Ego Graph 表示为 G_{v, r} 为 S_{v, r} 的子图。

由于存在多种由边代表的关系类型，本文提出了一种基于关系类型的邻居采样方法，以允许关系上的聚合。形式上一个基于关系的 ego graph 表示为 G_{v}=\left\{G_{v, r}: r \in \mathcal{R}\right\} . 因此，从 Random Walk Generation 生成的序列内的每个节点可以成为中心节点。因此，同一序列中的节点通过 relation-wise neighborhood sampling 形成其不相交的 ego graph。

3.4 Pairs Generation

Random path 内的 pairs 通常被用来定义图上的对比学习或自监督学习的正确率。此外，同一路径中的物品或用户，如 u-i-u-i，可能是潜在的推荐结果。因为该路径暗示用户具有相同的行为，并且物品具有相同的用户组。win_size 用于控制元路径中的 proximity。基于此生成 ego graph pairs 作为下一步的正训练样本。

3.5 GNNs Selection

在获得训练样本对之后，选择 GNN model 进行 ego graph 进行 encode。对于异构集合，基于 R-GCN 为每个单独的关系类型提供具有不同权重的邻域聚合。节点表示通过以下方式计算：

\begin{gathered} h_{v, r}^{k}=G N N_{r}\left(h_{v}^{k-1},\left\{h_{u}^{k-1}: u \in \mathcal{N}_{v, r}\right\}\right) \\ h_{v}^{k}=\alpha h_{v}^{0}+(1-\alpha) \sum_{r}^{R} \phi_{r} h_{v, r}^{k} \end{gathered}

其中 S_{v, r} 可以是任意基于 Message-passing 的 GNN model，Graph4Rec 提供了多种 GNN model 例如：GCN、GAT、LightGCN，或者使用者可以自己定义。

相较于同质图， \phi_{r} 代表多种关系类型聚合的权重，最简单的方法是将它看做是一个常量 \phi_{r}=1 ，同样该变量可以看作是可学习的，如 GATNE 采用浅层网络来提供由 \phi_{r}=\operatorname{softmax}\left(\mathbf{w}^{T} \tanh \left(\mathbf{W} h_{v, r}\right)\right) 计算的每个关系之间的注意力。

Over-smoothing 通过 \alpha 代表的残差连接模块进行缓解。也可以认为是 Personal PageRank。

为了解决冷启动问题，可以利用类别、品牌或用户配置文件等辅助信息与 ID 嵌入相结合。在 Graph4Rec 中支持具有多个槽的可配置稀疏特征，并且每个槽可以有多个值来支持可变长度的特征，例如文本或标签。

3.6 Training Optimizations

Parameter Server

随着图数据规模的增大，稀疏可学习参数（ID或边信息）急速增长，限制了 GNN model 在大规模推荐系统中的应用。本文采用了一个 Parameter Server，其中包含一个基于 PaddlePaddle 嵌入的键值存储。在每个训练步骤，从参数服务器远程拉取嵌入，将计算出的梯度推送到服务器进行异步更新。在分布式图引擎和 Parameter Server 的支持下，Graph4Rec 可以很容易地训练出具有大规模图数据的 GNN 模型，供推荐系统使用。

Walk, Sample, Pair: Order Matters

训练样本生成的顺序对 GNN 的训练速度很重要。最直观的生成顺序是先采样一条路径，然后对于路径内的当前顶点，在同一窗口内选择另一个顶点来构建对。然后对每对喂入到 GNN model 的 ego graph 进行采样。然而，这种方法会产生许多重复的节点，并且每个节点都必须包含一个 ego graph，增加了图引擎的通信量。为了缓解这一问题，作者交换了对生成和 ego graph 采样的顺序：在通过 Random Walk Generation 生成序列后，首先对路径中的每个顶点进行 ego graph 采样，然后构造 GNN model 的训练对。

假设采样路径的长度为 L ，窗口大小为 w ，则在采样 ego graph 之前生成对时需要O(w L) 个 ego graph 采样操作。但是如果改变顺序，采样次数可以减少到 O(L) ，但是减少了训练样本的多样性。

In-batch Negative Sampling

Graph4Rec 的主要思想是学习每个节点的表示，拉近相似节点，推远差异性大的节点。positive pairs 可以是观察到的相互作用，而 negative pairs 从 \mathcal{V} 中随机选择的。此过程中随机选择 negative pairs 会耗费大量时间，特别是在节点及其边信息保存在不同机器中的分布式训练过程中。因此，作者实现了一个改进的版本，使用了 In-batch Negative Sampling。最大化链接节点的得分，同时最小化 batch 中其他节点的得分。该方法可以减少额外的数据输入，从而提高训练速度。

Pre-training and Parameters Warm Start

传统的 walk-based 模型是快速有效的。首先对 walk-based models 中的稀疏嵌入进行预训练。然后训练一个基于 GNN 的模型，并继承参数，以达到快速收敛和提高性能的目的。

个人感觉 paper 中给出的框架图不是很清晰，很多细节可能需要看一下源码，这里占个坑...