从图(Graph)到图卷积(Graph Convolution): 漫谈图神经网络 (二)
作者: SivilTaram
编辑: Houye
在从图(Graph)到图卷积(Graph Convolution): 漫谈图神经网络 (一)中，我们简单介绍了基于循环图神经网络的两种重要模型，在本篇中，我们将着大量笔墨介绍图卷积神经网络中的卷积操作。接下来，我们将首先介绍一下图卷积神经网络的大概框架，借此说明它与基于循环的图神经网络的区别。接着，我们将从头开始为读者介绍卷积的基本概念，以及其在物理模型中的涵义。最后，我们将详细地介绍两种不同的卷积操作，分别为空域卷积和时域卷积，与其对应的经典模型。读者不需有任何信号处理方面的基础，傅里叶变换等概念都会在本文中详细介绍。
图卷积缘起
在开始正式介绍图卷积之前，我们先花一点篇幅探讨一个问题：为什么研究者们要设计图卷积操作，传统的卷积不能直接用在图上吗？ 要理解这个问题，我们首先要理解能够应用传统卷积的图像(欧式空间)与图(非欧空间)的区别。如果把图像中的每个像素点视作一个结点，如下图左侧所示，一张图片就可以看作一个非常稠密的图；下图右侧则是一个普通的图。阴影部分代表卷积核，左侧是一个传统的卷积核，右侧则是一个图卷积核。卷积代表的含义我们会在后文详细叙述，这里读者可以将其理解为在局部范围内的特征抽取方法。
GGNN语义解析实例
仔细观察两个图的结构，我们可以发现它们之间有2点非常不一样：
- 在图像为代表的欧式空间中，结点的邻居数量都是固定的。比如说绿色结点的邻居始终是8个(边缘上的点可以做Padding填充)。但在图这种非欧空间中，结点有多少邻居并不固定。目前绿色结点的邻居结点有2个，但其他结点也会有5个邻居的情况。
- 欧式空间中的卷积操作实际上是用固定大小可学习的卷积核来抽取像素的特征，比如这里就是抽取绿色结点对应像素及其相邻像素点的特征。但是因为图里的邻居结点不固定，所以传统的卷积核不能直接用于抽取图上结点的特征。
真正的难点聚焦于邻居结点数量不固定上。那么，研究者如何解决这个问题呢？其实说来也很简单，目前主流的研究从2条路来解决这件事：
- 提出一种方式把非欧空间的图转换成欧式空间。
- 找出一种可处理变长邻居结点的卷积核在图上抽取特征。
这两条实际上也是后续图卷积神经网络的设计原则，图卷积的本质是想找到适用于图的可学习卷积核。
图卷积框架(Framework)
上面说了图卷积的核心特征，下面我们先来一窥图卷积神经网络的全貌。如下图所示，输入的是整张图，在Convolution Layer 1里，对每个结点的邻居都进行一次卷积操作，并用卷积的结果更新该结点；然后经过激活函数如ReLU，然后再过一层卷积层Convolution Layer 2与一词激活函数；反复上述过程，直到层数达到预期深度。与GNN类似，图卷积神经网络也有一个局部输出函数，用于将结点的状态(包括隐藏状态与结点特征)转换成任务相关的标签，比如水军账号分类，本文中笔者称这种任务为Node-Level的任务；也有一些任务是对整张图进行分类的，比如化合物分类，本文中笔者称这种任务为Graph-Level的任务。卷积操作关心每个结点的隐藏状态如何更新，而对于Graph-Level的任务，它们会在卷积层后加入更多操作。本篇博客主要关心如何在图上做卷积，至于如何从结点信息得到整张图的表示，我们将在下一篇系列博客中讲述。
图卷积神经网络全貌
多说一句，GCN与GNN乍看好像还挺像的。为了不让读者误解，在这里我们澄清一下它们根本上的不同：GCN是多层堆叠，比如上图中的Layer 1和Layer 2的参数是不同的；GNN是迭代求解，可以看作每一层Layer参数是共享的。
卷积(Convolution)
正如我们在上篇博客的开头说到的，图卷积神经网络主要有两类，一类是基于空域的，另一类则是基于频域的。通俗点解释，空域可以类比到直接在图片的像素点上进行卷积，而频域可以类比到对图片进行傅里叶变换后，再进行卷积。傅里叶变换的概念我们先按下不讲，我们先对两类方法的代表模型做个大概介绍。
基于空域卷积的方法直接将卷积操作定义在每个结点的连接关系上，它跟传统的卷积神经网络中的卷积更相似一些。在这个类别中比较有代表性的方法有 Message Passing Neural Networks(MPNN)[1], GraphSage[2], Diffusion Convolution Neural Networks(DCNN)[3], PATCHY-SAN[4]等。
基于频域卷积的方法则从图信号处理起家，包括 Spectral CNN[5], Cheybyshev Spectral CNN(ChebNet)[6], 和 First order of ChebNet(1stChebNet)[7]等。
在介绍这些具体的模型前，先让我们从不同的角度来回顾一下卷积的概念，重新思考一下卷积的本质。
深度学习中的卷积
空域卷积(Spatial Convolution)
介绍完卷积的基础概念后，我们先来介绍下空域卷积(Spatial Convolution)。从设计理念上看，空域卷积与深度学习中的卷积的应用方式类似，其核心在于聚合邻居结点的信息。比如说，一种最简单的无参卷积方式可以是：将所有直连邻居结点的隐藏状态加和，来更新当前结点的隐藏状态。
最简单的空域卷积
这里非参式的卷积只是为了举一个简单易懂的例子，实际上图卷积在建模时需要的都是带参数、可学习的卷积核。
MPNN网络模型
图采样与聚合(Graph Sample and Aggregate)
MPNN很好地概括了空域卷积的过程，但定义在这个框架下的所有模型都有一个共同的缺陷：卷积操作针对的对象是整张图，也就意味着要将所有结点放入内存/显存中，才能进行卷积操作。但对实际场景中的大规模图而言，整个图上的卷积操作并不现实。GraphSage[2]提出的动机之一就是解决这个问题。从该方法的名字我们也能看出，区别于传统的全图卷积，GraphSage利用采样(Sample)部分结点的方式进行学习。当然，即使不需要整张图同时卷积，GraphSage仍然需要聚合邻居结点的信息，即论文中定义的aggregate的操作。这种操作类似于MPNN中的消息传递过程。
GraphSage采样过程
图结构序列化(PATCHY-SAN)
我们之前曾提到卷积神经网络不能应用在图结构上是因为图是非欧式空间，所以大部分算法都沿着找到适用于图的卷积核这个思路来走。而 PATCHY-SAN 算法 [4] 另辟蹊径，它将图结构转换成了序列结构，然后直接利用卷积神经网络在转化成的序列结构上做卷积。由于 PATCHY-SAN在其论文中主要用于图的分类任务，我们下面的计算过程也主要针对图分类问题(例如，判断某个社群的职业)。
那么，图结构转换成序列结构最主要的挑战在何处呢，如果简单的话，为什么以前的工作没有尝试把图转成序列结构呢？就笔者个人的观点来看，这种序列转换要保持图结构的两个特点：1. 同构的性质。2. 邻居结点的连接关系。对于前者而言，意味着当我们把图上结点的标号随机打乱，得到的仍应是一样的序列。简单来说就是，同构图产生的序列应当相似，甚至一样；对于后者，则意味着我们要保持邻居结点与目标结点的距离关系，如在图中的三阶邻居在序列中不应该成为一阶邻居等。
Pathcy-san framework
下图可能可以帮助读者更好地理解这种算法，图来自[12]。整个流程自底向上：首先根据自定义规则对图里的结点进行排序，然后选择前6个结点，即图中的 1至6；接着我们把这些结点
Patchy-san 具体样例
频域卷积(Spectral Convolution)
空域卷积非常直观地借鉴了图像里的卷积操作，但据笔者的了解，它缺乏一定的理论基础。而频域卷积则不同，相比于空域卷积而言，它主要利用的是图傅里叶变换(Graph Fourier Transform)实现卷积。简单来讲，它利用图的拉普拉斯矩阵(Laplacian matrix)导出其频域上的的拉普拉斯算子，再类比频域上的欧式空间中的卷积，导出图卷积的公式。虽然公式的形式与空域卷积非常相似，但频域卷积的推导过程却有些艰深晦涩。接下来我们将攻克这部分看起来很难的数学公式，主要涉及到傅里叶变换(Fourier Transform)和拉普拉斯算子(Laplacian operator)。即使读者没有学过任何相关知识也不要紧，笔者将尽可能用形象的描述解释每个公式的涵义，让读者能感悟这些公式的美妙之处。
前置内容
如上所述，在本小节，我们将介绍两个主要的知识点：傅里叶变换与拉普拉斯算子。在介绍之前，我们先抛出两个问题：1. 什么是傅里叶变换; 2. 如何将傅里叶变换扩展到图结构上。这两个问题是前置内容部分要解决的核心问题，读者可带着这两个问题，完成下面内容的阅读。
傅里叶变换的示例
那傅里叶变换能干啥呢，有一个简单的应用是给图像去除一些规律噪点。比如说下面这个例子，原图来自知乎 [13]。
在傅里叶变换前，图像上有一些规律的条纹，直接在原图上去掉条纹有点困难，但我们可以将图片通过傅里叶变换变到频谱图中，频谱图中那些规律的点就是原图中的背景条纹。
傅里叶变换的示例
只要在频谱图中擦除这些点，就可以将背景条纹去掉，得到下图右侧的结果。
傅里叶变换的示例
除了可以用来分离噪声点与正常点，傅里叶变换还凭借上面的恒等式，在加速卷积运算方面有很大的潜力，**快速傅里叶变换(Fast Fourier Transform)**也是由此而生。实际上呢，现在大家最常用的卷积神经网络，完全可以搭配傅里叶变换。下面这张图就表示了一个普通的卷积神经网络如何与傅里叶变换搭配，其中的 IFFT 即 快速傅里叶变换的逆变换(Inverse Fast Fourier Transform：
傅里叶变换的示例
拉普拉斯算子(Laplacian operator) 的物理意义是空间二阶导，准确定义是：标量梯度场中的散度，一般可用于描述物理量的流入流出。比如说在二维空间中的温度传播规律，一般可以用拉普拉斯算子来描述。
拉普拉斯矩阵
示意图
参考文献
[1]. Neural Message Passing for Quantum Chemistry, https://arxiv.org/abs/1704.01212
[2]. Inductive Representation Learning on Large Graphs, https://arxiv.org/abs/1706.02216
[3]. Diffusion-Convolutional Neural Networks, https://arxiv.org/abs/1511.02136
[4]. Learning Convolutional Neural Networks for Graphs, https://arxiv.org/pdf/1605.05273
[5]. Spectral Networks and Locally Connected Networks on Graphs, https://arxiv.org/abs/1312.6203
[6]. Convolutional neural networks on graphs with fast localized spectral filtering, https://papers.nips.cc/paper/6081-convolutional-neural-networks-on-graphs-with-fast-localized-spectral-filtering
[7]. Semi-Supervised Classification with Graph Convolutional Networks, https://arxiv.org/pdf/1609.02907
[8]. 如何通俗易懂地解释卷积, https://www.zhihu.com/question/22298352
[9]. https://en.wikipedia.org/wiki/Convolution
[10]. https://mlnotebook.github.io/post/CNN1/
[11]. http://snap.stanford.edu/proj/embeddings-www
[12]. https://zhuanlan.zhihu.com/p/37840709
[13]. https://www.zhihu.com/question/20460630/answer/105888045
[14]. https://en.wikipedia.org/wiki/Laplacian_matrix
[15]. Spectral Networks and Locally Connected Networks on Graphs , https://arxiv.org/abs/1312.6203
[16]. Convolutional neural networks on graphs with fast localized spectral filtering, https://arxiv.org/abs/1606.09375
