全网最详细解读《GIN-HOW POWERFUL ARE GRAPH NEURAL NETWORKS》

Abstract + Introduction

关于邻居聚合策略以及池化策略都有很多相关的研究，并且这些 GNNs 已经达到了目前最先进的性能，然而对于 GNNs 的各种性质以及性能上限我们并没有一个理论性的认识，也没有对 GNN 表征能力的形式化分析。言下之意：这些 GNNs 模型的研究虽然效果很好，但并没有系统理论的支撑，并不知道是基于什么导致了更好的性能，而是基于经验主义的。

GNN 也能够具备跟 WL-test 一样强大的判别能力。

作者研究了 multiset 聚合函数的多种变体，并从理论上分析了聚合函数对于区分不同 multiset 的判别能力。为了具备强大的表征能力，GNN 必须将不同的 multiset 聚合成不同的表示。只要聚合函数能够达到跟 hash 散列一样的单射性，那么理论上是能够达到跟 WL-test 一样的判别能力的。因此，聚合函数的单射性越强，GNN 的表征能力就越强。

在上述条件下，建立了邻居聚合以及 Graph readout 的 condition。
识别了当下流行的 GNN 变体（GCN，GraphSAGE）无法区分的图结构，并精确表征了其能够成功捕捉的图结构类型。
开发了一个简单的神经网络架构 GIN，并且证明了它在表征能力上与 WL-test 性能相当。

作者通过图数据集的分类任务验证了理论，其中 GNN 的表征能力对于捕获图结构的信息至关重要。研究比较了基于不同聚合函数 GNNs，结果证明性能最强大的 GIN 模型从经验的角度来看也具备高表征能力，几乎能够完美拟合训练数据，而一些较弱的 GNN 变体则通常欠拟合训练数据。此外，表征能力更强的 GNNs 在测试集精度上比其他模型性能更优，主要表现在图分类任务上达到了目前最优的性能。

PRELIMINARIES

