图网络层级信息挖掘分类算法综述

魏文超，蔺广逢，廖开阳，康晓兵，赵凡

西安理工大学印刷包装与数字媒体学院，西安 710048

0 引 言

深度学习(deep learning)作为机器学习的一个研究分支发展迅速(Zhou等，2018)，其将现实世界中的每个概念都表现为更加抽象的概念来定义，并通过神经网络提取样本特征。深度学习在多领域的成功归功于计算资源的快速发展、大量训练数据的收集，以及从欧氏数据(具有很好的平移不变性(Ali等，1990)的数据)中提取潜在表征的有效性。例如，卷积神经网络(convolutional neural network，CNN)(Krizhevsky等，2012)可以利用平移不变性、局部连通性和图像数据语意合成性提取与整个数据集共享的局部有意义的特征，用于各种图像分析任务。深度神经网络的最新进展推进了模式识别和数据挖掘领域的研究。目标检测、机器翻译和语音识别等许多机器学习任务曾高度依赖手工特征提取信息特征集合，但多种端到端深度学习方式，即卷积神经网络(Krizhevsky等，2012)、长短期记忆网络(long short-term memory，LSTM)(Hochreiter等，1997)和自编码器(AutoEncoders)(Vincent等，2010)改变了这种状况。

尽管深度学习在欧几里得数据中取得了很大成功，但非欧氏数据(不具有平移不变性的数据)在实际中应用更广泛。例如，在电子商务领域，一个基于图的学习系统能够利用用户与产品之间的交互实现高度精准的推荐。在化学领域，分子被建模为图，新药研发需要测定其生物活性。在引文网络中，文章之间通过引用关系互相连接，需要将它们分成不同类别的文献(Wu等，2021)。

图卷积神经网络(graph convolutional network, GCN)为解决图问题提供了新的思路。借助于卷积神经网络对局部结构的建模能力及图上普遍存在的节点依赖关系，图卷积神经网络将处理欧氏数据的卷积神经网络推广到建模图结构数据，实现图卷积，完成了节点之间的信息聚合。尽管图卷积网络取得了巨大成功，但在节点分类任务中，几乎现有模型都只有两三层的浅层模型架构。传统的深度学习模型在堆叠大量网络层后，由于强大的表示能力，在很多问题上了取得了显著效果。在计算机视觉领域，卷积神经网络的深度对性能起着至关重要的作用。Alex等人(2012)提出具有8层卷积层的AlexNet模型；Simonyan等人(2014)提出的VGG(Visual Geometry Group)模型具有19层卷积层；Szegedy等人(2014)提出的GoogLeNet模型具有22层卷积层。更深的深度神经网络模型能够得到更大的接收域，从而获取更多表达信息。受卷积神经网络的启发，深度图卷积神经网络模型也期望具有更强的表现力。

但图卷积神经网络(GCN)的浅层设计似乎违反直觉，因为这些模型的深层版本原则上可以获得更多信息，但实际情况却性能表现得更差。主要原因在于深层图结构优化的特有难点——过平滑现象(Li等，2018)。一个直观解释是图卷积神经网络通过重复应用拉普拉斯平滑融合来自不同邻域的节点特征，平滑操作使得同一聚类中顶点特征相似，简化了分类任务，但当层数加深时，图中每个节点的表达倾向于收敛到某一个值，不同聚类中的顶点变得无法区分。受到过平滑问题限制的浅模型体系结构限制了其从高阶邻域提取知识的能力，也阻碍了节点分类任务的进一步发展。Dehmamy等人(2019)通过图矩(graph moments)(Bondy等，1976；Lin等，1995)分析GCN在图拓扑学习中的表示能力，表明更深的GCN具有更高能力学习更高阶的图矩。Loukas(2019)分析了图神经网络的局限性，指出基于消息传递框架的图神经网络的深度和宽度受到限制时，会失去很大部分的表达能力。

因此，利用图层级结构至关重要，以便能够以有效的方式聚合高阶信息来进行更好的预测。很多研究人员探索图上的深度学习方法并对其综述，但对更重要的分支——层级结构信息挖掘的研究和应用总结仍存在空白。为此，本文对图网络层级挖掘算法的发展进行了深入分析和总结。同时，通过图卷积神经网络层级特性实验，表明现有的层级信息挖掘算法仍然没有对图的信息进行完全探索，其分类能力并没有达到预期结果。

