K阶图卷积属性网络社团检测方法

陈 洁，张二明，王倩倩，赵 姝+，张燕平

1.安徽大学 计算机科学与技术学院，合肥 230601

2.安徽大学 国际教育学院，合肥 230601

近年来，在许多学科中，将结构化数据建模和解释为网络的趋势日益增长。网络作为一种描述实体之间关系的普遍抽象概念，已成为数据科学研究的热点，网络分析也日益受到生物学和计算机科学等领域的关注[1]。社团检测是网络分析中的一项重要任务，其目的是将网络划分为多个社团，使得同一社团内的节点联系比较紧密，不同社团内的节点联系比较稀疏。

在许多领域中，真实的网络数据不仅包括节点的结构信息也包括节点的属性信息。例如，在社交网络中，边缘表示人与人之间的关系（友谊、合作等），节点属性描述的是一个人的角色或性格。在引文网络中，节点代表论文，边缘表示论文之间的引用关系，节点属性描述论文的特征（关键词、发表时间等）。属性网络社团检测任务中如果节点结构信息缺失导致网络结构稀疏，属性信息可以补充结构信息，缓解网络结构的稀疏性，使社团检测更加精确。因此，同时考虑节点的结构信息和属性信息有助于提高社团检测的性能。目前，涉及到属性网络社团检测任务[2]的研究并不多，如何融合节点的结构信息与属性信息进行社团检测仍然是一个难题。

现有的经典社团检测方法，如K-means只能利用节点属性信息进行社团划分。Louvain算法[3]只能利用节点的结构信息进行社团划分。然而，在属性网络中这两类社团检测方法皆存在不足，前者没有利用属性网络中的结构信息，后者没有利用属性网络中属性信息。

近几年，结合属性信息与结构信息的社团检测方法被提出，包括基于生成模型[4]、光谱聚类[5]、随机游走[6-7]、马尔可夫随机场[8-9]、非负矩阵分解[10]和图卷积网络（graph convolution network，GCN）[11]等方法。特别是基于图卷积的方法，如GAE（graph autoencoders）[12]在几个属性网络社团检测任务上展示了先进的性能。但是现有的图卷积方法大多数是直接使用图卷积作为特征提取器，每个卷积层都加上一个投影层，很难叠加很多层，训练一个深度模型。如ARGE（adversarially regularized graph autoencoder）[13]和MGAE（marginalized graph autoencoder）[14]使用两层和三层的图卷积，只考虑每个节点两阶或三阶以内的邻居，没有充分利用节点之间的关系。此外，这些方法都是用一个固定的低阶图卷积算法模型，忽略了真实数据集的多样性，这可能降低社团检测结果。

为了克服原始网络结构的稀疏性和利用节点的高阶结构关联，本文提出了一种基于K阶图卷积的属性网络社团检测方法（K-order graph convolution community detection method，KGCN）。首先，根据节点属性之间的相似性添加新边缘对原始网络进行重构，弥补节点的结构信息。其次，相邻的节点具有相似的特征表示，往往属于一个社团。不像之前方法那样设计一个叠加多层的图卷积，而是设计一个考虑到每个节点K阶邻居的K阶图卷积，作为节点特征的低通图滤波器来获得平滑的特征表示。最后，采用谱聚类算法进行社团检测。KGCN 考虑到现实网络结构的多样性，针对不同的属性网络可以选择不同的K值。在四个真实属性网络上的实验结果表明，KGCN具有很强的竞争力，在很多情况下优于最先进的方法。

1 相关工作

现有的社团检测算法大致分为三种[15]：基于结构的社团检测方法、基于属性的社团检测方法和融合结构与属性的社团检测方法。

