阅读总结：《Graph Convolutional Neural Networks for Web-Scale Recommender Systems》

Graph Convolutional Neural Networks for Web-Scale Recommender Systems

主要内容概括：

1、

模型：



优化：

大部分译文：

摘要：
图结构的深度神经网络在推荐系统应用中最近已经有很好的表现。然而，使这些方法变得实用，对于拥有千万物品和一亿用户的网络推荐系统，还有挑战。我们阐述了一个发展和应用在Pinterest上的大规模的深度推荐工程。 结合随机游走和图卷积 产生节点的嵌入 图结构和节点特征信息。
相比于之前的GCN方法，新颖的方法基于随机游走去构成卷积，并且设计了一个新颖的训练策略，依靠于更难的训练例子提高鲁棒性和收敛性。 应用于Pinterest并使用7500万个例子在一个三百万节点的图上，18000万条边。

1 introduction

…

主要的挑战是将基于gcn的节点嵌入扩展到具有数十亿个节点和数百亿条边的图。扩展GCNs是困难的，因为在大数据环境中工作时，它们的设计的许多核心假设都被违反了。例如，所有现有的基于gcn的推荐系统在训练过程中都需要在整个图拉普拉斯矩阵上运行——当底层图有数十亿个节点且结构在不断进化时，这种假设是不可行的。

现在的工作。在这里，我们展示了一个高度可伸缩的GCN框架，该框架是我们在Pinterest开发并部署在生产环境中的。我们的框架是一个基于随机漫步的GCN，名为PinSage，它运行在一个包含30亿个节点和180亿个edgs的大型图上——这个图比GCNs的典型应用程序大10,000倍。

PinSage利用了几个关键的见解，大大提高了GCNs的可伸缩性:

1、On-the-fly convolutions:

传统的GCN算法是通过特征矩阵乘以整个图拉普拉斯矩阵的幂来实现每一种形式的图卷积。相比之下，我们的PinSage算法通过对节点周围的邻域进行采样，并从这个采样邻域动态构造计算图，从而执行高效的局部卷积。 这些动态构建的计算图(图1)指定了如何围绕特定节点进行局部卷积，从而减少了训练过程中对整个图的操作。

2、Producer-consumer minibatch construction:

我们开发了一个生产者-消费者架构，用于构建小批量，以确保在模型培训期间最大限度的GPU利用率。

3、Efficient MapReduce inference ：

给出了一个训练有素的GCN模型，我们设计了一个有效的MapReduce管道，它可以分解训练有素的模型，为数十亿个节点生成嵌入，同时最小化重复计算。

除了这些基本的可扩展性的进步，我们还引入了新的培训技术和算法创新。这些创新提高了PinSage学习表示的质量，从而显著提高了下游推荐系统任务的性能:

1、Constructing convolutions via random walks:

取节点的全部邻域进行卷积(图1)，会产生巨大的计算图，因此我们采用采样的方法。然而，随机抽样是次优的，我们开发了一种利用短随机游动对计算图进行抽样的新技术。另一个好处是，每个节点现在都有一个重要性评分，我们在池/聚合步骤中使用了这个评分。

2、Importance pooling:

图卷积的一个核心组成部分是图中局部邻域特征信息的聚合。我们介绍了一种基于随机漫步相似度度量的节点特征权重方法，使离线评价指标的性能提高了46%。

3、Curriculum training:

我们设计了一个课程训练方案，在训练过程中对算法进行了较难和较难的训练，使算法的性能提高了12%。
通过广泛的离线指标、受控用户研究和A/B测试，我们表明，与其他可伸缩的基于深度内容的推荐算法相比，我们的方法在项目-项目推荐任务，以及一个“homefeed”推荐任务。在离线排名指标中，我们比最佳执行基准提高了40%以上，在面对面的人工评估中，我们的推荐在60%的情况下是首选的，而A/B测试显示，在不同设置下，用户参与度提高了30%至100%。据我们所知，这是深度图嵌入的最大应用，为基于图卷积架构的新一代推荐系统铺平了道路。

AB测试是为Web或App界面或流程制作两个（A/B）或多个（A/B/n）版本，在同一时间维度，分别让组成成分相同（相似）的访客群组（目标人群）随机的访问这些版本，收集各群组的用户体验数据和业务数据，最后分析、评估出最好版本，正式采用。

2 related work