本文深入总结图网络层级信息挖掘算法的发展及存在的部分问题。贡献如下：1)针对图网络的层级信息的关联性，按照正则化方法和架构调整方法对现有图网络层级信息挖掘算法进行综述；2)对图网络层级挖掘算法进行系统分析，为每一类代表性图网络层级信息挖掘算法模型提供详细说明分析；3)进行图卷积神经网络层级特性实验，表明图结构中存在层级特性节点且现有的图层级信息挖掘算法仍然没有对图的信息进行完全探索，现存的图网络层级算法在节点分类任务上并没有达到最好的分类结果；4)在分析现有方法的基础上，论述了图网络层级挖掘算法存在的问题，并提出未来可能的研究方向。

1 定义和发展背景

1.1 符号定义

本文使用的常见符号及这些符号的详细说明如表1所示。

表1 常见符号定义

1.2 图卷积神经网络发展

按照传统的卷积神经网络和循环神经网络的定义，标准神经网络是按特定顺序堆叠节点特征进行输入，因此无法正确处理图结构数据的输入，因为图中没有自然的节点顺序。为了完整地呈现图结构数据，需遍历所有可能的顺序作为模型输入，如卷积神经网络(CNN)和循环神经网络(recurrent neural network，RNN)，这在计算时有大量冗余操作。为解决这个问题，图神经网络分别在每个节点上传播信息，避免了节点数据的输入顺序。同时，图中的边表示两个节点之间的依赖关系信息。在标准神经网络中，依赖信息仅被视为节点的特征。图神经网络(graph neural network，GNN)可以通过图结构进行传播，而不是将其用做特征的一部分。通常，GNN通过其邻域的状态的加权和来更新节点数据的隐藏状态。

随着深度学习的发展，研究人员将深度学习的模型引入图数据中进行端到端的建模，而图卷积神经网络则是发展最活跃的一个方向。在建模图卷积神经网络时，研究人员更关注如何在图上构建卷积算子(徐冰冰 等，2020)。

卷积定理如下：信号卷积的傅里叶变换等价于信号傅里叶变换的乘积(Shuman等，2013)，即

F(f*g)=F(f)·F(g)

(1)

式中，f和g表示两个原始信号，F(f)表示f的傅里叶变换，·表示乘积算子，*表示卷积算子。对式(1)两端进行傅里叶逆变换，可得

f*g=F-1(F(f)·F(g))

(2)

式中，F-1表示信号f的逆傅里叶变换。

利用卷积定理，可以对谱空间的信号做乘法，再利用逆傅里叶变换将信号转换到原空间来实现图卷积，从而避免了因图数据不满足平移不变性而造成的构造传统意义的卷积运算困难。

图结构的傅里叶变换依赖于图中的拉普拉斯矩阵的特征向量，以特征向量作为谱空间下的一组基底，图上信号x的傅里叶变换为

(3)

(4)

Brune等人(2013)提出第一个图卷积神经网络，基于图谱理论(spectral graph theory)从卷积定理出发，开发了一种图卷积的变体，在谱空间定义图卷积。该方法利用卷积定理在每一层定义图卷积算子，在损失函数指导下，通过梯度反向传播学习卷积核，并堆叠多层组成神经网络。谱卷积神经网络第m层的结构为

(5)

Kipf 等人(2016)对谱方法中的卷积核进行参数化，提出了基于半监督的图卷积神经网络，降低了时空复杂度。

(6)

Kipf等人(2016)为图结构的半监督节点分类如图1所示，任务设计了两层图卷积网络，并将模型简化为

图1 图卷积神经网络结构图(Kipf等，2016)

(7)

谱方法通常同时处理整个图，且难以并行或扩展到大图上。对此，基于空间的图卷积网络在节点域使用注意力机制和序列化模型。

给定一组节点特征作为图注意力层的输入，h={h1,h2,…,hN},hi∈RF，其中N是节点的数量，F为每个节点的特征数，通过注意力层可以生成一组新的节点特性，可能有不同的维数F′，输出为h′={h′1,h′2,…,h′N},h′i∈RF′。对每个节点作用一个权值矩阵W∈RF′×F，然后对每个节点应用注意力机制，一个共享的注意力机制α:RF′×RF′→R，计算注意力系数eij=α(Whi,Whj)，这表明节点j的特征对节点i的重要性。为了使不同节点间的系数易于比较，图注意力网络(graph attention network，GAT)使用softmax函数对所有j的选择进行标准化，即

