“前不久，图灵奖获得者Geoffrey Hinton教授在演讲中透露了下一代神经网络模型的构想。那么，有哪些模型会成为下一代NLP模型的主力呢？”

 

今天，小犀为大家唠唠图神经网络…

图在生活中无处不在，其实我们每天面对的很多数据都是图，如地铁线路、社交网络、分子结构等。把数据和信息点通过关系串接成为各种知识图谱，也越来越多运用在大家的工作和学习中。

 

 

对于丰富的图数据，人们展开了大量研究。尤其是近年，算法炼丹师们对深度学习方法在图数据上的扩展越来越感兴趣。在GPU算力提升（已经每核1块钱了）和深度学习技术普及的推动下，研究人员借鉴了卷积网络、循环网络和深度自动编码器的思想，定义和设计了用于处理图数据的神经网络结构，由此一个新的研究热点——“图神经网络（Graph Neural Networks，GNN）”应运而生。

 

图神经网络是用于图结构数据的深度学习架构，将端到端学习与归纳推理相结合，业界普遍认为其有望解决之前处理不好的因果推理、可解释性等一系列瓶颈问题，是未来的重点研究领域。

 

可GNN如此火爆，我们还不太了解？别着急，今天小犀就以图卷积网络（Graph Convolution Networks，以下简称GCN）为例，带你走进图神经网络，一探其中奥秘。

 

了解CNN卷积模型的朋友应该知道，CNN的核心在于利用它的卷积核kernel，即一个个小窗口进行平移，通过卷积的方式来提取信号特征。

 

这种特征提取的方式在结构规则的图片、语言等数据上是非常奏效的，但是在一些不规则的数据结构（非欧空间数据），例如图结构的处理上显得有些吃力。

 

这时候GCN就出现了，简单理解，GCN跟CNN功能一样，是利用卷积原理进行特征提取，只不过它的对象是图数据。GCN精妙地设计了一种从图数据中提取特征的方法，从而让我们可以使用这些特征去对图数据进行节点分类（node classification）、图分类（graph classification）、边预测（link prediction），还可以顺便得到图的嵌入表示（graph embedding），可见用途广泛，功能强大。

 

那GCN如何实现从图数据中提取特征呢？主要基于物理思想——图中的每个结点由于受到邻居和更远的点影响，不断地改变自己的状态，直到最终的平衡，关系越亲近的邻居对其影响越大（是不是有点像NLP处理的上下文语义？）。

 

对GCN而言，节点Embedding是由自身和邻居节点Embedding聚合之后再进行非线性变换而得到。然而在对空间域(Spatial Domain)中节点的Embedding进行卷积操作(即聚合邻居Embedding信息)时，由于图数据的节点邻居个数、次序都是不定的，无法直接使用传统图像上的CNN模型中的卷积操作，所以需要从频谱域(Spectral Domain)上重新定义这样的卷积操作，再通过卷积定理转换回空间域上。

 

为了在频谱域和空间域中转换，就需要借助信号处理领域耳熟能详的傅里叶公式，其中涉及到图上傅里叶变换(从空间域变换到频谱域)和图上傅里叶逆变换(从频谱域回到空间域)的变换公式。下面就“空间域”、“频谱域”、“图上傅里叶变换”及“图上傅里叶逆变换”几个概念做简单介绍。

（前方大段公式预警…）⚠️⚠️⚠️

 

空间域与频谱域

 

空间域(spatial domain)又称顶点域(vertex domain)，是最直观感受GCN逐层传播算法的域，即：节点v的Embedding是其所有邻居节点Embedding(包括自己的Embedding)的聚合结果。由于空间域中图不满足平移不变性，无法直接在空间域中定义卷积。因此，引出了频谱域(spectral domain)的概念。

 

借助卷积定理，我们可以通过定义频谱域上的卷积操作来得到空间域图上的卷积操作。即将图由空间域变换到频谱域，频谱域中实现卷积，然后再变回空间域。那么图在频谱域上是如何表示的呢，这就引出了另一个概念：谱图理论，谱图理论主要研究的是图的拉普拉斯(Lapalacian)矩阵的特征值和所对应的特征向量对于图拓扑性质的影响，是对图空间拓扑的数学描述。下面先来介绍什么是拉普拉斯矩阵。

 

图的拉普拉斯矩阵

 

 

