老徐书房

推荐算法实战-7-召回（3）-图卷积

 
  • 2024年 04月05日

本文是推荐算法实战系列第七篇文章。

前面文章包括：

  1. 推荐系统简介
  2. 特征工程
  3. embedding
  4. 精排
  5. 召回（1）：传统召回以及召回中的loss设计
  6. 召回（2）：word2vec召回、FM召回和双塔召回

本文继续介绍召回模型：图卷积召回。

6、GCN召回：邻里互助

从某种程度讲，推荐算法就是在做“邻域学习”，融合“近邻”的用户、物料信息预估当前用户-物料的喜好。

这里的“近邻”并不是显式定义的，它是通过丰富的特征工程、特征交叉、模型设计等隐式挖掘的。

推荐模型的本质是预估“用户-物品”交互矩阵中每个元素的值，即每个用户对每个物品的喜好度。 原始的“用户-物品”交互矩阵数据不全，很多元素是空的，存在稀疏性和局部性，推荐模型需要“无中生有”，根据已有的数据预估每个元素的值。

为了解决稀疏性和局部性，推荐模型的学习过程必须充分依赖“邻里互助”。

GCN的功能可以描述为：根据图中每个节点的输入特征和图的拓扑信息，经过图卷积，生成每个节点的embedding。

图卷积的核心是，邻居节点的信息沿着边传递、融合到目标节点，并最终在目标节点聚合，得到目标节点融合了全局信息的Embedding。

6.1、GCN基础

GCN是图卷积神经网络，Graph Convolutional Network。

可以将推荐系统建模成一张图：各种实体（用户、商品、店铺、品牌等）作为图的节点；互动关系（点击、购买等）作为图的边。

GCN将召回建模成边预测问题（link prediction）。即预测两个节点间是否有边。如果用户节点u和物体节点t之间有边，那么t可以作为u的U2I召回结果。如果t1和t2之间有边，可以作为I2I召回结果。

  • 正样本：一条边两端的节点v1、v2构成正样本。
  • 负样本：为v1在图中随机采样一部分节点作为负样本。
  • loss：之前介绍的NEG、Sampled softmax、Marginal hinge、BPR loss都可以使用
  • embedding生成：GraphSage

GCN通过节点和边的拓扑结构建模了数据集中的用户-用户，用户-物料，物料-物料等各种邻域信息，它能充分利用这些拓扑信息生成embedding：

  • GCN能够让两个用户的信息，通过他们共同购买过的商品、或共同关注的品牌等媒介，相互传递，从而丰富用户建模时的信息来源。
  • GCN能够让两个物品的信息，通过它们共同属于的品牌、被相同关键词搜索过等媒介，相互传递，从而丰富物料建模时的信息来源。

6.1.1、GraphSage

GraphSage是GCN的一种实现思想。

在graphsage之前，GCN的实现大都是“直推式的”（transductive），预测和训练使用相同结构的图，训练图中未出现的节点预测时无法给出embedding。

graphsage不直接学习每个节点的向量，而是学习一个转换函数。只要输入节点的特征和连接关系，就能利用转换函数获得该节点的向量。所以，graphsage是“归纳式的”（inductive），训练时未曾出现的节点，也能获得向量表示。

graphsage的inductive性质，能够将训练结果扩展至新用户和新物料，成为GCN应用于推荐系统的主流方案。

其思路如下： \(\begin{aligned} h_v^0 &= x_v \\ h_v^k &= \sigma \Big( W_k \sum_{u \in N(v)} \frac{h_u^{k-1}}{|N(v)|} + B_kh_v^{k-1} \Big) \\ z_v &= h_v^{last} \end{aligned}\)

  • $h_v^0$:节点v的第0层卷积结果，等于节点v的特征向量xv。
  • $h_v^{last}$:节点v的最后一层卷积结果，就是节点v的最终的embedding向量。
  • 第二行表示第k层的卷积，由两部分组成：邻居节点信息和当前节点信息。前面部分表示节点v的所有邻居节点的上一层输出的聚合（average pooling），再用权重矩阵Wk线性映射。后面部分表示对节点v自己的上一层输出用权重矩阵B线性映射。最后经过非线性激活函数得到本层（k）的输出。
  • 融合邻居节点和目标节点信息，得到目标节点输出向量的过程，称作图卷积。和CNN、DNN等一样，图卷积也会执行多层以扩展目标节点的感受野。

