近年来，深度学习被广泛应用在图像识别^[1]、语音识别^[2]、自然语言处理^[3]等领域，而对于在复杂网络如社交网络、电信网络、蛋白质相互作用网络以及道路网络等方面的应用，还有很大的研究空间. 目前，研究者将深度学习的思想应用到图论^[4-5]上，使采用深度学习的方法处理图结构数据并挖掘复杂网络社团结构成为可能.

传统的复杂网络社团发现方法有谱聚类方法^[6-7]、标签传播方法^[8-9]、模块度优化方法^[10-11]等，这些方法在基于大数据的复杂性科学研究上效果较差. 文献[12]结合随机块模型和图神经网络，提出了一种基于图神经网络的社团发现方法，为复杂网络社团发现的研究提供了新思路. 大多数图神经网络模型都有一个通用的架构，这些模型统称为图卷积网络. 之所以称之为卷积，是因为滤波器参数通常在图中所有位置共享^[13]. 针对图结构数据，目前很多研究者提出了不同的图卷积神经网络. Yang等^[14]通过应用对称拉普拉斯模块作为图的有效嵌入机制提出了图卷积神经网络模型，然而该方法限制了其光谱近似的表达力，并且限制了在稀疏图中的应用. Kipf等^[15]根据频谱图卷积使用一阶近似简化计算的方法，直接操作于图结构数据的网络模型，提出了一种简单有效的层式传播方法，并验证了图结构神经网络模型可以处理图数据中节点半监督学习问题，但是在训练时由于跨层的递归邻域扩展，运算时间和内存消耗很多. 此外，Li等^[16]提出自适应图卷积神经网络，输入可以是多种图结构的原始数据，该网络不使用共享频谱核，而是给批量中的每个样本一个特定的图拉普拉斯矩阵，客观描述其独特拓扑结构. 根据其独特的图拓扑，定制化图拉普拉斯算子将带来定制化的频谱滤波器. 但是，该网络在训练时效率较低，并且无法扩展到大规模数据集上.

为了解决以上问题，本文提出一种基于重要性抽样的图卷积社团发现方法，主要包括：图结构的内积操作、图的粗粒化和池化、隐层特征提取与分类等步骤.

本研究通过对复杂网络进行处理，采用卷积神经网络对图进行粗粒化和池化操作，提取特征后进行分类，从而实现复杂网络的社团发现. 在训练网络时，通过对样本的重要性抽样来减少梯度计算的时间.

通常，复杂网络可以抽象为图 $G = (V,E,W)$ 模型，其中 $V = \{ {v_i},i = 1,2,\cdots,n\} $ 表示网络节点的集合； $E = \{ {e_i},i = 1,2,\cdots,m\} $ 表示网络中边的集合，且 $({v_i},{v_j}) \in E$ 表示复杂网络中的关系； ${ W} \in {{ R}^{N \times N}}$ 为的邻接权重矩阵. 对于每个图，均存在一个邻接矩阵A；当节点 ${v_i}$ 与 ${v_j}$ 有连边时， ${A_{ij}} = 1$；否则， ${A_{ij}} = 0$. 对图中的每个节点分配一个唯一标签，表示社团，则社团结构为一个标签向量 $s:V \to $ $ \{ 1,K\} $.

图上的神经网络模型是机器学习研究的一个热点领域，本研究使用的图卷积网络是图上神经网络中的一种. 在图像上，卷积操作是使用一些固定大小的卷积核来扫描输入的图像. 将图像上的卷积操作推广到任意结构的图结构上时，同样可以定义任何一个节点的邻域与一系列权重矩阵，这是图卷积网络的基本思想. 但是，与图像不同的是，在普通的图结构上，如果使用邻接矩阵来定义邻域，每个节点的邻域中节点的数量并不是固定的，而图像上像素附近的像素总是固定的. 因此，很难确定需要使用的卷积核的参数维度以及通过排列权重矩阵与邻域内的节点来进行的内积运算. 本研究将内积操作变成使用同一个向量与所有邻域内节点上的特征向量计算内积，并将结果求均值. 这样操作可以使得卷积核的参数确定为一个固定长度的向量，而且不需要考虑邻域内节点的顺序.

池化操作需要为图上的节点选择适当的邻域，使相似的节点能够聚集在一起，相当于保留局部几何结构图的多尺度聚类. 然而图的聚类是一个难题，并且必须使用近似值. 虽然目前有许多聚类技术，如谱聚类方法，但是为了使每个层产生一个对应于不同的数据域的粗粒化图，需要采用多层次聚类算法. 此外，还需要通过图的大小控制图的粗粒化和池化. 本研究采用Graclus多层聚类算法的粗化阶段^[17]进行图的粗粒化，并采用归一化剪切对图进行归一化处理.

