基于卷积网络的社区检测算法研究综述

摘要：社区检测是将网络中特征相同的成员聚合在一起，社区内成员关系紧密，社区之间成员关系稀疏。社区检测在数据挖掘中具有重要意义。近年来由于大数据和深度学习的高速发展，使得深度学习在社区检测模型中有了显著发展。卷积神经网络在社区检测领域的应用调查对社区检测模型具有重要意义，通过对卷积网络和图卷积网络社区检测方法的归纳总结，总结现有方法的优缺点。最后，通过这个快速增长的深度学习领域提出亟待解决的问题。

关键词：社区检测；数据挖掘；神经网络；图卷积网络；重叠社区；拓扑不完全网络

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2024）24-0097-04

开放科学（资源服务）标识码（OSID）

0 引言

自从2002年以来，Girvan和Newman[1]打开了图划分的新方向。在过去十年里，计算机科学的研究者通过利用静态和动态网络，小型和大型网络的网络拓扑结构和语义信息广泛的研究社区检测算法。

社区检测是一个越来越具有现实意义的研究领域。俗话说“物以类聚，人以群分”。基于六度分离理论，世界上任何人都能够通过6个熟悉的人知道其他人。这个俗语和六度分离理论都暗示了社交网络的惊人联系。“物以类聚，人以群分”强调了人们倾向于与具有相似兴趣、背景或特征的人聚集在一起的趋势。而六度分离理论则指出了人与人之间的连接并不像我们想象的那么遥远，即使我们可能认识的人数很少，通过社交网络中的连接，我们仍然可以与世界上任何一个人建立联系。这两者共同揭示了社会网络的奇妙和复杂性，以及人际关系的密切联系。比如，社会网络中典型的购物网站，社区检测挖掘商家与用户、商品与商品、用户与用户、品牌与商家之间的关系，以此来推广产品和提供个性化服务。 社区检测应用在代谢网络和蛋白质网络中揭示生物体内复杂的调控机制和生物学过程，有助于理解各种疾病的发生机制。因此，社区检测在数据挖掘和网络分析中非常重要。

许多传统社区检测技术，如光谱聚类和统计推断能够应用在小型网络和简单社区检测模型中。然而，包含丰富非线性信息的真实世界网络因为具有复杂的拓扑和高维特征，使得传统模型不太适用于实际应用。随着大数据的深度学习技术的蓬勃发展，越来越大的规模，高稀疏性，复杂结构，动态网络在现实世界中的场景被探索。传统社区检测方法解决不了的问题使用深度学习技术能够很好地解决，包括网络中非线性关系的处理；从高维网络数据到低维网络数据的转化；社区检测时更有效的保留网络结构的复杂性等。因此，社区检测的深度学习方法是一个新的趋势，包括卷积网络社区检测（Convolutional Neural Networks ，CNNs）、生成对抗网络（Generative Adversarial Networks，GAN）、深度非负矩阵因子（Deep Non-negative Matrix Factorization，DNMF）、深度嵌入（Deep Embeddings，DE）等。卷积网络作为深度学习的代表，在复杂网络的社区检测中占有很重要的位置。卷积网络包括卷积神经网络和图卷积网络（Graph Convolutional Networks ，GCNs）[2]。

卷积网络的一般框架是复杂结构关系高维数据到低维数据的学习，能够自动学习和提取非结构特征，从而在进行社区检测时提供更多有效的知识。除此之外，在提取特征进行社区进测时，卷积网络能够将节点、边、邻居节点或者多个网络结构的信息融合并进行更加有效的社区检测。

1 社区检测

定义1：网络 给定一个基本网络[G（V，E）]，且[V={V1，V2，...，Vn}]是节点集合，[E=eijni，j=1]代表节点之间的边集。[N（vi）={u∈V|（vi，u）∈E}]定义为[vi]的邻居节点，[A=[aij]]定义为[n×n]维邻接矩阵。如果[eij=E]则[aij=1]，否则[aij=0]。如果[aij≠aji]，[G]是一个有向网络，否则[G]是一个无向网络。如果[aij]由[wij∈W]加权，则[G=（V，E，W）]是权重网络，否则就是非权重网络。如果[aij]的值是+1和-1，[G]是信号网络。如果节点[vi∈V]归属于[xi∈X∈ℝn×d]，[G=（V，E，X）]是属性网络，否则就是无属性网络。

