云加社区
👉 目录
1 背景介绍
2 算法设计
3 应用场景
本文介绍了腾讯游戏社交算法团队研发的能够处理百亿级大规模图数据的分布式网络表征算法，及其在多个游戏业务场景落地应用，并且取得明显的实际业务效果提升。
01
背景介绍
大部分数据都可以用图来表示。如图1所示，在社交网络中，用户可以当做网络中的节点，用户之间的社交关系形成网络中的边；在网页链接网络中，网页形成网络中的节点，网页的超链接构成了网络中的边；在用户购买物品网络中，用户和物品分别形成网络的节点，用户购买物品的行为构成了网络的边。
图1：图数据
在游戏中，我们有大量的图数据，包括游戏中的好友关系、玩家互动关系、玩家与道具的关系等等。不同的图数据代表不同的信息。比如，平台好友关系网络是熟人关系网络，游戏好友关系网络是游戏中的陌生人网络，对局后的点赞行为形成的网络体现了玩家的游戏水平，道具购买网络展现了玩家的付费偏好。在这些图数据上的任务，通常有两种：链路预测和节点分类。在链路预测任务中，我们要预测两个没有连边的节点是否可能构建连边，比如好友推荐任务；在节点分类任务中，给定一些节点的类别，我们要预测其他节点的类别，比如预测玩家是否流失或付费任务。
解决上述图数据上的任务，可以通过机器学习的方法，也就是把节点在图数据中的特征输入到机器学习模型中（比如，XGBoost 或者 MLP），同时结合训练样本，从而得到一个预测模型，如图2所示。
图2：图数据上的任务
网络表征算法（Network Embedding）是目前使用比较广泛的提取图数据上节点特征的技术。这个技术可以为图上的所有节点计算一个指定长度的特征向量，使得在图上距离较近的节点，在特征向量空间中的距离也比较近。这些算法通常可以粗略地分为两种类型：基于随机游走的算法和基于矩阵分解的算法。如图3所示，基于随机游走的算法首先生成大量的随机游走路径，然后最大化节点在路径序列中的似然相似度；基于矩阵分解的算法则将节点的相似矩阵分解为节点特征向量的点乘。
图3：网络表征算法的两种类别及其优化函数
然而，在数据量较大的图数据中，现有的网络表征算法具有较大的计算困难，主要是由于图数据可能较大而在单机内存中不能存储，并且计算算法较为复杂而需要较长的计算时间。另外，在公司中，我们大量的图数据都存储在分布式数据库 TDW。因此，我们创新性地提出采用分布式计算框架 Spark 来计算网络表征。
02
算法设计
为了克服图遍历和模型训练中造成分布式计算中大量的通信代价，我们提出了基于递归图分割的分布式网络表征算法。这个方法，首先是运行递归图分割，其中每次迭代计算中的图分割将一个图分割成多个子图，如图4所示。这些子图主要有两类：基于同一个分区构建的 induced subgraph，和基于跨不同分区的边构建的 border subgraph。如果 border subgraph 的节点数比较多，则我们继续对 border subgraph 进行分割，直到每个子图的节点数量比较近似。
图4：图分割将一个图 G 分割多个 induced subgraphs 和一个 border subgraph
于是，我们可以对图3中给出的优化函数进行改写。对于基于随机游走的算法，优化函数可以分成两部分，一部分是同一个分区的节点之间的似然相似，另一个部分是不同分区的节点之间的释然相似。
相似地，基于矩阵分解的算法的优化函数也可以类似地分解成两部分：
那么，这也就是暗示了我们可以通过每个子图上单独计算网络表征，然后通过融合这些子图的网络表征，可以近似地得到满足优化函数的网络表征。
如图5所示，最终的算法包括三个阶段：
（1）采用递归图分割，将图数据分割成多个大小比较相近的子图；
（2）对每个子图单独运行已有的网络表征算法，我们采用了 node2vec；
（3）将所有子图的表征进行融合，得到每个节点最终的表征。
图5：分布式网络表征算法
03
应用场景
我们已经将本方案的分布式网络表征算法应用到超过5款游戏的多个业务场景中，包括好友推荐和道具推荐。其中，这些游戏来自多个不同的品类，并且大部分游戏的网络边数量超过百亿。表1展示了算法在多个游戏社交网络的运行时间。
| 游戏 | 点数 (亿) | 边数 (亿) | 运行时间 (h) |
| Game A | 2+ | 80+ | 10 |
| Game B | 7+ | 200+ | 16 |
| Game C | 6+ | 300+ | 21 |
| Game D | 1+ | 200+ | 23 |
| Game E | 0.04 | 2+ | 5 |
| Game F | 0.05 | 4+ | 7 |
同时，图6展示了分布式网络表征算法在多个业务场景中的应用效果。
图6：分布式网络表征算法在多个业务场景中相对原有方法的相对提升幅度
团队介绍
相关论文资料
[1] Wenqing Lin: Large-Scale Network Embedding in Apache Spark. KDD 2021
[2] Wenqing Lin, Feng He, Faqiang Zhang, Xu Cheng, Hongyun Cai: Initialization for Network Embedding: A Graph Partition Approach. WSDM 2020
-End-
原创作者 | 林文清
