前言

类似于图像上传统的卷积运算，基于空间的方法根据节点的空间关系定义图卷积。图像可以看作是一种特殊的图形式，每个像素代表一个节点。每个像素都直接连接到它附近的像素，如下图左所示。对3*3的区域应用一个过滤器，通过对每个通道的中心节点及其相邻节点的像素值进行加权平均。类似的，基于空间的图卷积将中心节点的表示与其邻居的表示进行卷积，得到中心节点的更新表示，如下图右。从另一个角度来看，基于空间的ConvGNNs与RecGNNs共享相同的信息传播/消息传递思想。空间图卷积运算实质上是沿着边传播节点信息。

本篇主要涉及三个有代表性的空间图卷积工作：PATCHY-SAN、graphSAGE、GAT。

PATCHY-SAN (Learning Convolutional Neural Networks for Graphs, ICML2016)

**该工作提出了一个框架PATCHY-SAN (Select-Assemble-Normalize)，可以从任意图中学习卷积神经网络。**这些图可能是无向的、有向的，可以同时有离散和连续的节点和边属性。

0. From CNN

该方法基于卷积神经网络(CNNs)的概念，并将其扩展到任意图。下图说明了图像的CNN局部连接的接受域（receptive field）。 图像可以表示为正方形网格图，其节点表示像素。 现在，可以将CNN视为遍历节点序列（节点1-4）并为每个节点生成固定大小的邻域图（3x3网格）。 邻域图用作从像素节点读取特征值的接受域。但是，对于许多图，缺少特定于问题的排序（空间，时间或其他），并且图的节点也不对应。 在这些情况下，必须解决两个问题：

1. 确定要为其创建的邻域图的节点序列
2. 计算邻域图的范数，即从图表示到向量空间表示的唯一映射。
   该工作所提出的方法称为PATCHY-SAN，解决了任意图的这两个问题。对于每个输入图，它首先确定创建邻域图的节点(及其顺序)。 对于每个节点，提取并归一化由k个节点组成的邻域，也就是说，它以固定的线性顺序唯一地映射到空间。最后，归一化的邻域图作为接收域与CNN组件相结合。
   
   上述文字描述的就是该工作方法的主要流程，按步骤划分为节点序列选取（node sequence selection）、邻域集合（neighborhood assembly）、邻域归一化（nneighborhood normalization），最后送入**卷积结构（convolutional architecture）**进行特征提取。下图描述了前三步的过程，下文将按照每一步的算法逐一介绍。

1. Node Sequence Selection

（节点序列选取：在每个输入图中选取$w$个将为其创建接收域的节点。）其中$w$是接受域的个数，也是卷积操作的个数，在示例中$w=6$。
在算法1中：

1. 将输入图的节点按照graph labeling算法给定的顺序进行排序。
2. 使用给定的步幅$s$遍历所得的节点序列，选取出前$w$个被访问的节点。
3. 对于每个访问的节点，执行算法3构造一个接收域，直到创建了$w$个接收域。如果节点数少于$w$，则该算法将创建全零接受域以用于填充。
   

2. Neighborhood Assembly

（邻域集合：为$w$中的每个节点构建数量为$k$的邻域区域。）
对于节点序列选取中的第3步——为标识的每个节点构造一个接受域， 算法3首先调用算法2来为节点组合一个本地邻域，邻域的节点是接受域的候选。
算法2列出了邻域集合步骤：对于$w$中每个节点$v$进行广度优先搜索BFS，探索节点$v$的一阶邻域，并将这些节点添加到集合N中。如果收集到的节点数少于$k$，则继续探索二阶邻域，以此类推直到N中有至少$k$个节点，或者直到没有更多的邻域可供添加。注意，此时$k$和$N$的大小可能不同。在示例中$k=4$，即保留每个节点的4个邻域节点作为邻域区域。

3. Neighborhood Normalization

