图神经网络

前面讲了图机器学习的一些传统方法，现在正式进入到课程的核心部分：图神经网络。

Design of GNN

那么图神经网络和我们之前接触的一些深度神经网络有什么不同呢？

对于别的类型的神经网络，往往我们都是处理一些类似网格的或者序列信号，但是这些方法往往不能直接运用到图数据中。一个原因是在图数据中不同的节点往往没有固定顺序，拓扑结构非常复杂，并且不同图的大小往往不一样（比如做分子结构毒性预测，不同的分子很可能含有的原子数目不一样）。另一个原因是图数据很可能具有多模态的信息，甚至可能出现异质的节点。

一个处理图数据最简单的想法是将描述图结构的邻接矩阵和节点的特征整合成一个新的矩阵，并且将这个矩阵放到传统的神经网络中作为输入。

这个方法的问题在于神经网络输入层的大小和节点的数量呈O(|V|)的关系，对于不同大小的图没法处理，并且对于节点在邻接矩阵中的位置很敏感。

对于graph representation我们需要保证permutation invariance的性质，即对于同一个图不同的order plan经过一个函数f过后的值需要是相同的。

对于node representation我们需要保证permutation equivariance的性质。

对于同一个图的相同位置的节点，经过函数f映射过后需要拥有相同的值。

图神经网络里面包含了多个permutation equivariant/invariant的函数。

图神经网络的一个key idea就是通过聚合节点的local network的邻居的信息来生成node embedding。

每一个计算图的深度可以是任意的，

对于layer0的embedding就是当前节点的feature，其它layer的则是结合了节点本身信息和它从k hop邻居节点收集到的信息。

一个比较经典的想法如上所示。个人比较疑惑的点在于$h_v^{(k)}$是怎么求出来的，按照计算图来看，单个的计算图中假设第（k+1）layer中有节点v那么第k个layer中必然没有节点v。目前我倾向于认为由于有多个计算图的存在，每个计算图中对于相同节点的embedding都是相同的，所以即使某一个计算图中没有某个embedding也没有关系。

在实际的操作的过程中，很多aggregation的操作很多时候能够使用（稀疏）矩阵运算给高效的执行。

对于图神经网络有一个很重要的点是它的inductive capability，在我们训练的过程中不同的计算图中模型的参数是共享的。此时模型的参数是sublinear in |V|，并且可以泛化到没有见过的节点。

还有一个比较有意思的点是在课件中提到transformer可以被视作一种特殊的GNN，具体可以参考

Transformers are Graph Neural Networks | by Chaitanya K. Joshi | Towards Data Science

一层GNN主要做了两件事情，第一件是收集邻居节点的信息，第二件事情是将这些信息和自己本身的信息做aggregation。

Classical GNN Layers

Graph Convolutional Networks (GCN)

将GCN layer写成message+aggregation的形式

我们可以得到GCN的aggregation其实是做了一个sum的操作,而message的部分则是做了一个 normalization。

GraphSAGE

这个是做了一个两阶段的aggregation，先是从邻居节点进行聚合，然后是将聚合的产物和上一层的本节点的embedding拼接然后再进行聚合。公式里面的AGG有多种方式，比如常见的取mean，取max等等，甚至还可以接一个LSTM。在GraphSAGE中还可能会使用l2 normalization。

Graph Attention Network

在前面介绍的GCN和GraphSAGE中对于邻居节点都赋予了相同的重要性，在GAT中我们使用注意力机制，使得能够给不同的邻居节点分配不同的权重。

假设我们有两个不同的节点u，v。我们可以使用下面的式子来计算u的消息对于v的重要程度$e_{vu}$(注意：$e_{vu}$和$e_{uv}$是不同的)。

这个最终注意力的计算需要再经过一个softmax操作。

我们也可以有multi-head attention，最终再整合多个attention head的结果。

Others

在GNN中假如神经网络的层数过多很可能会出现over smoothing的情况。不同的节点可能最终embedding的结果非常相似导致效果不好。这是由于增大层数之后GNN的receptive field变大导致不同的节点的field高度重叠，增大了区分的难度。

假如我们真的需要很多层的GNN我们可以参考Resnet，创造一些shortcut来延缓over smoothing的副作用。

使GNN的表达能力变强的方法：

（1）让aggregation操作都使用神经网络来刻画。

（2）在GNN layer前面或者后面增加别的layer