解读PingSage：图卷积神经网络在数十亿数据网络级别推荐系统的应用

论文作者 | Rex Ying, Ruining He 等

编译 | Maglish

编辑 | Vincent

AI 前线导读：深度神经网络在图结构数据方面的进步大大提高了推荐系统基准的最佳性能。然而，对于具有数十亿数据项和数亿用户网络级别的推荐任务来说，这些方法的实际应用和可扩展性仍然是一个挑战。Pinterest 的研究人员提出了一种新的图卷积网络 PinSage，能够生成包含图结构和节点特征信息的有效嵌入表示，并且设计了新的训练策略，以提高模型的鲁棒性和收敛性。作者在 Pinterest 网站上部署了 PinSage，并利用 75 亿个样本对其进行训练。与深度学习基线方法相比，PinSage 能够生成更高质量的推荐。对于推荐任务，PinSage 比最佳基线方法的点击率提高了 150%，MRR 提高了 60%。 这是迄今为止深度图嵌入表示的最大应用，为基于图卷积结构的新一代网络级别的推荐系统铺平了道路。 本文是 AI 前线第 80 篇论文导读，为你详细解读 PinSage 背后的技术细节。

更多优质内容请关注微信公众号“AI 前线”（ID：ai-front）

介  绍

深度学习方法在推荐系统应用中有着越来越重要的应用，利用深度模型学习到的特征表示，可以补充，甚至取代传统的推荐算法。近年来，随着能够在图结构数据上进行学习的深度学习方法的出现，这一领域取得了重大进展，因为图结构数据一直是推荐应用的基础（例如，开发用户到项目的交互图以及社交图）。

其中最突出的是图卷积网络（GCN）这一深度学习体系结构的成功。GCN 背后的核心思想是学习如何利用神经网络迭代地聚合来自局部图邻域的特征信息（如图 1 所示）。一个“卷积”操作从一个节点的单跳图邻域转换并聚集特征信息，并且通过叠加多个这样的卷积操作，信息可以传播到图的远端。与基于内容的深度模型（如递归神经网络）不同的是，GCN 既利用了内容信息，也利用了图结构。基于 GCN 的方法在无数推荐系统的基准上建立了新的标准。然而，相对于基准任务的提升还需要进一步转化才能在现实生产环境中应用。

现实环境所面临的主要挑战是如何将基于 GCN 的节点嵌入表示的训练和推理阶段扩展到具有数十亿个节点和数百亿个边的图中。扩展 GCN 是很难的，因为在大数据环境下工作，会违反它们的设计中潜在的许多核心假设。例如，现有的基于 GCN 的推荐系统在训练期间都需要在全图拉普拉斯上运行，但当基础图具有数十亿个节点并且结构不断变化时，这种假设是不成立的。

我们提出了一个在 Pinterest 中开发并已应用于生产的高度可扩展的 GCN 框架，PinSage。它在具有 30 亿个节点以及 180 亿个边的图结构上运行，比经典的 GCN 应用中的图结构大了 10000 倍。PinSage 充分利用了以下几个关键的思想，大大提高了 GCN 的可扩展性：

图 1：使用 2 层卷积的模型架构概览。左：一个小的输入图示例。右图：2 层神经网络，用上一层的表示计算 A 节点及其邻域 N(A)（节点 B、C、D）的嵌入表示 h(2)A。底部：计算输入图每个节点嵌入表示的神经网络。虽然每个节点的神经网络都不同，但它们共享相同的参数集（即卷积 (1) 和卷积 (2) 函数的参数）。具有相同阴影的框表示共享参数；γ表示重要性池化函数；而长矩形框表示稠密连接的多层神经网络。

在线卷积： 传统的 GCN 算法通过将特征矩阵乘以全图拉普拉斯的幂进行图卷积。相反，PinSage 算法通过对一个节点周围的邻域进行采样，并从该采样邻域动态构造一个计算图，来实现高效的局部卷积。这些动态构造的计算图（图 1）指定了如何围绕特定节点进行局部卷积，并降低了在训练期间对整个图进行操作的需要。

通过随机行走构造卷积： 取节点的整个邻域进行卷积（图 1），会产生巨大的计算图，因此我们利用采样的方法。我们开发了一种利用短随机游走对计算图进行采样的技术。该方法的另一个好处是每个节点都有一个重要性评分，我们在池化 / 聚合步骤中可以利用该评分。

重要性池化： 图卷积的一个核心组成部分是图中来自局部邻域的特征信息的聚合。我们引入了一种基于随机游走相似性度量的方法来衡量节点特征在这个聚合中的重要性，从而在离线评估度量中获得了 46% 的性能提升。