（邻域归一化：从邻域区域中选择接受域的节点，并确定接受域中节点的顺序。）
节点的接受域是通过规范化上一步中的邻域区域而构建的，归一化在邻域图的节点上施加了一个顺序，以便从无序图空间映射到具有线性顺序的向量空间。基本的思想是利用图标记程序，对于两个不同的图， 来自这两个图的子结构$g1$和$g2$，它们在各自的图中有相似的结构，那么他们的标签应该相似。为了使这个直观形式化，定义了最优图正规化问题，其目的是寻找相对于给定图集的最优标记。
在具体的算法4中：根据到节点$v$的距离来计算每个邻域节点的排序，而为了使每个节点的标签唯一，采用NAUTY(McKay&Piperno, 2014)算法分别对$w$个邻域区域进行标记。若节点数大于$k$则按排序截取前$k$个，不足$k$则用虚拟节点（dummy nodes）补充。

4. Convolutional Architecture

PATCHY-SAN能够处理节点和边属性（离散和连续）。设节点特征的个数为$a_v$，边特征的个数为$a_e$。 对于每个输入图G，它将节点和边的归一化接受域分别表达为张量$(w,k,a_v)$和张量$(w,k,k,a_e)$，$a_v$和$a_e$相当于输入通道的个数（代表不同特征）。 该架构的其余部分和传统CNN相同，可以任意选择。

文中举例的一个完整网络结构如下，共有两层卷积+一层池化：

总结

该工作基于图结构实现了卷及操作，原理是通过节点选取、邻域构造和归一化将图结构逐步转化为接受域（receptive field）序列，然后采用CNN进行特征提取。

GraphSAGE (Inductive Representation Learning on Large Graphs, NIPS2017)

ICLR2017的论文——Semi-Supervised Classification with Graph Convolutional Networks从谱域的角度定义了GCN，也成为图卷积网络入门必读的paper。
但是，其所代表的GCN有一个关键的局限——直推式学习（Transductive Learning）：要求在一个确定的图中学习顶点的嵌入，即把所有节点都参与到训练，而无法直接泛化到在训练过程没有出现过的节点。如果要适应新的节点则需要重新训练所有节点，非常麻烦。
GraphSAGE则提出一种新思路：我们不必一定要得到每个节点的一个固定的表示，我们可以直接学习一种节点的表示方法，不管图怎么改变，都可以很容易地得到新的表示。这里运用到的思想类似元学习（Meta Learning），“授人以鱼不如授人以渔”。
GraphSAGE是一种能够利用节点的属性信息高效产生未知节点嵌入的一种归纳式学习(Inductive Learning)的框架，其核心思想是通过学习一个对邻域节点进行聚合表示的函数来生成目标节点的嵌入。

1. Embedding generation

GraphSAGE = Graph SAmple and aggreGatE，即图的采样和聚合，具体过程如下图所示：

1. 对节点的邻居进行采样
2. 聚合所采样邻居的特征信息
3. 根据聚合的信息生成嵌入，预测图内容或标签

将该过程表述成算法如下：

外层循环的K代表着网络层数，也就是中心节点所能聚合到的邻居阶数，同时也代表着聚合次数，也是聚合函数个数。
文中通过实验测试出：当$K=2$时（中心节点最多可以将其二阶邻域的节点信息聚合到自己的嵌入表示中），当一阶邻域数与二阶邻域数的乘积$S1\ast S2<500$时，模型就可以达到很好的效果。
在内层循环中，对每个节点$v$，首先使用$v$的邻居节点的$k-1$层的嵌入表示$h_u^{k-1}$来通过聚合函数生成$v$的邻居节点的$k$层表示$h_{N(v)}^k$ 。之后将$h_{N(v)}^k$和节点$v$的第$k-1$层的嵌入表示$h_v^{k-1}$进行拼接，经过一个非线性变换$W^k$产生节点$v$的第$k$层的嵌入表示$h_v^k$。