(8)

图2 图注意力机制结构等，2017)

GAT基本思想是根据每个节点在其邻节点上的注意力，对节点表示进行更新。GAT具有如下几个特点：1)相比于GCN，无需特征分解等复杂的矩阵运算，计算速度快;2)引入注意力机制，计算节点的重要性，提高模型的表达能力;3)通过对邻域信息的注意力加权，帮助节点融合相似性信息。

经典的图卷积神经网络算法在很多任务上取得了显著效果，然而将这些算法应用于实际数据时仍面临一些挑战。

Li等人(2018)证明了图卷积算子为拉普拉斯平滑的一种特殊形式——对称拉普拉斯平滑。

拉普拉斯平滑(Taubin，1995)在输入特征的每个维度处理定义为

(9)

将其写为矩阵形式为

(10)

图结构由于存在信息聚合传播特性，拉普拉斯平滑法将节点的新特征表征为自身特征及其相邻顶点的加权平均。由于同一聚类中的顶点往往是密集连接的，平滑引导它们的特征相似，使得分类任务更加容易(Li等，2018)。这是GCN的基本处理机制，但它也带来了因卷积层数增加引起的潜在过平滑的问题，重复应用拉普拉斯平滑可能会混合来自不同聚类的特征，导致数据难以区分。

图3 Zachary’s karate club 数据集上针对GCN的15层级进行的节点嵌入(Li等，2018)

然而，由于图卷积是一个局部滤波器——相邻邻居的特征向量的线性组合，一个浅层GCN不能充分传播标签信息到只有少数标签的整个图中，这反映了GCN模型无法探索全局图结构。同时，深层的GCN意味着更大的接收域，深层体系结构在计算机视觉中的关键优势之一是它们能够堆叠简单的结构形成深层结构实现复杂功能。因此，图卷积神经网络的层级信息挖掘是必要的，但受过平滑和过拟合现象的影响无法直接通过堆叠卷积层来构建深度图卷积网络。过拟合现象会削弱小数据集的泛化能力，过平滑会随着深度的增加将输出表示与输入特征隔离，从而阻碍模型训练。基于层级结构的研究则关注构建一个层级的图卷积模型，从而能够获取更多的表达信息。

2 图卷积层级信息挖掘算法及其分类

受过平滑和过拟合问题影响的浅模型体系结构限制了它们从高阶邻域提取知识的能力，即无法从当前节点邻域的远程跳跃中提取特征。能否设计一种避免过平滑和过拟合的深层网络结构，且获取到层级信息是一个迫切需要解决的问题。将层级结构算法迁移到图数据分析的核心在于图层级卷积算子构建与图层级间信息融合。其中，图层级卷积算子构建的目的是刻画节点的局部表示，层级信息融合目的是层级间信息的互补性探索。

图网络层级信息挖掘算法分类如表2所示。按图层级研究方法关注点的不同，现有图层级信息挖掘算法分为两类。第1类是正则化技术(regularisation techniques)，该技术关注于图层级卷积算子的构造，例如DropEdge(Rong等, 2019)等方法利用图结构关系，通过每层随机剔除部分边来加深图神经网络并减缓过平滑现象发生；第2类是架构调整方法(structural adjustment method)，该方法关注于层级之间的信息融合，包括各类残差连接，例如知识跳跃或仿射残差连接。

表2 图网络层级信息挖掘算法

2.1 正则化方法

正则化方法主要是基于正则化技术处理图的层级结构信息，该类方法更关注于图层级卷积算子构建。图卷积算子(按特定权重聚合邻域节点的特征)是图卷积神经网络方法的核心算子。在架构调整方法中虽然按照某种机制将层级信息融合在一起，但并没有关注每个层级模型的构建，因此仍具有局限性，忽略了节点的拓扑关系以及边信息等。正则化方法具有以下两个特点：1)关注节点特性和边特性构建图层级卷积算子；2)采用正则化方法缓解图过平滑和过拟合现象，可以构造出更深的图网络模型。正则化代表性方法如表3所示。

表3 正则化代表性方法

2.1.1 基于卷积定理的正则化方法

