Hierarchical Graph Pooling with Structure Learning

2024-08-05

Hierarchical Graph Pooling with Structure Learning

会议: AAAI 2020(疑似撤稿)

论文地址：https://arxiv.org/abs/1911.05954

github: https://github.com/cszhangzhen/HGP-SL

DGL开源库：https://github.com/dmlc/dgl/tree/master/examples/pytorch/hgp_sl

[TOC]

摘要

图神经网络 (GNN) 将深度神经网络扩展到图结构数据，在许多图相关任务中取得了最先进的性能。然而，现有的 GNN 模型主要关注设计图卷积操作。图池化 (或下采样) 操作在分层表示学习中发挥着重要作用，通常被忽视。在这篇论文中，我们提出了一种新的图池化操作符，称为具有结构学习的分层图池化 (HGP-SL)，它可以集成到各种图神经网络架构中。HGP-SL 将图池化和结构学习集成到一个统一的模块中，以生成图的分层表示。具体来说，图池化操作根据我们定义的节点信息分数自适应地选择一组节点来形成一个诱导子图，用于后续层。为了保留图的拓扑信息的完整性，我们进一步引入了一种结构学习机制，以学习每层池化图的精炼图结构。通过将 HGP-SL 操作符与图神经网络相结合，我们进行了图级别表示学习，重点关注图分类任务。在六个广泛使用的基准数据集上的实验结果表明了我们提出的模型的有效性。

介绍

具有卷积和池化层的深度神经网络在各种具有挑战性的任务中取得了巨大的成功，从计算机视觉 (He 等人，2016 年)、自然语言理解 (Bahdanau、Cho 和 Bengio，2015 年) 到视频处理 (Karpathy 等人，2014 年)。这些任务中的数据通常表示在欧几里得空间中（即，建模为二维或三维张量），因此通常包含卷积操作的局部和顺序信息 (Defferrard、Bresson 和 Vandergheynst，2016 年)。然而，在许多现实世界问题中，大量数据（例如社交网络、化学分子和生物网络）都位于非欧几里得领域，可以自然地表示为图。由于神经网络强大的能力，将卷积和池化操作推广到图结构数据非常吸引人。

最近，人们已经进行了大量尝试将卷积操作推广到任意图，称为图神经网络 (GNN)。一般来说，这些算法可以分为两大类：频谱和空间方法。对于频谱方法，它们通常根据图傅里叶变换定义图卷积操作 (Bruna 等人，2013 年；Defferrard、Bresson 和 Vandergheynst，2016 年；Kipf 和 Welling，2017 年)。对于空间方法，图卷积操作是通过直接聚合来自其邻域的节点表示来设计的 (Hamilton、Ying 和 Leskovec，2017 年；Monti 等人，2017 年；Veliˇckovi´c 等人，2018 年；Morris 等人，2019 年)。上述大多数方法主要涉及跨图转换、传播和聚合节点特征，这可以符合消息传递方案 (Gilmer 等人，2017 年)。GNN 已应用于不同类型的图 (Veliˇckovi´c 等人，2018 年；Derr、Ma 和 Tang，2018 年)，并在许多图相关任务中取得了出色的性能，包括节点分类 (Kipf 和 Welling，2017 年)、链接预测 (Schlichtkrull 等人，2018 年；Zhang 等人，2018b 年) 和推荐 (Ying 等人，2018a 年) 等。

然而，尽管图池化操作在图分类任务中起着关键作用 (Ying 等人，2018b 年)，但图中的池化操作尚未得到广泛研究。图分类的目标是通过利用其节点特征和图结构信息来预测整个图的标签，即需要图级别表示。GNN 最初是为学习有意义的节点级别表示而设计的，因此生成图级别表示的常用方法是通过全局汇总图中的所有节点表示。尽管可行，但通过这种方式生成的图级别表示本质上仍然是“平的”，因为在整个过程中忽略了整个图结构信息。此外，GNN 只能通过边在节点之间传递消息，但不能以分层的方式聚合节点信息。同时，图通常具有不同的子结构，节点扮演着不同的角色，因此它们应以不同的方式为图级别表示做出贡献。例如，在蛋白质-蛋白质相互作用图中，某些子结构可能代表一些特定的功能，这对预测整个图的特性具有重要意义。为了捕获图的局部和全局结构信息，需要分层池化过程。

