从池化的角度看GNN（包含PR-GNN，EdgePool等7篇论文）下篇

前言

这里承接上篇笔记【从池化的角度看GNN（包含PR-GNN，EdgePool等7篇论文）中篇】继续后面几篇论文的笔记：

• 论文StructPool：《StructPool: Structured Graph Pooling via Conditional Random Fields》
• 论文ASAP：《ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations》
• 论文HCP-SL：《Hierarchical Graph Pooling with Structure Learning》

这里为了方便大家阅读，我把总结部分同步到每一篇笔记中

原创笔记，未经同意请勿转载

上篇笔记链接：从池化的角度看GNN（包含PR-GNN，EdgePool等7篇论文）上篇
中篇笔记链接：从池化的角度看GNN（包含PR-GNN，EdgePool等7篇论文）中篇

一些总结

现有图池化操作主要可以分为全局池化（如SortPool)、分层池化，分层池化中还可以分为基于聚类(如DiffPool，StructPool)和基于重要性排序(如TopK Poolig，SAGPool，GSAPool等）的池化操作，同时也可以衍生出基于频谱上处理的池化操作（如EigenPool，LaPool，HaarPool等）。

1. 改进1：为更加有效的利用图中边所带来的信息，还又EdgePool的池化操作，使得图在池化过程中也可以关注到对应的边缘特征。
2. 改进2：如何更加有效地利用节点对之间关联关系所包含的特征信息，如PR-GNN
3. 改进3：如何改进基于重要性排序的图池化操作？——》所面对的问题：丢弃不重要节点所带来的特征信息重要缺失问题 ——-》解决方法：① 拉大节点之间差距，如PR-GNN ② 在丢弃前聚类节点特征，如GSAPool ③ 多特征融合与子图学习机制辅助，如HCP-SL
4. 改进4：如何改进基于聚类的图池化操作？——-》所面对的问题：聚类之后的模型可解释性差，聚类之间的关联关系少 ——》解决方法：① 聚类信息中融入关联关系与图结构信息，如StructPool ② 簇内外注意力机制加持与局部关注，如ASAP
5. 改进5：如何更有效的保留图层次及子图结构信息？——》所面对的问题：在空间域上处理的池化操作不利于图结构信息的保留 ——》解决方法：频谱上的处理：① 拉普拉斯变换，如LaPool ② 图傅里叶变换，如EigenPool ③ Haar变换，如HaarPool

一些早期论文的简要介绍

下篇放最后三篇。

5??论文StructPool：《StructPool: Structured Graph Pooling via Conditional Random Fields》

• 来源： ICLR2020

• 原文链接： https://openreview.net/forum?id=BJxg_hVtwH

• 代码链接： https://github.com/Nate1874/StructPool

• 数据任务：
  （1）数据任务：图分类、节点分类
  （2）数据集：在八个数据集上进行评估STRUCTPOOL，包括五个生物信息学蛋白质数据集，ENZYMES，PTC，MUTAG，PROTEINS，D＆D以及三个社交网络数据集，COLLAB，IMDB-B，IMDB-M。

• 参考阅读的博客：
  STRUCTPOOL via CRF，ICLR2020_五月的echo的博客-CSDN博客
  STRUCTPOOL: STRUCTURED GRAPH POOLING VIA CONDITIONAL RANDOM FIELDS - 知乎

• 主要的出发点： 存目前一些性能比较好的图池化方法，如SORTPOOL，TOPKPOOL，DIFFPOOL和SAGPOOL都未显式地对不同节点之间关系建模，因此可能会忽略重要的结构信息，即没有显式的考虑图的结构信息，并将Graph Pooling的过程转化为节点聚类的问题（如基于聚类的分层池化操作）。然而，对于一个节点的分类，其分类的结构不仅与其自身的节点特征相关，还与其他节点的分类结果存在关联关系。因此，StructPool作者次啊用条件随机场（CRF）方法来模拟这种节点之间的高阶的关联关系，并结合图的结构信息来设计Gibbs能量方程。【以往基于聚类的图池化方法的目标是学习一个聚类分配矩阵，但该分配矩阵只考虑到节点本身的特征。而StrcutPool则在其基础上利用CRF来综合考虑节点自身的特征矩阵和不同节点的分配关系来生成对应的聚类分配矩阵。】

• 亮点：利用CRF来综合考虑节点自身的特征矩阵和不同节点的分配关系来生成对应的聚类分配矩阵，并结合图的结构信息来设计Gibbs能量方程。
  

• 内容：
  （1）一些概率图模型知识
  （2）论文原理
  

• 实验结果：
  

6??论文ASAP：《ASAP: Adaptive Structure Aware Pooling for Learning Hierarchical Graph Representations》

• 来源： AAAI2020

• 原文链接： https://www.aaai.org/Papers/AAAI/2020GB/AAAI-RanjanE.8336.pdf

• 代码链接： https://github.com/malllabiisc/ASAP

• 数据任务：
  （1）任务：图分类任务
  （2）数据集：
  

• 主要的出发点： 全局池化与层次池化的局限性：

• 全局池化（Global Pooling）

  • 优点： 可以进一步完成池化操作（比较能够轻松地伸缩到大型图中），可以尽量的保留大量的特征信息
  • 缺点： 无法有效的捕获图的层次结构信息，子图的结构
  • 例子：
    ① 通过迭代的基于内容的注意力方法找到图中每个节点的重要性的Set2Set。(https://arxiv.org/abs/1511.06391)
    ② 使用全局注意力机制聚合图中节点的Global-Attention方法。(https://arxiv.org/abs/1511.05493)
    ③ 根据节点特征排序再将几个节点拼接来表述图结构的SortPool。(https://chyson.net/papers/AAAI_2018_DGCNN.pdf)

• 层次池化（Hierarchical Pooling）

  • 优点： 可以捕捉图的拓扑结构信息
  • 缺点： 不利于简单地伸缩到大型图中，无法尽可能地保留大量的特征信息
  • 例子：
    ① DiffPool通过聚合节点形成了若干个簇，簇个数为固定的(超参数)。其中聚类所用的矩阵为通过一层GNN计算的软分配矩阵，该矩阵是一个稠密矩阵，导致其对大图计算效率较低。
    ② TopK基于一个可学习的投影向量对节点进行评分，并保留部分高分节点。它避免了节点聚类和软分配矩阵的计算，以保持图计算的稀疏性。
    ③ SAGPool通过自注意力机制改进了TopK，使用GNN为节点打分的同时能够考虑图结构。
    由于TopK和SAGPool不聚合节点，也不计算软边权值，无法有效保存节点和边信息。该论文提出的ASAP具有层次化池化方法的所有优良特性的同时不影响图操作的稀疏性。

• 亮点： 提出了一种自适应结构感知的池化操作ASAP
  （1）一种能够分层捕获局部子图信息的稀疏池化算子，该池化方法能够根据池化图的边连接更好的学习全局特征；
  （2）一种新的更适合与像池化这种全局任务的自注意力机制；
  （3）一种新的图卷积方法LEConv，用来自适应的学习图子结构中的局部极值(local extremas)。
  总体而言，ASAP是对层次化池化方法的综合和优化，解决了DiffPool中非稀疏的问题，同时利用聚类的思想进行了采样。而且ASAP实际上利用了两次自注意力机制打分，一次作用在簇内，一次作用在簇间，即在丢弃节点前进行注意力机制的聚合，保留了丢弃节点的信息，同时用节点的增量来改进注意力机制。

• 内容： 结构与SAGPool的分层池化结构相类似
  
  ASAP首先对graph进行分层聚类，从而有效地学习图结构中存在的层级信息等。论文在此基础上提出了Master2Token自注意机制，该机制使该模型更好地捕获Cluster中每个节点的重要性，进一步根据该Score计算整个Cluster的表示。根据Cluster的表示计算Graph的表示，为了选择哪些Cluster比较重要，论文提出了LEConv，一种改进的GNN公式，该公式可以根据对cluster进行评分。有了得分就可以选择Topk得到Graph的表示。这样可以确保在整个图形中选择代表性的cluster。ASAP为所选的cluster计算了边的权重，并有效地捕获边的连通性信息，该方法比较容易扩展大型图形。
  （a）向ASAP输入图表。
  （b）ASAP initial clustering 1-hop neighborhood，考虑所有节点为medoid1。为简便起见，我们仅将节点2和6的簇形成表示为medoid。使用M2T attention计算簇隶属度。
  （c）使用LEConv对集群进行评分。颜色越深表示分数越高。
  （d）在合并图中选择得分最高的集群的一部分。利用所选簇成员节点之间的边权重新计算邻接矩阵。
  （e） ASAP的输出。
  （f）层次图分类架构概述。

• 实验结果
  

7??论文HCP-SL：《Hierarchical Graph Pooling with Structure Learning》

• 来源： AAAI2019
• 原文链接： https://arxiv.org/pdf/1911.05954.pdf
• 代码链接： https://github.com/cszhangzhen/HGP-SL
• 主要的出发点： 现在的层次池化方法大概分为两种：
  （1）基于聚类：根据分配矩阵，把节点分配到不同的簇中以完成池化。缺点：计算代价比较高。
  （2）基于采样：根据节点的得分情况，保留排名前k个节点，其他的则直接舍弃。缺点：不能保留关键的子结构甚至不能保证拓扑信息的完整性。
• 亮点： 提出了一种新的基于TopK的图池化操作符HGP-SL，它可以集成到各种图神经网络架构中。HGP-SL将图池和结构学习整合到一个统一的模块中，以生成图的层次表示。更具体地说，图池操作自适应地选择节点的子集，形成后续层的诱导子图。为了保持图的拓扑信息的完整性，进一步引入了一种结构学习机制，在每一层上学习一个优化的集合图结构。将HGP-SL算子与图神经网络相结合，以图分类任务为重点，进行图级表示学习。
• 内容：
  1. 在每个卷积层后的HGP-SL池化层，通过为每个节点打分，然后通过节点选择的方式完成图池化，即：获得当前图的一个子图。
  2. 一种新的结构学习方式，即对子图构造新的邻接矩阵。
  3. 利用多层级特征融合的方法增强模型最后readout层的表征能力（要求每一层的特征维度不发生变化）
     
• 实验结果