Graclus使用贪心算法使图粗粒化，其主要过程包括：在每个粗化层选择一个节点i，若节点i的所有邻域内的节点都已标记，则标记i，找到下一个未标记的节点；若节点i的邻域内存在未标记的j，使得 ${{e(i,j)}} \times {{(w}}_{{{(i)}}}^{{{ - 1}}}{{ + w}}_{{{(j)}}}^{{{ - 1}}}{{ )}}$ 最大化（ ${e_{(i,j)}}$ 为节点i，j之间的权重， $w(i)$、 $w(j)$ 分别为节点i、j的权值），即使局部归一化剪切的权值最大化，然后标记这2个节点，并将其权值之和设置为归一化剪切的权值. 重复此过程，直到所有节点都被遍历. 该过程实现了将大规模图缩小到规模合适的图，并保持原图中节点的重要特征和性质，有效实现了图的粗粒化.

由于以上粗粒化方法得到的图中节点是以任意方式排列，会影响池化操作的有效性，从而影响社团发现的准确性，需要对匹配好的节点重新排序，使图实现有效池化. 图的粗粒化与池化举例说明如图1所示. 其中，图模型A的节点数为8、边数为12，且节点是以任意方式排列，首先通过Graclus多层聚类算法的粗化阶段以及大小为4的池化核，如图模型A中标记为0和1的节点，在粗化后得到标记为0的节点，以此类推，图模型A被缩小为粗粒化图B，在图B的基础上继续进行粗化，得到粗粒化图C. 此外，将节点进行重新排序，如有效池化图D所示. 该过程实现了将一个节点数为8的图模型缩小至规模为3的图模型.

本研究提出的基于重要性抽样的图卷积网络社团发现方法，基本框架如图2所示. 首先将初始化的节点输入到卷积层，进行粗粒化和池化操作，提取图模型的隐层特征，再将提取的特征进行分类，发现复杂网络中的社团结构. 具体过程如下.

1）初始化网络节点标签，一些节点标记，其他节点不标记；

2)输入初始化的节点到图卷积层，使用Rectified Liner Uints（ReLU）激活函数，则节点的传播规则如下：

(1) ${{{H}}^{(l + 1)}} = {\mathop{\rm Re}\nolimits} {\rm LU}\;\;({{\tilde{ D}}^{ - \frac{1}{2}}}{\tilde{ A}}{{\tilde{ D}}^{ - \frac{1}{2}}}{{{H}}^{(l)}}{{{W}}^{(l)}}). $

式中： $\tilde {{A}} = {{A}} + {{{I}}_N}$ 为图模型G的邻接矩阵， ${I_N}$ 为特征矩阵， ${{{D}}_{ii}} = \sum_i {{{{A}}_{ij}}} $ 为度矩阵， ${{{W}}^{(l)}}$ 为第l层的权重矩阵， ${{{H}}^{(l)}} \in {{{R}}^{N \times D}}$ 为在第l层的激活矩阵，N为矩阵维数，且 ${{{H}}^{(0)}} = {{X}}$，X为节点集V的特征向量；

3）对图模型中的节点按照1.2节的方法进行粗粒化和池化操作，将未标记的节点i与其相邻的无标签节点j进行局部归一化，然后把2个相邻的节点进行标记，将粗粒化后节点的权重作为这2个节点的权重之和，重复此过程直到所有的节点都被粗粒化. 对粗粒化后的节点进行池化操作，使节点重新排列，相似的节点则聚集在一起，提取出图模型结构的隐层特征；

4）将提取的特征输入到全连接层进行处理，将结果输入到softmax分类器，模型如下：

(2) ${{Z}} = f({{X}},{{A}}) = {\rm soft}\max \;\;({\tilde{ A}}\operatorname{Re} {\rm LU}({{AX}}{{{W}}^{{{(0)}}}}{{{W}}^{{{(l)}}}})). $

式中： ${{{W}}^{(0)}} \in {{{R}}^{N \times N}}$ 为输入层的权重矩阵， ${{{W}} ^{(l)}}\in{{{R}}^{N \times N}} $ 为输出层的权重矩阵，softmax激活函数定义如下：

(3) ${\rm soft}\max \;({x_i}) = {\left[ {{{\sum} _i}\exp \;({x_i})} \right]^{ - 1}}\exp \;{({x_i})}. $

5）输出标签节点，标签节点的损失函数为

(4) ${\rm Loss} = - \sum\limits_{l \in {y_{\rm L}}} {\sum\limits_{f = 1}\; {{{{Y}}_{{{f}}{{l}}}}} } \ln \;{{{Z}}_{{{fl}}}}. $

