差分进化算法优化的图注意力网络集成研究

刘鹏飞，张伟峰，何克晶

(1.华南农业大学 数学与信息学院，广东 广州 510642；2.华南理工大学 计算机科学与工程学院，广东 广州 510006)

现实中很多数据例如三维网格、社交网络和合成化合物等通常以图结构表示其原始信息.图数据中节点的不规则特点和相互依赖关系使得现有的深度神经网络算法在处理图数据时面临着挑战，如卷积计算难以直接应用到图数据.

图神经网络扩展自递归神经网络，由文献[1]根据图数据的特点并参考以往卷积网络和深度自动编码器等技术提出，可处理循环图、有向图和无向图等.此后相关研究不断出现：例如文献[2]利用转移矩阵定义邻域，同时学习每个输入通道和邻域度的权重；文献[3]从图结构选出具有代表性的节点序列并对它们分别求出一个可卷积的归一化邻域；文献[4]提出GraphSAGE 模型，先搜索图中每节点的固定邻域，再在其上进行聚合操作.

图神经网络当前主要可划分为5 种：图卷积网络、图注意力网络、图自编码器、图生成网络和图时空网络.注意力机制随着深度神经网络的发展而产生，能够放大数据中最重要部分的影响.目前注意力机制开始融入到图神经网络的聚合过程，着重于输入信息中最重要部分[5].

受上述相关工作启发，文献[6]引入了基于注意力机制的图神经网络对图结构数据进行节点分类，其关键在于通过观察每个节点的邻居来计算图中每个节点的表示.注意力机制主要有3 个特点：①支持节点−邻居对之间并行计算；②支持对邻居指定任意权重，可应用于度数不同的图节点；③支持归纳的学习问题，包括将模型推广到不可见的图形[7].

分析已有的研究结果，图注意力网络的分类效果尚有改进的空间.一般而言，分类器性能的提升可以从算法本身进行改进，或者利用某种算法对分类器超参数进行优化，以及结合流行的集成学习策略等.集成学习为促进分类模型的性能和稳健性提供了行之有效的方法.它通过组合多个基学习器的输出来完成预测任务，往往能够得到比基学习器更好的泛化性能.

目前尚未有研究将智能算法优化的集成学习策略应用到图数据分类或者图注意力网络.本文提出差分进化算法优化的图注意力网络集成并展开相关实验证明其效果.

1 相关理论

1.1 集成学习集成学习(Ensemble Learning)通过某种规则组合多个基学习器以降低学习难度，提高分类模型的稳健性并避免过拟合，其在很多机器学习任务上取得了成功[8].基学习器之间的差异性是集成学习成功的关键因素.一般而言，增强基学习器的多样性可采用4 种策略：数据样本扰动、数据属性扰动、输出表示扰动和及算法参数扰动[9].

不同的多样性增强策略有不同类型的基学习器与之对应.总体上基学习器可分为稳定和不稳定两种，后者是指对样本扰动或参数扰动敏感，轻微变化都会导致基学习器学习性能产生显著变化.

集成学习有不同的基学习器组合方式，其中最常见的为多数投票法，它遵循少数服从多数原则确定待预测样本的类别标签.经典的Bagging 算法即套袋法从原始样本集中进行k轮抽取得到k个相互独立的训练集并在其上分别进行训练得到k个基学习器.所有基学习器具有相等的投票权重，将上一步得到的k个模型采用投票的方式进行综合从而得到分类结果.

在Boosting 或AdaBoost 算法中，每个基学习器根据其在训练集上的错误率被赋予不同的权重[10].AdaBoost 本质上是通过贪婪搜索最小化训练样本的指数损失.文献[11]提出的图卷积网络集成模型AdaGCN 能够有效地从当前节点的高阶邻域中提取知识，并以Adaboost 的方式将邻域中不同跳数的知识整合到图卷积网络集成.文献[12]利用boosting 理论，证明了在弱学习型条件下训练误差的收敛性；并将boosting 算法应用于多尺度图神经网络集成的训练中，以完成节点预测任务.

总体而言，为分类器集成的基学习器找到一个最佳的权重组合甚至次优的方案往往需要大量计算.一种常见做法是基于某种优化算法，以分类器集成在验证集上的性能指标为目标，优化多个基学习器对应的权重向量或者矩阵.例如文献[13]提出了遗传算法中一种新的惩罚性适应度函数以促进弱分类器组合中权重优化.文献[14]提出了基于欧氏距离适应度的差分进化算法以训练神经网络集成.