基于卷积定理的谱图神经网络的建模必须基于拉普拉斯矩阵的特征值分解，且拉普拉斯矩阵带来拉普拉斯平滑现象。因此有研究人员提出改变图傅里叶变换实现图卷积定理。

小波神经网络(Xu等，2019)提出用小波基代替图卷积中的傅里叶基(Hammond等，2011)。按照原理，小波基可表示为Ψs=(ψs1,ψs2,…,ψsn)，其中，每一个小波都对应一个从节点i扩散到图上的信号，且s为尺度参数。小波基底的定义依赖于拉普拉斯矩阵的特征向量，即

Ψs=UGsUT

(11)

(12)

相比于图傅里叶变换(式(4))，图小波变换对节点邻域的调整更加灵活，通过改变尺度参数s调节中心节点的信息扩散范围。图小波神经网络卷积层定义为

(13)

考虑到小波变换通常比傅里叶变换具有更强的提取有用信息的能力，Wang等人(2021a)提出深度图小波卷积网络(deep graph wavelet convolutional neural network，DeepGWC)用于半监督节点分类任务。其中，DeepGWC的第l层表示为

Hl+1=σ(Hl′Wl′)

(14)

式中，σ为激活函数，Hl′是在H上进行图卷积的结果，Wl′是可优化的特征映射矩阵。Hl′和Wl′具体为

(15)

Wl′=βlWl+(1-βl)I

(16)

(17)

式中，γ表示初始残差项图小波变换项的比例。通过残差机制和小波变化的信息获取能力，DeepGWC构建了一个64层深度模型，并减弱了过平滑现象。

Bianchi等人(2022)基于自回归移动平均(auto regressive moving average，ARMA)滤波器(Narang等, 2013)提出一种新颖的图卷积层，与多项式滤波器相比，该卷积层提供了更灵活的频率响应，对噪声更鲁棒且可以更好地捕获全局图结构，并定义新的GCS(graph convolutional skip)层为

(18)

图4 ARMA卷积层结构(Bianchi等，2022)

(19)

实验表明，PairNorm使更深的GCN、GAT和SGC(simplifying graph convolutional networks)模型对过度平滑具有更强的鲁棒性，并极大提高了更深网络构架的性能。

Rong等人(2019)认为图神经网络无法加深主要有两个原因，过拟合(over-fitting)和过平滑(over-smoothing)，并提出了DropEdge机制，在模型训练时，随机删减掉原始图中的边来缓解这两个问题，其定义DropEdge 中的邻接矩阵为

Adrop=A-A′

(20)

式中，A′是原始边集中的随机子集，并通过丢弃率α控制子集大小。Rong等人(2019)从理论上证明，DropEdge既可以降低过平滑的收敛速度，又可以减少由过平滑引起的信息损失，且可用于许多GNN模型以增强性能。例如，JKNet(jumping knowledge networks)(Xu等，2018)、GCN(Kipf等，2016)、ResGCN(Li等，2019b)和GraphSAGE(Hamilton等，2017)等。

图5展示了多层GCN在Cora数据集上的表现能力(Rong等，2019)。可以看出，GCN-4陷入过拟合问题，训练误差小，但验证误差大；GCN-8的训练由于过平滑而不能令人满意地收敛。通过应用DropEdge，GCN-4和GCN-8在训练和验证方面都能很好地工作。

图5 多层GCN在Cora数据集上的表现能力(Rong等, 2020)

上述方法从卷积定理出发，关注于卷积定理中卷积核、节点特征和边的处理，通过重新构建图卷积聚合方式来减弱过平滑现象。

2.1.2 基于注意力机制的正则化法

基于卷积定理的图神经网络可以看做以拉普拉斯矩阵或其变体作为聚合函数。在注意力机制的启发下，一些研究通过注意力机制方式从节点域学习聚合函数。

Klicpera等人(2019a)探索了GCN与PageRank算法(Page等, 1999)之间的关系，提出基于personalized page rank 的改进版本的信息传递方式，认为根据图卷积网络(GCN)的消息传递算法与随机游走之间的关系，随着层数的增加，GCN会收敛到该随机游走的极限分布。极限分布是整个图的一个属性，没有考虑随机游走的起始(根)节点。因此，该方法不适合描述根节点的邻域。GCN的性能会因大量层聚合或传播而下降。为了将PageRank的影响分数用于半监督分类，Klicpera等人(2019a)根据每个节点的自身特征生成预测，然后通过personalized page rank方案进行传播，以生成最终预测，并基于此提出PPNP(personalized propagation of neural predictions)算法，具体为