…
然而，尽管GCN算法取得了成功，但是之前的工作还没有成功地将它们应用到具有数十亿个节点和edgs的生产级数据中——这一限制主要是由于传统的GCN方法需要在训练过程中对整个图Laplacian进行操作。在这里，我们填补了这一空白，并表明，GCNs可以缩放到生产规模的推荐系统设置涉及数十亿个节点/项目。我们的工作还展示了GCNs在真实环境中对推荐性能的显著影响。
在算法设计方面，我们的工作与Hamilton等(2017a)的GraphSAGE算法[18]和Chen等(2018)的[8]密切相关。GraphSAGE是GCNs的一种归纳变体，我们对其进行了修改，以避免对整个图Laplacian进行操作。我们从根本上改进了GraphSAGE，消除了整个图形存储在GPU内存中的限制，使用低延迟随机游走对生产者-消费者体系结构中的图形邻居进行采样。我们还引入了一些新的训练技术来提高性能，并引入了一个MapReduce推理管道来扩展到具有数十亿个节点的图。

3method

在本节中，我们将描述PinSage体系结构和培训的技术细节，以及使用经过培训的PinSage模型高效生成嵌入的MapReduce管道。
我们方法的关键计算量是局部图卷积的概念。生成节点的嵌入(即。,一个项目),我们应用多个卷积模块聚合特征信息(如视觉、文本功能)从节点的本地图附近(图1)。每个模块学习如何从一个小聚合信息图的邻居——罩、堆积等多个模块,我们的方法可以获得当地的网络拓扑信息。重要的是，这些局部卷积模块的参数在所有节点之间共享，使得我们的方法的参数复杂度与输入图的大小无关。

3.1 problem setup

