基于图粗化的层次图池化方法研究

陈 洁,薛远远,曹京晶,赵 姝,张燕平

1(计算智能与信号处理教育部重点实验室,合肥 230601) 2(安徽大学 计算机科学与技术学院,合肥 230601) 3(安徽省信息材料与智能传感重点实验室,合肥 230601) 4(科学技术部科技人才交流开发服务中心,北京 100045)

1 引 言

受卷积神经网络(Convolutional Neural Networks,CNNs)在图像目标识别、语音识别和自然语言处理等领域[1-3]成功应用的启发,许多研究人员试图将图卷积运算扩展到图结构数据中,例如社交网络[4]、引文网络[5]和生物网络[6,7]等.近些年来,研究学者们提出了各种GNN模型,它们在图表示学习领域大都取得了显著成功,尤其是在节点级表示学习任务,如节点分类[8,9]和链路预测[10,11]等.然而,如果缺少池化机制,几乎现有的GNN模型都会缺乏学习图层次表示的能力,这使它们在图分类任务[12]中的推广与应用受到很大阻碍.在图数据挖掘领域中,图分类是一个重要的研究方向,许多实际任务中都有相关应用.例如,根据已经存在的化合物的信息预测未知化合物是否有毒以及判断DNA蛋白质是否发生突变等.目前如何将池化操作扩展到图数据吸引了越来越多研究者的关注.

早期一些工作通过全局汇总图中所有节点表示执行图的池化操作.然而采用这种方式生成的图级表示本质上依旧是“平坦的”.它们不能以分层的方式聚合节点表示,也就导致无法有效提取图潜在层次结构中包含的丰富信息.例如Zhang等人[13]提出的排序图池化方法SortPool,该方法首先根据图中节点的角色将节点重新排列为有意义的顺序,然后再进行池化操作.

最近有一些工作专注于GNNs中的分层池化过程,旨在学习图的层次表示,获得更完备的图级表示.本文根据模型建模方式将这些方法分为两大类:基于采样的层次图池化方法和基于聚类的层次图池化方法.

基于采样的层次图池化方法[14-16],例如SAGPool算法[14]和Graph U-Nets算法[15],它们主要通过从原始图中选择前k个重要的节点生成更粗粒度的图作为下一卷积层的输入图.然而,采样图中重要节点生成的粗化图可能无法保留关键的局部结构信息,并且会破坏图拓扑结构的完整性.例如,在图中两个不直接相连但共享许多邻居的节点在生成的粗图中可能会变得彼此不可达,这将会阻碍节点之间消息的传递过程.

基于聚类的层次图池化方法[17-20],它们通常将图的池化操作看做是节点的聚类问题,图中的节点被逐层分组合并以实现图的粗化.然而,Ying等人[17]提出的Diffpool算法需要额外的神经网络层计算存储分配矩阵,复杂度较高.另外,该方法采用加和的方式求解粗图中超节点的特征表示不能捕获节点在图中的地位和作用.Ekagra等人[18]提出的自适应感知池ASAP仅在每个子图中区分节点的重要性,并且该方法对图分层聚类后生成的子图之间存在重叠节点.

综上所述,目前基于聚类的层次图池化方法主要存在以下问题:它们或者需要增加额外的神经网络层实现图的粗化,或者没有从全局的角度区分节点的重要性大小.为了解决这些问题,本文提出一种基于图粗化的层次图池化方法HGP-GC.该方法对特征图执行池化过程中主要包括图结构粗化和图属性粗化两大部分.图结构粗化部分并不需要额外的神经网络层即可实现特征图尺寸的缩减.图属性粗化部分利用一个图注意力网络从全局角度捕获节点的重要性.实验证明,HGP-GC在多个基准数据集上的图分类性能相比于基线方法都有不同程度的提升.简而言之,本文的主要贡献可归纳如下:

1)本文提出一种基于图粗化的池化方法HGP-GC学习图的层次表示.该方法同时考虑图拓扑结构信息和节点特征信息捕获节点在全图上的重要性大小.