定义2：社区 给定一组社区[C={C1，C2，…，CK}]，每个社区[Ck]是图[G]的一个分区，它保持区域结构和聚类性质[3]。也就是说，社区[Ck]中的成员都具有相同的属性和结构。社区聚集到社区[Ck]的节点[vi]应当满足条件：社区内部节点的度要超过外部节点的度。假设[Ck⋂Ck'=∅]，[（∀k，k'）]，[C]表示离散社区，否则就表示重叠社区。

定义3：社区检测输入 深度学习模型将网络拓扑结构和网络属性作为输入。节点和边形成的拓扑能够在矩阵中加以表示，比如邻接矩阵[A]，信号邻接矩阵[A（+，-）]，以及类似模块矩阵[B]的测量矩阵。网络属性表示网络实体额外的信息，例如节点属性[X]。

社区检测输出 社区检测输出方法的目标是输出一组离散或者重叠社区。比如，学生俱乐部只允许一个学生加入其中的一个俱乐部，这是离散社区的典型代表。参与社交网络中多个圈子的用户，这是重叠社区的典型代表。部分重叠社区的检测方法可以检测离散社区。

2 基于卷积神经网络的社区检测算法

CNNs是一类针对图像数据等网格状拓扑数据提出的特殊的前馈深度神经网络（Deep Neural Network，DNN），其卷积层减少计算成本和池化操作来确保CNN特征表示中的稳健性。现有的社区检测方法实现了具有严格数据输入限制的CNN模型，见图1。

传统的社区检测是深度学习模型中的无监督学习任务，现实中网络可能边缺失，这种拓扑结构不完整的网络，进行社区检测时会降低其准确度。为此，Xin等[4]提出了第一个针对不完全拓扑网络结构的有监督CNN社区检测模型。通过设计一个结构化深度卷积神经网络模型，以便能够更好地检测网络拓扑结构不完整网络的社区。通过添线性或者星型预处理方法来调整网络结构，该深度卷积神经网络有两个卷积层和一个全连接层组成。然后在每个特征图上应用最大池化运算，最后第二卷积层的最大池化操作之后的特征图都连接到全连接层，逐步将不完整拓扑结构网络的特征补充完整。最后一个连接层[f]为每个节点[vi]更新社区：

[oki=σ（bfk+Wfkh（2）i）] （1）

其中[σ]表示激活函数，[Wfk]和[bfk]第[k]个神经元的权重和偏差，[h（2）i]是前两个卷积层输出节点表示向量。该模型的损失函数为：

[L=12i∥oi-yi∥22=12ik（oki-yii）2] （2）

这里[yi]表示节点[vi]的标记向量，[yki∈{0，1}]表示[vi]是否属于第[k]个社区。该模型社区检测中，用10%的标记节点实现了约80%的准确率，表明使用线性和星型预处理方法能够有效提高社区检测的准确率。

大规模社交网络具有高稀疏性，Sperli[5]设计了一个可以处理大维度和高稀疏性的卷积神经网络，全连接层由[k]个输出神经元组成，每个神经元对应一个特定的社区。每个特征图中的每条条目都连接到全连接层上的所有[k]个神经元，表示为：

[okn=relu（bf+WfkqC1C2n）] （3）

其中[okn]是第[k]层神经元的值，表示节点[n]属于第[k]个社区的概率，[bf]，[Wfk]和[qC1C2n]分别是统计偏差、权重矩阵和第二卷积层输出。同样为了处理维数和稀疏性问题，Santo等人[6]引入了SparseConv2D算子修改CNN的输入层，用来更有效的在稀疏矩阵上执行卷积。虽然神经卷积网络在社区检测上取得了一定的效果，但是根据现有的模型，都无法处理社区的重叠密集情况，其中一个节点可能属于多个社区。GCN在处理图数据具有很强的优势，其最近的发展表明其有能力在图形的数据中建模和捕捉复杂关系。因此，越来越多的社区检测方法开始关注GCN。

3 基于图卷积网络的社区检测算法

GCN是基于CNNs图结构数据提出的，并在频谱滤波器的一阶近似上执行。GCNs的分层传播规则是：

[H（l+1）=σ（D-12AD-12H（l）W（l））] （4）

其中[l]层的潜在表示保存在矩阵[H（l）（X（0）=H）]中，通过激活函数[σ（⋅）]和特定层训练权重矩阵[W（l）]中；[A=A+In]和[In]表示单位矩阵；[Dij=jaij]且[aij∈A]。

