腾讯游戏自研学术成果：基于图分割的网络表征学习初始化技术

腾讯技术工程官方号

发布于 2019-10-18 09:40:04

6740

发布于 2019-10-18 09:40:04

图是一种通用的数据表现形式，图算法逐渐在大数据处理中展现其价值。网络表征学习算法作为目前比较主流的一种图数据处理算法，引起学术界和工业界的极大兴趣。本文介绍了 IEG 在网络表征学习方面的一个自研学术成果，最近被国际顶级学术会议 13th ACM International Conference on Web Search and Data Mining (WSDM 2020) 接收为学术长文。个人始终认为并且坚持研究与业务是可以相辅相成的。因此，该技术起源于对游戏业务优化的需求，升华于对技术细节的精益求精。
背景

网络表征学习算法将网络中的每个节点映射为一个长度固定的向量，并且这个向量的长度远远小于网络中节点数量。因此，网络表征学习算法得到的节点向量可以作为大部分机器学习模型的输入，从而能够应用到各种业务中。比如，在某RPG游戏的好友召回活动中，采用网络表征的算法比其他算法在回流率上相对提升了32.6%；在某MOBA游戏的师徒推荐功能中，采用网络表征的算法比其他算法在点击率上相对提升了4.48%。

网络表征学习的算法主要有DeepWalk、node2vec和LINE。然而，这些算法采用了非凸优化技术来求解模型，比如随机梯度下降算法（SGD）。但是，非凸优化技术的初始化对该技术的性能和效果都会产生较大的影响。如果选择了不好的初始化值，可能会导致计算结果集中在不好的局部最优（local minima）上。

国际人工智能学术会议AAAI 2018有个技术HARP也是为了解决网络表征学习初始化的问题。HARP采用多层次的网络压缩方法，容易将本应属于两个不同分区的节点合并为一个节点，比如网络结构中桥（bridge）上的两个节点，因此也不能很好地反映出网络结构的整体特点。另外，多层次的计算需要较高的计算量，特别是当网络结构比较大的时候。

为了克服上述问题和提高网络表征学习算法的性能，我们提出了考虑网络结构的基于图分割的网络表征学习初始化技术（Graph Partition Approach），简称为GPA。GPA技术先采用图分割算法将网络图结构分割成若干区块，接着将所得到的区块当作抽象节点，于是构建了一个抽象网络。最后通过计算抽象网络的表征，从而得到原网络的表征初始值。基于图分割算法，抽象节点之间的边具有最小分割边数（minimal edge cut）的特点，因此可以更好地刻画网络的整体结构。另外，基于图分割的技术不需要多层次的计算方式，可以减少计算量。

在多个实验中，验证了GPA可以明显地提高网络表征学习算法的效率和性能。具体来说，链路预测任务上相对于采用HARP技术初始化的方案提升了7.76%，在节点分类任务上则相对提升了8.74%。另外，在运行时间上，GPA也相对HARP减少了至少20%。

此外，我们还在一些游戏场景中验证了GPA技术对线上业务效果的提升作用。比如，在某类游戏的回流激励活动中，相对于无特殊初始化的方案，采用GPA技术的网络表征学习算法在点击率上相对提升了1.83%，在回流率上相对提升了6.43%。

2. 算法简述

本技术方案GPA采用四个步骤来生成网络的表征初始值，如图1所示。首先，GPA利用图分割算法将网络图结构分割成若干区块。然后基于分割区块，构建抽象网络，其大小将远远小于原始网络结构大小。在构建抽象网络时，我们把每个区块表示为一个节点（称为抽象节点），把区块之间的边合并成一条边（称为抽象边）。接着，我们采用网络表征学习算法计算抽象网络的每个抽象节点的节点向量。最后，基于传播算法，我们将抽象节点的节点向量传回该节点所表示的原网络结构里的节点，从而计算得到原网络结构里每个节点的节点向量的初始值。

图 1：基于图分割的网络表征学习初始化技术

在计算抽象网络的表征时，需要通过设置特定的超参数来运行网络表征学习算法，比如node2vec的超参数包括随机游走路径的长度和个数。这些超参数往往对模型和算法的性能起到了关键性的作用。然而，现有的网络表征学习算法没有提出如何快速地寻找合适的超参数，并且传统的超参数选择方法（比如网格搜索）具有较高的运行代价。因此，本技术方案还包括一个基于图属性和回归模型的超参数选择方法，如图2所示。

图 2：基于图属性和回归模型的网络表征学习算法超参数选取技术

更多技术细节请看提前发布的论文：https://arxiv.org/abs/1908.10697

3. 相关成果

3.1 业务效果

我们将本技术GPA应用在游戏的多个业务场景中，从而提升相关业务的效果。比如在某类游戏的好友召回活动中，我们需要为每个活跃玩家计算一个长度有限（比如10个）的推荐列表。每个活跃玩家的推荐列表上是流失玩家，并且是该玩家的好友。也就是说，好友召回活动是使用活跃玩家去召回流失玩家。基于本技术方案GPA，我们首先计算该游戏的社交网络上每个玩家的节点向量初始值，然后把这个初始值输入到node2vec算法中，得到玩家最终的节点表征向量。基于节点向量，我们计算活跃玩家与流失玩家之间的欧式距离相似度。然后，按欧式距离相似度，从小到大依次排序，从而得到每个活跃玩家的推荐列表。基于A/B test的评测方法，相对于无特殊初始化的方案，以及其他算法（比如Personalized PageRank），采用GPA技术的网络表征学习算法在点击率上相对提升了1.83%，在回流率上相对提升了6.43%。

3.2 论文

Wenqing Lin, Feng He, Faqiang Zhang, Xu Cheng, Hongyun Cai. Initialization for Network Embedding: A Graph Partition Approach.
Proceedings of the 13th ACM International Conference on Web Search and Data Mining (WSDM), full research paper, 2020.

WSDM是数据挖掘和分析领域成长较快的国际顶级学术会议，通常读作“wisdom”。如图3所示，在Google Scholar上的学术会议和期刊影响力排名中，WSDM在数据挖掘领域和数据库领域分别排名第4和第6。明年会议WSDM 2020的网址是 http://wsdm-conference.org/2020/。