社群介绍算法在腾讯游戏的通常

本次分享的标题是社群介绍在腾讯游戏中的运行。第一部分将回答什么是社群介绍，为什么要启动社群介绍，以及如何启动社群介绍。第二部分将解说如何处置社群介绍冷启疑问，咱们提出了一个自顺应的社群检测算法，相关论文已宣布于 KDD 2024。第三部分将引见一个有解放的社群介绍算法，关键处置腾讯游戏社群介绍数据稀疏的疑问，相关论文宣布在 KDD 2023。最后一部分是对咱们团队的便捷引见。

社交网络的定义是由节点(团体)和节点之间的社会相关(亲人、共事、好友等)组成的网络结构。社交网络中的节点通常就是独立的团体，部分节点汇合构成社群，一个社群通常由咨询严密的人组成，社交网络中通常有多个社群。

再来便捷引见下社群介绍义务的 motivation，咱们宿愿经过社群介绍方式，为游戏内玩家介绍适宜的社群，从而优化游戏内用户生动度和付费率。

钻研标明，游戏社交网络中的社群其实是游戏社区兴盛的表现，游戏社群对优化玩家付费生动有正向作用。举个便捷例子，同一个社群内玩家或许有高生动度玩家，也有低生动度玩家，他们都在一个社群就会发生一些交互，比如对局、组队等行为。经过社群内玩家的交互，可以使高活带低活，从而优化社群内玩家总体生动度。

上方两幅图展现的是有社群玩家和无社群玩家的付费率，以及他们的游戏期间。可以发现有社群玩家游戏期间和付费率远高于无社群游戏玩家。所以咱们宿愿经过为这些无社群玩家介绍社群，激励他们添加社群，来优化最终社群内用户生动度和付费率。

除此之外，须要社群介绍还有一个要素，游戏内社群数量十分庞大，咱们的一个游戏或许有几百万甚至几千万的社群数量，用户在实在状况下去选用想要添加的社群时，就会存在信息过载的疑问。因此咱们宿愿用>

3.在腾讯游戏中运行社群算法

社群介绍面临诸多应战。首先，游戏内用户和社群的交互极端稀疏。在极端状况下，比如游戏产品刚刚上线，或许大部分用户都没有跟任何社群交互过，对社群而言，外面存在的玩家数量十分少，在这种冷启动的状况下咱们会结合一些社群发现算法经过 unsupervised learning 方式给玩家介绍一些潜在社群，推进玩家去构成一些新社群。

除此之外，游戏社交网络也是一个典型无标度网络，其规模十分渺小。在不同场景下，社交网络规模或许是几亿甚至十几亿节点的超大规模图。如何把 graph learning 的方法用到实在环球渺小规模的图上也是一个很有应战性的事件。

这里就引见一下咱们怎样样在实在的腾讯游戏运行场景群中用社群介绍算法。首先给定一个游戏社交网络节点，玩家边代表玩家间的交互。社交网络是社群介绍算法的输入，咱们经过算法和> 在这里咱们列了两个运行场景，一个是腾讯游戏中话题圈子介绍。望文生义，话题圈子和社团其实都是由一部分玩家、一部分用户去所构成的子个体，咱们要以一个个体为单位，将其当作一个 item 去介绍给不同的玩家，来激励他们添加到对应圈子或许社团中。

除此之外，还有好友和组队介绍等场景，咱们也偏向于给同一个社群内的玩家去介绍好友，激励他们成功一系列组队或对局等生动义务，经过社群内玩家高活拉低活的方式，优化社群内总体用户生动度。

接上去将详细引见咱们研发的两个社群介绍算法。

二、自顺应 K-Free 社群检测算法

首先是自顺应 K-Free 社群检测算法，咱们的目的是发现社交网络中潜在的社群，从而处置社群介绍冷启动疑问。

在设计算法之前，咱们首先对实在业务中遇到的痛点疑问启动了形象，将其方式化为迷信识题（算法疑问）。

社群检测算法在业务场景中的两个痛点为：

算法无法同时处置两个痛点。传统算法(如 Louvain)不须要社群数目先验，然而无法感知节点和社群的语义属性。深度学习算法(深度图聚类)可以联结学习语义属性，但须要社群数目先验。

这两种算法都没有方法处置咱们的业务疑问，所以咱们提出了 K-free 社群检测疑问。这个疑问就是在实在社群数目 k 未知的前提下，开掘同时有网络结构信息和语义结构特点的社群结构。

以传统的算法为例，其优化目的为模块度，即社群网络结构的严密水平，以模块度为目的优化进去的社群，其实是同一个社群内连边尽量浓密，社群间连边尽量稀疏。