2)对图执行下采样过程中,HGP-GC不需要引入额外的神经网络层计算存储分类矩阵,而是直接通过定义稀疏位置矩阵记录节点之间的合并关系.

3)本文在5个公共数据集上进行图分类实验,证明了HGP-GC方法与一系列最先进的图池化方法相比在图分类任务中的优越性.

2 相关工作

2.1 图神经网络

近些年来将卷积操作推广到图数据上的一些研究工作,它们大致可以分为两大类:谱方法和空间方法[21].谱方法通过图傅里叶变换和卷积定理定义图卷积运算,主要挑战在于谱域中定义的卷积滤波器未局限于节点域中.例如,谱卷积神经网络(Spectral CNN)[22]是最早提出在图结构数据上构建卷积神经网络的方法,该方法基于卷积定理通过学习卷积核实现图卷积操作,以完成节点之间的信息聚合.小波神经网络(GWNN)[23]用小波变换替代傅里叶变换实现卷积定理,不仅让图卷积神经网络满足了局部性,而且也大大降低了计算的复杂度.为了使图卷积神经网络在半监督学习领域发挥作用,Kipf 等人[8]对切比雪夫网络进行简化并提出一阶图卷积神经网络模型.

与谱方法不同,空间方法在节点域中定义卷积,其卷积定义为位于目标节点附近的所有邻居节点的加权平均函数,主要挑战在于邻域的大小在每个节点之间变化很大.例如,图注意力网络(GAT)[9]通过注意力机制定义聚合函数,将邻居节点的表示以加权和的形式聚合到自身.但节点之间的权重计算依赖于节点的特征表示,因此计算过程中需要加载整个图的节点特征,这阻碍了它在大规模图上的应用.与GAT需要考虑图中全部节点不同,Hamiltoz等人[24]提出图采样聚合网络(GraphSAGE),该方法对邻居节点做随机采样,仅把采样的节点作为相关节点,这就避免了整个图数据的加载.Liang等人[25]从邻域采样和邻域聚合两个角度提出的HGCN模型,该模型根据关系紧密度衡量不同邻居对当前节点的重要程度,选择关系紧密度高的邻居节点进行采样,旨在减少随机采样带来的不确定性.最近,基于置信度的图卷积网络(ConfGCN)[26]认为节点是以一定的置信度为一个标签,因此,CongGCN为图中每个节点学习置信度函数,并将其作用在节点相关性上用于修正聚合函数.

虽然如此,上文中提到的各种GNN模型大多都是用来学习有意义的节点级表示,这些模型由于缺少池化机制而无法提取图的层次结构信息,这严重阻碍了它们在图级表示学习任务中的推广与应用.

2.2 全局图池化方法

为了将图神经网络应用于图级表示学习相关的任务中,需要一种方法汇总学习到的节点表示以生成图的表示.早期的一些方法采用全局池化方式,通过将图中所有节点表示进行融合得到图的表示.它们通常采用的融合方式包括求和(Sum)、最大值(Max)和平均值(Mean).如公式(1)所示,Henaff等人[12]证明,在模型的开始部分执行简单的操作可以减小图的尺寸,降低问题的求解复杂度.其中,k表示卷积层的层数,Hi表示第i个节点的嵌入向量.

(1)

例如Vinyals等人[27]提出SET2SET模型通过LSTM汇总图中所有节点表示实现全局池化操作.Zhang等人[13]提出的排序图池化方法SortPool根据节点在图中的角色将节点重新排列为有意义的顺序,对图执行池化操作后,利用特征图值的最后一个通道将节点表示合并汇总.然而,这些方法不能以分层的方式提取图的特征信息,忽略了图中可能存在的层次结构,不利于研究人员为图级预测任务构建模型.

2.3 层次图池化方法

最近有一些研究工作使用分层池化的方法学习图的特征表示,它们可以分为以下两大类:基于采样的分层池化方法和基于聚类的分层池化方法.