Hi,:=fθ(Xi,:)

(21)

式中，X是特征矩阵，fθ是带有参数集θ的神经网络，生成预测H∈Rn×c。PPNP从传播步骤中分离出了用于预测的神经网络，使得PPNP算法可以聚合无限多个邻域。

为了加快计算速度，Klicpera等人(2019a)提出APPNP(approximate personalized propagation of neural predictions)算法，采用近似的方法来避免计算矩阵的逆，即

Z(0)=H=fθ(X)

(22)

(23)

(24)

式中，K定义了迭代的步数，在PPNP和APPNP中，可以通过概率α来调整影响每个节点的邻域的大小，从而针对不同类型的网络调整模型。图6解释了如何将个性化网页排名(personalized page rank)用于网络预测。

图6 Personalized page rank用于网络预测(Klicpera等, 2019a)

Klicpera等人(2019b)通过引入一个强大的、空间局部化的图卷积——图扩散卷积(graph diffusion convolution，GDC)来消除图卷积中只使用直接邻居的限制。GDC模型通过扩散矩阵定义广义扩散模型，具体为

(25)

Chen等人(2020a)提出GCNII模型，利用初始残差和恒等映射解决过平滑问题，有效缓解了过平滑问题。GCNII的l层定义为

((1-βl)In+βlW(l)))

(26)

在上述方法中，拉普拉斯矩阵带来的过平滑问题阻碍了深度图模型的研究。为此，重新设计神经网络来学习聚合函数，基于正则化技术处理图的层级结构信息，即图卷积层级算子的重新构造能够自适应于任务和具体的图结构，有更大的灵活性。

2.2 架构调整方法

与卷积神经网络层级卷积相对应，图卷积层级结构也具有类似的性质，不同深度的层级模型捕获不同的语义特征，浅层模型受节点特性影响较大，更关注于节点的局部信息，而深层模型则受图拓扑结构的影响，更关注于图全局信息，将不同层的嵌入基于注意力方式结合起来，可以获取更全面的信息。架构调整方法主要是利用图卷积层之间的相互关系进行深层叠加，并通过某种机制进行信息融合。一个简单的解决方案是通过残差连接(ResNets)实现的，但是这种做法在构建的深度图模型的预测性能和计算效率方面都不令人满意。

架构方法具有以下特点：1)灵活利用每个节点的不同邻域范围，实现更好的结构感知；2)关注图局部信息和全局信息；3)引入注意力机制，获取层级的互补性信息，增强节点的表达。

最新代表性的架构调整方法如表4所示。

表4 最新代表性的架构调整方法

针对图结构的层级特性，Xu 等人(2018)提出JKNet(jumping knowledge networks)。为了适应局部邻域属性和任务，采用基于跳跃知识网络的跳跃连接和注意力机制，将GCN每一层分别与最终层连接，并利用concatenation、maximization pooling、long short-term memory attention等操作自适应聚合每一层特征作为最终节点表示。模型结构如图7所示。

图7 4层JKNet模型示意图(Xu等, 2018)

Abu-El-Haija等人(2020)提出了模型N-GCN(network of GCNs)，与JKNet不同，N-GCN使用GCN随机游走中在不同距离处发现的节点对上层训练多个全局控制网络实例，并将每层输出拼接在一起，最后利用全连接网络进行层级信息融合。N-GCN模型结构如图8所示。

图8 N-GCN结构示意图(Abu-El-Haija等, 2020)

Sun 等人(2021)提出AdaGCN，使用集成学习方法探索层级特性。针对前一层模型在测试数据集上的准确度，优化该层在最终模型的注意力系数。准确度越低则注意力系数越低，这样使得模型能够以AdaBoost的方式对层级特征进行融合。AdaGCN模型关注的是每一层模型在测试数据集上的准确度，对同一层节点分配的注意力系数相同。AdaGCN模型结构如图9所示。

图9 AdaGCN模型结构示意图(Sun等, 2021)

Abu-El-Haija等人(2019a)提出MixHop-GCN,通过重复混合不同距离的邻域特征表示来学习邻域混合关系，并利用超参数融合层级特征。

