基于SPARK的大规模网络表征算法及其在腾讯游戏中的应用

👉目录

1 背景介绍

2 算法设计

3 应用场景

图2：图数据上的任务

网络表征算法（Network Embedding）是目前使用比较广泛的提取图数据上节点特征的技术。这个技术可以为图上的所有节点计算一个指定长度的特征向量，使得在图上距离较近的节点，在特征向量空间中的距离也比较近。这些算法通常可以粗略地分为两种类型：基于随机游走的算法和基于矩阵分解的算法。如图3所示，基于随机游走的算法首先生成大量的随机游走路径，然后最大化节点在路径序列中的似然相似度；基于矩阵分解的算法则将节点的相似矩阵分解为节点特征向量的点乘。

然而，在数据量较大的图数据中，现有的网络表征算法具有较大的计算困难，主要是由于图数据可能较大而在单机内存中不能存储，并且计算算法较为复杂而需要较长的计算时间。另外，在公司中，我们大量的图数据都存储在分布式数据库 TDW。因此，我们创新性地提出采用分布式计算框架 Spark 来计算网络表征。

为了克服图遍历和模型训练中造成分布式计算中大量的通信代价，我们提出了基于递归图分割的分布式网络表征算法。这个方法，首先是运行递归图分割，其中每次迭代计算中的图分割将一个图分割成多个子图，如图4所示。这些子图主要有两类：基于同一个分区构建的 induced subgraph，和基于跨不同分区的边构建的 border subgraph。如果 border subgraph 的节点数比较多，则我们继续对 border subgraph 进行分割，直到每个子图的节点数量比较近似。

图4：图分割将一个图 G 分割多个 induced subgraphs 和一个 border subgraph

那么，这也就是暗示了我们可以通过每个子图上单独计算网络表征，然后通过融合这些子图的网络表征，可以近似地得到满足优化函数的网络表征。

如图5所示，最终的算法包括三个阶段：

（1）采用递归图分割，将图数据分割成多个大小比较相近的子图；

（2）对每个子图单独运行已有的网络表征算法，我们采用了 node2vec；

（3）将所有子图的表征进行融合，得到每个节点最终的表征。

[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