融合结构和特征的图层次化池化模型

马涪元，王 英，李丽娜，汪洪吉

1.吉林大学计算机科学与技术学院，长春130012

2.符号计算与知识工程教育部重点实验室（吉林大学），长春130012

3.吉林大学人工智能学院，长春130012

为了定义图卷积操作，研究者们定义了基于谱域和基于空间的图卷积方法，这些方法都涉及沿着图中的边转换、传递和聚合图中的节点信息，在学习节点表示的任务中取得了良好效果。然而，在面对图分类任务时，考虑到图中不同位置和不同状态的节点有着不同的作用，以及图中还可能存在着一些具有特定功能的子结构，仅通过图卷积操作无法利用这些信息。例如，在一个蛋白质图中，分子（图的节点）通过键（图的边）连接，一些由特定分子以及连接它们的键组成的子结构具有特定的功能。这些具有特定功能的局部结构对整个图的表示也十分重要。因此，受卷积神经网络启发，利用图的局部和全局结构获取图表示的层次化池化应运而生。

目前，图的层次化池化研究已有一定成果，主要有两种策略对图进行池化：（1）聚类策略，通过应用聚类算法将当前层的节点分配给若干个聚类，每个聚类将作为池化后下一层的一个节点，池化后节点的表示通过对聚类内部的节点特征进行聚合获得，节点间的连接关系则通过聚合聚类间节点的连接关系获得。（2）采样策略，通过设计一种重要性标准为当前层每一个节点计算一个重要性得分，根据得分选择top-k节点作为池化后下一层的节点，池化后节点的表示为原节点表示与节点得分的一个点积，考虑到抛弃的节点中仍含有大量信息，Zhang 等人[1]提出对被选择的节点进行一次信息传递，将其邻居信息汇聚以获取新节点表示，池化后节点的连接关系为原节点间的连接关系。考虑到被抛弃的大量结构信息以及出现孤立节点的可能性，Zhang 等人[2]提出应用结构学习机制为节点学习新的链接关系。以这两种策略构建层次池化模型取得了较好的效果。

考虑对图数据池化的两种实现策略，聚类策略一般隐式地利用结构信息和节点特征信息，使得其可能产生不合理的分配矩阵，而采样策略在池化节点时仅利用结构信息或是节点特征，节点的重要性仅被从一个方面考虑，没有充分利用图数据中蕴含的信息。因此，本文结合节点特征和图结构提出结构和特征融合池化（structure and feature fusion pooling，SAFPool）。主要贡献如下：

（1）基于聚类策略，分别捕获图结构信息和节点特征信息学习聚类分配，并结合得到最终的聚类分配结果。

（2）SAFPool 模型显式利用图结构信息和节点特征信息为图生成聚类分配矩阵，依照聚类对节点信息进行聚合得到粗化图实现池化。

（3）在相同的模型结构和数据集下，与其他方法相比，SAFPool取得了较好的效果。

1 相关性研究

1.1 图卷积神经网络

图卷积神经网络由于其在处理图结构数据上优异的表现正受到越来越多的关注，目前也已经有了丰富的成果，基于谱域的图卷积神经网络有着坚实的理论基础，其从信号处理的角度看待图数据。Bruna等人[3]将图信号从节点域变换到谱域后根据卷积定理通过点积实现卷积操作，谱域卷积依赖对拉普拉斯矩阵的特征分解，需要耗费大量算力且没有局部化，每次卷积将对所有的节点进行聚合；Defferrard 等人[4]利用切比雪夫多项式，将聚合范围缩减到节点的k阶邻域，同时利用k阶多项式避免了对拉普拉斯矩阵的特征分解，减少了运算复杂度；随着Kipf 等人[5]进一步的简化，将k阶邻域变为仅聚合一阶邻域信息，在效率和效果上取得了极好的效果，基于谱域的图卷积神经网络变得有效实用。基于空间的方法学习卷积神经网络，利用图空间结构即节点间的连接关系对邻域信息进行聚合（例如，消息传递神经网络（message passing neural networks，MPNNs)[6]、Graph-Sage[7]、GAT（graph attention network）[8]、GIN（graph isomorphism network）[9]）。由于图数据不同于图像数据，节点不具有固定的邻域结构，如此便不能如同卷积神经网络一样共享滤波器中的加权参数，其聚合函数只能选择使用不受节点排列顺序影响的函数。不论是基于谱域还是基于空间的图卷积神经网络，其操作都可概括为根据图结构对节点特征信息转换、传递和聚合。