除了这些在可扩展性方面的改进之外，我们还引入了新的训练技巧和算法创新。这些创新提高了 PinSage 学习的特征表示质量，从而显著提升了下游推荐系统任务的性能：

生产者 - 消费者 minibatch 构造： 我们设计了一个生产者 - 消费者架构，用于构造 minibatch 运算，以确保在模型训练期间最大限度地利用 GPU。一个大内存、CPU 绑定的生产者有效地对节点网络邻域进行采样并获取定义局部卷积所需的特征，而一个 GPU 绑定的 TensorFlow 模型则消费这些预定义的计算图，实现高效地 SGD 计算。

有效的 MapReduce 推理： 给定一个完全训练的 GCN 模型，我们设计了一个高效的 MapReduce 管道，可以将训练后的模型分布到数十亿个节点上，同时最小化重复计算。

课程训练： 我们设计了一个课程训练方案，逐步提升训练样本的难度，从而获得了 12% 的性能提升。

我们在 Pinterest 的各项推荐任务中部署了 PinSage，Pinterest 是一个流行的内容发现和管理的应用程序，用户可以通过图钉（Pins）进行交互，Pins 是在线内容的可视书签（例如，他们想烹饪的菜谱，或者他们想购买的衣服）。Pinterest 是世界上最大的用户管理的图像库，有超过 20 亿个独特的图钉被收集到超过 10 亿块钉板上。

通过广泛的离线评价、受控用户研究和 A/B 测试，我们发现，PinSage 在项目 - 项目推荐任务（pin 相关的推荐）和家庭订阅推荐任务中都达到了最先进的性能。在离线排序指标中，我们比最佳表现基线提高了 40% 以上，在用户调查中，我们的推荐中有 60% 左右被首选，而 A/B 测试显示，用户参与度提高了 30% 至 100%。

据我们所知，这是有史以来最大的深度图嵌入应用，为基于图卷积结构的新一代推荐系统铺平了道路。

方  法

PinSage 中最重要的思想是局部图卷积。为了产生一个节点的嵌入表示，我们应用多个卷积模块，从一个节点的局部图邻域累积特征信息（视觉特征、文本特征）。每个模块都从一个小的图邻域中学习如何累积信息，通过堆叠多个这样的模块，我们的方法可以从局部网络拓扑中学习到有用的信息。更重要的是，这些局部卷积模块的参数在多个节点之间共享，使算法的参数复杂度独立于输入图的大小。

问题描述

Pinterest 是一个内容发现应用，用户可以通过图钉（Pins）来互动。我们的任务是为图钉生成高质量的内嵌表示。为了学习这些内嵌表示，我们将 Pinterest 环境建模为一张由两套不相关的节点组成的二分图，I（图钉）和 C（钉板）。

除了图结构，我们也假设图钉 u 与实值属性 xu 相关。这些属性指定了一个条目的元数据或内容信息。在 Pinterest 中，我们提取图钉的文本以及图像特征。我们的目标是利用这两个输入属性，以及二分图的结构，生成高质量的内嵌表示。这些内嵌表示随后被用于推荐系统，通过最近邻查找得到候选条目（例如给定一个图钉，找到相关的图钉），或者在机器学习系统中用于对候选项排序。

模型结构

我们利用局部卷积模块为节点产生嵌入表示。首先输入节点的特征，然后学习神经网络，将图的特征转换并累积，计算节点内嵌表示。

局部卷积

算法 1 局部卷积操作

我们将 u 的邻域 v 的内嵌表示 zv 通过一个稠密神经网络进行转换，然后对得到的矢量集应用累积或池化函数（元素级别的平均或加权和，用γ表示）（步骤 1）。累积步骤得到了 u 的局部邻域 N(u) 的矢量表示 nu。然后我们将累积邻域矢量 nu 和 u 当前的表示 hu 相连接，并通过另一个稠密神经网络层进行转换（步骤 2）。步骤 3 中对 zu 进行归一化，能够稳定训练过程。算法的输出即为节点 u 的嵌入了自身信息和局部图邻域信息的特征表示 zu。

基于重要性的邻域

算法的一项重要创新是选择领域 N(u) 的方法。在 PinSage 中，我们定义了基于重要性的邻域，其中节点 u 的邻域定义为对 u 最具有影响力的 T 个节点。我们模拟随机游走，从节点 u 开始，计算随机游走访问节点的 L1 正则化访问次数。u 的邻域定义为正则化访问次数最高的前 T 个节点。这一定义让算法 1 在累积邻域的矢量表示时考虑其重要性。因此，算法 1 中的γ函数为加权平均，权重即为节点的 L1 正则化访问次数。我们将这一方法命名为重要性池化。

