《HOW POWERFUL ARE GRAPH NEURAL NETWORKS?》论文阅读

发表于ICLR 2019.

abstract

尽管GNN彻底改变了图表示学习，但是在表示属性上存在限制。我们提出了一个理论框架来分析捕捉不同的图结构的GNNs的表达能力。我们的结果展示了GNN变体的分辨能力，例如GCN和GraphSAGE难以分辨一些简单的图结构。之后我们提出了一种简单的架构，是GNN类别里最具表达能力的，和weisfeiler-lehman graph isomorphism test一样有效。我们在一系列的图分类benchmarks上进行了实验来测试我们的理论发现，证实了我们的模型达到了sota的表现。

1.introduction

以往的GNN都基于实验直觉，启发式算法或者试错法（experimental trail-and-error）。对GNNs的理论分析很少，GNN的普通分析表达能力受限。

于是我们提出了分析GNNs的表达能力的理论框架。我们的框架被GNNs与Weisfeiler-Lehman graph isomorphism test（用于辨别图类别的有效的test）之间的close connection所激发灵感。和GNNs相似，the WL test迭代地更新节点特征通过聚合邻居节点的特征向量。使得WL test很powerful的原因是通过映射聚合更新将不同的节点邻居映射味不同的特征向量。我们的key insight是GNN可以获得像WL test的强分辨能力：如果GNN的聚合策略可以具有高表达能力以及能够建模映射函数。

为了数学化上述的insight，我们的框架首先提出给定的节点的邻居的特征向量味multiset（具有重复元素的set），于是GNN的聚合过程就可以被视为是在multiset之上的聚合函数。为了含有强表达能力，GNN必须能够聚合不同的multisets到不同的表征上去。我们严格地学习了multiset函数的变体并且理论地分析了它们的表达能力。mutiset function的辨别能力越强，则相应的GNN的表达能力也越强。

主要的结果概括如下：
1)GNNs在辨别图结构上至多和WL test一样powerful。
2)我们提出了GNNs和WL test一样powerful的再邻居聚合和graph readout函数上需要的条件。
3)我们提出popular的GNN变体（如GCN和graphSAGE）无法辨别部分图结构，之后我们精确地提出了GNN-based models可以辨别的图结构。
4)我们提出了一种简单的神经架构，graph isomorphism network(GIN),证明了它的辨别能力/表达能力和WL test一样。

我们在图分类数据集上验证了我们的理论，GNN的表达能力对于捕捉图结构是至关重要的。特别地，我们比较了具有不同的聚合函数的GNNs的表现。我们的结果验证了最powerful的GNN是GIN，理论地说明了适应于训练数据的高表达能力，其他的GNN变体经常欠拟合于训练数据。在test set上的图分类GIN得到了sota。

2.preliminaries

weisfeiler-lehman test：the graph isomorphism problem用于辨别两张图是否拓扑一致。这是一个具有挑战性的问题：目前不存在多项式时间的算法。除了一些极端情况，WL test是一种高效的辨别图的种类的算法。它的一维形式，“naive vertex refinement”，和GNNs的邻居聚合过程是相似的。WL test的迭代过程如下：(1)聚合节点和它的邻居的labels （2）将聚合出的labels hash到unique的新labels上去。这种算法决定了两个图是否是同构的：如果在某轮迭代上，两个图的节点的labels不同。

基于WL test，WL subtree kernel用于测量两张图的相似程度。kernel使用WL test在不同iterations的节点labels的counts作为图的特征向量。WL test在第k次迭代的节点的label代表了以该节点为root的高度为k的子图结构。因此，WL subtree kernel的图结构本质上是图中不同rooted subtrees的counts。

3.theoretical framework：overview

GNN循环迭代更新每个节点的特征向量来捕捉网络结构以及节点周围的节点的特征。在本篇论文中，我们假定节点的输入特征来自于可数的体系（universe）。对于有限图，any固定model深层的节点特征也来自于可数的universe。为了表达的简洁性，我们可以为每个特征向量赋予一个unique label in { a , b , c , . . . } \{a,b,c,...\} {a,b,c,...}。于是邻居节点的集合的特征向量形成了一个multiset：相同的元素可以在集合中出现多次（因为不同的节点可以具有完全相同的特征向量）。

