【文章来源：https://arxiv.org/pdf/2402.14393】
摘要
motivation:图池是建立在GNN之上的。它旨在通过将一组节点及其底层结构压缩为更简洁的表示来捕获图级信息。早期的图池化方法，如mean，add或pool对图中的所有节点执行排列不变操作。这些平面池化方法忽略了节点之间的区别，无法对图中的潜在层次结构进行建模。因此，它们只能以粗略的方式在图级捕获信息。为了克服这一限制，他们转而对图数据进行分层池化，以更准确地捕获结构信息。主要的方法是节点删除和节点聚类。节点删除方法通过在每一步删除一定比例的节点来减小图的大小。虽然它们具有内存效率，但它们不可逆转地丢失节点信息，并可能损害图的连通性，导致次优性能。另一方面，节点聚类方法在每个池化层执行聚类，允许对每个节点进行软聚类分配，从而保留其信息。然而，这是以具有二次内存复杂度的密集集群分配矩阵为代价的，牺牲了可扩展性。现有图池化方法的另一个基本问题是，它们无法为每个单独的图学习个性化的池化结构，即它们为所有图预定义固定的池化比例或层数。理想情况下，模型应该为每个图学习个性化的池化树。
contribution:为了克服这两个关键问题，作者提出了一种受自下而上语法归纳最新进展启发的图解析算法。在自然语言处理中，语法归纳技术在没有任何引导监督的情况下从输入文本序列中提取潜在的离散结构。将这种方法应用于图领域，并用它来学习池化树。如图2所示，作者的模型采用了一种图解析算法，该算法为k层的每个节点分配一个离散赋值，能够推断出高度k处的节点数n_k。当图被完全解析，解析过程结束，能够推断出总高度h_max。因此，作者的模型可以以端到端方式为每个单独的图学习池化树。解析算法基于局部性，从而保证了池化过程中的图连通性。作者对节点进行聚类而不是丢弃，既保持了节点信息的完整性，又保证了离散聚类过程的内存效率。
方法
GRAPH POOLING COMPONENTS
Graph information encoding 该模块提取节点特征和图结构，生成有用的度量。为节点聚类方法生成集群分配向量。为了编码结构信息，作者应用一个GNN模块，然后在相邻节点上使用MLP来计算边分数:
Multiset computation 该模块计算G(k+1)的特征矩阵X(k+1)。由于输入节点集可以被视为多集，因此该模块可以被视为多集函数。作者使用DeepSets实现这个模块:
因为图解析算法A是不可微的，为了更新公式1中的MLP，作者需要在反向传播中涉及边分数。为了实现这一点，作者通过边分数计算掩码y(k)。考虑G(k+1)中聚类vi诱导的子图Gi(k)(冒)。作者将内的边表示为εi(k)(冒)，而1是一个维的全1向量。通过将分数相加，然后与特征相乘，聚类可以知道分配给它的边的数量。
GRAPH PARSING ALGORITHM
作者的图解析算法，A以边分数矩阵作为输入C(k)，并返回赋值矩阵S(k)。作者没有对池化比率或集群数量施加任何限制。因此，作者从节点推断聚类的方式类似于语法归纳中从较小单位(例如短语)推断较大单位(例如子句)的方式。为了使池化结构可学习，模型
既依赖于图拓扑，也依赖于图拓扑上定义的一组连续值，即边分数。因此，当通过梯度更新边分数时，池化结构也可以通过解码来更新。为了详细说明这个解码过程，作者首先介绍其中使用的三个操作符。
Definition 1.
DOM(·)(“dominant”的缩写):该操作符为每个节点选择优势边，从而决定其分配。首先对边分数矩阵C(k)执行逐行max索引，得到种子边idx，然后过滤掉其他边，构造矩阵:
Definition 2.
EXP(·)(“expand”的缩写):该算子通过邻居查找在过滤后的图G(k)(冒)上展开一组种子边idx。首先用idx诱导节点集L，然后合并被它们支配的相邻边idx’。idxx、idxy表示边集idx的起始节点索引集和结束节点索引集:
Definition 3.
GEN(·)(“generate”的缩写):给定一个赋值映射s，将节点L映射到集群j，该算子使用s生成赋值矩阵S(k):
MODEL ARCHITECTURE
Graph-level architecture 通过利用前几节介绍的池化层，可以直接将该模型用于图分类任务。作者的模型架构(如图3所示)仅由一个池化层组成，该池化层逐步减小输入图的大小，直到它与图解析算法A产生的输出图相匹配。随后，利用多集计算模块将最终图转换为单个节点，并生成用于图分类的压缩向量。
Node-level architecture 作者为节点分类任务开发了编码器-解码器架构(见图3)。作者的方法包括在编码器块中使用自下而上的池将图压缩成更小的大小，然后在解码器块中扩展它。在编码过程中，作者将分配矩阵存储在每个池层，并在解码过程中使用该信息进行解池。作者实现第k个解池化层如下:
信息丰富的节点表示对于节点级任务至关重要。为了实现这一点，作者为多集计算模块使用了一个单独的GNN编码器。在节点级架构中，池化层中的公式3需要改写为:
论文实验结果：