1.2 差分进化算法差分进化算法（Differential Evolution，DE）是一种基于群体差异的全局随机优化算法，具有收敛速度快、结构简单和鲁棒性强等优点，广泛地应用在组合优化等领域.

遗传算法启发了差分进化算法的发展，两者都包括：以个体适应度为选择标准，随机生成初始种群，经历变异、交叉和选择3 个操作算子的计算，但两种算法的上述操作算子的定义并不完全相同.此外差分进化算法的变异操作需要先由父代任意两个个体进行向量差计算，并将加权后的结果与父代第三个个体向量进行向量和计算以生成新的个体向量作为候选，最后将该个体与其父代相应个体进行选择操作[15].

在很多优化问题上，差分进化算法的效果比遗传算法更好.文献[16]利用差分进化算法对分类器集成的权重进行优化并取得了较好效果.

1.3 基学习器：图注意力网络注意力机制(Attention Mechanism)模仿人类选择性地关注信息中的某一部分，并忽略其他从而提高信息处理效率.注意力机制的关键在于对信息设置权重，权重高的信息能够获得重点处理.

图注意力网络是在前述图神经网络基础上引入注意力机制，实现对邻居权重的自动分配从而区分需要重点关注的邻居节点[17].

假设图G=(V,E)，V为结点集，E为边集合，带有注意力机制的图卷积运算[6]定义为：

其中，k代表图神经网络的层编号，表示结点v的特征向量，d为节点特征向量的维数，v∈V，σ(.)为sigmoid 激活函数，N(v)表示v的邻居结点集合，W为可学习的模型参数，为注意力权重，用于衡量结点v与其邻居u之间的连接强度，其计算表达为[18]：

其中g(.)为LeakyReLU 激活函数，a为可学习参数的向量，T 为转置操作.softmax 函数（归一化指数函数）确保注意力权重在节点v的所有邻居上加起来为1.

图注意力网络还可通过多头注意力机制学习不同子空间中的注意力信息，将空间分成M个子空间，同时分别对其运行多个注意力机制函数后再整合[19]，如：

其中，∥ 为连接操作，t为迭代索引编号.

2 优化算法

2.1 模型框架神经网络及其扩展深度神经网络都属于不稳定的基学习器，因而本文使用图注意力网络作为基学习器时，可以采用样本扰动策略来提高集成多样性.

文献[20]表明分类器集成的模型聚合过程中用普通策略例如多数投票法得到的集成预测性能效果往往一般.为了提升分类器集成的效果，本文采用了前文所述的差分进化算法；相对于其他优化方法，在分类器集成的权重矩阵或者向量求解上更加有效.

本文提出的差分进化算法优化的图注意力网络集成（Differential Evolution Optimized Graph Attention Network Ensemble，DEOGATE)流程如图1 所示.流程的全部子过程均由程序自动完成.过程框架分为训练阶段和测试阶段两个阶段.由前文所述，图数据与普通的分类数据有较大不同之处，图数据中节点具有相互依赖关系，因此在预处理时必须先计算图数据的边和邻接矩阵，然后才能进行抽样及后续步骤.后面会根据具体的图数据的特点简述预处理.

图1 差分进化算法优化的图注意力网络集成流程图Fig.1 Flow chart of graph attention network ensemble optimized by differential evolution algorithm

训练阶段包括3 个步骤：首先，计算图数据集的边和邻接矩阵；其次，抽样数据并构建基学习器；再次，采用差分进化算法对分类器集成权重向量进行优化.

测试阶段利用分类器集成的所有基学习器对样本分别预测并通过对应权值组合计算得到预测结果.

图注意力网络集成中的基学习器组合对应的每个候选权重向量由差分进化算法种群中的一个个体所代表.假设数据集共有k个类别，分类器集成中共有L个基学习器，则分类器集成中每个个体x可表示为x=(w1,w2,···,wL).差分进化算法以待优化的目标函数为适应度函数，且只能求函数极小值，因此分类器集成的待优化函数f表示为：

其中，ϕ 为分类器集成的整体准确率，优化算法希望对f函数值最小化.