堆叠卷积

每次应用卷积运算（算法 1），我们都会得到一个新的节点表示。我们可以将多个这样的卷积叠加在一起，以便获得围绕节点 u 的局部图结构的更多信息。我们使用多个卷积层，在这里，第 k 层卷积的输入取决于第 k-1 层输出的表示，而初始（即“第 0 层”）表示等于输入的节点特征。算法 1 中的模型参数（Q，q，W 和 w）对于所有节点共享，但是不同层之间不共享。

算法 2 详细描述了堆叠卷积如何为一个小批次的节点集 M 生成嵌入表示。我们首先计算每个节点的邻域，然后应用 K 次卷积迭代生成目标节点的第 K 层表示。最后卷积层的输出通过一个全连接网络生成最终的嵌入表示 zu。

损失函数

我们使用基于最大边界的损失函数。基本思想是我们想最大化正样本的内积，即查询条目和对应的相关条目的内嵌表示。同时我们想确保负样本（查询条目和无关条目的内嵌表示）的内积比正样本的内积小，并且小的程度超过一个提前定义的边界。因此一对节点内嵌表示 (zq, zi) 的损失函数定义如下：

较大批尺寸在多 GPU 上训练

为了在一台机器上充分利用多个 GPU 进行训练，我们以多塔的方式进行正向和反向传播。对于多个 GPU，我们首先将每个小批次（图 1 底部）划分为大小相等的部分。每个 GPU 接受小批次的一部分，并使用相同的参数集执行计算。反向传播之后，所有 GPU 上每个参数的梯度聚合在一起，然后执行一次同步 SGD。

生产者 - 消费者 minibatch 构造

在训练过程中，数十亿节点的邻接表和特征矩阵因其尺寸较大而被放置在 CPU 内存中。然而，在 PinSage 的卷积步骤中，每个 GPU 进程都需要访问邻域和邻域中节点的特征信息。从 GPU 访问 CPU 内存中的数据是不高效的。为了解决这个问题，我们使用重新索引技术创建子图 G’=(V’, E’)，其中包含节点及其邻域信息。在每个 minibatch 迭代开始时，G’的邻接表和小特征矩阵被送入 GPU，这样在卷积过程中不需要 GPU 和 CPU 之间的通信，大大提高了 GPU 的利用率。

采样负样本

为了提高大批次训练的效率，我们采样 500 个负样本，供每个 minibatch 中的所有训练样本共享。与单独为每个节点进行负采样相比，这大大节省了在每个训练步骤中需要计算的嵌入表示的数量。

在最简单的情况下，我们可以从整个样本集中均匀采样负样本，但这样的负样本构成对系统的约束太过“简单”，因为系统只需要确保正样本对（q, i）的内积比 q 和 500 个负样本的内积大即可，系统无法学习到足够细粒度的特征表示。为了解决这一问题，我们为每个正训练样本增加“更难”的负样本，即与查询条目 q 相关，但是不如正样本 i 相关程度高的负样本，我们称之为“难负样本”。它们是通过对图中条目根据个性化的 PageRank 分数进行排序而生成的。排位在 2000-5000 的条目被随机采样为“难负样本”。如图 2 所示，“难负样本”与其他随机的负样本相比，与查询样本更相似，因此对于模型来说挑战性也更强，使模型从更细的粒度上区分条目。

图 2：随机负样本和“难负样本”示意图。“难负样本”与其他随机负样本相比，与查询样本更相似，但是不如正样本相似。

在整个训练过程中使用“难负样本”将使训练所需的时间加倍。为了帮助收敛，我们制定了课程训练计划。在训练的第一个阶段，不使用“难负样本”，使算法在参数空间中快速找到损失相对较小的区域。然后，我们在随后的训练中添加“难负样本”，让模型学习如何区分高度相关的图钉和仅轻微相关的图钉。在训练的第 n 个阶段，我们将 n-1 个“难负样本”添加到每个样本的负样本集合中。

通过 MapReduce 的节点内嵌表示

由于模型训练过程节点的邻域会有重叠，因此许多节点在不同层被重复计算。为了保证推理阶段的效率，我们采用 MapReduce 方法实现无重复计算的模型推理。MapReduce 管道包括两个关键部分：

（1）一个 MapReduce 将所有的图钉映射到低维的隐空间，进行堆叠操作。

（2）另一个 MapReduce 将得到的图钉表示和他们所出现的钉板的标号相关联，然后通过池化其邻域的特征得到钉板的内嵌表示。