SAGPool[14]和Graph U-Nets[15]两种算法思想相似,它们均是根据图结构信息和节点的属性信息为图中每个节点学习一个标量,以此标量表征节点在图上的重要性程度,对此标量进行排序后选择前k个节点用于生成粗粒度图,从而学习图的层次表示.然而,这种方式尽管很有效,却可能会破坏图结构信息的完整性.

与采样的层次池化方法不同,Ying 等人[17]提出可微图池Diffpool,该方法使用图神经网络学习节点的低维度嵌入向量,然后根据节点的向量表示将图中相似的节点映射到一组簇中,把每一个簇看做超节点生成粗粒度的图作为下一神经网络层的输入图,从而实现以分层的方式推断和聚合节点的信息.然而,Diffpool需要增加额外的神经网络层学习分配矩阵,软簇分配需要存储每一层中的分配矩阵,这导致该方法内存需求较大,限制了其在大规模图上的应用.用于学习图层次表示的自适应结构感知池ASAP,该模型首先对原始图分层聚类,聚类得到的每个簇是由节点及其一阶邻居组成.然后使用注意力机制计算簇中节点重要性得分,依据每个节点的注意力分数选择分数高的簇生成粗化图.然而,ASAP池化方法仅在每个聚类生成的簇,即节点自身及其一阶邻居中区分节点的重要性程度,本文认为这种方式在一定程度上限制了模型对空间信息相关性的捕获能力.

为解决上述挑战,本文提出一种基于图粗化的层次图池化方法HGP-GC.对图执行池化操作时,HGP-GC 不仅能够从全图的角度捕获节点的重要性大小,而且不需要增加额外的神经网络层用于分配矩阵的计算和存储.

3 预备知识

本节对图分类的数学定义以及HGP-GC池化策略实现过程中使用的相关技术进行简单介绍.

3.1 问题定义

对于任意无向图G=(V,ε,X),其中V表示图G的节点集合,|V|=N表示图中共有N个节点,ε表示边的集合.节点vi∈V具有由xi表示的d维特征表示.X∈RN×d表示图节点特征矩阵,A∈RN×d表示图的邻接矩阵,用于定义节点之间的相互连接关系.GP=(VP,EP,XP)为图G经过一次池化操作后的符号表示.Xcoar和Acoar分别表示图Gp的节点特征矩阵和邻接矩阵.

给定数据集D={(G1,y1),(G2,y2),…},图分类的目标是学习一个映射f:G→y,其中G表示输入图的集合,y是与图关联的标签集合.

3.2 图卷积神经网络

图卷积神经网络(GCN)[9]在各种具有挑战性的任务中都表现出了非常高效的性能.因此,本研究中使用GCN模型提取用于图分类任务的节点特征信息.简要回顾其消息传递机制,对于GCN的第l层,它将图G的邻接矩阵A和节点特征矩阵H(l)作为输入,则第l+1卷积层的输出节点特征表示为:

(2)

3.3 图傅里叶变换

传统傅里叶变换[28]将平方可积的函数f(t)表示成复指数函数的积分或级数形式:

(3)

由传统傅里叶变换可知,如果能够在图上找到一组基向量,就可以实现图上的傅里叶变换.

图上傅里叶变换的定义依赖于拉普拉斯矩阵的特征向量,以特征向量作为谱空间下的一组基底,则图上信号x∈Rn的傅里叶变换为:

(4)

(5)

4 基于图粗化的层次图池化方法:HGP-GC

本研究旨在开发一个由卷积层和池化层组成的图神经网络模型,用于提取图结构数据的层次特征信息以应用于图分类任务.为了解决目前层次图池化模型中存在的一些问题,本文提出一种基于图粗化的池化方法HGP-GC.该方法主要由两部分组成:图结构粗化和图属性粗化.

