用于社区检测的深度学习：进展、挑战和机遇

摘要

由于社区代表了相似的观点、相似的功能、相似的目的等，因此社区检测在科学探究和数据分析中都是一个重要且极其有用的工具。 然而，随着深度学习技术以令人印象深刻的性能处理高维图数据的能力不断增强，传统的社区检测方法（例如谱聚类和统计推断）正在被淘汰。 因此，对通过深度学习进行社区检测的当前进展进行调查是及时的。 本文分为该领域的三大研究流——深度神经网络、深度图嵌入和图神经网络，总结了每个流中各种框架、模型和算法的贡献，以及当前尚未解决的挑战和未来的研究机会仍有待探索。

1简介

网络/图的两个基本元素是节点和边。 从连通性和密度的角度来看，社区被称为局部密集连通子图或节点集群Fortunato and Hric (2016)。 除了子图的内部凝聚力之外，还应该考虑它们之间的分离。 为此，图论提出了两个具体规则来确定这些节点和边中哪些构成社区：1）社区中的节点紧密连接； 2）不同社区的节点连接稀疏。 一个简单而流行的理解是，社区是内部连接多于外部连接的子图。

图1： 社交网络中社区检测的示例。 根据个体的紧密程度将网络划分为两个社区：社区$C_1$包含3个节点，社区$C_2$包含4个节点。

在现实世界中，社区中的节点可以共享共同的属性或提供类似的功能Fortunato (2010)，而找到这些共性是当今存在的几乎所有社区检测策略的战略关键。 社区检测，或更具体地说，基于相似特征或特征集的节点聚类，有助于我们理解网络的固有模式和功能。 例如，蛋白质-蛋白质相互作用（PPI）网络中的群落检测揭示了具有相似生物学功能的蛋白质Chen and Yuan (2006)。 在引文网络中，社区检测决定了研究主题Chen 和 Redner (2010) 的重要性、互连性和演变。 在企业网络中，通过研究公司线下的内部资源和线上的企业社交关系，可以将员工划分为社区张等人(2017)。 在Twitter、Facebook等社交网络中，具有共同兴趣或共同好友的用户可能是同一社区Yang等人(2013)的成员，如图1所示。

大多数传统的社区检测方法都是基于统计推断和传统的机器学习。 例如，用于检测社区并描述其形成方式的最广泛使用的方法之一是随机块模型Karrer 和 Newman (2011)。 然而，尽管这种策略过去很受欢迎，但面对当今复杂的数据集和复杂的社交场景，它却举步维艰。 在传统的机器学习中，检测社区通常被认为是图上的聚类问题。 但这些方法高度依赖于数据的特征。 例如，谱聚类 Ng 等人 (2002) 使用特征向量将节点划分为社区，在稀疏网络中表现不佳。

越来越清楚的是，网络规模和数据维度的不断增加需要更强大的技术来以可行的计算速度Rosvall 和 Bergstrom (2008) 维持有效和高效的性能。

至少目前，深度学习 LeCun 等人 (2015) 是解决方案。 通过深度学习，计算模型可以学习多个抽象级别的数据表示，这非常适合网络数据。 而且，它学习非线性特征的能力正在大大进步，并且在计算机视觉和自然语言处理等数据具有内在关系的广泛领域中取得了成功。 此外，多层深度神经网络可以降低数据的维度Zhang (2018)，从而拓宽了社区检测、节点分类和链路预测等网络分析任务的潜在范围。

在本次调查中，我们重点关注社区检测深度学习的新趋势。 我们的调查分为三个主要部分：

1. 我们回顾并评估了用于社区检测的各种深度学习方法的优势；

2. 我们从技术角度对最先进的研究进行总结和分类；和

3. 我们确定并讨论尚未解决的技术挑战，以及对未来工作有希望的机会的建议。

据我们所知，这是第一篇对用于社区检测的深度学习进行全面回顾的工作。 我们调查的大多数论文都发表在人工智能、机器学习、数据挖掘和网络服务领域最近召开的有影响力的国际会议上，例如，NIPS、ICLR、AAAI、IJCAI、KDD、ICDM、CIKM、ICDE 和 WWW。 高质量同行评审期刊上的文章也包括在内。

