摘要
为解决异质信息网络中现有社区搜索方法存在的局限性，本文提出了一种融合多种语义关系的异质信息网络社区搜索方法，采用高效的“离线学习-在线搜索”策略，其核心在于：利用语义注意力机制自适应学习不同元路径对目标社区凝聚性的权重贡献，精准量化语义差异；再结合网络结构与节点属性特征度量节点相关性，定位社区成员。离线阶段预训练节点-社区关联模型，生成节点归属各类社区的概率分布向量；在线阶段基于预计算结果快速响应社区搜索。此策略既可保持学习模型的灵活性，有效捕捉异质网络语义与属性，又将主要计算负担置于离线阶段，显著提升查询效率，尤其适用于高频场景。在多个真实数据集上的验证实验表明，本方法在社区有效性（语义相关性、结构凝聚性、属性一致性）和查询效率上均显著优于现有主流方法。
Abstract
To address key limitations in existing community search methods for heterogeneous information networks (HINs) , this paper proposes a community search method for HINs that integrates multiple semantic relationships, employing an efficient “offline learning, online search” strategy. Its core lies in: adaptively learning the weight contributions of different meta-paths to the target community cohesiveness using a semantic attention mechanism to precisely quantify semantic differences; and subsequently measuring node relevance by combining network structure and node attribute features to locate community members. In the offline phase, a node-community association model is pre-trained to generate probability distribution vectors indicating node affiliation across various communities. In the online phase, community search is rapidly responded to based on precomputed results. This strategy maintains the flexibility of the learning model to effectively capture heterogeneous network semantics and attributes, while shifting the main computational burden to the offline phase, significantly improving query efficiency, making it particularly suitable for high-query-frequency scenarios. Experiments on multiple real-world HIN datasets demonstrate that our method significantly outperforms existing mainstream methods in both community effectiveness (semantic relevance, structural cohesiveness, attribute consistency) and query efficiency.
真实世界的关系可以抽象为各种信息网络，如书目网络、社交网络、蛋白质网络等。社区搜索（community search，CS）[1]是从网络中找到包含查询节点的凝聚子图。由于其高度个性化和广泛的应用价值（例如事件组织、传染病监控、产品推广、舆情调控等），使其成为网络分析任务中的一个重要研究方向。
异质信息网络（heterogeneous information network，HIN）[2-3]是一种包含多种类型对象和连接关系的网络，其中不同类型的对象和连接关系从不同的维度刻画了网络的语义，可以更加完整自然地对现实世界的网络数据进行建模。因此，基于HIN的CS能够搜索到类型更为丰富的社区[4-5]，如（k，）-core[6]，（k，）-truss[7]，Butterfly-core[8]，Significance-（α，β）-community[9]。这些社区语义丰富，易于解释。然而，HIN中丰富的语义信息及节点和连边的多样性也给CS带来了挑战。首先，不同类型对象之间的连接存在不同的语义，可能具有不同的形成机制，同时也会相互关联和相互影响，导致各自在CS中的作用也不同。因此，区分不同的语义关系，即区分各种对象和连接及其在CS中的作用是必要的。其次，不同类型的对象可以通过不同类型的关系连接在一起，同种类型的对象也可以通过不同的方式组织在一起，因此，在异质信息网络中CS的搜索空间更大，计算更复杂，如何设计高效的搜索算法以满足实时、可扩展的要求也是CS的一个关键问题。
现有的CS方法可以分为基于规则的方法和基于学习的方法。基于规则的方法可以在给定的预定义结构约束（如（k，）-core[6]、kК-core[10]等）上发现满足特定条件的社区，这种方法找到的社区结构凝聚性较高，但是参数k的指定较为困难，较高的k可能找不到期望的社区，而较低的k可能导致返回的社区规模较大，使得社区查找不够灵活；基于学习的方法是通过模型训练来定位社区，可灵活地捕获到社区的结构和属性相似性（如ICS-GNN[11]等），但是，针对每个查询都需要重新训练模型会影响搜索的效率，且由于放宽了社区的结构限制（仅需要保持社区连通），导致结果社区的凝聚性较低。另外，大部分基于学习的方法都是面向节点和边类型单一的同质网络设计的，难以应用于包含丰富语义的HIN中查询社区。
鉴于使用规则和学习模型的CS方法存在的问题及不同语义关系对目标社区重要性捕捉的必要性，本研究提出了异质信息网络中融合多种语义关系的社区搜索方法（heterogeneous network community search with multiple semantic relationships，HCSMS）及采用离线学习和在线搜索的高效搜索策略。HCSMS是一种基于图神经网络（graph neural network，GNN）的CS方法，通过多条元路径来捕获多种语义关系，其中，不同语义关系对目标社区的重要性通过语义注意力模型[12]在不断的训练和迭代中得到学习，并在结合网络结构特征和节点属性特征的基础上，指导节点与查询节点相关性的衡量，以产生节点位于不同类别社区的概率。本研究将目标类型节点与查询节点属于同一类别社区的概率定义为节点评分，并通过一种贪心策略来寻找一定规模（社区内的节点数目）内具有最大评分总和的稠密连通子图作为目标社区，社区的评分总和最大，意味着社区成员与查询节点最相关。为了加强目标社区的结构凝聚性，本文进一步引入k-core模型来提高社区的凝聚性。
由于模型学习到目标类型节点属于不同类别社区的概率与查询节点无关，因此，离线学习策略可以预先学习到目标类型节点属于不同类别社区的概率。在线搜索阶段输入查询节点，并根据查询节点的类别从离线阶段训练好的模型上获得节点评分，然后综合结构凝聚性和社区大小约束定位社区。由于不需要针对每个查询节点重新训练模型来获得节点评分，因此社区搜索速度得到提升，且查询频率越高，查询效率提升越明显。另外，对于评分相差较大的两个相邻节点，他们属于相同社区的可能性相较于评分相近的节点会更小。基于这个观察，本文提出一种网络优化策略，将概率相差较大节点间的连边删除，从而减少在线搜索时遍历的时间，进一步提高社区定位的效率。
1 研究概况
当前社区搜索研究主要可分为基于规则和基于学习两类方法。
基于规则的社区搜索依赖预定义规则定位社区。这类方法通常使用预定义规则来查找社区，如（k，）-core[6]求指定元路径下社区内节点度大于k；（k，）-truss[7]规定社区中每条边至少存在于k-2个三角形中的最大子图[13]； kК-core[10]在（k，）-core基础上结合节点属性关键字，增强属性相似性捕获；Butterfly-Core [8]以两个查询节点为中心，基于k-core[14]搜索构建蝴蝶状密集社区；Significance-（α，β）-community[9] 基于二部图，通过节点参与度与边权重变化挖掘社区；基于主题的交互图和（k，l，η）-有影响力社区[15]，则致力于解决主题感知下的社区搜索问题。
基于学习的社区搜索通过模型训练度量节点相关性，突破规则限制。早期方法多基于随机游走，如Guo等[16]引入了社区的结构规则，提出属性核等方法；Zhao等[17]采用不立即回访模型实现社区向量检索；Liu等[18]以亲密度和孤立度综合评估节点关系。基于图神经网络的研究，如Gao和Chen等[11，19]提出的ICS-GNN，将CS转化为二分类问题，通过候选子图训练提升效率。Jiang等[20]提出的QD-GNN，支持属性查询，优化检索条件。但上述方法多针对同质网络，难以适配异质信息网络（HIN）。近年面向HIN的研究中，ICSMIM[21]通过挖掘互信息最大节点集构建社区；VMCS-DGNN[22]在指定元路径训练模型，并利用0/1背包问题平衡结构与属性指标；SNCS[23]融合拓扑和潜在特征，实现语义约束下的社区搜索，CS-DAHIN[24]研究动态异质网络的社区搜索。
本文所提HCSMS方法是一种基于学习的社区搜索方法，与现有研究的区别在于，HCSMS以进一步捕获HIN中不同语义关系对目标社区的影响来发现社区，且HCSMS使用的查询框架可以不需要针对每轮查询重新训练模型，提高了搜索的效率。
2 基本概念及问题描述
2.1 基本概念
定义1 异质信息网络（HIN）[2]。HIN定义为一个具有对象类型的映射函数φ∶V→T（节点→节点类型）和关系映射函数φ∶E→R（边→边类型）的图G=（V，E），节点和边均属于特定类型，如图1（a）所示。
图1语义关系分析示意图
Fig.1Semantic relationship analysis diagram
定义2 网络模式[6]。是定义在节点类型集合T和边类型集合R上的一个有向图SG=（T，R），其是HIN的元描述，引导网络语义的探究，如图1（b）所示。网络中的节点是网络模式的实例化，例如，a1是作者类型A的一个实例。
定义3 元路径[2]。在网络模式中由边序列连接的节点类型序列，可表示为特定形式，其长度有相应定义，元路径能够描述节点间的语义关系，如APA描述论文合作关系，图1（a）中，a1p1a3为元路径APA的一个实例。
定义4 -邻居。通过元路径与节点i连接的所有节点集合={v1，v2，···}。其中，i的-邻居包含节点本身。
定义5 -连通图。HIN通过元路径诱导的一个同质图，该图中任意一个节点i的所有直接邻居均为i的-邻居。如图1（d）描述的是图1（a）中HIN的（1）-连通图，图1（e）描述的是图1（a）中HIN的（1，2，3，4）-连通图。
2.2 问题描述
语义关系捕获不充分。部分方法仅依赖单条元路径刻画单一语义关系，难以全面捕捉网络复杂性；其他一些方法虽引入多条元路径描述多元语义，但未对其重要性进行差异化考量，导致社区质量受限。图1（a）是一个包含作者学术和体育关系的HIN，同个查询a3基于不同元路径的处理方式将找到不同的社区，即图1（d）、（e）、（f）和（g）。其中，图1（d）仅基于单一语义导致社区较为稀疏，图1（e）未差异化考量元路径导致社区联系不够紧密，图1（f）和图1（g）对不同的元路径进行区分融合而找到了不同的社区（学术相关和运动相关），易于解释且更符合实际情况。因此，如何量化不同语义关系的重要性并实现有效融合以提升社区搜索效果，仍是亟待探索的关键问题。
语义关系学习成本。现实世界中的HIN节点和边类型繁杂，需要大量的元路径描述，人为地指定元路径关系来查找社区成本极高。因此，如何从多元语义关系中自动学习并识别对目标社区最为关键的语义关系，成为HIN社区搜索领域亟待突破的核心问题。
搜索效率待提高。基于学习模型的ICS-GNN，虽通过构建候选子图查询在一定程度上提升了效率，但每次查询均需建立候选子图训练模型，训练耗时久，在查询频率较高时，难以满足及时搜索的需求。
2.3 问题定义
给定一个HIN G=（V，E），一个查询节点q，社区规模s，G中的元路径集合为M={1，···，m}。本文的目标是为q找到一个社区C=（Vc，Ec），q∈Vc，对于任意一个节点v∈Vc，有φ（v）=φ（q），且Vc中的节点之间要具有属性相似性。Ec中的边是紧密的保证社区内聚结构，Ec至少包含两种以上元路径连通图关系，且包含的这些元路径连通图关系具有相关性，保证社区是语义相关的。
3 社区搜索框架设计
为了找到属性相似、结构内聚和语义相关的社区，本文设计了社区搜索方法HCSMS，其框架包含离线学习和在线搜索两个阶段，如图2所示。离线学习针对多种语义信息融合网络中的结构及节点属性，以计算各个节点属于不同类别社区的概率；在线查询时，输入查询节点并依据其标签类别，匹配离线阶段预计算的节点-社区归属概率（即节点评分），实现社区精准定位。节点评分反映了节点与查询节点的相关性，节点评分高，意味着节点与查询节点相关性高。
图2中输入的HIN包含4种节点类型（4种形状）及6种连边类型，形状相同但颜色不同的节点表示其属于相同的节点类型，但标签类别不同，如节点a和b均为作者，但作者a的标签可能是人工智能，作者b的标签可能是数据库。节点的属性描述了节点的特征，每种类型节点的属性用属性特征矩阵H描述。
图2HCSMS框架
Fig.2Framework of HCSMS
3.1 离线学习
离线学习阶段包含节点评分计算和网络优化两个模块。
3.1.1 节点评分计算
在图2中，圆形节点a和b的标签属于两种类别（两种颜色），需要分别训练两个GNN模型。两个GNN模型分别以节点a和节点b的标签为正例进行训练，训练结束后获得所有圆形节点属于两种社区类别的概率（评分）。
算法1概述了离线阶段的核心流程：基于节点标签类别训练GNN模型，计算节点对不同社区类别的归属评分。第1行的循环根据每种标签类别训练一个GNN模型，第2行初始化节点评分向量δi为一个一维零向量，第3行循环使GNN模型收敛，第4行中的v.lable表示节点v的标签，若v.lable属于类别，则由行5选择以v的类型为起始节点的元路径集合，第5行中的x.head表示元路径x的起始节点，第6行基于元路径x以及节点级注意力机制计算节点v的节点级嵌入，聚合公式见式（1）。
(1)
式中：σ（·）为非线性激活函数，为节点v在元路径x下的元路径邻居集合，hv为节点v的属性特征矩阵，为在元路径下节点v对节点u的注意力系数，为在元路径x下的注意力向量。
第7行使用语义级注意力聚合来自不同元路径的得到节点v的最终嵌入zv，计算公式如下：
(2)
式中：tanh（·）为激活函数，V为顶点集合，qT为语义注意力向量，m表示元路径数量，W为权重矩阵可学习参数，b为偏置项，为元路径x的注意力系数，用于衡量x的重要性。
第8行将zv通过多层感知机（MLP）计算节点v的评分δi[v]。最后，计算完所有标签类别下的所有节点的评分，获得δ={δ1，δ2，···，δn}，完成算法。
模型训练的损失计算如等式为
(3)
式中：δi[v]表示节点v属于第i类标签社区的预测概率，yv表示节点v属于第i类标签社区的真实概率，若v.lable=，则yv=1，否则yv=0。
通过对核心步骤的分析，算法的时间复杂度可以表示为O（nL·nγ·nM·n·d），由于标签数量nL，元路径数nM，嵌入维度d均为常数级，因此，时间复杂度可简化为O（n·nγ），其中，nγ为最大迭代次数，n为节点数。空间复杂度主要由节点特征和嵌入维度决定，且语义级融合与元路径数量有关，因此算法1的空间复杂度可以表示为O（nM·n·（D+d）），由于节点特征维度D要远大于嵌入维度d以及元路径数量nM，因此可以简化为O（n·D）。
3.1.2 网络优化
评分相差较大的两个邻居节点属于相同社区的可能性比评分相近的邻居节点小。基于这个观察，本文提出一种网络优化策略，将网络中评分相差较大的节点间的连边删除，从而减少在线搜索时节点遍历的时间，进而提高社区定位的效率。
图3（a）是圆形类型节点与其元路径邻居的连接关系图，圆形节点内的数值是算法1计算的节点属于蓝色标签类别的评分，连边上的数值表示边的两个端点的评分差的绝对值，设置评分差阈值θ=3，则图3（a）中有4条边被删除，优化后的网络如图3（b）所示。以定位社区C3为例，不经过网络优化前，需要遍历23次，优化后，只需要遍历14次，有效提高了社区定位的效率。
网络优化过程如算法2所示，其中第1行循环表明每种标签类别的网络都要优化，第2行初始化优化图的节点集和边集，其中表示u在所有元路径下元路径邻居的集合，第3行和第4行遍历优化图节点集中的所有节点及其邻居，第5行删除评分差小于阈值θ的边。该算法的时间和空间复杂度主要取决于节点的数量n，其时间复杂度可以表示为O（n2），空间复杂度为O（n）。
图3网络优化
Fig.3Network optimization
3.2 在线搜索
在线搜索输入查询节点，根据查询节点的标签类别匹配离线阶段学习好的与查询节点属于同类别社区的概率，然后定位目标社区。目标社区定义为具有最大综合评分的稠密连通子图。
定义6 最大评分和社区。给定一个HIN G=（V，E），查询节点q，社区规模s以及节点评分δ，最大评分和社区是G中满足如下条件的一个连通子图C=（Vc，Ec，δc）：
（1）查询节点q∈Vc，且Vc中的任意节点的类型与q的类型相同，即φ（vi）=φ（vq）；
（2）|Vc|≤ε，且C保持连通；
（3）C中节点评分总和是最大的。
条件（1）要求查询节点包含在目标社区中，社区中的节点类型与查询节点保持一致；条件（2）对社区的规模进行了限制，且社区必须是连通的。条件（3）要求社区内节点评分总和最大，即保证社区内所有节点的标签类别与查询节点的标签类别是最相关的，意味着属性相似性最高。
为了搜索最大评分和社区，提出了BFS-Max算法。BFS-Max的主要思想是从当前社区出发，每次仅遍历当前社区内节点的所有邻居，将社区外评分最大的邻居节点加入社区。当前社区初始化为查询节点。图2中在线搜索对BFS-Max算法实现过程进行了演示，第1轮迭代后，社区更新为C1，然后遍历C1的所有邻居，搜索评分最大的节点加入社区，第2轮迭代后，社区更新为C2。重复这个过程，直至社区规模满足要求。
算法3的伪代码描述了BFS-Max的实现过程。第1行根据查询节点q的标签的类别选择优化图，第2行初始化目标社区中的节点和边，第3行循环找到满足社区规模的社区，第4行选择当前社区内所有节点的所有不在社区内的具有最大评分的元路径邻居，第5行将选择的邻居及相应的边加入社区，完成搜索。
该算法的时间复杂度可以表示为O（nL·s·n′·e），其中标签数量nL和社区规模为常数级s，图优化后节点数量n′远大于节点的边数e，因此，可以简化为O（n′）；空间复杂度表示为O（s+n′+e），同理可简化为O（n′）。
由于一定规模内具有最大评分和的连通子图的结构凝聚性可能不高，因此本文提出BFS-Max的增强算法BM-adv，在挖掘到最大概率和的连通子图后，进一步通过k-core模型来挖掘凝聚性强的社区。如图2在线搜索中，展示了s=4，k=2找到的最大评分和社区以及最大评分和k-core社区。BM-adv的伪代码如算法4所示。
第1行通过BFS-Max找到社区，第2行的循环确保社区内所有节点的度大于k，第3，4行搜索不满足k-core，第5，6行删除不满足k-core的节点及在社区内的连边。
该算法的时间和空间复杂度取决于优化后的图的节点数量n′，其复杂性与算法3类似，因此，其时间和空间复杂度均为O（n′）。
4 实验及分析
本文在3个异质信息网络上进行了大量实验，以进行如下验证。
W1：区分不同语义关系的重要性是否能够找到更高质量的社区。
W2：使用GNN模型学习网络结构、节点属性以及语义信息对节点相关性进行综合衡量，验证是否能够提高社区的质量。
W3：离线学习和在线查询的框架以及网络优化策略是否能够提高社区搜索的效率。
4.1 实验设置
4.1.1 数据集
本文使用3个HIN数据集进行实验，数据集的相关信息如表1所示。
表1数据集相关信息
Tab.1Dataset related information
ACM数据集[12]的论文、作者、主题3种类型节点来自数据库、无线通信和数据挖掘领域的论文发表记录。实验过程中查询节点从论文中选择，论文属性针对1 803个关键词进行了one-hot编码，维度为1 803，论文的标签类别有3种。
DBLP数据集[25]包含数据挖掘、人工智能、计算机视觉和自然语言处理领域相关的作者、论文、会议、术语4种类型节点，实验过程中查询节点从作者中选择，作者属性是one-hot编码，维度为2 000，作者的标签类别有4种。
IMDB数据集[12]包含电影、演员、导演3种类型的节点，实验过程中查询节点从电影中选择，其属性是电影情节的one-hot编码，维度为1 007，电影的标签类别有3种。
4.1.2 对比算法
本文选择了几种基线算法作为对比算法，对比算法的描述如下。
4.1.2.1 ICS-GNN[11]
ICS-GNN是基于GNN的同质网络社区搜索方法，其主要思想是在大图上建立社区候选子图训练GNN模型，并通过用户指导的交互方式在子图上定位社区。ICS-GNN设计了BFS-swap、Greedy-G和Greedy-T三种社区搜索算法。与ICS-GNN对比分析的目的，是验证HCSMS在异质网络中挖掘语义信息进行社区搜索的有效性。
1）BFS-swap.该算法首先在候选子图上通过BFS（广度优先遍历）方式找到一个规模为s的社区，然后通过节点交换的方式，将社区外评分大的节点与社区内评分低的节点进行交换，从而保证社区评分最大。
2）Greedy-G.该算法是为应对当查询节点位于社区边缘时定位最大评分社区的困难，通过节点与社区的最短距离，结合节点评分综合计算收益以挖掘社区。
3）Greedy-T.该算法是Greedy-G的简化版，使用节点与查询节点的距离来代替最短路径的计算。
4.1.2.2 (k, ) -core[6]
（k，）-core是一种仅考虑结构内聚性挖掘社区的模型，该模型的搜索算法FastBCore是在指定元路径下寻找满足节点度大于k，且结构连接紧密的凝聚子图。与FastBCore的比较是为验证所提社区搜索方法协同网络拓扑结构和节点属性，在社区定位上的有效性。
4.1.2.3 ICSMIM[21]
ICSMIM是基于GNN的异质网络的社区搜索方法。该方法使用互信息来描述节点之间的相关性，通过社区搜索算法MI-Max挖掘异质网络中互信息最大的节点以构建目标社区。与ICSMIM对比的目的，是验证本文所提的社区度量指标相较于互信息的有效性。
4.1.2.4 VMCS-DGNN[22]
该方法是基于解耦图神经网络的异质网络社区搜索方法，其是在大图上建立候选子图来训练GNN模型，然后基于0/1背包问题对社区属性和结构凝聚性指标进行平衡来寻找社区。VMCS-DGNN需要指定元路径来搜索社区，与VMCS-DGNN对比的目的，是验证多种语义关系融合寻找社区及离线学习和在线搜索框架的有效性。
4.1.3 评价指标
1）社区精确度
社区精确度定义为结果社区中，标签与查询节点一致的节点占所有节点的比例，精确率越高说明模型性能越好。
2）社区F1-score
F1-score是准确率和召回率的调和平均值，用于衡量搜索社区与真实社区的接近程度，F1-score越高说明结果越精确。
3）社区密度
社区密度计算公式为m/[n×（n-1）/2]，其中m为社区内部的总边数，n为社区内节点的个数。社区密度用于衡量社区凝聚程度，社区密度越高，说明社区结构越紧密。
4）社区搜索效率
社区搜索效率是指完成社区搜索过程需要的时间。查询需要的时间越少，查询效率越高。
4.1.4 实现细节
本文随机初始化可学习参数，并通过Adam对模型进行优化。在训练过程中，设置学习率为0.001，正则化参数为0.001，衰退率为0.6，隐藏层数为2，注意力头数为4，语义级注意力可学习参数q的维度为128，最终嵌入维度为2，迭代次数为200。在所有对比算法中，为了保证公平性，在无特别情况说明时，默认社区规模为30，并按照同一组查询节点进行社区搜索。对于算法ICS-GNN，本文在目标类型节点（表1中带*的类型）的元路径诱导连通图中进行搜索，模型训练参数设置与原文一致。对于算法FastBcore，社区规模会受到社区结构（k，）-core中k值的影响，本文选取了社区规模可以接近30的k值作为（k，）-core的k。本文算法基于Python3.8实现，运行环境为AMD Ryzen 75800H CPU（3.20 GHz）、16 GB内存及 GeForce RTX 3080 GPU，模型训练通过PyTorch框架完成。
4.2 模型有效性分析
4.2.1 社区质量对比分析
表2给出了不同社区搜索算法在不同数据集上的精确度和F1-score以及社区密度值，可以看到，HCSMS通过BFS-Max算法找到的社区在3个数据集上均取得了最高的精确度和F1-score，BM-adv算法在3个数据集上取得了最高的社区密度值，说明HCSMS挖掘到的社区的质量优于基线方法。
表2不同社区搜索算法的社区质量对比
Tab.2Comparison of community quality among different community search algorithms
FastBcore找到的社区有较高的密度，但精确度、F1-score低于其他几种社区搜索算法，这是因为FastBcore仅聚焦于结构凝聚性，既未融合节点属性信息，也没有捕获HIN中的多元语义关系。ICS-GNN的3个社区定位算法中，Greedy-G算法的精确度、F1-score和社区密度值最高，但Greedy-G在3个数据集上的精确度、F1-score和社区密度值均低于MI-Max、BFS-Max、BM-adv的值，而MI-Max的值比BFS-Max、BM-adv的低，说明基于本文所提方法的社区度量方式优于使用互信息度量，VMCS-DGNN的精确度和F1-score低于BFS-Max，社区密度低于BM-adv，说明融合多种语义关系来定位社区有利于提高社区的质量。此外，与其他算法的社区密度值相比，BM-adv的社区密度值提高较大，且BM-adv的精确度和F1-score仅次于BFS-Max，牺牲一定的精确度换取更高的社区密度是有意义的。
4.2.2 社区搜索效率对比分析
本节将通过两种对比验证了HCSMS的效率：
1）仅对比各种搜索算法定位社区的时间，不包含模型的训练时间，结果如图4所示；2）对比HCSMS使用BFS-Max算法和ICS-GNN使用BFS-swap算法在不同查询频率下的平均查询时间，结果如图5所示。
图4社区定位算法效率对比
Fig.4Comparison of efficiency of searching algorithms
图5不同查询频率下的效率对比
Fig.5Efficiency comparison under different query frequencies
从图4可以看到，BFS-Max查询社区消耗的时间最少，其次是MI-Max，再者是BFS-swap。这是因为BFS-swap需要先捕获结构连通性，再交换节点，搜索时间比直接寻找最大评分和与最大互信息的BFS-Max和BFS-MI长。BFS-Max由于通过网络优化减少了节点搜索范围，因此查询效率要比BFS-MI高。VMCS-DGNN比BFS-swap耗时长，是因为VMCS-DGNN加入了0/1背包问题对节点价值进行计算。另外，BM-adv的搜索时间也较长，这是因为BM-adv在定位最大评分和社区后，又进行了 k-core判断。Greedy-T、Greedy-G的搜索时间最长，因为其需要计算最短路径距离。
从图5可以看到，在各个数据集上ICS-GNN在不同查询频率下的平均查询时间几乎不变；在低频查询（1~10次查询）时，ICS-GNN的平均查询时间比HCSMS高，但随着查询频率增加，HCSMS的平均查询时间逐渐减少。当查询频率达到50次时，HCSMS的平均查询时间已经优于ICS-GNN。这些结果体现了离线学习对于高频查询的优越性。
4.2.3 搜索算法分析
为了验证本文所提社区定位算法的有效性，本节在HCSMS中首先进行离线学习，然后分别用BFS-Max、BM-adv、BFS-swap、Greedy-T、Greedy-G定位社区，对比所获社区的质量，结果如图6所示；同理，在ICS-GNN中基于相同的GNN模型分别使用上述算法定位社区，对比所获社区的质量，结果如图7所示。由图6和图7可以看到，BFS-Max找到的社区具有最大的社区精确度和F1-score，BM-adv算法在社区密度上取得最大值，且BM-adv所获社区的精确度、F1-score仅次于BFS-Max，说明BFS-Max和BM-adv可以更好地判定社区成员。另外，对比图6和图7可以看到，同一个算法在HCSMS上的表现要比ICS-GNN更高，说明HCSMS的模型能够更好地捕获节点间的相似性。
图6HCSMS模型上不同的社区定位算法对比
Fig.6Comparison of different community localization algorithms on the HCSMS model
图7ICS-GNN模型上不同的社区定位算法对比
Fig.7Comparison of different community localization algorithms on the ICS-GNN model
4.3 参数敏感性分析
本文在3个数据集上测试了网络优化阈值θ、社区规模s、元路径数量m对社区精确度、F1-score和社区密度以及社区搜索效率的影响。
4.3.1 网络优化阈值敏感性分析
网络优化阈值θ的取值范围在0~1之间，图8展示了不同θ下BFS-Max社区精确度、F1-score和社区密度以及社区搜索效率。由图8可以看到，社区精确度、F1-score、社区密度和搜索时间均随θ的减小而减小，这是因为θ越小，网络优化时删除的连边会越多，网络越稀疏，尽管查询过程需要遍历的边减少，但真实的社区信息遭到破坏。在ACM、DBLP和IMDB数据集中，θ分别取0.5，0.3和0.7左右可以同时兼顾社区质量和搜索时间。
图8网络优化阈值分析
Fig.8Network optimization threshold analysis
4.3.2 社区规模敏感性分析
图9描述了BM-Max不同社区规模s下所获得的社区精确度、F1-score和社区密度以及社区搜索效率。从图9可以看到，随着社区规模s的增加，3个数据集上社区精确度和F1-score的变化幅度不大，但社区密度逐渐减小，查询过程需要的时间成本增加。
图9社区规模分析
Fig.9Community size analysis
4.3.3 元路径数量敏感性分析
表3给出了在不同m下BFS-Max所获得的社区精确度、F1-score和社区密度以及社区搜索效率。其中m=1表示在一条元路径下进行搜索。实验中社区规模s=100。从表3可以看到，随着元路径数量的增加，社区精确度和F1-score以及社区密度都在增加，搜索时间也逐渐变长。这是因为元路径的增加扩展了节点间的交互关系，增加了网络的稠密性。
表3元路径数量敏感性分析
Tab.3Sensitivity analysis of the number of meta paths
4.4 消融研究
为了验证HCSMS各个模块的有效性，本文设计了HCSMS的6个变体进行消融实验，具体描述如下。
变体1 HCSMSGNN:HCSMS中消除了GNN特征融合模块，仅考虑结构特征通过BFS挖掘规模为s的社区，以验证HCSMS通过GNN融合网络结构、节点属性信息查找社区的有效性。
变体2 HCSMSsin:HCSMS中消除了多种语义关系影响，只使用一条元路径来寻找社区，以验证HCSMS融合多种语义关系查询社区的有效性。
变体3 HCSMSnode:HCSMS中消除了节点级别的关注，并赋予每个元路径邻居同样的重要性，以验证模型在节点级信息融合的有效性。
变体4 HCSMSsim:HCSMS中消除了语义级别的关注，并赋予每条元路径同等的重要性，以验证模型区分多种语义关系重要性进行融合的有效性。
变体5 HCSMSre:HCSMS中消除了网络优化模块的影响，在模型训练完成后直接通过BFS-Max定位目标社区，以验证网络优化对社区搜索效率的影响。
变体6 HCSMSBM:HCSMS中消除了BM-adv算法对结构的限制，仅挖掘最大评分和社区。HCSMS和各个变体的搜索结果如表4所示，可以看到，HCSMSGNN的查询时间最短，但社区精确度最低，说明通过GNN捕获网络中多维信息综合衡量节点相关性对搜索高质量的社区是有效的。
HCSMS的所有指标均比HCSMSsin高，且HCSMSsin的社区密度较其他变体都低，说明融合多种语义关系对社区搜索是有利的，且仅基于一种元路径难以挖掘到密度较高的社区。
HCSMS的所有指标均比HCSMSnode高，说明模型使用节点注意力融合有利于对节点做出更好的评分，对搜索高质量的社区是有效的。
HCSMS的所有指标均比HCSMSsim高，说明区分多种语义关系的重要性来挖掘社区可以提高社区的精准度和结构凝聚性。
在所有变体中HCSMSre搜索耗时最长，说明网络优化可以降低查询的时间成本。
HCSMS的社区密度是最高的，但精准度和F1-score仅次于HCSMSBM，说明挖掘结构凝聚性会影响到社区的属性相似性，但牺牲一定的精确度来换取高回报的社区凝聚性是有意义的。
表4消融研究结果
Tab.4Results of ablation research
4.5 案例研究
为了验证区分多种语义关系挖掘社区的有效性，本文选取DBLP数据集中的1=APCPA、2=APTPA两条元路径进行案例研究，并设置查询节点q=“WeiZhou”进行了如下查询：1）分别基于元路径1=APCPA和2=APTPA单独查询；2）基于3=1+2查询，即同时考虑两种语义关系，但不区分两种语义关系的重要性；3）基于4= （）查询，即同时考虑两种语义关系，但1比2重要；4）基于5=查询，即同时考虑两种语义关系，但2比1重要。查询结果见表5，可以看到，基于1和2的查询均未找到满足社区规模s=10的社区，且基于1和2的查询结果中除“Steve Jones”和“Zeng Minzu”的重叠，其余节点都只出现在一条元路径的查询结果中；基于3的查询可以找到满足规模的社区，且包含只在1和2独立查询结果中的作者；基于4和5的查询可以同时找到1和2独立查询结果中的作者，且4的查询过程中优先选择只基于1找到的作者，原因是4的查询中1比2重要，反之，5查询过程则优先选择只基于2找到的作者。由于“Steve Jones”和“Zeng Minzu”是1和2独立查询结果中的重叠作者，表明他们与查询节点q的联系更密切，在4和5的查询中有较高的评分，会较早加入社区。
另外，为了验证HCSMS中离线学习和在线搜索策略的有效性，本文针对3个查询节点，分别进行了一次不分离学习和搜索的查询，即输入一个查询节点，根据其标签类别训练一个GNN模型获得节点评分来定位社区。然后，对3个查询节点分别再进行一次使用的离线学习和在线搜索策略的查询，即在离线阶段根据节点标签类别训练多个GNN模型，然后通过在线阶段输入查询节点，根据其标签类别从学习好的GNN模型上获得节点评分来定位社区。由表6查询结果可见，不分离学习和搜索方式查找到的作者与分离学习和搜索查找到的作者是相同的，说明离线学习和在线搜索策略不会影响到社区成员的定位，因此，HCSMS使用的离线学习和在线搜索策略是有效的。
表5语义关系案例研究
Tab.5Semantic Relationship Case Study
表6搜索策略案例研究
Tab.6Semantic relationship case study
5 结语
本文研究了异质信息网络中的社区搜索问题，提出了异质信息网络中融合多种语义关系的社区搜索方法HCSMS，及采用离线学习和在线搜索的高效策略，从HIN中挖掘属性相似、结构内聚且包含多种语义关系的社区。HCSMS通过多条元路径捕捉HIN的多种语义关系，并通过语义注意力机制区分各种语义关系的重要性来引导社区定位，离线阶段预训练节点-社区关联模型，生成节点归属各类社区的概率分布向量，在线查询则基于具体的查询，利用预训练模型快速定位目标社区。HCSMS无需基于规则定义社区，具有较高的灵活性；其概率预计算机制与查询无关，显著提高了高频场景下的社区搜索效率。与5个基线算法对比及消融案例研究的结果，验证了HCSMS的有效性和效率。
目前，使用GNN进行异质网络社区搜索的研究尚处于探索阶段，异质网络中除结构信息、属性信息外，还包含许多信息，如时间信息、位置信息等，因此融合更多信息的异质网络社区搜索还有待深入研究。