一些最新的工作专注于 GNN 中的分层池化过程 (Ying 等人，2018b 年；Gao 和 Ji，2019 年；Diehl，2019 年；Gao、Chen 和 Ji，2019 年)。这些模型通常通过将节点分组或采样到子图中来逐层粗化图，从而使整个图信息逐渐减少到分层诱导子图。然而，图池化操作仍有改进的余地。在节点分组方法中，分层池化方法 (Ying 等人，2018b 年；Diehl，2019 年) 具有很高的计算复杂性，需要额外的神经网络来减小节点数量。在节点采样方法中，生成的诱导子图 (Gao 和 Ji，2019 年；Lee、Lee 和 Kang，2019 年) 可能无法保留关键子结构，最终甚至丢失图拓扑信息的完整性。例如，在原始图中没有直接连接但共享许多共同邻居的两个节点可能在诱导子图中彼此无法到达，即使直观上它们在子图中应该是“接近”的。因此，扭曲的图结构会阻碍后续层中的消息传递。

为了解决上述局限性，我们提出了一个新的图池化操作符 HGP-SL 来学习分层图级别表示。具体来说，HGP-SL 首先根据我们定义的节点信息分数自适应地选择一组节点，充分利用节点特征和图拓扑信息。此外，我们提出的图池化操作是一个非参数步骤，因此在这个过程中不需要优化任何额外的参数。然后，我们将稀疏注意力 (Martins 和 Astudillo，2016 年) 机制应用于池化图，旨在学习一个保留原始图关键子结构的精炼图结构。我们将池化操作符集成到图卷积神经网络中进行图分类，整个过程可以以端到端的方式进行优化。总结一下，本文的主要贡献如下：

我们引入了一个新的图池化操作符 HGP-SL，它可以集成到各种图神经网络架构中。与卷积神经网络中的池化操作类似，我们提出的图池化操作是非参数的，并且非常容易实现。
据我们所知，我们是第一个为池化图设计结构学习机制的人，其优点是学习一个精炼的图结构来保留图的关键子结构。
我们在六个公共数据集上进行了广泛的实验，以证明 HGP-SL 的有效性以及与一系列最先进方法的优越性。

本文的模型

符号和问题公式

给定一组图数据 $G={G_1, G_2, ··· , G_n}$ ，其中每个图中的节点和边数可能相差很大。对于任意图 $G_i = (V_i, E_i, X_i)$ ，我们有 $n_i$ 和 $e_i$ 分别表示节点数和边数。令 $A_i ∈ R^{n_i×n_i} $为相邻矩阵，描述其边连接信息，$ Xi∈R^{n_i×f}$代表节点特征矩阵，其中 $f $ 是节点属性的维度。标签矩阵 $Y∈R^{n×c} $ 指示每个图的关联标签，即如果 $G_i $属于类别 j，则$ Y_{ij}=1 $，否则 $Y_{ij }= 0$ 。由于图结构和节点数量在层之间由于图池化操作而发生变化，我们进一步将输入到第 k 层的第 i 个图表示为 $G^k_i$ ，具有 $n^k_i$ 个节点。相邻矩阵和隐藏表示矩阵分别表示为 $A^k_i ∈ R^{n^k_i ×n^k_i}$ 和$ H^k_i ∈ R^{nk_i×d}$。使用上述符号，我们正式定义我们的问题如下：输入: 给定具有标签信息 $Y_L$ 的图数据集 $G_L$ ，图神经网络层的数量 K，池化比率 r，以及每层表示维度 d。输出: 我们的目标是使用图神经网络以端到端的方式预测 $G/G_L $的未知图标签。

图卷积神经网络

