图分类《Hierarchical Graph Representation Learning with Differentiable Pooling》阅读笔记
图分类《Hierarchical Graph Representation Learning with Differentiable Pooling》阅读笔记
Abstract
对于图神经网络（GNNs），其主要包含三种核心任务：Node Classification、Link Prediction以及GraphClassification。本文着重探讨的是GraphClassification。作者指出，在现有的大多数GNN架构中缺乏对图层次结构的学习能力。原文描述如下：
However, current GNN methods are fundamentally shallow and lack hierarchical representation capability—a significant constraint in scenarios requiring graph classification, where the objective is to predict labels for entire graphs.
为此, 作者提出了一种名为DIFFPOOL 的图池化模块, 其支持学习图的不同层次表达并可集成多种端到端GNNs架构, 并且具有可微性特性。该模块通过为每个节点学习可微化的软聚类(soft) cluster assignment, 将这些节点分配至多个簇中, 这些簇随后被用作下一层_GNN Layer_ 的输入（即_coarsened input）。
Introduction
问题分析
对于 flat 的缺陷以及 hierarchical 的必要性方面，在作者的观点中提到：flat 本质上其核心特征是仅能借助_edges_来完成信息整合与推导过程，并非依赖于 hierarchical 的层级式整合机制。
A显著缺陷在于其结构上存在局限性，在现有的GNN架构中无法通过边传播信息实现层次化的聚合与推断能力。
该方法依次对每个节点生成其嵌入表示，并通过全局聚合汇总所有节点的嵌入表示。例如采用元素-wise加法运算或者设计的神经网络模型来处理整个集合。作者列举了四篇采用此类标准方法的文章：
[1] http://proceedings.mlr.press/v48/daib16.pdf
[3] https://arxiv.org/pdf/1704.01212.pdf
[4] https://arxiv.org/pdf/1511.05493.pdf
关于此类标准方法的 局限性 ，研究者仍指出 层次化 方法在实现 图分类 任务中更具优势
该作者所提出的办法与_CNNs_中的空间池化机制（即_Spatial Pooling Operation_）有相似之处。其主要难点在于_graph结构缺乏空间局部性（即_notion of spatial locality）。也就是说，在实际应用中难以直接将_nodes进行池化操作以达到统一效果。具体而言，在实际操作中由于_graph的拓扑结构无法方便地构建特定的patch区域。此外，在不同规模的_graphs中节点数和边的数量也会有所差异。
解决方案
该系统通过分组_nodes_搭建基于底层图基础上的层级式多层架构（hierarchical multi-layer scaffold）。 DIFFPOOL 在每个_Graph Neural Network（GNN）层中负责将_nodes_归入到相应的簇集合中。随后通过逐层叠加_Graph Neural Networks layers_以形成层次化的结构。
该图对DIFFPOOL模型进行高层次（high-level）概述或说明。具体而言，在每一个_hierarchical layer_中：首先，在每个节点(node)处初始化其嵌入表示(embedding)，这通常通过一个图神经网络层(GNN Layer)完成；接着，在嵌入空间中将节点进行聚类(cluster)，从而生成降阶后的图结构(coarsened graph)；最后，在生成的降阶图上再部署另一个图神经网络层(GNN Layer)，进一步提取高层次特征。
Proposed Method
首先是 Graph 的 Notation ：
GNNs 的"Message-Passing "结构：
H代表node embeddings, 即Messages. M被定义为消息传播函数. DIFFPOOL方法对于M不敏感, 即它适用于各种不同的M.
在_GNN Layer中生成了节点表示_Z = GNN(A,X)，其中邻接矩阵_A被采用。为了构建一个压缩后的图（假设其大小为_m < n），我们引入了新的邻接矩阵_A'（尺寸为nxn）以及相应的表示_Z'（尺寸为mxd）。其压缩后的图可作为后续层输入进行操作。这一过程将被重复使用K次（如上文所述）。当前面临的问题在于如何利用本层生成的数据来进行节点聚类或池化操作，并且这种方法需适用于所有可能的比例_M以及每一层。
如何获取 coarsened graph
定义第 l 层的 Cluster Assignment Matrix ：
S 每一行都代表_l_层的一个_node(cluster)，而每一列则代表_l+1_层的一个_node(cluster)。作者将其命名为 soft assignment，并建议读者通过查看代码来更好地理解这一机制。
我在奥格这里找到了一个法术师，并且打开了一个传送门。
DIFFPOOL 定义如下：
Real matrix A represents a fully connected edge-weighted graph (a fully connected edge-weighted graph) in the context of clustering analysis. Here, A_ij signifies the connectivity strength between cluster i and cluster j (Connectivity Strength). Specifically, the ith row of X records the embedding vector for cluster i. The coarsened adjacency matrix and the cluster embedding matrix X will be employed as the input to another GNN layer, providing a hierarchical representation foundation for subsequent clustering tasks.
如何获取 assignment matrix S 和 embedding matrices Z
作者基于cluster node features X 和 coarsened adjacency matrix A 作为输入参数，在两个各自独立设计的GNN层中分别完成对变量S和变量Z值的学习与计算过程。其中用于生成Z的部分属于标准型GNN架构，并被命名为embedding GNN模块。
生成 S 的 GNN 为加了 softmax 的 GNN Layer ：
这里的 softmax 是row-wise fashion 的。从矩阵乘法的角度去看这个公式：
等价于(l+1, l) \times (l, d) = (l+1, d)，即通过多维度特征上的加权聚合来实现节点信息的融合。其中多个权重被作者称为hierarchical权重。关于每一层中cluster数量的设定均为超参数，在最终阶段将cluster数目缩减至1以生成图嵌入向量。
关于优化
涉及梯度下降法来实现优化过程。然而作者指出在训练过程中面临挑战。
涉及梯度下降法来实现优化过程。然而作者指出在训练过程中面临挑战。
所以这里采用了additional link prediction task ，使得关键节点得以被有效地_gathered_在一起。对于每一层，作者均进行了如下方程的优化：
作者指出PoolGNN的另一个关键特性是每个节点聚类归属结果应倾向于呈现one-hot分布形式。这有助于更加清晰地刻画不同聚类之间的关联关系。基于此原则性要求作者提出了一种优化方法（如公式所示），以实现上述目标
在每一层中将L_LP、L_E与分类损失结合使用。作者指出使用这两个损失函数会导致收敛速度减缓，尽管整体效果有所提升。
Conclusion
精巧的艺术品，向优秀的作者致敬
除了复杂度略大
才疏学浅，欢迎批评
慢慢来比较快