基于结构的社团检测方法：利用结构信息对网络进行划分是一种经典的社团检测方法，通过边缘信息优化某种衡量指标得到最优社团结构，Louvain算法[3]是其中有代表性的算法。然而由于计算成本高，这些算法无法处理大规模网络。标签传播[16]算法根据结构信息在网络之中传播标签进行社团检测，该算法虽然具有可扩展性，但最近的研究表明，它在许多常见的场景[17]上运行时并不健壮。也有一些解决方案试图从其他角度进行社团检测，如DandM（deepwork and Markov）[18]算法通过网络表示学习模型将结构信息转换为特征信息，再利用概率图模型进行社团检测。

基于属性的社团检测方法：K-means是一种基于属性的社团检测方法，被广泛应用于科研和工业领域。该方法首先定义K个初始社团中心，通过不断迭代将节点划分到合适的社团，在网络表示学习模型的基础上有着大量的扩展[19-20]。

融合结构与属性的社团检测方法：属性网络社团检测方法需同时考虑节点的结构信息和属性信息。SA-Cluster[21]和HeteroAttractor[22]使用虚拟顶点来映射属性值。每个属性值由网络上的单个虚拟顶点表示。这些虚拟顶点与网络中的所有顶点相连，以保持它们的属性关系。CODICIL[23]、SAC2（structural and attribute cluster two）[24]使用属性为每个顶点寻找最近的邻居，然后通过连接每个顶点与其邻居来重构网络，保留属性信息。一些新的方法使用图卷积网络整合结构信息和属性信息。例如，GAE 算法和VGAE（variational graph auto-encoders）算法用双层图卷积学习节点表示，然后分别用自编码器和变分自编码器重构邻接矩阵。MGAE算法用三层图卷积学习节点特征表示，然后应用边缘去噪自编码器重构给定的节点特征。ARGE 算法和ARVGE（adversarially regularized variational graph autoencoder）算法分别通过GAE 和VGAE 学习节点嵌入，然后使用生成对抗网络强制节点嵌入以匹配先验分布。

2 模型介绍

本文提出的KGCN社团检测方法如图1所示，共分为三大部分：第一部分根据节点的属性信息对原始网络进行重构，得到缓解稀疏性的重构网络；第二部分考虑到每个节点K阶内的邻居，采用K阶图卷积编码器对节点进行编码得到节点特征表示；第三部分根据获得的节点特征表示使用谱聚类算法进行社团检测得到属性网络的社团结构。

图1 KGCN模型框架Fig.1 KGCN model framework

2.1 问题定义

给出一个属性网络G=(V,E,X)，其中V={v1,v2,…,vn}表示包含n个节点的集合，E 表示边缘集合，X=[x1,x2,…,xn]T∈Rn×d表示节点的属性矩阵，xi∈Rd表示节点vi的属性信息。本文任务是将n个节点划分为m个社团C={c1,c2,…,cm}。

2.2 重构网络

属性网络同时包含节点的结构信息和节点的属性信息，对原始网络结构进行重构，首先定义节点之间的属性相似度。

其中，Suv∈[0,1]为节点u与节点v之间的相似度，然后根据节点之间的属性相似度在具有相似属性的节点对之间添加新的边缘。

其中，E为新增边缘集合，α为属性相似度阈值。如果节点u与节点v之间的相似度大于阈值α则在两节点之间添加一条新的边缘补充节点的结构信息，缓解原始网络的稀疏性。重构后网络的邻接矩阵表示为A={auv}∈Rn×n，如果节点u与节点v之间存在连边，则auv=1，相反auv=0。

2.3 K 阶图卷积

利用节点属性信息缓解网络结构稀疏性得到重构网络，然后使用K阶图卷积编码器对节点进行编码，得到每个节点的特征表示。图卷积定义为图信号f与图滤波器G的乘积。

其中，Z=[z1,z2,…,zn]T，zq为用户相关特征向量uq的系数，系数的大小表示uq的强度。

考虑到同一社团内的节点不仅要在结构上具有紧密性，在属性上也应具有同质性，因此对属性矩阵X进行图卷积，使得相邻节点在每个维度上具有相似的特征值。滤波后的属性矩阵计算如下：

其中，k为正整数，不同的k值对应不同阶的邻居。k阶图卷积迭代计算公式为：