二部图；I (containing pins) item and C (containing boards) user。我们的目标是利用这些输入属性以及二部图的结构来生成高质量的嵌入。然后，通过最近邻查找(即或将其作为机器学习系统的功能，对候选对象进行排序。

3.2 Model Architecture

我们使用局部卷积模块为节点生成嵌入。我们从输入节点特性开始，然后学习在图上转换和聚合特性的神经网络，以计算节点嵌入(图1)。
Forward propagation algorithm向前传播算法：我们考虑了为节点u生成一个嵌入的zu的任务，它取决于节点的输入特性和围绕该节点的图结构。
PinSage算法的核心是一个局部卷积操作，在这里我们学习如何从u的邻域聚合信息(图1)。
基本的想法是,我们将表示zv,∀v∈N (u) (u’s neighbors)通过密集的神经网络,然后应用一个聚合器/池功能(例如,element-wise意味着或加权和,表示为γ)对结果向量的集合(第1行)。
这个聚合步骤提供了一个向量表示nu, of u’s local neighborhood, N(u).。然后，我们将聚集的邻域向量nu与u当前表示的hu连接起来，并通过另一个密集的神经网络层(第2行)对连接后的向量进行转换。
此外，第3行中的规范化使训练更加稳定，并且对规范化嵌入执行近似最近邻搜索更有效(第3.5节)。
该算法的输出是u的一种表示形式，它包含了关于它自身和它的局部图邻域的信息。
Importance-based neighborhoods.: 我们方法中的一个重要创新是如何定义节点邻域N(u)，即，我们如何在算法1中选择要进行卷积的邻居集。以前的GCN方法只研究k-hop图邻域，而在PinSage中，我们定义了基于重要性的邻居圈，其中节点u的邻域定义为对节点u影响最大的T个节点。具体来说：我们模拟从节点u开始的随机游动，计算随机游动[14]所访问的节点的L1归一化标准化访问计数。然后将u的邻域定义为对节点u具有最高归一化访问次数的顶层T节点。
这种基于重要性的邻域偏移的优点有两方面。首先，选择要聚合的固定数量的节点允许我们在训练[18]期间控制算法的内存占用。其次，它允许算法1在聚合邻居的向量表示时考虑到邻居的重要性。特别是,我们在算法实现γ1作为一个加权平均数,根据L1规范化访问计数定义了权重。我们将这种新方法称为重要性池化。
Stacking convolutions：每次我们应用卷积操作(1算法）得到一个新的节点表示,我们可以彼此堆叠多个这样的运算上的能获得更多的信息节点周围的局部图结构。特别是,我们使用多层卷积,k层卷积的输入取决于k−1层的输出(图1),最初的表示等于输入节点的特征。注意，算法1中的模型参数(Q、Q、W和W)在节点之间共享，但在层之间不同。
算法2详细介绍了堆叠卷积 如何为一个小批量节点集M生成嵌入，我们首先计算每个节点的邻域，然后应用K个卷积迭代生成目标节点的K层表示。最终的输出卷积层是通过一个全连接的神经网络来生成最终的输出嵌入,∀u∈M。
全套参数模型,然后,我们学习的是:每个卷积层的重量和偏见参数(Q(k),q(k),W(k),w(k) ,∀k∈{1,…, k})以及最终密度的神经网络层参数,G1, G2, g。
算法1中第一行的输出维数(Q)的列空间维数在各层均设为m。为简单起见，我们设置了所有卷积层的输出维数(即，算法1第3行输出为）相等，我们用d表示这个size参数。模型的最终输出维数(应用算法2第18行)也设为d。

3.3 model training

我们以监督的方式训练PinSage，使用最大边际排名损失。在这个设置中，我们假设我们可以访问一组标记为L的项对，其中集合(q,i)∈L。项对假设是相关的，即,我们假设如果(q,i)∈L然后项目i是一个很好的推荐候选对于查询项q。训练阶段的目标是优化PinSage参数，为了对(q,i)∈L的输出嵌入在标记设置中离得很近。
我们首先详细描述基于margin-based的损失函数。在此之后，我们将概述我们开发的几种技术，这些技术提高了PinSage的计算效率和快速收敛速度，允许我们对数十亿个节点图和数十亿个训练示例进行训练。最后，我们描述了我们的课程培训方案，它提高了建议的整体质量。
Loss function. 为了训练模型的参数，我们使用了基于最大边缘的损失函数。基本思想是
maximize the inner product of positive examples-- the embedding of the query item and the corresponding related item.
Smaller --the inner product of negative examples—the inner product between the embedding of the query item and an unrelated item
损失函数-（待解）
解释消极样本抽样：
为了充分利用单台机器上的多个gpu进行训练，我们采用多塔方式进行正向和反向传播。对于多个gpu，我们首先将每个小批处理(图1底部)划分为大小相同的部分。每个GPU都使用minibatch的一部分，并使用相同的参数集执行计算。在向后传播之后，将所有gpu上每个参数的梯度聚合在一起，并执行同步SGD的单个步骤。由于需要对非常多的示例进行培训(规模为数十亿)，所以我们运行的系统批量很大，从512到4096不等。我们使用与Goyal等人提出的[16]类似的技术来保证快速收敛，并在处理大批量时保持训练和泛化精度。我们使用一个渐进的热身过程，根据线性缩放规则，将学习速度从小增加到第一个历元的峰值。之后学习速度呈指数下降。
Producer-consumer minibatch construction：在训练过程中，千万计的节点邻接表和特征矩阵由于太大了被放置在CPU内存中。然而，在PinSage的convolve步骤中，每个GPU处理需要邻居和邻居节点的特征信息。从GPU访问CPU内存中的数据效率不高，解决这个问题，我们使用重索引技术来创建一个包含节点及其邻域的子图g ’ =(V '，E ')，它将涉及到当前微型批处理的计算。提取了一个只包含与当前小批量计算相关的节点特征的小特征矩阵，使其顺序与G '中节点的索引一致。邻接表G`和小特征矩阵放入GPUs在每个小批量迭代开始的时候。因此在卷积的过程中GPU和CPU之间不需要通信，大大提高了GPU的利用率。
该训练程序交替使用cpu和gpu。模型计算是在gpu中进行的，而提取特征、重新索引和负采样则是在cpu上进行的。为了使多塔训练的GPU计算并行化，以及使用OpenMP[25]进行CPU计算，我们设计了一个生产者-消费者模式，在当前迭代中运行GPU计算，在下一次迭代中并行运行CPU计算。这进一步减少了将近一半的训练时间。
Sampling negative items ：在我们的损失函数(式1)采用负采样作为边缘似然[23]归一化因子的近似。为了提高大批量培训的效率，我们在每个小批量的培训实例中抽取了500个负面项目作为样本进行共享。这大大节省了在每个训练步骤中需要计算的嵌入的数量，而不是单独对每个节点执行负抽样。从经验上看，我们没有发现两种抽样方案的性能有什么不同。
在最简单的情况下，我们可以从整个集合中均匀地抽取反例。但是，确保正面示例的内积(对项(q,i))大于q，并且500个负面项中的每一个都过于“容易”，并且没有提供足够好的“分辨率”供系统学习。特别是，我们的推荐算法应该能够在超过20亿项的目录中找到1000个与q最相关的项。换句话说，我们的模型应该能够区分/识别200万项中的1项。但是对于500个随机的负项，模型的分辨率只有1 / 500。因此，如果我们从20亿项中随机抽取500个负项作为样本，那么这些项中任何一个与查询项稍微相关的可能性都很小。因此，在很大的概率下，该学习将不能进行良好的参数更新，也不能将稍微相关的项目与非常相关的项目区分开来。
为解决上述问题，对于每一个积极的训练实例(即，项对(q,i))，我们加上“硬”的否定例子，即，与查询项q有一定关联，但不像正向项i那么相关的项。我们将这些项称为“硬负项”。它们是根据图中查询项q[14]的PageRank评分对项进行排序而生成的。排名在2000-5000的项目被随机抽取为硬阴性项目。如图2所示，硬负面示例比随机负面示例更类似于查询，因此对模型进行排序很有挑战性，这迫使模型学会以更细的粒度区分项目。
在整个训练过程中使用硬否定项，可以使训练所需的时间翻倍。为了帮助融合，我们开发了一个课程培训方案[4]。在训练的第一个阶段，没有使用硬的负项，使得算法能够快速地在参数空间中找到损失相对较小的区域。然后，我们在随后的年代中添加硬的负面项目，重点学习如何区分高度相关的引脚和仅仅轻微相关的引脚。在训练的历元n中，我们为每一项向负项集合中添加n - 1个硬负项。

3.4 Node Embeddings via MapReduce

在对模型进行了培训之后，直接应用培训后的模型为所有项目生成嵌入仍然具有挑战性，包括那些在培训期间没有看到的项目。使用算法计算节点嵌入会导致节点的k跳邻域重叠而导致重复计算。如图1所示，在为不同的目标节点生成嵌入时，在多个层上重复计算许多节点。为了保证有效的推理，我们开发了一种MapReduce方法，它不需要重复计算就可以运行模型推理。
我们发现节点嵌入的推断非常适合MapReduce计算模型。图3详细描述了二部pin-to-board Pinterest图上的数据流，其中我们假设输入(即，“layer-0”)节点为引脚/项(layer-1节点为板/上下文)。
MapReduce管道有两个关键部分: (1)使用一个MapReduce作业将所有引脚投影到一个低维的潜在空间，在那里执行聚合操作(算法1，第1行)。(2)然后使用另一个MapReduce作业将生成的pin表示与它们所在的板的id连接起来，通过汇集其(抽样的)邻居的特性计算板的嵌入。
注意，我们的方法避免了冗余计算，并且每个节点的潜在向量只计算一次。2 .得到板的嵌入后，我们使用另外两个MapReduce作业来计算pin的第二层嵌入，方法与上面的方法类似，这个过程可以根据需要迭代(最多可迭代K个卷积层)

3.5 Efficient nearest-neighbor lookups ：

PinSage生成的嵌入可用于广泛的下游推荐任务，在许多设置中，我们可以直接使用这些嵌入，通过在学习的嵌入空间中执行最近邻居查找来进行推荐。也就是说，给定一个查询项q，我们可以推荐其嵌入是查询项嵌入的k近邻的项。

4 实验部分

为了证明PinSage的效率和它生成的嵌入的质量，我们在整个Pinterest对象图上进行了一套全面的实验，包括离线实验、生产A /B测试以及用户研究。

4.1 Experimental Setup

4.2 Offline Evaluation

表1比较了使用命中率和MRR的各种方法的性能。
PinSage使用我们新的重要池聚合和硬负面示例实现了67%的命中率和0.59 MRR的最佳性能，在命中率方面比*基线高出40%(150%相对)，在MRR方面也高出22%(60%相对)。我们还观察到，将视觉信息和文本信息结合起来比单独使用任何一种信息都要有效得多(与仅使用视觉/注释相比，组合方法的性能提高了60%)。

4.3 User Studies

表2显示了PinSage与4条基线之间的直接比较结果。在用户认为与之相关的项目中，约60%的预发酵项目是PinSage推荐的。

此外，我们还通过随机的方法将嵌入空间可视化选择1000个项目，计算二维t-SNE坐标如图6所示。我们观察到项目嵌入的接近性与内容的相似性很好地对应，相同类别的项目被嵌入到空间的同一部分。
注意，视觉上不同但主题相同的物品，在嵌入空间上也是相近的，这可以从图底部描绘不同时尚相关物品的物品看出。

4.4 Production A/B Test

最后，我们还报告了产品A/B测试实验，该实验比较了PinSage与Pinterest上其他基于深度学习内容的推荐系统在homefeed推荐任务上的性能。
我们发现PinSage一致推荐的pin比其他方法更容易被用户重新固定。根据特定的设置，我们观察到与基于注释和可视化嵌入的建议相比，repin的速度提高了10-30%。

4.5 Training and Inference Runtime Analysis

5 结论

提出了一种随机游走图卷积网络PinSage。PinSage是一种高度可伸缩的GCN算法，能够学习在包含数十亿对象的web级图中节点的嵌入。除了确保可伸缩性的新技术之外，我们还引入了重要性池化和课程培训的使用，这极大地提高了嵌入性能。我们在Pinterest上部署了PinSage，并综合评估了许多推荐任务的学习嵌入的质量，离线指标、用户研究和A/B测试都显示推荐性能有了显著的改进。我们的工作证明了图卷积方法在生产推荐系统中的影响，我们相信PinSage在未来可以进一步扩展，解决其他大规模的图表示学习问题，包括知识图推理和图聚类。

随机游走（random walk）也称随机漫步，随机行走等是指基于过去的表现，无法预测将来的发展步骤和方向。核心概念是指任何无规则行走者所带的守恒量都各自对应着一个扩散运输定律 ，接近于布朗运动，是布朗运动理想的数学状态，现阶段主要应用于互联网链接分析及金融股票市场中。