GNN_GIN论文笔记

借结课展示的强制力，更新 How Powerful Are Graph Neural Networks? 论文阅读笔记如下。

此工作发表于ICLR19，将GNN聚合邻居的方式与WL test做类比，理论上论证了GNN表达能力的上限为WL Subtree kernel，并根据分析提出GIN模型。论文提供了理解GNN表达能力的新思路，也启迪GNN模型架构发展的方向。

1. Background & Contributions

GNN近年来来发展迅速，在图表示学习方向取得耀眼成果。但大部分模型的设计都基于经验或直觉，缺少对GNN性质的深入理解分析。

本工作主要有4方面的贡献：(见下图)

2. Preliminaries

本工作讨论的为Message-Passing类的GNN模型，

此类模型每层进行AGGREGATE及COMBINE操作，分别负责收集邻居信息、结合邻居和节点自身信息更新hidden state。

若需要获得graph-level的图表示，则一般操作，是对网络最后一层的所有节点信息做聚合，即使用READOUT函数取得最后的图表示\(h_G\)。READOUT函数需要满足permutation invariant，常用的简单函数有如求和SUM。

本工作中涉及的WL Test是尝试判断图同构的经典方法。

图同构问题是图论中的经典问题，且是NP问题。若两个图是同构的，则存在双射函数，能将一个图中节点对应映射为另一图中对应节点。

如下图，图G、H为同构图，可通过双射的函数f找到两图中一一对应的节点。

WL Test是图同构的一个必要非充分的条件。其算法迭代执行如下两步：

每个节点收集一阶邻居的标签（是不是很像MPNN收集message的步骤）；
将聚合后的标签集合做hash，创建新的唯一标签；

每轮迭代后比较两图节点标签集合异同，如使用Jaccard积，如果不同则能说明两图非同构，否则两图可能是同构的。

一轮迭代的例子如下图。

3. This works

3.1 GNN表达能力上界

任何基于统计的表示学习模型，都想将同类样本映射到表示空间中相近甚至相同位置，不同类样本则尽量远离。

对于图表示学习，若说两个节点是一样的，则意味着节点的结构、特征都相同。具体的，则是两个节点导出的子树结构完全相同，且子树上的节点所有的特征也相同。

相应的，理想化的GNN能将上述相同节点映射到相同表示空间，不相似节点则映射至表示空间中彼此远离的位置。

实际上，满足上述要求的GNN，实质上是在解决图同构问题。

multiset为后文论证中常用概念，实质上用于描述每个节点所收到的邻居信息。

从Section 2中GNN与WL Test介绍可以发现，二者聚合邻居信息更新自身节点hidden state/label的过程在方式上相近。

作者在一系列证明后给出结论：基于aggregation的GNN模型，在分辨不同图任务中的能力上界为WL Test。

自然而然的问题，怎样构建GNN模型才能逼近表达能力上界呢？

作者进一步推导证明，模型的Aggregate, Combine, Readout函数都必须是单射函数。（与ideally GNN类似，单射函数保证了不同结构、特征的节点被映射为不同的嵌入表示）。

3.2 GIN

基于上图结论，作者提出Graph Isomorphism Network(GIN)。

其中，\(f^{(k)}\)为多层感知机MLP，ε为可学习的参数，二者再加上SUM共同保证了模型函数的单射性。

对应的，READOUT函数也要使用SUM来保证单射性。与通常做法不同，GIN为了把握全局的图结构，它的图表示\(h_G\)聚合了网络\({1,..,k}\)层的全部信息。

对于传统基于一阶邻居聚合的GNN模型，本工作发现它们有如下问题： 1. 所使用的单层perceptron在一定场景中是非单射的，表达能力不如MLPs； 1. Mean 和 Max-pooling 算子是非单射的，在下图结构中，节点v和v'聚合所得邻居信息的结果可能一致，意味着使用这两个算子可能丢失更具体的结构信息。