图卷积神经网络 (或 GCN) (Kipf 和 Welling，2017 年) 已被证明在各种具有挑战性的任务中非常高效，并取得了有希望的 performance。因此，我们选择 GCN 作为我们模型的构建块，并在本节中简要回顾其机制。请注意，我们提出的 HGP-SL 操作符也可以集成到其他图神经网络架构中，例如 GraphSAGE (Hamilton、Ying 和 Leskovec，2017 年) 和 GAT (Veliˇckovi´c 等人，2018 年)。我们将在实验部分讨论这一点。在 GCN 的第 k 层中，它将图 $G$ 的相邻矩阵 $A$ 和隐藏表示矩阵 $H_k$ 作为输入，然后下一层的输出将生成如下：

$H_{k+1} = σ(\tilde{D}^\frac{−1}{2} \tilde A \tilde D^\frac{−1}{2} H_kW^k) \quad (1)$

其中 σ(·) 是非线性激活函数，H0 = X, ˜A = A + I 是具有自连接的相邻矩阵。˜D 是 ˜A 的对角度矩阵，Wk ∈ Rdk×dk+1 是一个可训练的权重矩阵。为了方便参数调整，我们设置输出维度 dk+1 = dk = d 对于所有层。

整体神经网络架构

图 1 提供了我们提出的结合图神经网络的分层图池化与结构学习 (HGP-SL) 的概述，其中在图卷积操作之间添加了图池化操作。提出的 HGP-SL 操作符由两个主要组件组成：1) 图池化，它保留一组信息节点并形成一个更小的诱导子图；2) 结构学习，它学习一个精炼的图结构，用于池化子图。我们提出的结构学习的优点在于其能够保留基本图结构信息的能力，这将促进消息传递过程。正如这个说明性示例中所示，池化子图可能存在孤立节点，但直观上应该是连接的，因此它将阻碍后续层中特别是当从其邻域节点聚合信息时的信息传播。整个架构是卷积和池化操作的堆叠，因此可以以分层的方式进行图表示学习。然后，使用读取函数来汇总每个级别的节点表示，最终图级别表示是不同级别汇总的总和。最后，将图级别表示输入到具有 softmax 层的多层感知器 (MLP) 以执行图分类任务。在以下内容中，我们将介绍图池化和结构学习层的细节。

图 1：结合图神经网络的 HGP-SL 操作符架构概述。该图展示了 HGP-SL 操作符与图神经网络结合的架构。虚线框展示了 HGP-SL 的工作流程，包括图池化和结构学习。学习到的边在图中以虚线表示。这个过程（卷积和池化操作）会重复几次。然后，应用一个读取函数来汇总每个级别的节点表示，使其成为一个固定大小的表示，然后通过 MLP 层进行图分类。

图池化操作

在本节中，我们介绍我们提出的图池化操作，以实现对图数据的下采样。受 (Gao 和 Ji，2019 年；Lee、Lee 和 Kang，2019 年；Gao、Xiong 和 Frossard，2019 年) 的启发，池化操作识别一组信息节点来形成一个新的但更小的图。在这里，我们设计了一个非参数池化操作，它可以充分利用节点特征和图结构信息。我们提出的图池化操作的关键是定义一个标准，该标准指导节点选择过程。为了执行节点采样，我们首先引入一个称为节点信息分数的标准来评估每个节点在其邻域中包含的信息。通常，如果一个节点的表示可以通过其邻域表示重建，则意味着该节点可能在池化图中被删除，而几乎没有信息丢失。在这里，我们正式定义节点信息分数为节点表示本身与其从邻域构建的表示之间的曼哈顿距离：

$p = γ(G_i) = ||(I^k_i − (D^k_i)^{−1}A^k_i) H^k_i||_1, \quad(2)$

其中 Ak i ∈ Rnk i ×nk i 和 Hk i ∈ Rnk i ×d 是相邻和节点表示矩阵。∥ · ∥1 执行逐行 ℓ1 范数。Dk i 表示 Ak i 的对角度矩阵，Ik i 是单位矩阵。因此，我们得到 p ∈ Rni 编码图中每个节点的信息分数。在获得节点信息分数后，我们现在可以选择应该由池化操作保留的节点。为了近似图信息，我们选择保留不能很好地由其邻域表示的节点，即，在构建池化图时，相对较大的节点信息分数的节点将被保留，因为它们可以提供更多信息。具体来说，我们首先根据其节点信息分数对图中的节点进行排序，然后选择 top-rank作为保留的节点，如下所示：

