受影响传播控制行走：异构信息网络中社区检测的表示学习方法

《Expert Systems with Applications》：Influence Propagation Controlled Walks: A Representation Learning Approach for Community Detection in Heterogeneous Information Networks

　　维什努·库马尔|P. 拉达·克里希纳

摘要：异构信息网络中的社区检测面临巨大挑战，因为这类网络具有多样的结构与语义特征。现有的社区检测模型往往无法在网络的密集区域和稀疏区域都取得均衡的性能，因为它们对整个网络一视同仁，没有考虑不同节点类型的局部行为及其相互连接关系。在本文中，我们提出了一种新的社区检测模型，通过引入受影响传播控制的元路径引导随机游走（IPCwalks）来高效学习异构信息网络的低维特征表示。首先，我们构建了一个IPCwalks语料库，其中节点从当前节点转移到下一个节点的过程取决于聚类系数和影响传播得分。随后，我们对每条元路径的所有IPCwalks应用跳字模型，以学习每个节点的低维潜在特征。接着，我们利用注意力机制聚合节点特征，并结合聚类系数和影响传播得分的乘积因子。最后，我们对聚合后的特征应用聚类算法来识别社区。实验结果表明，我们的模型显著优于现有的社区检测技术，包括那些基于同质和异质网络表示学习的算法。

引言：近年来，社交网络变得越来越重要，它借助互联网的力量促进了来自不同地理背景的用户之间的联系与互动（Hou, Cen, Dong, Zhang, & Tang, 2023）。现实世界中的社交网络规模庞大且结构复杂，通常被表示为异构信息网络（Zhang, Yin, Zhu, & Zhang, 2020）。在这些网络中，不同类型的用户被表示为节点，而他们之间的各种连接则表现为边。例如学术网络、电子商务平台以及交通网络等。在异构信息网络中，结构上相似的节点在各种语义信息方面可能存在显著差异（Zhang et al., 2020; Carvalho, Pedro, & Batista, 2013）。每种边的类型都承载着特定的语义意义，这使得这些网络能够通过直接的或间接的节点连接传递丰富的结构与语义信息。然而，节点和边的异质性，以及不同的连通性和网络稀疏度，给社区检测、推荐系统、欺诈检测、信息检索以及情感分析带来了巨大挑战（Shi, Li, Zhang, Sun, & Yu, 2017）。

社区检测是社交网络挖掘中的重要任务之一，它能够揭示复杂网络的底层结构，帮助识别网络中具有相似角色或功能的职能模块或节点群（Han, Jin, Xing, Yang, & Xiong, 2023; Sun & Han, 2013）。在大型网络中应用社区检测可涵盖多种实际领域，比如精准营销、推荐系统、理解社会动态以及信息传播（Newman, 2016）。传统的社区检测算法会整体分析整个图结构，因此计算量大且耗时较长（Shaham et al., 2018; Newman, 2016）。各种方法包括基于模块度的算法，如Louvain算法和Girvan-Newman算法，这类算法通过最大化群体内的连接密度来优化模块度以检测社区（Newman, 2016）；谱聚类则利用图拉普拉斯矩阵的特征向量对网络进行划分，从而有效捕捉网络的全局结构（Shaham et al., 2018）。其他技术还包括基于邻居为节点分配标签的标签传播算法、构建社区树的分层聚类算法、利用随机游走来识别社区结构的Infomap算法、根据相似性将节点划分为K组的K均值聚类算法，以及通过团体识别重叠社区的团渗透法（CPM），这些方法也都旨在揭示社区结构（Garza & Schaeffer, 2019; De Meo, Ferrara, Fiumara, & Provetti, 2011a）。但这些方法在处理异构信息网络时存在两个主要问题：其一，它们提取的图结构特征往往不足以捕捉网络固有的异质性；其二，它们假设网络结构均匀，这简化了网络中存在的复杂关系与互动，未能体现不同节点类型之间的复杂性及不同的连通程度。这些难题使得在网络中识别有意义的群体变得十分困难，甚至可能导致社区分类错误。

