Graph Convolutional Neural Networks for Web-Scale Recommender Systems

Introduction

Pinterest是一款以兴趣为基础的社交网络，提供图片瀑布流的用户体验，论文发表的时候还没有上市，估值蛮高，现在的话市值200多亿刀，用户看到一个图片如果喜欢的话可以pin到自己的board中，好友可以repin(转发)。

用户在Pinterest中自己感兴趣的东西用图钉(pin)钉在钉板(broad)，包扩20亿pin ，10亿board 以及180亿边（若pin在broad中，则它们之间存在一条边）

图片会有对应的主题，比如美食、穿搭、体育、美妆等等，自己的board也可以对pin在其中的图片分类。

 nod2vec 和 DeepWalk无法处理类似的图：

• 这些是无监督的方法；

• 他们无法引入节点特征信息；

• 他们直接学习节点的embedding， 模型的参数和图的规模是线性的，这种大图无法计算；

论文的优化点：

• 对GCN主要的改进

• 动态卷积(On-the-fly convolution) : 通过对邻居的采样，动态的构建计算图；

• 小批量计算(Producer-sonsumer minibatch construction) : CPU作为生产者采样节点，GPU作为消费者计算梯度；

• 管道化计算(Efficient MapReduce inference)：设计MapReduce的pipeline进行embedding泛化；

• 算法方面的改进：

• 短途随机游走(Constructing convolutions via random walks)： 通过random walks来采样出计算图；

• 重要性池化(importance pooling) ： 用带权的pooling方式，提升46%效果；

• 渐进式训练(curriculum training)：通过添加难的负样本提高训练效果，提升12%效果；

Method

Problem Setup

• Pinteres有两种节点：

• pins: 图片，boards:  用户整理的认为主题相关的pins集合；

• 20亿个pins, 10亿个boards, 180亿条边；

• 目标是利用pin-broard二分图结构和属性（如描述文本、图片特征），生成pin的高质量的embedding用于推荐任务（如相关pin推荐，或者作为机器学习系统的输入特征）；

• 将以上数据建模成二部图， I(pins集合)， C (boards集合)， 整个图节点: V = I + C

• 把pin和board分别当作item和user，这样就和其他推荐算法的使用相似了，只不过board不是特定的用户个体而是用户定义的某一个集合(更细粒度上的用户)；

Model Architecture

左上角是我们拥有的一张图，A点是我们的目标节点，我们希望通过深度为2的图网络获得A点的Embedding信息;

• 首先向下搜索A的所有一阶邻居(B、C、D)完成第一层搜索；

• 接着分别对B、C、D做向下搜索，得到B点的一阶邻居(A、C)、C点的一阶邻居(A、B、E、F)和D点的一阶邻居(A)，这时完成第二层搜索；

• 反过来通过卷积核向上计算更新每一层的节点向量，最终回到A点，完成一轮更新。

• 要完成整张图的更新，就需要对所有点执行操作(最下面的多个小图BATCH of NETWORKS)

前向推导算法(Forward propagation algorithm)

邻居重要性（Importance-based neighborhoods）

• 对于邻居的采样不是简单的随机采样，对于节点u的邻居定义了重要性， 然后模拟随机游走的算法去采集u的邻居

从节点u开始随机游走，统计每个节点的访问次数（L1正则化），取访问次数top的节点作为u的邻居 （引自《Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time》）

这样的好处：

• 可以选择固定个数的邻居做aggregate聚合；

• 当在聚合邻居信息的时候可以考虑邻居的重要性；

堆叠卷积（stacking convolutions）

• 第k层卷积的输入是k-1层的数据；

• 算法中层与层之间的参数（Q, q, W, w）对所有节点共享；

• 训练的时候用的minibatch:

获得M(全局图中大小为mini-batch的子图) 中每个节点二跳邻居（基于随机游走抽样， K=2），并保存成三个集合

生成M中每个节点embedding

15~16行是与GraphSage不同的，目标节点与各自邻居聚合之后的embedding并不是直接替换目前节点的当前embedding，而是经过一层dense层后再替换。

Node Embedding via MapReduce

如果直接使用上述PinSage的minibatch算法生成Embedding，会有大量的重复计算，如计算当前target节点的时候，其相当一部分邻居节点已经计算过Embedding了，而当这些邻居节点作为target节点的时候，当前target节点极有可能需要再重新计算一遍，这一部分的重复计算既耗时又浪费。

通过训练的模型泛化embedding到全部的节点，设计了一个两阶段的MapReduce的流程（因为K=2），其实就是embedding的两阶段传递：

• 第一个MapReduce，根据算法中的aggregation方法，把embedding进行聚合；

1）

pin的embedding; 执行聚合操作计算所有pins的Embedding 2）boards的embedding: 将pins和对应的boards匹配，基于采样后的board邻居特征（即pins的Embedding）做pooling得到board的Embedding

• 第二个MapReduce，用第一次聚合的embedding的输出，再做一次聚合；

两个任务执行完后第一层的卷积操作就算执行完了，如果有K层卷积操作，类似地再重复执行K-1遍这两个MapReduce任务，得到全量节点的Embedding后，导入到数据库中供下游应用查询

Experiments

Baselines

• Visual embedding: 图片的视觉信息

• Annotation Embedding ： Pins的文本信息

• Combined Embedding: 视觉+文本

• Graph-based（Pixie）: biased random walk based的方法，Pinterest的线上基础方法

• PinSage

没有对比其他的深度学习方法，因为图的规模，其他方法用不了

PinSage的变种

• max-pooling : 不带hard负样本的element-wise max

• mean-pooling：element-wise mean 

• mean-pooling-xent：用cross-entropy loss的，其他和mean-pooling一样

• mean-pooling-hard：加上了hard负样本的element-wise mean

• PinSage： 用了hard负样本和importance pooling

1、Offline Evaluation

• hit-rate: 对于正样本（q, i ），计算 q 的 top K （K=500，从500万中查找）近邻，统计样本i 在前500的比例；

• MMR（Mean Reciprocal Rank）:平均倒数排名， 考虑了物品i的排名信息

• embedding的评估：

• 评价模型的另一个考虑点则是模型的Embedding在向量空间中的分布情况，怎样是好的分布呢？

• 既然在推荐时经常采用距离最近的准则做筛选，以余弦距离为例，那首先希望的是Embedding可以在余弦距离为0的地方有较为稠密的分布，这是推荐模型要满足的最基本条件；

• 但如果所有的向量都聚集在空间中很狭小的区域，也可以“欺骗”我们达到这样的效果，所以还应该有更广的覆盖区间。如图所示PinSage既可以在余弦距离为0处有很好的聚集效果，也覆盖了更广的空间。

2、User Studies

• 找了一堆人，给他们PinSage和四个baseline归纳的图片，让他们评价谁更好

3、线上AB测试

• 比较了用户收藏pin的行为，提升了10-30%；

训练和线上推断的分析

• 在子图上去训练embedding和参数，对于新节点，通过推断去生成；

• 训练的时候使用3亿个节点（全图是30亿）的节点就可以达到最好的效果，通过添加更多的训练节点并没有明显的效果提升；

• 下图展示了，不同的batch size：

• 每一轮迭代的计算时间（毫秒）

• 收敛需要的迭代次数

• 整体的计算时间

• 下图展示了选取不同邻居个数的表现，最后他们选了50

直白的看PinSage没有对GraphSAGE在模型结构这些创新点上做出太多改进，但提供了一套完整的落地流程与验证。

比如MapReduce的应用，GPU-CPU的合理分配使用，这些工作是需要时间的积累，大量工程实际的训练才可以得来的。