这项调查中的信息应直接支持研究人员和技术专家了解社区检测深度学习领域的过去、当前和未来趋势。

本次调查的其余部分组织如下。 2 部分阐明了社区检测的概念。 3部分解释了当今社区检测方法必须基于深度学习的原因。 4 节对基于深度学习的新型社区检测方法进行了调查。 5 部分讨论了该领域在近期进展中仍面临的挑战，并为学者和领域专家提供了未来研究机会的建议。 最后，第6部分对调查进行了总结。

2社区检测

在本文中，网络是一种特殊的图，它抽象了现实世界系统中的复杂关系，例如互联网、学术合作或社会团体。

定义1

（网络） 根据图论，加权网络表示为 $\mathrm{G}=(\mathrm{V},\mathrm{E},\mathrm{W})$，未加权网络表示为 $\mathrm{G}=(\mathrm{V},\mathrm{E})$，其中 $\mathrm{V}$ 和 $\mathrm{E}$ 表示分别表示节点和边的集合，$\mathrm{W}$表示$\mathrm{E}$在连接强度或容量方面的相应权重。 在未加权网络中，$\mathrm{W}$被视为1，可以从$\mathrm{G}$中删除。

子图$g\subseteq G$是保留原始网络结构的图的划分。 子图的划分遵循预先定义的规则，不同的规则可能会导致不同形式的子图。 社区是一种代表真实社会现象的子图。 换句话说，社区是具有共同特征的一群人或物体。

定义2

（社区） 社区是网络中的子图，其中节点共享密集连接。 稀疏连接的节点描绘了社区。 在这里，我们使用 $𝒞=\{{\mathrm{C}}_1,{\mathrm{C}}_2,\mathrm{\dots },{\mathrm{C}}_{\mathrm{k}}\}$ 表示从网络 $\mathrm{G}$ 中划分出的一组 $\mathrm{k}$ 社区，其中 ${\mathrm{C}}_{\mathrm{i}}$ 是 $\mathrm{i}$来自此网络分区的第一个社区。 聚类到社团${\mathrm{C}}_{\mathrm{i}}$中的节点$\mathrm{v}$满足社团内每个节点的内部度超过其外部度的条件。

因此，社区检测的目标是发现网络$G$中的社区$𝒞$。

图2： 用于社区检测的深度学习：进展、挑战和机遇。 本概述基于社区检测文献中有关卷积神经网络 (CNN)、自动编码器、生成对抗网络 (GAN)、深度非负矩阵分解 (NMF)、深度稀疏过滤 (SF)、社区嵌入、图神经网络（GNN）和图卷积网络（GCN）。 4 节中更详细地讨论了每种方法。 5 节更详细地讨论了每个挑战和相关机遇。

3为什么要通过深度学习进行检测？