但咱们只思索模块度目的是不够的，还要去思索一些语义的 semantic 目的。比如权衡社群内节点语义属性的相似性，也有一些算法去针对这些目的做一些独自的优化。同时咱们在实在社群中往往要权衡两类优化目的，正所谓物以类聚人以群分，咱们宿愿最终的社群 modularity 和 semantic 目的都高。

咱们在实在试验中发现，像 Louvain 这种算法检测进去的社群数量比实在数值要高很多。比如左边这张图，咱们以图上节点分类数据集为例，coral 数据集，咱们发现它实在类别数是 7，然而假设用 Louvain 算法划分社群则能分红 105 个，远高于咱们实在想获取的理想 k 值。但用 k-means 的话，虽然能刚好分红 7 个 cluster，然而它的 modularity 又十分低，或许仅仅是语义水平上相似，然而结构上齐全不相似（图上距离十分远）。

也有一些方法是用了如今比拟火的图神经网络这种深度学习方法去做深度图聚类，图神经网络是聚合图中街坊信息，来降级节点的示意，这一方式可同时启动图上结构和属性信息的联结学习，虽然处置了痛点一，但有一个限度，它要跟现有的聚类方法结合，比如像 k-means，要有一个先验 k。实在业务状况下，咱们不知道 k 究竟是多少，所以这类算法通常起来会有必定艰巨。

那么必定要有 k 吗？假设把深度图聚类中 k-means 聚类换一种聚类方式，比如密度聚类 DBSCAN 是不是就可以了呢？咱们经过实在试验发现这其实是无法以的，由于 DBSCAN 也有一些比拟强的先验参数，像搜查半径，而且它实在划分进去节点的一些特色空间散布会有必定解体疑问。比如像下图展现的，Coral 数据集其实是有 7 个实在类别，DBSCAN 容易将其划分为 3 个 cluster，并不是理想的状况。

那么经常使用 k-means，经过遍历 k，选模块度最高的 k 是不是就可以呢？这是可以的，但它的缺陷就是比拟低效。首先咱们要确定候选 k 的搜查范围，再去穷举或许搜查尝试，因此比拟低效。

既然这些方法都没有方法同时处置咱们的痛点疑问，咱们就宿愿经过联结学习的方式，既统筹特色与结构与语义信息，同时又自顺应地确定划分社群数量。咱们提出了深度自顺应的生成式的K-Free Community Detection 算法，简称 DAG。

DAG 关键由两个模块构成，这两个模块区分处置了前文的两个痛点。

接上去详细引见一下这两个模块是怎样上班的。在预训练阶段咱们会用 mask attribute reconstruction 链目的，随机采样一组节点，将对应属性交流为 mask token。而后经过 graph auto encoder 将其解码，获取重建后的 attribute，使重建后的 attribute 和实在未 mask 前的 attribute 尽量凑近。

第一步输入一个 input graph 即临界点矩阵 A，以及图属性矩阵■(~@X)。第二步随机 mask 一组 NODE 的对应属性，而后输入到 GNN encoder 里，再经过一层二重 mask，获取基于 mask 特色的节点示意。第三步经过 GNN decoder 获取重建后属性示意，最后计算 construction loss，这里是经过 GNN 聚合街坊信息的方式去复原某节点被 mask 掉的属性信息。

经过预训练 loss，咱们既捕捉了节点的结构属性，又捕捉了节点的语义属性。接上去咱们经过 readout 函数将节点划分红适宜 k 值，经过 readout 函数获取每个节点对应的社群 ID，readout 是一个神经网络，它的输入是一个高维稀疏向量。这个高维向量外面只要稀疏的 k 个维度被激活，这 k 个维度对应该节点属于的社群。

如何保障模型训练获取高维稀疏矩阵的同时又能学到社群数量呢？

咱们经过链路预测义务去捕捉网络中的结构属性，计算节点的 BPR loss，从而让网络中相邻的节点 embedding 更凑近，不相邻节 embedding 会更远一些。

引见到这里，这个 loss 其实只能获取一个成果，就是让这个 community application 的 result 函数进一步获取图结构的信息。

但如何保障稀疏性呢？当 k-searching 搜查社群数量时，添加一组稀疏解放。经过 readout 函数输入的是每一个 NODE 属于的社群 ID 向量。咱们会对这个向量做稀疏解放，比如对列做 L2 norm，同时对行做 L1 norm，L1 norm 是很强的吸入性解放。这样输入的 ID 向量散布概率在某一维比拟大，其余维比拟小，是一个横向稀疏向量。同时咱们在列方向加 L2 norm 稀疏性解放，这会使得 readout 函数输入比拟高维向量，但其实只要少数 k 维度对应的社群 ID 激活值比拟高。