definition 1: multiset：multiset是一个2-tuple：$X=(S,m)$，$S$是multiset内的单独元素,$m$为各元素在multiset中出现的重数：$S\to \mathbb{N}>=1$。

为了学习GNN的表达能力，我们分析了什么时候GNN将两个节点映射到embedding空间的相同位置。一个具有最强表达能力的GNN应该当两个节点的相关节点具有完全相同的特征的完全相同的子树结构，则将他们映射到相同的location。由于子树是通过节点邻居来迭代定义的，我们可以简化我们的分析为GNN是否能将两个邻居（2 multisets）映射到相同的embedding or representation。我们将GNN的聚合策略抽象为一系列的函数over multisets（可以使用NN来表达），然后分析它们是否可以代表injective multiset functions。（强调这种injective，完成强表达能力的映射）。

4.building powerful graph neural networks

首先，我们描述了GNN-based model的最大表达能力。理想地，最强的GNN应该能够通过将不同的图结构映射成为embedding space中不同的表征，其实是解决图同构问题（graph isomorphism problem）。同构图映射为相同的表征，非同构图映射为不同的表征。在我们的分析中，我们描述GNNs的表达能力通过一个slightly weaker criterion：一个强大的启发式算法：WL graph isomorphism test，它在通常情况下都表现良好，除了一些特殊情况（如：regular graphs）。

lemma 2： 若$G_1,G_2$是两个非同构图。若一个神经网络$A:G\to {\mathbb{R}}^d$将$G_1,G_2$映射到不同的embeddings，则WL test也判断$G_1,G_2$为非同构的。

任何aggregation-based的GNN在判别不同图上的性能最多和WL test一样。一个自然的follow-up问题是：是否存在GNNs和WL test的性能一致？我们的答案是，是：如果neighbor aggregation和graph-level readout functions是injective的，那么GNN和WL test一样powerful。

theorem 3： 令$A:G\to {\mathbb{R}}^d$为一个GNN。当具有充足数量的GNN层，$A$将任意图$G_1,G_2$(WL test验证为非同构的)映射到不同的embeddings，如果下面的条件满足：
a) $A$迭代地聚合和更新节点特征通过：

h v ( k ) = ϕ ( h v ( k − 1 ) , f ( { h u ( k − 1 ) : u ∈ N ( v ) } ) ) , h_v^{(k)}=\phi(h_v^{(k-1)},f(\{h_u^{(k-1)}:u \in N(v)\})), hv(k)​=ϕ(hv(k−1)​,f({hu(k−1)​:u∈N(v)})), 其中 $f$作用于multisets上， $\varphi$为injective的（单射）。
b) $A$的graph-level readout，作用于节点特征的multiset { h v ( k ) } \{h_v^{(k)}\} {hv(k)​}上的,是injective的。

对于可数集合，injectiveness很好地描述了函数是否保持了输入的distinctness。对于不可数集合，节点的特征是连续的，需要更深层的考虑。描述学习到的特征在函数图中how close是具有研究意义的，我们将对此进行future work，并且聚焦于输入的节点特征是否来自于可数集合（可以是一个不可数集合${\mathbb{R}}^d$的子集）。

lemma 4： 假定输入特征空间$X$是可数的，设被GNN的第k层拟合的函数为$g^{(k)}$ for $k=1,...,L$，其中$g^{(1)}$定义于范围固定的multisets上。$g^{(k)}$的范围：i.e. 节点隐藏特征空间$h_v^{(k)}$对于所有的$k=1,...,L$是可数的。

对于GNN，除了辨别不同图以外，捕捉图结构的相似性也是很值得讨论的。WL test中的节点特征向量本质上是one-hot encodings因此无法捕捉subtrees的相似性。相反，GNN满足theorem 3中的准则，将WL test泛化到学习embedding上，它将subtrees映射到低维空间。这使得GNNs不仅能够判别不同的图结构还能够将相似的图结构映射为相似的embeddings以及捕捉图结构之间的依赖性。对于不同图上的子树的共现性是稀疏的或者存在noisy edges以及节点特征的情况，捕捉节点labels的结构相似性对于泛化是特别有效的。

4.1 graph isomorphism network（GIN）

