【论文笔记】www18 Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time

1.overview

论文地址

pintersert推荐第一部分–pinsage kdd18

这是pinterest推荐系统的第二部分。这也是pinsage中随机游走的原型。

一个基于随机游走的召回方案,这里的图不是协同过滤中的物品-用户交互图,而是pin和board之间的关联图。pin是指图片,board可理解为收藏夹,详细背景见pinsage。该论文解决的几个问题:

  • 大规模:单机可放下,易并行,易扩展
  • 实时更新:没有预计算,随机游走时early stop,且运行时间与图规模无关。

问题:给定一个查询q,找出相关的item。这里的查询q是一个pair set,每个pair包括一个pin和一个权重。最终返回的是基于这一组pin的相关的查询结果。

2. graph puring

这部分名字高级,但实际是一个数据清洗。且位于random walk之后,但实践中逻辑应该是先洗数据。

首先是用LDA topic model 进行了聚类。之后利用聚类结果,对高度节点一些错分的borad进行剪枝。

3. pixie random walk

查询集合中每个pin都要进行随机游走,这里以一个为例。

给定一个查询的pin,通过随机游走,每次随机游走时记录每个节点被访问的次数,最终根据节点的访问次数进行排序,获得相关的pin。下为一次随机游走的伪码。
【论文笔记】www18 Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time

3.1异质图上的随机游走

随机游走时,考虑到图是一个二分图(异质图),pin需要走两步才能得到下一个pin。这里基于meta-path实现的异质图上的随机游走。line7-line11为一次随机游走的过程。line7是从当前的pin出发,走一步到相邻的board上,line8在从board出发,到下一个pin,实现异步图上的随机游走。

line5表明该随机游走是带重启的。

3.2个性化推荐

basic的随机游走没有用户信息,所以推荐不是个性化的。personaizedNeighbor是实现个性化推荐,通过用户特征给邻居不同的权重。加入了user feature,相当于再随机游走是给不同节点赋于不同的权值,每个用户使用featrue在图上进行“修改”,避免了为每个用户保存一个独有的图。文中并没有详细的阐述该函数的细节,但给出了一些例子,如特征为语言和地区,借此来进行边的筛选。

3.3early stop

随机游走的运行时间主要取决与随机游走的步数step。随机游走的step越多,其结果越稳定,但所需的时间也越长。而不同的pin到达稳态所需的step应该是不同的。对于度较低的节点step少一些也是稳定的。为此,提出一种启发式的early stop。随着随机游走的进行,当其结果趋于稳定时,即若干step后,结果不发生变化,就可以停止。但对每个节点进行监视的代价过大,原文中提到该代价可能大于随机游走的代价。再次对其进行简化,至少由np个节点被访问了nHighVisited次,就停止。这个统计即为第10-11行。13行结束的条件也多了一个。

在后续实验中表明结果相对稳定。

3.4权重的处理

每个pin的权重是与时间相关的。权重主要是对随机游走时step由影响。

对于度较大的节点,出现在较多的board中,所以需要较多的step来迭代,使得度大的多迭代,度小的少迭代。如果分配step时按照节点度进行线性递减,可能会导致部分底度节点step过小甚至为负。为此提出一种亚线性模型

【论文笔记】www18 Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time
【论文笔记】www18 Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time
其中,E(q)为节点q的度,wq时节点的权重,Q是查询集合。

3.5 hit booster

查询中每个pin都执行结束后,获得了若干个查询结果,最后是将这些结果进行合并。

对于查询结果中的某个pin值p,若其只产生于一次查询的随机游走(只与某个查询相关),和该pin出现在每次查询的随机游走中(与多个查询相关),其顺序应该是不同的。应该使得关联多个查询结果的pin排序更靠前。

最终的得分计算如下:
【论文笔记】www18 Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time

以上就是pixie random walk的主要部分,整个查询集合的伪码如下:

【论文笔记】www18 Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time

reference

  • http://lipixun.me/2018/02/16/pixie
上一篇:1106 Lowest Price in Supply Chain (25 分)【难度: 一般 / 知识点: 树的遍历】


下一篇:java_stream分组操作