图同构神经网络GIN
Published:
论文阅读笔记：How Powerful are Graph Neural Networks?
在 图卷积网络GCN 中我们已经知道图神经网络在结点分类等任务上的作用，但GIN（图同构神经网络）给出了一个对于图嵌入（graph embedding）更强的公式。
GIN，图同构神经网络，致力于解决使用GNN对图进行分类的问题，我们知道采用GCN等GNN可以得到每个结点的嵌入向量表示（node embedding), 如果我们将一张图的所有节点的向量表示拼接起来，便可以得到整张图的向量表示（graph embedding)
WL测试
首先文章说，WL测试是GNN判断图同构的上界，直观来讲，WL测试每次将一个多重集（一个结点的邻居集合）用一个哈希函数做了一个单射，而GNN聚合邻居信息的时候，虽然使用了各种各样的函数，但显然并不是单射，比如常用的$Max(x)Sum(x),Mean(x)$这些函数都不是单射，那么当然不可能有WL测试强了。文中的严谨证明用了反证法，证明了如果WL测试停止时不能判断出两个图是否同构，那么GNN也不能。
GIN公式
文章提出了一种新的图卷积方式，而且证明了该方式可以达到WL测试的上界，
该公式如下：
\[h_{k+1}(u) = MLP((1+\epsilon) h_k(u) + \sum_{(u,v) \in E} h_k(v))\]其中$\epsilon$是一个可学习的无理数参数。
GIN公式推导
下面，我们推导GIN的公式。
定理1.1：多重集的单射函数
首先我们知道，GNN中聚集一个结点的邻居信息，可以定义为一个多重集上的函数，那么要达到WL测试的上界，就要求这个函数是单射（多重集：集合中元素可以重复的集合）。
如果我们假设多重集$X$是可列集，而且集合的元素有限，那么显然存在函数$h$,
\[h(X) = \sum_{x\in X} f(x)\]使得$h$这个单射可以表示为一组单射函数$f$的和，直观来讲，只要开一个$n$ 位数组，$n$为集合元素个数的上界，而每一位的值域也是$n$, 存储每一个元素的出现次数，然后我们以看，这样的数组不就是一个$n$位$n$进制数嘛，那确实它可以写成上面的表示形式，$h(X)$表示这个$n$进制数的数值，而$f(x)$ 表示每一位代表的数值。
定理1.2：Ego-Graph的单射函数
那么这样子，我们就可以区分出每个结点的不同邻居结构了，但我们目的是区分每个结点的结点中心图Ego-Graph, 也就是我们还要考虑这个结点本身，那我们又需要一个单射函数，
\[h(c,X) = (1+\epsilon) f(c) + \sum_{x \in X} f(x)\]其中,$c$表示结点$c$的特征，$X$表示该结点的邻居的特征的集合，$\epsilon$ 为任意的无理数，但$x,c$都为有理数，$f$也为有理函数
我们来证明这样的定义是一个单射，
\[(X,c) \neq (X',c') \Rightarrow h(c,X) \neq h(c',X')\]若$X=X’ \ or \ c=c’$ 显然，由$f$为单射，左式一定可以推出右式，
我们只需考虑最难的情况，也即,$X \neq X’ , c \neq c’$ ,
用反证法，假设$h(c,X) = h(c’,X’)$,
\[\epsilon (f(c)- f(c') = f(c) -f(c') + \sum f(x) - \sum f(x')\]由于左端为无理数，右端为有理数，显然矛盾，故得证，
定理1.3：可学习的单射函数GIN
基于上面的性质，只需要在上面的公式中加入可学习参数就可以推出GIN的最终公式。
那再定义一个单射函数$\phi$ ,单射函数嵌套单射函数显然也是单射的嘛，
\[h(c,X) = \phi((1+\epsilon) f(c) + \sum_{x \in X} f(x))\]利用MLP强大的拟合能力学习$\phi$函数和$f$函数，并且令$MLP = f^{(l)} \circ \phi^{(l-1)}$，可以得到GIN最终的公式
\[h_{k+1}(u) = MLP((1+\epsilon) h_k(u) + \sum_{(u,v) \in E} h_k(v))\]