Pinterest：将GCN应用于图像推荐

Pinterest是国外的一款社交软件，采用的是瀑布流的形式展现图片内容，无需用户翻页，新的图片不断自动加载在页面底端，让用户不断的发现新的图片。可以说是图片版的Twitter，用户可以浏览、收藏、关注自己喜欢的图片。

该平台最主要的价值就是通过分析大量用户留下的兴趣痕迹，帮助用户发现和匹配他们感兴趣的想法和商品。随着用户量的增加和网站对象的增加，该团队不得不考虑如何使自己的搜索引擎变得更加智能。

2018年，该平台和斯坦福大学的研究人员共同发表了一篇论文，提出了PinSage的GCN[1]。

PinSage 背景

PinSage，一个能够学习节点嵌入的随机游走GCN，输入的图是包含数十亿对象的web-scale graph，图中的节点是图像。通过这种方法能够根据邻居节点的信息来实现更加强大和准确的节点嵌入。比如，如果让机器识别图像，床栏和花园栅栏会比较相似，让机器分辨起来很困难，但是在构建的Graph中，大门和花园栅栏通常会成为邻居节点，但是床和大门却很少相邻。通过graph的构建，可以建立其图像背后的语义关系，而不仅仅是图像的内容。

Pinterest工程师表示他们的PinSage是目前最大的深度图嵌入应用，并且也是图卷积在推荐系统中应用的一大突破。（该团队使用英伟达Tesla GPU的和cuDNN -accelerated TensorFlow深度学习框架，用大约18TB字节的数据，75亿例子图训练卷积网络，30亿board和Pin节点。）

目前业界将GCN应用于推荐系统的主要困难就是图的规模太大，可能有数十亿个节点和上百亿的边。而在大数据的工作环境中想要扩展GCN并不容易，比如现在的推荐系统在训练GCN的时候，都需要对全图进行拉普拉斯操作，但是对于有数十亿上百亿节点的大规模图来说，这不太可行。

PinSage 创新

PinSage则是一个高度可扩展的GCN框架，该框架可以对具有30亿个节点，180亿条边的图进行操作，这比一般的GCN应用的图大10000倍。

用户主要使用Pinterest来保存和管理他们感兴趣的在线内容的可视标签（Pins），包括食品、衣服、产品等等。这些Pins相关联内容的集合定义为boards。将Pinterest的环境建模为一个二部图，由两个不相交的集合组成，一个是Pins，一个是boards。简单来说Pin为一个item，board是用户定义的上下文。

on-the-fly convolution

传统GCN算法通过将特征矩阵乘上完整拉普拉斯算子的幂来执行卷积，PinSage则通过对节点周围的邻域进行采样并动态构建计算图来执行局部卷积。这些动态构建的计算图指定了如何在特定节点周围执行局部卷积，由此减轻在训练期间对整个图进行操作的需要。

图1

通过随机游走构建卷积

在完整的节点邻域上进行卷积将导致巨大的计算图，因此采取采样的方式。那如何定义邻域就需要考虑，也就是如何选择一组邻居进行卷积呢？在PinSage中，通过模拟随机游走并选择具有最高访问次数的邻居来定义基于重要性的邻域。这样做有两方面好处：

1、允许聚合器在聚合邻居向量时考虑邻居的重要性，将这种方法成为importance pooling。

2、选择固定数量的节点进行聚合允许在训练期间控制算法的内存占用。

Mapreduce inference

给定一个完全训练好的GCN模型，用训练好的模型为所有节点生成嵌入仍然是一个挑战，包括那些在训练中隐藏的节点。简单地计算具有局部共解的节点的嵌入会导致由节点K-hop邻域之间的重叠引起的重复计算。

图如1中所示，节点嵌入自上而下的聚合很适合Google的大规模数据集运算框架，Map reduce，在Mapreduce中将所有节点上的每个聚合步骤分解为三个操作：map、join和reduce。简而言之，对于每个聚合步骤，使用map将所有节点投影到潜在空间，而不需要任何重复的计算，然后join将它们发送到层次结构上相应的上层节点，最后reduce以执行聚合以获得上层节点的嵌入。

模型结构

Node embedding前向传播算法

考虑为节点z生成嵌入zu依赖与该节点的输入特征和邻域。

1、执行聚合函数，对u邻居节点的feature计算聚合表达,参数是每个邻居节点的权重。

2、第二行中选用concat()，因为根据论文[2]，concat的效果要比直接取这两者的平均更好。

3、第三行使得训练更加稳定，并且对归一化嵌入执行近似最近邻搜索更加有效（论文中第3.5节）。该算法的输出是一个u的表示，它包含了关于它自己和它的局部图邻域的信息。

模型训练算法

用户学习

通过在不同的学习表征之间进行比较看一看PinSage的有效性。在研究中，向用户呈现查询Pin的图像，以及通过两种不同的推荐算法检索的两个Pin。然后用户被要求选择两个候选Pin中的哪一个(如果有的话)与查询Pin更相关。用户被指示在诸如视觉外观、对象类别和个人身份等方面找到推荐Pin和查询Pin之间的各种关联。如果两个推荐Pin看起来同等相关，用户可以选择“同等”。如果三分之二的用户对同一个问题没有达成共识，我们认为结果是不确定的。