1.2 图层次池化模型

层次化池化模型通过层次结构利用图的全局和局部结构信息得到更有效的图表示，为了利用图的局部结构信息，其在每一个池化层通过聚类或采样策略缩减节点的规模得到一个粗化图。

基于聚类的方法通过利用图中节点和结构信息对节点聚类，将每一个聚类作为池化后的粗化图中的一个节点，通过聚合局部聚类的信息利用图的局部结构。DiffPool[10]在池化层通过图神经网络模块为节点学习聚类分配矩阵，通过聚类分配矩阵聚合同一聚类下的节点特征和聚类间的拓扑结构。EigenPool[11]直接通过谱聚类获得节点分配矩阵，并基于谱域理论通过上采样为聚类学习新的表示。StructPool[12]在获取聚类分配矩阵时，着重考虑节点的邻域节点对其聚类分配的影响，利用条件随机场从结构上考虑节点的邻域节点的聚类分配对节点聚类分配的影响。

基于采样的策略通过为节点计算重要性得分，保留最重要的前k个节点以及它们间的连接关系生成粗化图实现池化。gPool[13]通过计算节点表示在一个与节点表示等长的可训练权重上投影计算节点重要性。SAGPool[14]通过GCN（graph convolutional networks）为节点计算重要性得分，GCN 利用结构信息的同时也隐式利用了节点的特征信息。HGP-SL（hierarchical graph pooling with structure learning）[2]则考虑节点与邻域的信息差异，将与邻域信息差异越大的节点作为越重要的节点。

以上基于聚类的策略在生成聚类分配矩阵时都从图结构信息入手。DiffPool 通过GCN 利用图结构信息，谱聚类则是通过图最小切思想对图进行聚类划分，StructPool 则考虑邻域信息的聚类分配对当前节点的影响。考虑到采样策略中许多模型利用图节点特征信息进行采样并获得了良好的效果，为提升基于聚类策略的模型的效果，本文模型SAFPool在为节点生成聚类分配矩阵时，同时考虑利用图中的结构信息和节点信息，以使模型在分类任务中更加客观和准确。

2 层次化池化模型

为了获得图的表示，全局池化策略利用图卷积神经网络获得节点表示，通过加和、读出、神经网络等方法将图中所有节点的特征聚合得到图的表示。考虑到全局池化没有利用图中丰富的结构信息，所有节点不论位置、属性为形成图的表示发挥同样的作用，本质上十分“平坦”。因此，通过学习卷积神经网络的层次池化模型提出图层次化池化模型，针对图结构数据设计池化操作，以利用图的全局和局部结构信息获取更有效的图表示。为了逐层地捕获图的局部结构，针对图数据的池化操作主要有两种策略：基于聚类策略和基于采样策略。

2.1 基于聚类的层次化模型

由于图数据的结构复杂性，对数据的池化难以直接学习卷积神经网络中的对网格状数据进行池化操作。同时，不同的图拥有不同的节点数和边数，为池化操作的设计带来了更大挑战。为了解决这些问题，Ying 等人[10]开创性地使用聚类方法实现池化，提出DiffPool 模型，在图数据上引入了层次池化操作用以生成图的分层表示，其能够以端到端的方式堆叠图神经网络结构实现与各种图神经网络结构的结合。

给定一个图神经网络模型的输出Z=GNN(A,X)和图的邻接矩阵A∈Rn×n，X∈Rn×d表示节点特征矩阵，其中d是节点特征的维度。池化操作需要定义一种策略输出一张粗化图，该粗化图将包含m＜n个节点，节点间具有带权邻接矩阵A′∈Rm×m和节点嵌入表示Z′∈Rm×d，使得该新粗化图可以用于输入另一个图神经网络层。通过重复该粗化图的过程L次可以构建出一个L层图神经网络的模型，该模型可以输出关于输入图的一系列越来越粗化的图。因此，池化操作需要学习如何利用图神经网络层的输出对节点进行聚类或者池化，如此才能将粗化图作为图神经网络的输入。相较于传统图粗化任务，针对图分类的层次化池化模型面对着更大的挑战，不同于在一张图上进行粗化，图分类任务需要对一组图进行处理，而不同的图具有不同的节点数目、边数目和结构信息，因此，池化操作在实现时必须能够涵盖不同的图且适应不同图结构。