对于无向图G = (V, E)，其Laplacian矩阵的定义为：L = D - A，其中L 为拉普拉斯矩阵Laplacian matrix；D为对角度矩阵Degree matrix，对角线上的元素是顶点的度，即该元素链接的元素的个数；A为邻接矩阵 Adjacency matrix ，即表示任意两个顶点之间的邻接关系，邻接则为1，不邻接则为0。拉普拉斯矩阵还有几种扩展定义：

 L^sym:=D^-1/2LD^-1/ 称为对称正规拉普拉斯矩阵(Symmetric Normalized Laplacian)，论文中一般用的是这种Laplacian的定义。

L^rw:=D^-1L 称为随机游走正规拉普拉斯矩阵(Random Walk Normalized Laplacian)。

由于L = D - A，且无向图中D为对称矩阵，因此拉普拉斯矩阵是对称矩阵，可以进行特征分解(谱分解)，谱分解对于图从空间域到频谱域的变换至关重要，因为我们用来变换的工具傅里叶变换(Fourier Transform)需要利用Laplacian矩阵的特征值和特征向量，通过变换，从拓扑结构的图(spatial domain)到拉普拉斯矩阵再到谱图(spectral domain)这条链路就形成了。

 

傅里叶正变换：

从Spatial域到Spectral域

 

简单理解，傅里叶变换就是一种变换方式，将信号由 t 域变换到 w 域。

 

连续域的傅里叶变换定义为：

即信号 f(t) 与基函数e^−iωt 的积分。

图上的傅里叶变换，可仿上定义为将连续的傅里叶变换写成离散积分(求和)的形式：

 

其中f是对图上节点的变换，比如说返回节点Embedding，f(i)和图上的节点一一对应，ul(i)表示第l个特征向量的第i个分量。那么节点Embedding f(i)在特征值λl下的图傅里叶变换就是与λl对应的特征向量ul进行内积运算。

利用矩阵乘法将图上的傅里叶变换推广到矩阵形式：

 

即f 在图上的傅里叶变换的矩阵形式为：

简而言之，给定输入节点Embedding f, 左乘U⊤即可以得到f经图上傅里叶变换的输出Embedding  f^。

 

傅里叶逆变换：

从spectral域到spatial域

 

那么，我们将节点从空间域变换到频率域之后，怎么变换回空间域呢？传统的傅里叶逆变换是对频率ω积分：

类比到离散域(图上)则为对特征值λ_l求和：

利用矩阵乘法将图上的傅里叶逆变换推广到矩阵形式：

即f在图上的傅里叶逆变换的矩阵形式为：

简而言之，给定节点Embedding的在频率域上的表示 f^ ，左乘U即可得到节点Embedding在空间域上的表示。

那卷积定理如何实现？主要利用了函数卷积的傅里叶变换是函数傅里叶变换的乘积，即对于函数 f(t) 与 h(t) 两者的卷积是其傅里叶变换乘积的逆变换：

其中⋆表示卷积运算

 

概念和公式解释了这么多，总结一句话（小编：早点说嘛，看了那么多公式）：就是空间域卷积相当于傅立叶域（频谱域）相乘。如下图所示，先对图和卷积核做傅立叶变换后相乘，再傅立叶反变换回来，就得到了空间域卷积。其中的逻辑关系等价：空间域卷积——频谱域相乘。中间的桥梁就是傅立叶变换与反傅立叶变换。

 

以上只是GCN基于频谱域处理的原理，人们针对该方法在降低计算复杂度等方面提出了很多更实际的实现。

 

此外，还有基于空间域的卷积，主要是通过节点的k-hop邻居来聚合得到节点的特征表示。

 

除了图卷积网络(GCN)外，GNN中还有基于注意力更新的图网络(GAT)、基于门控的更新的图网络、具有跳边的图网络等。

 

目前，GNN的应用场景也不断延伸，覆盖了计算机视觉、自然语言处理、交通预测、知识图谱、推荐、反欺诈等场景。

但是，在一些实际场景中，网络的规模往往非常大，比如新浪微博，Twitter等社交关系网络，往往覆盖了数亿级的节点和边。目前绝大多数的图卷积神经网络模型还不适用于这种超大规模的网络。

 

并且，在实际场景中，网络往往具有动态性。这种动态性包括不断随时间变换的节点与边上的特征，不断变换的网络的结构。而目前的图卷积神经神经网络都是针对静态的网络设计的，因此设计能建模网络动态变化的图卷积神经网络也是未来的一个重要方向。

 

犀语算法团队也在努力研究和试验最新GNN相关模型及工程化，不断将更先进的NLP处理能力集成到各位看官的应用场景中，让我们共同期待吧！

 

———————————————