2.4 谱聚类

根据图卷积滤波后的节点特征采用谱聚类算法[26]进行社团划分，将n个节点划分到m个社团中。首先计算彼此节点之间的相似性，得到非负对称的相似度矩阵S。

通过计算S的m个最大特征值相关的特征表示作为初始节点，然后应用K-means 算法进行社团检测，得到m个社团结构。

2.5 时间复杂度分析

用n表示节点数，d表示属性数，m表示社团个数，N表示邻接矩阵A的非零项数。对原始网络进行重构得到重构网络的时间复杂度是O(n2)。由于邻接矩阵N≪n2，初始化时计算Ls的时间复杂度为O(N)，对于一个稀疏的Ls，式（7）中计算K阶图卷积的最快方法是将X左乘重复K次，其时间复杂度为O(NdK)。对进行谱聚类的时间复杂度为O(n2d+n2m)。由于m≪d≪n，总的时间复杂度为O(n2d+NdK)。

3 实验结果与分析

3.1 数据集

本文在4个真实数据集[25]上进行了实验（所有数据集的边缘都是无向的）。Cora、CiteSeer 和Pubmed是由科学出版物组成的引文网络，每个顶点代表一个出版物，一条边表示一条引文关系。Wiki是一个网页网络，如果一个网页与另外一个网页有链接，则存在连边。Cora与CiteSeer每个顶点的二元属性表明词包中有一个单词存在或不存在。Pubmed与Wiki每个顶点的属性为词的权重。数据集的详细信息如表1所示。

表1 数据集详细信息Table 1 Dataset details

3.2 评估指标与对比算法

为了评估社团检测性能，将KGCN 与三类社团检测方法进行对比，使用三个常用性能指标[27]：精度（accuracy，Acc）、归一化互信息（normalized mutual information，NMI）和F1-score（F1）。对比算法如下：

（1）基于属性的社团检测方法：K-means 和Spectral-g利用线性核函数构造几点属性相似性矩阵进行社团检测。

（2）基于结构的社团检测方法：以节点邻接矩阵作为相似矩阵的谱聚类算法（Spectral-g），DNGR 利用深度神经网络学习节点表示，再进行社团划分。

（3）融合结构和属性的社团检测方法：图自编码器GAE 和图变分自编码器VGAE，边缘图自编码器MGAE，反向正则化图自编码器ARGE和ARVGE，以及自适应图编码器AGC。

3.3 参数设置

对比算法中的参数遵循原始文献中的设置。其中DeepWalk的随机漫步次数为10次，每个节点的潜在维数为128，每次随机漫步的路径长度为80。DNGR的自编码器有三层，分别包含512个神经元和256个隐含层神经元。对于GAE和VGAE，构建了隐含层具有32 个神经元和嵌入层具有16 个神经元的编码器，并使用学习率为0.01的Adam优化器训练编码器进行200次迭代。对于MGAE，损失等级p为0.4，层数为3，λ参数为10-5。对于ARGE 和ARVGE，本文构造了一个包含32 个神经元隐含层和16 个神经元嵌入层的编码器。识别器由两个隐含层组成，分别包含16 个神经元和64 个神经元。在Cora、CiteSeer和Wiki 上，本文用Adam 优化器训练了ARGE 和ARVGE 的自动编码器相关模型200 次迭代，编码器学习率和判别器学习率均为0.001；在Pubmed 上，本文以编码器学习率0.001 和识别器学习率0.008 训练它们进行2 000 次迭代。在算法KGCN 中，超参数α和k分别在网络重构和节点编码过程中起到作用。定义α取值范围为α∈[0,1]，步长为0.1,k的取值范围为k∈[1,60]，步长为1，通过实验观察KGCN 算法的最佳参数值。如图2、图3所示，在4个真实数据集上α和k的普适性范围为α∈[0.5,1.0]和k∈[15,25]。其中当α=0.5,k=14 时Cora 数据集取得最佳实验结果，当α=1.0,k=19 时CiteSeer 数据集取得最佳实验结果，当α=0.9,k=50 时Pubmed 数据集取得最佳实验结果，当α=0.2,k=4 时Wiki 数据集取得最佳实验结果。