GCNs进行社区检测是在深度图卷积层上全局提取复杂特征并聚合节点邻居信息。有两类基于GCNs的社区检测算法[7]：有监督/半监督算法以及无监督算法。GCNs使用传统深度学习算子来进行社区检测，比如用于统计推断的SBMs，用于频谱分析的拉普拉斯矩阵和用于信念传播的概率图模型 [8] 。比如线形图神经网络（Line Graph Nerual Network，LGNN）是一个有监督的社区检测模型，改进了SBNs并减少了计算开销，将非回溯算子与信念传播的消息传递规则相结合，学习网络中的节点表示特征 。激活函数softmax识别条件概率：节点[vi]属于社区[Ck（oi，k=p（yi=ck|Θ，G））]，并且最小化社区标签所有可能的组合交叉熵损失[SC]：

[L（Θ）=minπ∈SC-ilogoi，π（yi）]   （5）

GCN本身并不是为了进行社区检测，因此模型并不能准确进行社区分类。为了弥补这个差距，一种半监督的社区GCN检测模型MRFasGCN通过使用马尔科夫随机场进行社区检测，同时能够将社区检测结果进行优化。为了实现无监督的社区检测，一个基于GCN框架的网络表示学习SGCN模型设计了局部标签采样模型[9]并确定社区检测的结构中心，利用图卷积网络进行局部特征提取，通过将标签采样模型和GCN集成到一个无监督框架中，SGCN在训练每个没有先验标签节点的社区成员身份时融合拓扑和属性来进行社区检测。基于图神经网络的重叠社区检测[10]（Neural Overlapping Community Detection，NOCD）模型，是一个无监督端到端的深度学习模型，将GCN模型和伯努利-泊松（Bernoulli-Poisson，BP）概率相结合，使用ReLU激活函数应用在输出层，BP模型的负对数似然对从属矩阵使用最小化参数进行优化，GNN为相邻节点输出相似的社区隶属向量。邻域聚合算法将图卷积公式化为对称拉普拉斯平滑运算，聚合节点与邻居的特征信息。但是这种算法在神经网络深度增加时会导致过度平滑的问题。因此Hu等人[11]设计了图卷积梯形网络（Graph Convolutional Ladder-shape Networks，GCLN），这是一种新的图神经网络结构，使用上下文特征通道构建具有收缩和扩张路径的对称结构，该梯形架构允许网络直接将上下文信息从浅层传输、融合到更深层，克服过度平滑，扩展神经网络的规模。分层传播等式如下：

[H（l+1）=s（D-12AD-12H（l）W（l））] （6）

独立性提升图纠缠网络[12]（Independence Promoted Graph Disentangled Network，IPGDN）将现实网络中纠缠的潜在因素独立表示出来，同时增强节点表示之前的独立性，以降低检测邻域的难度。邻域路由中的Hilbert-Schmidt独立准则（HSIC）正则化支持IPGDN。

属性图上的社区检测除了需要处理网络结构，同时需要考虑属性特征。其中结构不同但是属性相同或相似特征的节点可能会划分为同一社区。为了解决这一问题，在自适应图卷积[13]（AGC）中嵌入了一个低通滤波器，通过[p（λq）=（1-12λq）k]，其中[G]的频率响应函数[p∧=diag（p（λ1，…，p（λn））]在所有特征值上递减且非负。AGC以[k]为单位卷积选择合适的邻域跳跃大小，并通过[k]阶图卷积将图特征表示为：

[X=（I-12Ls）kX] （7）

其中[Ls]表示[λq]上的对称归一化图拉普拉斯算子。滤波器平滑节点嵌入[X]调整到[k]，[k]越高，滤波性能越好，社区检测准确度更高。自适应图解码器[14]（Adaptive Graph Encoder，AGE）是另一个扩展到社区检测的平滑滤波器模型。AGE自适应的执行节点相似性测量（[S=[sij]]）和t-附加拉普拉斯平滑滤波器：

[X=（I-γL）tX] （8）

[L=（vi，vj）∈V-s′ijlog（sij）-（1-s′ij）log（1-sij）] （9）

其中[V]表示正（相似）和负（不相似）样本上的平衡训练集，[s′ij]是节点（[vi，vj]）上的排序二进制相似性标签。

