图分类问题是一个重要的图层面的学习任务，需要关注图数据的全局信息，包括图的结构信息以及各个节点的属性信息。 给定多张图，以及每张图对应的标签，图分类任务需要通过学习得出一个由图到相应标签的图分类模型，重点在于如何通过学习得出一个优秀的全图表示向量。

在图分类任务中实现层次化池化的机制，是GNN需要解决的基础问题。

1. 基于全局池化的图分类

在MPNN中，除了为图中节点的表示学习提供了一般框架外，作者也涉及了一个读出（readout）机制对经过K轮迭代的所有结点进行一次性聚合操作，从而输出图的全局表示：
y = R ( { h i ( k ) ∣ ∀ v j ∈ V } ) y=R(\{h_i^{(k)|\forall v_j\in V}\}) y=R({hi(k)∣∀vj​∈V​})
读出机制与CNN模型中常用的紧跟最后一个卷积层的全局池化（Global Pooling）操作如出一辙。都是通过对所有输入的一次性聚合得到全局表达，且与池化的常见类型一样，读出机制也可以取Sum、Mean、Max等类型的函数。

另一种方式是引入一个与所有结点都相连的虚拟节点，将全图的表示等价于这个虚拟节点的表示。这种思虑也在GN中全局表示$u$的更新过程中得到了体现。

显然，读出机制丢失了图数据里丰富的结构信息，其本质是将输入数据看作一种平整且规则的结构数据，所有的结点都被同等看待，这与图数据本身相违背。因此，读出机制更适应对小图数据的学习，一方面是因为小图数据结构信息单一，另一方面是经过K轮消息传播机制的迭代之后，图中各个结点的表达会更加接近全局表达，此时读出机制也能较好地提取全局信息，而且，读出机制易于实现，非常适合作为图分类的基准模型。

2. 基于层次化池化的图分类

列举3中不同的思路介绍能够实现图数据层次化池化的方案：
（1）基于图坍缩（Graph Coarsening）的池化机制：图坍缩是将图划分为不同的子图，然后将子图视为超级节点，从而形成一个坍缩的图。
（2）基于TopK的池化机制：对图中每个节点学习出一个分数，基于这个分数的排序丢弃一些低分数的节点，这类方法借鉴了CNN中最大池化操作的思路：将更重要的信息筛选出来。不同的是，图数据难以实现局部滑窗操作，因此需要依据分数进行全局筛选。
（3）基于边收缩（Edge Contraction）的池化机制：边收缩是指并行地将图中的边移除，并将被移除边的两个节点合并，同时保持被移除节点的连接关系，该思虑是一种通过归并操作来逐步学习图的全局信息的方法。

2.1 基于图坍缩的池化机制

1 图坍缩

假设对于图G，通过某种划分策略得到K个子图 { G ( k ) } k = 1 K \{G^{(k)}\}_{k=1}^K {G(k)}k=1K​，$N_k$表示子图$G^{(k)}$中的节点数，${\Gamma }^{(k)}$表示子图$G^{(k)}$的节点列表。

图坍缩就是将图中的节点划分为几个节点簇，每个节点簇作为下一次图坍缩的节点。下面给出图坍缩中的两个比较重要的矩阵：

• 第一个是簇分配矩阵$S\in R^{N\times K}$，其定义如下：$S_{ij}=1$当且仅当$v_i\in {\Gamma }^{(j)}$。令$A_{coar}=S^{T}AS$，描述了图坍缩之后的超级节点之间的连接强度，设置$A_{coar}[i,i]=0$。
• 第二个是采样算子$C\in R^{N\times N_k}$，其定义为$C_{ij}^{(k)}=1$，当且仅当${\Gamma }_j^{(k)}=v_i$。其中，${\Gamma }_j^{(k)}$表示列表${\Gamma }^{(k)}$中的第j个元素。C是节点在原图和子图中顺序关系的一个指示矩阵。

假设定义在G上的一维图信号为$x\in R^N$，下列两式分别完成了对图信号的下采样于上采样操作：$$x^{(k)}=(C^{(k)}{)}^{T}x，\bar{x}=C^{(k)}{x}^{(k)}$$，上述左式完成了对图信号在子图$G^{(k)}$上的采样（切片）功能；右式完成了子图信号$x^{(k)}$在全图的上采样功能。该操作保持子图中节点的信号值不变，同时将不属于该子图的其他节点的值设置为0。显然，该采样算子也适用于多维信号矩阵$X\in R^{N\times d}$。

