UC 热点资讯

作家：腾讯游戏搪塞算法团队

布景

游戏内的玩家和玩家间的交互关连组成了游戏搪塞采集，其中部分关连亲密的好友或者兴味邻近的玩家进一步组成了搪塞采蚁集的社群，举例游戏内的社团、俱乐部或者以某个大V玩家为环节的局部东谈主群所组成的子采集。同期社群亦然游戏内搪塞生态昌盛的一个发扬，参谋标明，社群内的玩家通常有着更高的搪塞度和活跃度，此外属于吞并个社群内的玩家通常有着邻近的活跃模式，因此对游戏内社群的挖掘和分析关于理解游戏内用户的搪塞和活跃模式意旨要紧。

图1：游戏社群检测颠倒利用暗意图

游戏搪塞采集具有采集范畴高大、语义特征丰富等特质，除了玩家之间海量的关连链数据（举例好友、情侣、师徒、组队等），还有丰富的玩家语义属性（举例玩家等第、战力、玩法偏好等），何如衡量搪塞采集的“结构”和“语义”信息从而充分挖掘游戏内敬爱迎合的用户群体是一项极具挑战性的任务。如图1所示，社群检测（community detection）旨在将搪塞采集永别为不同社群，以发现搪塞采蚁集兴味相似的东谈主，从而提高行为执行和资源投放的效力。传统的社群检测算法（举例Lovain等）大多只谈判搪塞采集的结构信息，将社群界说为社群内连络密集、社群间连络寥落的东谈主群，但其忽略了节点的语义信息；此外，已有的社群检测算法通常需要东谈主为指定社群数量K，并将搪塞采集永别为K个社群，但是委果的业务场景中通常莫得这么的先验学问，需要蹧跶大家学问和大王人东谈主力来笃定社群数量K。

基于上述挑战，咱们建议了深度自得当生成式社群检测算法DAG，从数据生成的视角建模搪塞采蚁集社群的产生经由，在不需要东谈主为指定社群数量K的情况下，自得当地将放浪的搪塞采集永别红恰当数量的社群，并通过图神经采集算法对搪塞采蚁集的结构和语义信息调节建模，从而充分挖掘搪塞采蚁集邃密连络并语义相似的社群。基于该算法，咱们不仅不错挖掘搪塞采蚁集的潜在社群并加深对社群内玩家步履模式的理解，还不错竣事对游戏内不同社群玩家的个性化资源投放，举例，咱们不错为偏好特定玩法的社群投放他们更感兴味的任务，并饱读舞吞并社群内的用户组队完成，以高活带低活的样式拉动社群内成员的举座活跃度，握续加多用户粘性。

咱们围绕搪塞采集挖掘、图神经采集、组合优化等工夫，握续优化社群挖掘和推选算法，并与游戏业务团队邃密互助，共同探索促进用户活跃度的运营模式，落幕现在咱们团队自研的社群挖掘、社群推选算法如故在好友组队推选、圈子推选、战队推选等多个腾讯游戏业务场景告捷落地，并取得了权臣的成果提高。底下将要点先容DAG算法颠倒在骨子业务场景中的成果。

计议责任和挑战

社群检测的轨范主要分为传统的社区检测以及深度图聚类算法，但是这些算法各自又存在不同的问题，即难以衡量图结构和语义属性，以及无法自得当寻找社群数量。

痛点一：难以衡量的拓扑结构和语义相似性

社区检测算法，如Louvain，通过最大化模块度的轨范来进行优化，模块度不错简单理解为“同社群内的边数与不同社群间社群的边数之差”。Louvain的刚正在于简单高效，况且不错自得当地找出社群的数量。

图2：传统社区检测算法暗意图

但是，由于传统算法的优化标的通常只局限于拓扑结构（边的数量），相通蹙迫的语义相似性会被疏远，这使得传统算法找到的社群结构通常是有偏的。在实验中，咱们发现通过传统社群算法（如Louvain）检测出的社群通常具有很高的模块度，但语义相似性却偏低。在游戏搪塞场景中，这意味着检测出的社群里面玩家枯竭语义上的共性和可解说性，这断绝了咱们将其利用到推选或者用户分析等卑劣任务中。

痛点二：未知的先验社群数量K

深度图聚类（Deep Graph Clustering，简称DGC）算法通过图神经采集来对图上的节点镶嵌进行考研，并将考研标的与聚类算法（如K-means）邻接起来。DGC轨范诚然概况在图的拓扑结构和语义属性中取得致密的衡量，但是需要一个先验的社群数量K四肢考研的超参数，社群数量K的考取极大影响了最终社群检测的落幕。但是业务需求中，咱们对潜在的社群结构通常莫得先验学问，很难找到一个准确的社群数量K。这等于所谓的“第二十二条军规”窘境——现存的轨范需要一个无法赢得的输入才智得到靠谱的输出。