这样咱们就无法把确定属性节点应该被划分红多少个社群的一个 case，经过稀疏解放方式，获取 readout hold，这个节点所属的授权 ID，同时保障社群数量适中，最终要保障预训练 loss，以及社群附属 readout 函数 BPR loss 都比拟低。再配合组稀疏 loss 就可以自顺应地获取 k 个社群。

除了模型外，咱们还提出了社交网络划分社群品质的评价目的，称为 EDGE Metric。这个目的处置了传统目的例如 modularity、模块度或许语义相似性难以权衡网络结构和语义相似度的权衡。咱们在原始论文中也做了一系列 theoretical 和 empirical study，去撑持目的的优点。

在实在的评价环节中，用户实在社群标签是未知的，训练虽然是 unsupervised learning，但评价其实还是须要用到大批人工标注的实在标签作为 Label，当标签比拟少时，如今罕用的处置方法或许是把一些分类数据集里样本的类别当作社群标签。

咱们发如今曝光转化率这个线上目的上，咱们的 model 相比于 baseline 优化大略在 4% 到 9%，像 DGC model，它的优化就比拟普通，甚至发生了负向增益。而咱们的模型有着比拟稳固的优化。

三、有解放的大规模社群介绍

咱们想处置的另一个疑问，就是在不知道社群数量k 的状况下去划分适当数量的社群，同时统筹结构和语义属性。服务的场景为，针对一些刚起步不久的腾讯游戏做冷启动的社群介绍时，可以无监视地发现一些社群。但假设游戏曾经是比拟成熟的产品了，曾经积攒了必定用户和社群 item 的交互历史，应用这部分信息再结合一些传统介绍算法，或许会到达更好成果。基于此 motivation，咱们又进一步做了有解放的大规模社群介绍算法 ComRec。这篇 paper 也雷同宣布在 KDD 会议上。

游戏场景中社群介绍解放疑问中的解放该怎样了解呢？

不同于传统社群，社交网络中社群，每一个用户在同一时辰只能添加一个社群，也就是说他不能同时添加两个社群。在传统的社交网络里，一个用户或许是属于多个社群，不同社群之间存在 overlap。但在咱们的 problem setting 限度下，有很强的 Constraint，用户在同一时辰只能在一个社群外面，用户只能从一个社群分开后，才干添加另一个社群。

社群介绍场景关键有两大应战：

咱们的社群介绍算法关键分为三个模块，一是标签模块机制-labeling agenda，它形容的是解放，同一个 NODE 在同一时辰只能添加一个社群。除此之外咱们经过一个图神经网络模块去获取对应的 user item 示意。为了统筹大规模图上的信息，及部分社群介绍，咱们做了一系列的优化，将其分红了 global propagation 和 local propagation。

社群标签机制是咱们要用向量示意节点，它能否属于某一社群是比拟便捷的示意方式，比如有 k 个社群，就用 K 维 one-hot 向量示意该节点是不是属于其中一个社群。然而这样会有一个疑问，咱们的社群或许是百万甚至千万级别的数量，one-hot 向量维度会很高，会给模型 learning 环节形成艰巨。在实践设计中咱们做了必定的解放安适，只会保养一个一维标签标注 NODE 是不是附属于某一社群，而不区分它详细属于哪个社群。

基于 label 机制，咱们的外围目的是宿愿标注 NODE 能否属于某一社群，还是不属于任何社群。咱们要进一步思索图神经网络是如何做信息传递的。传统的图神经网络在做信息传递时，每一个节点在每一轮降级都集聚合一切街坊信息，把街坊信息特色聚合后，经过一个图卷汇合，比如均值聚合获取一个向量，下一步就是经过聚合后的信息去降级节点向量示意。但在咱们的 setting 下，面临大规模图应战，同时须要做社群介绍，因此咱们宿愿同社群内节点的示意更凑近。

咱们的做法是，将其分红 global feature propagation 和 local feature propagation。Global feature propagation 是 column-wised propagation，比如保养一个 nd 维用户 feature embedding 示意矩阵，要在 column 维度上做一个 propagation，不同于传统的图神经网络，每一次性都会用一切街坊特色降级一切节点。咱们做了一系列优化，把原本 n^n 的复杂度变成了亚线性。

图上节点不是每一轮都会降级节点示意，而是会有必定提前，咱们的降级机制是每一个节点在累积接纳 message 到必定水平下，才会去降级节点示意。在详细成功上，思索到咱们是运行到一些工业场景，外围的计算代码是用 C++ 成功的，这优化了很多效率。

最终成果，在 2000 万节点的图上，只要要 30 秒就可以成功一次性极速计算。除了经过 global propagation 在整个图级别捕捉街坊节点信息和结构信息，以及结街坊散布的语义信息，还经过 local propagation 进一步增强社群示意，由于咱们的模型是用来做社群介绍的，社群其实是一个子图，local propagation 可以了解为是一个 subgraph 级别的 propagation，下图红圈圈进去的节点属于同一个社群，咱们就在同一个社群里启动信息传递，或许说启动 feature 的平滑，让同一个社群节点 feature embedding 愈加凑近，相似度更高。属于不同社群的节点，相似度更低一些。

