最近打算从联邦学习方向转到联邦+图方向，因此读一些GNN相关的综述论文，从入门开始

摘要

深度学习被运用到图像分类、视频处理和自然语言处理等任务中，但是这些任务的数据表示都是在欧式空间中的。有一些任务的数据表示并不是在欧式空间中的，而是以图的形式进行表示。如果我们用传统的深度学习方法去完成这些任务将会非常棘手。GNN（graph neural networks）是解决这类任务的合适模型。

Introduction

曾经很多机器学习任务，如对象检测、机器翻译和语音识别，严重依赖人工的特征工程。这些问题被很多端对端的深度学习方法所解决，例如CNN，RNN。也就是说，在一些传统的机器学习任务中，例如图像识别，由于图像像素太多，我们需要人工去提取图像的一些关键特征，达到降维的过程。但是这个手工提取特征的过程被CNN给去掉了，不需要人工去提取特征，只需要将输入丢进去，就能拿到输出了，着就是“端对端”，两端分别代表者输入和输出。对于一个特定的任务，特征提取得好不好其实很重要，直接影响到最后模型的效果，端对端的深度学习方法可以自己去学习，也就是将特征提取这一步融入到算法中，不需要人来干预了。这也是深度学习相对于传统机器学习算法的一个明显的优势。

CNN等一些神经网络模型可以从欧式空间中的数据中学习特征，但是对于图的数据束手无策，因此在电子商务(e-commence)、蛋白质生物工程等领域CNN可能表现没有那么好。如何处理图数据是很多神经网络面临的难题，特别是对于CNN来说，因为在图的数据中一个节点的邻居节点的个数是不定的，那么CNN中适用于图像领域的卷积操作在处理图数据的时候便毫无用武之地了。另外一个原因是，在传统机器学习里面的一个核心假设便是每一个输入实例之间是相互独立、没有联系的，但是在处理图数据的时候我们必须要考虑这些邻接信息，甚至目标便是去挖掘这些邻接信息

为了处理图数据，许多研究者在CNN的基础上进行改进，设计新的模型去挖掘图数据的信息。有一种设想是将一张图也看作一个2D的图像，然后在这张图上进行卷积操作：

但是这种方法有几个缺点：1.邻居节点的个数是确定的。2.节点的顺序也是确定的。但是在我们认知的图中，这两者都是不确定的，一般使用的是以下的图卷积操作：

卷积操作本质上是一种局部的aggregation操作，是在局部做加权求和的运算操作，我们在上图的图卷积操作中将一个节点与邻居节点的边权进行加权求和得到这个节点的一个卷积值

背景

第一个出现的图神经网络是递归图神经网络(RecGNNs)，是GNN的先驱，与RNN不同的是，RNN是在时间维度上进行展开，而RecGNNs是在空间维度上进行展开。RecGNNs通过迭代地传播邻居信息直到达到稳定的固定点，来学习目标节点的表示。这种神经网络有一个缺点便是在计算上会非常昂贵

第二个出现的图神经网络是卷积图神经网络(ConvGNN)，顾名思义，这是收到CNN在计算机视觉领域成功实践的启发。ConvGNN主要分为两类方法，第一种是居于频谱的方法，第二种是基于空间的方法。

除了上面两种比较早的图神经网络，近几年在其基础上进行改进出现了许多新的神经网络：自动编码器(GAE)、时空图神经网络(STGNN)

图神经网络和图嵌入的对比

图嵌入（或者网络嵌入）旨在将网络节点表示为低阶的向量表示，同时保留网络的拓扑结构和节点的内容信息，以便可以使用简单的现成机器学习算法去执行后续的任务，如分类、聚类等。GNN是一个深度学习模型，旨在通过端对端的方式解决与图相关的任务。两者之间的主要区别在于，GNN是一些列神经网络模型的组合，适用与多种任务，而图嵌入是为了解决同一种任务的多种方法

图神经网络和图核方法的对比

图核方法是解决图分类问题的一种历史主导的技术。它通过核函数将图或者节点嵌入到向量空间中，与GNN的映射函数不同的是，该核函数是确定的而不是可学习的

定义

定义1：图

一张图由一系列的顶点和边来表示，即表示为$G=(V,E)$，其中$V$表示顶点(vertices)，$E$表示边(edges)，$v_i$表示第$i$个顶点，$e_{ij}$表示连接第$i$个顶点和第$j$的边的权值。 N ( v ) = { u ∈ V ∣ ( v , u ) ∈ E } N(v) = \{u \in V|(v,u)\in E\} N(v)={u∈V∣(v,u)∈E} 表示节点$v$的邻居节点的集合。邻接矩阵$A$表示如果$A_{ij}=1$代表着节点$i$和$j$具有相连的边，$A_{ij}=0$代表节点$i$和$j$不具有相连的边。$X\in R^{n\times d}$表示节点的属性，$n$个节点，$d$维的特征向量。$X^e\in R^{m\times c}$表示边的属性。

定义2：有向图

跟传统的有向图/无向图的定义一样

定义3：时空图(Spatial-Temporal Graph)

就是在图的定义中多加了一个时间维度，$G^{(t)}=(V,E,X^{(t)})$，其中$X^{(t)}\in R^{n\times d}$，按定义来理解便是图中节点的属性会随着时间改变

分类和框架

图神经网络的分类

Recurrent graph neural networks (RecGNNs)

旨在学习具有递归神经体系结构的节点表示。该模型假设图中的一个节点不断与其邻居交换信息，直到达到稳定状态。

Convolutional graph neural networks (ConvGNNs)

主要思想是对于图中的某个节点，它会汇总自身与邻居节点的信息来学到节点表示，并且可以通过多层卷及来学习到高阶节点表示

下图是使用ConvGNNs来对节点分类的一个例子：

在每一个卷积层，它会通过对每个节点的邻居节点的特征进行加权求和操作来封装该节点的隐藏表示，然后通过一个Relu层，类似与激活函数，并将结果输入到下一层中。一般层数越多，学到的隐藏表示便越高阶

下图是使用ConvGNNs来对图像分类的一个例子
该神经网络引入了池化层，目的是将一个完整的图分化为多个子图，然后去学习多个子图的高阶表示，最后综合多个子图的高阶表示来学到完整的图的高阶表示

Graph autoencoders (GAEs)

GAE是无监督学习，将节点和图嵌入为潜在向量空间，并从嵌入的信息中重构图数据。
该模型首先使用图卷积层来获得每个节点的嵌入表示，然后解码器计算该嵌入表示的一个成对的距离，然后通过激活函数重建图的邻接矩阵。

Spatial-temporal graph neural networks (STGNNs)

STGNN同时考虑空间依赖性和时间依赖性，其模型框架如下：

在上图中，一个CNN层会紧跟着一个卷积层，卷积层作用在$A$和$X^{(t)}$上捕获空间相关性，而CNN层沿着时间轴去捕获时间的相关性