式中： ${y_{\rm{L}}}$ 为标签节点集合， ${{{Y}}_{{{f}}{{l}}}}$ 为标签矩阵， ${{{Z}}_{{{f}}{{l}}}}$ 为softmax分类器的输出. 将具有相同标签的节点为同一个社团.

使用随机梯度下降法 (stochastic gradient descent, SGD)训练并优化网络模型时，图卷积网络和许多标准神经网络架构之间的一个显著差异是样本损失缺乏独立性. SGD及其批量泛化之类的训练算法是基于相对独立数据样本的损失函数的累加性质来设计的. 对于任意图结构，每个节点都与其所有邻节点进行卷积，因此定义一个有效的样本梯度计算是有必要的.

具体而言，原始SGD的损失是关于数据分布D的某些函数g的期望，用公式可表示为

(5) $L = {E_{x \sim D}}[g(p,x)]. $

式中：p为待优化的模型参数. 通常，数据分布是未知的，需要通过访问n个样本最小化经验损失，最小化经验损失可表示为

(6) ${L_{{\rm{emp}}}} = \frac{1}{n}\sum\limits_{i = 1}^n\;\; {g(p,{x_i})} . $

在SGD的每一步中，若假设 $\nabla g$ 为无偏差样本，则梯度近似为 $\nabla g(p,{x_i})$.

与原始SGD不同，在访问样本时，本研究设计重要性抽样法对样本进行抽取. 通过改变给定样本空间的概率分布进行抽样，提高对重要区域的抽样权重，从而使对计算结果有重要作用的样本出现的概率更大，以便减少方差，提高抽样效率和估计精度. 具体过程如下：

1）选取重要性函数g（x），从g（x）中抽取样本X₁，X₂，···，X_N；

2）计算样本的估计值 $\hat \theta $；

3）重复以上过程m次，得到m个估计 ${\hat \theta _1},{\hat \theta _{2,}}\cdots, $ ${\hat \theta _m}$；

4）用样本方差m⁻¹$\sum\nolimits_{{{i = 1}}}^{{m}} $估计 $\hat \theta $ 的方差.

采用该方法定义并计算样本的损失和梯度，计算比较简单，即使所要解决的问题复杂度很高，也不会影响计算精度和收敛速度. 本研究所采用的重要性函数g（x）是指采样的样本所在社团占总样本的比例.

为了验证本研究提出方法的有效性，采用社会网络数据集^[18]：Zachary karate club美国大学空手道俱乐部、College Football美国大学生足球联赛网络，引文网络数据集^[14]：Cora、Citeseer和Pubmed，大规模数据知识图谱NELL^[14]以及社交新闻网络Reddit ^[19]进行验证. 社会网络数据集Zachary karate club节点表示俱乐部中的成员，边表示成员之间存在的友谊关系，College Football节点代表足球队，2个节点之间的边表示2支球队之间进行过1场比赛，参赛的115支大学生代表队被分为12个联盟. 引文网络数据集包含作者、引文等信息，每个节点表示文档，边表示文档之间的引用关系，特征表示描述文档的词汇数，社团表示文档的主题. Reddit是一个大型的在线论坛，用户可以在不同的主题社区发布和评论内容，节点表示论坛上的帖子，边表示同1个用户对2个帖子都发表过评论，社团表示帖子所在的社区，特征表示描述帖子的词汇. 数据的统计信息如表1所示.

本研究采用如式（2）所示的网络模型进行训练，对于实验数据集（节点数）的设置如表2所示. 其中Karate以及Footballs数据集由于数据量较少，分别随机选择适量的节点作为训练集和验证集，剩余的节点作为测试集；引文网络每个文档都有1个类标签，对于每个数据集选用每个主题中的20个标签进行训练，随机选择500个节点作为验证集，1 000个节点作为测试集；对于NELL以及Reddit数据集，随机选择训练集、验证集以及测试集节点. 使用引文网络数据集Cora进行超参数优化，Citeseer和Pubmed数据集使用与Cora数据集相同的超参数，当训练多个卷积层时，采用反向传播算法计算其梯度.

本研究实验平台的设置包括：Intel（R）Core（TM）i5-4460 CPU @ 3.20 GHz处理器、8 GB内存、Ubuntu16.4下的Linux操作系统以及JDK1.8，并使用TensorFlow深度学习框架和Python编程语言实现.

为了验证本文方法的网络深度对准确性的影响，在本实验中，采用引文网络数据集，通过设置不同的网络层数，探讨其对社团发现准确性的影响. 训练网络时设置的迭代次数为300，采用Adam优化学习算法^[20]，学习速率为0.01. 当交叉验证损失在连续10次迭代后不再下降时，停止训练. 其他超参数设置如下: 设置第一层和最后一层随机丢弃率（dropout rate）为0.5，第一层L2正则化的权重衰减系数为 $5 \times {10^{ - 4}}$，每个隐藏层的单元数为16，学习率为0.01. 对于引文网络数据集Cora、Citeseer和Pubmed，网络不同深度的社团检测性能如图3所示，同时对比了在隐藏层之间使用残差连接^[21]的效果. 图3中，L为网络层数；R_acc为社团检测的准确性，Res代表残差连接层.