2. Aggregator Architectures

由于在图中节点的邻居是天然无序的，所以希望构造出的聚合函数是对称的（inherently symmetric），即改变输入的顺序，函数的输出结果不变。

Mean aggregator

Mean aggregator类似于GCN框架中使用的卷积传播规则。将嵌入生成算法的4、5行替换为下式来得出该方法的归纳变量，直接产生目标节点的向量表示，而不是邻居节点的向量表示。Mean aggregator将目标节点和邻居节点的第$k-1$层嵌入拼接起来，然后对其每个维度进行求均值，再将得到的结果做一次非线性变换$W$，生成目标节点的第$k$层嵌入表示。

LSTM aggregator

引入循环神经网络LSTM来encode邻居的特征，有更强的表示能力。由于LSTM不是对称（inherently symmetric）的，所以在使用时需要对目标节点的邻居进行随机打乱，再输入到LSTM中。

Pooling aggregator

先对目标节点的每个邻居节点的嵌入表示独立进行非线性变换（MLP）$W_{pool}$得到向量，之后把所有邻居节点的向量做一次池化操作(max pooling / mean pooling)进行聚合，该工作中采用了max pooling。

3. Learning the parameters

以上是GraphSAGE的前向传播过程，下面简单介绍训练过程。
为了在完全无监督的情况下学习有用的预测表示，该工作基于图的输出表示$z_u$的损失函数进行参数学习——权重矩阵$W_k$和聚合函数的参数。 基于图的损失函数，希望相近的节点具有相似的表示，分离节点有不同的表示：

其中$v$是在定长随机游走中出现在$u$附近的节点，$\sigma$是sigmoid函数，$P_n$是负采样分布，$Q$是负样本数量。
不同于以前的嵌入方法，$z_u$是由一个节点的局部邻域所包含的特征生成的，而不是为每个节点训练唯一的嵌入。

4. 实验

最终的实验结果表明，在GraphSAGE中LSTM和pooling聚合的方法效果最好。

5. 思考

GraphSAGE有必要和GCN相比较进行思考：

1. 本质上来说，GCN（归一化邻接矩阵后乘以特征矩阵）也是一种均值聚合的过程。而两者的区别在于，GCN中的邻接矩阵是固定的，并且只支持整张图一起训练，这就导致了它对于新节点/新边的动态适应力不足。
2. 本质上来说，GraphSAGE的归纳式学习在于聚合函数中包含了对于邻居节点的聚合，即多了采样的过程，该过程中邻接矩阵是不断变化的，相当于从GCN中的固定参数变成了输入变量。
3. 训练过程中的minibatch方法同理，每次提取的子图中同一个节点的邻接矩阵也很可能不同。

所以，相比于GCN，GraphSAGE的改进在于可以灵活地动态进行分批训练和采样。

GAT (Graph Attention Networks, ICLR2018)

该工作提出了图注意力网络（GAT）——在图结构化数据上运行的新型神经网络体系结构，利用masked self-attention层来解决基于图卷积或其类似的方法的缺点。 通过堆叠节点能够参与其邻域特征的层，为邻域中的不同节点指定了不同的权重，而无需进行任何昂贵的矩阵运算（如求逆）或依赖于已知的图。通过这种方式，可以同时解决基于频谱的图神经网络的几个关键挑战，并使该模型在归纳学习（inductive learning）上和传导学习（transductive learning）上一样易用。
（除了原文，以下内容主要参考了两篇知乎文章：向往的GAT、Graph Attention Networks阅读笔记）

0. 概念

传导学习（Transductive Learning）：即前文提到的直推式学习，先观察特定的训练样本，然后对特定的测试样本做出预测。训练阶段与测试阶段都基于同样的图结构。
归纳学习（Inductive Learning）：先从训练样本中学习到一定的模式，然后利用其对测试样本进行预测。训练阶段与测试阶段需要处理的图不同，通常是训练阶段只是在子图（subgraph）上进行，测试阶段需要处理未知的节点。

