腾讯游戏自研学术效果:基于图支解的收集外征进修初始化技能


图是一种通用的数据外现方式,图算法渐渐大数据处理中展现其代价。收集外征进修算法举措目前比较主流的一种图数据处理算法,惹起学术界和工业界的极大兴味。

本文先容了 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/。

图 3:Google Scholar上与数据开掘相关的学术集会和期刊影响力排名



3.3 专利

  • 《收集外征进修的初始化技能》,申请号:201910309766.0

    《收集外征进修的超参数采纳方法》,申请号:201910220752.1

  • 《晋升收集外征进修算法功用的数据压缩技能》,申请号:201910557086.0

腾讯技能工程
腾讯技能工程

腾讯技能工程遗迹群中文字幕AV的实质专栏

表面自回归模子数据开掘图神经收集
11
以前果真没有人这么做过吗???哎,这几天也搞图支解的题目,觉得这个念法很简单,果真以前没人占坑。