在分析了最强GNN的条件，我们接下来提出一个简单的构架，GIN，它满足了theorem 3中的条件。该模型推广了WL test因此达到了GNNs的最大辨别能力。

为了对于邻居聚合来建模injective multiset函数，我们发展了deep multisets的理论，i.e. 利用神经网络来参数化universal multiset functions。我们的下一个lemma陈述了sum aggregator可以代表injective（universal functions over multisets）。

lemma 5: 假设$\mathcal{X}$是可数的。存在一个函数$f:\mathcal{X}\to {\mathbb{R}}^n$，所以对于每个multiset $X\subset \mathcal{X}$ , $h(X)={\sum }_{x\in X}f(x)$都是unique的。更进一步，任何multiset函数$g$可以被分解为$g(X)=\varphi ({\sum }_{x\in X}f(x))$。

一个重要的区别在deep multisets和sets之间的是certain popular injective set functions，比如mean aggregator，不是injective multiset functions。以引理 5 中通用多集函数的建模机制为构建块，我们可以设想聚合方案，该方案可以表示节点及其邻居的多集上的通用函数，从而满足定理 3 中的单射条件（a）。 我们的下一个推论在许多这样的聚合方案中提供了一个简单而具体的公式。

corollary 5: 假设$\mathcal{X}$是可数的。存在一个函数:$f:\mathcal{X}\to {\mathbb{R}}^n$，对于无限多种$ϵ$,包括无理数，对于每个对$(c,X),c\in \mathcal{X},X\subset \mathcal{X}$是一个固定范围内的multiset,$h(c,X)=(1+ϵ)\cdot f(c)+{\sum }_{x\in X}f(x)$是unique的。更进一步，对于这样的pair的任何函数$g$可以被分解为$g(c,X)=\phi ((1+ϵ)\cdot f(c)+{\sum }_{x\in X}f(x))$.

我们可以利用MLPs来学习推论6中的$f,g$。实际上，我们可以用一个MLP来拟合$f^{(k+1)}\circ {\phi }^{(k)}$（其中$\circ$表示复合映射），因为MLP可以表示函数的分解。在第一轮迭代中，我们在求和之前不需要MLP如果输入特征为one-hot encodings，因为它们的summation是单射的。我们可以令$ϵ$为一个固定的标量或者是一个可学习的参数。GIN更新节点的表征的过程如下：

$h_v^{(k)}=ML{P}^{(k)}((1+{ϵ}^{(k)})\cdot h_v^{(k-1)}+{\sum }_{u\in N(v)}{h}_u^{(k-1)}).（4.1）$ 事实上，可能存在其他很多的powerful GNNs。GIN只是其中一种最强的GNN，GIN还很简洁。

4.2 graph-level readout of GIN

充足数量的迭代是实现好的分辨能力的关键。然而，早期的迭代可能泛化得更好。为了考虑所有的结构信息，我们使用了模型的所有iteration的信息。

h G = C O N C A T ( R E A D O U T ( { h v ( k ) ∣ v ∈ G } ) ∣ k = 0 , 1 , . . . , K ) . h_G=CONCAT(READOUT(\{h_v^{(k)}|v\in G\})|k=0,1,...,K). hG​=CONCAT(READOUT({hv(k)​∣v∈G})∣k=0,1,...,K).

如果GIN在同层的iteration上使用summing来替换READOUT（我们不需要额外的MLP，和（4.1）的道理一致），这样就泛化了WL test以及WL subtree kernel。

5. less powerful but still interesting GNNs

接下来我们讲概述不满足定理3（单射条件）的GNNs，包括GCN,GraphSAGE。我们对于4.1的aggregator的两个层面进行了消融对比：(1)使用单层感知机，而非是MLPs （2）使用mean或者max-pooling来提到sum。我们可以看到这些GNN变体可能难以分清简单的图并且没有WL test有效。尽管如此，使用mean aggregator的模型如GCN，在节点分类任务上表现良好。为了更好地进行理解，我们准确地说明了不同的GNN变体是否能够捕捉一个图并且讨论了利用图来学习的影响。

5.1 1-layer perceptron are not sufficient