全局图注意力（global graph attention）：顾名思义，就是每一个节点都对于图上任意顶点都进行attention运算。这样的优点是完全不依赖于图的结构，对于inductive任务无压力；缺点是丢掉了图结构的特征、运算面临着高昂的成本。
局部图注意力（masked graph attention）：注意力机制的运算只在一阶邻居节点上进行，该工作中采用了这种方式。

1. 计算图注意力系数（attention coefficient）

graph attention layer对于节点$i$，逐个计算它的邻居们和它自己之间的相似系数：
$$e_{ij}=a([W{h}_i\parallel W{h}_j]),j\in N_i$$其中，首先一个共享参数$W$的线性映射对于节点的特征进行了增维，这是一种常见的特征增强（feature augment）方法；$[\cdot \parallel \cdot ]$对于节点$i,j$的变换后的特征进行了拼接（concatenate）；最后$a(\cdot )$把拼接后的高维特征映射到一个实数上，作者是通过 single-layer feedforward neural network实现的。
接下来基于相关系数进行归一化：
$${\alpha }_{ij}=\frac{\exp (LeakyReLU(e_{ij}))}{{\sum }_{k\in N_i}\exp (LeakyReLU(e_{ij}))}$$至此注意力系数${\alpha }_{ij}$求解完毕，过程如下图（左）所示：

2. 聚合（aggregate）

如同GraphSAGE一样，基于空间的图卷积网络绕不开聚合。在这里，聚合就是根据计算好的注意力系数${\alpha }_{ij}$，把特征$h_j$加权求和：
$$h_i^{\prime }=\sigma (\sum _{j\in N_i}{\alpha }_{ij}W{h}_j)$$其中，$h_i^{\prime }$就是GAT输出的对于每个节点$i$的新特征（融合了邻域信息），$\sigma (\cdot )$是激活函数。
为了提高模型的拟合能力，在本文中还引入了multi-head attention，即同时使用多个$W^k$计算注意力，然后将各个$W^k$计算得到的结果合并（连接）：
$$h_i^{\prime }(K)={\parallel }_{k=1}^K\sigma (\sum _{j\in N_i}{\alpha }_{ij}^k{W}^k{h}_j)$$其中，$\parallel$表示连接，${\alpha }_{ij}^k$和$W^k$表示第$k$个multi-head得到的计算结果。类似的，也可以用求和的方式进行合并：
$$h_i^{\prime }(K)=\sigma (\frac{1}{K}\sum _{k=1}^K\sum _{j\in N_i}{\alpha }_{ij}^k{W}^k{h}_j)$$聚合过程如上图（右）所示。

3. 理解

• GCN与GAT都是将邻居顶点的特征聚合到中心节点上（一种aggregate运算），利用graph上的local stationary学习新的节点特征表达。不同的是GCN利用了拉普拉斯矩阵，GAT利用attention系数。GAT会更强，因为节点特征之间的相关性被更好地融入到模型中。
• GAT的运算方式是逐节点的运算（node-wise），每一次运算都需要循环遍历图上的所有顶点来完成。逐节点运算意味着，摆脱了拉普利矩阵的束缚，使得有向图问题迎刃而解。
• 为什么GAT适用于归纳学习？GAT中重要的学习参数是$W$与$a(\cdot )$，因为上述的逐节点运算方式，这两个参数仅与节点特征相关，与图的结构毫无关系。所以测试任务中改变图的结构，对于GAT影响并不大，只需要改变邻居$N_i$，重新计算即可。与此相反的是，GCN是一种全图的计算方式，一次计算就更新全图的节点特征。学习的参数很大程度与图结构相关，这使得GCN在inductive任务上遇到困境。
• 一句话概括：GAT就是将注意力机制attention应用在了基于空间的图卷积网络上。