图2 评价指标随α 变化图Fig.2 Preformance changing with α

图3 评价指标随k 变化图Fig.3 Preformance changing with k

3.4 结果分析

遵循参数设置部分的最优参数值，本文在4个真实数据集上分别运行10次取平均值作为最终实验结果，如表2所示，其中加粗表示最优实验结果。

由表2可以得出，本文提出的KGCN算法在总体上优于其他11种算法。KGCN的社团检测性能与仅利用结构信息或属性信息的社团检测方法相比，往往表现出很大的优势。原因是同一社团内不仅在结构上具有紧密性，在属性上也具有同质性，KGCN 算法融合了节点的结构信息与节点的属性信息，这两种信息可以相互补充，提高社团检测性能。

表2 不同数据集上各算法结果对比Table 2 Comparison of algorithm results on different datasets 单位：%

KGCN 算法与现有的同时使用属性信息和结构信息的社团检测方法相比依然有着很大的优势。因为GAE、VGAE、ARGE和ARVGE在对节点进行编码时仅考虑到每个节点的二阶邻居，MGAE 只考虑到每个节点的三阶邻居，AGC 模型虽然考虑到节点的高阶邻居，但原始的网络结构具有稀疏性，部分节点因为缺失结构信息会导致社团检测性能下降。KGCN 算法通过属性信息重构网络缓解了原始网络的稀疏性，在节点编码时获得质量更佳的节点特征表示，从而提高社团检测性能。

由实验数据可以得出，在数据集CiteSeer与Wiki上，KGCN算法在所有评价指标上均优于其他对比算法。相比第二优算法，KGCN在CiteSeer数据集上分别取得了1.7%的精度提升、2.4%的归一化互信息提升和1.5%的F1值提升；KGCN在Wiki数据集上分别取得了21.3%的精度提升、28.9%的归一化互信息提升和38.0%的F1 值提升；在数据集Cora 和Pubmed上，KGCN在评价指标Acc和F1上获得最优的表现，可能由于属性长度较短，未能根据不丰富的属性信息得到理想的重构网络，在评价指标NMI 上仅获得相近的结果，其中在Cora 数据集上，KGCN 算法与第二优算法相比获得了3.3%的精度提升和2.4%的F1值提升。

3.5 消融分析

与其他社团检测算法对比的同时，也针对KGCN算法进行了如下消融分析：原始网络结构上使用一阶图卷积对节点进行编码（Ori_1），原始网络结构上使用K阶图卷积对节点进行编码（Ori_k），重构网络上使用K阶图卷积对节点进行编码（Re_k）。表3给出了实验结果，其中加粗表示最优实验结果。通过表3可以看出，Ori_1的社团检测结果最差，这是因为原始网络具有稀疏性且低阶图卷积没有考虑节点高阶结构关联。Ori_k 的社团检测结果有所提升，这是因为对节点进行编码时考虑到节点高阶结构关联。Re_k 得到最优社团检测结果，这是因为其不仅克服了原始网络结构的稀疏性，在对节点进行编码时也考虑到节点高阶结构关联。

表3 消融分析实验结果Table 3 Results of ablation analysis 单位：%

4 总结与展望

本文提出了一种属性网络社团检测方法。首先根据节点的属性信息对原始网络进行重构，缓解原始网络结构的稀疏性。为充分利用结构信息和优化不同属性网络的社团检测性能，针对不同的属性网络考虑到不同阶的邻居，采用K阶图卷积编码器对节点进行编码获得节点特征表示。最后根据获得的节点特征表示使用谱聚类算法进行社团检测。实验结果表明，本文提出的融合属性信息与结构信息的K阶图卷积社团检测方法在许多大型真实网络上都优于目前最先进的社区检测方法。在未来的工作中，考虑改进网络重构方法，使方法具有更好的社团检测性能。