如果忽略邻居节点，第k层的输出只依赖于本节点的上一层输出，它与MLP中的第k层的前代公式一模一样。这说明，GraphSage是MLP的一种改进。它在做MLP之前，先把节点v的邻居信息和节点v的旧信息融合。

邻居信息的融合可以通过简单的average pooling，也可以像前几篇文章介绍的EGES等模型一样，采用attention、concat等方式。

经过多层卷积后，单个节点使用的信息不仅包括本身、邻居节点，还会扩展到全部整个图网络，具有“全局视野”。用CNN的术语，GCN扩大了单个节点的 “感受野”（receptive field）。

6.2、PinSage：大规模图卷积

PinSage是Pinterest团队开发的召回算法。在30亿节点、180亿边的超大规模图上实现了GraphSage。

PinSage建模的是Pin（网址）和Board（网址的收藏夹）两类节点组成的同构二部图。

Pin节点有Id、文本、图片等特征。Board节点是一类特殊的只有ID特征的Pin节点。

PinSage是同构图，意思是图中只有一类节点和一类边。

PinSage的目标是学习高质量的Pin embedding，用于I2I召回。

  • 正样本：用户收藏了Pin1，系统给他推荐了若干相似Pin，如果用户收藏了Pin2，那么（Pin1、Pin2）构成正样本。
  • 负样本：随机采样
  • embedding生成：采用标准的GraphSage算法，根据当前节点的特征和邻居节点的信息，经过多层图卷积得到最终的embedding。采用concat方式融合本节点和邻居节点上一层卷积输出。

PinSage算法上没有创新，其亮点在于工程优化。

6.2.1、mini-batch训练

PinSage的难点在于图结构太大，节点和边数量庞大，无法完整载入内存。也无法在每次前代、回代时更新所有节点。

它的做法是，将训练过程分成多个mini-batch。每个mini-batch只处理一小批节点集合。根据输入的节点集合M，采样出一批邻居节点，只在这些节点构成的子图上训练。（备注：集合M如何得到，采样吗？）

每一个mini-batch的训练步骤如下：

  • 输入M：节点的集合。（当前batch的输入）
  • 输入N：邻居采样函数，N(u)从节点u的所有邻居节点中采样一部分。
  • 输出：M中每个节点的embedding。
  • loss：？？

构图过程自上向下，逐层展开：

  • K：卷积层数（超参数？）。
  • $S^{(k)}$：第k层卷积所在子图的输出节点，即目标节点。
  • 最后一层卷积的输出节点$S^{(K)}$ = M。由此向下，第k-1层子图的节点由第k层子图扩展而来。它包含第k层的输出节点和它们经采样的邻居节点。
  • 由此，可以得到每一层卷积所需要的子图。这些子图是原始图的一小部分，可以载入内存、GPU计算。

卷积过程自下向上，逐层卷积：

  • 第0层的卷积输入是每个节点的原始特征。
  • 从第1层开始进行图卷积运算。
  • 每层卷积，拿到当前节点和邻居节点的上一层输出，concat后，再经过卷积运算。
  • 最后一层的卷积输出再做一些映射（可选），作为节点的embedding。

为了进一步提升效率，PinSage实现了“生产者-消费者”结构：

  • CPU：为当前mini-batch生成计算子图的操作在CPU上运行，利用CPU的大内存优势。
  • GPU：负责在各层子图上实现卷积的前代和后代。
  • “抽取子图”和“子图上卷积”并发执行。

6.2.2、邻居采样

在大型推荐系统中，有些节点的邻居节点数高达上万，需要通过N(v)函数采样部分邻居节点。