为了利用图神经网络的输出实现聚类，池化操作的关键是在L层的模型中，利用上一层生成的节点表示为当前层学习一个聚类分配矩阵。因此，需要每一层同时提取对图分类有用的节点表示和对层次池化有用的节点表示，并使用图神经网络模块构建对一组图都有效的一般的池化策略。池化操作由两部分构成：（1）根据聚类分配矩阵实现池化；（2）使用图神经网络结构生成分配矩阵。

在得到一层节点到聚类的分配矩阵Sl后，DiffPool 的池化操作根据分配矩阵Sl对这些节点表示进行聚合得到对应聚类的表示，依据l层的邻接矩阵Al，根据不同聚类内包含的节点间的连接关系生成表示每对聚类间连接强度的粗化邻接矩阵。DiffPool 通过将该层节点信息聚合到聚类实现对输入图的粗化。

为了获取在l层进行池化所需要的分配矩阵Sl和嵌入表示矩阵Zl，DiffPool利用两个独立的图卷积神经网络分别生成这两个矩阵，两个图卷积神经网络的输入相同，是从前一层输入l层的节点特征Xl和节点邻接矩阵Al。在l层生成节点嵌入表示的是一个标准图神经网络模块：

该模块将l层中的聚类节点的节点表示传入一个图神经网络模块，进而学习一个关于聚类节点的新的表示Zl。另一方面，在l层生成分配矩阵的是带有Softmax 的另一个图神经网络模块：

其中，Softmax 函数以行方式作用在图神经网络的输出上，GNNl,pool(·)的输出维度是预定义参数，其决定对l层节点分配到多少个聚类（也即l+1 层的节点数），是模型中的超参数。DiffPool 池化层中的两个图神经网络模块接受相同的输入，但各自有着不同的参数且发挥着不同的作用，GNNl,embed(·)用于在l层为l层的节点生成新的表示，GNNl,pool(·)用于在l层为l层节点生成分配矩阵。在第0 层时，池化模型的输入为原始图数据，在l-1 层时，该层生成的分配矩阵维度应设置为1，如此在最后一层将前一层中的所有信息聚合在一起生成最终的图表示。

2.2 基于采样的层次化模型

为了在池化层缩减节点规模，另一种策略是对节点采样，池化层不断地寻找重要节点，卷积层则对这些重要节点的信息进行局部汇聚，最终通过这些采样获取重要节点信息对整张图进行表示。Lee 等人[14]提出SAGPool 使用图神经网络模块计算一个自注意力分数作为选择标准。注意力机制[15]在深度学习模型中广泛使用，这样的机制可以使得模型更多关注重要的特征而较少关注不重要的特征。具体而言，自注意力[16]也被称为内部注意力，其允许输入特征作为自身的注意力要素。SAGPool 通过图卷积神经网络获取自注意力分数，其可以利用不同的图卷积神经网络层，例如使用前文所述的1stChebNet，其自注意力分数的计算可通过如下公式进行：

其中，Xidx,：是对节点特征矩阵的行索引，即仅保留节点特征矩阵中被idx 作为索引选择的节点；Aidx,idx是一个包含行和列的索引，即仅保留邻接矩阵中两个端点都是被idx 作为索引选择的节点的边。Xout和Aout分别作为经过池化的新图的节点表示矩阵和邻接矩阵。SAGPool 通过舍弃所有未被选择的节点的相关信息，仅保留通过自注意力分数选择的节点信息进行池化操作。

3 结构和特征融合池化

本文提出结构和特征融合池化（SAFPool），考虑显式地利用图结构信息和图节点特征信息实现聚类策略。池化层模型主要包含两部分：聚类学习和聚类池化。

3.1 聚类学习

聚类学习是SAFPool 模型的关键，SAFPool 模型同时显式地利用图的结构信息和图中节点特征为节点学习聚类划分，其包含三个组成部分：基于结构的聚类学习（structure-based cluster learning，SBCL）、基于特征的聚类学习（feature-based cluster learning，FBCL）和结构-特征聚类学习（structure feature cluster learning，SFCL）。池化层进行聚类学习过程如图1所示。

图1 池化层聚类学习Fig.1 Cluster learning in pooling layer

