1、小 型 微 型 计 算 机 系 统 ：年 月 第 期 收稿日期：收修改稿日期：基金项目：国家重点研发计划子课题项目（）资助；国家自然科学基金项目（）资助；安徽省高校自然科学基金项目（）资助 作者简介：陈 洁，女，年生，博士，副教授，会员，研究方向为机器学习、情感计算、三支决策；薛远远，男，年生，硕士研究生，研究方向为机器学习、网络表示学习、图神经网络；曹京晶，女，年生，硕士，助理研究员，研究方向为科技人才信息、科技政策、人才评价；赵 姝（通讯作者），女，年生，博士，教授，会员，研究方向为机器学习、社交网络、粒计算；张燕平，女，年生，博士，教授，会员，研究方向为计算智能与商空间理论、机器学习方法
2、与应用、人工神经网络与智能信息处理基于图粗化的层次图池化方法研究陈 洁，薛远远，曹京晶，赵 姝，张燕平，（计算智能与信号处理教育部重点实验室，合肥）（安徽大学 计算机科学与技术学院，合肥）（安徽省信息材料与智能传感重点实验室，合肥）（科学技术部科技人才交流开发服务中心，北京）：摘 要：图神经网络（，）已被证明能有效对图结构数据进行建模，池化机制在使用 模型提取图层次特征过程中至关重要，近年来已经引起了越来越多研究者们的关注 现有基于聚类的层次图池化方法要么需要增加额外的神经网络层以实现特征图的粗化；要么不能从全局角度捕获节点在图中的重要性大小 针对以上问题，本文提出一种基于图粗化的层次图池化方
3、法（，），用于学习图的层次特征表示 该方法主要包括图结构粗化和图属性粗化两个部分 利用结构粗化实现特征图尺寸的缩减；利用属性粗化突显图中重要节点对图级表示的关键作用 通过将 池化策略与现有神经网络相结合，在不同规模公共数据集上的图分类实验结果证明了 的有效性关 键 词：图神经网络；图池化；层次图表示学习；节点重要性；图分类中图分类号：文献标识码：文 章 编 号：（），（，）（，）（，）（，）：，：，：；引 言受卷积神经网络（，）在图像目标识别、语音识别和自然语言处理等领域成功应用的启发，许多研究人员试图将图卷积运算扩展到图结构数据中，例如社交网络、引文网络和生物网络，等 近些年来，研究学者们提
4、出了各种 模型，它们在图表示学习领域大都取得了显著成功，尤其是在节点级表示学习任务，如节点分类，和链路预测，等 然而，如果缺少池化机制，几乎现有的 模型都会缺乏学习图层次表示的能力，这使它们在图分类任务中的推广与应用受到很大阻碍 在图数据挖掘领域中，图分类是一个重要的研究方向，许多实际任务中都有相关应用 例如，根据已经存在的化合物的信息预测未知化合物是否有毒以及判断 蛋白质是否发生突变等 目前如何将池化操作扩展到图数据吸引了越来越多研究者的关注早期一些工作通过全局汇总图中所有节点表示执行图的池化操作 然而采用这种方式生成的图级表示本质上依旧是“平坦的”它们不能以分层的方式聚合节点表示，也就导致
5、无法有效提取图潜在层次结构中包含的丰富信息 例如 等人提出的排序图池化方法，该方法首先根据图中节点的角色将节点重新排列为有意义的顺序，然后再进行池化操作最近有一些工作专注于 中的分层池化过程，旨在学习图的层次表示，获得更完备的图级表示 本文根据模型建模方式将这些方法分为两大类：基于采样的层次图池化方法和基于聚类的层次图池化方法基于采样的层次图池化方法，例如 算法和 算法，它们主要通过从原始图中选择前 个重要的节点生成更粗粒度的图作为下一卷积层的输入图 然而，采样图中重要节点生成的粗化图可能无法保留关键的局部结构信息，并且会破坏图拓扑结构的完整性 例如，在图中两个不直接相连但共享许多邻居的节点在
6、生成的粗图中可能会变得彼此不可达，这将会阻碍节点之间消息的传递过程基于聚类的层次图池化方法，它们通常将图的池化操作看做是节点的聚类问题，图中的节点被逐层分组合并以实现图的粗化 然而，等人提出的 算法需要额外的神经网络层计算存储分配矩阵，复杂度较高 另外，该方法采用加和的方式求解粗图中超节点的特征表示不能捕获节点在图中的地位和作用 等人提出的自适应感知池 仅在每个子图中区分节点的重要性，并且该方法对图分层聚类后生成的子图之间存在重叠节点综上所述，目前基于聚类的层次图池化方法主要存在以下问题：它们或者需要增加额外的神经网络层实现图的粗化，或者没有从全局的角度区分节点的重要性大小 为了解决这些问题，
7、本文提出一种基于图粗化的层次图池化方法 该方法对特征图执行池化过程中主要包括图结构粗化和图属性粗化两大部分 图结构粗化部分并不需要额外的神经网络层即可实现特征图尺寸的缩减 图属性粗化部分利用一个图注意力网络从全局角度捕获节点的重要性 实验证明，在多个基准数据集上的图分类性能相比于基线方法都有不同程度的提升 简而言之，本文的主要贡献可归纳如下：）本文提出一种基于图粗化的池化方法 学习图的层次表示 该方法同时考虑图拓扑结构信息和节点特征信息捕获节点在全图上的重要性大小）对图执行下采样过程中，不需要引入额外的神经网络层计算存储分类矩阵，而是直接通过定义稀疏位置矩阵记录节点之间的合并关系）本文在 个公
8、共数据集上进行图分类实验，证明了 方法与一系列最先进的图池化方法相比在图分类任务中的优越性 相关工作 图神经网络近些年来将卷积操作推广到图数据上的一些研究工作，它们大致可以分为两大类：谱方法和空间方法 谱方法通过图傅里叶变换和卷积定理定义图卷积运算，主要挑战在于谱域中定义的卷积滤波器未局限于节点域中 例如，谱卷积神经网络（）是最早提出在图结构数据上构建卷积神经网络的方法，该方法基于卷积定理通过学习卷积核实现图卷积操作，以完成节点之间的信息聚合 小波神经网络（）用小波变换替代傅里叶变换实现卷积定理，不仅让图卷积神经网络满足了局部性，而且也大大降低了计算的复杂度 为了使图卷积神经网络在半监督学习领
9、域发挥作用，等人对切比雪夫网络进行简化并提出一阶图卷积神经网络模型与谱方法不同，空间方法在节点域中定义卷积，其卷积定义为位于目标节点附近的所有邻居节点的加权平均函数，主要挑战在于邻域的大小在每个节点之间变化很大 例如，图注意力网络（）通过注意力机制定义聚合函数，将邻居节点的表示以加权和的形式聚合到自身 但节点之间的权重计算依赖于节点的特征表示，因此计算过程中需要加载整个图的节点特征，这阻碍了它在大规模图上的应用 与 需要考虑图中全部节点不同，等人提出图采样聚合网络（），该方法对邻居节点做随机采样，仅把采样的节点作为相关节点，这就避免了整个图数据的加载 等人从邻域采样和邻域聚合两个角度提出的 模
10、型，该模型根据关系紧密度衡量不同邻居对当前节点的重要程度，选择关系紧密度高的邻居节点进行采样，旨在减少随机采样带来的不确定性 最近，基于置信度的图卷积网络（）认为节点是以一定的置信度为一个标签，因此，为图中每个节点学习置信度函数，并将其作用在节点相关性上用于修正聚合函数虽然如此，上文中提到的各种 模型大多都是用来学习有意义的节点级表示，这些模型由于缺少池化机制而无法提取图的层次结构信息，这严重阻碍了它们在图级表示学习任务中的推广与应用 全局图池化方法为了将图神经网络应用于图级表示学习相关的任务中，需要一种方法汇总学习到的节点表示以生成图的表示 早期的一些方法采用全局池化方式，通过将图中所有节点
11、表示进行融合得到图的表示 它们通常采用的融合方式包括求和（）、最大值（）和平均值（）如公式（）所示，等人证明，在模型的开始部分执行简单的操作可以减小图的尺寸，降低问题的求解复杂度 其中，表示卷积层的层数，表示第 个节点的嵌入向量 （，）（）例如 等人提出 模型通过 汇总图中所有节点表示实现全局池化操作 等人提出的排序图池化方法 根据节点在图中的角色将节点重新排列为有意义的顺序，对图执行池化操作后，利用特征图值的最后一个通道将节点表示合并汇总 然而，这些方法不能以分层的方式提取图的特征信息，忽略了图中可能存在的层次结构，不利于研究人员为图级预测任务构建模型 层次图池化方法最近有一些研究工作使用分
12、层池化的方法学习图的特征 小 型 微 型 计 算 机 系 统 年表示，它们可以分为以下两大类：基于采样的分层池化方法和基于聚类的分层池化方法和 两种算法思想相似，它们均是根据图结构信息和节点的属性信息为图中每个节点学习一个标量，以此标量表征节点在图上的重要性程度，对此标量进行排序后选择前 个节点用于生成粗粒度图，从而学习图的层次表示 然而，这种方式尽管很有效，却可能会破坏图结构信息的完整性与采样的层次池化方法不同，等人提出可微图池，该方法使用图神经网络学习节点的低维度嵌入向量，然后根据节点的向量表示将图中相似的节点映射到一组簇中，把每一个簇看做超节点生成粗粒度的图作为下一神经网络层的输入图，从
13、而实现以分层的方式推断和聚合节点的信息 然而，需要增加额外的神经网络层学习分配矩阵，软簇分配需要存储每一层中的分配矩阵，这导致该方法内存需求较大，限制了其在大规模图上的应用 用于学习图层次表示的自适应结构感知池，该模型首先对原始图分层聚类，聚类得到的每个簇是由节点及其一阶邻居组成 然后使用注意力机制计算簇中节点重要性得分，依据每个节点的注意力分数选择分数高的簇生成粗化图 然而，池化方法仅在每个聚类生成的簇，即节点自身及其一阶邻居中区分节点的重要性程度，本文认为这种方式在一定程度上限制了模型对空间信息相关性的捕获能力为解决上述挑战，本文提出一种基于图粗化的层次图池化方法 对图执行池化操作时，不仅
14、能够从全图的角度捕获节点的重要性大小，而且不需要增加额外的神经网络层用于分配矩阵的计算和存储 预备知识本节对图分类的数学定义以及 池化策略实现过程中使用的相关技术进行简单介绍 问题定义对于任意无向图 （，），其中 表示图 的节点集合，表示图中共有 个节点，表示边的集合 节点 具有由 表示的 维特征表示 表示图节点特征矩阵，表示图的邻接矩阵，用于定义节点之间的相互连接关系 （，）为图 经过一次池化操作后的符号表示 和 分别表示图 的节点特征矩阵和邻接矩阵给定数据集 （，），（，），图分类的目标是学习一个映射：，其中 表示输入图的集合，是与图关联的标签集合 图卷积神经网络图卷积神经网络（）在各种具
15、有挑战性的任务中都表现出了非常高效的性能 因此，本研究中使用 模型提取用于图分类任务的节点特征信息 简要回顾其消息传递机制，对于 的第 层，它将图 的邻接矩阵 和节点特征矩阵（）作为输入，则第 卷积层的输出节点特征表示为：（）（，）（?（）（）（）其中，（）表示非线性激活函数?等于 ，是单位矩阵?是?的度矩阵，?是当前层的节点特征矩阵，对于输入层，是输入图的属性矩阵（）是第 层中的可学习参数矩阵 图傅里叶变换传统傅里叶变换将平方可积的函数（）表示成复指数函数的积分或级数形式：（）（）（）（）由传统傅里叶变换可知，如果能够在图上找到一组基向量，就可以实现图上的傅里叶变换图上傅里叶变换的定义依赖于
16、拉普拉斯矩阵的特征向量，以特征向量作为谱空间下的一组基底，则图上信号 的傅里叶变换为：（）其中，指信号在空间域的原始表示 指信号 变换到谱域后的表示 表示特征向量矩阵的转置，用于傅里叶变换 因此，信号 的傅里叶逆变换可以表示为：（）基于图粗化的层次图池化方法：本研究旨在开发一个由卷积层和池化层组成的图神经网络模型，用于提取图结构数据的层次特征信息以应用于图分类任务 为了解决目前层次图池化模型中存在的一些问题，本文提出一种基于图粗化的池化方法 该方法主要由两部分组成：图结构粗化和图属性粗化图结构粗化主要解决目前已存在模型训练过程中需要增加额外的神经网络层问题 在利用谱聚类方法对节点聚类后，模型直接通过定义一个位置信息矩阵用于确定超节点之间的连接关系，实现特征图规模的缩小，这使得以分层方式逐层提取图的特征信息成为可能图属性粗化利用图注意力网络计算节点在图中的重要性分数，基于该分数更新节点的特征表示获得节点的增强特征表示 然后，使用傅里叶变换原理实现属性粗化图 结合 池化方法的图神经网络 图 展示了结合 方法的图神经网络模型体系结构 图中节点颜色的深浅表示该节点在图中的重要程度，颜色越深表示