近些年神经网络的成功极大促进了人类在模式识别和数据挖掘方向的研究。许多机器学习任务，比如目标识别[1-2]，机器翻译[3-4]和语音识别[5]，在过去十分依赖手动提取有用的特征信息，但现如今已可以使用各种各样的端到端学习方法，如卷积神经网络（CNNs）[6]，递归神经网络（RNNs）[7]以及自编码器（autoencoders）[8]。深度学习在诸多领域的成功可以归因于计算机资源（可以狭义认为是GPU）的快速发展以及深度学习从欧氏空间提取隐藏表示的高效性。
虽然深度学习方法可以有效地提取欧氏空间下对象的隐藏表示，但现在有许多应用涉及的数据却都是由图结构表示的，如电子商务中用户和商品的关系、化学中的分子模型、社交网站的引文网络等等。图的复杂性对现有的机器学习方法造成了极大的挑战。因为图不规则，即图本身可大可小；图包含的节点可以有序也可以无序；每个节点的邻居个数也可能不一样hellip;hellip;这些特性导致一些可以在欧氏空间使用的操作（如卷积操作）难以应用到图结构。更重要的是，现有的机器学习方法的核心假设是学习的对象之间是相互独立的，但这种假设显然不适用于图结构，因为图中的节点以边相连，每条边代表两个节点之间的某种关系。
不过受CNNs、RNNs、自编码器的启发，研究人员也开发出许多适用于图结构的方法。参考其他文献，本报告也将这些用于图结构的方法统称为图神经网络（GNNs）。 现今，人们一般将图神经网络进一步细分为4小类，即递归图神经网络（RecGNNs）、图卷积神经网络（ConvGNNs）、图自编码器（GAEs）和时空图神经网络（STGNNs）。
图卷积神经网络（ConvGNNs）
图卷积神经网络，顾名思义，也采用了卷积的操作。因为图卷积相较于其他神经网络方法效率更高且更加方便，所以近些年ConvGNNs快速流行起来。总的来说，ConvGNNS分为了两类，即基于频域（spectral-based）和基于空域（spatial-based）的两类方法。基于频域的方法以图信号处理[10]的视角，通过引进滤波器来定义图卷积操作。简单来说，可以将基于频域的图卷积理解为移除图信号中的噪声。而基于空域的方法更加类似传统的在图像上应用的卷积操作。可以将图中的节点比作图像中的像素，相应的空域的图卷积操作也就被定义为一个节点与该节点的邻居进行卷积。特别需要提的是，相较于基于频域的方法，基于空域的方法更高效、灵活且泛化能力强，所以基于空域的方法近年来发展极为迅猛。
- 基于频域的图卷积神经网络（Spectral-based ConvGNNs）
基于频域的方法在图信号分析[10-12]中有坚实的数学基础。它们认为图是无向的，而归一化的图拉普拉斯矩阵正是无向图的数学表示。归一化的图拉普拉斯矩阵被定义为，其中表示图的度矩阵，。归一化的图拉普拉斯矩阵具有一个良好的性质，即它是实对称的半正定矩阵，因此它可以被分解为，其中是由特征向量按序排列形成的矩阵，则是以特征值作为主元素的对角矩阵。在图信号处理中，一个图信号是一个包含了所有节点的特征向量，就表示第个节点的值。对信号的图傅里叶变换被定义为，图的逆傅里叶变换则为，其中是信号经过傅里叶变换后的结果。图傅里叶变换将输入的图信号投影到以归一化图拉普拉斯矩阵的特征向量为基的正交空间，而是图信号在新空间中的坐标。因此，输入信号可以表示为，即图的逆傅里叶变换。进一步，用一个过滤器对输入信号进行图卷积的过程被定义为：
其中，表示逐元素积，即哈达玛积。基于频域的方法都采用这样的图卷积定义，但不同的方法选择的过滤器不同。
谱卷积神经网络（Spectral CNN）[13]假定过滤器是由可学习的参数构成的集合。Spectral CNN的卷积层被定义为：
其中，表示层号，是输入图信号，表示输入通道个数，表示输出通道个数。因为利用了拉普拉斯矩阵的特征分解，Spectral CNN也面临三个限制。第一，图的任何变动都将导致特征基的变动；第二，学习到的过滤器对卷积域有非常强的依赖性，意味着它们无法适用于不用的图结构；第三，特征分解的时间复杂度为，这是难以接受的。因此，在随后的工作中，ChebNet[14]和GCN[15]，利用近似和简化的方法将计算复杂度降低至。
- 基于空域的图卷积神经网络（Spatial-based ConvGNNs）
与传统的定义在图像上的卷积方法类似，基于空域的方法在一个节点和其他节点的空间关系基础上定义图卷积。当像素被视为节点的时候，图像其实可以被视为一张特殊的图。正如图1a所描述的那样，每个像素与相邻像素相连，利用一个大小的卷积核对图像进行卷积。类似地，如图1b所示，基于空域的图卷积在中心节点和其邻居之间进行，可以得到中心节点的数据表示。从另一种角度看，基于空域的图卷积神经网络其实借鉴了递归图神经网络信息传播的思想，即卷积操作实质上在利用边传播节点信息。基于空域的图卷积神经网络都遵循这样的思想，如[16-18]。