有了采样算子的定义，对于子图$G^{(k)}$的邻接矩阵$A^{(k)}\in R^{N_k\times N_k}$，可以通过下式获得（事实上，$A^{(k)}$也可以通过对A进行矩阵的双向切片操作获得）：$$A^{(k)}=(C^{(k)}{)}^{T}A{C}^{(k)}$$

通过$A_{coar}=S^{T}AS$和$A^{(k)}=(C^{(k)}{)}^{T}A{C}^{(k)}$可以确定簇内的邻接关系以及簇间的邻接关系。进一步讲，如果能够确定簇内信号的融合方法，将结果表示为超级节点上的信号，那么迭代地重复上述过程，就能够获得越来越全局的图信号了。

上图即为图塌缩与GNN结合的过程：该图展示了一个经过3个池化层最后坍缩成一个超级节点，然后进行图分类任务的GNN模型。在得到最后一个超级节点的特征向量之后，使用了一个三层的MLP网络进行图分类任务的学习。

目前DIFFOOL和EigenPooL是两种基于图坍缩的图神经网络算法。

2 DIFFPOOL

DIFFPOOL是首个将图坍缩过程与GNN结合起来进行图层面任务学习的算法。DIFFPOOL提出了一个可学习的簇分配矩阵。具体来说，首先通过一个GNN对每个节点进行特征学习，然后通过另一个GNN为每个节点学习出所属各个簇的概率分布：
$$Z^{(l)}=GN{N}_{l,embed}(A^{(l)},H^{(l)})$$
$$S^{(l)}=softmax(GN{N}_{l,pool}(A^{(l)},H^{(l)}))$$
其中$A^{(l)}\in R^{n^{(l)}\times n^{(l)}},S^{(l)}\in R^{n^{(l)}\times n^{(l+1)}}$，$n^{(l)}$表示第$l$层的节点数，$n^{(l+1)}$表示第$(l+1)$层的节点（簇）数，相较于上文$S$矩阵的硬分配，这里学习出来的$S$矩阵是一个软分配器，其值表示节点被分配到任意一个簇的概率，由于概率值不为0，因此这是一个下层超级节点到上层所有节点之间的全连接结构。
$GN{N}_{l,embed}$, $GN{N}_{l,pool}$是两个独立的GNN层，二者的输入相同，但是参数不同，学习的目的不同。需要强调一点的是，对于最后一层的簇分配矩阵，需要直接将该矩阵固定成一个全“1”的矩阵，这是因为，此时需要将图坍缩成一个超级节点，由此获得图的全局表示。

有了上述两个式子的输出结果，可以对图进行坍缩：
$$H^{(l+1)}=S^{(l{)}^T}{Z}^{(l)}$$
$$A^{(l+1)}=S^{(l{)}^T}{A}^{(l)}{S}^{(l)}$$
这里将上述两个公式成为DIFFPOOL层（$(A^{(l)},Z^{(l)})\to (A^{(l+1)},H^{(l+1)})$）。$H^{(l+1)}=S^{(l{)}^T}{Z}^{(l)}$是对簇内的信息执行融合操作，$S^{(l{)}^T}{Z}^{(l)}$表示的是对簇内所有节点的特征向量进行加和处理。$A^{(l+1)}=S^{(l{)}^T}{A}^{(l)}{S}^{(l)}$为簇间的邻接矩阵的计算。

DIFFPOOL具有排列不变性：假设 P ∈ { 0 , 1 } n × n P\in \{0,1\}^{n\times n} P∈{0,1}n×n是一个任意的排列矩阵，只需要保证前面用到的GNN层是排列不变的，DIFFPOOL层就具有排列不变性，即$$DIFFPOOL(A,Z)=DIFFPOOL(PA{P}^T,PX)$$，排列矩阵的作用是对图中节点进行重排序，比如一个仅有两个节点向量的图，如果我们需要将两个节点的编号进行对调，则对应的排列矩阵$P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$，排列矩阵是正交的，即$P^{T}P=I$。可以通过$PX,PA{P}^T$来分别获得重排序之后的特征矩阵与邻接矩阵。

总的来说，节点是否重新排序并不应该影响节点聚合成簇的结果。

有了上述DIFFPOOL层的定义，就可以模仿CNN分类模型的结构设计，不断组合堆叠GNN层与DIFFPOOL层，实现一种可导的、层次化池化的学习机制，并逐渐获得图的全局表示。

3. EigenPooling

