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。下为一次随机游走的伪码。
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过小甚至为负。为此提出一种亚线性模型
其中，E（q）为节点q的度，wq时节点的权重，Q是查询集合。
3.5 hit booster
查询中每个pin都执行结束后，获得了若干个查询结果，最后是将这些结果进行合并。
对于查询结果中的某个pin值p，若其只产生于一次查询的随机游走（只与某个查询相关），和该pin出现在每次查询的随机游走中（与多个查询相关），其顺序应该是不同的。应该使得关联多个查询结果的pin排序更靠前。
最终的得分计算如下：
以上就是pixie random walk的主要部分，整个查询集合的伪码如下：
reference
- http://lipixun.me/2018/02/16/pixie