$\begin{align} idx &= top-rank(p, ⌈r ∗ n^k_i⌉) \\ \hat H ^{k+1}_i &= H^k_i(idx, :) \\ A^{k+1}_i &= A^k_i(idx, idx), \end{align} \quad(3)$

其中 r 是池化比率，top-rank(·) 表示返回 top nk+1 i = ⌈r ∗ nk i ⌉ 值的索引的函数。Hk i (idx, :) 和 Ak i (idx, idx) 执行行或 (和) 列提取，以形成诱导子图的节点表示矩阵和相邻矩阵。因此，我们有 ˜Hk+1 i ∈ Rnk+1 i ×d 和 Ak+1 i ∈ Rnk+1 i ×nk+1 i 表示下一层的节点特征和图结构信息。

结构学习机制

在本节中，我们介绍了我们提出的结构学习机制如何在池化图中学习一个精炼的图结构。正如我们在图 1 中所说明的，池化操作可能导致高度相关的节点在诱导子图中断开连接，这会丢失图结构信息的完整性，并进一步阻碍后续层中的消息传递过程。同时，来自领域知识 (例如，社交网络) 或由人类建立的图结构 (例如，KNN 图) 通常对于图神经网络中的学习任务来说不是最优的，因为信息丢失或噪声。为了克服这个问题，(Li 等人，2018 年) 提出使用近似距离度量学习算法自适应地估计图拉普拉斯矩阵，这可能导致局部最优解。 (Jiang 等人，2019 年) 引入学习构建的图结构以进行节点标签估计，但它生成密集连接图，不适用于我们的分层图级别表示学习场景。在这里，我们开发了一个新的结构学习层，它通过稀疏注意力机制 (Martins 和 Astudillo，2016 年) 学习稀疏图结构。对于第 k 层第 k 层图 Gi 的池化子图 Gk i，我们将其结构信息 Ak i ∈ Rnk i ×nk i 和隐藏表示 Hk i ∈ Rnk i ×d 作为输入。我们的目标是学习一个精炼的图结构，该结构编码每对节点之间的潜在成对关系。形式上，我们使用一个参数化为权重向量 →a∈ R1×2d 的单层神经网络。然后，注意力机制计算节点 vp 和 vq 之间的相似度分数可以表示为：

$E^k_i(p, q) = σ(\vec{a} [H^k_i (p, :)||H^k_i(q, :)]^⊤) + λ·A^k_i(p, q), \quad(4)$

其中 σ(·) 是像 ReLU(·) 这样的激活函数，|| 表示连接操作。Hk i (p, :) ∈ R1×d 和 Hk i (q, :) ∈ R1×d 指的是矩阵 Hk i 的第 p 行和第 q 行，分别代表节点 vp 和 vq 的表示。具体来说，Ak i 编码诱导子图结构信息，其中 Ak i

(p, q) = 0 如果节点 vp 和 vq 没有直接连接。我们将 Ak i 集成到我们的结构学习层中，以使注意力机制倾向于在直接连接的节点之间给出一个相对较大的相似度分数，同时尝试学习断开连接的节点之间的潜在成对关系。λ 是它们之间的权衡参数。为了使相似度分数易于跨不同节点进行比较，我们可以使用 softmax 函数跨节点对其进行归一化：

$S^k_i(p, q) = \frac{exp(E^k_i(p, q))}{\sum^{n^k_i}_{m=1} exp(E^k_i (p, m))} , \quad(5)$

然而，softmax 变换总是具有非零值，从而导致密集的全连接图，这可能会将大量噪声引入到学习的结构中。因此，我们建议使用 sparsemax 函数 (Martins 和 Astudillo，2016 年)，它保留了 softmax 函数的大多数重要特性，并且还具有生成稀疏分布的能力。sparsemax(·) 函数旨在返回输入到概率单纯形的欧几里得投影，可以表示如下：

$\begin{align} S^k_i(p, q) &= sparsemax(E^k_i(p, q)) \\ sparsemax(E^k_i(p, q)) &= [E^k_i(p, q) − τ(E^k_i(p, :))]_+, \end{align} \quad{(6)}$