PinSage基于“随机游走”的采样方式。

由图上某个节点p开始，进行若干次随机游走，记录随机游走过程中访问到的邻居节点和访问次数，记录为Visits[p][neighbor] = visit_count。访问次数表示该邻居的重要性。最后，Visits[p]中前N个邻居作为采样结果，纳入计算节点p的子图中。

Visits[p]还有其它用途：

  • 卷积过程中聚合邻居向量的AGG函数，可以采用加权平均，其加权系数来自Visits[p]
  • 对Visits[p]降序排列，排名3000-5000的节点被认为与p相关，但是相关性没有那么强，从中采样一部分作为p的Hard negative参与训练，提升模型的分辨力。

6.2.3、基于MapReduce的分布式推理

上述mini-batch训练过程还存在一些不足：

  • 它描述的是训练过程，不适用于推理过程。它采用“邻居采样”引入了随机性，线上预测时需要聚合节点的全部邻居。
  • 尽管两个batch包含的节点不同，但是它们的子图很可能包含相同的邻居节点。共享邻居节点的卷积被反复计算，浪费了算力。

PinSage开发了基于Mapreduce的分布式框架，并发生成各节点的embedding。

Mapper节点独立地将上一轮卷积得到的老向量映射成新向量，并发送给邻居节点。

Reducer节点接收邻居节点的卷积结果，聚合，生成新的向量。

6.3、异构图上的GCN

PinSage用于同构图，但是实际的推荐系统存在着多种实体（用户、商户、品牌等）和多种关系（浏览、关注、点击、购买等）。

业界尝试把推荐系统建模为异构图，并在异构图上做图卷积，利用多元化的节点和边信息，学习高质量的节点embedding。

图卷积的核心在于，邻居节点的信息沿着边传递、聚合到目标节点。

异构图上的卷积的难点在于，如何让不同类型的邻居节点分门别类地传递、聚合信息。

思路之一就是将异构图拆解成多个同构图。例如Pinterest提出的PinSage的升级版MultiBiSage：

  • 按照每种交互关系构建出一个同构二部图，一共拆成K个二部图。
  • 在每个同构二部图上执行PinSage或其它图卷积算法，得等Pin节点的Embedding
  • 将上述K个Embedding融合成一个Embedding，可以将它们当做序列，输入transformer进行self-attention。
  • 其结果是融合了各种交互关系的Embedding。

该思路是让节点之间的信息传递只发生在单一关系的同构图上，最后再融合各种关系下的卷积结果。

微信的GraphTR采用了完全不同的思路。它直接在异构图上卷积，不同类型的邻居节点在卷积时要分门别类。

  • GraphTR的异构图上，有用户、视频、视频标签、视频来源四类节点。
  • 在进行第k层卷积时，先将目标节点t的邻居节点按照类型分成四组。
  • 每一类下的所有邻居节点的k-1层卷积输出组成一个序列，该序列先和目标节点通过transformer聚合成一个一个向量。
  • 融合方式有两种：第一种，拿目标节点k-1层卷积输出$h_t^{(k-1)}$作query与某一类的邻居节点的序列作target attention，得到$h_{t-video}^{k}$，表示所有视频类邻居节点向目标节点聚合的结果。第二种，将目标节点和邻居序列先concat，再喂入transformer得到1+M个向量，再average pooling得到$h_{t-video}^{k}$。
  • 以此类推，对每一类邻居节点，得到一个聚合向量，最后得到四个聚合向量。
  • 对这四个聚合向量做FM pooling，得到目标节点t第k层卷积结果。 \(\begin{aligned} H_t^k &= [h_{t-video}^k,h_{t-user}^k,h_{t-tag}^k,h_{t-media}^k] \\ h_t^k &= \sum_{i=1}^4\sum_{j={i+1}}^4H_t^k[i] \odot H_t^k[j] \end{aligned}\)

GraphTR先用Transformer实现同一类型的邻居节点内部的信息交叉与融合，再用FM实现不同类型的聚合向量之间的信息交叉。

本文总访问量次

搜索