基于图过滤框架对图卷积滤波器灵活性的研究

徐鑫强,何 鹏,2

(1.湖北大学计算机与信息工程学院,湖北 武汉 430062; 2.湖北省应用数学重点实验室,湖北 武汉 430062)

0 引 言

近几年，为了更有效地处理图数据，研究人员提出了图卷积神经网络(Graph Convolutional Network)方法，它在图数据的结点嵌入表征学习中表现出了强大的建模能力。不同于传统的基线算法(DeepWalk[1]、GraRep[2])，它将卷积神经网络迁移到图结构上，进行端到端的学习，而且已经在许多场景下取得了显著的效果，例如在推荐系统、交通预测、网络分析等领域的成功应用。图卷积神经网络的出现，极大地提高了人们对此类数据的信息挖掘能力，因此正受到人们越来越多的关注和研究。

图卷积神经网络的最新进展可分为谱方法和空间方法2类。谱方法利用图上卷积定理从频谱域定义图卷积，借助于图谱理论来实现拓扑图上的卷积操作；空间方法从结点域出发，直接将卷积操作定义在每个结点的连接关系上，利用聚合函数来聚合每个中心结点和其邻近结点，它和传统的卷积神经网络中的卷积更相似些。谱卷积神经网络通过对图信号进行傅里叶变换进入谱域，基于卷积定理构建可学习的卷积核以实现图卷积，它避免了在空间域因图数据不满足平移不变性而造成卷积核定义困难的问题。卷积核刻画了结点的局部结构，在损失函数指导下利用梯度反向回传学习卷积核，基于谱域的卷积操作将网络的拓扑结构和结点的属性等特征用神经网络进行捕获，从而完成结点之间的信息聚合，最终更新结点的相似度表征，并服务于后续任务，例如结点分类、链路预测等。因此，卷积核对图卷积神经网络的特征提取效果起着至关重要的作用。而不同的图数据需要进行差异化的图信号处理，为了在实际情况中应对场景不同给图卷积模型性能发挥带来的限制，需要提高卷积核的灵活性，具体来说，就是如何设计一个更好的卷积核，以便在应对各种图数据时，都可以精确捕获图结构以及其他信息(尤其是数据特征)来获得结点的相似度表征。

尽管以前研究已取得了许多进展，但在现有方法的基础上仍可以做些有益的尝试和拓展。基于图谱理论的图卷积网络(GCN[3])表现出令人印象深刻的效果。GCN的成功启发了许多关于半监督学习的图神经网络的后续工作，这是由于其特殊设计的一阶卷积滤波器可以非常有效地对结点的连接信息和特征信息同时进行学习以获得结点相似度表征。但是由于其并未过多地考虑图的特性，在不同应用场景上滤波器显得灵活性不够，例如，当对于只含有很少量标签的图时，表征学习的分类准确度会有所下降[4]。最近，GCN的改进模型IGCN(Improved Graph Convolutional Network)[4]从图滤波框架的角度研究了图数据上的卷积操作。其基本思想是将数据特征作为信号放在编码数据样本之间关系的基础图上，并在该图上使用适当的低通图卷积滤波器以生成平滑且具有代表性的特征。平滑是对图信号进行低通滤波，滤除其剧烈变化的部分(高频信号)，使得相邻结点表征在不断融合中更为相似。它通过在GCN滤波器上引入指数参数k来实现对滤波器强度的控制，增大k值，可以提高滤波器的平滑力度，模型灵活性得到有效增强。但应注意到调整指数参数也会带来一定的时间损失(时间复杂度和指数呈线性关系)[4]。

本文在IGCN的基础上引入滤波器频率响应函数的平移参数μ，让此类滤波器在指数参数一定的情况下，还具有另一种可调控滤波器平滑力度的途径。模型通过在有效范围内控制μ达到了增强滤波器灵活性的目的，且不需要增加额外的神经网络可训练权重数量，保持了模型的浅层结构。同时，本文在图过滤框架下详细解释了平衡参数的作用原理并从图划分的角度提供了更为全面的见解。需要指出的是，IGCN已经表现出优异的学习效果，当已经能为结点学习到较合适的特征表示时，加入平衡参数只在微小范围内再根据具体的滤波需求对滤波器实施微调操作，但当滤波器的平滑力度不足以产生较好的相似度表征时，只控制平衡参数μ也可以显著地提升平滑效果。