其中 [x]+ = max{0, x}，τ(·) 是一个阈值函数，它根据算法 1 中所示的程序返回一个阈值。因此，sparsemax(·) 保留阈值以上的值，而其他值将被截断为零，从而产生稀疏图结构。与 softmax 函数类似，sparsemax(·) 也具有非负和总和为一的特性，也就是说，Sk i (p, q) ≥ 0 且 Pnk i q=1 Sk i (p, q) = 1。证明过程可在补充材料中找到。

提高结构学习效率

对于大规模图，在学习结构 Sk i 时，计算每对节点之间的相似度将计算成本很高。如果我们进一步考虑图的局部化和平滑性特性，那么在节点的 h-hop 邻居内 (h = 2 或 3) 限制计算过程是合理的。因此，Sk i 的计算成本可以大大降低。

重新审视 GCN 和图池化

在获得精炼的图结构 Sk i 后，我们在以下层中根据 ˜Hk i 和 Sk i (而不是 Ak i) 执行图卷积和池化操作。因此，方程 (1) 可以简化如下：

$H^k_i = σ(S^k_i \tilde H^k_i W^k). \quad(7)$

由于学习的 Sk i 满足 Pnk i q=1 Sk i (p, q) = 1，因此我们得到对角矩阵 Dk i = Diag(d1, d2, · · · , dnk i )，其中 dp = Pnk i q Sk i (p, q)，这退化为单位矩阵 Ik i。同样，方程 (2) 中的节点信息分数的计算也可以简化如下：

$p = γ(G_i) =||(I^k_i − S^k_i)H^k_i||_1, \quad(8)$

这使得我们的模型非常易于实现。

读取函数和输出层

正如我们在图 1 中所证明的，神经网络架构重复了多次图卷积和池化操作，因此我们会在每个级别观察到不同大小的多个子图：H1 i ，H2 i ，· · · ，HK i。为了生成一个固定大小的图级别表示，我们设计了一个读取函数，该函数汇总子图中的所有节点表示。在这里，我们简单地使用每个子图中的平均池化和最大池化的连接，如下所示：

$r^k_i = R(H^k_i) = σ( \frac{1}{n^k_i}\sum^{h^k_i}_{p=1}H^k_i (p, :)|| \overset{d}{max} H^k_i (:, q)), \quad(9)$

其中 σ(·) 是一个非线性激活函数，rk i ∈ R2d。然后，我们将不同级别的读取输出相加以形成最终的图级别表示：

$z_i = r^1_i + r^2_i + ... + r^K_i, \quad(10)$

它总结了不同级别的图表示。最后，我们将图级别表示输入到具有 softmax 分类器的 MLP 层，损失函数定义为预测值在标签上的交叉熵：

$\begin{align} \hat Y &= softmax(MLP(Z)) \\ L &= − \sum_{i∈L}\sum^c_{j=1}Y_{ij}log \hat Y_{ij}, \end{align} \quad(11)$

其中 $ \hat Y_{ij} $ 表示图 Gi 属于类别 j 的预测概率，$ Y_{ij} $ 是真实值。L 表示具有标签的图训练集。

实验和分析

数据集

我们采用六个常用的公共基准数据集进行实证研究。六个数据集的统计信息总结在表 1 中，更多描述如下：ENZYMES (Borgwardt 等人，2005 年) 是蛋白质三级结构的数据库，每个酶属于 6 个 EC 顶层类别之一。PROTEINS 和 D&D (Dobson 和 Doig，2003 年) 是两个蛋白质图数据集，其中节点表示氨基酸，如果两个节点之间的距离小于 6 埃，则通过边连接。标签指示蛋白质是否为非酶。NCI1 和 NCI109 (Shervashidze 等人，2011 年) 是针对非小细胞肺癌和卵巢癌细胞系的两个生物数据集，其中每个图是一个化学化合物，节点和边分别代表原子和化学键。Mutagenicity (Kazius、McGuire 和 Bursi，2005 年) 是药物化学化合物数据集，可分为两类：致突变物和非致突变物。

基线