池化层进行聚类学习首先需要通过基于结构信息的聚类学习模块和基于节点特征信息的聚类学习模块，基于结构的聚类学习利用图卷积神经网络通过图结构为节点学习聚类分配，基于特征的聚类学习则利用多层感知机通过节点特征为节点学习聚类分配，结构-特征聚类学习则融合二者学习到的聚类表示生成最终的聚类分配。

基于结构的聚类学习：一般来说，一张图中包含着大量的节点和边，蕴含着丰富的结构信息，因此在学习节点的聚类分配时就要考虑充分利用这些信息，图卷积神经网络模块沿着图中的边利用节点的邻域信息对节点表示进行更新，这个过程中通过利用邻域信息，即节点的邻居构成和邻居属性实现对结构信息的利用。因此本文使用图神经网络模块利用图中结构信息为节点学习聚类分配，利用结构信息进行聚类学习可以表示为：

基于特征的聚类学习：在图数据中，节点也往往包含着特征信息，这些特征信息能在很大程度上对节点进行表示，因此直接利用节点的特征信息学习聚类分配也有其必要性。本文通过应用多层感知机来通过节点特征学习聚类分配，公式如下：

结构-特征聚类学习：图卷积神经网络能够高效地利用图结构信息，多层感知机则专注于节点特征信息，为了同时利用这两种方法学习到的聚类分配矩阵，使结果更加客观且具有更好的鲁棒性，在获取从图结构和节点特征信息学习到的聚类分配矩阵后，将两个聚类分配矩阵融合在一起：

其中，权重a是一个预定义的超参数。

3.2 聚类池化

在获取最终的聚类分配矩阵后，将根据聚类分配矩阵实现池化。将层次模型中l层的分配矩阵表示为Sl∈Rnl×nl+1，Sl中每一行对应着l层的nl个节点（或是聚类），每一列则对应着l+1 层的nl+1个聚类，Sl中每一个值对应着该行的l层节点属于该列对应的l+1 层聚类的概率。直观上，分配矩阵Sl为l层的所有节点提供了分配给l+1 层各个聚类的概率。

假设已获取l层的分配矩阵Sl，并将该层的节点邻接矩阵表示为Al，该层的节点嵌入表示用Zl进行表示。给定这些输入，聚类池化将依照分配矩阵将属于各个聚类的节点特征聚合作为聚类表示，将各个聚类包含的节点到其他聚类包含的节点的连接强度聚合作为聚类间的连接强度，以此得到池化后的粗化图。该粗化图的邻接矩阵和嵌入表示分别使用Al+1和Xl+1表示，即(Al+1,Xl+1)=Pool(Al,Zl)。具体而言，其使用以下两个公式进行池化：

整个层次化池化模型是通过将图卷积神经网络模块和池化模块依次堆叠起来建立的，如图2 所示。通过将卷积层和池化层交替堆叠在一起，可以不断地汇聚整张图的信息直到得到整张图的表示，每经过一次池化模型就会在输入的基础上对更高层的局部结构信息进行汇聚，通过读出操作在每一次池化后都将池化结果作为图表示的一部分，可以极好地保留整张图在各个层次上表现出的特征，从而实现同时捕获局部和全局结构得到图的表示。

图2 层次化池化模型结构Fig.2 Illustration of hierarchical pooling model architecture

4 实验

4.1 数据集

为了验证SAFPool模型的有效性，本文使用三个生物信息相关的图分类数据集，选择三个时下较新的层次化池化模型进行对比。

PROTEINS[17]是一个蛋白质图数据集，每张图中的节点表示一个氨基酸，若两个氨基酸之间的距离小于6 埃，则认定代表这两个氨基酸的节点间存在一条边，图的标签则指示该蛋白质是否为蛋白酶。NCI1 和NCI109[18]是抗癌活性分类的两个生物学数据集，其中每张图都表示一个化合物，图的节点和边分别代表原子和化学键。这三个数据集的基本信息如表1 所示。

表1 数据集信息表Table 1 Dataset information table

将数据集按照8∶1∶1 的比例划分为训练集、验证集和测试集，在相同的模型结构和参数设置下运行SAFPool以及当前较新的三个模型。通过对比不同模型的效果对模型的有效性进行验证，同时通过对不同聚类学习模块的学习结果进行可视化，观察模型的创新点即引入的基于特征的聚类学习模块的效果。

4.2 基线方法与实验设置

