图嵌入综述

图分析任务可以大致抽象的分为以下四类：（a)节点分类（b)链接预测（c)聚类（d)可视化。

真实的图（网络）往往是高维、难以处理的，20世纪初，研究人员发明了图形嵌入算法，作为降维术的一部分。

嵌入的思想是在向量空间中保持连接的节点彼此靠近。

自2010年以来，关于图嵌入的研究已经转移到解决网络稀疏性的可伸缩图嵌入技术上，例如，图分解（Graph Factorization)使用邻接矩阵的近似分解作为嵌入。

图嵌入的目的是发现高维图的低维向量表示。

图嵌入的方法：

主要分为三大类：

（1）基于因子分解的方法；
（2）基于随机游走的方法；
（3）基于深度学习的方法。

预备知识以及符号定义：

图嵌入的一些符号

一阶近似：边缘近似的权值也称为节点vi和vj之间的一阶近似值，因为他们是两个节点之间第一也是最重要的相似性度量。

二阶近似一对节点之间的二阶近似描述了该对节点领域结构的相似性。

二阶近似的例子

基于因子分解的方法

• Local Linear Embedding(LLE)

LLE假设每个节点都是嵌入空间中相邻节点的线性组合。如果假设图G的邻接矩阵元素代表节点j能够表示节点i的权重，我们定义：

于是我们可以通过最小化：

为了去除退化解，嵌入的方差被约束为：

• Laplacian Eigenmaps

拉普拉斯特征映射的目的是在权重wij较高时，保持两个节点嵌入后离得较近，也就是说被分割的太远的两个相似节点会得到更多的反馈（惩罚），具体来说，就是要最小化以下目标函数：

其中L是图G的拉普拉斯算子，目标函数受到：

• Cauchy graph embedding
  拉普拉斯特征映射对对嵌入节点之间的距离使用二次方的惩罚函数：

  
  
  
  
  因此，在保持节点之间的相似性的同时，节点之间的差异性会被破坏。柯西嵌入通过使用：
  
  替换原有的惩罚函数来解决这个问题，重新排列后，要最大化的目标函数变成：
  
  
  伴随着：
  
  
  和
  
  两个约束。新的目标函数是距离的反函数，因此更加强调相似的节点而不是不同的节点。

Structure Preserving Embedding(SPE)

Structure Preserving Embedding(SPE)

• 基于随机游走的方法

DeepWalk

DeepWalk方法受到word2vec的启发，首先选择某一特定点为起始点，做随机游走得到点的序列，然后将这个得到的序列视为句子，用word2vec来学习，得到该点的表示向量。Deepwalk通过随机游走可以获图中点的局部上下文信息，因此学到的表示向量反映的是该点在图中的局部结构，两个点在图中共有的邻近点（或者高阶邻接点）越多则对应的两个向量之间的距离就越短。

node2vec

与DeepWalk相似，node2vec通过最大化随机游走得到的序列中的节点出现的概率来保持节点之间的高阶邻近性。与DeepWalk最大的区别在于，node2Vec采用有偏随机游走，在广度优先（bfs)和深度优先(dfs)图搜索之间进行权衡，从而产生比DeepWalk更高质量和更多信息量的嵌入。

BFS和DFS的例子

Hierarchical representation learning for networks(HARP)

DeepWalk和node2vec随机初始化节点嵌入以训练模型。由于它们的目标函数是非凸的，这种初始化很可能陷入局部最优。HARP引入一种策略，通过更好的权重初始化来改进解决方案并避免局部最优。为此，HARP通过使用图形粗化聚合层次结构上一层中的节点来创造节点的层次结构。然后他生成最粗糙的图的嵌入，并用所学到的嵌入初始化精炼图的节点嵌入（层次结构中的一个）。它通过层次结构传播这种嵌入，以获得原始图形的嵌入。因此，可以将HARP与基于随机游走的方法结合使用，以获得更好的优化函数解。

• 基于深度学习的方法

Structural deep network embedding(SDNE)

SDNE建议使用深度自动编码器来保持一阶和二阶网络邻近度。它通过联合优化这两个近似值来实现这一点。该方法利用高度非线性函数来获得嵌入。模型由两部分组成：无监督和监督。前者包括一个自动编码器，目的是寻找一个可以重构其领域节点的嵌入。后者基于拉普拉斯特征映射，当相似顶点在嵌入空间中彼此映射得很远时，该映射将会受到惩罚。

半监督的SDNE模型

Deep neural networks for learning graph representations(DNGR)