图分类任务：给定图集合 \(\{G_1, G_2, ..., G_n\} ∈ G\ 并且其标签集合为 \(\{y_1, y_2, ..., y_n\} ∈ Y\，目标是学习每个图的表征向量 \(h_G\ 以预测图的标签，整个过程可以被表示为 \(y_G = g(h_G\

Graph Neural Networks. GNNs 利用图的结构和节点特征 \(X_v\ 去学习一个节点表征向量 \(h_v\（或是整个图的表征向量 \(h_G\）。当前 GNNs 都采用了邻居聚合策略，通过聚合策略迭代更新每个节点的表征向量。经过 k 次聚合迭代后，一个节点的表征能够捕捉 k-hop 邻居节点的特征信息。形式上，第 k 层 GNN 可表示为：

公式表达的意思即：先聚合节点 \(v\ 的邻居节点表征，得到 \(a_v(k\，然后结合 \(a_v(k\ 与节点自身的表征 \(h_v(k-1\ 生成节点 \(v\ 新的表征 \(h_v(k\。

即：GraphSAGE 会将所有的邻居节点进行一个线性投影，然后通过 ReLU 激活，再取出其中的最大值作为邻居聚合后的表征向量。这个邻居节点 multiset 的表征向量会跟节点自身的表征向量拼在一起作线性投影。

而许多其他的 GNNs 聚合/Combine 过程都能够被公式 2.1 表示。

Weisfeiler-Lehman test. 图同构问题是指 判别两个图是否具备拓扑相同性。而 WL-test 则是针对图同构问题的一个高效的算法，它的判别操作过程类似于 GNN 中的邻居聚合，wL-test 迭代地聚合节点与邻居节点的标签，将聚合的标签进行一次 hash 散列为一个新的唯一标签。如果在某次迭代中，两个图之间的节点标签不同，则可以判定两个图是非同构的。

而 Shervashidze et al. 又基于 WL-test 提出了 WL subtree kernel 算法，该算法能够评估两个图的相似性。

如果我们能够在图分类任务中，精确而高效地判定出两个图的相似性，那么在预测任务中，就更容易确定两个图是否属于一个类别。而 GNN 的聚合操作与 WL-test 高度相似，因此我们可以合理怀疑：GNN 能够在图相似性评估的过程（图表征学习）中达到 WL-test 的性能水平。只要聚合函数能起到跟 hash 函数一样的单射性，那么理论上二者是能够达到同级别的性能水平的。

3 THEORETICAL FRAMEWORK: OVERVIEW

整个论文中，作者假设节点的特征向量是离散的（毕竟特征向量值连续的情况下，99.9999% 都不会聚合出一个相同的嵌入，作者也就没牛逼可吹了）。作者将这样的图称为有限图。对于有限图，更深卷积层的特征向量也同样是离散的。

为了研究 GNN 的表征能力，作者分析了 GNN 什么情况下会将两个节点映射到嵌入空间中的相同位置。直观地说，一个最强大的 GNN 只有在两个节点具备相同的邻居子树结构时才会将它们映射到同一个嵌入空间的位置。我们也可以将问题简化为：GNN是否映射两个相同的邻域特征（multiset）映射到相同的嵌入表示。毕竟最强大的 GNN 永远不会将两个不同的邻域特征映射到同一个嵌入，即聚合函数必须是单射 injective 的。因此，我们将 GNN 的聚合函数抽象为一种可以由 neural network 表示的 multiset function，并分析该函数是否能够表示为 injective multiset function。

injective function，即单射函数，表示输入跟输出是一对一的关系，即对于不同的输入x，f(x 永远不可能存在相同的输出。

4 BUILDING POWERFUL GRAPH NEURAL NETWORKS

首先我们给出了 GNN 模型的最大表征能力，即具备单射性的聚合策略。理想情况下，最强大的 GNN 可以通过将不同的图结构映射到不同的嵌入空间来区分它们。然而，这种将任意两个不同的 Graph 映射到不同的嵌入空间的能力意味着要解决一个困难的图同构问题。即：我们希望同构图映射到相同的嵌入空间，非同构图映射到不同的嵌入空间。但在我们的分析中，我们利用一个稍微弱一些的标准来定义 GNN 的表征能力 —— WL-test，它通常能够很好地区分非同构图，并且性能也较高，除了少数例外情况（比如正则图）。

因此，任何基于聚合的 GNN 在区分不同的图方面最多也就跟 WL-test 一样强大。那么是否存在与 WL-test 一样强大的 GNN 呢？

GNN 通过式子 \(h_v(k=φ(h_v(k-1, f(\{h_u(k-1:u∈N(v\}\ 聚合并且递归更新节点特征

GNN 的 graph-level readout 入参也是 multisets（即节点特征 \(\{h_v(k\}\），并且 readout 满足 injective。

此外，描述学习到的特征在函数图像中的亲密度也是一件非常有趣的事情。我们将把这些问题留到未来的工作，并且将重心放到输入节点特征来自可数集合的情况。

除了区分不同的图以外，GNN 还有一个重要的优点，即能够捕获图结构的相似性。而 WL-test 是无法捕获图之间的相似性的，这也是为什么我们不直接采用 WL-test 到图数据任务处理中。

相比之下，满足 Theorem 3 的 GNN 通过学习将邻居节点特征聚合映射到一个向量空间，相隔较远距离的嵌入大概率不属于一个类别，而相隔较近的嵌入则同属一个类别。这使得 GNN 不仅可以区分不同的图结构，还可以将近似的图结构映射到相似的嵌入，并捕获图结构之间的依赖关系。捕获节点的结构相似性被证明是有助于泛化的，特别是当邻居的特征向量的是稀疏的，或者存在噪声边缘特征时。

4.1 GRAPH ISOMORPHISM NETWORK (GIN

为了建模一个单射邻居聚合函数，作者提出了一种 “deep multisets” 理论，即：用神经网络参数化 “通用的单射邻居聚合函数”。下一个 Lemma 说明了 sum-aggregators 能够在邻居聚合函数上具备单射的性质。

引理5，主要就是证明了 sum-aggregation 的单射性，我们明白这一点即可。

Deep MultiSets 和 sets 最重要的一个区别是：是否满足单射的性质。比如 mean-aggregator 就不满足单射性质。（后面会解释 mean-aggregation 为什么不满足单射性）

以 Lemma 5. 中的 “通用的单射邻居聚合函数” 建模机制作为构建模块，我们可以构想出一个聚合方案，该方案能够表示一个 “入参为节点以及其邻居 multiset” 的泛函数，因此满足 Theorem 3. 中的 injective condition。下一个推论给出了一个简单而具体的公式。

其实跟引理5 差不太多，只需要把 c 理解为节点自身，X 理解为节点邻居多集即可。

在第一次迭代聚合时，若输入的特征是 one-hot encodings，那么我们在进行 sum 聚合之前并不需要 MLPs，因为这些特征的求和操作已经满足单射性质。我们可以让 \(\epsilon\ 作为一个可学习参数或是固定参数。那么此时 GIN 的聚合操作可以由如下公式表示：

4.2 GRAPH-LEVEL READOUT OF GIN

通过 GIN 学习的节点嵌入可以直接用于节点分类问题以及链路预测问题，但对于图分类问题，我们提出了以下方法：通过节点的嵌入构造整个图的嵌入。一般我们会把这个过程称为 Graph Readout。

因此，作者利用到了每一次迭代聚合的节点表征信息，通过类似 Jumping Knowledge Networks (Xu et al., 2018 的架构来实现，并用下列 Readout concat 方案替换 Eq 2.4：

基于 Theorem 3. 和 Corollary 6. GNN 能够很好地推广 WL-test 和 WL subtree kernel（在求和之前，我们不需要额外的 MLP，原因跟 Eq 4.1 的相同，此时的 sum 已经满足了单射性质）

5 LESS POWERFUL BUT STILL INTERESTING GNNS

均值池化或最大池化，而不采用 sum（不采用求和而是采用 mean or max 的聚合策略是否可行）

我们将会惊讶地发现，这些 GNN 变体会无法识别一些简单的图，并且性能也不如 wL-test 强大。但尽管如此，采用 mean aggregators 的模型（如 GCN）在节点分类任务中还是会得到不错的结果。为了更便于理解，我们将精确地描述不同 GNN 变体能或不能捕捉到的图，并且讨论有关 “图学习” 的含义。

5.1 1-LAYER PERCEPTRONS ARE NOT SUFFICIENT

虽然有了偏置项和足够大的输出维度，单层感知机大概率能够区分不同的 multisets，但尽管如此，与采用多层感知机的模型不同，单层感知机即便是带有偏置项，也不属于 multisets function 的通用逼近函数。因此，即便 1-layer GNN 能够将不同的图嵌入到不同的表征，但这种嵌入可能无法充分捕获两个图的相似性，并且对于简单分类器（比如线性分类器）来说很难拟合。在 Section 7 中我们将会看到，1-layer GNN 在应用图分类任务时，会导致严重的欠拟合，并且在 test Accuracy 方面也通常比 MLPs GNN 表现差。

5.2 STRUCTURES THAT CONFUSE MEAN AND MAX-POOLING

平均池化聚合以及最大池化聚合都仍然属于 well-defined 的多集函数，因为它们都是排列不变的。但它们都不满足单射性。图2根据聚合器的表征能力对三种聚合器进行了排名，并且图3阐述了 max-pooling 和 mean-pooling 无法区分的结构。节点颜色表明了不同的节点特征，并且我们假设 GNNs 会在 combine 操作之前先执行 Aggregation。

Fig.3a 表明，平均和最大池化对于区分具备重复特征的节点是困难的。我们定义 \(h_{color}\ 为节点特征的映射结果（相同特征会映射到相同的颜色）。Fig.3b 表明，对于两个不同结构的图，最大池化聚合 \(max(h_{g}, h_{r}\ and \(max (h_{g}, h_{r}, h_{r}\ 能够取到相同的表征。因此最大池化聚合并不能区分这两张图。但 sum aggregator 仍然能够区分。同样地，对于 Fig.3c，mean and max pooling 同样会无法区分，因为 \(\frac{1}{2}(hg + hr = \frac{1}{4}(hg + hg + hr + hr\

5.3 MEAN LEARNS DISTRIBUTIONS

若在 graph 任务中，若 提取统计信息以及信息分布 比 提取特定结构信息 更加重要，那么 mean aggregator 的效果还不错。此外，若节点特征多样且重复性较少时，mean aggregator 跟 sum aggregator 的效果一样好。或许这能够被解释为什么平均存在一定的局限性，但平均聚合 GNNs 对节点分类的任务依然很有效，比如文章主题分类，社群检测这类任务，它们都属于节点特征丰富，且邻域特征分布为分类任务提供了更明显的信息。

5.4 MAX-POOLING LEARNS SETS WITH DISTINCT ELEMENTS

可以将 3D 点云理解为三维图像，一般会应用于建筑安全隐患识别，城市管理等。

5.5 REMARKS ON OTHER AGGREGATORS

还有一些其他的非标准邻居聚合方式，但本篇论文并未提及，比如：weighted average via attention (Velickovic et al., 2018，LSTM pooling (Hamilton et al., 2017a; Murphy et al., 2018. 本文强调的是：该理论框架足够普适去描述基于聚合方式的 GNNs 的表征性能。未来会考虑应用框架去分析和理解其他的聚合方式。

6 OTHER RELATED WORK

相比之下，上述结论为分析和描述一个广泛类别的 GNN 的表达能力提供了一个更一般的理论框架。最近，许多基于 GNN 的架构被提出，包括和聚合和 MLP（巴塔格利亚等人，2016；斯卡塞利等人，2009b；Duvenaud等人，2015），而大多数没有理论推导。与许多先前的 GNN 架构相比，我们的图同构网络（GIN）在理论上更加充分，并且简单而强大。

7 EXPERIMENTS

在实验部分比较了 GIN 于其他较弱的 GNN 变体在测试集，训练集上的表现。训练集能够去评估模型的表征能力，且测试集能评估模型的泛化能力。

Datasets. 我们采用 9 个图分类 benchmarks：4个生物信息学数据集（MUTAG，PTC，NCI1，PROTEINS）以及5个社交网络数据集（COLLAB，IMDB-BINARY，IMDB-MULTI，REDDIT-BINARY，REDDIT-MULTI5K）。重要的是，我们实验目的并不是让模型依赖于输入节点的特征，而是主要让模型从网络结构中学习。因此，在生物信息学 Graph 中，节点具有分类输入特征；但在社交网络中，节点没有特征。

Models and configurations. 我们评估了 GINs（Eqs.4.1 and 4.2）以及其他 less powerful GNN 变体。而针对 GIN 框架，我们考虑它的两个变体：

一个更简单的 GIN-0，其中 Eq.4.1 的参数 \(\epsilon\ 固定为0。

在 Fig.4 以及 Table.1 中，模型会根据 其采用的聚合方式/感知机的层数 来命名，例如 mean-1-layer 和 max-1-layer 分别对应了 GCN 和 GraphSAGE，并且会在此基础上进行较小的修改。我们对 GINs 以及 GNN 变体都采用相同的 Graph Readout（Eq.4.2），为了更好的测试性能，生物学信息数据集上采用 sum readout，社交网络数据集采用 mean readout。

batch size：
dropout ratio：{0, 0.5} after dense layer
epochs number：调整为 10 次平均交叉验证精度最好的 single epoch

注意，由于数据集size较小，使用验证集进行超参调整时非常不稳定的，比如 MUTAG 验证集只包含 18 条数据。

hidden units of size 64
minibatch of size 128
dropout ratio 0.5

为了比较，WL subtree kernel 的训练精度也会被报告，其中我们将迭代次数设置为4，对比 5 GNN layers。

Baselines. 我们将上述 GNNs 与最先进的图分类基准进行比较：

最先进的深度学习架构 —— DCNN，PATCHY-SAN，DGCNN
Anonymous Walk Embeddings

7.1 RESULTS

Training set performance. 我们通过比较 GNNs 的训练精度来验证之前对 GNN 模型表征能力的理论分析。具备较高表征能力的模型应该具备较高的训练准确度。Fig.4 展示了具备相同超参的 GINs 和较弱的 GNN 变体的训练曲线。首先，理论上最强大的 GNN，即 GIN-\(\epsilon\ 和 GIN-0 都能够完美地拟合所有的训练集。

模型表征能力进行的排名一致，在训练精度方面

sum aggregators 大于 mean / max aggregators

Test set performance.

首先，对于 GINs，尤其是 GIN-0，在 9 个数据集上都比较弱的 GNN 变体表现都好。GINs 在社交网络数据集上表现更好，这种类型的数据包含了大量的训练图数据。

即使提供节点的 degree 作为输入特征，基于 mean-aggregation GNNs 也远远不如 sum-aggregation GNNs（在 REDDIT-BINARY 数据集上，mean-mlp aggregation 准确率为 71.2±4.6%，在REDDIT-MULTI5K 准确率为 41.3±2.1%）

8 CONCLUSION

在本文中，我们开发了一个关于 GNNs 表征能力推到的理论基础，并证明了当下流行的 GNN variants 的表征能力上限。我们还基于邻域聚合设计了一个可证明的性能最强大的 GNN。未来工作的一个有趣方向是超越邻域聚合（或消息传递），以追求更强大的图学习架构。为了完成这个愿景，理解和改进 GNN 的泛化特性以及更好地理解它们的优化前景也会很有趣。

编程笔记 » 全网最详细解读《GIN-HOW POWERFUL ARE GRAPH NEURAL NETWORKS》