基学习器的预测输出为矩阵，每行代表一个样本的预测结果.由实验所采用的具体数据集所决定，假设每一行有y列数字，分别代表该列对应类别的概率，则取最大概率值所在列的标签为该样本的输出类别.

样本z属于类别j的加权概率S j(z)为分类器集成中所有基学习器对样本z给出的原始概率的加权值，计算公式如下：

分类器集成的决策规则表示为：

其中，Ω()为聚合函数，其输入为样本z全部类别的加权概率的集合，输出规则为：

即样本z属于类别k仅当其类别k的支持度Sk(z)大于其它任意类别的支持度.

2.2 DEOGATE 算法步骤对于加权投票法的分类器集成，核心问题在于分类器集成中权重向量的求解，一个典型的差分进化算法优化图注意力网络集成的训练过程可以被描述为如下步骤：

输入图数据集；图神经网络超参数；集成算法参数；差分进化算法主要参数.

输出分类器集成预测结果.

步骤 1预处理图数据集；

步骤 2划分数据集为独立的训练集、测试集和验证集；

步骤 3对训练集进行有放回抽样，重复此操作，得到预设个数的训练子集；

步骤 4分别在训练子集上以图注意力网络算法构建基学习器组成分类器集成；

步骤 5在差分进化算法中随机生成若干个个体的初始群体（每个个体代表一个解，其由一组满足约束的权向量组成）；初始化已循环次数；

步骤 6根据公式（4）评估父代个体的适应度；

步骤 7通过变异和交叉操作生成新个体；

步骤 8计算新个体的适应度；

步骤 9比较新个体与父代个体的适应度，如果新个体更好，则将父代对应个体替换为新个体，否则新个体被丢弃；

步骤 10为当前已循环次数增加1；

步骤 11当已循环次数小于迭代次数或者迭代终止误差大于预设值时，重复步骤 7～10，否则输出当前种群中最佳个体对应的权值向量；

步骤 12对应权值组合计算并输出集成预测结果.

该算法不依赖用户输入的健壮性不稳定的超参数，以分类器集成的预测准确率为最终优化目标，优化过程无需度量各基本分类器之间的差异性.

3 实验及结果

本节通过实验验证DEOGATE 模型的有效性，分析讨论实验中的数据特征、相关的参数设置等.文中实验所采用的环境配置：硬件为英特尔 I5-10400f，包含6 核心12 线程，主频2.9 GHz；内存为32 GB，操作系统为Ubuntu 20.04 Linux，深度学习框架为Pytorch，版本号为1.7；图注意力网络模型为Pygat 1.0，来自文献[6]；差分进化算法来自版本号为1.5.2 的Scipy 模块中的differential_evolution优化方法；编程环境为Anaconda 3，运行环境为Python 3.8.5.所有实验均由中央处理器完成计算，没有使用图形处理器.

3.1 数据集及预处理DEOGATE 所采用的基学习器图注意力网络模型支持直推学习（Transductive learning）和归纳学习（Inductive Learning）两种模式.本文实验采用直推学习模式并应用在引文网络数据集Cora[21]的节点分类任务上.图数据集往往仅部分节点有类别标签，直推学习则支持在训练过程中使用其他节点的特征以及节点间的连接关系[22].

Cora 数据集拥有7 个类别，包含2 708 个样本（节点），每个样本代表一篇论文，每篇论文均非孤立：或引用了至少一篇其他论文，或被其他论文引用，这种引用关系用图的边表示，数据集总共包含5 429 条边.所有论文均属于如下类别之一：①案例，②遗传算法，③神经网络，④概率方法，⑤强化学习，⑥规则学习，⑦理论.每个样本均为一个1 433 维的词向量，其中每个元素都对应一个词，用1 或0两种取值表示该元素对应的词在论文中出现与否.

由图数据的特点所决定，Cora 数据的主要预处理步骤包括：①提取特征，转为压缩稀疏行矩阵；②读取数据并提取标签，转为独热（one-hot）编码；③计算样本之间的引用关系并保存为数组；④将非对称邻接矩阵转变为对称邻接矩阵.

为保证训练和测试过程中不同作用的数据子集之间的相互独立，在上述预处理步骤返回的邻接矩阵和特征矩阵里面，随机选取约60%即1 625 条记录用于构建训练集，约20%的数据即541 条记录用于构建测试集，约20%的数据即542 条记录用于构建验证集.在构建分类器集成的基学习器时，每次随机有放回地从训练集抽取约80%的数据即1 300条记录用于不同基学习器的训练.

