目录

19.什么是图谱和图傅里叶变换?

20.以 GCN 为例，简述基于频谱域的图神经网络的发展

图卷积网络(GCN)

GCN网络层数

小结笔记

---

19.什么是图谱和图傅里叶变换?

在数据的分析和统计应用中，数据往往呈现出非欧氏空间的复杂结构。它们不仅包含个体的信息，而且包含个体间相互关系的信息。因此，这种数据经常用图来表示。比如下列数据：大脑中神经元之间的相互作用；互联网链接网页的依赖关系；人与人之间的社会关系；代谢系统中蛋白质之间的关系；化学中化合物之间的结构；或者传感器网络中的传感器之间的相互作用。图恰恰可以用来表示这些数据的个体以及个体之间的相互关系。用统计的方法分析基于图表示的数据往往是行不通的，因为图表示的数据是没有数学结构(距离，范数)的离散的相互作用的个体。然而，基于谱图理论的技术为图数据的分析提供了一个类似“频率”的概念。

图傅里叶变换(Graph Fourier transformation, GFT)是一种类似于傅里叶变换的数据转换方法，它将焦点聚集在图的内部结构(拉普拉斯矩阵)和相应图特征(图信号)的相互作用上，并且提供了一种GSP 特征值谱的分析视角。相关领域近期工作的一个共同特点是：定义与顶点相关的数据为图信号，并运用类似经典的信号处理手段，研究新的GSP 技术，比如滤波、采样、插值等。

在GFT 中，拉普拉斯矩阵的特征值被当做GFT 的频率，拉普拉斯矩阵的特征矢量被当做GFT 的变换基。GFT 可以看作GSP 中的数学棱镜，矩阵的正交分解是其理论基础，它能将一个看似很复杂的图信号函数分解为一系列不同特征值的特征矢量的叠加。如果将特征矢量当做简单的信号函数，从分析的角度看，它是用简单的信号去逼近(或代替)复杂信号；从几何的角度看，它是以一族正交函数为基矢量，将函数空间进行正交分解，相应的系数(特征值)即为坐标；从变换的角度的看，它建立了图信号与特征值序列之间的对应关系；而从物理意义上看，它将图信号分解为一系列的简单信号的组合，从而建立了特征值谱理论。因此，通过GFT 可以将顶点域形式的图信号转换为图谱域形式的特征值谱。

简单来说，就是一副图像，可以认为是不同方向不同频率不同幅值的波组成的，傅里叶变换就是经过转换，得到这些波的信息，然后通过改变波进行一些处理。

20.以 GCN 为例，简述基于频谱域的图神经网络的发展

GCN问题本质

    图中的每个结点无时无刻不因为邻居和更远的点的影响而在改变着自己的状态直到最终的平衡，关系越亲近的邻居影响越大。

GCN的实质

    是在一张Graph Network中特征（Feature）和消息（Message）中的流动和传播！

研究GCN的原因

•     CNN无法处理非欧几里得结构数据，因为此种结构没有平移不变性，卷积核的大小无法固定不变。
•     拓扑图中包含许多重要的信息，可以通过图谱论进行挖掘。
•     拓扑连接是一种广义的数据结构，且一般来说任何数据在赋范空间内都可以建立拓扑关系。例如谱聚类（谱聚类原理总结）

GCN的目的：提取拓扑图的空间特征。

核心理论： Sepectral graph theory 图谱论

图谱论简述

核心思想：

•     借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质。
•     借助于图谱的理论来实现拓扑图上的卷积操作。

为什么GCN要用拉普拉斯矩阵？

• （1）拉普拉斯是对称矩阵，可以进行特征分解（谱分解），这和GCN的Spectral domain对应。
• （2）拉普拉斯矩阵只在中心顶点和一阶相连的顶点上（1-hop neighbor）有非0元素，其余之处均为0.
• （3）拉普拉斯算子和拉普拉斯矩阵之间的关系。

拉普拉斯矩阵的谱分解（特征分解）

•     矩阵的谱分解，特征分解，对角化都是同一概念。特征分解
•     不是所有矩阵都可以特征分解，充要条件为n阶方阵存在n个线性无关的特征向量。
•     线性无关与线性相关
•     拉普拉斯矩阵是半正定对称矩阵，有如下三个性质：
•     对称矩阵一定有n个线性无关的特征向量
•     半正定矩阵的特征值一定非负
•     对称矩阵的特征向量相互正交，及所有的特征向量构成的矩阵为正交矩阵。

为什么要使用图(Graph)？

