萝卜兔作者pinterest engineering来源

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看起来同等相关,用户可以选择“同等”。如果三分之二的用户对同一个问题没有达成共识,我们认为结果是不确定的。

上图显示了比较结果,其中Pixie是一个纯粹的基于图的方法[3],具有最高分数的item将作为检索推荐。在用户认为更相关的item中,大约有60%左右的首选item是由PinSage推荐的。

上图给出了几种推荐的例子,分析了优势和劣势。最终视觉、文本和图信息,PinSage能够找到视觉和主题上都相似的推荐。

最后,在实际应用中,Pinterest的Shop and Look产品浏览量提高了25%,足以可见GCN在推荐系统中的强大。

参考链接

论文[1]:https://arxiv.org/abs/1806.01973

论文[2]:  https://arxiv.org/abs/1609.02907

论文[3]:https://arxiv.org/abs/1711.07601

https://medium.com/pinterest-engineering/pinsage-a-new-graph-convolutional-neural-network-for-web-scale-recommender-systems-88795a107f48

极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论推荐系统GCN
4
相关数据
深度学习技术

深度学习(deep learning)是机器学习的分支,是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。 深度学习是机器学习中一种基于对数据进行表征学习的算法,至今已有数种深度学习框架,如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

最近邻搜索技术

最邻近搜索(Nearest Neighbor Search, NNS)又称为“最近点搜索”(Closest point search),是一个在尺度空间中寻找最近点的优化问题。问题描述如下:在尺度空间M中给定一个点集S和一个目标点q ∈ M,在S中找到距离q最近的点。很多情况下,M为多维的欧几里得空间,距离由欧几里得距离或曼哈顿距离决定。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

TensorFlow技术

TensorFlow是一个开源软件库,用于各种感知和语言理解任务的机器学习。目前被50个团队用于研究和生产许多Google商业产品,如语音识别、Gmail、Google 相册和搜索,其中许多产品曾使用过其前任软件DistBelief。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

大数据技术技术

大数据,又称为巨量资料,指的是传统数据处理应用软件不足以处理它们的大或复杂的数据集的术语。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

推荐文章
暂无评论
暂无评论~