Li等人(2019b)利用卷积神经网络的概念，特别是残差/密集连接和扩展卷积，构建了一个非常深的56层GCN体系结构，在点云语义分割任务中可以显著提高性能。图10展示了3种GCN的主干块结构。大量实验表明，这些深度GCN框架具有积极作用。

图10 三种GCN的主干块结构(Li等，2019b)

在DeepGCN中，研究人员认为通用GCN网络从l层到l+1层的传播方式为

Gl+1=F(Gl,Wl)=

(27)

受到ResNet的启发，Spinelli等人(2021)对GCN进行更改，称为ResGCN。具体为

Gl+1=H(Gl,Wl)=

(28)

同时，为了利用各层之间的紧密连通性，改善网络的信息流，受DenseNet(Huang等，2017)的启发，Huang等人(2017)将类似想法应用于GCNs，以便利用不同GCN层的信息流，将DenseGCN定义为

Gl+1=H(Gl,Wl)=T(F(Gl,Wl),Gl)=

T(F(Gl,W),…,F(G0,W0),G0)

(29)

式中，T表示顶点级连接函数，将输入图G0与所有中间GCN层输出密集融合。

DeepGCNs利用ResGCN和DenseGCN处理GCNs的梯度消失问题，使GCN可以进行深层学习。

Spinelli等人(2021)提出AP-GCN(adaptive propagation GCN)模型，通过在每个节点上独立调整通信步骤的数量，特别是赋予每个节点一个暂停单元，利用线性网络对每个节点的层级输出特征进行判断，在每次信息传播后决定该节点是否继续通信。最终，利用线性网络判断出的停止概率值对层级特征进行融合。由于AP-GCN依据节点级别判断层级特性，且通过停止概率值阻断部分节点信息传播，因此获得了最新的分类表现。AP-GCN模型结构如图11所示。

图11 AP-GCN模型结构(Spinelli等, 2021)

Pei等人(2022)提出残差图卷积网络(residual graph convolutional network，ResGCN)用于网络中的异常检测，框架如图12所示。异常节点与其他节点有两方面不同；1)异常节点在结构上连接所有其他节点；2)异常节点属性与多数节点明显不同。Pei等人(2022)提出的方法是一种基于注意力的深度残差建模方法，使用GCN建模属性网络可以捕获稀疏性和非线性。利用深度神经网络可直接从输入中学习残差，而基于残差的注意力机制可减少异常节点带来的不利影响并防止过度平滑。

图12 ResGCN框架(Pei等, 2022)

为了在模型构建中考虑高阶结构关系来提高节点分类模型的表现，研究人员通过以上方式融合大范围和小范围的特征组合，自适应地调整每个节点的影响半径，聚合不同层级节点表达产生节点的最终表达，以此探索层级互补性信息。

3 图卷积网络层级特性实验

图结构节点受到的结构影响不同，从邻域获取信息的能力不同，自身携带信息的能力也不同。为了验证图结构节点存在层级特性以及其过平滑现象，在3种标准引文数据集Cora、CiteSeer和PubMed上对图卷积神经网络层级进行实验，探索不同深度的图卷积神经网络对其节点的分类能力。

GCN-0：

Y=σ(XW),W∈RF×C

(30)

GCN-1：

(31)

GCN-2：

W1∈RF×H,W2∈RH×C

(32)

GCN-3：

W1∈RF×H,W2∈RH×H,W3∈RH×C

(33)

在实验中，模型基于PyTorch Geometric(Fey等，2019)标准图神经网络库设计，各数据集参数如表5

表5 层级特性实验参数定义

所示，为了可复现结果，随机种子设置为42。

表6 图卷积网络层级特性实验结果

图网络层级信息挖掘算法均采用不同的信息挖掘手段，试图使用一个统一的模型，利用端到端的学习方式将不同特性节点分类成功。从预期结果来看，如果有一个模型可以将每个层级的特性节点均分类成功，图网络节点分类任务将显著性突破，但遗憾的是，目前的算法尚未能达到预期结果。

4 应 用

图卷积神经网络提出以来，受到网络分析、推荐系统、计算机视觉和自然语言处理等领域研究人员的关注。其中，图网络层级信息挖掘算法主要应用于网络分析、推荐系统和计算机视觉领域，相关算法及任务如表7所示。

表7 图网络层级信息挖掘算法应用总结

4.1 在网络分析中的应用

