Rec - Large Scale Product Graph Construction for Recommendation in E-commerce
这篇论文想要解决什么问题？
解决大规模电商推荐系统中产品关系图构建的关键挑战。 论文关注的核心问题包括：
产品间关系的捕捉：理解并捕捉产品之间的关系是现代电子商务推荐系统的基础。这些关系可以被视为产品重构索引，能够根据给定的种子产品返回排名列表。
产品替代和互补关系：产品间存在两种非常重要的关系：替代关系和互补关系。替代产品是可以互相替换的产品，而互补产品是可能一起购买的产品。不同环境对推荐的相关性有不同的要求，因此需要不同的关系图来加速推荐。
挑战：大规模推荐系统面临的挑战包括准确性、鲁棒性、数据稀疏性、关系方向性和可扩展性。
为什么需要解决这些问题？
- 电商业务驱动：
- 规模：淘宝/Amazon 等平台每日需服务 数十亿用户、千亿级商品，传统推荐算法无法在 O(1)时间复杂度 内完成实时预测（如毫秒级响应）。
- 场景复杂性：用户行为分 “购买前”（需要替代品比较） 和 “购买后”（需要互补品搭配），单一关系图无法满足动态需求。
- 商业指标：推荐延迟 >200ms 会显著降低转化率（CTR/CVR），需通过 预构建产品图索引 加速召回。
- 数据挑战：
- 噪声：用户点击中存在大量误触、刷单等噪声，传统方法无法区分。
- 稀疏性：购买行为稀疏（点击/购买比例≈100:1），互补关系更难捕捉。
- 方向性：互补关系是 非对称 的（手机→手机壳合理，反向不合理）。
之前的算法以及优缺点：
| 类别 | 代表算法 | 优点 | 缺点（论文针对的痛点） |
|---|---|---|---|
| 协同过滤 (CF) | - Item-based CF [Sarwar’01] - User-based CF [Breese’98] | - 简单、易并行 - 无需内容特征 | - 仅局部相似度（如余弦/Jaccard），忽略用户-商品图的高阶结构 - 噪声敏感：误点击直接干扰相似度计算 - 稀疏性：共购数据稀疏，互补关系难以捕捉 |
| 内容推荐 (CB) | - TF-IDF 向量 [Pazzani’97] - 词袋模型 [Mooney’00] | - 解决冷启动 - 可解释性强 | - 文本特征噪声大：淘宝商品标题/描述由商家填写，质量参差不齐 - 无法捕捉隐含需求：如“红色T恤”与“红色运动鞋”的互补关系 |
| 混合方法 | - Amazon Item-to-Item [Linden’03] - Hybrid CF+CB [Burke’02] | - 结合多源信息 | - 复杂度高：需融合文本、行为、上下文，难以实时计算 - 扩展性差：O(N×M) 复杂度无法应对十亿级数据 |
| 图方法 | - 随机游走 [Koren’10] - 矩阵分解 [Rendle’10] | - 捕捉高阶关系 - 支持时序 | - 三阶以上计算爆炸：无法实时 - 稀疏性未解决：需大量采样或正则化 |
王树森老师的b站视频 例子： “我喜欢看《笑傲江湖》” + “《笑傲江湖》与《鹿鼎记》相似”+“我没看过《鹿鼎记》” ——> 给我推荐《鹿鼎记》。逻辑很简单，问题在推荐系统如何知道《笑傲江湖》与《鹿鼎记》相似？
量化用户对交互过的物品的兴趣，已知物品之间的相似度，预估用户对候选物品的兴趣：$$\Sigma like(user,item_{j}) sim(item_{j},item)$$
如何计算物品相似度？- 受众重合度越高，物品越相似 $sim(i_1,i_2) = \frac{|V|}{\sqrt{|W_1| |W_2|}}$；考虑用户喜爱程度：$$sim(i_1,i_2)=\frac{\Sigma like(v,i_1) like(v,i_2)}{\sqrt{\Sigma like^{2}(u_1,i_1)}\sqrt{\Sigma like^{2}(u_2,i_2)}}$$余弦相似度，把每个物品表示为一个稀疏向量，每个元素对应一位用户。
召回流程：
- 事先做离线计算
- 建立“用户->物品”的索引：记录每个用户最近点击、交互过的物品ID，这样给定任意用户ID，可以找到他近期感兴趣的物品列表。
- 建立“物品->物品”的索引：计算物品之间凉凉相似度。对于每个物品，索引它最相似的k个物品。
- 线上做召回
- 给定用户ID，通过“用户->物品”索引，找到用户近期感兴趣的物品列表(last-n)
- 对于last-n列表中每个物品，通过“物品->物品”的索引，找到top-k的相似物品。
- 对于取回的相似物品（最多有nk个），用公式预估用户对物品的兴趣分数
- 返回分数最高的100个物品，作为推荐结果。
Q：索引的意义在于避免枚举所有的物品。 Q：离线计算大（更新索引），在线计算小。
论文如何解决这些问题？
Swing
传统 CF 像 “数共同好友” 来判断两人是否相似，而 Swing 像 “检查共同好友的朋友圈是否也重叠。
“把『用户-商品-用户』这条二阶结构当成一个『稳固小三角形』，每出现一次就给商品对加分；用户之间重叠商品越多（越泛化），权重越低，最终累加得到抗噪的替代相似度。”
Swing 算法 3 步流程（对应论文 2.1）
构图
• 输入：用户-点击商品列表
• 输出：无向二部图 G=(U∪I,E)。计算相似度（公式 1）
• 对任意商品对 (i,j)，取共同点击用户集合 Uᵢ∩Uⱼ。
• 对其中每对用户 (u,v)，算
s(i,j)=Σ Σ 1/(α+|Iᵤ∩Iᵥ|)。
• α=1 默认，|Iᵤ∩Iᵥ| 越大→权重越小。用户活跃度惩罚（公式 2）
• 引入 wᵤ=1/√|Iᵤ|，最终
s(i,j)=Σ Σ wᵤ·wᵥ·1/(α+|Iᵤ∩Iᵥ|)。
• 越活跃的用户贡献越小。
复杂度：O(T·N²·M)，论文用 MapReduce/Spark 并行化。
并行实现细节（对应论文 2.2）
数据格式
• 每行：user → [i₁,i₂,…,iₙ]（该用户点过的全部商品）。Map 阶段
• 对每个 user 的每条边 (u,i)，广播到所有邻居，输出
key = (i, j) 或 (j, i)，value = u。Reduce 阶段
• 按 key=(i,j) 聚合得到共同用户列表 Uᵢ∩Uⱼ。
• 在本地计算 Swing 值，输出 (i,j,s(i,j))。工程优化
• Combiner 提前聚合，减少 shuffle 量；
• 爆款商品采样高频用户，防止 reducer 内存爆炸。
Q：如果两人越同质，那么在相似度上的贡献权重应该越大？ A：弱化泛化用户 Q：确实有泛化用户的存在，但这样会不会错过真正很像的用户？ A：用户权重惩罚项
Swing 算法：严谨定义与公式
1. 图模型
给定用户-商品二部图 ( \mathcal{G} = (\mathcal{U} \cup \mathcal{I}, \mathcal{E}) )，其中边 ( (u, i) \in \mathcal{E} ) 表示用户 ( u \in \mathcal{U} ) 对商品 ( i \in \mathcal{I} ) 的点击行为。
2. 相似度定义
对于任意商品对 ( (i, j) \in \mathcal{I} \times \mathcal{I} )，定义共同点击用户集合： [ \mathcal{S}_{ij} = \mathcal{U}_i \cap \mathcal{U}_j ] 其中 ( \mathcal{U}_i = { u \in \mathcal{U} \mid (u, i) \in \mathcal{E} } ) 为点击商品 ( i ) 的用户集合。
Swing 相似度定义为： [ \text{Swing}(i, j) = \sum_{u \in \mathcal{S}{ij}} \sum{\substack{v \in \mathcal{S}_{ij} \ v \neq u}} \frac{w_u w_v}{\alpha + |\mathcal{I}_u \cap \mathcal{I}_v|} ] 其中：
- ( \mathcal{I}_u = { i \in \mathcal{I} \mid (u, i) \in \mathcal{E} } ) 为用户 ( u ) 点击的商品集合；
- ( w_u = \frac{1}{\sqrt{|\mathcal{I}_u|}} ) 为用户活跃度惩罚权重（Adamic/Adar 形式）；
- ( \alpha > 0 ) 为平滑超参数（论文中默认 ( \alpha = 1 )）。
3. 复杂度分析
设：
- ( |\mathcal{I}| = T )（商品总数）；
- 平均商品度为 ( N )（每商品平均被 ( N ) 个用户点击）；
- 平均用户度为 ( M )（每用户平均点击 ( M ) 个商品）。
则 Swing 计算复杂度为： [ \Theta(T N^2 M) ] 通过 MapReduce/Spark 两级聚合实现线性可扩展：
- Map 阶段：广播用户点击向量；
- Reduce 阶段：局部计算商品对相似度。
4. 关键性质
- 噪声鲁棒：需至少两个用户共同点击商品对，误点击影响指数下降；
- 长尾友好：仅依赖局部二阶共现，无需全局统计；
- 可并行：无共享状态，适合分布式计算。
Surprise
1. 问题定义
给定用户-商品购买记录，学习互补关系
[
\mathcal{G}\text{purchase} = (\mathcal{U} \cup \mathcal{I}, \mathcal{E}\text{purchase}),
]
目标：为每件已购商品 (i) 输出互补候选商品列表，解决数据稀疏与时间敏感性。
2. 三级漏斗框架
| 层级 | 输入 | 公式 | 作用 |
|---|---|---|---|
| 类别级 | 商品类别树 & 共购 | (\theta(c_i, c_j) = \frac{N(c_j \succ c_i)}{N(c_j)}) | 先筛大类，降候选量 |
| 商品级 | 时序购买记录 | (s_1(i,j) = \frac{\sum_{u \in \mathcal{U}_{i \succ j}} \frac{1}{1+ | t_{u,j}-t_{u,i} |
| 聚类级 | Swing 相似度图 | (s_2(i,j) = s_1\bigl(L(i),L(j)\bigr)) | 用簇-簇共购补稀疏 |
3. 核心公式
类别相关度
[ \theta(c_i, c_j) = \frac{\left|{u \mid \exists t_{u,j} > t_{u,i},, i \in c_i,, j \in c_j}\right|}{\left|{u \mid j \in c_j}\right|} ]商品级互补分数（含时间衰减）
[ s_1(i,j) = \frac{\displaystyle\sum_{u \in \mathcal{U}{i \succ j}} \frac{1}{1+|t{u,j}-t_{u,i}|}}{|\mathcal{U}i|\cdot|\mathcal{U}j|}, \qquad \mathcal{U}{i \succ j} \triangleq {u \mid t{u,j} > t_{u,i}} ]聚类级互补分数
[ s_2(i,j) = \frac{\displaystyle\sum_{u \in \mathcal{U}{L(i) \succ L(j)}} \frac{1}{1+|t{u,L(j)}-t_{u,L(i)}|}}{|\mathcal{U}{L(i)}|\cdot|\mathcal{U}{L(j)}|} ]最终 Surprise 得分
[ s(i,j) = \omega \cdot s_1(i,j) + (1-\omega)\cdot s_2(i,j), \qquad \omega=0.8\ (\text{实验设定}) ]
4. 聚类实现（Algorithm 2）
- 图：以 Swing 相似度为权重的有向图 (G=(\mathcal{I},E))。
- 算法：Label Propagation（异步更新，阻尼系数 (\beta=0.25)，最大迭代 10 轮）。
- 复杂度：(O(|E|))，十亿节点 15 min 收敛。
5. 复杂度与效果
- 离线：共购-CF 1.3 h → Surprise 2.5 h（可接受）。
- 在线 A/B：
- CTR +35 %、CVR +183 %（vs. 共购-CF）。
- 长尾商品覆盖提升 2.1×。
6. 性质
- 稀疏鲁棒：簇级统计 + 类别过滤 + 时间衰减三重降稀疏。
- 方向保持：严格 (t_{u,j} > t_{u,i}) 保证互补方向性。
- 可扩展：MapReduce/Spark 并行，支持千亿边图。