GCN滤波器在图卷积神经网络中应用广泛。例如，在谱图卷积结构中，具有Cayley多项式的图卷积神经网络（CayleyNets）提出了一种用于社区检测高阶近似的有效cayley滤波器。CayleyNets应用于窄带滤波，原因是低频中包含大量的社区信息，用于社区检测的目标表示。CayleyNets结合Cayley滤波器，包含频谱卷积层中的平均池和节点上的半监督softmax分类器用于社区成员的预测。为了缓解图神经网络稀疏性的瓶颈，Zhang等人[15]提出了属性图聚类的谱嵌入网络（SENet），通过利用共享邻居的信息来改进图结构，借助频谱聚类损失来学习节点嵌入，该损失函数为：

[L=-tr（（H（3））ΤD-12KD-12H（3））] （10）

其中[K]是编码类型和属性的核矩阵。 社区深度图最大熵[16]（Community Deep Graph Infomax ，CommDGI）通过节点和社区上的交互信息（MI）联合优化图表示和聚类，并测量图模块化以实现最大化，该算法通过对比训练来获得更好的表示、节点聚类的k-均值和目标聚类中心。Zhao等人[17]提出了一个图去偏对比学习，同时执行表示和聚类，从而提高聚类结果和判别表示。Moradan等人[18]提出了图卷积网络上的统一社区检测（Unified Community dectection with Graph Convolutional Networks，UCoDe），是属性图中进行社区检测的统一方法，引入新的对比损失来进行社区检测，能够同时检测非重叠社区和重叠社区。

4 现有卷积网络社区检测算法的研究难点

虽然深度学习已经将社区检测带入一个繁荣的时代，但仍有一些悬而未决的问题需要进一步研究。

1）未知的社区数量。现实场景中的社区检测，由于获取成本高，大多数数据都没有标记，因此社区数量[k]是未知的。深度学习中的非监督检测算法提供了一个有效的方法来处理未知场景的问题，但是一般需要指定[k]为先验知识。因此在不知道社区数量[k]时算法无法进行，因此在图卷积网络中解决社区数量[k]的问题就变得非常重要。

2）分层网络社区检测限制。网络通常显示不同规模的社区树状层次结构，其中较低层次的结构聚集在一起，形成较高级别的大社区。因此，在这种情况下社区检测算法要求从低层次到高层次的顺序检测。传统方法一般遵守三条规则：第一，直接估计层次；第二，以自上而下的方式递归合并社区；第三，以自上而下的方式递归的划分社区；算法的性能受到大量参数或者网络密度要求的限制。但是，社区层次无法保留在深度学习模型中。随着高阶关系表示的发展，我们相信深度学习模型包括卷积网络可以促进分层社区检测的发展。

3）多层网络。现实中的网络很少有单层的，一般都是多层网络。多层网络是由多个相互依赖的图组成（在这里称为层），每一层代表不同类型实体之间的交互，跨层链接反映了实体之间的依赖关系。比如在多层社会网络中，节点可以代表个体，每一层的层内连接可表示为友谊、亲属关系或者同学等。因此，此类网络中的社区检测可以利用更多的信息来表达更好的结果。与单层网络中社区检测相比，多层网络社区检测算法仍然处于起步阶段，方法内容都比较少。多层社区检测方法简化过程是将多层网络的信息融合到一层，然后采用单层网络的社区检测算法。现有的方法是将低维表示中的多层信息扁平化，但是存在以下问题：交互数据类型之间的不同；每层中不同级别的稀疏性；跨层连接的可能性；层与层之间的可延展性。图卷积网络能够更有效地处理图结构数据，对多层网络的社区检测有更好的适用性。

4）异构网络。为了准确的描述现实情况，网络中会包含不同的信息，即异构信息。包含异构信息的网络就被称为异构网络。异构信息表达出现实世界不同实体之间的关系，比如演员和电影，物品和消费者等。由于其信息的复杂和重叠，不能直接使用同构网络的卷积神经网络社区检测建模方式，故异构网络的社区检测研究具有很大的挑战性。

5）网络异质性。网络异质性可以解释为连接属性属于不同社区或具有不同特征的现象。例如，欺诈者故意与普通用建立连接以免被发现。对于社区检测，跨社区连接的边界节点符合此网络属性。现有的卷积神经网络包括图卷积网络都无法准确地提供异质网络的社区检测。

