摘要

在图神经网络（GNNs）中，池化操作通过计算输入图的局部汇总信息来捕捉其全局特性，是构建能够学习分层表示的深层GNN的关键组件。本文提出了一种名为节点裁剪池化（Node Decimation Pooling, NDP）的GNN池化算子，该算子能够在保持图整体拓扑结构的前提下生成更粗粒度的图。在训练过程中，GNN学习新的节点表示，并将其拟合到一个在预处理阶段离线计算得到的多级粗化图金字塔上。NDP包含三个步骤：首先，通过一种基于谱算法的节点裁剪过程，选择由该谱算法近似求解最大割（\maxcut{}）问题所确定的图划分中某一侧的节点；其次，将所选节点通过Kron约简（Kron reduction）连接，构建出粗化图；最后，由于生成的图具有高度稠密性，我们进一步引入稀疏化处理，对粗化图的邻接矩阵进行剪枝，以降低后续GNN计算过程中的开销。值得注意的是，我们证明了在不显著改变图结构的前提下，可以移除大量边。实验结果表明，相较于当前最先进的图池化算子，NDP在计算效率上更具优势，同时在多种典型的图分类任务中仍能取得具有竞争力的性能表现。