【图神经网络】图分类学习研究综述[2]：基于图神经网络的图分类
基于GNN的图分类学习研究综述[2]：基于图神经网络的图分类
论文阅读：《基于图神经网络（GNN）的图分类学习综述》
第3章 基于图神经网络的图分类
3.1 卷积操作
3.2 池化操作
论文阅读：基于GNN的图分类学习研究综述
摘要
关键词 ：图分类、图核、图卷积；图池化；图神经网络
3. 基于图神经网络的图分类
大多数图核方法往往依赖于一组固定的表征形式。然而，在面对变化的数据场景时这种固化的特征表示往往难以有效适应。本研究特别关注基于图神经网络的图分类问题，在这一领域中我们探索了一种全新的学习策略以显著提升了该任务的整体准确性。
基于图像分类任务的传统卷积神经网络模型主要由卷积层与下采样层两部分构成，在设计这些层时依据的是图像数据所具有的固有结构性规律及平移不变性的假设。然而，在实际应用中发现传统方法难以适应更为复杂的非欧几里得空间中的图数据分析特点。具体而言，在同一规模及拓扑结构各异的数据集中处理不同规模及拓扑结构的图节点集合时会遇到诸多本质性的技术难题，在构建适用于图数据分析的卷积核与降维机制时面临诸多本质性的技术难题
给定一组图的数据，在应用基于图神经网络的分类算法时，算法会通过卷积操作逐步提取特征。随后对提取到的特征进行降维处理，并有效降低了数据量。这一过程可循环迭代执行下去直至完成全部特征抽取工作。最终构建出完整的节点表示向量，并以便实现对图像类别的识别目标。
本节主要从卷积算子和池化算子两个核心组件出发，在此基础上系统性地总结与分析了基于图神经网络的图分类方法。通过图5可以看出，在该框架中可选的功能单元及模块采用虚线标示，在循环层结构则由环形箭头指示。
3.1 卷积
在图级别任务中进行图卷积操作旨在完成图数据的特征提取与变换任务，在这一过程中需要充分挖掘节点特征以及拓扑关系信息以提升模型性能。目前在图分类任务中主流的卷积架构可分为两类：其一是基于信息传递（message-passing）机制的设计方案，在这种架构下直接在原始图结构上构建由邻居信息聚合与迭代更新机制构成的卷积算子，并结合注意力权重分配实现多尺度特征融合；其二是以传统计算机视觉中的CNN（Convolutional Neural Network）为基础的设计方案，在这种架构下首先需要将非欧氏空间中的图数据映射到规则网格结构上然后再通过传统CNN框架进行标准的空间域局部线性变换
（1）信息传递式卷积
Gilmer等提出了信息传递式（MPNN）的通用框架，将卷积过程形式化为信息传递和节点信息更新两个函数。信息传递是指各个节点将自己邻居的信息聚合到自身节点，节点信息更新是将该节点上一层的节点表示与聚合后的邻居信息进行结合的过程。本文把符合这种框架的卷积方式称为信息传递式（MPNN）卷积。
在图分类任务中，信息传递式卷积用来进行特征变换，得到图上节点的表示。以Kipf等提出的图卷积网络GCN为例：
H^{(l+1)}=\sigma (\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})
其中，H^{(l)}是l层中节点的表示矩阵，W^{(l)}是可训练的参数矩阵，\widetilde{A}=A+I_N表示包含自连接的邻接矩阵，\sigma表示非线性激活函数。
这类图分类模型通常首先通过提取节点特征以及图的结构信息来生成经过特征映射后的节点表示。这些方法均采用了基于信息传递机制的GCN架构来进行节点表示学习过程。除此之外，在DiffPool框架下其卷积模块支持灵活选择不同类型的MPNN卷积架构。其中Zhang等提出的方法在设计上与传统的GCN有所不同主要体现在其特殊的池化策略上：这类模型通常首先通过提取节点特征以及图的结构信息来生成经过特征映射后的节点表示；随后结合特定的池化操作获得全局表征并完成分类任务；其中具体的卷积操作定义为Z=f(tilde{D}{-1}tilde{A}XW)这里的tilde{A}与传统GCN定义一致而tilde{D}是一个度矩阵且其对角线元素tilde{D}{ii}=sum_j tilde{A}_{ij}该公式中的W属于R^{c×c'}是一个可训练的学习参数矩阵；研究者们进一步证明了这种设计在理论上相较于传统的GCN架构更接近于Weisfeiler-Lehman算法这一重要的图神经网络基准方法。Ying等则提出了基于微分池化的可学习性增强方法：在DiffPool框架下其卷积模块支持灵活选择不同类型的MPNN卷积架构从而实现了对复杂图结构的有效建模能力
在上文中所提及的各种模型中,这些图卷积网络的设计均源自于上文所述的一阶Weisfeiler-Lehman（1-WL）算法.然而研究者们指出,基于一阶Weisferlman信息传递机制构建的图卷积神经网络,其表达能力受限于一阶Weisfeiler-Lehman（1-WL）算法.具体而言,对于许多非同构图而言,该类信息传递式架构无法实现精确区分.进一步分析可知,当一阶Weisferlman算法判定两个非同构图具有潜在结构相似性时,基于此类架构设计的信息传递机制仍会导致这两幅图像对应的表征向量产生相同输出.这种有限的区分能力会对图分类任务的效果产生显著负面影响.
近年来，在研究领域取得了一系列进展的基础上
其中，
N(s)=\{t\in[V(G)]^k \mid |s\cap t|=k-1\}
，
用于描述集合s与邻居集合t之间的交集大小关系。
其表达能力与set k-WL算法具有相似的强度。
该模型需枚举大小为k的子图结构，
但由于计算复杂度较高的限制，
目前仅考虑了k等于1、2、3的情形，
并构建了一种分层递进式的1-2-3GNN网络架构。
在图分类任务中表现出色，
在单一层次上的表现优于传统1-GNN模型。
Maron等研究者通过矩阵相乘的方式实现了类似于3-WL区分能力的GNN模型构建，
这种方案不仅降低了空间复杂度，
还具备更加便捷部署的优势。
目前，在评估图卷积神经网络的表现时，通常会参考其是否能识别同构图的能力。
CNN式卷积指的是先将原始非欧式的图数据按照特定规则转换到欧式空间后执行传统意义上的二维卷积操作。
Niepert及其团队研究表明：
然而由于大多数节点不具备统一的空间排列方式这一假设往往无法准确反映真实世界中的复杂情况。
Niepert等提出了PSCN模型来转化非欧图数据为欧式数据，并通过节点选择的方法来解决不同图数据中的节点数量不一致的问题。具体而言，在每个具体的网络中应用图标记算法按照某种排序标准对所有节点进行排序。这样做的目的是让来自不同网络但具有相似结构的节点在序列中的位置也具有相似性。随后从中选取一定数量的节点作为代表。该模型通过宽度优先搜索的方式聚合邻居信息并进行排序，在无序的空间中构建出一个具有线性顺序的向量空间。接着在这个序列中选取一定数量作为中心节点的感受野区域。由于最优化的标准化问题是NP-hard的问题，在众多图标记方法中选择了效果较好的方案，并借助辅助工具对邻居关系中的节点进行了定序处理后得到统一表示。之后使用了一维卷积层来进行卷积操作，在卷积核大小与感受野大小相同的前提下完成特征提取和其他卷积和分类模块的设计
为了应对图中节点数量不一的问题（...），本研究中的PSCN模型采用了特定的节点选择策略。这种策略使得在后续的卷积操作中难以实现多层堆叠（...），从而只能提取出局部关键结构（...）。直观上来说，在第二次卷积时发现（...），因此缺少这些节点的信息（...），导致无法完成第二次卷积操作（...），因而也无法提取到全局的重要结构（...）。针对这一问题（...），Tzeng团队提出了一种称为Ego-CNN的新架构（如图7所示）。该方法能够有效识别图中的局部和整体关键结构（如图7所示）。
不同于PSCN（基于空间邻域的卷积神经网络），Ego-CNN（基于自我中心的卷积网络）采用了不同的初始化方法和邻居选择策略。具体而言，在输入图中所有节点经过网络嵌入算法生成初始表达后（这一过程避免了传统方法中对节点选择的依赖），Ego-CNN会对每个节点选择指定数量的邻居并将其表达信息连接作为感受野的基础。接着通过与相同尺寸的感受野进行多层卷积操作完成特征提取。这种卷积过程可被数学公式表示如下：
H^{(l)}_{n,d} = \sigma (E^{(n,l)} \cdot W^{(l,d)} + b^{(l)}_{d})
其中E^{(n,l)} = [H^{l-1}_{n,:}, H^{(l-1)}_{Nbr(n,1),:}, ..., H^{l-1}_{Nbr(n,K),:}]^T表示节点n在l层的邻居表示矩阵。该矩阵由节点n及其前K个最近邻居在l-1层的空间表示构成，并且这些邻居关系是在模型初始化阶段就已确定并保持不变（即Nbr(n,K)）。\sigma为激活函数，b_d为偏置项；\cdot代表Frobenius内积（定义为两个矩阵对应元素乘积之和）。值得注意的是，在这种设计下与PSCN相比虽然卷积操作原理相同但两者的区别主要体现在两方面：第一是邻居的选择方式不同——Ego-CNN采用固定的K阶邻居定义而PSCN则基于动态的空间邻域；第二是多层卷积的操作方式——由于Ego-CNN未提前筛选节点因此其聚合后的邻居表示能够更充分地利用已有信息避免了PSCN可能出现的某些特定情况（如某类节点在某一层不存在的情况）。此外通过重复利用上一层节点的空间表示特征在每一层的操作中模型都能够聚焦于当前中心点附近的不同范围结构从而实现对重要结构特征的有效捕捉最终实现结果的关键部分可以通过反卷积的方式进行可视化展示
PSCN和Ego-CNN都对节点进行了卷积操作，在这一过程中充分运用了网络拓扑结构的信息。与之不同的是，在将图表示为矩阵时有效地捕捉到丰富结构性信息的是Peng等人提出的一种称为MA-GCNN的新模型。具体而言，在这一过程中充分运用了网络拓扑结构的信息。
在对图数据进行预处理时，该模型通过某种选择策略识别出N个关键节点，并对这些节点各自选取K个具有重要关联性的邻居节点来生成N个子图集。随后系统将这些子图集转化为基于2-跳路径 motif 的矩阵表示，在此过程中通过匹配得到的多个 motif 构建子图表示，并将各子图间的表示进行连接从而形成整个图的数据表征。
研究表明，在该模型的设计中，默认情况下会通过motif匹配机制来保留子图中的连边信息。这一过程即为：初始表示中通过motif匹配机制来提取并保留子图中的连边信息。随后基于此设计思路，默认情况下会对该矩阵执行两次不同尺度的感受野卷积操作，并结合子图级别的注意力机制来生成重要子结构组成的表征进而完成分类任务。从直观来看，在图分类任务中采用子图级别注意力机制相比节点级别更容易实现可解释性目标。实验结果表明，在实际运行过程中基于子图的卷积运算确实能够获得更好的分类效果这进一步验证了该模型在预处理过程中有效提取了空间结构特征并实现了性能优势
但值得注意的是与PSCN类似该模型也采用了节点筛选过程其中节点选择过程相当于一次池化操作这一做法直接导致了一部分重要的局部结构信息被舍弃掉
对比这两种卷积方法，在MPNN架构中假设相邻节点具有相同的标签。从而采用了基于邻居信息的传递机制，这种机制是从单个节点的角度出发特别适合用于节点级别的分类任务。然而，在CNN式卷积架构中存在参数过多导致模型难以捕捉所有关键结构特征的问题。目前尚不清楚哪种类型的卷积方法最适合图分类任务，也不知道什么样的卷积架构能够最有效地利用图中的结构信息进行分类。接下来仍然需要探索这一领域的发展方向
3.2 池化
传统卷积网络中的池化过程也被称为降维处理，在神经网络模型训练过程中能够有效降低特征维度的同时优化参数规模，并且能够显著扩大感受野的范围。由于图像数据中各像素点的空间结构具有高度统一性，在传统的卷积神经网络设计中其池化操作在处理空间结构信息时通常较为简单直观，并主要包含最大值池化、加和池化以及平均值池化的具体实现方式。
在图像分类任务中,池化操作通常与不同类型的卷积层协同工作,以减少特征空间的复杂度,从而提取整体图像的表征信息。
与图像数据不同，在图数据处理中，在对各个节点的局部拓扑特征进行提取时（即池化过程中），需要充分考虑各节点独有的局部特征信息。
池化过程涉及对图进行粗化处理；通过将具有相似特征的节点进行聚类，从而必须为简化后的图重新定义合理的邻居关系。通常分为两个主要步骤：
- 第一步,求分配矩阵 ,分配矩阵决定哪些邻居聚类在一起形成聚类簇. 分配矩阵S^{(l)}\in R^{n_{l}\times n_{l+1}}是第l层节点分配到l+1层不同的聚类簇中的指示矩阵.矩阵的行表示节点,共有n_{l}个.列表示粗化后的聚类簇,共有n_{l+1}个.
- 第二步,按照分配矩阵进行聚合 ,即选定聚类簇中节点的聚合方式并将每个聚类簇聚合为一个新的超节点,所有的超节点构成新的图.通常在最直接的聚合方式下,新图的特征矩阵由X^{(l+1)}=S^{(l)T}X^{(l)}得到,邻居矩阵由A^{(l+1)}=S^{(l)T}A^{(l)}S^{(l)}得到. 当然,很多模型会提出新的更复杂的聚合方式.
该文以分布矩阵为基础，在图分类领域的降维技术研究中进行了系统性分析，并详细阐述了具体的分配机制及融合方式。
该方法通过节点硬分配实现图结构数据的有效聚类与压缩. 具体而言, 硬分配矩阵是从行维度定义的一种二值化分配形式, 其中每行仅有一个元素为1,其余均为0. 这种设计确保每个节点精确归属至单一聚类簇中. 马等人提出的谱池化(EigenPooling)方法基于谱聚类技术生成硬分配矩阵S^{(l)}, 并以此进行子图划分. 该过程将原图划分为若干互不重叠的子图簇,并将每个子图视为超节点. 子图之间的邻接关系则由A^{(l+1)}=S^{(l)T}A^{(l)}S^{(l)}公式确定. 在特征聚合阶段,EigenPooling并非直接采用分配矩阵作为池化算子,而是通过对子图特征进行分解并整合特征向量生成多个池化算子. 最终, 超节点表示可由池化算子\Theta_{l}作用于原始特征表示X, 即X_l=\Theta_{l}^TX. 多个池化算子得到的不同超节点表示经过拼接处理后形成最终表征. 从局部视角来看,这一过程相当于对子图上的信号执行傅里叶变换;从全局角度分析,则相当于应用滤波器对整个图信号进行处理. 这种设计保留了良好的恢复能力与信息保持特性:既能精确恢复原始信号,又能有效维持网络中的关键信息含量. 图8展示了基于信息传递型图卷积与EigenPooling框架实现的图像分类流程.
Wu及其团队则指出，在图中具有相同度值的节点可能存在类似的结构性信息。为了保留与这些高关联性相关联的信息特征,Wu等人开发了一种称为DEMO-Net的新方法。该模型在聚类过程中,将所有具有相同度值且相邻连接起来的关键点聚合成一个超单元,并通过特征融合的方式实现了对这些关键点的高度抽象概括;这种聚类方式也与基于硬分配矩阵的方法一致。
Diehl等人的研究提出了EdgePool方法，该方法通过分析边的重要性来决定哪些节点应被合并成一个虚拟节点。具体而言，在池化操作中，EdgePool首先会对每条边进行评估并排序，在此基础上选择连接性最强的边，并将这两端的节点聚合成一个新的虚拟节点。值得注意的是，尽管该方法并未明确定义分配矩阵（A），但其操作实质上属于节点硬聚类池化过程。
此外，在关注这些基本概念的同时,一些简单的置换不变(permutation invariant)函数(如加和池化与最大池化等),也可被视为一种基于节点硬分配机制的应用实例.
在基于节点硬分配的图池化模型中,生成节点嵌入表示后,通常会依据图聚类方法或特定规则将节点归纳为簇,确保每个节点仅归属于一个簇.该种池化机制所得的图表示高度依赖于节点聚类规则,但在实际应用中,可能会出现聚类规则与分类任务之间存在不适配的情况,从而对图分类性能产生影响.
(2) 节点软分配与聚合
节点的软聚类划分是一种将图中的节点划分为若干可能相互交叉的簇群的方法,即每个节点可能同时归属于多个簇.从行向量的角度分析,该方法的核心在于构建一个概率分布矩阵,其中每一行代表一个节点,其元素取值范围在0到1之间.具体而言,对于第j个簇,元素p_{ij}表示的是该节点i对该簇j的概率隶属度.基于参数化的可微池化架构,Ying等提出了一个有效的网络设计框架.该框架由编码器与解码器两部分构成:编码器分支负责提取节点在当前层次信息特征,而解码器分支则生成对应的聚类概率分布矩阵.整个过程如图9所示:首先通过编码器获取各层次的信息表示;接着利用池化操作生成聚类关系映射.
计算第l层节点表示及 soft assignment matrix后, 通过公式 X^{(l+1)} = S^{(l)T} X^{(l)} 和 A^{(l+1)} = S^{(l)T} A^{(l)} S^{(l)} 分别获得粗化图的节点表示与邻接矩阵. 然而, 该模型采用学习方法获取 soft assignment matrix时, 仅依赖于图分类任务返回的梯度信息难以有效训练可微分池化图神经网络架构.
为了解决这一问题，在模型训练中加入了辅助链路预测任务；假设相邻节点应被合并在一起。此外，以确保每个聚类簇中的元素明确无误，该模型还对学得的模糊分配矩阵施加约束条件……其中每一行都应尽可能接近one-hot向量（即每行仅包含一个1值而其余均为0）。可微分池化首次提出通过学习机制获取分配矩阵的方法；然而，在实际应用中获得理想的分配矩阵仍然面临诸多挑战：一方面该方法需处理较为复杂的优化问题；另一方面由于模糊分配矩阵通常较为密集导致计算开销显著增加。
DiffPool旨在通过学习机制生成一种软分配矩阵以实现图的分类任务；值得注意的是，在这一过程中,DiffPool与之相比,Amir等人开发了一种基于记忆机制的图神经网络架构；其核心目标在于通过多轮学习过程获得多样化的特征表达；随后将这些中间结果经过卷积操作整合成一个统一的soft attention矩阵用于后续池化操作；实验结果表明该方法在多项基准测试中表现优异
对比较前文所述基于节点硬划分的传统池化方法而言,类池化策略不强求每个样本必须唯一归属于某一个子群组,这种较为宽松的方式更能贴近真实世界的情况，在某些情况下，一个样本可能会同时参与到多个子群组的角色当中。进一步而言，在现有研究探索的不同池化策略时发现，在采用基于节点的软划分策略的情况下，大多数方法倾向于通过学习机制来确定子群划分关系矩阵，并且通过端到端优化策略，在任务相关的场景下表现出较好的性能。
(3)节点选择与聚合
基于节点选择的池化方法是指从图中选择一些节点来代表整个图,其中被选出的每个节点都代表一个簇. 一般来说,节点选择型分配矩阵在每一列中有一个值为,其他均为0.也就是在n_l个节点中选择n_{l+1}个节点作为粗化后图节点. 这类方法的核心在于设计一种为节点打分和选择节点的方式. Lee等人首先提出了基于自注意力的池化(SAGPool)模型, 该模型在进行池化是,同时考虑了节点特征和图拓扑信息. 具体地, SAGPool利用图卷积网络为每个节点学得一个自注意力分数,这个分数表示节点在图中的重要性:
Z=\sigma (\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}X\Theta_{att})
其中, Z\in R^{N\times 1}, \widetilde{A}的定义和GCN中相同, \Theta_{att}\in R^{F\times 1}是SAGPool模型中唯一的参数. 得到节点重要性分数降序排列, 按照排序结果保留一定比例的重要节点, 当作粗化图的节点:
idx=top-rank(Z,[kN]), Z_{mask}=Z_{idx},
其中, top-rank函数返回值最大的[kN]个节点的标号idx, 在进行池化时,保留被选择的重要节点的节点特征和它们之间的连接方式:
X'=X_{idx,:}, X_{out}=X'\odot Z_{mask}, A_{out}=A_{idx,idx},
其中, X_{out}和A_{out}是池化后图的节点特征矩阵和邻接矩阵. 图10 给出了SAGPool的结构示意图.
Gao等人提出了GraphU-Net模型，并借鉴了传统图像领域中U-Net架构的设计理念。该模型的独特之处在于引入了图上自适应池化（gPool）和上采样（gUnpool）操作。值得注意的是，在池化操作中采用了一种基于可训练映射向量p的方式进行节点筛选，在这一过程中与SAGPool的主要区别在于其选择策略的不同点在于：通过一个可训练的映射向量p将所有节点特征投影到一个一维标量空间中；这个标量值的大小直接反映了该节点所携带信息的重要程度。为了尽可能多地保留原始图中的关键信息,gPool方法选择了具有较大标量值对应的那些节点构建新的子图结构；计算流程如下：首先计算y=\frac{X^lp^l}{||p^l||},然后根据y值对候选节点进行排序并选取前k个具有最高保留能力的节点；接着通过Sigmoid函数作用于这些被选中节点的特征表示\widetilde{y},从而提取出各被选中节点所保留信息的比例值；idx变量则记录了这些被选中节点的具体索引编号；最后通过保留这些被选中节点及其原有的连接关系来构建新的邻接矩阵,同时按照比例保留各被选中节点对应的特征矩阵作为新图的基本表示形式
Cangea等研究者也采用了GraphU-Net中的节点选择策略来进行图池化操作。针对现有技术存在的两大局限性:(1)现有的DiffPool算法难以有效处理大规模图数据;(2)现有基于GraphU-Net等池化方法在提取图结构特征方面仍显不足, Ranjan等人为此开发出了一种创新性的自适应结构感知池化方法(ASAP)。该方法首先将每个节点视为聚类核心,并在局部范围内进行聚类形成簇,随后通过设计一种新型卷积操作对各簇进行打分并排序,最终选取得分最高的kN个簇作为池化后的图结构代表。值得注意的是,在节点聚类形成簇的过程中,所形成的簇的数量与原始图中的节点总数相等;而每个簇的表示形式则相当于整合了该节点及其邻居信息后的表征向量。因此,从整体来看,ASAP算法所实施的池化过程本质上属于基于节点选择的池化框架
这些基于节点选择的图池化方法中存在一些问题:
- 节点选择策略的单一化处理方式较为不足,缺乏针对性;
- 未被选中的节点特征信息通过简单剔除的方式去除,导致特征信息未能有效提取;
张等人开发了一种结合网络拓扑结构与节点属性的图自适应池化方法。该方法的主要创新点在于其独特的节点选择策略设计：主要包含两个独立模块以及一个综合决策模块。具体而言，在每一轮采样过程中系统会自动识别出若干候选采样点，并通过多轮迭代最终确定最终采样点集合。此外，在实际应用中我们发现，在每一轮采样之前会对所有原始信息进行全局融合处理
张等人提出了一种结构学习的层次图池化方法，在该研究中主要体现在通过层次图池化实现特征的有效提取过程中，并在此过程中提出了具有明确意义的节点筛选机制。该研究者指出，在这一过程中, 当一个节点能够由其邻接节点通过某种运算推导得出时, 该节点在构建池化后的图时将被移除, 并且这种操作不会导致信息损失. 进一步研究表明, 这种基于自适应核函数的设计理念所形成的池化操作展现出优异的分类性能.
在目前的分类任务中, 将池化方法分成了:
- 基于节点硬分配,
- 基于节点软分配
- 基于节点选择的池化.
从另一个视角来看,所有图上的池化方法可分为两大类:一种是全局池化技术,它通过一次池化操作获得整个图的表示,例如DGCNN. 另一种是层次池化方法,在每层卷积操作后执行不同规模的池化操作以减小图尺寸,最终获得整个图的表示,如DiffPool和SAGPool.
在卷积过程中, 节点沿图边传播信息后生成的基础表示具有平性特征. 层级缩减机制可实现对图结构的关键分层抽象表达. 该层级缩减方法已在多种模型架构中展现出良好的效果. 表3系统性地汇总与对比了现有基于图神经网络的知识分类方法及其性能指标.
下一节:图分类方法评价及图分类应用