很多问题在本质是都可以表示为图的形式。在真实世界中，我们会发现很多数据其实是以图的形式存在的，比如分子网络，社交网络以及论文引用网络等等。

基于图的任务

针对图数据，通常有以下几种比较常见的任务类型：

    结点分类(Node classification)：给定一个结点，预测其类型。

    链路预测(Link prediction)：预测两个结点之间是否存在连接。

    社区检测(Community detection)：确定具有紧密连接关系的结点簇。

    网络相似度(Network similarity)：衡量两个网络或子网络之间的相似性。

机器学习工作流

在图中，我们不仅有结点的特征（结点的数据），还有图的结构（结点之间是如何进行连接的）。

对于前者，我们很容易可以获得关于每一个结点的数据，但是对于后者，要抽取出关于网络结构的信息并非易事。

例如，如果两个结点相较其它结点更加相近，那我们是否应该以不同的方式来对待它们？对于具有很高或很低度(degree)的结点又应该如何处理？

事实上，每一个特定的任务在特征工程上，也即通过构造特征来表示结构信息，都是非常耗时耗力的事情。例如在下面的结点分类的任务中，特征的构造是一项具有技巧性的工作

将结点的特征与结构的信息同时作为输入，然后让机器自己去决定到底要利用哪些信息是非常有效且方便的方法，这也就是为什么我们需要图表示学习(Graph Representation Learning)的原因。

图卷积网络(GCN)

论文地址：Semi-supervised Classification with Graph Convolutional Networks

GCN是一种能够直接作用于图并且利用其结构信息的卷积神经网络。

这篇文章解决的是在一个图中，只有少部分结点的标签是已知情况下(Semi-supervised learning)的结点分类问题。

正如GCN名字中的卷积所揭示的，该思想是由图像领域迁移到图领域的。然而图像通常具有固定的结构，而图的结构却更加灵活、复杂。

GCN的主要思想：对于每个结点，我们都要考虑其所有邻居以及其自身所包含的特征信息。假设我们使用average()函数，那对每一个结点进行上述操作后，就可以得到能够输入到神经网络的平均值表示。

在上图中，我们以一个简单的引用网络为例。每一个结点代表一篇文章，而边代表代表引用情况。在这里首先有一个预处理的步骤，也就是将论文的原始文本通过NLP嵌入的方法先转化为向量。

接下来让我们考虑绿色结点。首先得到包括其自身的所有节点的特征值，然后取平均，然后该平均值向量可以输入到一个神经网络中，再得到一个向量。

上面的例子使用的是平均值函数，然而在实际应用当中我们可以采用更为复杂的聚合函数，GCN神经网络的结构也可以比上面图中的网络结构更复杂。如下图就是一个两层全连接GCN的例子，每一层的输出都作为下一层的输入。

GCN网络层数

网络层数的含义

网络的层数代表着结点特征所能到达的最远距离。比如一层的GCN，每个结点只能得到其一阶邻居身上的信息。对于所有结点来说，信息获取的过程是独立、同时开展的。当我们在一层GCN上再堆一层时，就可以重复收集邻居信息的过程，并且收集到的邻居信息中已经包含了这些邻居结点在上一个阶段所收集的他们的邻居结点的信息。这就使得GCN的网络层数也就是每个结点的信息所能达到的maximum number of hops。因此，我们所设定的层的数目取决于我们想要使得结点的信息在网络中传递多远的距离。需要注意的是，通常我们不会需要结点的信息传播太远。经过6~7个hops，基本上就可以使结点的信息传播到整个网络，这也使得聚合不那么有意义。

我们所使用的GCN应该有多少层？

在文章中，作者对于深层GCNs和浅层GCNs的效果开展了一些实验，由图可以看到，2~3层的网络应该是比较好的。当GCN达到7层时，效果已经变得较差，但是通过加上residual connections between hidden layers可以使效果变好。

小结笔记

•     GCNs可以用于网络中的半监督学习问题
•     GCNs可以用于学习网络中结点的特征与网络结构的信息
•     GCN的主要思想是对每个结点的邻居及其自身的信息作加权平均，从而得到一个可以传入神经网络的结果向量。
•     可以通过加深GCNs以获得更大的信息传播范围，如果要较大的层数，需要残差连接以提升效果。通常使用2~3层的GCN。
•     当看到矩阵时，可以当作是一种矩阵标准化的过程。
•     有一个GCN的demo库，提供了一些包括GCN在内的GNN算法。

**注意：**本文所提出的框架目前仅适用于有权或无权的无向图。然后有向图是可以通过添加额外的结点转化为无相图的。

print('下章预告：图神经网络-下')