图核方法。这组方法通过利用精心设计的核来执行图分类。我们选择三个经典算法：GRAPHLET (Shervashidze 等人，2009 年)、最短路径核 (SP) (Borgwardt 和 Kriegel，2005 年) 和 Weisfeiler-Lehman 核 (WL) (Shervashidze 等人，2011 年) 作为基线。

图神经网络。这组方法包括代表性图神经网络：GCN (Kipf 和 Welling，2017 年)、GraphSAGE (Hamilton、Ying 和 Leskovec，2017 年) 和 GAT (Veliˇckovi´c 等人，2018 年)，它们旨在学习有意义的节点级别表示。因此，我们使用我们提出的读取函数来汇总节点表示以进行图分类。

图池化模型。在这组中，我们进一步考虑了许多将 GNN 与池化操作结合在一起的模型，用于图级别表示学习。Set2Set (Vinyals、Bengio 和 Kudlur，2015 年) 和 DGCNN (Zhang 等人，2018a 年) 是两种新的全局图池化算法。其他五个分层图池化模型，包括 DiffPool (Ying 等人，2018b 年)、gPool (Gao 和 Ji，2019 年)、SAGPool (Lee、Lee 和 Kang，2019 年)、EdgePool (Diehl，2019 年) 和 EigenPool (Ma 等人，2019 年)，也作为基线进行比较。

HGP-SL 变体。为了进一步分析我们提出的 HGP-SL 操作符的有效性，我们在这里考虑四个变体：HGP-SLNSL (无结构学习) 丢弃结构学习层以验证我们提出的结构学习模块的有效性，HGP-SLHOP 删除结构学习层并在其 h-hop 内连接节点，HGP-SLDEN (DENse) 使用结构学习层学习一个密集图结构，使用方程 (5) 中定义的 softmax 函数，HGP-SL 使用方程 (6) 中定义的 sparsemax 函数学习一个稀疏图结构。HGP-SLDEN 和 HGP-SL 使用效率改进的结构学习策略。

**实验和参数设置。**遵循许多先前的工作 (Ying 等人，2018b 年；Ma 等人，2019 年)，我们将每个数据集随机分为三部分：80% 作为训练集，10% 作为验证集，剩余 10% 作为测试集。我们重复此随机分割过程 10 次，并报告具有标准偏差的平均性能。对于基线算法，我们使用作者发布的源代码，并根据验证集将其超参数调整为最佳。为了确保公平比较，现有池化基线和我们的模型使用相同的神经网络架构。所有方法和数据集中节点表示的维度设置为 128。我们使用 PyTorch 实现 HGP-SL，并使用 Adam 优化器优化模型。学习率和权重衰减在 {0.1, 0.01, 0.001, 1e−4, 1e−5} 中搜索，池化比率 r ∈ [0.1, 0.9]，层 K ∈ [1, 5]。MLP 由三个全连接层组成，每层神经元的数量设置为 256、128、64，后跟 softmax 分类器。在训练过程中使用早期停止标准，即如果验证损失在 100 个连续的 epoch 中没有下降，则停止训练。源代码公开发布 4。

图分类的性能

表 2 报告了分类性能。总结如下，我们可以从结果中得出以下观察结果：