图3：DGC的“第二十二条军规”

DGC轨范之是以需要先验的社群数量K ，是因为其考研标的和K-Means聚类是相互耦合的，DGC轨范会在考研中不休地进行K-Means聚类，并字据聚类落幕不休地修正考研的标的。K-Means自身必须要有一个K四肢参数，因此这个先验学问便不能或缺。这个时辰，可能有的一又友们要问：

Q1：能否换个不需要指定K的聚类算法？

咱们知谈，除了K-Means这么的基于均值的聚类轨范外，还有些不错自得当找到聚类个数的算法，举例DBSCAN这类基于密度的聚类轨范。咱们尝试将DGC轨范的K-Means聚类部分替换为了DBSCAN聚类，在公开数据集Cora上进行考研，并将考研完的节点镶嵌向量通过T-SNE降维并可视化。

图4：深度图聚类（DGC）算法邻接不同聚类模子的落幕（左：K-means聚类；右：DBSCAN聚类）

如图4所示，K-means算法（左图）会将采蚁集的节点永别为预设好的K个社群，这类基于强先验学问的聚类算法对超参数社群数量K的开采口角常明锐的。但是替换为 DBSCAN （右图）之后，模子考研出现了崩溃，扫数的节点镶嵌王人处于吞并个一语气的流形上，因而无法得到显明的社群关连。

Q2：可否穷举扫数的K并选一个最优解？

一种暴力解法是起首指定一个社群数量K的候选鸿沟，然后算法遍历得到一个“最好的K”。但是在委果的业务中，社群数量K的鸿沟通常无法先见，况且社群检测是一个无监督任务，咱们很难找到有效的监督筹商，卑劣任务需要进行 A/B Test 来收罗用户响应，自身既耗时也充满不笃定性；此外，每尝试一个新的K 王人需要从头考研通盘模子，这使得模子考研老本骤增。为了进一步诠释，咱们使用社群检测中最流行的筹商——模块度，四肢揣度社群质地狠恶的无监督筹商，以公开数据集Cora上的实验为例，已知该数据集右7个委果的社群类别，咱们使用了四个不同的 DGC 模子将 K 从 2 遍历到 14，并记载模块度的变化情况。

图5：不同的社群数量超参数K对已有社群检测算法的影响

如图5所示，对扫数的社群检测算法来说，无监督筹商最高的场合王人不是先验的数字7，大部分的轨范跟着社群数量提高，模块度有更高的趋势。遍历K取最高筹商的有缱绻既低效，成果也不太令东谈主舒心。

要最初容

在本责任中，咱们将上述业务问题详细化为科学问题，初度建议并界说了K-Free社群检测任务：在不需要指定社群数量K的情况下将搪塞采集永别为合适数量的社群。为了处治这一问题，咱们建议了深度自得当社群检测算法DAG（Deep Adaptive and Generative），从数据生成的视角对社群数量K和社群检测任务进行调节学习。DAG 起首用Mask AutoEncoder (MAE) 四肢节点镶嵌的预考研，让节点镶嵌同期包含自身拓扑邻居的语义信息（痛点一）；进一步DAG使用社群附庸采集（CAN）建模搪塞采集的生成经由，这么无需聚类，不错成功通过模子读出每个节点的社群ID。在此基础上，DAG将搜索K退换为了一个可微分的社群礼聘问题。这个退换使得DAG不错端到端同期学习社群的数量和节点的社群附庸（痛点二）。

图6：本文建议的DAG社群检测算法暗意图

接下来分别先容DAG的每一个模块：

1. 掩码属性重建模块

该模块使用一个图自编码器（Graph AutoEncoder）对节点特征进行重建。起首咱们在图上赶紧采样一组点，并对采样出的点的属性特征进行掩码，然后将经过掩码的图输入图神经采集（GNN）编码器进行编码，生成图上节点的镶嵌H，并对之前赶紧采样点的镶嵌进行二次掩码（替换成和镶嵌等长的mask token），终末咱们使用一个GNN解码器对图上的镶嵌进行解码，收复那些被掩码点的原始特征。考研的失掉函数如下式所述：

接下来，咱们以掩码属性重建模块学习到的节点镶嵌四肢输入进行社群检测。咱们想象了一个无需任何聚类的读出（Readout）模块，其成功输出节点属于每一个社群的概率。

