Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time

• 概
• 符号说明
• Pixie

Eksombatchai C., Jindal P., Liu J. Z., Liu Y., Sharma R., Sugnet C., Ulrich M. and Leskovec J. Pixie: A system for recommending 3+ billion items to 200+ million users in real-time. WWW, 2018.

概

Pinterest 的一个大规模处理图的方案 (偏推理而不是训练).

符号说明

• \(P\) pins, \(B\) boards;
• \(E\) edges, pin \(p\) 归类到 board \(b\) 中则二者存在一边;
• \(G = (P, B, E)\), 图, \(P, B\) 为点集, \(E\) 为边集;
• \(q\) query, 用户相关的请求;
• \(Q = [(q_1, w_1), (q_2, w_2), \ldots, (q_{|Q|}, w_{|Q|})]\), 一组 queries.

Pixie

• 首先, 我们的任务是根据用户相关的一组 queries \(Q\) (其中 \(w_q\) 表示这个 query 的重要性), 然后基于此从图 \(G\) 中推断出最相关的一些 pins.

• Pixie 的思路很简单:

  1. 对于每个 \(q \in Q\), 进行随机游走得到一串 pins 的 counts (即经过某个 pin 的次数), 记为 \(V_q\);
  2. 通过某种方式 pooling 这些 \(V_q, q=1,\cdots, |Q|\), 得到 \(V\);
  3. 挑选 \(V\) 中最大的一些 pins 作为推荐.

• 不同于一般的随机游走, Pixie 采取的随机游走的是和用户的特征 \(U\) 相关的, 故而有个性化:

  1. currBoard = E(currPin)[PersonalizedNeighbor(E,U)];
  2. currPin = E(currBoard)[PersonalizedNeighbor(E,U)];
  3. V[currPin]++
  4. 重复直到达到最大的次数.

• 其中 PersonalizedNeighbor(E,U) 根据用户 \(U\) 计算边的权重.

• 最后的 pooling 的操作为:

  \[V[p] = (\sum_{q \in Q} \sqrt{V_q[p]})^2. \]

  这反映的直觉是, 假设两个 pin \(p_1, p_2\) 的总的经历次数是相同的, 但是 \(p_1\) 在不同的 \(q\) 的链上出现的出现次数差不多, \(p_2\) 则是频繁出现在同一条链上, 则推荐 \(p_1\) 是一个更好的选择.

• 下面是一些加速的 trick:

  1. 不同的起始点 \(q\) 设置不同的最大链长度 (依据 degree 大小), 此外采取早停策略 (如果top-K counts 的 pins 几乎不变, 则早停);
  2. graph pruning: 移除掉那些很杂的 boards (计算熵判断); 针对那些 high-degree 的点, 删除掉其中不那么重要的边. 这部分操作即带来了效率上的提升, 精度也有所提升 (主要是因为删除了一些噪声).