Expressive Power of GNNs

消息传递型图神经网络

图神经网络（GNNs），究其本质，是一种特殊的映射$f$，它将顶点的特征及其图的结构映射为一个包含了图连接信息的向量，这一个过程称为Node Embedding，事实上是一个编码的过程。将图的连接信息和顶点特征一起映射为一个向量，这内在地存在一个消息传递（Message Passing）的过程，因为对于某个中心顶点来说，图的连接信息主要体现为其邻接顶点，要想在中心顶点中包含图的连接信息，就要将其邻接顶点的信息传递到中心顶点去：

$$
\begin{align*}
a _{v} ^{(k)}&=\text{AGGREGATE} ^{(k)}(\left\{h _u ^{k-1}:u\in\mathcal{N}(v)\right\})\tag{1}\\
h _{v} ^{(k)}&=\text{COMBINE} ^{(k)}(h _v ^{(k-1)},a _n ^{(k)})\tag{2}
\end{align*}
$$

式$(1)$表示中心顶点$v$的邻接顶点集$\mathcal{N}(v)$对中心顶点的第$k$次消息传递，式$(2)$则是中心顶点$v$由自己之前的特征$h _v ^{(k-1)}$和邻接顶点的新消息$a _v ^{(k)}$产生感受野更大的新特征。

图神经网络的表达能力

对于某个中心顶点$v$，$k$次的消息传递可以生成一个距离中心顶点最远距离为$k$-hop的子图，这个子图也可以被表示成一个高度为$k+1$的根子树（或称计算图）：

Fig. 1. Rooted subtree (k=2)

要想使得图神经网络的Node Embedding能够充分体现出中心顶点与全图的关系，并且与其他顶点相互区别，根子树到Embedding的映射就应该是唯一的，因此可以把图神经网络的表达能力定义为：

$$
\begin{align*}
\text{GNN的表达能力}&=\text{不同计算图学到不同Embedding的能力}\\
&=\text{区分根结点Embedding的能力}\\
&=\text{区分不同图结构的能力}
\end{align*}
$$

最理想的情况是对于不同的计算图，其Embedding也不相同。要想达到这样的效果：

1. $\text{AGGREGATE}$是单射函数；

2. $\text{COMBINE}$是单射函数；

3. 若要对整个图进行分析，还需要额外的$\text{READOUT}$操作生成图的全局信息：

   $$
   h _G=\text{READOUT}(\left\{h _v ^{(K)}|v\in G\right\})
   $$
   此时，$\text{READOUT}$也必须是单射函数。

Weisfeiler-Lehman test

Weisfeiler-Lehman test（WL test）是所有消息传递型图神经网络的“祖宗”，其能力也是消息传递型图神经网络能力的上限，它的消息传递满足上面的三点要求。

WL test假设所有顶点都是无特征的，它初始时为所有顶点都分配了相同的颜色1：

Fig. 2. Assign initial colors

之后，通过消息传递，邻接顶点的颜色汇聚到中心顶点：

Fig. 3. Aggregate neighboring colors

再经由哈希映射（所有图共用一个哈希表），将顶点映射为新的颜色：

Fig. 4. Combine and hash aggregated colors

不断重复Fig 3和Fig 4的操作$k$次：

Fig. 5. Next round

最后，执行$\text{READOUT}$操作。WL test定义$\text{READOUT}$操作为：将整个过程中，每张图所出现的所有颜色的次数作为该图的Embedding（没出现的记为0）：

Fig. 6. Readout

并定义：

$$
\phi(G_1) ^T\phi(G_2)
$$

为两张图的相似度（实际计算时两个向量都要归一化后再点乘）。

GIN

作者在文章的后半部分提出了全新的消息传递型图神经网络Graph Isomorphism Network（GIN）。作者认为，GIN是对WL test的最优近似，因为WL test可以写为：

$$
c _{v} ^{(k)}=\text{HASH} ^{(k)}(c _v ^{(k-1)},\left\{c _u ^{k-1}:u\in\mathcal{N}(v)\right\})
$$

其中，$c _v ^{(k)}$表示顶点$v$在第$k$次消息传递后的color，而作者将GIN定义为：

$$
h _{v} ^{(k)}=\text{MLP} ^{(k)}((1+\epsilon ^{(k)})h _v ^{(k-1)}+\sum _{u\in \mathcal{N}(v)}h _u ^{k-1})
$$

其中$\text{MLP}$和$\epsilon$均是可学习的参数。作者如此定义GIN是基于两个方面的考虑：

1. Sum-pooling具有很强的单射能力
   相比于GCN用的mean-pooling和GraphSAGE用的max-pooling，sum-pooling具有更强的区分不同图结构的能力。如下图Fig 7所示的两张图，在这两张图中，所有顶点的特征都相同。虽然它们很明显是两张完全不同的图，但是如果用mean-pooling或者max-pooling，中心顶点$v$和$v'$最终的Embedding将完全相同，因而无法区分出这两张图，而对于sum-pooling，则不会出现这种情况。
   

   Fig. 7. Mean and Max both fail

2. Universal approximation theorem
   根据Hornik等提出的Universal approximation theorem，只要参数足够多，一层MLP可以拟合任何的函数。因此，GIN中的MLP是作者用于拟合ML test中的哈希函数的。

   GIN将$\text{READOUT}$也定义为sum，但不同的是，作者将$0-K$的$\text{READOUT}$都拼接了起来以求保留可能在中间过程中出现的更能体现图整体特点的信息：
   $$
   h _G=\text{CONCAT}(\text{READOUT}(\left\{h _v ^{(k)}|v\in G\right\})|k=0,1,...,K)
   $$

参考

• How Powerful are Graph Neural Networks?
• 传统图机器学习的特征工程-全图【斯坦福CS224W】
• 图神经网络GNN的表达能力