DNGR结合了随机游走和深度自动编码器。该模型由3部分组成：随机游走，正点互信息（PPMI）计算和叠加去噪自编码器。在输入图上使用随机游走模型生成概率共现矩阵，将该矩阵转化为PPMI矩阵，输入到叠加去噪自动编码器中得到嵌入。输入PPMI矩阵保证了自动编码器模型能够捕获更高阶的近似度。此外，使用叠加去噪自动编码器有助于模型在图中存在噪声时的鲁棒性，以及捕获任务（如链路预测和节点分类）所需的底层结构。

Graph convolutional networks(GCN)

上面讨论的基于深度网络的方法，即SDNE和DNGR，以每个节点的全局（一行DNGR的PPMI和SDNE的邻接矩阵）作为输入。对于大型稀疏图来说，这可能时一种计算代价很高且不适用方法。图卷积网络（GCN）通过在图上定义卷积算子来解决这个问题。该模型迭代的聚合了节点的邻域嵌入，并使用在前一次迭代中学到的嵌入及其嵌入一个节点来描述全局邻域。
参考链接:https://zhuanlan.zhihu.com/p/62629465

什么是图神经网络？

在过去的几年中，神经网络的成功推动了模式识别和数据挖掘的研究。很多机器学习任务，如目标检测、机器翻译和语音识别，曾经严重依赖手工的特征工程来提取信息特征集，最近被各种端到端的深度学习范式（例如卷积神经网络（CNN）、长短记忆（LSTM）和自动编码器）彻底改变了。在许多领域中，深度学习的成功部分归因于快速发展的计算资源（如GPU）和大量训练数据的可用性，部分归因于深度学习从欧式空间数据中提取潜在表示的有效性。
尽管深度学习在欧式空间中的数据方面取得了巨大的成功，但在许多实际的的应用场景中的数据是从非欧式空间生成的，同样需要进行分析。例如，在电子商务中，一个基于图的学习系统能够利用用户和产品之间的交互来做出非常准确的推荐。图数据的复杂性对现有的机器学习的的算法提出了重大的挑战，这是因为图数据是不规则的。每个图都有一个大小可变的无序节点，图中的每个节点都有不同数量的相邻节点，导致一些重要的操作（例如卷积）在图像上很容易计算，但是不再适合直接用于图域。此外，现有机器学习算法的一个核心假设是实例彼此独立。然而，对于图数据来说，情况并非如此，图中的每个实例（节点）通过一些复杂的链接信息与其他实例（邻居）相关，这些信息可用于捕捉实例之间的相互依赖关系。
近年来，人们对深度学习的方法在图数据上的扩展越来越感兴趣。在深度学习的成功推进下，研究人员借鉴了卷积网络、循环神经网络和深度自编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点--“图神经网络（Graph Neural Network）”应运而生。
需要注意的是，图神经网络的研究与图嵌入或网络嵌入密切相关，图嵌入或网络嵌入式数据挖掘和机器学习届日益关注的另一个课题。图嵌入旨在通过保留图的网络拓扑结构和节点内容信息，将图中顶点表示为低维向量空间，以便使用简单的机器学习算法（例如，支持向量机分类）进行处理。许多图嵌入算法是通过无监督的算法，它们可大致分为三个类别，即矩阵分解、随机游走和深度学习方法。同时图嵌入的深度学习方法也属于图神经网络，包括基于图自动编码的算法（如DNGR和SDNE）和无监督训练的图卷积神经网络（如GraphSage）。下图描述了图嵌入和图神经网络的区别：

Network Embedding vs Graph Neural Network

历史脉络

1.图神经网络的概念最早是在2005年提出的。2009年Franco博士在其论文中定义了图神经网络的理论基础。
2.最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间（比如图像Image）或者序列（比如像文本Text），许多常见场景也都可以转换成图（Graph），然后就能使用图神经网络技术来建模。
3.2009年后图神经网络也陆续有一些相关研究，但是没有太大波澜。直到2013年，在图信号处理（Graph Singnal Pprocessing）的基础上，Bruna(这位是LeCun的学生)在文献中首次提出图上的基于频域（Spectral-domain）和基于空域（Spatial-domain）的卷积神经网络。
4.其后至今，学界提出了很多基于空域的图卷积方式，也有不少学者视图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少是，只受到部分学者的青睐。
5.值得一提的是，图神经网络与图表示学习（Represent Learning for Graph）的发展历程也惊人相似。2014年，在Word2vec的启发下,Perozzi等人提出了DeepWalk，开启了深度学习时代图表示学习的大门。更有趣的是，就在几乎同一时间，Bordes等人提出了大名鼎鼎的TransE，为知识图谱的分布表示（Represent Learning for Knowledge Graph）奠定了基础。

图神经网络(Graph Neural Network)

状态更新与输出