图结构粗化主要解决目前已存在模型训练过程中需要增加额外的神经网络层问题.在利用谱聚类方法对节点聚类后,HGP-GC模型直接通过定义一个位置信息矩阵用于确定超节点之间的连接关系,实现特征图规模的缩小,这使得以分层方式逐层提取图的特征信息成为可能.

图属性粗化利用图注意力网络计算节点在图中的重要性分数,基于该分数更新节点的特征表示获得节点的增强特征表示.然后,使用傅里叶变换原理实现属性粗化.

图1展示了结合HGP-GC方法的图神经网络模型体系结构.图中节点颜色的深浅表示该节点在图中的重要程度,颜色越深表示节点在图中的地位越重要.给定一个输入图,首先利用一个GCN卷积层学习节点的低维嵌入向量.然后注意力层综合考虑节点特征信息和图拓扑结构信息计算节点重要性得分更新节点的特征表示.最后,利用位置矩阵实现图结构粗化,使用傅里叶变换原理实现图属性粗化.该池化方法的具体实现过程如算法1所示.

图1 结合HGP-GC池化方法的图神经网络Fig.1 Graph neural network combined with HGP-GC pooling method

算法1.HGP-GC图池化策略

输入:图G=(V,ε,A)和属性矩阵X

输出:粗图Gp的邻接矩阵Acoar和特征矩阵Xcoar

1. 节点特征表示矩阵:H(l)←f(X,A)

2. 子图集合:C={G1,G2,…,Gk}←谱聚类

3. //图结构粗化

5. //图属性粗化

6. 节点增强特征表示矩阵:X′∈RN×d←注意力层

8. 粗图节点特征矩阵:

return:Acoar,Xcoar

4.1 图结构粗化

图结构粗化是基于子图划分的,目前已有多种方法可以将一个给定图划分成一组不含重叠节点的子图.本文采用谱聚类方法获取子图.图中节点经过聚类后形成一组子图,每个子图看作一个超节点生成粗粒度的图.如何确定超节点之间的连接关系是结构粗化过程中面临的一大问题.

Diffpool算法通过增加额外的神经网络层学习对应每一层的软分配矩阵确定超节点之间的关系,这种方式不但复杂度高,而且存储每次计算得到的分配矩阵导致模型的内存需求较高.不同于Diffpool模型,HGP-GC通过定义每层的稀疏位置信息矩阵S用于记录节点的合并关系.

给定的输入图G,矩阵A∈RN×N和X∈RN×d分别表示其邻接矩阵和节点特征矩阵.用C={G1,G2,…,Gk}表示使用谱聚类方法对图中节点执行一次聚类操作后生成的子图集合.

定义第l层的位置矩阵Sl∈RN×k用于记录图G中的节点在粗图Gp中的位置信息.位置矩阵Sl的具体定义如公式(6)所示:

(6)

那么,卷积神经网络第l层的输入图G经过结构粗化后生成的第l+1层中的粗化图Gp,其邻接矩阵Acoar可以被确定为:

(7)

4.2 图属性粗化

网络中不同的节点起着大小不同的作用,例如社交网络中有意见领袖的大V,交通网络中有至关重要的交通枢纽.本文对网络中节点重要性大小定义了一个指标,用来定量地衡量每个节点在网络中重要性的大小.

对图执行池化操作过程中,为了能够从全图角度捕获不同节点的重要性,HGP-GC采用一种图注意力机制实现.注意力机制可以让模型更关注输入数据中和当前任务更相关的信息,减少了对外部信息的依赖,用来捕获节点特征的内部相关性.

给定输入图节点的特征矩阵X∈RN×d,利用公式(8)计算图中每个节点的重要性分数Sc∈RN×1.利用这种方式计算得到的节点重要性分数能够同时考虑图拓扑结构信息和节点的特征信息.

(8)

(9)

Mk[i,j]=1, 当且仅当Lk(j)=vi

(10)

(11)

(12)

5 实验与结果