在网络分析领域，引文网络是最常见的数据。该网络中，节点为论文的特征，特征中的0和1表示该论文有无对应的词汇，边为论文节点之间引用关系，是无向图网络。

常见的数据集包括Cora、CiteSeer和PubMed等，具体描述如表5所示。

典型的分类任务是给定每篇文章的内容信息与文章之间的引用关系，将每篇文章分类到对应的领域。在该类任务中，图卷积神经网络对节点文本属性和引用网络结构进行有效建模，取得了巨大成功。部分模型分类结果如表8所示。包括直接使用内容信息，如MLP(multilayer perceptron)(Gardner等, 1998)；仅使用结构信息，如DeepWalk(Perozzi等，2014)和传统图上半监督节点分类方法，如Planetoid(Yang等，2016)。实验结果表明，以GCN为代表的图卷积神经网络算法及其融合层级信息后的分类准确度远高于传统方法。

表8 不同模型在Cora、CiteSeer和PubMed数据集上的节点分类结果

网络分析中另一个发展分支为社交网络分析，主要任务有用户画像、舆情分析、社交垃圾邮件检测和谣言检测等。Zhang等人(2018)在链接预测问题中，通过在每个目标链接周围提取局部子图，学习一种映射子图模式，以链接存在的函数，从而自动学习适合当前网络的“启发式”方法，并证明可以从局部子图很好地近似所有这些启发式方法。Qiu等人(2018)关注于用户级社会影响力的预测，通过将网络嵌入、图卷积和图注意力网络构建到一个统一的框架DeepInf中，设计了一种端到端的方法来自动发现社会影响中的隐藏和预测信号。

确定影响媒体讨论新闻事件方式的政治视角是一项重要而富有挑战性的任务，Li等人(2019a)提出通过GCN来捕获文档的社交环境，以此来预测作者的政治倾向。Peng等人(2019)基于知识元路径实例的社交事件相似度度量(knowledgeable meta-paths instances based social event similarity，KIES)，提出基于GCN的社交事件分类算法。Wu等人(2020)基于Markov random field reasoning(Li，1994)提出一种基于图卷积网络的社交垃圾邮件发送者检测模型。Bian等人(2020)提出一种双向图模型，称为双向图卷积网络(bi-directional graph convolutional networks，Bi-GCN)，通过对谣言自上而下和自下而上的传播进行操作来探索这两个特征，以此进行社交谣言检测。

4.2 在推荐系统中的应用

基于图的推荐系统将项目和用户作为节点。通过利用项目与项目之间、用户与用户之间以及用户与项目之间的关系，使得系统能够产生高质量的建议。推荐系统的关键是对用户评价项目的重要性。因此，可以将其视为链接预测或矩阵补全问题，从而能够有效建模商品与用户之间的联系。

He等人(2020)将图卷积层级信息用于推荐系统，提出LightGCN模型，在将每个用户(项目)与ID(identity)嵌入关联后，在用户—项目交互图上传播嵌入以对其改进，然后将不同传播层的嵌入信息与加权和相结合，得到最终的预测嵌入信息。Ying等人(2018)将卷积神经网络应用于推荐系统，提出一个数据高效的图卷积神经网络算法PinSage，对商品节点产生嵌入表达。这些表达包含图结构和节点特征信息。相比传统的图卷积方式，该方法使用一个高效的随机游走策略建模卷积，设计了一个新的训练策略，成功地将图卷积神经网络应用于超大规模推荐系统。

相比于传统方法，图卷积神经网络能够更好地利用在推荐系统普遍存在的用户属性和商品属性信息，这也是图卷积神经网络能够在推荐系统任务上引起人们广泛关注的原因。

4.3 在计算机视觉中的应用

计算机视觉方面的应用主要为物体识别、图片分类和语义分割等任务，同时更关注于少样本分类以及复杂语义情况下的建模和学习。

