How Powerful are Graph Neural Networks?[ICLR'19]

ICLR19一篇从图同构测试(Graph Isomorphism Test)角度说明GNN性能表现的论文

解决的问题

GNN性能表现好的原因是什么?

贡献:

  1. 证明了GNN的性能上限是Weisfeiler-Lehman (WL) test,最多只和它一样有效
  2. 给出了GNN在什么条件下能够和WL test一样有效
  3. 指明了主流GNN框架如GCN、GraphSage无法区分的图结构,以及它们能够区分的图结构的特点
  4. 提出了一个简单有效的框架GIN,能够与WL test一样有效

做法及创新

首先是介绍现有GNN框架的做法及图同构测试的定义,还有WL test的做法。

GNN与WL test

论文认为主流的GNN框架可以分为下面这三步:

  1. Aggregate:聚合邻域内的信息

  2. Combine:将聚合后的邻域信息与当前顶点信息结合

  3. Readout:通过图中的每个顶点的表示得到图的表示

图同构测试就是判断两张图是否在拓扑结构上相同。而WL test的做法是迭代地进行以下步骤:

  • 聚合顶点及其邻域的标签信息
  • 将聚合后的标签集合哈希成唯一的新标签

如果经过若干次迭代后,两张图中的顶点的标签出现了不同则判断为不同构。基于WL test有一种核函数被提出以计算图之间的相似性。直观上来说,如下图所示,一个顶点在第$k$次迭代时的标签,实际表示了一颗以该顶点为根顶点高度为$k$的子树。

yVPBNQ.png

而GNN同样是通过迭代地更新图中每个顶点的特征向量来捕捉图的结构信息以其周围顶点的特征,这里的结构特征同样可以是上图的根子树rooted subtree。如果给每个顶点的特征向量一个唯一的标签例如{a,b,c,…},那一个顶点的邻域中所有顶点的特征向量可以构成一个Multiset,它的定义基本和C++中的Multiset一样,是一个Set的同时里面的元素还可以重复例如{a,a,b,c}。论文中对Multiset给出的数学定义是:$X=(S,m)$,其中$S$由Multiset中的非重复元素构成,$m$表示$S$中的元素在$X$中的频数。

直观上来说,一个有效的GNN应该只有在两个顶点对应的根子树结构相同,且其中对应顶点的特征向量也相同时,才将这两个顶点在特征空间中映射成相同的表示。也就是永远不会将不同的两个Multiset映射成同一个特征表示(因为Multiset中的顶点也是根子树中的顶点,既然它们都是通过聚合邻域得到的)。这也就意味着GNN中使用的聚合函数必须是单射的,对值域内的每一个$y$,存在最多一个定义域内的$x$使得$f(x)=y$。有下面这么一个引理:

设$G_1$和$G_2$是两个非同构图,如果一个图神经网络$A:G\rightarrow \mathbb{R}^d$将$G_1$和$G_2$映射成不同的embedding,那么WL test同样会判断这两个图为非同构。

引理表明在图区分任务上,一个图神经网络的表现最多和WL test一样好。而一样好的条件是,这个图神经网络的邻居聚合函数和图表示函数都是单射的。这里的一个局限是,函数考虑的定义域和值域都是离散集合。

图神经网络相较于WL test的另一个好处是,WL test输入的顶点特征向量都是one-hot编码,这无法捕捉到子树之间的结构相似度:

Note that node feature vectors in the WL test are essentially one-hot encodings and thus cannot capture the similarity between subtrees. In contrast, a GNN satisfying the criteria in Theorem 3 generalizes the WL test by learning to embed the subtrees to low-dimensional space. This enables GNNs to not only discriminate different structures, but also to learn to map similar graph structures to similar embeddings and capture dependencies between graph structures.

图同构网络GIN

基于上面介绍的引理和结论,论文提出的GIN框架如下:

对比一开始论文给出的GNN主流框架,可以看到是Aggregate函数选取了求和函数,Combine函数选取了MLP+(1+$\epsilon$)的形式。常见的Aggregate函数包括求和Sum、最大值Max和平均值Mean,论文花了一部分篇幅来说明求和相较于其他两个函数的好处:

yGIv5D.png yGoirt.png

上面两幅图分别说明这几种聚合函数的特点及何种场景下会导致误差。第一幅图中即使减少了顶点的数量但对于取平均和最大值函数来说得到的信息保持不变,第二幅图也是想说明同样的问题,例如取平均,两个一样的顶点与三个一样的顶点取平均出来结构都是一样的,但它们分别对应的局部结构是不相同的。

对于顶点分类及边预测这类下游任务,只要得到顶点的embedding即可。而对于图分类任务,还需要根据所有顶点的embedding来得到图的一个表示,也就是前面提到的主流GNN框架做法的第三步Readout函数。论文的做法类似于JK-Net,将所有层的表示都考虑进来,不过没有具体说是怎么做的。

最后,论文还探讨了那些不满足上面定理的GNN框架如GCN、GraphSAGE等,这些框架都采用一层感知机如ReLU来将Multiset映射成特征表示,而不像论文的做法采用多层感知机,而ReLU存在将不同的Multiset表示成同一种特征表示的情况,即$\exist X_1 \not=X_2,\ s.t. \ \sum_{x\in X_1}\text{ReLU}(Wx)=\sum_{x\in X_2}\text{ReLU}(Wx)$。论文中直接给了一个简单的例子:$X_1=\{1,1,1,1,1\},X_2=\{2,3\}$,因为有$\sum_{x\in X_1}\text{ReLU}(Wx)=\text{ReLU}(W\sum_{x\in X_1}x)$。

数据集

MUTAG、PTC、NCI1、PROTEINS、COLLAB、IMDB-BINARY、IMDB-MULTI、REDDIT-BINARY、REDDIT-MULTI5K