EigenPooling是一种基于图坍缩的池化机制。它没有对图分类模型引入任何需要学习的参数，这种非参的池化机制与视觉模型中的各类池化层具有很高的类比性。
表1 EigenPooling与视觉模型中的池化比较

性质	EigenPooling	视觉模型中的Pooling
前置层类型	GNN	CNN
作用域	子图	滑窗
作用域的选取	图分区算法（比如用谱聚类对图划分子图）	设定超参数，比如2×2的窗口大小
具体池化操作	基于子图的傅里叶变换	取最大值或均值
池化层是否带参	否	否

EigenPooling的具体过程中，其核心步骤在于作用域的选取以及池化操作，作用域是通过划分子图的方式对图进行分区得到的，这等价于图坍缩的过程，通过这一步可以得到新的超级节点之间的邻接矩阵。池化操作需要考虑的是对作用域内的信息进行融合，通过这一步可以得到关于新的超级节点的特征矩阵。
注意：在视觉模型中池化操作的作用域都是规则的栅格结构，而在图坍缩的子图上，作用域内的信息包含了结构信息与属性信息，特别是结构信息，不同的子图间有比较大的区别，EigenPooling就同时考虑了这两种信息并进行了融合。
（1）图坍缩
EigenPooling中的图坍缩并没有给图分类模型引进任何需要学习的参数，其思路是借用一些图分区的算法来实现图的划分，比如谱聚类算法。
谱聚类是一类比较典型的聚类算法，其基本思路是先将数据变换到特征空间以凸显更好的区分度，然后执行聚类操作，比如选用Kmeans算法进行聚类，算法的输入是邻接矩阵以及簇数K，输出的是每个节点所属的簇。

注意：如果选用Kmeans算法进行聚类，那么簇的分配就是一种硬分配，每个节点仅能从属于一个簇，这种硬分配保持了图坍缩之后的超级节点之间连接的稀疏性。而DIFFPOOL中的是软分配机制，节点以概率的形式分配到每一个簇中，导致超级节点之间以全连接的形式彼此相连，增加了模型的空间复杂度和时间复杂度。
将图进行划分之后，调用$A_{coar}=S^{T}AS$就可以得到超级节点间的邻接关系，当然，EigenPooling在这一步没有考虑超级节点簇内的连接强度。
（2）池化操作
在确定了子图划分以及相应的邻接矩阵之后，需要对每个子图内的信息进行整合抽取。在DIFFPOOL中选择了对节点特征进行加和，这种方式损失了子图的结构信息，而EigenPooling用子图上的信号在盖子图上的图傅里叶变换来代表结构信息与属性信息的整合输出。

图信号的频谱展示了图信号在各个频率分量上的强度，它是将图的结构信息与信号本身的信息统一考虑进去，而得到的一种关于图信号的标识信息。因此，EigenPooling选用了频谱信息来表示子图信息的统一整合。

假设子图$G^{(k)}$的拉普拉斯矩阵为$L^{(K)}$，对应的特征向量为${\vec{u}}_1^{(k)},{\vec{u}}_2^{(k)},...,{\vec{u}}_{N_k}^{(k)}$，然后，使用上采样算子$C^{(k)}$将该特征向量（子图上的傅里叶基）上采样到整个图：
$${\overline{\stackrel{⃗}{u}}}_l^{(k)}=C^{(k)}{\vec{u}}_l^{(k)}，l=1,...,N_k$$
为了将上述操作转换为矩阵形式，以得到池化算子${\Theta }_l\in R^{N\times K}$，将所有子图的第$l$个特征向量按行方向组织起来形成矩阵$\Theta$，即$${\Theta }_l=[{\overline{\stackrel{⃗}{u}}}_l^{(1)},...,{\overline{\stackrel{⃗}{u}}}_l^{(k)}]$$
注意，子图的节点数量是不同的，所以特征向量的数量也不同。用$N_{max}={\max }_{k=1,...,K}{N}_k$表示子图中的最大节点数。然后，若子图$G^{(k)}$的节点数小于$N_{max}$，可以将${\overline{\stackrel{⃗}{u}}}_l^{(k)}(N_k<l<N_{max})$设置为$0\in R^{N_k\times 1}$。

有了池化算子的矩阵形式，池化过程可描述为：$$X_l={\Theta }_l^{T}X$$
$X_l\in R^{K\times d}$是池化的结果。$X_l$的第$k$行表示的是第$k$个超级节点在${\Theta }_l$作用下的表示向量。按照该机制，共需要设计$N_{max}$个池化算子。为了结合不同池化算子收集到的信息，可以采用按列方向拼接的方式，将各个结果连接起来：
$$X_{pooled}=[X_0,...,X_{N_{max}}]$$
其中$X_{pooled}\in R^{K\times (d\cdot N_{max})}$是EigenPooling最终的池化结果。