在点云分割任务中，Li等人(2019b)通过构建的56层深度图卷积，在点云分割任务中达到了目前最好的表现结果。在点云生成任务中，Valsesia等人(2019)将图卷积引入生成对抗网络(generative adversarial network，GAN)(Goodfellow等, 2014)中，并研究了在图卷积生成器中定义上采样层的问题，以使其学会在数据分布前先利用自相似性更有效地采样，来解决点云生成任务中不规则分布无序点采样问题。在RGBD语义分割任务中，Qi等人(2017)提出一个3D图神经网络(3DGNN)，该网络在3D点云之上构建了一个k最近邻图。图中的每个节点对应于一组点，并与隐藏的表示向量相关联，该向量由一元CNN从2D图像提取的外观特征初始化。依靠循环功能，每个节点都会根据当前状态和来自邻居的传入消息动态更新其隐藏表示。在一定数量的时间步长上展开此传播模型，并将最终的每个节点表示形式用于预测每个像素的语义类别。在语义分割任务中，Zhang等人(2019a)为了捕获不同语义级别的对应关系，受特征金字塔(Lin等，2017)的启发，提出一种金字塔状结构，将不同大小的图像区域建模为图节点，并在不同级别进行图推理。

4.4 在其他领域的应用

图网络层级信息挖掘分类算法的研究方向不限于上述领域和任务，还包括自然语言处理(Song等，2018；Liu等，2019b)、问题解答(Chen等，2018)、行人交互(Qi等，2018)和视觉推理(Wang等，2020)等。由于图网络层级信息挖掘分类算法可以建模图结构数据，并且通过图卷积和注意力机制等能够改善图卷积经典算法在实际应用中的多尺度和过平滑等局限性，因此具有广泛的应用前景。

5 存在问题及发展方向

1)计算效率方面。相比较于浅层图卷积模型，深度层级模型的研究必然导致模型参数量的增多，同时带来过拟合、梯度消失和梯度爆炸等问题。尽管残差连接、密集连接和图层级信息挖掘等可缓解深度图模型的梯度消失、梯度爆炸等问题，但相比较浅层模型，深层模型需要更多的训练样本引导模型收敛。时间复杂度和空间复杂度成为制约深度图卷积模型学习的一个难点。

2)问题设置方面。图神经网络应用中一个具有挑战性的问题是如何处理具有动态结构的图，例如异构图和时序图。静态图是稳定的，因此可以利用拉普拉斯矩阵对其进行卷积处理，而动态图则引入了变化的结构。STGCN(spatial temporal graph convolutional network)(Yan等，2018)引入时间通道卷积建模人体运动过程中骨骼节点的运动序列信息；MRA-BGCN(multi-range attentive bicomponent GCN)(Chen等，2020c)在交通网络信号图中引入二分图卷积模型，建模节点和边在时序中的交互机制。但在上述研究中，图结构的节点固定，只有状态发生改变，依然可以依靠拉普拉斯矩阵建模空间相关性。当引入层级信息后，层级之间的节点信息传播不再遵循初始邻接关系的传播路径，节点的增加和消失导致信息传播出现变化，无法完全探索节点的层级特性，严重影响了图层级模型的稳定性和判断能力。

3)应用场景方面。图数据无处不在，图神经网络也已经在各种深度学习任务发挥至关重要的作用。相比较浅层图神经网络，使用层级图神经网络的优点在于，节点的局部子图和全局图结构之间的关系保留在节点表征中，丰富了节点的表达，在节点分类任务中已经得到有效应用，如点云识别、推荐系统等。而探索层级结构在其他各类数据图任务中的应用也非常重要，因为层级图卷积模型从不同角度为图任务提供了有效的解决方案。

6 结 语

深度图神经网络的训练过程非常艰难，除了深层神经体系结构中的典型难点(如大量参数导致反向传播梯度消失和过度拟合)外，还有一些图特有的难点，例如过平滑，这是由于应用了多个图卷积层，节点特征趋于收敛到同一向量并逐渐变得难以区分。这些问题都影响着图网络中的层级问题。而如何通过层级信息挖掘来捕获层级之间的互补信息，增大模型的表现能力是研究人员致力解决的问题。

本文介绍图卷积神经网络的发展及其典型算法，并将其分为正则化方法和架构调整方法两类。同时，总结最新的图卷积神经网络层级信息挖掘模型以及主要应用方向。针对图的层级特性进行实验，可以看出图结构中存在一些特殊节点，该节点受图的结构影响较大，因此表现出层级特性。层级信息挖掘算法的目的在于使用一个统一的模型，针对不同层级特性节点均有良好的分类效果。总的来说，虽然已经提出一些基于层级的图卷积网络算法，并能够减缓过平滑现象的发生，但如何有效挖掘层级之间的信息仍是一个迫切需要解决的问题。