6）拓扑不完全网络。现实场景中的关系并不总是可用的，这就导致了不完整的网络拓扑和孤立的子图。比如，蛋白质-蛋白质相互作用（protein-protein interaction，PPI）网络拓扑结构不完整，而检测所有的蛋白质之间的连接费用十分昂贵[15]。这种拓扑不完全网络在生物学上较为常见，而在这种不完全拓扑网络下划分社区意义重大。现有神经网络社区检测方法适用于拓扑完整的网络结构，针对拓扑不完全的网络社区检测方法非常有限。

5 结束语

本文从卷积网络入手，介绍了几种基于卷积神经网络和图卷积网络的社区检测算法，简要地说明了其算法的模型。卷积神经网络虽然比传统的非深度学习社区检测方法更具优势，但是在处理拓扑不完整结构、捕捉全局图特征困难等有局限性。图卷积网络结合传统社区检测算子弥补了卷积神经网络的局限性。针对现有卷积网络模型的优缺点，简要地阐述了研究的重点和未来的方向。下一步将会从以上几个方面入手，对图卷积网络的社区检测方法展开更深的研究。

参考文献：

[1] 高兵，宋敏，邹启杰，等.基于图嵌入和多标签传播的重叠社区检测算法[J].计算机应用研究，2024，41（5）：1428-1433.

[2] 胡永利，李鸥宵，孙艳丰.基于节点采样的子结构代表层次池化图卷积网络模型[J].北京工业大学学报，2024，50（6）：693-701.

[3] 高兵，宋敏，邹启杰，等.基于图嵌入和多标签传播的重叠社区检测算法[J].计算机应用研究，2024，41（5）：1428-1433.

[4] XIN X，WANG C K，YING X，et al.Deep community detection in topologically incomplete networks[J].Physica A：Statistical Mechanics and Its Applications，2017，469：342-352.

[5] SPERLÍ G.A deep learning based community detection approach[C]//Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing.Limassol Cyprus.ACM，2019：1107-1110.

[6] DE SANTO A，GALLI A，MOSCATO V，et al.A deep learning approach for semi-supervised community detection in Online Social Networks[J].Knowledge-Based Systems，2021，229：107345.

[7] 杨士杰，帅阳，韩超，等.基于非负矩阵分解的有向网络半监督社区检测[J].计算机系统应用，2024，33（1）：49-57.

[8] 宁懿昕.基于图神经网络的社区检测[D].南昌：江西科技师范大学，2022.

[9] WANG X F，LI J H，YANG L，et al.Unsupervised learning for community detection in attributed networks based on graph convolutional network[J].Neurocomputing，2021，456：147-155.

[10] SHCHUR O，GÜNNEMANN S.Overlapping community detection with graph neural networks[EB/OL].2019：1909.12201.https：//arxiv.org/abs/1909.12201v1

[11] HU R Q，PAN S R，LONG G D，et al.Going deep：graph convolutional ladder-shape networks[J].Proceedings of the AAAI Conference on Artificial Intelligence，2020，34（3）：2838-2845.

[12] LIU Y B，WANG X，WU S，et al.Independence promoted graph disentangled networks[J].Proceedings of the AAAI Conference on Artificial Intelligence，2020，34（4）：4916-4923.

[13] ZHANG X T，LIU H，LI Q M，et al.Attributed graph clustering via adaptive graph convolution[EB/OL].2019：1906.01210.https：//arxiv.org/abs/1906.01210v1

[14] ZHANG X T，LIU H，WU X M，et al.Spectral embedding network for attributed graph clustering[J].Neural Networks，2021，142：388-396.

[15] ZHANG T Q，XIONG Y，ZHANG J W，et al.CommDGI：community detection oriented deep graph infomax[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management.Virtual Event Ireland.ACM，2020：1843-1852.

[16] ZHAO H， YANG X， WANG Z， et al. Graph debiased contrastive learning with joint representation clustering[C]. IJCAI. 2021：3434-3440.

[17] ZHANG X T，LIU H，WU X M，et al.Spectral embedding network for attributed graph clustering[J].Neural Networks，2021，142：388-396.

[18] MORADAN A，DRAGANOV A，MOTTIN D，et al.UCoDe：unified community detection with graph convolutional networks[J].Machine Learning，2023，112（12）：5057-5080.

【通联编辑：王 力】