为了验证HGP-GC池化方法的性能,本文在图分类任务上与目前相关的先进模型进行了比较.实验结果表明HGP-GC方法的图分类性能相比于基线方法具有更高的分类准确率.

5.1 数据集

本文在5个生物数据集上进行图分类实验,表1总结了实验数据集的详细统计信息.其中Gavg,Cavg,Vavg和Eavg分别代表每个数据集中图的数量、图的标签、节点数量以及边条数的平均值.下面简单介绍一下各个数据集的基本情况.

表1 实验数据集Table 1 Experimental datasets

ENZYMES[29,30]是一个蛋白质三级结构数据集,由BRENDA酶数据库中的600种酶组成,酶的类别是6个EC顶类中的一个.DD[6,7]是一个包含1178个蛋白质结构的数据集,每个图表示一个蛋白质结构,图中的节点代表氨基酸,图的标签表示该蛋白质是酶或非酶.PROTEINS[7,29]是一个包含1113个图的蛋白质数据集,图中的节点表示氨基酸序列的组成部分,图的标签表示该蛋白质是酶或非酶.NCI1和NCI109[31,32]数据集中的每个图表示一个化合物,图中的节点表示化合物的原子,边表示化学键,这两个数据集用于抗癌活性分类.

5.2 对比算法

本文实验部分对比了一些具有代表性和最新的具有不同池化方法的图神经网络模型,主要选择以下6种池化方法作为基线方法:SET2SET[27]、SortPool[13]、DiffPool[17]、Graph U-Nets[15]、SAGPool[14]和ASAP[18].接下来对基线方法进行简单介绍.

SET2SET:该方法建立在GCN的基础上,利用Set2Set方法获得整个图的表示,而不是对所有节点表示求平均值,本质上仍然是“平坦的”.

SortPool:该基线方法提出一种端到端深度学习结构用于图分类.在将节点的特征输入传统的一维卷积之前,首先对节点特征进行排序,而不是对它们进行汇总,能够从全局图拓扑结构中学习图表示.该算法也是“扁平化”的,并不具备提取图层次特征的能力.

DiffPool:该方法是一种可微的图池化方法,它能够以端到端的方式适应各种图神经网络架构,以生成图的层次表示.该算法通过一个逐渐压缩信息的过程得到图的表示,而不是采用先得到所有节点的特征表示后进行全局池化操作一次性得到图的表示.

Graph U-Nets:该方法基于池化层和上采样层构建一个作用在图数据上的编码器-解码器模型.池化层根据节点在可训练投影向量上的投影值对重要节点进行采样,上采样层则依据节点位置信息将图恢复至原始结构.该方法可应用于节点分类和图分类任务.

SAGPool:该方法是一种基于自注意力机制的图池化方法,利用自注意力机制来区分应该保留和应该删除的节点,即采样重要节点构成粗粒度图.

ASAP:该方法是一种稀疏可微的层次图池化方法,它对局部子图进行分层聚类,并利用自注意力机制使模型能够更好的捕捉子图内部节点的重要性,然后选择具有代表性的子图生成粗粒度图,实现对图的下采样操作.

5.3 实验设置及评价指标

实验过程中,每个数据集被随机拆分成3部分,即80%作为训练集,10%作为验证集,10%作为测试集.每次实验重复10次这种随机拆分,并记录10中不同拆分情形下的平均性能作为实验结果.

为了更直观的体现本文所提出模型性能的有效性,根据以往的工作,实验采用广泛使用的评价指标,即图分类的测试准确率来评估模型的分类性能.

5.4 图分类结果

本节将HGP-GC池化方法与上述6种基线方法在5个公用数据集上的图分类结果进行比较,分类结果详见表2.这里需要特别说明:除ENZYMES数据集,其余所有数据集上的图分类结果均引用于文献[18]中.从该表中可以得出以下结论:

表2 HGP-GC模型图分类实验结果Table 2 Experimental results of HGP-GC model graph classification