3.2 参数设置已有研究表明，基学习器数量会影响分类器集成的总体分类性能.集成学习器的整体性能往往随基学习器数量的增加而提高，但并非单调递增，而是达到一个稳定值后在其附近震荡[23].基学习器的数目既要考虑训练代价，也要考虑到有放回随机抽样和参数扰动的特点.

实验分为5 轮，每轮的基学习器个数不同，分别为（5，10，15，20，25）.每轮实验包含两部分.第一部分是基学习器即图注意力网络模型的超参数固定时的测试，第二部分是超参数可变时的测试.测试内容包括不同分类模型的预测能力和DEOGATE 的训练时长.

每轮的差分进化算法主要参数都相同：种群大小为15，变异率为0.5，基因重组率为0.7，最大迭代次数为1 000，迭代终止误差为 1 ×10−7，搜索策略为best1bin.

第一部分的图注意力网络模型主要超参数设定如下：训练次数（epochs）为1 000，学习率为0.005，隐单元数为8，多头注意力（attention heads）个数为8，权重衰减为 5×10−4，耐心度（Patience）为100，丢弃率（dropout）为0.6.第二部分的图注意力网络模型的超参数由人工设定改为在一定范围内随机生成，以检验数据扰动叠加参数扰动后的分类器集成的总体性能.具体而言，图神经网络主要参数随机变化范围：训练次数仍为1 000，学习率为0.001 至0.009，隐单元数为1～9，多头注意力个数为1～9，权重衰减为 1 ×10−4～ 9×10−4，耐心度为50～200，丢弃率为0.1～0.9.

3.3 结果与分析

3.3.1 分类性能 本文实验为多元分类问题，采用了准确率作为评价指标.多元分类问题的准确率计算较一般的二元分类问题稍有不同，为各个类别中被预测正确的样本之和占参与预测的总样本数的比例.

表1 和表2 分别描述了基学习器个数为（5，10，15，20，25）时，图注意力网络超参数在固定时和在随机生成时DEOGATE 的总体输出性能（用准确率表达）；与之对比的是分类器集成内部的多个基学习器的平均准确率和标准差，以及多数投票法集成（记为VoteEnsemble）的准确率.

表1 固定超参数时分类准确率Tab.1 Classification accuracy with fixed super parameters

表2 随机超参数时分类准确率Tab.2 Classification accuracy with random super parameters

表1 数据中的基学习器平均准确率及其标准差展示了基学习器间的区别不太显著，意味着从原始训练集通过有放回抽样得到的数据扰动还不够大；但DEOGATE 在验证集上取得了几乎最好的分类效果，其分类表现相比单个基学习器而言十分稳健，在少数没有取得最好的分类效果时，也能够非常接近集成中效果最好的基学习器.5 轮测试中固定超参数下的DEOGATE 准确率比集成内部基学习器平均准确率高0.001～0.011；同时也以0～0.005的差距持平或领先于多数投票法分类器集成.说明集成方案能够提高图数据的分类准确率，且差分进化算法优化的集成方案比多数投票法方案表现要优秀.

在文献[6]的实验部分，其提出的图注意力网络模型的超参数与本实验第一部分基学习器的超参数相同，该模型对Cora 数据集的分类准确率为（0.83±0.007），已经超过了在此之前表现最优秀的MoNet[24]（0.817±000.5）和GCN[25]（0.815）.本实验第一部分的分类器集成中基学习器的分类准确率比文献[6]高的主要原因是实验目的不同而导致的数据集划分策略不同.本实验需要尽可能地构建多个基学习器，且希望基学习器的学习样本能尽可能多，从而划分给验证集的样本数较少.而文献[6]意图测试直推学习模式下的分类性能，因此划分到测试集的样本较多，为1 000 个.

表2 数据中的基学习器的平均准确率及其标准差展示了基学习器间的准确率差别很显著，说明参数扰动对分类器的性能影响很大.5 轮测试中随机超参数下的DEOGATE 准确率比集成内部基学习器平均准确率高0.053～0.173；并以0.003～0.006的微弱优势领先于多数投票法分类器集成.最后DEOGATE 在多轮验证集上仍然取得了几乎最好的分类效果，但整体性能相比前一轮固定参数时有少量下降.经分析是随机参数导致了部分基学习器性能下降较为明显，从而影响了集成的整体性能.