与其他机器学习方法相比，用于社区检测的深度学习的明显优势是它能够对高维数据的特征表示进行编码Zhang (2018)。 对于图结构数据，这意味着利用网络的拓扑信息Fortunato (2010)。 深度学习模型还可以学习节点、邻域和子图的模式Wu等人(2020)。 此外，它们对与大规模图形数据相关的稀疏性具有更强的弹性。 最后，在许多现实场景中，考虑到大多数节点是未标记的，并且数据中的社区几乎没有先验知识，深度学习是无监督学习任务的最佳选择 Tia​​n 等人 (2014 ）。

除了简单地检查网络拓扑来检测社区之外，一些策略还探索语义描述作为数据中的节点特征。 传统的社区检测方法主要基于邻接矩阵和节点属性矩阵 Yang 等人 (2013)；他等人(2017). 然而，深度学习可以创建更强大的节点属性和社区结构表示。 为此，最近的研究表明了深度学习社区检测的新方向，例如Xie等人(2018)中的深度学习模型；巴蒂亚和拉尼 (2019)； Sun 等人 (2019) 以及基于社区属性改进的深度学习模型 Zhang 等人 (2018)；涂等人(2019)。

这些研究让我们了解深度学习可能给社区检测的未来带来什么：

• 性能改进；

• 基于更多、更丰富的特征进行检测的能力；

• 基于网络拓扑和节点属性进行检测的能力，以获得更稳健、性能更好的模型；和

• 检测更大规模网络中更复杂结构的能力。

4 利用深度学习进行社区检测

本节提供了社区检测深度学习最新研究进展的技术概述。 每个小节涵盖三大类方法之一，即深度神经网络、深度图嵌入和图神经网络。 在每个小节中，我们总结了最有影响力的方法以及各种框架、模型和算法的贡献。 图 2 概述了这些方法及其相应的挑战。

4.1基于深度神经网络的社区检测

深度神经网络具有建模和捕获综合关系的天然优势。 社区检测领域最流行的三种深度神经网络模型是卷积神经网络（CNN）、自动编码器和生成对抗网络（GAN）。 下面依次总结每一项。

4.1.1 基于CNN的方法

CNN 的两个关键组成部分是卷积运算和卷积层上的池化运算。 卷积运算使用卷积核来降低计算成本。 随后将池化操作应用于特征映射，以确保 CNN 的鲁棒性。

利用 CNN 的进步，Xin 等人 (2017) 设计了一种新颖的 CNN 模型来检测拓扑不完整网络中的社区，从现实世界网络中观察到的网络中存在一些边缘缺失。 Sperlí (2019) 在 CNN 框架中包含稀疏矩阵卷积，专门用于处理与邻接矩阵相关的高度稀疏表示。

4.1.2 基于自动编码器的方法

堆叠式自动编码器是一种非常强大的深度神经网络模型，用于社区检测Yang 等人 (2016)。

将自动编码器应用于社区检测的灵感来自于发现自动编码器和谱聚类在谱矩阵的低维近似方面具有相似的框架Cao等人(2018b)。 Bhatia 和 Rani (2018) 设计的方法着眼于网络拓扑，通过基于随机游走的个性化 PageRank 来学习节点集群，并通过优化社区结构的模块化来微调检测。 为了利用节点属性信息，Cao等人(2018b)提出了一种堆叠式自动编码器，通过网络拓扑和节点属性结合社区检测，增强隐藏层的泛化能力的深度神经网络。 为了进一步解决网络拓扑和节点属性之间的匹配问题，Cao等人(2018a)通过引入自适应参数作为匹配的权衡控制，开发了一种图正则化自动编码器方法。

为了避免预先设定社区数量，分层堆叠自动编码器可以基于网络结构Bhatia and Rani (2018)有效地找到社区中心。 此外，这种自动选择机制确保模型严格根据社区标准分配节点。 自从这一发现以来，越来越多的方法自适应地学习社区结构，而不是预先定义一个数字。 例如，Choong 等人 (2018) 引入了混合高斯模型来从社区结构中捕获高阶模式，并对观察到的网络的生成过程进行建模以检测社区。

对于连接带有正号和负号的网络，它们被命名为符号网络Xu等人(2019)。 为了处理边缘上的签名信息，半监督堆叠自动编码器重建邻接矩阵来表示签名网络，从而进一步学习深度网络嵌入Shen and Chung (2018)。

4.1.3 基于 GAN 的方法

生成对抗网络（GAN）涉及两个相互竞争的深度神经网络，从而可以快速调整训练精度。 这些方法通常在无人监督的情况下运行，生成与训练集具有相同统计数据的新数据。 GAN 已被探索用于图形表示任务，非常有效Wang 等人 (2019)。

Jia等人(2019)认为传统的基于图聚类的社区检测方法无法处理社区的密集重叠，即一个节点可能属于多个社区。 为此，他们提出了一种新颖的模型CommunityGAN，联合解决基于GAN的重叠社区检测和图表示学习。 更重要的是，与没有特定含义的一般图节点表示相比，CommunityGAN 具有表示节点对社区的成员资格强度的能力。

4.2 基于深度图嵌入的社区检测

深度图嵌入是一种将网络中的节点映射到低维向量空间的技术，同时在表示中保存尽可能多的结构信息Xue等人(2019)。 图嵌入方法特别适用于基于网络分析的机器学习任务，例如，链接预测、节点分类和节点聚类，因为它们可以引用表示中的潜在特征，而不是搜索网络。 之后，聚类方法，例如$k$-means，可以支持社区检测。

4.2.1 基于深度 NMF 的方法

非负矩阵分解（NMF）是一组计算算法，它将一个矩阵分解为两个矩阵，并且三个矩阵都没有负元素。 对于社区检测，NMF 方法通过最小化进一步聚类任务的误差函数，将网络的邻接矩阵近似为两个因式分解矩阵的乘积。

Ye等人(2018)提出了一种新颖的深度NMF模型，该模型通过在深度学习过程中将社区结构映射回原始网络结构来提高性能。 通过添加节点属性并形成属性图，基于深度NMF的社区检测只需要邻接矩阵和节点属性矩阵进行分解。 此外，Li等人(2018)结合深度特征学习和深度网络嵌入，利用NMF进行基于节点属性和社区嵌入的属性社区检测。

4.2.2 基于深度 SF 的方法

嵌入可以对成对关系的输入进行编码，以避免搜索稀疏邻接矩阵，因此稀疏过滤（SF）是一种有效的深度特征学习算法，只需要一个超参数来处理高维输入Ngiam等人（2011） 。 Xie 等人 (2018) 提出了一种通过深度稀疏过滤来发现网络社区的高效网络表示方法，该方法特别适用于大规模网络。 无监督深度学习算法提取网络特征，然后用于划分网络。

4.2.3 基于社区嵌入的方法

传统上，图嵌入侧重于单个节点，但网络中的社区反映了高阶邻近性，例如相似的观点和行为。 这是图嵌入的一个重要但很大程度上尚未开发的领域，专注于嵌入社区，其目标是学习低维空间中社区的节点分布。 Cavallari 等人 (2017) 研究了这个想法，认为这种新颖且不平凡的策略可能有益于社区检测。 例如，通过过渡图嵌入方法，可以利用节点分布来保留网络结构，从而反过来改进社区检测。 Zhang等人(2018)提出了一种社区保留网络嵌入方法来学习网络表示。 他们在社区检测方面的表现证明了其优越性。 此外，Tu等人(2019)提出了一种新颖的图嵌入模型，该模型同时学习节点和社区的嵌入，其优化过程在社区分配和节点嵌入之间交替，而不是同时求解两项任务。

4.3基于图神经网络的社区检测

GNN 是图挖掘和深度学习的技术融合，它们最近的快速发展表明它们有能力建模和捕获基于图的数据中的复杂关系。 例如，Chen 等人 (2019) 中用于监督社区检测的 GNN 引入了非回溯算子来定义边缘邻接。 这种方法不仅是提高学习性能的可行方法，而且操作员选择也方便。

图卷积网络 (GCN) 继承了 CNN 的快速学习能力，并通过集成考虑网络中实体概率分布的概率模型进一步改进了这一优势。 例如，Jin 等人 (2019) 将马尔可夫随机场与语义信息的归因网络相结合来支持半监督学习，而 Shchur 和 Gunnemann (2019) 则集成了具有 GCN 的伯努利-泊松概率模型，用于重叠社区检测，以便卷积层可以识别复杂的网络模式。

5挑战与机遇

尽管近年来，特别是过去五年，我们见证了深度学习在社区检测方面的快速发展，但仍然存在需要更好解决的问题和尚未解决的挑战。 与我们知识中的大多数差距一样，这些问题为未来的研究提供了机会。 在本节中，我们讨论社区面临的七大挑战，首先是社区检测中最长期存在的问题。

5.1 挑战一：未知数量的社区

需要提前知道社区数量所带来的挑战已经存在很长时间了，尽管提出了一些解决方案，但这个问题仍然没有得到完全解决。 在机器学习中，社区检测通常被视为无监督的聚类任务，因为从现实世界网络中提取的大多数数据没有标签。 这导致了第 22 条军规：需要对数据进行标记以确定社区的数量，但在对数据进行标记之前需要知道社区的数量。 深度学习方法通​​过根据一个或多个潜在空间中的相似性对节点进行聚类，在一定程度上解决了这一问题。 然而，聚类算法仍然需要提前知道最终的聚类数量。

机会：目前，一个有效的解决方案是通过分析网络拓扑来计算社区数量，例如基于随机游走的Bhatia and Rani (2018, 2019)基于PageRank的个性化。 然而，这种方法不能保证网络中的每个节点都被分配到一个社区。 因此，尚未找到该问题的完整且完整的解决方案。

5.2 挑战二：分层网络

分层网络由分层网络组成，每层网络共享特定的功能。 因此，社区检测策略必须能够提取分层表示。 其中涉及的挑战包括区分不同的关系类型（例如水平和垂直），以及管理不同层中不同程度的稀疏性。

机遇:Song 和 Thiagarajan (2018) 提出了一种多层 DeepWalk，通过创建层间边缘来利用不同层之间的依赖关系，同时保留层次结构。 它学习每一层中每个节点的表示，并通过细化策略进行微调。 另一种可能的解决方案是同时优化适用于所有层的通用表示和保留特定于层的网络结构的局部表示。 此外，该方案相对于层次结构中的层数的可扩展性是值得怀疑的，在设计新颖的解决方案时应考虑这一点。 此外，需要新的模型来区分分层网络中不同类型的连接。 因此，在我们拥有用于检测分层网络社区的深度学习方法之前，还有很多工作要做。

5.3挑战三：网络异构性

网络异构性是指网络包含明显不同类型的实体和关系，这意味着用于同质网络的策略不一定有效。 特别是，在模型和算法的设计中需要解决与每种类型的实体相关的不同概率分布。

机遇：迄今为止，很少有深度学习方法考虑网络异构性。 在我们调查的工作中，Chang 等人 (2015) 通过非线性嵌入函数来解决这个问题，以捕获异构网络实体之间的复杂交互。 然而，他们的方法忽略了节点之间关系的不同语义Fu等人(2017)。 异构网络中社区检测的未来机会可能包括：1）深度图嵌入模型和支持算法； 2）具有新颖训练过程的特定深度学习模型，用于学习隐藏层内的异构图属性； 3）可以利用节点之间不同类型关系的新颖模型。

5.4 挑战四：边上的签名信息

许多现实世界的网络都有代表积极或消极关系的符号边。 挑战在于需要以不同的方式对待这些关系。

机会：一种可能的解决方案是通过设计随机游走过程来合并正边缘和负边缘。 Hu 等人 (2019) 遵循这一思想，开发了一种基于词嵌入的稀疏图嵌入模型。 但对于一些小型的现实世界签名网络，他们的方法的性能不如基线谱方法。 另一种可能的解决方案是重建带符号网络的邻接矩阵表示。 然而，这引发了其他问题，因为在现实世界中，邻接连接绝大多数是正的。 Shen 和 Chung (2018) 施加了惩罚，以确保他们的堆叠自动编码器模型更多地关注于重建较稀有的负边缘而不是丰富的正边缘。 然而，如果事先不了解社区中的大多数关系（这在许多情况下都是现实的），这种方法就行不通。 因此，仍然需要在签名网络中进行无监督社区检测的有效方法。

5.5 挑战五：社区嵌入

社区嵌入旨在创建社区的表示，而不是每个单独节点的表示Cavallari 等人 (2017)。 因此，焦点转移到社区感知的高阶邻近度，而不是与节点邻域相关的一阶或二阶邻近度。 这是一个新兴的研究领域，需要克服三个主要挑战：1）计算成本高； 2）节点与社区结构之间的关系评估； 3）应用深度学习模型时的其他问题，例如跨社区的分布变化。

机会：从我们的调查中，我们直觉地发现了一种通过自动选择节点和/或社区上的表示模块来支持社区嵌入的智能方法。 为此，我们建议以下研究目标：1）探索如何将社区嵌入整合到深度学习模型中； 2）确定如何直接嵌入社区结构以获得一系列好处，例如快速计算； 3）设计一种优化集成深度社区检测学习模型中超参数的方法。

5.6 挑战六：网络动态

动态变化会影响网络拓扑或节点属性，每个属性都必须以自己的方式处理。 拓扑变化，例如添加或删除节点或边，不仅会引起局部社区的变化，还会导致整个网络的全局变化Liu 等人 (2020)。 对于动态网络，深度学习模型需要通过一系列快照进行重新训练。 动态网络时间属性的技术挑战在于动态的深层特征提取。

机遇：用于检测具有动态空间和时间属性的社区的深度学习方法尚未得到很好的发展。 因此，未来的研究方向包括：1）检测和识别社区的空间变化； 2）学习嵌入时间特征和社区结构信息的深层模式； 3）开发一种统一的深度学习方法用于社区检测，可以同时处理空间和时间特征。

5.7挑战七：大规模网络

如今，大规模网络可以包含数百万个节点、边缘和结构模式，并且也可以是高度动态的，正如 Facebook 和 Twitter 等网络所证明的那样。 这提出了在真正的大规模社区检测成为现实之前需要解决的许多发展领域。 例如，大规模网络可能有其固有的规模特征，如社会网络中的无规模（即，幂律程度分布）。 这种特殊的分布会影响深度学习在社区检测中的性能。 可扩展性似乎是使深度学习能够在大规模网络环境中检测社区的另一个关键问题。 不断变化的网络类型进一步增加了检测难度。 总体而言，大规模网络中的深度社区检测涉及上述所有六个挑战以及可扩展学习的挑战。

机会：为了充分利用大规模网络中的丰富信息，需要具有更低计算复杂度和更大灵活性的新型无监督聚类算法。 分布式计算架构在大规模机器学习社区中很流行。 因此，一个可能的方向是开发一种鲁棒的深度学习检测方法，以实现高性能的协作计算。 另一方面，对于高维邻接矩阵，深度学习中常用的降维关键策略(即矩阵低秩逼近）不适用于大规模网络，并且即使是目前的分布式计算解决方案仍然过于昂贵。 因此，对新颖的深度学习框架、模型和算法的需求很高。 作为社区检测中最大的挑战，这些框架需要在精度和速度方面远远超过当前的基准。

6 结论

如今，我们所有人都在由许多社区组成的错综复杂的系统中生活、工作和娱乐。 同样，随着我们对世界的了解不断增长，我们发现物体具有不止一种功能，思想有不止一种目的，所有事物之间的相互联系比我们之前想象的要大得多。 检测这些群落及其固有的功能和特征有助于我们全面了解周围环境，发现复杂的关系来描述和解释社会现象。

传统的社区检测方法通常依赖于统计推断和传统的机器学习方法，例如随机块模型和谱聚类。 但深度学习的进步催生了社区检测策略，这些策略具有更强大的处理高维图数据的能力，并且性能令人印象深刻。

在本次调查中，我们回顾了三种广泛的深度学习方法的技术趋势以及模型和算法开发的当前状态，以检测各种场景中的社区。 我们还确定了通过深度学习进行社区检测以完全成熟需要克服的七个重要挑战。

在某种程度上，这些挑战可以作为下一代社区检测的指南。 尽管许多研究人员正在积极致力于解决这些问题，但我们指出仍然存在许多机会来为这一不断发展的重要领域的发展做出贡献。

致谢

这项工作部分得到 ARC DECRA 的资助 DE200100964 的支持，部分得到 2018 年 MQ 和 Data61 之间的合作项目的支持，部分得到 MQEPS 的资助 96804590 的支持，部分得到国家自然科学基金委的资助 61872360 和 61976162 的支持，以及青年创新促进会的支持CAS 协会资助 2017210，部分由 NSF 资助 III-1526499、III-1763325、III-1909323 和 CNS-1930941。 F. Liu 和 S. Xu 对这项工作做出了同等贡献。