为了对模型的性能进行检验，本文选择了两个近期工作提出的模型：HGP-SL（hierarchical graph pooling with structure learning）[2]和GSAPool（graph selfadaptive pooling）[1]。由于这两种模型都是基于采样策略实现的，本文又选择了基于聚类策略的Diffpool[10]模型，同时若将本文提出的模型SAFPool中池化层的FBCL 模块移除即可被视为一个Diffpool模型。

HGP-SL 模型通过将三个卷积层与两个池化层交替堆叠构建层次化模型学习图表示，图表示亦通过读出操作聚合各个池化层的局部结构信息获得，卷积层的输出节点表示维度为128。由于HGP-SL 模型使用采样策略实现聚类，其不必执行矩阵乘法操作，可以使用将批次中的图以分块对角矩阵组织在一张图中的形式构建批数据，此时可以依照池化率在池化时为每张图保留不同数目的节点，这里模型设置的池化率为0.5。GSAPool模型同样使用采样策略，由三个卷积层和三个池化层交替堆叠而成，其池化率亦设为0.5。Diffpool 模型使用的聚类策略，同本文模型SAFPool一样由三个卷积层和三个池化层交替堆叠而成，其池化参数也与本文模型SAFPool相同，三个池化层学习的聚类数分别为14、7、1。模型在训练时都采用相同的训练策略，即迭代的epoch数为1 000，并且当模型在验证集上的损失连续50个epoch都不再变得更小时也停止训练，认为得到了最好的模型，激活函数为ReLU函数，参数初始化方法为Glorot Uniform。

4.3 实验结果与分析

本文模型与三个对比基线方法的对比如表2所示。

表2 图分类模型在不同数据集上的对比实验结果Table 2 Comparative experimental results of graph classification models on different datasets 单位：%

表2 中，各个数据集中的最优效果加粗显示，可以看到本文模型SAFPool 在三个数据集上都取得了最优表现。尤其与Diffpool 的对比效果说明在为节点生成聚类分配矩阵时，通过图卷积神经网络利用图结构信息，同时引入多层感知机处理图节点表示信息，为节点生成聚类分配矩阵进行池化可以提升模型效果，证明了池化操作在通过图卷积神经网络利用图结构信息外引入节点特征信息的有效性。

为了更加直观地研究基于特征的聚类学习模块的引入的效果，说明基于节点特征的聚类学习的必要性，本文对基于结构的聚类学习模块、基于特征的聚类学习模块以及结构-特征聚类学习模块在一张图上同一池化层得到的聚类分别进行可视化展示，可视化效果见表3。

表3 SAFPool模型不同模块的聚类分配结果Table 3 Cluster assignment results of different modules of SAFPool

为了对节点的聚类分配可视化显示，本文对节点分配矩阵进行了一定处理，虽然在执行池化操作时一个节点可能属于多个聚类，依照其属于该聚类的概率发挥不同程度的作用，可视化时为了醒目而令节点仅属于分配概率最大的聚类，表3 中展示的图片中节点的颜色就表示节点所属的聚类。从表中可以看出基于结构的聚类学习模块和基于特征的聚类学习模块学习的聚类分配矩阵存在着明显的差别，二者结合得到的聚类分配也与它们的原本分配概率存在较大差别，说明模型引入特征信息生成聚类确实能够带来新的信息，同时对最终的池化结果带来较大的影响。

5 结束语

本文在图卷积之外显式地补充节点特征用于池化，通过实验说明了这种方法的有效性。同时显式利用图结构信息和图中的节点信息生成节点分配矩阵实现聚类策略相较于基线模型取得了较好的效果，尤其与利用图卷积神经网络隐式利用图结构和节点特征信息实现聚类策略的Diffpool 模型对比，充分说明了图中的节点包含的信息对表达图特征具有重要作用。

现实的图数据中含有大量富有意义的局部结构信息，层次化池化模型正是为了利用这些局部结构而提出的。在当前方法中，局部结构的获取是通过端到端的训练获得的，并没有对应上现实数据中具有特定作用的局部结构，是否能将现实数据中的局部结构引入池化操作过程中以提高模型的有效性和可解释性也是十分值得研究的方向。

同时，在训练模型时也可以考虑与一些智能算法[19-20]，如MBO（monarch butterfly optimization）[21]、EWA（earthworm optimization algorithm）[22]、MS（moth search）[23]结合以提高模型的表现。