近期基于神经网络的技术能够将网络嵌入到低维潜在特征空间中，从而有效捕捉异构信息网络中不同节点之间的复杂结构与语义关系（De Meo, Ferrara, Fiumara, & Provetti, 2011b; Traag, Waltman, & van Eck, 2018）。随机游走是深度学习模型中的核心策略，诸如DeepWalk（Perozzi, Al-Rfou, & Skiena, 2014）、Node2Vec（Grover & Leskovec, 2016）、Metapath2Vec（Dong, Chawla, & Swami, 2017）、HIN2Vec（Fu, Lee, & Lei, 2017）、Network Vector（Wu & Lerman, 2017）以及LINE（Ribeiro & Towsley, 2010）等模型，都能通过捕捉结构与语义依赖关系来实现特征表示学习。这些模型将随机游走视为一系列相连的节点，类似自然语言处理中的句子，再借助深度学习技术为社区检测等任务生成有意义的嵌入向量（Xu, 2020; Li, Yu, Qin, Mao, & Jin, 2015）。像M-DHIN这样的可扩展模型则通过基于元图的嵌入来捕捉异构信息网络中的动态变化，仅处理发生变化的节点，从而提升效率（Ribeiro & Towsley, 2010），而包括自编码器和聚类算法在内的图表示学习方法，则可用于分析网络结构随时间的变化趋势（Perozzi et al., 2014）。

不过，使用随机游走学习特征时会面临一些问题，比如样本偏差、对噪声敏感、存在歧义以及节点重复等现象，这些问题都会影响到结构和语义信息的获取（Blondel, Guillaume, Lambiotte, & Lefebvre, 2008; Grover & Leskovec, 2016）。元路径是一种特殊的随机游走类型，它会考虑节点和边的类型信息，从而有效捕捉异构信息网络中直接或间接相连节点之间的复杂关系（Dong et al., 2017; Fu et al., 2017）。这些基于元路径的连接在结构关系方面的含义和强度各不相同（见图1）。在异构信息网络中，对于不同的元路径，两个或多个节点可能属于同一个社区，也可能属于不同的社区。例如在图1中，作者1和作者2的节点被归入社区2，尽管他们之间没有任何直接的连接或合著过任何论文，但由于在同一会议上发表过论文，就可以被归为同一个社区。因此，节点的行为以及它与所在局部区域内其他节点的连接程度，在很大程度上会受到节点间基于元路径的语义关系影响。总体而言，这些方法都体现了低维表示在揭示异构信息网络中社区结构方面的潜力，不过性能会随着网络稀疏度的不同而有所差异（Dong et al., 2017）。

Metapath2vec（Fu et al., 2017）在异构信息网络中运用基于元路径的随机游走，节点的转移由类型映射来引导。这种游走会持续进行，直到达到最大长度或找不到有效的下一个节点类型，从而生成受控的随机游走。但这种方法存在明显局限性：它没有控制节点在转移过程中的重复出现，也没有考虑相邻节点与当前节点之间的连接强度。因此，较长的游走过程会积累噪声和无关信息，妨碍对有价值的语义模式的准确识别。此外，基于元路径引导的随机游走还会遇到复杂且模糊的语义模式，从而导致难以提取连贯的语义信息。更长的路径所带来的更高复杂性，也会降低捕捉网络中有意义关系所需的精确度。其他类似模型如HIN2vec、metapath2vec++和HEBE也试图通过元路径学习节点嵌入，但在整合多条路径以及处理无关连接的噪声方面存在困难。解决这些问题是提升异构信息网络中节点嵌入质量及应用性能的关键。正因如此，Metapath2vec无法有效表示节点，进而对社区检测等任务产生负面影响。

在本文中，我们提出了一种名为IPC-CommDet的高效特征表示学习型社区检测模型，用于处理异构信息网络，该模型能够编码邻域的最大异质性、结构复杂性以及节点间的语义关联度。所提出的模型分为四个阶段。第一阶段，我们设计了一种基于元路径引导、受影响传播控制的随机游走（IPCwalk）的网络探索方法，用于收集随机游走语料库。IPCwalk根据两个因素来控制节点的转移：一是当前节点的聚类系数得分（CCscore），它反映了该节点邻域的结构特征；二是当前节点的影响传播得分（IPscore）。如果IPscore超过用户设定的阈值（在我们的实验中该阈值为0.5），则该节点被视为潜在的影响者。如果潜在影响者数量与游走长度的比值超过停止游走的阈值WSth，游走就会继续，否则就会停止。这两个阈值都属于超参数：IPscore阈值决定了影响者识别的灵敏度，而WSth则控制游走长度。它们的最优值是通过第5.4.3节中的消融实验确定的，我们在该实验中测试了WSth∈{0.4, 0.5, 0.6, 0.7, 0.9}的不同取值，最终发现WSth=0.7时社区检测性能最佳，在DBLP和IMDB数据集上均取得了最好的效果。