首先，我们可以从结果中得出一个总的观察结果，即我们提出的 HGP-SL 在所有数据集上始终优于其他最先进的基线。例如，我们的方法在 PROTEINS 数据集上比最佳基线提高了约 3.08%，比没有分层池化机制的 GCN 提高了 12.97%。这验证了添加图池化模块的必要性。
值得注意的是，传统的基于图核的方法表现出有竞争力的性能。然而，精心设计的图核通常涉及大量的人类领域知识，难以推广到具有任意结构的图。此外，提取图特征和执行图分类的两阶段程序可能会导致次优性能。
与先前工作 (Ma 等人，2019 年) 的发现一致，我们还观察到 GNN 组无法达到令人满意的结果。我们认为主要原因是因为它们在全局汇总节点表示时忽略了图结构信息，这进一步验证了添加图池化模块的必要性。
特别是，全局池化方法 Set2Set 和 DGCNN 被 HGP-SL 等大多数分层池化方法超越，但有少数例外。这是因为它们学习的图表示仍然是“平面的”，并且忽略了图中的层次结构信息或功能单元，这些单元在预测整个图标签方面发挥着重要作用。
我们注意到，分层池化模型在大多数基线中实现了相对更好的性能，这进一步证明了分层池化机制的有效性。其中，gPool 和 SAGPool 在 ENZYMES 数据集上的表现较差。这可能是由于每个类别的训练样本有限，导致神经网络过拟合。EdgePool 在这组竞争者中获得了最佳性能，它通过收缩图中的每一对节点来缩小图的大小。显然，我们的 HGP-SL 以不同的增益优于 EdgePool。
最后，HGP-SL 和 HGP-SLDEN 比 HGP-SLNSL 和 HGP-SLHOP 表现得更好，这证明了我们提出的结构学习层是有效的。此外，HGP-SLHOP 的表现比 HGP-SL 差。这是因为其 h-hop 内的断开连接的节点仍然无法相互到达。HGP-SL 进一步优于 HGP-SLDEN，这表明学习的密集图结构可能会引入额外的噪声信息并降低性能。此外，在现实场景中，图通常具有稀疏的拓扑结构，因此我们提出的 HGP-SL 可以比 HGP-SLDEN 学习更合理的图结构。

消融研究和可视化

HGP-SL 卷积神经网络架构。如前几节所述，我们提出的 HGP-SL 可以集成到各种图神经网络架构中。我们考虑三种最广泛使用的图卷积架构作为我们模型的构建块，以研究不同卷积操作的影响：GCN (Kipf 和 Welling，2017 年)、GraphSAGE (Hamilton、Ying 和 Leskovec，2017 年) 和 GAT (Veliˇckovi´c 等人，2018 年)。我们在三个数据集上评估它们，这些数据集涵盖了小型和大型数据集。他们的结果如表 3 所示。在剩余的数据集中也可以找到类似的结果，但由于空间有限，我们省略了它们。如表 3 所示，图分类的性能取决于选择的数据集和 HGP-SL 中的 GNN 类型。此外，我们还结合了 gPool 和 SAGPool 提出的 top-K 选择程序，并将其与我们提出的结构学习相结合。我们将其命名为 gPool-SL 和 SAGPool-SL 架构。从结果中，我们观察到 gPool-SL 和 SAGPool-SL 通过集成结构学习机制优于 gPool 和 SAGPool，这验证了我们提出的结构学习的有效性。

超参数分析。我们进一步研究了几个关键超参数的敏感性，通过在不同的尺度上改变它们。具体来说，我们研究神经网络层数 K、图表示维度 d 和池化比率 r 如何影响图分类性能。如图 2 所示，当分别设置 K = 3、d = 128 和 r = 0.8 时，HGP-SL 几乎在所有数据集上都实现了最佳性能。池化比率 r 不能太小，否则在池化过程中会丢失大部分图结构信息。

可视化。我们使用 networkx 5 可视化 HGP-SL 及其变体的池化结果。具体来说，我们从 PROTEINS 数据集中随机抽取一个包含 154 个节点的图。我们构建了一个三层图神经网络，池化比率设置为 0.5，然后生成三个池化图，节点分别为 77、39 和 20。我们在图 3 中绘制了第三个池化图。它显示 HGP-SLNSL 和 HGP-SLDEN 无法保留有意义的图拓扑结构，而 HGP-SL 在池化后能够保留原始蛋白质图相对合理的拓扑结构。

结论

在本文中，我们研究了图分类任务的图级别表示学习。我们提出了一种新的图池化操作符 HGP-SL，它使 GNN 能够学习分层的图表示。它还可以方便地集成到各种 GNN 架构中。具体来说，图池化操作是一个非参数步骤，它利用节点特征和图结构信息对图进行下采样。然后，在池化操作上堆叠一个结构学习层，旨在学习一个精炼的图结构，该结构可以最好地保留基本的拓扑信息。我们将提出的 HGP-SL 操作符与图卷积神经网络相结合，以进行图分类任务。在六个广泛使用的基准数据集上进行的综合实验表明，它与一系列最先进的方法相比具有优越性。