具体讲，咱们通过一个基于寥落料理的社群附庸采集（Community Affiliation Network, CAN）来进行社群数量和社群附庸的调节学习。如图7所示 ，图中的矩形节点是游戏搪塞采蚁集的玩家，他们的好友关连组成了委果的搪塞采集。CAN 的假定在于，施行搪塞采蚁集的节点之是以存在好友关连，是因为他们有肖似的社群关连。如图7左上角所示，咱们假定存在编造的社群节点（圆点），和搪塞采集的成员节点变成了一个带权二部图，而每个搪塞采集成员节点和社群节点的边权涌现了玩家关于该社群的附庸概率。

假定有K个社群和N个节点，那么每个节点王人有个长度为K的社群附庸向量c，扫数节点的社群附庸则可刻画为一个N×K的社群附庸矩阵C，关于第i个节点，它所属于的社群id等于对应社群附庸概率最大的维度：

而基于CAN的假定，两个搪塞采集的成员节点是否有好友关连则取决于社群附庸关连的相似度。因此，咱们不错使用BPR loss对采集进行考研，这不错视作一个链路瞻望任务：

其中点 i 和 点 j 之间存在好友关连，而点 i 和点 u 之间不存在好友关连，咱们为每一条边 (i, j) 赶紧采样了一组不存在边的节点对 (i, u)四肢负样本。

3. 基于组寥落料理的社群数量搜索

终末咱们基于社群附庸模块的输出竣事端到端的社群数量搜索。在此，咱们作念了一步问题退换，DAG将原始的社群数量搜索问题退换为该合并（删除）若干豪阔社群的问题，而这种删除是通过对参数矩阵的列进行寥落化料理竣事的。咱们使用组寥落（Group Sparsity）料理来竣事自得当的冗余社群删除，界说为：

通过组寥落料理，咱们不错将权重矩阵的列数开采为一个较大的数值kmax，在考研经由中，由于组寥落会让一些权重列变为零向量，因此模子的输出鸿沟将从kmax种可能社群徐徐减轻并拘谨到一个“最好K值”。

实验落幕

咱们在腾讯某MMORPG游戏的好友推选模块中部署了咱们的算法，将游戏中的日活玩家看作图上的一个节点，并将放浪的好友关连视作一个无权的边，构建了游戏好友的关连采集。在好友推选模块中，每当某玩家点击推选模块，模块将复返给玩家一个排序后的好友列表；当玩家点击了某个好友后，好友会受到邀请，并礼聘是否欢跃组队；若好友欢跃组队，玩家和该好友将解锁特定的组队玩法任务以获取奖励。字据推选模块的想象，咱们使用了三个评价筹商：

点击率：玩家点击了推选模块后，点击好友发送邀请的比率。组队率：当好友收到邀请后，好友欢跃组队的比率。总体告捷率：当玩家点击推选模块后，最终与好友组成戎行的比率。不错视作前两者的乘积。

咱们使用DAG模子对模子进行考研，并获取每个玩家的社群标签。除此以外，咱们也对比了DAG跟其他两种算法，包括业务基线Intimacy（基于好友亲密度排序）和首先进的DGC轨范CCGC两种算法的成果。咱们进行了时长为一周的线上A/B实验，并汇总了三种轨范的各项筹商，其中各算法的成果如表1所示：

表1：各社群推选算法线上A/B实验对比（括号内涌现CCGC和DAG算法比拟Intimacy算法的成果相对提高）

不错看出，咱们的轨范比拟基线算法在点击率、组队率、总体告捷率筹商上分别提高了4.9%，4.4%，9.44%。这意味着咱们的算法挖掘出了更挑升旨的社群，并再次考证了同社群内的玩家将有更高的活跃度和搪塞度。

回来

本文将腾讯游戏委果业务场景中的痛点问题样式为K-Free社群检测问题，并想象了深度自得当生成式社群检测算法DAG，基于图神经采集工夫挖掘游戏搪塞采蚁集的用户语义信息和搪塞结构信息，并想象了基于组寥落料理社群附庸和搜索算法对社群数量K和社群附庸任务进行调节学习。此外，本文先容了该算法在搪塞推选类业务中的利用案例和算法对提高用户点击率、组队率等中枢业务筹商的骨子成果，也但愿本文的内容能为大家处治骨子业务问题带来一些匡助。

参考文件

1. Chang Liu, et al. "DAG: Deep Adaptive and Generative K-Free Community Detection on Attributed Graphs." Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024.

2. Zhang, Xingyi, et al. "Constrained social community recommendation." Proceedings of the 29th ACM SIGKDD conference on knowledge discovery and data mining. 2023.