最早的图神经网络起源于Franco博士的论文，他的理论基础是不动点理论。给定一张图，每个节点都有自己的特征（feature），在此用表示节点的特征；连接两个节点的边也有自己的特征，在此用表示节点和节点之间的边的特征；GNN的学习目标是获得每个节点的图感知的隐藏状态(state embedding)，这就意味着：对于每个节点，它的隐藏状态包含了来自于邻居节点的信息。那么，如果让每个节点都感知到图上的其他节点呢？GNN通过迭代更新所有节点的隐藏状态来实现，在时刻，节点的隐藏状态按照如下方式更新：上面这个公式中的就是隐藏状态的状态更新函数，在论文中也被称为局部转移函数（local transaction function）。公式中的指的是与节点相邻的边的特征，指的是节点的邻居节点的特征,则指邻居节点在时刻的隐藏状态。注意是对所有的节点都成立的，是一个全局共享的函数。那么怎么把它和深度学习结合在一起呢？利用神经网络（Neural Network）来拟合这个复杂函数。值得一提的是，虽然看起来的输入是不定长参数，但是在内部我们可以先将不定长的参数通过一定操作变成一个固定的参数，比如说用所有的隐藏状态加起来表示所有的隐藏状态。下面举个例子来进行说明：

不动点理论