图 3：使用 MapReduce 计算第一层表示。第二层计算遵循相同的管道，只是输入是第一层表示，而不是原始条目特征。

高效最近邻查找

PinSage 产生的内嵌表示可以用于许多下游的推荐任务，我们可以通过在学习到的内嵌空间进行最近邻查找来完成推荐任务。即给定一个查询条目 q，我们可以通过查找查询条目 q 的内嵌表示的 K 个最近邻内嵌表示，来进行推荐。PinSage 模型是离线训练的，所有的节点内嵌表示都是通过 MapReduce 计算并保存在数据库中，高效的近邻查找操作使系统能够以在线方式提供推荐。

实  验

我们通过两个任务来评价 PinSage 生成的内嵌表示：推荐相关图钉和在用户的家庭或新闻订阅中推荐图钉。对于推荐相关图钉任务，我们选择查询图钉在内嵌空间的 K 个最近邻。我们使用离线排序衡量和受控用户研究来评估推荐相关图钉任务的表现。对于家庭订阅推荐任务，我们选择与用户最近钉在钉板上的条目在内嵌空间最接近的图钉。我们使用 A/B 测试来衡量对用户参与度的整体影响。

对比基线实验

（1）视觉内嵌表示（Visual）：利用深度视觉内嵌表示的最近邻进行推荐。视觉特征为 VGG-16 中提取的特征。

（2）注释内嵌表示（Annotation）：利用注释内嵌表示的最近邻进行推荐。文本注释内嵌表示使用 Word2Vec 模型训练得到。

（3）结合内嵌表示（Combined）：结合视觉内嵌表示和注释内嵌表示，利用一个 2 层感知器计算结合内嵌表示。

（4）基于图的方法（Pixie）：Pixie: A System for Recommending 3+ Billion Items to 200+Million Users in Real-Time

消融研究

• max-pooling（γ=max）

• mean-pooling（γ=mean）

• mean-pooling-xent

• mean-pooling-hard

• PinSage

离线评价

表 1：PinSage 与基于内容的深度学习基线方法的点击率和 MRR（Mean Reciprocal Rank）对比。总的来说，相比于最佳基线，PinSage 在点击率上提升了 150%，在 MRR 上提升了 60%。

内嵌表示相似性分布

图 4：视觉内嵌表示、标注内嵌表示和 PinSage 内嵌表示的成对余弦相似度的概率密度。其中 PinSage 的分布范围最广，证明了学习到的内嵌表示具有足够的分辨率。

用户调查

表 2：用户调查结果：哪种方法推荐的图像与查询图像更相关。大约有 60% 的用户更喜欢的条目是由 PinSage 推荐的。

图 5：不同算法推荐的 Pinterest 图钉结果。左边的是查询图钉，右边的是分别利用 Visual、Annotation、Pixie 和 PinSage 计算得到的推荐结果。

图 6：PinSage 内嵌空间的可视化图。我们发现到条目内嵌表示的接近性与内容的相似性很好地对应，并且同一类别的条目位于内嵌空间的同一位置。

产品 A/B 测试

A/B 测试对比了 PinSage 和其他基于内容的深度学习推荐系统在 Pinterest 上对于家庭订阅推荐的表现。我们通过观察用户参与度来衡量算法的表现，衡量指标为用户保存推荐的比例——repin 率。我们发现 PinSage 推荐的图钉更容易被用户采纳，其 repin 率大概超过 Visual 和 Annotation 内嵌表示方法的 10%-30%。

训练和推理运行时间分析

表 3：不同批尺寸的运行时间对比，当批尺寸 =2048 时，训练效率最高。

表 4：邻域 T 的选择对表现的影响。我们发现随 T 的增加，收益逐渐减少，并且两层的 GCN，邻域尺寸为 50 的时候能最好的捕捉到节点的邻域信息，同时保证计算效率。

总  结

这篇论文提出了 PinSage，一个具有高度可扩展性的图卷积网络，能够学习网络规模下包含数十亿数据节点的图结构，为节点生成内嵌表示。通过局部卷积、重要性池化等方法，大大提高了 GCN 的可扩展性。作者介绍了重要性池化和课程训练两个训练技巧，显著提升了算法的性能。作者将 PinSage 部署在 Pinterest 上，并且在多个推荐任务上全面地评估了学习到的内嵌表示的质量。广泛的离线评价、受控用户研究和 A/B 测试结果显示，PinSage 在项目 - 项目推荐任务（pin 相关的推荐）和家庭订阅推荐任务中都取到了最先进的性能。

查看论文原文：

https://arxiv.org/pdf/1806.01973.pdf

你也「在看」吗？👇