基于聚类假设，本文分别在3个引文网络和1个知识图谱数据集上使用双层图卷积神经网络开展了半监督的图嵌入学习实验。通过设置多段平移参数值进行数值实验，并通过实验分析得出网络的稀疏程度是平衡参数μ取值的一个重要参考因素。实验结果显示，在时间不损失的情况下，基于二阶滤波器，在小规模的引文网络上，半监督分类的准确率优于最新的IGCN模型。另外在较大规模的知识图谱数据集上，利用参数μ可使滤波器在k=2的情况下，实现优于IGCN中使用指数参数k=5时的分类效果，即平衡参数μ是除了指数参数k外另一个控制滤波器平滑力度的重要参数。最后本文经过合理性分析,将引入平衡参数的做法推广到更高阶的低通滤波器上。

1 图过滤

本章将介绍图信号、图滤波和图卷积滤波器的概念。

1.1 定义1(图信号)

图信号是图的顶点集V上的实值函数f:V→R,可以向量形式表示为f=(f(v1),…,f(vn))T。任何图形信号f都可以分解为基本信号(φi)1≤i≤n的线性组合：

(1)

其中，C=(c1,…,cn)T,ci是φi的系数。系数ci的大小表示信号f中呈现的基本信号φi的强度，值越大，表示基本信号φi对信号f的特征表现贡献越大。与较低频率相关的基本信号在图形上更平滑[6]，即高频基信号φi(大特征值)代表的是图信号中剧烈变化的部分，低频基信号(小特征值)代表的是图信号中平滑的部分，其中基本信号φi的平滑度由特征值λi来衡量，即：

(2)

因此，平滑的图形信号f应该主要由低频基础信号来组成，以便相近结点在卷积中学到更为相似的表征。但同时对于各种不同的应用场景及图特性，还应考虑在结点的特征信息和连接信息之间调整捕获强度。例如，若同类结点的个性化信息非常丰富时，应当减弱低通滤波器的平滑力度，保持一定的结点特征多样性。

图过滤的基本思想是使用基础数据关系图设计适当的图过滤器，将过滤器作用于图信号以便生成用于下游任务的平滑信号。例如，可以将特征矩阵X的一列视为图信号，图滤波提供了一种将图结构和顶点特征进行集成以进行学习的原理方法。线性的图滤波器可以表示为矩阵G∈Rn×n，输出信号是Gf，本文将重点放在图卷积滤波器上。

1.2 定义2(图卷积滤波器)

当且仅当存在一个函数p(λ):R→R且满足G=Φp(Λ)Φ-1，其中p(Λ)=diag(p(λ1),…,(λn))时，线性图滤波器G才是卷积滤波器。函数p(λ)被称为滤波器G的频率响应函数，它控制着对不同频率的基信号的响应。一般而言，为了产生平滑信号，滤波器G应能够将低频基频信号保留在f中，同时滤除高频基频信号。通过公式(1)，输出信号可以被写成：

(3)

2 回顾和拓展IGCN

图卷积网络(GCN)通过使用频谱图卷积的局部一阶逼近进一步简化了ChebyNet[7]，并在半监督学习中取得了可喜的成果。GCN模型包含3个步骤：

2)定义分层传播规则为：

(4)

3)堆叠2层并在输出上应用softmax函数产生预测矩阵的特征为：

(5)

(6)

具有频率响应函数为：

(7)

(8)

(9)

IGCN可以通过指数k方便地调整过滤强度来实现标签效率，并保持具有合理数量的可训练参数的浅层结构，从而避免过度拟合[4]。

IGCN模型中低通滤波器的强度由参数k控制，对于不同的应用场景选择合适的k是很重要的。直观地，在半监督的图嵌入学习任务中，当每个类别中的标签很少时，应增加过滤的强度，以使远处的结点可以具有与标签结点相似的特征表示，便于分类。但是过度平滑通常会致使不同类结点表征趋于同质化，导致不正确的类边界。同时，本文注意到，越来越多应用场景的出现带来了更具差异化的滤波需求。因此，出于精细设计的考虑，本文引入平衡参数μ，使滤波器在指数不变的情况下，还具有一个平滑力度的控制区间，也就是说可以不需要增加神经网络可训练权重数量，通过调控平衡参数也可实现对图卷积滤波器的平滑力度的控制，进而使模型能适应多样的应用场景。具体实现过程如下：

GCN根据图谱卷积ChebyNet使用一阶近似简化计算的方法，从而提出了一种简单有效的层次传播模型。ChebyNet的谱卷积定义为：

