摘要：在游戏社交网络中，具有相似兴趣的玩家往往会聚集在一起，从而形成一个个群体组织，这些群体组织被称为社群。本文重点研究了游戏中的受约束社群推荐问题，即每个玩家在当前时刻最多只能加入一个社群，并提出了ComRec算法，它在预计算期间，同时捕捉扩展图上的全局和局部信息，从而加速了在实际大规模图上的训练过程，此外，ComRec算法还引入了标签机制来提高算法的表示学习能力。我们在三个腾讯手游数据集上评估ComRec算法的有效性，实验结果表明，ComRec算法在离线实验中优于对比算法，取得了不错的效果。本文介绍的算法已经被国际数据挖掘领域的前沿学术会议KDD 2023录用发表（接收率是22.1%），KDD是每年一度的具有较高影响力的CCF A类顶级会议。
引言
在游戏社交网络中存在大量的社群，这些社群是具有相似兴趣的玩家自发形成的群体组织，这种凝聚特性是游戏社交发展的必然结果，也是游戏内部社交生态繁荣性的一个重要体现。一般说来，社群中的玩家整体上具有更高的活跃度。同时，随着游戏社交网络中社群的蓬勃发展，社群的数目会越来越大，对于玩家而言，如何从如此多的社群中，选择合适的加入社群这也是一件非常困难的事。
[ 图1 游戏中的社群推荐场景 ]
本文重点研究了游戏社交网络中向玩家推荐社群的问题，在传统的社群推荐场景中，一个玩家可以加入多个社群，这意味着社群之间是可以重叠的，而在我们研究的社群推荐场景中，每个玩家每一个时刻最多只能加入一个社群。这种社群数量受约束的特性，严重限制了正训练样本的数量，使得这个问题非常具有挑战性。
为了解决上述问题，我们提出了ComRec算法，ComRec是一个基于GNN的表达力强且有效的受约束社群推荐框架，并且由三个模块组成，第一个模块是标签机制，根据最近的子图表示学习理论可知，使用标准消息传递机制GNN框架无法区分的节点，在引入子图内外节点的概念后，可根据子图内外节点为非同构子图生成不同嵌入，从而使得这些节点变得可以被GNN所区分开来。因此，我们根据节点与社群的关系分配标签，进而增强了节点的隐含层特征在信息传播过程中的表征能力。此外，我们还证明了ComRec与传统的消息传递GNN 相比更具有更好的表示学习能力。
在实际的推荐应用中，推荐结果通常需要每日更新，这对模型的可扩展性和训练效率提出了挑战。为了解决这个问题，我们提出了第二个模块中所展示的全局特征传播策略，全局特征传播策略将特征传播过程与非线性变换分离，数据的特征在列归一化后逐列进行传播。通过这种策略，算法的时间复杂度被显著地降低到亚线性。经过实验验证，ComRec算法可以在仅使用CPU机器的情况下，30秒内在包含超过2000万个节点的图上完成了特征传播过程，并取得了较好的推荐效果，相关的数据见实验结果部分。
需要注意的是，先前很多方法在信息传播过程中，只考虑在每个节点的1-阶邻域节点信息，而忽略了不同节点类型的局部结构。此外，游戏中社群受到玩家加入条件的约束，这使得玩家和社群之间的交互非常稀疏。为了在表示学习过程中体现社群成员影响力的差异性，并充分利用节点的局部结构信息，在第三个模块中，我们提出了局部特征传播机制，通过传播并聚合局部成员的交互信息，从而生成具有更大信息量的社群表征向量。
在实验中，我们将ComRec算法与其他推荐算法，在受约束的社群推荐任务上进行比较，一系列实验结果表明，ComRec算法在四个实验数据集上的效果要优于其他参与对比的算法。本文的贡献可以总结为如下几点：
➢ 我们定义了一个新推荐问题，即受限的社群推荐；
➢ 我们提出了一种表达力强、高效且有效的ComRec算法框架，用于受限社群推荐任务；
➢ 我们在真实的大型图上进行了广泛的离线实验，离线实验结果表明，ComRec算法在相应指标上优势较为明显，在某些指标上，最高具有12.80%和6.61%的提升；
研究现状
基于协同过滤的社群推荐. 基于CF(Collaborative Filtering)的方法是解决社群推荐问题的重要思路，不少学者在这方面做出了很多工作。CCF [2]考虑社群-用户和社群-描述的共现关系，并依据共线关系计算社区、用户和描述之间的联合概率分布。Pairwise PLSI [3]采用pair-wise的学习方法，根据历史记录，最大化两个社群之间用户偏好的差异。Wang等人[4]将隐式的用户-社群评分纳入社群推荐中，由此获得时序用户-社群亲和力值(Affinity)。最近，基于neural CF方法[5]，展示了GNN在推荐系统中的有效性。由于每个社群可以被视为图G中的虚拟用户，因此基于GNN的CF方法也可以用于处理社群推荐问题。大多数基于GNN的CF方法都会假设图中的每个用户至少都会加入一个社群,然而，在实际应用中，这种假设过于理想化。例如，在某款策略手游中，只有约10%的用户加入了游戏内社群，同时，由于玩家加入社群条件的约束，用户与社群之间的交互非常稀疏。
社交推荐. 利用社交关系是提升推荐系统效果的另一种途径，RecSSN [6]通过关系网络获得每个用户的全局信息。近几年来，基于GNN社交推荐方法在社交推荐任务中较为常见，已经成为社交推荐任务中非常重要解决方法。GraphRec [7]从两个不同的角度聚合节点特征来学习用户表示。DiffNet++ [8]在一个统一的框架中提出了社交扩散和兴趣扩散，以从不同的方面聚合嵌入。FeSoG [9]采用伪标签技术来解决隐私保护方面的挑战。然而，这些模型中绝大多数都采用注意机制，现实世界中的图往往拥有上百万甚至更多的节点，过高的复杂度极大地限制了这类模型在真实业务场景中应用范围。
群组推荐. 群组推荐是向一组用户进行推荐，这类问题的关键在于如何推断一组用户的决策。SIGR [13]采用注意机制学习不同群组中用户的社交影响力。GroupIM [12]通过最大化群组表示和成员表示之间的互信息来聚合用户偏好。如果我们将群组视为图中的虚拟用户，那么群组推荐也可以被视为社群推荐的反向问题。然而，由于用户和群组之间的交互非常稀疏，很多群组推荐方法需要额外的侧面信息，如：用户-物品交互信息等，来提高群组中用户偏好的估计精度。因此，如何将群组推荐方法推广到社群推荐问题而不需要侧面信息仍然是一个开放的问题。
背景知识与问题定义
设与
分别为玩家与社群的集合，其中：
为玩家的数目，
为社群的数目。设
为玩家-社群的交互图，如果
则表明玩家加入了社群
，假设玩家之间的社交关系已提前获知，并且用
代表玩家-玩家之间的好友关系图。将
与
进行合并融合，从而形成一个新的扩展图
，图中节点的特征矩阵为
，其中
为社群节点的特征矩阵，
为玩家节点的特征矩阵，
为按列方向拼接的函数。在游戏内，社群推荐任务即是给当前未加入社群的玩家推荐合适的社群，让尽可能多的玩家加入到社群中。除此之外，我们还进一步给出了受限社群推荐问题的定义(如定义1所示)，即玩家在某一时刻，最多只能加入一个社群，这种受约束的推荐场景在游戏内非常常见，很多游戏的战队推荐场景都要符合这个约束条件。
定义1.(受约束社群推荐) 设为一个无向图，
和
分别为图
与
中节点的特征矩阵。此外，每个玩家最多只能加入一个社群。受约束社群推荐任务的目标是在上述约束条件下，为尚未加入社群的玩家推荐合适的社群。
需要注意的是，在社群检测这类的图挖掘任务中，其目标是在复杂网络中发现节点类簇，这些类簇内部的节点之间具有稠密的连接，不同类簇之间的连接尽可能稀疏。在社群检测中，社群是未知的，需要用社群发现算法找出未知的社群结构。然而，在社群推荐中，社群是显式已知的，并由游戏中的玩家所创建。例如，在某策略手游中，玩家可以创建俱乐部，其他人可以加入现有的俱乐部，在给玩家推荐俱乐部之前，我们已经知道了游戏中有哪些社群。在本文中，我们使用社群节点来表示现有的社群，并使用社群来表示由社群节点及其成员生成的子图。
ComRec算法结构
在受约束的社群推荐任务中，每个用户同时只能加入一个社群。这个问题主要有两个方面挑战。首先，在大多数推荐场景中，用户和物品或社群之间有丰富的交互。然而，在游戏社群推荐中，由于游戏规则的约束，每个玩家每天最多只有一个正样本。此外，大多数玩家可能尚未加入任何社群，导致正训练数据极度稀疏。其次，在游戏内，没有额外的item信息。因此，为玩家推荐可加入的社群属于冷启动问题，这使得它变得非常具有挑战性。为了应对上述问题，我们提出了ComRec算法框架。
4.1 模型的基本框架
图2展示了本文所提出的ComRec算法框架，ComRec算法包含三个模块：标签机制、全局特征传播与局部特征传播。
[ 图2 ComRec算法的基本框架示意图 ]
第一个模块是扩展图G上的标签机制，该扩展图由玩家-玩家社交网络和玩家-社群二分图
生成。由于用户受邻近用户节点和社区节点的影响，将社交网络与玩家-社群二分图相结合为表示学习过程提供了从两个不同角度学习节点表示的机会。此外，每个社群可以被视为扩展图中的子图。由于区分不同的子图对于生表示学习过程很重要，我们采用了标签策略来增强ComRec算法的表示学习能力。
第二个模块是全局特征传播，它将特征传播与复杂的参数训练过程分离开来。传统的社交推荐方法一般会同时使用图与
的嵌入来训练网络，然后将两个的嵌入连接在一起以获得最终预测，而ComRec算法直接在扩展图上传播信息，保留了用于生成社群节点嵌入的玩家-玩家交互信息。为了加速在数千万用户的大规模图上的训练过程，我们设计了一个高效的全局特征传播算法，这个过程只有亚线性时间复杂度。
第三个模块是局部特征传播。在传统的推荐方法中，节点特征大多在每个节点的邻域节点内传播，而没有区分不同的结构或节点类型。此外，在游戏社群推荐场景中，训练数据非常稀疏，因此采用子图上的局部特征进行传播可以进一步捕获每个社群的结构，从而生成具有更多信息的表示向量。
4.2 标签机制
图神经网络(Graph Neural Networks, GNNs)已在许多任务上取得了不错的效果，当前大多数GNNs算法都属于基于消息传递机制的GNNs网络(Message-Passing Graph Neural Network, MPGNN)，基于消息传递机制的GNNs网络聚合邻域节点的信息来更新当前节点的表示。对于MPGNN第k层而言，节点v在该层的表示为如下式所示：
其中：N (𝑣)为节点v在图G中的邻域节点。
正如文献[1]所讨论的那样，区分子图内外的节点使得GNN能够生成非同构子图的不同嵌入。给定一个节点𝑥和一个社群𝑐，标签机制会为节点分配一个标签向量来指示所属信息,节点𝑥的标签定义如下：
节点𝑥可以是用户节点或社群节点。通过向MPGNN引入额外的标签，它增强了图G中节点嵌入向量的表征能力。以下定理表明，标签机制可以提高MPGNN的表示学习能力。
定理1. 标签机制可以增强MPGNN的表示学习能力.
证明：首先，我们证明如果一个标准MPGNN可以区分两个不同的子图，则采用带有标签机制的框架也可以为它们生成不同的嵌入向量。
对于带有标签机制的消息传递框架，第k-1层节点𝑢的表示向量为：
很容易验证，总是存在一个映射𝜙，使得：
因此，给定一个标准的MPGNN框架M，总是存在一个带有标签机制的消息传递框架，可以产生与M相同的嵌入。如果M可以区分两个非同构子图，则带有标签机制的消息传递框架也可以为这两个子图生成不同的嵌入。
以上的证明过程表明，引入标签机制的MPGNN的表示学习能力不低于标准的MPGNN表示学习能力。
其次，我们需要证明存在一对非同构图，MPGNN无法区分，而带有标签机制的消息传递框架可以。考虑图3中的两个非同构图G1和G2，其中𝑐1和𝑐2表示社群节点。带有蓝色的节点和它们之间的边构成的子图表示社群。如果没有额外的特征信息，对于标准的MPGNN而言，由于节点𝑢和节点𝑣邻域生成的计算子树是同构的，引入节点𝑢和节点𝑣的表征向量也是相同的，如图3(b)所示。
[ 图3 G1与G2分别为社群c1与c2(蓝色标记的节点)生成的子图，图3(b)表示标准MPGNN无法区分节点u与节点v的计算子树，在采用标签机制后，节点u与节点v的计算子树可以被区分 ]
如果我们仅使用MPGNN来聚合信息，则节点u与节点v无法被区分。然而，如果把额外的标签信息纳入消息传递框架中，它可以区分𝑢和𝑣的计算子树，因为𝑢有三个社群内的邻居节点，而𝑣有三个社群外的邻居节点。
尽管标签机制可以提高MPGNN的表达能力，但它会产生额外的时间开销。如果我们利用批量训练策略，即将标签联合到一批节点中，然后在边之间传播信息，则标签可能在不同批次中变得不一致。为了解决这个问题，我们只为每个节点保留一个一维标签。如果一个节点属于一个社群，则标签值记为1，否则，标签值记为0。值得注意的是，即使只保留一个标签，上述定理仍然成立，即松弛后的标签机制仍然可以提高MPGNN的表征能力。
4.3 全局传播
根据社交网络理论可知[14]，用户的偏好很可能受到1阶邻域节点的影响。全局特征传播模块将来自扩展图G和图的社交信息和多条信息融合到到每个节点的表征向量中。由于标准GNN在大规模图上的计算成本很高，文献[4]建议将非线性变换与特征传播分离，LightGCN[15]的经验证明，在推荐系统中，非线性变换并不是必须的，非线性变换会增加算法复杂性，甚至会降低推荐模型的有效性。因此，我们采用LightGNN的基本框架，在预计算过程中解耦特征传播过程。
文献[10]提出了特征传播的近似算法，然而，PPRGo[10]仍需要线性运行开销进行特征传播，这对于大规模图来说复杂度仍然过高。AGP[11]假设给定的特征向量𝒙是𝐿1归一化的，即，其中每个维度对应于图中节点的特征值，其运行成本可以降低
，这与图的大小无关。然而，在许多情况下，这种有限的传播是不够的。为了解决这个问题，我们将列方向特征传播与𝐿2归一化相结合，其运行时间为
，在效率和有效性之间到达了平衡。
算法1展示了全局特征传播算法的伪代码。给定一个特征列，输出表示向量
中的特征信息通过𝛼-随机游走传播到邻域节点。在传播过程中，当前的特征信息以𝛼概率停留在当前节点上，或者以(1-𝛼)的概率随机传播到其邻居节点上。此外，向量
表示当前在每个节点传播但尚未存储的特征信息部分。因此，如果
的每一个元素值都是零，则终止特征传播过程并返回特征传播结果。
在算法1中，的初始值都是零（第1行），表示每个节点的特征信息尚未存储。我们在传播过程开始之前，先对特征矩阵进行归一化。然后，特征沿每个维度分别传播（第2行）。对于特征矩阵的第𝑘列，如果特征矩阵的元素
大于
（第3行），则节点𝑢会以𝛼概率将其特征传播到邻居邻域节点上（第4-7行），其中𝜖是给定的阈值，
是节点𝑢的出度。以下定理表明，使用全局传播算法可以在亚线性时间内生成表征矩阵𝑯，证明过程可见论文原文。
定理2. 如果原始特征矩阵𝑿中的每列都进行了𝐿2归一化，则使用算法1生成的表示矩阵𝑯的时间复杂度为.
4.4 局部特征传播
与用户-物品推荐任务不同，社群节点及其成员构成显式子图，并包含了额外的局部结构信息。此外，由于用户的约束，训练中正样本数据非常稀疏。为了生成更具信息量的社群表征，我们提出了局部特征传播模块，来获得同一社群内玩家的偏好。ComRec的局部特征传播包括两个步骤：局部更新和子图传播。
局部更新. Pooling函数在很多图任务中非常常见，如图分类任务。通过pooling函数，可以由节点的表征向量来生成图的表征向量，其过程可以表示为下式所示：
其中，pooling函数可以设置为𝑚𝑖𝑛、𝑚𝑎𝑥或者 𝑎𝑣𝑒𝑟𝑎𝑔𝑒 等。在ComRec算法中，我们扩展了上述方法来生成社群的表征向量，对于一个社群节点c而言，其表征向量可采用下式计算：
其中：为玩家u在社群c中偏好的权值，该权值可以通过注意力机制或用户设置的超参数获得，在实验中，我们发现采用均匀权值的特征聚合方法已经可以获得较好的推荐效果了，因此，
设为1，
可以避免权值更新产生的开销。通过局部更新，社群节点的表征向量包含了成员的偏好信息，这也可以被视为该社群偏好的总结。
子图更新. 局部更新过程旨在将成员偏好纳入社群表示中，但它并不包含社群成员之间的关联信息。由于社群和社群成员所组成的显式子图提供了额外的局部结构信息，为了充分利用这些信息，我们在子图中传播节点的表征向量，从而可以平滑每个社区内的节点表示。在局部传播期间，对于节点的第𝑘层表征向量可以定义为：
其中：为由社群c生成的子图中的节点i的1阶邻域节点集合。在子图传播过程中，算法没有考虑节点的自循环，这是因为在全局特征传播过程已经使用了𝛼-随机游走，节点i的信息会以概率传播给自己，这相当于已经考虑了节点的自循环。
4.5 训练与预测
在经过两个传播过程之后，我们采用一个MLP(Multi-Layer Perceptron)来输出每一个节点最终的表征向量，𝒁 = MLP(𝑯)，并采用玩家与社群表征向量之间的内积作为预测得分：
对于每一个玩家而言，采用上式所获得的top-k个社群作为最终的推荐结果。
损失函数. 在ComRec算法中，MLP的权值是唯一需要训练的参数。因此，ComRec算法支持高效的mini-batch训练方式，并且在大规模图任务上具有较好的可扩展性。在损失函数中，ComRec算法采用BPR loss(Bayesian Personalized Ranking loss)来最大化正样本对与负样本对之间的差异，其损失函数可表达为如下式所示：
其中：c为玩家u的正样本，为玩家u的负样本，𝑾为需要训练的参数。
训练样本. 正样本是曝光日志中玩家成功加入社群的样本对，对于负样本，如果直接为每个玩家随机采样一些社群，这些社群很可能与玩家之间并没有太大的相关性。因此，ComRec算法采用了硬负采样策略，为每个玩家选取相关性大的负样本。对于每个玩家𝑢而言，我们计算图G的PPR值，并选择玩家𝑢 top-5个PPR分数最高的社群作为硬负样本。
候选集(召回集)的选择. 由于每个玩家在每个时刻最多只能加入一个社群，因此，对于玩家u而言，很多社群与玩家u并不相关，如果选择这部分不相关的社群作为候选集，这些候选集很可能对推荐任务而言是无效的。为了使预测更加合理，我们根据游戏日志和玩家好友关系链为每个玩家𝑢选择一个候选集，候选集包含与该玩家对局过的玩家所加入的社群以及玩家𝑢好友所加入的社群。在获得社群候选集后，我们使用向量内积的方法(公式1所示)向每个玩家推荐社群。
实验结果
5.1 离线实验结果
为了验证算法的有效性，我们将ComRec算法运行在四个数据集上，这四个数据集来自于三款策略手游分别记为X,Y,Z，其中，将X数据集依据游戏区服ID的不同进一步划分为X-1与X-2两个数据集，最终的离线实验结果如下表1-表4所示。
表1 算法在X-1数据集上的实验结果
表2 算法在X-2数据集上的实验结果
表3 算法在Y数据集上的实验结果
表4 算法在Z数据集上的实验结果
由表1-4的实验结果可知，ComRec算法在四个数据集的Hit@5和NDGC@5指标都取得了最好的结果，上述实验结果证明了ComRec算法的有效性。除此之外，ComRec算法的时间开销也很有竞争力，在X-1和X-2两个数据集上，时间开销仅次于MLP，在Y与Z两个数据集上，也要优于DistNE、GraphRec、AutoIntCL、AttentionNet等算法。
研究团队和论文
Constrained Social Community Recommendation
https://edwlin.github.io/pubs/kdd2023-community.pdf
Xingyi Zhang, Shuliang Xu, Wenqing Lin, Sibo Wang.
Proceedings of ACM SIGKDD Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 5586-5596, 2023.
研发团队：
腾讯游戏社交算法组
https://socialalgo.github.io/
香港中文大学
参考文献：
[1]. Emily Alsentzer, Samuel Finlayson, Michelle Li, and Marinka Zitnik. 2020. Subgraph neural networks. In NeurIPS. 8017–8029.
[2]. Wen-Yen Chen, Dong Zhang, and Edward Y. Chang. 2008. Combinational Col- laborative Filtering for Personalized Community Recommendation. In SIGKDD. 115–123.
[3]. Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology (2001), 415–444.
[4]. Jiliang Tang, Xia Hu, and Huan Liu. 2013. Social recommendation: a review. SNAM 3, 4 (2013), 1113–1133.
[5]. Vishvas Vasuki, Nagarajan Natarajan, Zhengdong Lu, and Inderjit S. Dhillon. 2010. Affiliation Recommendation Using Auxiliary Networks. In RecSys. 103–110.
[6]. Jiliang Tang, Charu Aggarwal, and Huan Liu. 2016. Recommendations in signed social networks. In WWW. 31–40.
[7]. Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin.2019. Graph neural networks for social recommendation. In WWW. 417–426. 2020.
[8]. Le Wu, Junwei Li, Peijie Sun, Richang Hong, Yong Ge, and Meng Wang. 2020. Diffnet++: A neural influence and interest diffusion network for social recommendation. TKDE (2020).
[9]. Zhiwei Liu, Liangwei Yang, Ziwei Fan, Hao Peng, and Philip S Yu. 2022. Federated social recommendation with graph neural network. TIST 13, 4 (2022), 1–24.
[10]. Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. 2020. Scaling Graph Neural Networks with Approximate PageRank. In SIGKDD. 2464– 2473.
[11]. Hanzhi Wang, Mingguo He, Zhewei Wei, Sibo Wang, Ye Yuan, Xiaoyong Du, and Ji-Rong Wen. 2021. Approximate graph propagation. In SIGKDD. 1686–1696.
[12]. Hongzhi Yin, Qinyong Wang, Kai Zheng, Zhixu Li, Jiali Yang, and Xiaofang Zhou. 2019. Social influence-based group representation learning for group recommendation. In ICDE. 566–577.
[13]. Aravind Sankar, Yanhong Wu, Yuhang Wu, Wei Zhang, Hao Yang, and Hari Sundaram. 2020. Groupim: A mutual information maximization framework for neural group recommendation. In SIGIR. 1279–1288.
[14]. Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a feather: Homophily in social networks. Annual review of sociology (2001), 415–444.
[15]. Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, YongDong Zhang, and Meng Wang. 2020. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In SIGIR. 639–648.