由图3可知，对于引文网络Cora、Citeseer和Pubmed数据集，使用2层或3层网络社团发现的准确性效果最佳. 同时发现，当网络超过7层时，不使用残差连接的训练结果较差，因为每增加一层，每个节点的有效邻域也会随之增加. 此外，随着网络的深度增加，参数的数量也会增加，会出现过拟合的问题.

为了验证本研究提出方法的准确率，采用社会网络、引文网络、知识图谱以及社交新闻网络数据集进行实验，超参数设置主要有：随机丢弃率为0.5，L2正规化的权重衰减系数为 $5 \times {10^{ - 4}}$，隐层单元数为16；大规模数据集NELL和Reddit超参数设置为：随机丢弃率为0.5，L2归一化系数为 $1 \times {10^{ - 6}}$，隐层单元数为128. 使用dropout和L2归一化的目的是防止训练时过拟合. 当使用3层网络时，采用所提方法得到的测试结果的准确性与文献[14]和[15]对比如表3所示.

由表3可知，在准确性方面，对于节点数较少的社会网络数据集Karate和Footballs，测试的准确率分别为88. 9%、93.3%. 与文献[14]相比，所提方法的准确性显著提高，引文网络数据集Cora的准确率提高了6.0%，Citeseer的准确率提高了8.4%，Pubmed的准确率提高了2.3%；知识图谱数据集NELL的准确率提高了6.4%. 与文献[15]相比，所提方法的引文网络数据集Cora、Citeseer、Pubmed的准确率分别提高了0.2%、2.8%、3.3%；知识图谱数据集NELL的准确率提高了7.6%. 并且所提方法可扩展到大规模数据集Reddit，准确性高达93%.

此外，为了验证训练样本对测试结果准确性的影响，通过Cora数据集按照每类主题增加训练样本进行验证，验证集与测试集的节点数不变，分别为500和1 000. 实验结果如表4所示，其中N_E为训练集中每类主题的节点数，N_T为训练集的总节点数.

由表4可知，当每类主题训练的节点数由5个逐渐增加到40个时，测试结果的准确性明显提高；然而当每类主题训练的节点数由80个增加到100个时，测试结果的准确性提高不明显. 这主要是由于Cora数据集中每类主题的分布不均匀，当按每类主题数增加训练节点时，虽然训练样本的总节点数增加，但是每类训练样本占该类总节点数的比例却不同. 因此，按数据集中每类的分布情况选择训练样本会得到更好的效果.

为了验证本文提出方法的计算效率，采用社会网络、引文网络、知识图谱以及社交新闻网络数据集进行实验，超参数设置与2.2.2节相同，实验结果如表5所示.

由表5可知，在计算耗时方面，与文献[14]的方法对比，所提方法的计算耗时明显下降，特别是对于大数据集NELL，所提方法的计算效率明显提高；与文献[15]相比，除了Pubmed数据集之外，采用所提方法的计算耗时均有所下降，并且适用于更大规模的数据集. 由此可知，本文提出的方法在保证社团发现准确性较高的情况下，计算效率也显著提高，但是对于大数据的计算效率仍然有待提高.

为了验证本文方法训练时的计算占用内存，使用数据集Cora、Pubmed以及Reddit进行实验. 实验结果如图4所示. 可知，与文献[14]和[15]对比，所提方法采用了重要性抽样，因此在遍历样本时，直接采样的是图的节点而不是节点的邻域，从而减少了计算占用空间. 对于引文网络数据集，采用本文方法计算时内存空间减少了一半以上，并且适用于大规模数据集.

本研究的重要性抽样是蒙特卡罗方法中方差缩减技术中的一种，目的是在采用随机梯度下降法训练网络时，提高抽样效率和估计精度，因此实验中没有节点重要性的保存.

本研究提出了基于重要性抽样的图卷积社团发现方法，将复杂网络转化为易于处理的图结构数据，并且通过卷积层对图的粗粒化和池化操作，提高了社团发现的准确性. 在采用梯度下降法训练网络时，使用重要性抽样改变样本的分布来缩减方差，节省了梯度计算时间. 与文献[14]和[15]相比，提出的方法使用了不同数据集，在提高社团发现准确性的情况下，计算效率也有所提高，并且适用于大规模社交新闻网络数据集；同时，计算时占用的内存空间也明显减少. 随着网络中节点数目的增加，采用本研究方法可以得到更好的效果，未来进一步研究工作需要提升大规模数据的计算效率.