(10)

(11)

假设T=1,λmax=2，则ChebyNet卷积公式简化近似为：

(12)

此处，本文引入平衡参数μ，即令：

θ=θ0=-μθ1,μ∈[0,2]

(13)

于是图卷积的定义就近似为：

(14)

运用重归一化技巧，最后可以得到卷积公式为：

(15)

则频率响应函数为：

(16)

图1 可视化在Cora数据集上使用滤波器

3 图谱和图划分

平衡参数通过控制频率响应函数的水平位移来提取合适的平滑信号，此外，本文提出还可以从图划分的角度进一步解释平衡参数作用的原理。高阶Cheeger不等式[8-10]显示了图对应的拉普拉斯矩阵谱空间上的特征值和图空间中的图划分(聚类)之间的关系。本文使用Cheeger常数(Cheeger constant)，也被称为图的传导(graph conductance)来反映图的划分。本文从图的结点集合中抽取一个子集，作为图的划分，记作Q⊆V，Cheeger常数定义为：

(17)

在这里E(Q)是一个结点在划分的结点集Q中的边的集合，vol(Q)是结点集Q中的结点的度的和。Cheeger常数反映了图的二划分的划分效果，ω(Q)越小，则图被划分得越开，划分效果越明显。将Cheeger常数推广到图划分成更多个子集的情形，就是r阶Cheeger常数(r-way Cheeger constant)，它定义为：

ρG(r)=min{max{ω(Qi):Q1,Q2,…,Qr⊆Vdisjoint}}

(18)

r阶Cheeger常数中，使用r划分得到的r个划分结点集的Cheeger常数的最大值来衡量该r划分的效果，并以所有可能的r划分中的最好效果(最小值)来衡量图被r划分的程度，所以它表示的是图内在的划分(聚类)属性，ρG(r)越小，则图能被r划分的效果越好。

r阶Cheeger常数ρG(r)和图的谱域中的特征值存在着以下的关系：

(19)

该不等式叫做高阶Cheeger不等式。在高阶Cheeger不等式中，第r小的拉普拉斯矩阵的特征值设置了上下界来控制图的r划分指标ρG(r)，所以，可以从谱空间对图结构进行调制，使调整后的图结构更加强调局域的平滑信息或全局的聚类信息。

从高阶Cheeger不等式(19)可以推断出，小的拉普拉斯矩阵的特征值控制着图被划分成几个大的子图的划分效果，即图的相对全局的聚类效果；大的特征值控制着图被划分成许多个小的子图的划分效果，即相对局域的聚类效果。当大特征值衰减时，是对图的局域平滑效果的增强；对于小特征值的衰减效果，是对图的全局聚类效果的增强。对于低通滤波器而言，则主要是对高频信号(大特征值)的衰减。这一结论可以启发通过控制频谱空间的特征值，来控制图的高阶全局或局域的划分聚类效果。具体来说，增强低通滤波器的强度，是增大对大特征值的衰减，图结构的内在划分属性更加强调局域聚类，此时在拓扑图上的卷积操作将使相近结点的表征更加相似，加强了平滑信号所带来的作用。

4 实 验

本文利用TensorFlow构建图卷积核，在3个引文网络数据集和1个知识图谱数据集上执行半监督的图嵌入学习实验。为了让所做的对比实验是针对单一变量的，本文在与IGCN模型的对比实验中使用二阶(滤波器指数参数k=2)的双层神经网络，以确保在公平的实验设置环境下检验所做改进的有效性。

4.1 数据集

数据集的统计总结在表1中，引文网络数据集(Cora、Citeseer和Pubmed[11])包含每个文档的稀疏词袋特征向量以及文档之间的引文链接列表，结点是文档，边是引文链接。NELL[12-13]是从具有55864个关系结点和9891个实体结点的知识图中提取的二部图数据集。网络的稀疏度是图数据的一个重要特征，本文用边的数量与结点数的比值来衡量。

表1 数据集统计

4.2 实验设计