经过火阶段 propagation，咱们在统筹高效率的同时增强了社群信息的语义结构学习。

咱们在少量数据集上启动了试验。首先是离线数据集的 setting，咱们在四个腾讯游戏的内社交网络数据集上做了试验，这几个数据集都是百万节点及千万节点边的 setting。同时咱们也对比了像传统的网络嵌入方法 （network embedding），以及仅经常使用属性特色的像 MLP 介绍模型，特色交叉的 learning model AutoIntCL，还对比了一些基于频率的协同过滤介绍算法，比如 LightGCN 和 LightGCN-E，以及 social recommendation 的 model，比如 GraphRec。

最终 ComRec 相比于 baseline 方法都有 3.5%~5% 以上比拟可观的优化。模型的离线成果是经过 hit rate 和 NDCG 等一些排序目的启动评价的。

咱们也把模型部署到了实在线上环境-游戏内社群介绍。实在环球中图的规模是比拟大的，其中有 2000 万节点，28 万社群数量，1.6 亿条边，咱们在这样一个大规模图上去启动线上试验，评价目的也换成了线上评价目的。比如 user item 点击率，以及把社群列表曝光给玩家之后的曝光经过率，即玩家点击社群，而后放开添加社群的比例是多少。咱们的模型在线上目的上相比于 baseline model 也有着比拟可观的优化。同时咱们也对比了不同模型的运转期间，咱们的模型在保管了更好的介绍成果的同时运转期间也是起码的。

感兴味的同窗也可以搜查咱们的论文，相关代码也是开源的，欢迎大家来与咱们做进一步交流。

最后便捷引见一下咱们的团队。咱们是腾讯互娱CDP 数据迷信中心社交算法组，努力于研发高效且有效的社交网络算法和技术，经过开掘海量图数据服务于游戏社交介绍的相关场景，比如前文中引见的战队介绍、社群介绍、游戏内好友介绍，以及社交流传影响力最大化和社交营销等多种场景，宿愿助力于游戏场景优化用户生动度和付费率。欢迎感兴味的同窗添加咱们来独特探求社交算法在腾讯游戏中的有限或许。

Q1：第一个算法聚类是 unsupervised 聚类还是 supervised 聚类？

A1：第一个算法是 unsupervised 算法。咱们第一阶段的优化目的，是 feature reconstruction 优化目的，也就是只要要知道节点的特色，咱们是没有任何的节点标签的，优化目的其实是纯无监视目的。

第二阶段社群附属模块 learning 部分，它的一部分优化目的是 link prediction，即拿到一个图结构后 mask 其中一部分 edge，而后预测这些 edge 存在的概率，也可以以为是一个 unsupervised 的环节，这个环节是 Nodewise 义务，然而并不触及任何 Nodewise 标签，前面添加的 group sparsity 解放，是在 learning 进去的 representation 矩阵上做稀疏性解放，只要要算 L1 norm、L2 norm 和 optimization 相关 loss。全体算法流程是 unsupervised 环节，最终运行也是在无监视场景处置一些冷启疑问。

Q2：前面提到的 BGC 算法能否

A2：当然是可以的。像 DGC 算法，它是先经过图神经网络去学习节点级别示意，每一个样本都有对应向量，基于向量再去做聚类，比如经过 k-means 聚类成 k 个 cluster。咱们实在的业务场景中是一个异质图，或许是多相关网络，只要要扭转前面 encoder 模块，假设网络相关是同质图就选用同质图 GNN，假设是异质图只要换成 heterogeneous GNN。

前面聚类时，由于 heterogeneous graph 或许会存在多种类型节点和边，或许只能锚定其中某一类型节点，比如用户节点，在用户节点示意上做聚类，更准确地说是在同种可比的类型节点上做聚类。同质图和异质图不同就是 encoder 以及最后聚类逻辑上会有一点不同。

Q3：预训练义务和实在介绍义务能否有偏？

A3：预训练义务和介绍义务确实有偏向，比如像 DAG 这篇 paper，咱们关键处置的是冷启动疑问。当咱们没有 user item 交互历史的时刻，咱们没有方法依据他的历史交互序列去精准捕捉用户用意，然而咱们知道一些其余信息，比如用户在社交网络里亲密相关信息、他在详细下游义务当中的亲密相关。咱们可以经过这些信息补偿这种偏向。但假设要齐全消弭这种偏向，前面引见的 ComRec 算法还是要应用用户历史的 community 的交互序列，依据他的历史交互行为才干更精准描写用户对社群偏好水平，才干做齐全无偏介绍。