为了提高计算效率，选择使用前H个特征向量对应的池化结果，一般为$H<<N_{max}$：
$$X_{coar}=X_{pooled}=[X_0,...,X_H]$$
上述计算都在矩阵层面上进行，如果将计算回到向量形式上，可以清楚地看到EigenPooling是怎么利用图傅里叶变换对子图信息进行整合的。不失一般性，设全图上的信号为$\vec{x}$，则$X_l={\Theta }_l^{T}X$可描述为：
$$({\overline{\stackrel{⃗}{u}}}_l^{(k)}{)}^{T}x=({\overline{\stackrel{⃗}{u}}}_l^{(k)}{)}^T(C^{(k)}{)}^{T}x=({\vec{u}}_l^{(k)}{)}^T{x}^{(k)}$$
其输出表示子图上的信号在子图上对应的第$l$个特征向量上的傅里叶系数。

同DIFFPOOL一样，如果EigenPooling的前置GNN层选用GCN的话，EigenPooling整体也将具有排列不变性。总的来说，EigenPooling作为一种不带任何学习参数的池化机制，可以非常方便地整合到一般的GNN模型中，实现对图信息的层次化抽取学习。与DIFFPOOL相比，主要优势在保持了超级节点之间连接的稀疏性，同时提高了计算效率，在进行池化操作时，兼顾了子图的结构信息与属性信息，相比DIFFPOOL具有更高的价值。

2.2 基于TopK的池化机制

基于TopK的池化机制，是一个不断丢弃节点的过程，其抓住的是图不同尺度的信息。和CNN中基于局部滑窗的池化操作不同的是，TopK池化将作用域放到全图节点上。具体来说，首先设置一个表示池化率的超参数$k,k\in (0,1)$，接着学习出一个表示节点重要度的值$z$并对其进行降排序，然后将全图中N个节点下采样至$kN$个节点。用公式表示如下：
$$\vec{i}=top-rank(z,kN)$$
$$X^{\prime }=X_i,:$$
$$A^{\prime }=A_{i,j}$$
$X_{i,;}$表示按照向量$\vec{i}$的值对特征矩阵进行行切片，$A_{i,j}$表示按照向量$\vec{i}$的值对邻接矩阵同时进行行切片与列切片。

不同于DIFFPOOL，若将N个节点分配给$kN$个簇，会使得模型需要$k{N}^2$的空间复杂度来分配簇信息，而基于TopK的池化机制，每次只需要从原图中丢弃$(1-k)N$个节点即可。

如何学习节点的重要度？作者为图分类模型设置了一个全局的基向量$\vec{p}$，将节点特征向量在该基向量上的投影当作重要度：
$$z=\frac{X\vec{p}}{||\vec{p}||}$$
其中$X$为节点特征向量。该投影机制具有双重作用：（1）可以以投影的大小来确定TopK的排序；（2）投影大小还起到了一个梯度门限的作用，投影较小的节点仅有较小的梯度更新幅度，相对地，投影较大的节点会获得更加充分的梯度信息。

论文中给出的TopK的模型结构为：

定义gpool层为:
$$z=\frac{X\vec{p}}{||\vec{p}||},\vec{i}=top-rank(z,kN)$$
$$X^{\prime }=(X\odot tanh(z){)}_{\vec{i},:}$$
$$A^{\prime }=A_{i,i}$$
其中，$\vec{z}$为重要度值（节点分数），用于进行降序排序，计算方法是将节点的特征向量在基向量$\vec{p}$上进行投影。top-rank函数根据$\vec{z}$值选出重要度前$k$名的节点的下表。然后依据$\vec{i}$对原先的特征矩阵X和邻接矩阵A进行切片操作，相当于丢弃一些节点。
在特征矩阵的更新中点乘一个$tanh(z)$，这相当于利用节点的重要度对节点特征做了一次收缩变换，进一步强化了对重要度高的节点的梯度学习。