lemma 7说明使用1层感知机建模的网络邻居无法进行区分。
lemma 7: 存在有限的multisets $X_1\ne X_2$，对于任意线性映射$W,{\sum }_{x\in X_1}ReLU(Wx)={\sum }_{x\in X_2}ReLU(Wx).$

lemma 7说明了单层的感知机表现得像线性映射，所以这样的GNN层退化为简单的对于节点特征进行加和。我们的证明建立在bias terms在线性映射上是缺失的。如果具有bias term以及充分大的输出维度，单层感知机也许能够辨别不同的multisets。尽管如此，不像使用MLPs的模型，单层感知机（即使具有bias term的），不是对于multiset functions的通用估计。使用单层感知机的GNNs可以在一定程度上将不同的图映射到不同的位置，这些embeddings可能无法捕捉结构相似度以及对于简单分类很困难（如：线性分类）。在section 7中，我们会实验验证具有单层感知机的GNNs，当应用到图分类上去时，很多时候会对训练数据欠拟合以及在训练准确度上比具有MLPs的GNN的表现差。

5.2 structures that confuse mean and max-pooling

如果我们将$h(X)={\sum }_{x\in X}f(x)$替换为和GCN和GraphSAGE一样的mean or max-pooling：mean and max-pooling在multiset functions上仍旧定义良好，因为他们是permutation invariant的。但是它们不是单射的。

上图中不同的颜色代表不同的节点特征，并且我们认为GNNs首先聚合邻居，再将它们与中心节点组合。

如果输入节点特征包括一个代表节点的度的常数，那么mean可以还原sum，但是max-pooling不可以。

图3证明了mean和max无法辨别具有重复特征的节点。

5.3 mean learns distribution

为了描述mean aggregator可以辨别的multisets类，考虑例子：$X1=(S,m),X2=(S,k\cdot m)，$两者具有相同set的不同集合。mean aggregator只是捕捉了在multiset中元素的占比，但是不是实际的multiset。

corollary 8: 假设$\mathcal{X}$为可数的，存在一个函数$f:\mathcal{X}\to {\mathbb{R}}^n$，$h(X)=\frac{1}{|X|}{\sum }_{x\in X}f(x)$,$h(X_1)=h(X_2)$当且仅当$X_1,X_2$具有相同的分布。

mean aggregator在统计分布信息比实际图结构更重要的任务中表现良好。当节点特征是离散的且鲜有重复的时候，mean aggregator比sum aggregator更powerful，这可以解释为什么具有mean aggregator的GNN在节点分类任务上effective，邻居特征的分布为任务提供了strong signal。

5.4 max-pooling learns sets with distinct elements

图3中的例子说明了max-pooling将重复特征的节点考虑为单个节点。max-pooling适合于识别代表性元素或者框架，而不是分辨具体的结构或者分布。

corollary 9: 假设$\mathcal{X}$为可数的,存在一个函数$f:\mathcal{X}\to {\mathbb{R}}^{\infty }$，$h(X)=ma{x}_{x\in X}f(x),h(X_1)=h(X_2)$当且仅当$X_1,X_2$具有相同的underlying set（基础集）。

5.5 remarks on other aggregators

还存在一些其他的非标准的邻居聚合策略：weighted average via attention，LSTM pooling。我们的理论框架对于描述表达能力of任何aggregation-based GNNs都是十足通用的。

7.experiments

GIN-$ϵ$代表了(4.1)中的$ϵ$通过梯度下降进行学习，而GIN-0代表$ϵ$固定为0。GIN-0具有更好的表现：具有更好的泛化性能，在测试准确度上稳定略优于比GIN-$ϵ$。

GIN-$ϵ$和GIN-0都能很好地正常拟合训练数据，$ϵ$的训练对于模型没有额外的提升，GNN with MLP比具有多层感知机的具有更好的训练准确度，GNN with sum aggregator拟合得比mean和max更好。

在我们的实验中，GNNs的训练准确度始终不会优于WL subtree kernel。说明WL test提供了基于aggregation-based GNNs的表达能力的天花板。但是WL kernel 无法学习如何组合节点特征，这对于给定的预测任务却是十分重要的。

通过测试准确度，我们证明了具有强表达能力的GNN能够准确捕捉图结构于是泛化得很好。

说明：文中所有的定理都在附录中进行了证明，感兴趣的可以翻阅论文查看。