Pinterest在《Graph Convolutional Neural Networks for Web-Scale Recommender Systems》中提出了PinSage：
介绍
深度学习方法已经在推荐系统应用中非常重要，被用于学习关于图片、文本、单个用户的有用高维embeddings。使用deep models学到的representations可以被用于补全、或者替换传统的推荐算法（比如：CF）。并且这些学到的representations具有高可用性，因为他们可以被用在许多推荐任务中。例如，使用一个deep model学到的item embeddings可以被用于item-item推荐，并且可以推荐有主题的集合（例如：playlists，或者“feed”内容）
最近，在该领域内有较大发展——特别是能够基于在图结构化数据上学习的新deep learning方法的发展，这对于推荐应用来说很基础（例如：可以利用user-to-item交互图，也可以使用社交网络图）。
在这些成就中，最著名的是Graph Convolutional Networks（GCNs）深度学习结构的成功。GCNs背后的核心思想是：学习如何从局部图邻居（local graph neighborhoods）的feature信息中进行迭代式聚合（aggregate）（图1）。这样的一个“卷积（convolution）”操作会从一个node的一跳图邻居的feature信息进行转换和聚合，并且通过将多个这样的convolutions信息进行stacking可以传播到图的远方。不同于纯content-based deep models（例如：RNNs），GCNs会同时利用内容信息和图结构。GCN-based方法已经在无数推荐系统benchmarks上设置了一个新的标准。然而，在benchmark任务上的收益还没有转换到真实生产环境中。
同时将GCN-based node embeddings的training和inference扩展到具有数十亿nodes和数百亿edges的图上是一个巨大的挑战。当在一个大数据环境中，对GCNs进行扩展很难，因为在设计底下的许多核心假设是冲突的。例如，在训练期间，所有已存在的GCN-based推荐系统需要在整个图拉普拉斯算子（full graph Laplacian）上操作，因而是不可行：当底层图（underlying graph）具有数十亿nodes，它们的结构通常是演化的。
当前工作
这里我们提出了一个高度可扩展的GCN框架，我们在Pinterest的生产环境中开发和部署过。我们的框架，是一个random-walk-based GCN 称为“PinSage”，它在30亿nodes和180亿edges的一个大型图（massive graph）上操作——该graph是GCNs的常见应用的10000倍以上大。
PinSage会利用许多关键insights来弹性提升GCNs的可扩展性：
- on-the-fly convolutions：传统的GCN算法通过将feature matrics乘以full graph Laplacian的幂来执行图卷积。相反的，PinSage算法执行很高效，通过对在一个node周围的邻居进行抽样，并且从该抽样后的邻居来动态构建一个计算图。这些动态构建的计算图（图1）指定了如何在一个特定node周围执行一个局部卷积（localized convolution），并且缓和了在训练期间对整个graph操作的需求。
- Producer-consumer minibatch construction：我们开发了一个producer-consumer架构来构建minibatches，它能确保在模型训练期间最大化GPU利用率。一个大内存、CPU-bound producer可以有效抽样node network邻居，并且获取必要。
- 有效的MapReduce inference：给定一个fully-trained GCN模型，我们会设计一个有效的MapReduce pipeline，可以将训练好的模型分散来生成数十亿节点的embeddings，可以最小化重复计算。
图1
除了在可扩展性上的这些基础优点外，我们也会引入新的训练技术和算法创新点。这些创新点会改善由PinSage学到的representations的质量，从而能导致在下游推荐系统任务上获得大的提升：
- 通过random walks来构建convolutions：通过采用节点的所有邻居来执行convolutions（图1）会导致很大的计算图，因此，我们会采用sampling。然而，random sampling是次优的，我们会开发一种新的技术，它使用short random walks来采样计算图（computation graph）。一个额外的好处是：每个node具有一个importance score，我们会在pooling/aggregation step中使用。
- Importance pooling：graph convolutions的一个核心组件是：在graph中的局部邻居的feature信息的aggregation。我们会引入一个方法来对在该aggregation中的node features的importance进行权衡，它基于random-walk相似度measures，在离线评估指标中会有一个46%的效果增益。
- 课程培训（Curriculum training）：我们设计了一个Curriculum training的scheme，其中该算法会在训练期间feed越来越hard的样本，从而产生一个12%的效果增益。
对于在Pinterest中的多个推荐任务，我们已经部署了PinSage，它是一个用户可以对交互的pins进行流行内容发现和管理的应用，其中：pins是在线内容的一个可视化书签。用户会将这些pins组织成boards，它包含了许多相似pins的collections。总之，Pinterest是世界上关于图片的最大user-curated graph（用户组织图），具有20亿唯一的pins，被收集到超过10亿的boards上。
通过大量离线metrics、A/B tests，我们展示了：对比起其它可扩展的deep content-based推荐算法，我们的方法在一个item-item推荐任务上（例如：相关pins推荐）以及一个”homefeed”推荐任务上可以达到SOTA的效果。在离线ranking指标上，我们对比baseline获得了超过40%的提升，在head-to-head人工评估上，我们的推荐要好60%。。
据我们所知，这是最大的deep graph embeddings，为新一代基于graph convolutional结构的推荐系统铺平了道路。
2.相关工作
略
3.方法
在本节中，我们会描述PinSage结构、training、以及MapReduce pipeline的技术细节，可以使用一个训练好的PinSage模型来有效生成embeddings。
我们的方法的关键计算重任是：局部图卷积（localized graph convolutions）。为了为一个node（例如：一个item）生成embedding，我们会应用多个convolutional模块，它们会聚合来自该node的局部图邻居（local graph neighborhood）（图1）的feature信息（例如：可视化features、文本features）。每个module会学习如何从一个小的图邻居（graph neighborhood）来聚合信息，通过将多个这样的模型进行stacking，我们的方法可以获得关于局部网络拓朴的信息。重要的是，这些localizied convolutional modules的参数会跨所有nodes进行共享，使得我们的方法的参数复杂度完全取决于input graph size。
3.1 问题设定
Pinterest是一个内容发现应用，其中：
- 用户会将这些pins组织成boards，
- 用户会将比较相关的pins包成集合
总之，Pinterest graph包含了20亿pins，10亿boards，并且超过180亿的edges（例如：pins的成员和它们相应的boards）。
我们的任务是，生成pins的high-quality embeddings 或者 representations（例如：通过最近邻查询相关的pin推荐，或者在下游的reranking系统中使用）。为了学习这些embeddings，我们会将Pinterest环境建模成一个二部图，它包含了两个不相互交集合I（包含了pins）和C（包含了boards）的结点。注意，我们的方法也是天然泛化的，其中I被看成是一个items集合，C被看成是user-defined contexts和collections。
除了图结构外，我们也会假设：pins/items \(u \in I\)会与real-valued属性相关联，\(x_u \in R^d\)。总之，这些属性可以指定关于一个item的metadata或content信息，另外在Pinterest的case中，我们有：具有丰富文本信息和图片features有关的pins。我们的目标是，利用这些input属性，以及二部图结构来生成高质量embeddings。这些embeddings接着会被用于通过最近邻lookup的推荐系统的候选生成（例如：给定一个pin，发现相关pins）或者在对候选排序时作为features使用。
出于便利性和泛化性，当我们描述PinSage算法时，我们会简单地将完整graph的node set使用 \(V = I \cup C\)来表示，不会显式对pin和board nodes进行显式区别（除非严格必要），会统一使用更通用的术语“node”.
3.2 模型结构
我们会使用localized convolutinal模块来生成nodes的embeddings。我们从input node features开始，接着开始学习nueral networks，它会将通过graph来对features进行transform和aggregate来计算node embeddings（图1）。
前向传播算法
我们会考虑生成一个embedding的任务， 对于一个node u的\(z_u\)，它取决于node的input features和围绕该node的图结构。
算法1
PinSage算法的核心是一个localized convolution操作，其中，我们会学习如何从u的邻居（图1）的信息聚合。该过程在算法1 CONVOLVE中有详解。基本思想是：我们将关于u的邻居通过一个dense neural network进行转换成representations \(z_v \forall v \in N(u)\)，接着在vectors的结果集（第一行）上应用一个aggregator/pooling function（例如：一个element-wise mean或weighted sum，表示为\(\gamma\)）。该aggregation step会提供一个关于u的局部邻居\(N(u)\)的vector representation \(nu\)。我们接着将aggretated neighborhood vector \(n_u\)与u的当前representation \(h_u\)进行拼接，并将contantenated vector \(n_u\)与u的当前representation \(h_u\)进行concatenate在一起，并通过另一个dense neural network layer（第2行）将concatenated vector进行转换。经验上，我们观察到：当使用concatenation operation来替代average operation时会取得极大的效果提升。另外，在第3行中的normalization会使得训练更稳定，它对于normalized embeddings来说执行近似最近邻搜索更高效（第3.5节）。该算法的output是一个关于u的representation，同时包含了它自己以及它的局部图邻居间的信息。
Importance-based neighborhoods
在我们的方案中，一个重要概念是：如何定义节点邻居\(N(u)\)，例如：如何在算法1中选择要convolve的邻居集合。然而，之前的GCN方法会简单检查k-hop的图邻居，在PinSage中，我们定义了importance-based 邻居，其中：一个node u的邻居会被定义成T nodes会对node u施加最可能的影响。具体的，我们会从node u开始模拟random walks，并且计算出由random walk访问到的L1-normalized的节点访问数。u的邻居接着被定义成：对于node u具有最高的normalized visit counts的T个nodes。
该importnace-based邻居定义的优点是两面的。
- 首先，选择一个固定数目的节点来聚合，允许我们控制着在训练期间该算法的memory footprint。
- 第二，当聚合邻居的vector representations时，它会使算法1考虑邻居的importance
特别的，我们会在算法1中实现\(\gamma\)作为一个weighted-mean，它使用根据L1 normalized visit counts定义的weights。我们将该方法称为importance pooling。
Stacking convolutions
每个时间，我们会使用CONVOLVE操作（算法1），我们会从一个node处获得一个新的representation，并且将多个这样的convolutions相互进行stack，以便获得围绕node u的局部图结构的更多信息。特别的，我们会使用多个关于convolutions的layers，其中：在layer k上的convolutions的inputs依赖于来自layer k-1（图1）的representations output，其中：intial（例如：“layer 0”）representations等于input node features。注意，在算法1（Q,q,W,w）中的模型参数会跨nodes共享，但在layers间的参数则不同。
算法2会详细说明：stacked convolutions 是如何为一个nodes的minibatch set M生成embeddings。我们首先计算每个node的邻居，接着使用K个convolutional迭代来生成关于target nodes的layer-K的representations。final convolutional layer的output接着通过一个fully-connected neural network进行feed来生成最终的output embeddings \(z_u, \forall u \in M\)
我们接着学习模型的full set参数：对于每个convolutional layer \((Q^{k}, q^{(k)}, W^{(k)}, w^{(k)}, \forall k \in \lbrace 1,\cdots,K \rbrace)\)的weight和bias参数，以及最终dense neural network layer \(G_1, G_2, g\)的参数。在算法1中的Line 1的输出唯度（例如：Q的column-space维度）会被设置为，在所有layers上均是m。出于简洁性，我们将所有convolutional layers的输出维度设置为相当（算法1第3行），接着我们将该size参数通过d进行表示。该模型的最终output维度（算法2）也被设置为d。
算法2
3.3 模型训练
我们会以一个监督学习的方式，使用max-margin ranking loss来训练PinSage。在该setup中，我们假设：我们已经访问了一个关于items L的labeled pairs集合，其中：在该set中的pairs \((q, i) \in L\)会被假设是相关的——例如：我们假设：如果 \((q, i) \in L\)，那么item i是对于query item q的一个好推荐侯选。training阶段的目标是，最优化PinSage参数，以便在labeled set中的pairs \((q,i) \in L\)的output embedding 是非常接近的。
我们首先详细描述了margin-based loss function。根据此，我们给出了一个关于我们开发的多个技术的总览，它会导致PinSage的计算效率以及快速收敛，允许我们可以在数十亿节点的graphs和数十亿训练样本上进行训练。最终，我们描述了我们的curriculum-training scheme，它会提升推荐的总体质量。
Loss function
为了训练模型的参数，我们会使用一个Max-margin-based loss function。基本思想是：我们希望最大化正样本的inner product，例如：query item的embedding以及相应的相关item。同时，我们希望确认，负样本的inner product（例如：在query item的embedding和一个unrelated item间的inner product）要小于正样本由一些pre-defined margin给出的正样本。对于 \((z_q, z_i) \in L\)的node embeddings的单个pair的loss function：
\[J_G(z_q z_i) = E_{n_k \sim P_n(q)} max \lbrace 0, z_q \cdot z_{n_k} - z_q \cdot z_i + \Delta \rbrace\]…(1)
其中：
- \(P_n(q)\)表示了对于item q的负样本的分布
- \(\Delta\)表示了margin hyper-parameter
我们会在下面解释负样本的采样。
使用large minibatches的Multi-GPU训练
为了在单机训练上充分利用多个GPUs，我们会以一个multi-tower的形式来运行forward和backward propagation。有了多个GPUs后，我们首先会将每个minibatch（图1底部）划分成等size的比例。每个GPU会获取minibatch的一部分，并使用参数的相同集合进行计算。在backward propagation后，在所有GPUs上每个参数的gradients会聚合到一起，会执行单频synchronous SGD。由于需要在非常大数目的样本上（数十亿规模）训练，我们会使用large batch sizes进行运营，范围从512到4096.
我们使用由Goyal[16]提出的相似技术来确保快速收敛，当处理大的batch sizes时，并保持训练和泛化的准确率。我们使用一个渐近的热启过程（gradual warmup produre），在第一个epoch，根据线性scaling rule从小到大增加learning rate。之后，learning rate会指数递减。
Producer-consumer minibatch构建
在训练期间，由于size很大，对于数十亿nodes的feature matrix和adjacency list会在CPU memory中放置。然而，在PinSage的CONVOLVE step，每个GPU过程需要访问在邻居中节点的邻居和feature信息。从CPU内容中访问来自GPU的数据并不高效。为了解决该问题，我使用一个re-indexing技术来创建一个sub-graph \(G' = (V', E')\)包含了nodes和它的邻居，它会在当前minibatch的计算中被涉及。一个小的feature matrix会只包含了与当前minibatch的计算相关的node features，会被抽取出来，以便顺序与在G’中的nodes的index相一致。G’的adjacency list和small feature matrix会在每个minibatch迭代中被feed到GPUs中，因此，在GPU和CPU间的通信在CONVOLVE step期间不需要，极大提升了GPU利用率。
训练过程会交替使用CPUs和GPUs。模型会在GPUs中计算，然而：抽取features、re-indexing、negative sampling会在CPUs中计算。除了使用multi-tower training的并行GPU计算之外，CPU计算会使用OpenMP，我们会设计一个 producer-consumer pattern来在当前迭代中运行GPU计算，在下一迭代上并行使用CPU计算。这会进一步减少一半的训练时间。
对negative items进行采样
negative sampling会在我们的loss function中会被使用，作为edge likelihood的normalization factor的一个近似。当使用大的batch sizes训练时会提升效率，我们抽样一个关于500 negative items的集合，会在每个minibatch中与所有训练样本进行共享。对比起对于每个node独立运行负样本来说，这会极大节约需要在每个training step期间被计算的embeddings的数目。经验上，我们不会观察到在两个sampling schemes间效果的一个不同之处。
在最简单的case中，我们会从items的整个集合中均匀抽样负样本。然而，确保正样本（items(q,i)的pair）的内积大于q，500 negative items的每个都太“easy”，对于要学习的系统来说，不会提供足够好的“resolution”。特别的，我们的推荐算法可以发现在20亿items的catalog间与q 最相关的1000个relevant items. 换句话说，我们的模型会在20亿items上能够区分/标识 1个item。但在500个random negaive items，模型的resolution只有1/500. 因此，如果我们从20亿items中抽样出500个随机负样本items，任何这些与query items更轻微相关的items的机会更小。因此，该学习大概率不会做出好的参数更新，不能区分非常相关items和轻微相关items。
为了解决上述问题，对于每个正的训练样本（例如：item pair (q,i)），我们会增加“hard” negative examples，例如：items一定程度上与query item q相关，但与正样本item i不相关。我们称这些为“hard negative items”。他们会根据query item q的Personlized PageRank score通过在graph中的items进行ranking来生成。在2000-5000上排序的items会被随机抽样作为hard negative items。如图2所示，hard negative examples对比起random negative examples与query更相似，对于模型排序来说挑战更大，强制模型去学习以细粒度的方式区分items。
图2
通过training produre使用hard negative items，是需要训练至收敛的epochs数目的两倍。为了帮助收敛，我们开发了一个curriculum training scheme【4】。在训练的第一个epoch，不会使用hard negative items，以便算法快速发现在参数空间中的一个区域，其中：loss是相对小的。我们接着在后续epochs中添加hard negative items，聚焦于模型去学习如何区分高度相关pins和轻微相关pins。在训练的epoch n，我们会为每个item添加n-1个hard negative items到negative items集合。
3.4 通过MapReduce的Node embeddings
在模型被训练之后，直接使用训练好的模型来为所有items（包含了在训练期间没有见过的items）来生成embeddings仍然是很具挑战的。使用算法2以naive的方式计算nodes的embeddings，会导致重复计算，这是由nodes的K-hop邻居间的重合引起的。如图1所示，当为不同的target nodes生成embeddings时，许多nodes会在多个layers上重复计算。为了确保有效的inference，我们开发一个MapReduce方法，它无需重复计算即可运行model inference。
图3
我们观察到：node embeddings的inference可以非常好地借助于MapReduce的计算模型。图3详述了在二部图上的data flow，pin-to-board Pinterest graph，其中，我们假设：input（例如：“layer-0”） nodes是pins/items（以及layer-1 nodes是boards/contexts）。MapReduce pipeline具有两个关键部分：
- (1) 一个MapReduce 工作可以用于将所有pins投影到一个低维latent space中，其中：aggregation oepration会被执行（算法1，第一行）
- (2) 另一个MapReduce job接着用于将产生的pin representations，与他们出现的boards的ids进行联合，board embedding的计算会通过它的邻居的features进行pooling。
注意：我们的方法会避免冗余计算，每个node的latent vector只会计算一次。在boards的embedding会被包含后，我们会使用两个多的MapReduce jobs来计算关于pins的第二层的embeddings，以一个相似的方式，该过程可以尽快迭代（直到K个convolutional layers）。
3.5 高效地最近邻lookups
由PinSage生成的embeddings可以被用于许多下游推荐任务中，在许多settings中，我们可以直接使用在学到的embedding空间上通过最近邻查询这些embeddings来做出推荐。也就是说，给定一个query item q，我们可以推荐那些关于query item的embedding的embedding是K个最近邻。ANN可以通过locality sensitive hashing有效获得。在hash function被计算后，items的检索可以使用一个two-level检索过程，基于Weak AND操作符来实现。假设PingSage model通过离线训练给出，所有node embeddings会通过MapReduce进行计算，并在database中保存，有效的最近邻lookup operation可以确保系统以一个在线的方式提供服务。