WWW 2018. 对随机游走进行了改进，提出了Pixie随机游走，实际上就是一个有偏的随机游走，根据相似度进行偏离，从而实现个性化推荐，而且使用了早停策略。原文链接：Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time
Abstract
现代内容挖掘应用中，用户体验依赖于高质量的个性化推荐。但是构建一个能提供这种推荐的系统由于商品和用户的数量太大，以及推荐结果需要对用户的实时操作进行响应等问题变得比较困难。我们提出了Pixie，一个基于图的，可扩展的实时推荐系统，部署在了Pinterest上。给定一组用户指定的pins作为查询，Pixie会实时地从十亿个可能的pins中选择那些与查询的query最相关的pins。我们使用Pixie随机游走算法，利用Pinterest图中的30亿个顶点以及170亿条边来生成推荐。实验表明，我们的算法对比之前基于hadoop的推荐系统，提升了50%以上的user engagement。此外，我们使用一种图剪枝策略使得推荐性能提升了58%。最后，我们在系统层面上讨论了Pixie，单台服务器每秒在延时60毫秒的情况下可以处理1200个推荐请求。现在，这个系统为Pinterest提供了超过80%的贡献。
Related Work
推荐系统是一个大且经充分研究的研究领域。我们总结了以下相关工作，聚焦于大规模的工业界推荐系统。
Web-scale recommender systems. 一些基于web的生产系统刚才已经提到了[1, 7, 21]。不像Pixie，他们不是实时的，他们的推荐结果都是提前计算出来的。实际中，响应时间小于100毫秒的就可以算作是实时，因为这样的系统可以和实时的服务流相结合。举个例子，如果我们推荐一个结果需要1秒钟，用户就得等太长的时间了。这些系统的推荐结果都是提前计算出来的，比如提前一天，然后存储成key-value对。但老旧的推荐系统都不怎么好。实时推荐系统因为它能对用户的反应实时的反应，所以变得很重要。对用户行为的实时反应可以提供更好的推荐结果。我们的实验表明实时推荐系统表现的比需要几天或几个小时才能更新的推荐系统好30-50%。
其他的实时推荐系统包括新闻推荐[9, 26]。然而，这样的系统只推荐最新的内容。我们这里的主要差别是规模，Pinterest的目录比传统的推荐系统多了1000倍。
Random-walk-based approaches. 很多算法使用随机游走利用图结构进行推荐[2, 3, 28]。或许，我们的工作和Twiiter的"who to follow"系统最相近[14, 15]，它们的系统将整个图放到一台机器中，运行一个个性化的SALSA算法[19]。这些蒙特卡洛方法考虑了一个顶点相对于其他顶点的重要性，推荐结果会根据这些分数生成[13]。我们开发了一种新的随机游走方法，更快，效果更好。
Traditional collaborative filtering approaches. 更一般地来讲，我们的方法与协同过滤相关，协同过滤通过挖掘用户图和商品图之间的交集部分，匹配用户与相似的商品偏好来生成推荐结果。系统过滤依赖于用户-商品矩阵的矩阵分解，生成表示用户和商品的隐向量[16, 17, 25, 30]。然而，基于矩阵分解的协同过滤算法的时间与空间复杂度最低是用户-商品图中顶点数的线性关系，使得使用这些算法在数十亿的商品以及百亿用户的问题上变得很有挑战。相比之下，我们的随机游走推荐算法与数据集的大小无关。
Content-based methods. 在纯基于内容的推荐系统中，对商品的表示只依赖于它们的内容特征[24]。许多先进的大规模推荐系统是基于内容的，经常使用深度神经网络[6, 8, 11, 29]。尽管这些算法凭借着参数空间的维度只依赖于特征空间的维度，能扩展到大的数据集上，这些方法并不能利用图结构的信息，而这点（图结构信息）对Pinterest很重要。
3. Proposed Method
Pinterest是一个用户与pins交互的平台。用户可以保存相关的pins到board中。这些board是相似pins的集合体。举个例子，一个用户可以创建一个关于食谱的board，将食物相关的pins放进去。Pinterest可以看作是一些boards，每个board是一组pins，每个pin又组成了成千上万不同的boards。形式化来说，Pinterest可以组成一个无向二分图 $G = (P, B, E)^2$ 。其中，$P$ 表示一组pins，$B$ 表示boards的集合。集合 $P \cup B$是 $G$ 的顶点集。如果用户 $p$ 保存了 $b$，那么在pin $p \in P$ 与 board $b \in B$ 之间就有一条边 $e \in E$。我们使用 $E(p)$ 表示连接到pin $p$ 的board顶点，$E(b)$ 表示连接到 $b$ 的pins。我们认为图 $G$ 是连通的，在实际中也是这样的。
Pixie接受的输入是一组带权的pins $Q = \lbrace (q, w_q) \rbrace$，其中 $q$ 是查询的pin，$w_q$是在查询集合中的重要度。查询集合 $Q$ 是用户指定的，并且在每次用户的行为后动态生成的，最近操作的pins有高的权重，随着时间的增长，权重会降低。给定查询 $Q$ Pixie会通过模拟新式的有重启的有偏随机游走来生成推荐结果。
3.1 Pixie Random Walk
为了更好的解释Pixie，我们首先解释最简单的随机游走，然后讨论如何将它扩展到Pixes使用的新的随机游走算法上。所有基于基本随机游走的创新对于Pixie提升性能来说都是至关重要的。
Basic Random Walk. 考虑一个简单的例子，用户指定了查询 $Q$，包含一个pin $q$。给定一个输入pin $q$，可以在 $G$ 上模拟出很多短的随机游走，都是从 $q$ 开始的，记录每个pin $p$ 的访问次数(visit count)，表示随机游走访问到 $p$ 的次数。如果一个pin被访问的次数越多，那么这个 $q$ 就和它越相关。
我们在算法1中描述了最基本的随机游走 $\rm BASICRANDOMWALK$ [28]。每个随机游走生成了一个 steps 的序列。每个 step 由3个操作组成。首先，给定当前pin $p$，(初始为 $q$ )，我们从 $E(p)$ 中选择一条连接 $q$ 和 $b$ 的边 $e$。然后我们通过从 $E(b)$ 中采样一条连接 $b$ 和 $p’$ 的一条边，得到pin $pin’$。第三步，当前的pin更新到 $p’$，然后重复之前的步骤。
游走的长度由参数 $\alpha$ 决定。所有的 这样的随机游走的 steps 的数量决定了这个步骤的时间复杂度，我们用 $N$ 表示这个和。我们维护一个 counter $V$ 用来映射 pin 和访问次数。为了获得推荐的pins，我们可以从返回的 counter 提取访问次数最高的pins，将它们返回作为推荐结果。这个过程的时间复杂度是固定的，与图的大小无关。
Pixie随机游走算法由算法2和算法3组成，在基础随机游走上有以下提升：
- 对用户指定的pin的有偏随机游走
- 多个查询的pin，每个都有不同的权重
- multi-hit booster对多个查询pins的增强
- 在保持预测性能的情况下使用早停减少随机游走的步数
(1)Biasing the Pixie Random Walk. 针对用户对随机游走进行偏离很重要。对于同样的查询集合 $Q$，推荐结果对于不同的用户应该不同。举个例子，Pinterest图包含了不同语言、不同主题，以及不同兴趣的用户的pins和boards，给用户使用的语言以及他们兴趣相关的推荐是非常重要的。
我们通过使用基于用户特征的随机的边选择方法解决了有偏随机游走的问题。随机游走倾向于遍历和用户相关的边。可以看作这些边对于图中的其他边有更高的权重/重要性。我们将随机游走在图的一个特定区域内进行偏离，使得它可以专注于pins的一个子集。这个修改在提高个性化、质量、以及推荐内容的话题性上的提升很重要，得到了更高的用户满意度。
Pixie算法使用一组用户特征 $U$ 作为特征（算法2）。注意，不同的Pixie调用不同的用户和查询，我们可以使用动态基于用户和边的特征的有偏边选择方法，这种方法可以提高Pixie推荐结果的灵活性。特别地， $\rm PIXIERANDOMWALK$ 使用 $\rm PersonalizedNeighbor(E, U)$ 选择对用户 $U$ 重要的边。这能使边匹配用户的特征/偏好，比如语言或话题。从概念上来看，这使得我们在针对用户进行游走偏离时可以获得最小的存储以及计算开销。本质上来看，可以将这种方法看作是针对每个用户，使用一个不同的图，这个图的边权重是针对这个用户定制的（但是不需要存储起来）。在实际情况中，由于性能原因，我们将权重限制在了一个可能值组成的离散集合内。我们避免了在内存中存储相似语言和话题的的边导致的开销，因此 $\rm PersonalizedNeighbor(E, U)$ 是一个子范围操作器。
(2) Multiple Query Pins with Weights. 为了全面地对用户建模，基于给定用户的全部历史信息是很重要的。我们通过基于多个pins，而不是一个pin的查询方式完成了这个要求。查询集合 $Q$ 中的每个pin $q$ 被分配了一个不同的权重 $w_q$。权重基于用户对这个pin进行操作之后的时间，以及这个操作的类型。我们使用以下方法生成一组查询 $Q$ 的推荐结果。我们对 $q \in Q$ 使用Pixie Random Walk（算法2），使用相互独立的计数器，如 pin $p$ 的计数器 $V_q[p]$ 对每个查询 pin $q$ 进行记录。最后，通过使用一会儿要提到的新的公式融合访问次数。
这里有个重要的见解，获取有意义的访问次数需要的steps的数量依赖于pin的度。从一个高度的pin，也就是出现在很多boards中的pin的推荐结果需要的步数要远多于从一个低度的pin。因此，我们给每个pin分配的步数正比于它的度。但是，如果我们线性的分配步数给每个pin，那最后有可能给低度的pin连一步都分配不了。
我们基于一个根据度数亚线性增长的函数来分配步数，通过一个缩放因子 $s_q$ 给每个pin的权重 $w_q$进行缩放。我们给每个 pin 构建如下的缩放因子：
$$\tag{1} s\_q = \vert E(q) \vert \cdot (C - \log{\vert E(q) \vert}) $$其中 $s_q$ 是 pin $q \in Q$ 的缩放因子，$\vert E(q) \vert$ 是 $q$ 的度，$C = max_{p \in P}(E(p))$ 是 pin 度的最大值。这个函数不会不成比例地给流行的pins高的权重。我们通过下面的公式分配步数：
$$\tag{2} N\_q = w\_q N \frac{s\_q}{\sum\_{r \in Q} s\_r} $$其中，$N_q$是分配给从pin $q$ 起始的随机游走的总步数。这个分布有我们想要的性质：给高度数的pins更多的步数，给低度数的pin充分的步数。我们在算法3的第二行实现了这个。
(3) Multi-hit Booster. Pixie算法的另一个创新是，通常来说对于查询集合 $Q$，我们想要的推荐结果是与 $Q$ 中的多个 pins 相关的结果。直观上来看，候选的查询与越多的 pins 相关，那么这个候选项与整个查询就越相关。换句话说，从多个 pins 得来的具有高访问次数的候选项比从单一 pin 得来的具有很高的访问次数的候选项对于这个查询更相关。
这里我们的见解是：让Pixie增强从多个查询 pins 得到的候选 pins 的分数。我们通过一种新的方法聚合一个给定的 pin $p$ 的访问次数 $V_q[p]$。而不是简单的对所有的查询 pins $q \in Q$，加和给定 pin $p$ 的访问次数 $V_q[p]$，我们将他们变换，这种方式会奖励那些从多个不同的查询 pins $q$ 多次访问的 pins：
$$\tag{3} V[p] = ( \sum\_{q \in Q} \sqrt{V\_q[p]})^2 $$其中，$V[p]$ 是 pin $p$合并后的访问次数。注意，当一个候选 pin $p$通过游走从一个单独的查询 pin $q$ 起始后访问到时，访问次数是不变的。但是，如果候选 pin 从多个查询 pins 访问到，那么这个值就会增强。就会导致，选择计数器 $V$ 得到的最高的访问 pins 时，multi-hit pins 的比例会更高。我们在算法3的第5行实现了这个。
(4) Early Stopping. 我们刚才描述的步骤会跑一个固定 steps 个数 $N_q$ 的随机游走。然而，因为 Pixie 的运行时间依赖于 steps 的个数，我们希望跑尽可能少的步数。这里我们可以通过对查询 $q$ 调整步数 $N_q$，而不是对所有的查询使用固定的 $N_q$ 来减少运行时间。
我们的解决方案是一旦前几个候选项稳定后就停止游走。因为 Pixie 推荐几千个 pins，如果朴素地实现，这个监控（判断候选项变不变）会比随机游走本身还费时。我们的方法通过两个实数 $n_p$ 和 $n_v$ 克服了这个困难。至少 $n_p$ 个候选项被访问了至少 $n_v$ 次就停止游走。这个监控简单而且高效，因为我们只需要一个计数器来追踪候选项是否被访问了 $n_v$ 即可（算法2的12到15行）。
我们在4.2节展示了早停策略与长的随机游走差不多的结果，但是差不多少了一般的步数，加速了一倍左右。
3.2 Graph Pruning
另一个重要的创新是图的清理与剪枝。图剪枝提升了推荐质量，也减少了图的尺寸，所以这个算法可以在更小的图、更便宜的机器上，提供更好的缓存表现。
原始的Pinterest图有70亿个顶点和超过1000亿条边。但是，不是所有的 boards 都是有主题的。大的多样的boards会让游走向多个方向扩散，使得推荐结果质量下降。相似地，很多 pins 被错误的分到其他的 boards 中。图剪枝过程会清理图，并且让它变得主题更专一。另一个好处是，图剪枝也会让图变小，可以放到单台机器的内存中。不需要将图分布到多台机器上就可以得到很好的性能，因为随机游走不需要在不同的机器上“跳跃”。
步骤如下：首先，通过计算 boards 的主题分布的熵，量化每个 board 的内容多样性。然后在每个 pin 的描述上使用LDA主题模型获取概率主题向量。使用加入到 board 中最新的 pins 的主题向量作为输入信号，计算 board 的熵。删除掉有很大的熵的 boards 以及他们的边。
另一个挑战是，真实环境的数据集有很偏的长尾分布。在 Pinterest中，意味着一些 pins 非常流行，有可能被存入了几百万个 boards 中。对于这样的顶点，随机游走需要运行很多步，因为它需要在一个有大量邻居的网络中扩散。我们通过有系统性地丢弃高度 pins 的边解决这个问题。我们丢弃了那种 pin 的主题不属于那个 board 的边，而不是随机地丢弃边。我们使用和上面同样的主题向量，使用特征向量的余弦相似度计算一个 pin 对于一个 board 的相似度，然后只保留具有高相似度的边。实际上，剪枝的程度取决于 $pruning \ factor \ \delta$。我们将每个 pin $p$ 的度更新为 $\vert E(p) \vert ^ \delta$，丢弃连接 $p$ 和 与 $p$ 相似度低的 boards 的边。
在剪枝后，图包含了10亿个 boards，20亿个 pins，170亿条边。比较有意思的是，我们发现剪枝有两个优点：1. 图的大小减小了6倍（内存开销）；2. 得到了58%的相关推荐结果。