在开头提到，GNN的理论基础是不动点(the fixed point)理论，这里的不动点理论专指巴拿赫不动点定理(Banach's Fixed Point Theorem)。首先我们用表示若干个堆叠得到的一个函数，也称为全局更新函数，那么图上所有节点的状态更新公式可以写成：

不动点定理指的就是，不论是什么，只要是个压缩映射(contraction map),经过不断地迭代都会收敛到某一个固定的点，我们称之为不动点。那压缩映射又是什么呢，下图很好地展示了：

具体实现

在具体实现中，其实通过一个简单的前馈神经网络(Feed-forwar Neural Network)即可实现。比如说，一种实现方法可以是把每个邻居节点的特征、隐藏状态、每条相连边的特征以及节点本身的特征简单拼接在一起，在经过前馈神经网络后做一次简单的加和。

那么如何保证是个压缩映射呢，其实是通过限制对的偏导数矩阵的大小，这是通过一个对雅可比矩阵(Jacobian Matrix)的惩罚项(Penalty)来实现的。在这里使用表示在空间中的范数(norm)。范数是一个标量，它是向量的长度或者模，是在有限空间中坐标的连续函数。这里把简化成1维的，坐标之间的差值可以看作向量在空间中的距离，根据压缩映射的定义，可以导出：




推广一下，即得到雅可比矩阵的罚项需要满足其范数小于等于等价于压缩映射的条件。根据拉格朗日乘子法，将有约束问题变成带罚项的无约束优化问题，训练的目标可以表示成如下形式：

其中为超参数，与其相乘的项即为雅克比矩阵的罚项。

模型学习

上面我们花了一定的篇幅搞懂了如何让接近压缩映射，下面我们来具体叙述一下图神经网络中的损失是如何定义，以及模型是如何学习的。
仍然以社交网络举例，虽然每个节点都会隐藏状态以及输出，但并不是每个节点都有监督信号(Supervision)。比如说，社交网络中只有部分用户被明确标记了是否为水军账号，这样就构成了典型的节点二分类问题。那么很自然地，模型的损失即通过这些有监督信号的节点得到。假设监督节点一共有个，模型损失可以形式化为：那么模型如何学习呢？根据前向传播计算损失的过程，不难推出反向传播计算梯度的过程。在前向传播中，模型：
  1.调用若干次，比如次，直到收敛。
  2.此时每个节点的隐藏状态接近不动点的解。
  3.对于有监督信号的节点，将其隐藏状态通过得到输出，进而算出模型的损失。
根据上面的过程，在反向传播时，我们可以直接求出和对最终的隐藏状态的梯度。然而，因为模型递归调用了若干次，为计算和对最初的隐藏状态的梯度，我们需要同样递归式/迭代式计算次梯度。最终得到的梯度即为和对的梯度，然后该梯度用于更新模型的参数。这个算法就是Almeida-Pineda算法

GNN和RNN

相信熟悉RNN/LSTM/GRU等循环神经网络的同学看到这里有一点小困惑，因为图神经网络不论是前向传播的方式还是反向传播的优化优化算法，与循环神经网络都有点相像。这并不是你的错觉，实际上，图神经网络与循环神经网络确实很相似。为了清楚的显示出它们之间的不同我们用一张图来解释这两者设计上的不同：

• GNN的基础理论是不动点理论，这就意味着GNN沿时间展开的长度是动态的，是根据收敛条件确定的，而RNN沿时间展开的长度就等于序列本身的长度。
• GNN每次时间步的输入都是所有结点的特征，而RNN每次时间步的输入是该时刻对应的输入。同时，时间步之间的信息流也不相同，前者由边决定，后者则由序列的读入顺序决定。
• GNN采用AP算法反向传播优化，而RNN使用BPTT(Bacj Propogation Through Time)优化。前者对收敛性有要求，而后者对收敛性没有要求。
• GNN循环调用的目标是得到每个节点的稳定的隐藏状态，所以只有在隐藏状态收敛后才能输出；而RNN的每个时间步上都可以输出，比如语言模型。
  不过鉴于初代GNN和RNN结构上的相似性的，一些文章也喜欢把它称之为Recurrent-based GNN。

GNN的局限性

初代GNN，也就是基于循环结构的图神经网络的核心是不动点理论。它的核心观点是通过节点信息的传播使整张图达到收敛，在其基础上再进行预测。收敛作为GNN的内核，同样局限了其更为广泛的使用，其中最突出的是两个问题：

• GNN只将边作为一种传播手段，但并未区分不同边的功能。虽然我们可以在特征构造阶段为不同类型的边赋予不同的特征，但相比其他输入，边对结点隐藏状态的影响实在有限。并且GNN没有为边设置独立的学习参数，也就意味着无法通过模型学习到边的某些特征。
• 如果把GNN应用在图表示的场景中，使用不动点理论并不合适。这主要是因为基于不动点的收敛会导致节点之间的隐藏状态间存在较多的信息共享，从而导致节点状态太光滑(Over Smooth)，并且属于节点自身的特征信息匮乏(Less Informative)

门控图神经网络(Gated Graph Neural Network)

我们在上面细致的比较了GNN和RNN，可以发现他们有诸多相通之处。那么我们能不能直接用类似RNN的方法来定义GNN呢？于是乎，门控图神经网络(Gated Graph Neural Network,GNN
)就出现了。虽然在这里它们它们看起来类似，但实际上，它们的区别非常大，其中最核心的不同即是门控神经网络不以不动点理论为基础。这意味着：不再需要是一个压缩映射；迭代不需要到收敛才输出，可以迭代固定步长；优化算法也从AP算法转向BPTT。

状态更新

与图神经网络定义的范式一致，GGNN也有两个过程：状态更新与输出。相比GNN而言，它的主要区别来源于状态更新阶段。具体地，GNN参考了GRU的设计，把邻居节点的信息视作输入，节点本身的状态视为隐藏状态，其状态更新函数如下：

如果读者对GRU的更新公式熟悉的话，对上述式子应该很好理解。仔细观察上面这个公式，除了GRU式的设计外，GGNN还针对不同类型的边引入了可学习的参数W，每种edge对应一种，这样它就可以处理异构图。
但是，仔细对比GNN的GGNN的状态更新公式，细心的读者可能会发现：在GNN里需要作为输入的节点特征没有出现在GGNN的公式中！但是实际上，这些节点的特征对我们预测至关重要，因为它才是各个节点的根本所在。
为了处理这个问题，GGNN将节点特征作为隐藏状态初始化的一部分。那么重新回顾一下GGNN的流程，其实是这样：

• 用节点特征初始化各个节点的（部分）隐藏状态。
• 对整张图，按照上述状态更新公式固定迭代若干步。
• 对部分有监督信号的节点求得模型损失，利用BPTT算法反向传播求得和GRU参数的梯度。
  从初始化的流程我们也可以看出GNN和GGNN的区别：GNN依赖于不动点理论，所以每个节点的隐藏状态即使使用随机初始化都会收敛到不动点；GGNN则不同，不同的初始化对GGNN最终的结果影响很大。

图卷积缘起

在开始正式介绍图卷积之前，我们先花一点篇幅探讨一个问题：为什么研究者们要设计图卷积操作，传统的卷积不能直接用在图上吗？要理解这个问题，我们首先要理解能够应用传统卷积的图像（欧式空间）与图（非欧空间）的区别。如果把图像中的每个像素点视作一个节点，如下图左侧所示，一张图片就可看作一个非常稠密的图；下图右侧则是一个普通的图，阴影不分点代表卷积核，左侧是一个传统的卷积核，右侧则是一个图卷积核。卷积代表的含义在后门中会详细叙述，这里读者可以将其理解为在局部范围内的特征抽取方法。

• 在图像为代表的欧式空间中，节点的邻居数量都是固定的。比如说绿色节点的邻居始终是8个（边缘上的点可以做padding填充）。但在图这种非欧空间中，节点有多少邻居并不固定。目前绿色节点的邻居节点有2个，但其他节点也会有5个邻居的情况。
• 欧式空间中的卷积操作实际上是用固定大小可学习的卷积核来抽取像素的特征，比如这里就是抽取绿色节点对应像素及其相邻像素点的特征。但因为图里的邻居节点不固定，所以传统的卷积核不能直接用于抽取图上的节点的特征。
  真正的难点聚集在邻居节点数量不固定上。那么，研究者们如何解决这个问题呢是？其实说来也简单的，目前主流的研究从2条路来解决这件事：
• 提出一种方式把非欧式空间的图转换成欧式空间。
• 找到一种可以处理变长邻居节点的卷积核在图上抽取特征。
  这两条实际上也是后续图卷积神经网络的设计原则，图卷积的本质是想找到适用于图的可学习卷积核。

图卷积框架（Framework）

上面说了图卷积的核心特征，下面我们先来一窥图卷积神经网络的全貌。如下图所示，输入的是整张图，在Covolution Layer 1里，对每个节点的邻居进行一次卷积操作，并用卷积的结果更新该节点；然后经过激活函数如relu，然后再过一层卷积层Convolution Layer 2与一层激活；反复上诉过程，直到层数达到预期深度。与GNN类似，图卷积神经网络也有一个局部输出函数，用于将节点的状态（包括隐藏状态与节点特征）转换成任务相关的标签，比如水军账号分类，本文称这种任务为Node-Level的任务；也有一些任务是对整张图进行分类的，比如化合物分类，本文中称这种任务为Graph-Level的任务，它们会在卷积层后加入更多的操作。

卷积（Convolution）

正如之前所提到的，图卷积神经网络主要有两类，一类是基于空域的，另一类则是基于频域的。通俗点解释，空域可以类比到直接的图片的像素点上进行卷积，而频域可以类比到对图片进行傅里叶变换后，再进行卷积。傅里叶变换的概念先不深入，先对两类方法的代表模型做一个大概介绍。

• 基于空域卷积的方法直接将卷积操作定义在每个节点的连接关系上，它跟传统的卷积神经网络的卷积更相似一些。在这个类别中比较有代表性的方法有Message Passing Neural Networks(MPNN),GraphSage,Diffusion Convolution Neural Netwrks(DCNN)
  , PATCHY-SAN等。
• 基于频域卷积的方法则从图信号处理起家，包括 Spectral CNN
  ，Cheybyshev Spectral CNN(ChebNet)
  ,和First order of ChebNet(1stChebNet)等。

基础概念

由维基百科的介绍我们可以得知，卷积是一种定义在两个函数（跟）上的数学操作，旨在产生一个新的函数。那么和的卷积就可以写成，数学定义如下：

实例：掷骰子问题

光看数学定义可能会觉得非常抽象，下面举一个掷骰子的问题。（参考知乎）
想象我们现在有两个骰子，两个骰子分别是和，表示骰子向上一面为数字1的概率。同时抛掷这两个骰子1次，它们正面朝上数字和为4的概率是多少呢？相信大家很快就能想出它包含的三种情况，分别是：

• 向上为1，向上为3；
• 向上为2，向上为2；
• 向上为3，向上为1；
  最后这三种情况出现的概率和即为问题的答案，如果写成公式，就是，可以绘制成下图：
  
  
  如果稍微拓展一点，比如我们说或者等是可以取到的，只是它们的值为0而已。那么该公式就可以写成。仔细观察，这其实就是卷积。如果将它写成内积的形式，卷积其实就是。这么一看，是不是就对卷积的名字理解更加深刻了呢？所谓卷积，其实就是把一个函数卷（翻）过来，然后再与另外一个函数求内积。
  对应到不同方面，卷积可以有不同的解释：既可以看作我们在深度学习中常说的核（Kernel），也可以对应到信号处理中的滤波器（Filter）。而可以是我们所说的机器学习中的特征（Feature），也可以是信号处理中的信号（Signal）。和的卷积就可以看作是对的加权求和。

空域卷积（Spatial Convolution）

从设计理念上看，空域卷积与深度学习中的卷积的应用方式类似，其核心在于聚合邻居节点的信息。比如说一种最简单的无参卷积方式就是：将所有直连邻居节点的隐藏状态加和，来更新当前节点的隐藏状态。

这里非参式的卷积只是为了举一个简单易懂的例子，实际上图卷积在建模时需要的都是带参数、可学习的卷积核。

消息传递网络（Message Passing Neural Network）

消息传递网络(MPNN) 是由Google科学家提出的一种模型。严格意义上讲，MPNN不是一种具体的模型，而是一种空域卷积的形式化框架。它将空域卷积分解为两个过程：消息传递和状态更新操作，分别由和函数完成，将的特征作为其隐藏状态的初始态，空域卷积对隐藏状态的更新由如下公式表示：

其中代表图卷积的第层，上式的物理意义是：收到来自每个邻居后，每个节点如何更新自己的状态。
对比之前的GGNN，可能会发现这个公式与GGNN的公式很像。实际上，它们是截然不同的两种方式：GCN中通过级联的层捕捉邻居的消息，GNN通过级联的时间来捕捉邻居的消息；前者层与层之间的参数不同，后者可视为层之间共享参数。MPNN的示意图如下：

http://snap.stanford.edu/proj/embeddings-www/

图采样与聚合（Graph Sample and Aggregate）

MPNN很好地概括了空域卷积的过程，但定义在这个框架下的所有模型都有一个共同的缺陷：卷积操作针对的对象是整张图，也就意味着要讲所有节点放在内存/显存中，才能进行卷积操作。但对实际场景中的大规模图而言，整个图上的卷积操作并不现实。GraphSage提出的动机之一就是解决这个问题。从该方法的名字我们也能看出，区别传统的全图卷积，GraphSage利用采样（sample）部分节点的方式进行学习。当然，即使不需要整张图同时卷积，GraphSage仍然需要聚合邻居的信息，即论文中定义的的操作。这种操作类似于MPNN的消息传递过程。

1. 在图中随机采样若干个节点，节点数为传统任务中的batch_size。对于每个节点随机选择固定数目的邻居节点（这里邻居不一定是一阶邻居，也可以是二阶邻居）构成进行卷积操作的图。
2. 将邻居节点的信息通过函数聚合起来更新刚才采样的结点。
   3.计算采样节点处的损失。如果是无监督任务，我们希望图上的邻居节点的编码相似；如果是监督任务，即可根据具体结点的任务标签计算损失。
   最终，GraphSage的状态更新公式如下：
   
   GraphSage的设计重点就放在了函数的设计上。它可以是不带参数的，，也可以是带参数的如等神经网络。核心的原则仍然是，它需要可以处理变长的数据。

图结构序列化（PATCHY-SAN）

在之前提过卷积神经网络不能应用在图结构上是因为图是非欧式空间，所以大部分算法都沿着找到适用于图的卷积核这个思路走。而PATCHY-SAN算法另辟蹊径，它将图结构转化为序列结构，然后直接利用卷积神经网络在转化成的序列结构上做卷积。由于PATCHY-SAN在其论文中主要用于图的分类任务，我们下面的计算过程也主要针对图分类问题（例如，判断某个社群的职业）。
那么，图结构转换成序列结构最主要的挑战在何处呢，如果简单的话，为什么以前的工作没有尝试把图转换成序列结构呢？？这样的序列转换要保持图结构的两个特点：1.同构的性质。2.邻居接地那的连接关系。对于前者而言，意味着当我们把图上节点的标号随机打乱，得到的仍应是一样的序列。简单来说就是，同构图产生的序列应当相似，甚至一样；对于后者，则意味着我们要保持邻居节点与目标节点的距离关系，如在图中的三阶邻居在序列中不应该成为一阶邻居等。
PATCHY-SAN通过以下三个步骤来解决这两个问题：
1.节点选择（Node Sequence Selection）。该过程旨在与通过一些人为定义的规则（如度大的节点分数高，邻居的度大时分数较高等）为每个节点指定一个在图中的排序。在完成排序后，取出前个节点作为整个图的代表。
2.邻居节点构造（Neighborhood graph construction）。在完成节点排序后，以第1步选择的节点为中心，得到它们的邻居（这里的邻居可以是一阶邻居，也可以是二阶邻居）节点，就构成了个团。根据第1步得到的节点排序对每个团中的邻居节点进行排序，再取前k个邻居接地那按照顺序排列，即组成个有序的团。
3.图规范化（Graph Nornmalization）。按照每个团中的节点顺序可将所有团转换成固定长度的序列，再将它们按照中心节点的顺序从前到后依次拼接，即可得到一个长度为的代表整张图的序列。这样，我们就可以直接使用带1D的卷积神经网络对该序列建模，比如图分类（可类比文本序列分类）。值得注意的一点是，在第1步和第2步中，如果取不到或个节点时，要使用空节点作为填充(padding)。
一个形象的流程图如下所示：

频域卷积（Spectral Convolution）

空域卷积非常直观地借鉴了图像里的卷积操作，但据作者的了解，它缺乏一定的理论基础。而频域卷积则不同，相比于空域卷积而言，它主要利用的是图傅里叶变换（Graph Fourier Transform）实现卷积。简单来讲，它利用图的拉普拉斯矩阵（Laplacian matrix）导出其频域上的拉普拉斯算子，再类比频域上的欧式空间中的卷积，导出图卷积的公式。虽然公式的形式与空域卷积非常相似，但频域卷积的推导过程却有些艰深晦涩。接下来我们将攻克这部分看起来很难得数学公式，主要涉及到傅里叶变换（Fourier Transform）和拉普拉斯算子（Laplacian operator）。

• 什么是傅里叶变换（What is Fourier Transform）

借用维基百科的说法，傅里叶变换（FourierTransform, FT）会讲一个在空域（或时域）上定义的函数分解成频域上的若干频率成分。换句话说，傅里叶变换可以将一个函数从空域变到频域。先抛开傅里叶变换的数学公式不谈，用来表示傅里叶变换的话，我们先将一个很重要的恒等式：

这里的指的是傅里叶逆变换，是哈达玛乘积，指的是两个矩阵（或向量）的逐点乘积（Element-wise Multiplication）。仔细观察上面这个公式，它的直观含义可以用一句话来概括：空（时）域卷积等于频域乘积。简单来说就是，如果要算与的卷积，可以先将它们通过傅里叶变换变换到频域中，将两个函数在频域中相乘，然后再通过傅里叶变换转换出来，就可以得到和的卷积结果。下面的动图形象地展示了傅里叶变换的过程，这里我们把函数傅里叶变换后的结果写作。

拉普拉斯算子（Laplacian operator）的物理意义是空间二阶导，准确定义是：标量梯度场中的散度，一般可用于描述物理量的流入流出。比如说在二维空间中的温度传播规律，一般可以用拉普拉斯算子来描述。

为什么是特征函数呢？我们这里根据拉普拉斯算子的定义来稍微推导一下。众所周知，特征向量需要满足的定义式是：对于矩阵，其特征向量满足的条件应是矩阵与特征向量做乘法的结果，与特征向量乘标量的结果一样，即满足如下等式。
稍微推导一下即可知道，拉普拉斯算子作用在确实满足以上特征向量的定义：

这里的是求导符号，是二阶导。
实际上，再仔细观察傅里叶变换的式子，它本质上是将
函数映射到了以{}为基向量的空间中。

• 图上的傅里叶变换

终于到了本节的重点内容了，上面我们絮絮叨叨地铺垫了很多傅里叶变换的知识，主要是为了将傅里叶变换类比到图上，那么问题来了：在图上，我们去哪找拉普拉斯算子与呢？
聪明的研究者们找到了图的拉普拉斯矩阵(L)及其特征向量()，作为上述两者的替代品，至此，形成了图上傅里叶变换的生态系统。拉普拉斯矩阵，实际上是度矩阵（D）减去邻接矩阵（A），，如下图所示，图源自于wikipedia

正交矩阵的逆矩阵等于其转置矩阵
接下来我们要介绍的图上的频域卷积的工作都是在的基础上做文章。

频域卷积网络（Spectral CNN）

我们上面推导的这个就是首个提出的频域卷积神经网络的卷积核 https://arxiv.org/abs/1312.6203。假设层的隐藏状态为，类似地，第层为.。频域卷积层的状态更新计算公式如下：


仔细观察上式，可以发现一层卷积层参数有个。这里的其实可以类比全连接神经网络中的权重，为了方便读者理解，作者做了下面的示意图：

切比雪夫网络（ChebNet）

基本的频域卷积网络要计算拉普拉斯所有的特征值和特征向量，计算量巨大。在论文中提出了切比雪夫网络，它应用切比雪夫多项式（Chebyshev polynomials）来加速特征矩阵的求解。假设切比雪夫多项式的第k项是， 频域卷积核的计算方式如下：

切比雪夫多项式是以传递方式定义的一系列正交多项式序列。

那么怎么来呢，可以由切比雪夫多项式的定义得来：，递推式的前两项为以及.的作用是将特征向量矩阵归一化到[-1,1]之间。

图读出操作（Readout）

之前我们分别介绍了基于循环的图神经网络和基于卷积的图神经网络，那么在本篇中，我们则主要关注在得到了各个节点的表示后，如何生成整个图的表示。
图的读出操作，顾名思义，就是用来生成图表示的。它的别名有图粗化(Graph Coarsening)/图池化（Graph Pooling）。对于这种操作而言，它的核心要义在于：操作本身要对节点顺序不敏感。
这是为什么呢？这就不得不提到图本身的一些性质了。我们都知道，在欧式空间中，如果一张图旋转了，那么形成的新图片就不再是原来那张图片了；但在非欧式空间的图上，如果将一个图旋转一下，例如对它的节点重新编号，这样形成的图域原来的图其实是一个。这就是典型的图重构（Graph Isomorphism）问题。比如下面左右两个图，其实是等价的：

• 基于统计的方法（Statistics Category）

基于统计的方法应该是最常见的，比如说我们在求各种抽象表示所使用的平均（mean），求和（sum），取最大值（max）等操作。这些方法简单有效，又不会带来额外的模型参数。但同时我们必须承认，这些方法的信息损失太大。假设一个图里有1000个节点，每个节点的表示是100维；整张图本可表示的特征，这些简单的统计函数却直接将信息量直接压缩到了100维。尤其是，在这个过程中，每一维数据的分布特性被完全抹除。
考虑到这一点，文献的作者就提出要用类似直方图的方法来对每维数据分布进行建模。具体而言，可以通过以下的对比图来直观感受以下直方图是如何巧妙平衡数据信息的压缩与增强的。假设我们用100个介于[-3,1]的数字，如果我们直接将它们求和，如左图所示，我们完全看不出这100个数据的分布；而如果我们将[-3,1]等分成4个区域，比如说就是[-3,-2),[-2,-1),[-1,0),[0,1)。我们分开统计各个区域的和，可以发现一点原数据的分布特征，就如下右侧子图所示：

• 基于学习的方法（Learning Category）

基于统计的方法的一个坏处大概是它没办法参数化，间接地难以表示节点到图向量的这个“复杂”过程。基于学习的方法就是希望神经网络来拟合这个过程。

• 采样加全连接（Sample And FC）

最简单又最直接的做法，大概就是取固定数量的节点，通过一个全连接层（Fully connected Layer）得到图的表示。这里不论是随机采样也好，还是根据某些规则采样，都需要得到确定数量的节点，如果不都就做填充。公式也很简单直接（指的是将采样到的节点表示拼接在一起）：

这种方法的一个问题在于很难适用于规模差距很大的图。比如说训练时见过的图只有几百个节点，但测试的图可能有上千和节点，这种方法很难泛化。

• 全局节点（Global Node）

这一种做法的动机也很简单，考虑到图同构问题和基于统计的方法，从结点的表示生成最终的图表示主要有两个难点：

1. 很多情况下我们很难找到一个合适的根节点；
2. 如果直接用基于统计的方法对每个结点一视同仁，无法区别对待（比如某些重要的结点信息更多，就应该表达更多）。
   那我直接引入一个全局节点表示这张图的根节点，把它跟图中的每个节点通过一种特殊的边连接，最终拿下这个接地那的表示作为图的表示，岂不妙哉。

• 可微池化（Differentiable Pooling）

上面两种方法都比较简单，不会层次化去获得图的表示。所以论文
中，作者提出了一种层次化的图表示，而这则依赖于他们所提出的可微池化（Differentiable Pooling, DiffPool）技术。简单来讲，它不希望各个节点一次性得到图的表示，而是希望通过一个逐渐压缩信息的过程，来得到最终图的表示，如下图所示：

有哪些图神经网络？

在本文中，我们将图神经网络划分为五大类别，分别是：图卷积网络（Graph Convolution Networks,GCN）图注意力网络（Graph Attention Networks）、图自编码器（Graph Autoencoders）、图生成网络（Graph Generative Networks）和图时空网络（Graph Spatial-temporal Networks）。

符号定义

• 图卷积网络（Graph Convolution Networks,GCN）

图卷积网络将卷积运算从传统数据（例如图像）推广到图数据。其核心思想的是学习一个函数映射f(.)，通过该映射图中的节点vi可以聚合它自己的特征xi与它的邻居特征

• 1.Spectral-based Graph Convolutional Networks
  在基于频谱的图神经网络中，图被假定为无向图，无向图的一种鲁邦数学表示是正则化图拉普拉斯矩阵，即
  
  其中，A为图的邻接矩阵，D为对角矩阵且
  
  正则化图拉普拉斯具有实对称半正定的性质。利用这个性质，正则化拉普拉斯矩阵可以分解为
  
  ，其中
  U是由
  L的特征向量构成的矩阵，
  是对角矩阵，对角线上的值为L的特征值。正则化拉普拉斯矩阵的特征向量构成了一组正交基。
  在图信号处理过程中，一个图的信号：
  是一个由图的各个节点组成的特征向量，
  代表第i个节点。对图X的傅里叶变换由此被定义为：
  傅里叶反变换则为
  
  其中
  为傅里叶变换后的结果。
  为了更好地理解图的傅里叶变换，从它的定义我们可以看出，它确实将输入图信号投影到正交空间，在正交空间中，基由正则化图拉普拉斯的特征向量构成。
  转换后得到的信号
  的元素是新空间中图信号的坐标，因此原来的输入信号可以表示为：
  
  正是傅里叶反变换的结果。现在我们可以来定义对输入信号X的图卷积操作了!
  其中，
  是我们定义的滤波器；
  表示Hadamard product。假如我们定义这样一个滤波器：
  那么我们的图卷积操作可以简化表示为：

参考链接
参考链接