第二阶段，跳字模型会从IPCwalk语料库中学习节点的低维表示。接下来，我们会根据每个节点的CCscore和IPscore计算出一个乘积特征，从而为每条元路径生成多个特征。这些乘积特征通过同时捕捉结构连通性和影响动态，丰富了节点的表示形式。乘积特征使得模型能够考虑到节点之间不同的连通程度以及聚类倾向。较高的CCscore表明节点倾向于与相似节点聚集在一起，而较高的IPscore则反映其影响邻近节点的能力。这种双重视角对于准确识别社区结构至关重要，因为它既体现了节点的聚类倾向，也反映了其对邻近节点的影响力。第三阶段，我们利用注意力机制对这些特征进行聚合，该机制能够动态地确定哪些交互是重要的，然后将这些特征与乘积特征拼接在一起。最后，应用聚类算法根据所学到的特征来识别社区。

本研究的主要贡献如下：
•受影响传播控制的元路径引导随机游走（IPCwalks）：我们提出了一种用于异构信息网络探索的新随机游走策略，节点的转移由两个得分共同决定：聚类系数得分反映了节点邻域的结构紧密程度，而影响传播得分则体现了节点在邻域内传播信息的能力。这两个得分共同作用，使得生成的随机游走具有可变长度、语义连贯且能体现结构特征，从而克服了现有基于元路径的方法，如Metapath2vec所存在的噪声和歧义问题。
•丰富的低维节点特征表示：我们开发了一种特征学习框架，该框架将异构的跳字模型应用于IPCwalk语料库，从而获得节点的低维嵌入向量。进一步地，我们通过为每条元路径结合CCscore和IPscore计算出的乘积特征，将这些嵌入向量进一步丰富，从而将结构聚类倾向和影响动态共同编码到一个紧凑的特征向量中。
•基于注意力的多元路径特征聚合：我们引入了一种针对元路径的特定注意力机制，该机制会根据与每条元路径相关的潜在影响者节点的密度来计算注意力分数。这样就能对多条元路径的特征进行语义上有依据的加权组合，既保留了每条元路径独特的语义贡献，又减少了特征聚合过程中的语义干扰。

本文的其余结构如下：第2节将对相关研究进行详细梳理。第3节介绍异构信息网络中用于社区检测的基本组成部分。第4节阐述我们所提出的社区检测模型。第5节展示该模型的实验结果，并将其与两种真实异构信息网络数据集上的网络表示学习模型进行比较。第6节对全文进行总结。

相关研究：本节对为社交网络开发的社区检测模型进行了文献综述，涵盖了传统的图划分方法、网络表示学习以及图神经网络模型。

基本定义：定义1 异构信息网络：Said等人（2018）指出，异构信息网络包含多种类型的节点和边，这些节点和边代表了图形结构中的各类社交关系。异构信息网络可定义为有向图G=(V,E,A,R)，其中存在节点映射函数?(v): V → A和边映射函数ω(e): E → R，A和R分别表示节点类型集合和边类型集合，且满足|A|+|R|>2。在图1中，DBLP引用网络数据集被表示为一个异构信息网络，其中包含四种类型的节点，即作者、论文、术语以及……

提出的社区检测模型（IPC-COMMDET）：所提出的模型包含四个阶段。首先，我们引入元路径引导、受影响传播控制的随机游走（IPCwalks），用来探索异构信息网络并收集相应的随机游走语料库。其次，我们提出了用于为HINs中的每个节点生成低维特征表示的数学公式。第三，我们介绍了所提模型的框架，并通过基于注意力机制的对学习到的特征进行聚合处理。最后，我们应用聚类算法来检测社区结构。实验结果方面，我们在两个真实的异构数据集上进行了实验，即DBLP引文数据集和IMDB电影数据集，以此评估学习到的低维节点特征在社区检测方面的有效性。我们的研究还对比了所提模型与两类不同的基线网络表示模型。第一类包括三种表示学习模型，即DeepWalk、Node2vec和Metapath2vec。此外，我们还研究了GNN模型。结论部分指出，本文提出了一种用于HINs中社区检测的低维特征表示方法。我们设计了一种受影响传播控制的随机游走策略，该策略以元路径为引导，为每个节点收集随机游走序列。通过在IPCwalks过程中结合聚类系数以及基于元路径的节点类型映射概率来进行节点转换，该模型能够有效捕捉CRediT作者贡献度评估中的结构紧密性和语义关系。作者分工：Vishnu Kumar负责概念构建、方法设计、软件开发、验证、形式分析、研究工作、数据整理、初稿撰写及可视化；P. Radha Krishna负责概念构建、方法设计、验证、资源协调、审稿与编辑、项目监督、行政管理工作以及资金筹集。利益冲突声明：作者声明不存在与本论文相关的任何利益冲突。