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

本文是AI前线第80篇论文导读，为你详细解读PinSage背后的技术细节。

介绍

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

其中最突出的是图卷积网络（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

创作场景

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