今后若要实施参数扰动策略，可以考虑利用进化算法快速对基学习器的超参数进行优化，而非完全随机产生；使其既具有一定的差异性，又不会使基学习器的分类性能较人工经验设置参数时的基学习器差太远.

上述5 轮实验的两部分测试结果证明了所提出的DEOGATE 算法在Cora 数据集上超过了基本的图注意力网络和VoteEnsemble 的性能.DEOGATE算法被证明能够起作用，但是提升量有待进一步提高.

3.3.2 构建时长 深度神经网络模型的训练时间一般会非常长，而由其构建的分类器集成的训练时间更可能是个挑战.下述部分主要分析图注意力网络集成的构建时长，实际数据来自于上述5 轮实验所记录的运行时长.

DEOGATE 算法在单机运行环境下，构建时长t的计算表示为：

其中，ϖ(i)为分类器集成中第i个基学习器的训练时长，λ 为差分进化算法对权重向量的优化时长.

在当前硬件配置和固定超参数条件下，训练一个基学习器的时间较为固定，经过测试平均需要121 min.固定超参数时的分类器集成在不同基学习器数目下的总训练时间见图2 虚线.可看出，固定超参数时的分类器集成训练所需时间与分类器集成中基学习器个数成线性增长关系.针对学习时间较长的问题，将来可以训练并行化或利用图形处理器计算.

图2 不同基学习器数目的集成训练总时长Fig.2 Total duration of ensemble training with different number of base learners

与之相对，在当前硬件配置和超参数随机生成条件下，训练一个基学习器的时间变化较大，是因为不同的参数导致图注意力网络的训练时长也不同.超参数随机下的分类器集成在不同基学习器数目下的总训练时间见图2 的实线.

由图2 可见，分类器集成训练所需时间与分类器集成中基学习器个数关系成非线性增长关系.差分进化算法为基于群体的启发式搜索算法，本质为全局随机优化，收敛性分析较为复杂，实际应用中一般是分析其运行时长.图3 虚线显示了超参数固定时不同基学习器数目下差分进化算法的运行时长，实线显示了超参数随机生成时不同基学习器数目下差分进化算法的运行时长.不管超参数固定与否，差分进化算法运行时间随基学习器的数目变大而增长较快，两者为非线性增长关系；但超参数随机下的优化时长相比固定下的优化时长要短，经分析是因为前者情况下基学习器间性能差异大，导致差分进化算法较早达到停止条件.

图3 不同基学习器数目的差分进化优化时长Fig.3 Optimization time of differential evolution with different number of base learners

综合固定超参数与随机超参数时的分类准确率，以及集成训练总时长和差分进化优化时长的比较，若要在分类器集成中生成更多的基学习器，则超参数随机化可视为一个较为经济可行的策略.

4 结语

基于深度神经网络的图数据挖掘在高速发展的同时面临着参数设置、模型质量等诸多挑战，其性能提升研究成为热点.在不改变现有模型下进行分类器集成扩展是一种有效方案，但普通的相同权重投票法存在全局模型准确率欠缺的问题.针对该上述问题，本文提出了DEOGATE 算法，利用差分进化算法全局收敛快、实现简单的优点对图注意力网络集成训练过程中获取全局权重的关键步骤进行改进和优化.首先对图数据集计算边和邻接矩阵，进而划分为训练集、测试集和验证集，再对训练集进行有放回抽样划分为多个子数据集；随后在其上用基于图注意力网络的基学习器进行学习，并结合测试集利用差分进化算法进行集成权重向量的优化.DEOGATE 在Cora 数据上进行验证，结果表明，该方法取得了一定的效果，包括提高了分类模型的准确率和稳健性，并且得出利用参数扰动可在基本保持分类器集成性能的情况下较为明显地减少集成训练时间的结论.

实施过程中实现了一套通用的图注意力集成优化框架以适应更多新的深度图神经网络模型进行接入和测试，同样也支持不同类型的图数据，后续将引入其他图数据集如Citeseer 和Pubmed 进行测试.此外将来可以从多个角度对算法进行改进，包括更有代表性的数据抽样方案，新的异构基学习器集成策略；或引入细粒度的权重优化方案如对基分类器不同类别分别设置权重并优化；或对差分进化算法进行改进，使其更加适合于权重优化问题.