本文将引文链接视为(无向)边，并构造一个二进制的对称矩阵。每个文档都有一个类标签。对于训练，每个类有20个标签，但使用所有特征向量。半监督学习的目的是使用少数标签的文档的类型对文档进行分类。本文与GCN、IGCN进行比较，在相同的数据集划分中训练模型，模型迭代训练200次，并在包含1000个带标签的示例的测试集上评估预测准确度。本文使用和文献[4]一致的超参数集，对于Cora、Citeseer和Pubmed的参数值为：0.5(辍学率)、5·10-4(L2正则化)、16(隐藏单元数)、0.01(学习率)；对于NELL的参数值为：0.1(辍学率)、1·10-5(L2正则化)、64(隐藏单元数)、0.01(学习率)。

5 实验结果及分析

(a) Cora数据集上的准确度变化

(b) Citeseer数据集上的准确度变化

(c) Pubmed数据集上的准确度变化

(d) NELL数据集上的准确度变化图2 平衡参数μ对模型性能的影响

表2 关于分类准确性的结果摘要

对于不同的数据集，平衡参数会有一个相应的有效区间及最优解参数值，超过此区间，模型的学习能力会急剧地下降，改进也将失去意义。本文以Cora数据集为例分析平衡参数的作用原理以及其取值规律。对于Cora数据集，图卷积神经网络模型的频率响应函数图像在引入平衡参数前后进行对比，二阶滤波器下，IGCN的频率响应函数(μ=1)与优化后的模型在调整μ值后取得最佳分类效果时的频率响应函数(μ=1.1)的图像对比如图3所示。

图3 频率响应函数的图像对比

在图3中，μ值增大，频率响应函数右移，此时的

图4 IGCN模型在不同k值时的频率响应函数

高阶Cheeger不等式同样可以解释IGCN模型中指数参数k的作用。如图4所示，拉普拉斯矩阵特征值在[0,1]范围时，滤波器具有低通性，而通过设置同一个频率响应的最小通过值可以看到，随着指数增大，能通过的特征值越来越小，即平滑力度增强，故大特征值衰减效果越加明显，图的局域聚类效果加强。

对于越大的数据集，为了获得结点的相识度表征，需要加大滤波器处理信号的平滑力度[4]。NELL是所有测试数据集中稀疏程度最小的，却没有在μ>1的区间上取得最佳分类效果，其分类准确度随参数μ的增大而单调递减。这是因为对于此规模的数据集，k的设置应为一个较大的值，如在IGCN中，k设定为5左右，而本文实验中对所有数据集都使用二阶的滤波器，结点没有得到嵌入表示学习所需的平滑强度，因此对局部图结构信息的捕获表现出更强的需求，这时平衡参数μ的作用在于将平滑力度提升到一个合适的水平，可以看到模型分类准确度显著地提升了46%左右，甚至优于在IGCN中使用阶数k=5的分类效果。而在另外3个引文数据集中由于数据规模并不大，在二阶滤波器下已经能产生较好的平滑效果，此时参数μ的作用在于对滤波器强度进行微调以达到一个最佳的模型性能。此外，从图4中可以看到，对于此类更高阶的低通滤波器，控制参数μ，使函数平移，进而控制滤波器的性质同样具有有效性。

6 相关工作

关于卷积核的改进优化的文献很多，早期的基于图的方法采用一个共同的假设，即附近的顶点可能具有相同的标签，如拉普拉斯特征图[15]、光谱核[16-17]。在频谱域上，谱卷积神经网络(Spectral CNN)[18]是最早利用卷积定理在一般图结构上定义卷积算子的方法。Henaff等[19]提出了用带有平滑性约束的插值卷积核，这种方法降低学习参数的个数且实现了图卷积神经网络的局部化。全连接网络(FCN)[20]以(I-γ

其他相关研究包括GraphSAGE[27]、图表关注网络[28]、基于注意力的图神经网络[29]、图分区神经网络[30]、FastGCN[31]、双图卷积神经网络[32]、随机GCN[33]、贝叶斯GCN[34]、深层图infomax[35]、LanczosNet[36]等。

7 结束语

本文对经典图卷积神经网络的改进模型IGCN做了增强图滤波器灵活性的处理，引入可变对角矩阵μ作平移参数，实现了更精细设计的目的，通过控制参数μ可以调整滤波器的性质，并且不会带来时间上的损失和引入额外的待学习权重参数，保持了模型的浅层结构。相比于IGCN，模型性能有了进一步的提升，更加容易适应各种应用场景，同时，本文对平衡参数的作用原理及实验现象进行了多角度的解释，包括从图划分的角度来看待IGCN模型中指数参数k的作用。未来笔者计划研究针对各种应用场景的适当图过滤器的设计和自动选择，并应用提出的方法解决更多实际应用。