与基于图坍缩的池化机制相比，gpool层采取了层层丢弃节点的做法来提高远距离节点的融合效率，但是这种做法会使得其缺乏对所有节点进行有效信息融合的手段。因此，为了实现有效融合，在gpool层后面再加上一个readout层实现对该尺度下的图的全局信息的一次性聚合。readout层的具体实现方式是将全局平均池化与全局最大池化拼接起来：
$$s^{(l)}=(\frac{1}{N}\sum _{i=1}^N{x}_i^{(l)})||(\underset{i=1}{\overset{N}{\max }}{x}_i^{(l)})$$
最终，为了得到全图的表示，将各层的$s$相加：$$s=\sum _{l=1}^L{s}^{(l)}$$
其中读出层将平均池化与最大池化拼接起来，最终的全局池化是每一层池化结果的加和。

如上图所示的模型结构中，使用了两层gpool层，相应地设置了两层readout层，之后对两层readout层的输出进行相加得到全图的向量表示，然后送到一个MLP里面进行图分类的任务学习。

关于丢弃节点的池化机制，一种新的方式是：自注意力图池化（SAGPool），该方法使用了一个GNN对节点的重要度进行学习，与gpool全局基向量的设计相比，这种基于GNN的方式更好地利用图的结构信息对节点的重要度进行学习。

2.3 基于边收缩的池化机制

EdgePool核心思想是迭代式地将每条边上的节点进行两两归并形成一个新的节点，同时保留合并前两个节点的连接关系到新节点上，最终得到全图的特征表示。

存在的一个问题是：每个节点有多条边，但是每个节点只能从属于一条边进行收缩，那么该如何选择每个节点所丛属的边呢？EdgePool对每条边设计了一个分数，依据该分数进行非重复式的挑选与合并。具体操作如下：

对每条边，计算原始分数$r_{i,j}$：
$$r_{i,j}={\vec{w}}^T[{\vec{h}}_i||{\vec{h}}_j]+b$$
由于每个节点选择哪条边，需要从其局部邻居出发进行考虑，所以，我们对原始分数沿邻居节点进行归一化：
$$s_{ij}=softma{x}_j(r_{ij})$$
其中$r_{ij}$为每条边的原始分数，$s_{ij}$为原始分数沿着邻居节点归一化后的分数。得到上述分数后，对所有的$s_{ij}$进行排序，依次选择该分数最高的且未被选中的两个节点进行合并操作。

上图中，图a计算了图中每条边的原始分数$\vec{r}$，对于无向图，将方向进行双向复制，对于有向图则仅需按照方向进行后续操作，图b计算了$e^r$，节点分数为边入度边分数之和。例如图中的节点$D$的值就是$e^{0.5}=1.6$，$C$的值为$e^{0.5}+e^1+e^3=1.6+2.7+20=24.5$。图c沿着入边方向对每个结点进行归一化操作，图中的加黑的边表示被选中的进行合并的边。注意，在确定$<B,A>$边的时候，尽管$<B,C>$边上具有更高的分数0.8，但是C结点已经被选择与D节点合并，因此选择分数次高的$<B,A>$边进行合并，图d表示合并之后的结果。

合并之后新节点的特征向量${\vec{h}}_{ij}$为： h ⃗ i j = max ⁡ { s i j , s j i } ⋅ ( h ⃗ i + h ⃗ j ) \vec{h}_{ij}=\max\{s_{ij},s_{ji}\}\cdot (\vec{h}_i+\vec{h}_j) h ij​=max{sij​,sji​}⋅(h i​+h j​)

EdgePool与DIFFPOOL一样，都是不断对图中所有节点进行融合学习，不同的是DIFFPOOL需要自行设置聚类簇数，而EdgePool利用边收缩的原理，仅将邻居节点进行归并，并将归并比率严格控制在0.5，既保留了图的结构信息，有保证了图中连接的稀疏性，空间复杂度更低。

参考资料

[1] 图神经网络的池化操作
[2] 《深入理解图神经网络：GNN原理解析》
[3] Graph Convolutional Networks with EigenPooling
[4] EigenPool
[5] Gilmer J, Schoenholz S S, Riley P F, et al. Neural message passing for quantum chemistry[J]. arXiv preprint arXiv:1704.01212, 2017.
[6] Pham T, Tran T, Dam H, et al. Graph classification via deep learning with virtual nodes[J]. arXiv preprint arXiv:1708.04357, 2017.
[7] Ying Z, You J, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[C]//Advances in neural information processing systems. 2018: 4800-4810.
[8] Cangea C, Veličković P, Jovanović N, et al. Towards sparse hierarchical graph classifiers[J]. arXiv preprint arXiv:1811.01287, 2018.
[9] Diehl F. Edge contraction pooling for graph neural networks[J]. arXiv preprint arXiv:1905.10990, 2019.