1-1 大规模游戏社交网络节点相似性算法及其应用 - 林⽂清 腾讯游戏

Introduction

• 图形社交网络在 Web 和游戏中广泛应用，如友谊关系、俱乐部成员资格等。
• 图形可以是同质的（如友谊）或异质的（如俱乐部成员、项目交互），规模可达数十亿节点和千亿边。
• 应用包括朋友推荐、俱乐部推荐等。
• 链接分析和预测是关键问题，可通过学习节点邻近函数解决，包括排序现有边和预测新边。
• 经典方法包括 PageRank (PPR) 和共同邻居，但 PPR 存在不对称性，共同邻居需考虑高阶接近。

以前的工作

• PPR 定义为从节点 u 到 v 的随机游走概率，通过考虑所有可能路径计算。
• PPR 计算方法包括：
  • 功率迭代方法：空间复杂度 O(N^2)，需迭代直到收敛。
  • 蒙特卡罗方法：通过随机游走估计 PPR，适用于大规模图。
  • 加倍算法：合并段形成较长步行，但存在预处理和准确性问题。

我们的解决方案

• 并行管线框架：
  • 每条管道最多包含 M 个随机游走，每个随机数分多步生成，减少内存开销。
  • 后续管道有台阶，终止路径存储在内存中，活动路径继续扩展。
  • 预期轮数为 log(N/M) + 1 / (1-α) - 1。
• 随机邻居选择：
  • 小节点上存在缺陷，需优化选择方法。

优化

1. 别名方法：
   • 将权重转换为别名和切换概率，预处理阶段时间复杂度 O(N)，采样阶段 O(1)，空间复杂度 O(N)。
2. 处理大型节点：
   • 使用别名树将大节点邻居集分层组织，通过树遍历执行采样，时间复杂度 O(log N)。
3. 处理小节点：
   • 枚举大动作（长为 length-1 的移动），从大动作集生成多步随机游走，优化计算效率。
4. 优化启发式方法：
   • 根据可用内存和路径大小调整活动随机游走次数，提高吞吐量。

实验和部署

• 实验设置：
  • 使用内部集群（最多 201 台机器）和 13 个公共数据集（如 GraphX）。
  • 与 GXPPR 等方法比较，使用点击率等指标评估准确性。
• 优化影响：
  • 别名方法和别名树显著提升效率，处理大型节点和小节点效果显著。
• 部署：
  • 在腾讯游戏中用于友谊推荐，每日更新，基于 PPR(稳定) 和 TAP 排序。

Conclusions

1. 基于并行管道框架的分布式算法实现完全个性化 PPR 计算。
2. 采用别名树结构的分层采样算法避免大节点偏度。
3. 加快小节点计算的大动作。
4. 优化管道大小提高分布式算法吞吐量。
5. 在各种数据集上展示方法在效率和准确性方面的性能。