1)首先,从表中可以观察到一个普遍的结果,即HGP-GC池化方法在所有数据集上的图分类性能均优于其它基线方法.

2)其次,HGP-GC方法与基于采样的层次图池化方法(Graph U-Nets和SAGPool方法)相比,其图分类性能在5个数据集上都有相对较高的提升.这是因为采样图中重要节点压缩特征图的方式可能会忽略图中关键局部结构中的信息,并且会破坏原始图拓扑结构的完整性.

3)最后,HGP-GC方法相比于DiffPool,在DD,NCI1和NCI109数据集上的图分类性能提高了约10%.特别地,与HGP-GC方法较为类似的ASAP方法相比,在ENZYMES数据集上的分类精度提高了约24.97%,其他数据集上的结果也均有不同程度的提高.HGP-GC从全图的角度捕获不同节点的重要性大小,而ASAP算法则只在每个子图中区分节点的重要性后更新节点的特征表示.

5.5 区分节点重要性对模型性能的影响分析

图中不同节点具有不同的地位和角色,重要节点对图级表示学习的作用更为关键,如何有效捕获图中不同节点的重要性大小是图数据挖掘领域的一大挑战.

HGP-GC方法属性粗化部分通过一个注意力层捕获节点在图中的重要性大小.为了验证注意力层对模型性能的影响,本文设计了HGP-GC方法的一种变体方法HGP-GC_noatten,即利用GCN学习节点低维特征表示后,不进行节点重要性的区分,直接利用傅里叶变换对图执行属性粗化.该模型在ENZYMES,DD和NCI1数据集上进行图分类任务,实验结果如表3所示.从表中可以观察到,对图执行属性粗化之前捕获节点的重要性的图分类精确度都有不同程度的提升.

表3 节点重要性对模型的影响Table 3 Influence of node importance on the model

5.6 超参数分析

模型训练过程中,利用注意力层得到节点增强特征表示后,本文使用了傅里叶变换原理对图进行属性粗化.其中子图特征向量个数n为模型的一个关键超参数.为了分析其不同取值情况下对模型图分类准确度的影响,本文通过在不同尺度上改变该超参数来进一步研究分析.图2展示了超参数n取值分别为1,2,3,4情况下HGP-GC方法的图分类准确度.从该图中可以得出以下结论:

图2 超参数n对模型性能的影响Fig.2 Influence of super parameter n on model performance

在数据集DD,NCI1和NCI109上,超参数n的不同取值对模型的图分类结果影响相对平缓,模型具有较好的鲁棒性.而在数据集ENZYMES和PROTEINS上,超参数n取值为2时,模型的图分类精度分别提高了约1.66% 和1.78%,出现这种情况的原因在于这两个数据集中的节点附带了属性信息,使得模型可以捕获更多的节点属性信息.另外,在n取值为4时,部分数据集上的分类准确度有所下降,分析出现这种情况的原因是神经网络模型过拟合问题造成的.

6 结论与展望

图神经网络是机器学习和数据挖掘的一个重要研究领域,利用图神经网络模型提取图潜在层次结构中包含的丰富信息对将其应用于图级任务具有重要意义.本文提出了一种基于图粗化的层次图池化方法HGP-GC.该方法对特征图粗化过程中不需要增加额外的神经网络层即可以记录节点之间的合并关系,而且该方法综合考虑了节点的特征信息和图拓扑结构信息来捕获节点在全图上的重要性程度,旨在突显出关键节点对图级表示的重要作用.本文将HGP-GC池化方法与现有的图神经网络相结合,并以端到端的方式提取图潜在层次结构中包含的丰富信息,学习图的层次表示.在5个公用基准数据集上的图分类实验结果证明了该池化方法的有效性.

使用谱聚类对网络中的节点进行聚类操作时涉及到图拉普拉斯矩阵的分解,时间和空间复杂度相对较高.接下来的工作可考虑寻找一种新的聚类方法降低粗化过程中的复杂度问题,并在更多的任务上评估模型的性能.