图卷积网络入门(GCN)

【转】GCN入门

这篇文章很好的介绍了：

时域、空域、频域；频域的优势
傅立叶级数、连续傅立叶变换；傅立叶变换应用
拉普拉斯算子、图拉普阿斯矩阵、拉普拉斯谱分解
图上傅立叶变换
图卷积
初代GCN

本博客记录了本人对于该文的一点理解，仅供自己学习GNN、GCN使用。

1. 图：一种非欧数据结构

在欧氏空间中，卷积网络（CNN）具有平移不变性、权值共享、局部连接、分层次表达的特点，而图片及音频信号在其域中具有局部的平移不变性，因此卷积神经网络在图片及音频处理问题上表现良好。

平移不变性：
平移是一种几何变换，表示把一幅图像或一个空间中的每一个点在相同方向移动相同距离。比如对图像分类任务来说，图像中的目标不管被移动到图片的哪个位置，得到的结果（标签）应该是相同的，这就是卷积神经网络中的平移不变性。平移不变性意味着系统产生完全相同的响应（输出），不管它的输入是如何平移的。

平移不变性依赖于CNN的卷积和池化两步操作

然而，图网络是一种非欧式结构的数据，网络是不规则的关系型数据，因此其不存在平移不变性。

无向图的空间结构：(G=(Omega,W))，其中(Omega)表示图中所有节点的集合，(size = m)；(W)表示图的邻接矩阵，(shape = (m,m)),由于是无向图，(W)是一个对称矩阵。(W)中的值(W_{i,j})表示节点(i,j)之间的边的权重，为非负值，当这两个节点之间没有边的时候，认为权重值为0。

图中每个节点一般具有两种信息：

一是每个节点都有自己的特征信息。比如人的三维骨架，每个点都有三维坐标数据。

二是图谱中的每个节点还具有结构信息。具体来说就是节点与节点之间相连的信息。

个人理解：找不到一个统一模式的卷积核对于图中的每一个节点进行常规的卷积操作，因为图中的每一个节点都具有不同的特征信息以及结构信息。

因此，图是一种非欧式空间的数据结构，无法进行传统意义上的卷积操作。本论文旨在解决这一问题，将卷积的思想从欧式数据扩展到非欧数据上。

1.1 图的空域（节点域）和频域（谱域）

空间域与频率域为我们提供了不同的视角。在空间域中，函数自变量（x,y）被视为二维空间中的一个点，数字图像f(x,y)即为一个定义在二维空间中的矩形区域上的离散函数；换一个角度，如果将f(x,y)视为幅值变化的二维信号，则可以通过某些变换手段（如傅里叶变换、离散余弦变换、沃尔什变换和小波变换等）在频域下对图像进行处理了因为在频率域就是一些特性比较突出，容易处理。比如在空间图像里不好找出噪声的模式，如果变换到频率域，则比较好找出噪声的模式，并能更容易的处理。

具体名词解释如下：

空间域　英文： spatial domain。释义：又称图像空间(image space)。由图像像元组成的空间。在图像空间中以长度(距离)为自变量直接对像元值进行处理称为空间域处理。
频率域。英文： spatial frequency domain。释义：以频率(即波数)为自变量描述图像的特征,可以将一幅图像像元值在空间上的变化分解为具有不同振幅、空间频率和相位的简振函数的线性叠加,图像中各种频率成分的组成和分布称为空间频谱。这种对图像的频率特征进行分解、处理和分析称为频率域处理或波数域处理。

二者关系：

空间域与频率域可互相转换。在频率域中可以引用已经很成熟的频率域技术,处理的一般步骤为：①对图像施行二维离散傅立叶变换或小波变换,将图像由图像空间转换到频域空间。②在频率域中对图像的频谱作分析处理,以改变图像的频率特征。即设计不同的数字滤波器,对图像的频谱进行滤波。

空间域处理的应用可以参考：

频率域处理主要用于与图像空间频率有关的处理中。如图像恢复、图像重建、辐射变换、边缘增强、图像锐化、图像平滑、噪声压制、频谱分析、纹理分析等处理和分析中。

参考: 图的空域和频域

1.2 图结构数据扩展到GCN遇到的困难

对于图结构的数据，从最早的基于深经网络框架的GNN到将卷积引入图数据中，说实话卷积还真是个好东西。引入卷积的这类算法又被分为谱方法（spectral approaches）和非谱方法（non-spectral approaches）两类。谱方法是基于图的谱表征，通过图拉普拉斯算子的特征分解，在傅里叶域中定义的卷积运算需要进行密集的矩阵计算和非局部空间的滤波（计算）。在此基础上，GCN很有效地对节点的一阶邻域进行处理，从为避免复杂的矩阵运算。但是GCN依赖于图的结构信息，这就导致了在特定图结构上训练得到的模型往往不可以直接被使用到其他图结构上。非谱方法是直接在图上进行卷积而不是在图的谱上。这种方法的挑战之一是如何找到一个或者定义一个运算来处理可变大小的邻域并保证参数共享机制。

2. 空域与频域的转换

2.1 拉普拉斯算子

在数学中，拉普拉斯算子（Laplacian）是由欧几里得空间中的一个函数的梯度的散度给出的微分算子，通常有以下几种写法： $\Delta ,\nabla^2,\nabla \cdot \nabla$ 。所以对于任意函数 $f$ 来说，其拉普拉斯算子的定义为：

$\Delta f = \nabla^2 f = \nabla \cdot \nabla f \\ \\$

这里引入了一个新的概念——散度，这里简单介绍下：

散度（Divergence）是向量分析的一个向量算子，将向量空间上的向量场（矢量场）对应到一个标量场。散度描述的是向量场里一个点是汇聚点还是发源点。值为正时表示该点为发源点，值为负时表示该点为汇聚点，值为零时表示该点无源。散度在物理上的含义可以理解为磁场、热源等。

回到正文，我们看下拉普拉斯算子在 n 维空间中的笛卡尔坐标系的数学定义：

$\Delta f = \sum_{i=1}^n \frac{\partial ^2 f}{\partial x_i^2} \\ \\$

数学表示为各个维度的二阶偏导数之和。

以一维空间为例：

$\begin{aligned} \frac{\partial ^2 f}{\partial x_i^2} &= f^{''}(x) \\ &\approx f^{'}(x) - f^{'}(x-1) \\ &\approx f(x+1) - f(x) -(f(x) - f(x-1)) \\ &= f(x+1) + f(x-1)) - 2f(x) \end{aligned} \\ \\$

也就是说二阶导数近似于其二阶差分，可以理解为当前点对其在所有自由度上微扰之后获得的增益。这里自由度为 2，分别是 +1 和 -1 方向。

再以二维空间为例子：

$\begin{aligned} \Delta f(x,y) &= \frac{\partial ^2 f}{\partial x^2} + \frac{\partial ^2 f}{\partial y^2} \\ &=[f(x+1,y) + f(x-1,y)) - 2f(x,y) ]+[f(x,y+1) + f(x,y-1)) - 2f(x,y)] \\ &=f(x+1,y) + f(x-1,y)) + f(x,y+1) + f(x,y-1)) - 4f(x,y) \\ \end{aligned} \\ \\$

看到上面可能大家会很可能很陌生，但是这个就是图像中的拉普拉斯卷积核：

此时共有 4 个自由度 (1,0),(-1,0),(0,1),(0,-1)，当然如果对角线后其自由度可以为 8。

对此我们可以进行归纳：「拉普拉斯算子是所有自由度上进行微小变化后所获得的增益」。

我们将其推广到网络图中，考虑有 N 个节点的网络图，其自由度最大为 N，那么函数 $f$ 可以是 N 维的向量，即：

$f = (f_1,...,f_N) \\ \\$

其中， $f_i$ 表示函数 $f$ 在网络图中节点 i 处的函数值，类比 $f(x,y)$ 为函数 $f$ 在 (x,y) 的函数值。

在网络图中，两个节点的之间的增益为 $f_i-f_j$ ，考虑加权图则有 $w_{ij}(f_i-f_j)$ ，那么对于节点 i 来说，总增益即为拉普拉斯算子在节点 i 的值：

$\begin{aligned} \Delta \boldsymbol{f}_i &= \sum_{j \in N_i} \frac{\partial f_i}{\partial j^2} \\ & \approx \sum_{j} w_{ij} (f_i - f_j) \\ &= \sum_{j} w_{ij} (f_i - f_j) \\ &= (\sum_{j} w_{ij}) f_i - \sum_j w_{ij} f_j \\ &=d_if_i - w_{i:}f_i \\ \end{aligned} \\ \\$

其中， $d_i=\sum_{j\in N_i} w_{ij}$ 为节点 i 的度；上式第二行去掉了 $j\in N_{i}$ 是因为 $w_{ij}$ 可以控制节点 i 的邻接矩阵。

对于任意 $i\in N$ 都成立，所以我们有：

$\begin{aligned} \Delta {f} =\left( {\matrix{ {\Delta {f_1}} \cr \vdots \cr {\Delta {f_N}} \cr } } \right) & = \left( {\matrix{ {{d_1}{f_1} - {w_{1:}}f} \cr \vdots \cr {{d_N}{f_N} - {w_{N:}}f} \cr } } \right) \cr & =\left( {\matrix{ {{d_1}} & \cdots & 0 \cr \vdots & \ddots & \vdots \cr 0 & \cdots & {{d_N}} \cr } } \right) f - \left( {\matrix{ {{w_{1:}}} \cr \vdots \cr {{w_{N:}}} \cr } } \right)f \cr &= diag({d_i})f - \mathbf{W}f \cr &= (\mathbf{D} -\mathbf{W})f \cr &= \mathbf{L} f \cr \end{aligned} \\$

自此，我们便给出了图拉普拉斯矩阵的推导过程，这个公式的全称为：图拉普拉斯算子作用在由图节点信息构成的向量 $f$ 上得到的结果等于图拉普拉斯矩阵和向量 $f$ 的点积。拉普拉斯矩阵反映了当前节点对周围节点产生扰动时所产生的累积增益，直观上也可以理解为某一节点的权值变为其相邻节点权值的期望影响，形象一点就是拉普拉斯矩阵可以刻画局部的平滑度。

2.2 图拉普拉斯矩阵

图拉普拉斯矩阵可以定义为：

$\mathbf{L} = \mathbf{D}-\mathbf{W} \\ \\$

其中，D 为度矩阵，W 为邻接矩阵（对于有权图，W为有权邻接矩阵）。

考虑归一化后的拉普拉斯矩阵：

$\mathbf{L}_N = \mathbf{D}^{-1/2}(\mathbf{D}-\mathbf{W})\mathbf{D}^{-1/2} \\ \\$

2.3 拉普拉斯矩阵的谱分解

首先来看看什么是谱分解：维基百科：特征分解

拉普拉斯矩阵的谱分解就是矩阵的特征分解：

$\mathbf{Lu_k} = \lambda_k \mathbf{ u_k}\\ \\$

对于无向图来说，拉普拉斯矩阵是实对称矩阵，而实对称矩阵一定可以用正交矩阵进行正交相似对角化：

$\mathbf{L}=\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{-1} \\ \\$

其中， $\mathbf{\Lambda}$ 为特征值构成「对角矩阵」， $\mathbf{U}$ 为特征向量构成的「正交矩阵」。

又因为正交矩阵的逆等于正交矩阵的转置： $\mathbf{U}^{-1} = \mathbf{U}^{T}$ ，所以我们有：

$\mathbf{L}=\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{-1} =\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{T} \\ \\$

因为 L 是半正定矩阵，我们还可以有：

$\begin{aligned} f^T \mathbf{L} f &= f^TDf - f^TWf \\ &=\sum_id_if_i^2 - \sum_{i,j} f_i f_j w_{ij} \\ &=\frac{1}{2}\big(\sum_i d_i f_i^2-2\sum_{ij}f_i f_j w_{ij} + \sum_id_i f_i^2 \big) \\ &= \frac{1}{2}\sum_{i,j} w_{ij} (f_i - f_j)^2 \\ \end{aligned} \\ \\$

其中， $f_i$ 为节点 i 的信号。我们称 $f^T \mathbf{L} f$ 为图信号的总变差（Total Variation），可以刻画图信号整体的平滑度。

拉普拉斯的谱分解具有以下几点性质：

由于拉普拉斯矩阵以每行（列）元素之和为零，因此拉普拉斯矩阵的至少有一个特征值为 0，对应的特征向量 $u_0 = [1，1，，。。。 1]^T / \sqrt{N}$ ，且满足： $\mathbf{L} u_0 = 0 u_0$ 。
拉普拉斯矩阵的特征值都大于等于零，归一化的拉普拉斯矩阵的特征值区间为 [0, 2]；
如果有 n 个特征值为 0，则表示图有 n 个子图相互无连接；
特征值的总和为矩阵的迹，对于归一化的拉普拉斯矩阵，如果没有孤立节点或子图，其特征值为 N。

2.4 傅立叶变换

傅立叶变换分为傅立叶级数和连续傅立叶变换，我们先说傅立叶级数。

傅立叶级数适用于周期性函数，它能够将任何周期性函数分解成简单震荡函数的集合（正弦函数和余弦函数），举个例子，比如说下图：

左边是一个周期函数，右边是将周期函数分解成多个简单震荡函数，所以这个周期函数用数学公式可以表达为：

$f(t) \approx 2.5 + \frac{10}{\pi} {\left( \sin{{\frac{{\pi t}}{4}}} + \frac{1}{3}\sin{{\frac{{3 \pi t}}{4}}} + \frac{1}{5}\sin{{\frac{{5 \pi t}}{4}}} + \frac{1}{7}\sin{{\frac{{7 \pi t}}{4}}} \right)} \\ \\$

我们看到上图中的信号是随着时间变换的，所以我称之为「时域（Time domain）」。

我们观察到，不同的振荡函数具有不同的振幅和频率，以上图为例 $\frac{1}{3}sin(\frac{3\pi t}{4})$ 的振幅为 1/3 而频率为 $f=\frac{\omega}{2\pi} = \frac{3}{8}$ ，考虑以频率为横坐标，振幅为纵坐标，我们有：

这个就是我们所说的频域（Frequency Domain），其和时域是等价的，不过是从另外一个角度去描述信号。我们把它放在一起看一下：

给出傅立叶级数的公式：

$f(x)= \frac{a_0}{2} + \sum_{n=1}^{\infty} a_n \sin (n \omega x + \varphi_n) \\ \\$

还可以将其稍作变换：

$f(x)= \frac{a_0}{2} + \sum_{n=1}^{\infty} a_n \sin (n \omega x) + \sum_{n=1}^{\infty} b_n \cos (n \omega x) \\ \\$

这样我们便能看出来，此时的标准正交基为 $\{1, sin(n\omega t),cos(n\omega t)\; \big| \; n=1,..,\infty \}$ ，而对应的系数 $\{ \frac{a_0}{2},a_n,b_n \big| n=1,...,\infty \}$ 其实就是傅立叶级数在这组标准正交基下的向量。这便是傅立叶变换，将信号从时域变换到频域中。

这里介绍下傅立叶变换后的基为正交基，因为有个知识点后面还会用到。

我们知道判断两个向量是否正交可以用向量点乘求和等于 0 来判断，这种方法我们称为点积（内积）：

$v \cdot w = v^t w = v_1w_1 + v_2w_2 + ...+v_nw_n = 0 \\ \\$

与向量点积不同的是，函数是连续的，假设现在有两个函数 f 和 g，f 的周期为 2n，我们也想用上述连续累加的方式来使得函数内积和向量内积的概念一致，而积分正是函数累加的概念，所以我们有：

$f\cdot g = \int_0^{2\pi} f(x)g(x)dx \\ \\$

对于上面我们说的傅立叶变换后的正交基，我们容易得到：

$\int_{0}^{2\pi} cos(mx)sin(nx) dx = 0 \\ \int_{0}^{2\pi} sin(mx)sin(nx) dx = \pi \delta_{mn} \quad m,n>1 \\ \int_{0}^{2\pi} cos(mx)cos(nx) dx = \pi \delta_{mn} \quad m,n>1 \\ where \quad \delta_{mn} = \left\{ \begin{aligned} 1 \quad m = n \\ 0 \quad m \neq n \end{aligned} \right. \\ \\$

容易证明上述标准基为正交基。

在数学里，希尔伯特空间（Hilbert Space）是有限维欧几里得空间的一个推广，是一个完备的内积空间，其定义了一个带有内积的完备向量空间。在希尔伯空间中，一个抽象元素通常被称为向量，它可以是一个复数或者函数。傅立叶分析的一个重要目的是将一个给定的函数表示成一族给定的基底函数的和，而希尔伯特空间为傅立叶分析提供了一种有效的表述方式。

可能大家看到这里要爆炸了，不过不用担心，我们只需要记住上面「两个函数的内积形式」即可。

现实中大部分函数都是非周期的，如果涉及到非周期性函数该怎么办呢？

在介绍非周期性函数之前，我们先简单介绍下欧拉公式。

考虑横轴为 1，纵轴为虚单位 i 的坐标系，图上任意一点都可以表示为 $cos\theta + i\;sin \theta$ 。

根据欧拉公式，我们可以写成：

$cos\theta + i\;sin \theta = e^{i\theta} \\ \\$

其中，e 为自然对数的底数。

所以坐标轴上的点现在有了两种表示方式：

考虑 $\theta = \omega t$ ， $\theta$ 会随着 t 的增大而逆时针旋转。所以 $e^{i \omega t}$ 可以表示为坐标点 A 随着时间 t 逆时针旋转。我们以时间 t 为横坐标，则可以记录到坐标点 A 映射在虚轴的运动轨迹：

左边图是我们看到的旋转频率，称为频域，而右边图看到是时间流逝，称为时域，是不是和我们刚刚介绍的（从时域变换到频域）正好相反？也就是说，时域和频域其实是可以相互转换的。

回到正题，考虑非周期函数的傅立叶变换。

事实上，我们可以将非周期函数考虑为周期无穷大的函数，考虑频域中的横坐标： $f=\frac{1}{T}$ ，当周期 T 无穷大大时，频域图就从离散点变为连续的曲线，如下图：

那么，我们该如何从这个非周期函数中分解出各种信号呢？答案就是利用正交！比如说，假设这函数中有一个 $cos(n \omega x)$ 的信号，那么我们用 $cos(n wx)$ 就可以把它乘出来，而其他分量如 $\{1, sin(m\omega x),cos(k\omega x)| m,k=[1...\infty) , k\neq n\}$ 都会因为正交而消失。所以我们需要对函数做一个内积：

$\mathcal{F}_T(\omega) = \int_{-\infty}^{+\infty} f(t)e^{-i\omega t} dt \\$

其中， $e^{-iwt}$ 刚刚介绍过，就是一组正交基的组合。我们用正交基去与函数求内积，如果原函数中包含频率为 $\omega$ 的三角函数，则 $\mathcal{\hat F}_T(\omega)$ 便为 0，反之为 0，这样自然分离能分离出相应的信号，其图示如上图 c 中右部分所示。

细心的同学可能还会注意到上式的计算的结果中还有复数 i。其实是样子的：「实数部分表示振幅」，「虚数部分表示相位」。相关资料同学们可以自己查阅，不再进行过多介绍。

以上就是我们所说的傅立叶变换（Fourier Transform，FT）。同样的我们也存在逆变换：

$f(t) = \frac{1}{2\pi} \int_{-\infty}^{+\infty} \mathcal{F}_T e^{i\omega t}d\omega \\ \\$

于是，我们便实现了将信号拆成多个正弦信号，再把正弦信号逆变换为原来信号的过程。

简单介绍下傅立叶变换的应用吧，省得看了那么多不知道他能干什么。

一个很经典的例子就是：分离、降噪。如果男生和女生一起说话，该如何分离出两者的声音呢？答案就是对这一段声音（时域）做傅立叶变换转换到频率，而男女生的声音频率不同，在频域中，低频为男生，中频为女生，高频可能为噪音，我们可以根据需要去除中频和高频的信号，并将其进行逆变换，这样便分离出了男生的声音。

2.5 图傅立叶变换

我们之前提到，我们在图上定义卷积操作，遇到的困难主要是空域不具备“平移不变性”，难以定义一个合适的卷积核。要想解决这个问题，有两种思路，一种是设法直接在空域定义卷积，另一种方法是先将空域转化到谱域，在谱域上定义卷积操作，最后再将结果转化回空域。图傅立叶变换就是用于完成图的空域与谱域之间的转化。

回顾下拉普拉斯谱分析：

$\mathbf{Lu_k} = \lambda_k \mathbf{ u_k}\\ \\$

我们类比一下：

信号中的傅立叶变换网络图中的傅立叶变换频率 $\omega$ 特征值 $\lambda_k$ 正交基中某个向量 $e^{iwt}$ 正交矩阵中的某个向量 $\mathbf{u_k}$

是不是长得非常像，所以我们也有了网络图上的傅立叶变换：

$\mathcal{ F}_T(\lambda_k) = \hat f_k=\sum_{i=1}^N f(i) u_{k}(i) \\ \\$

其中， $f_k=(f_k(i),...,f_k(n))$ 为网络图上的 n 维向量， $f_k(i)$ 表示网络中的节点 i 的第 k 个分量， $u_{k}(i)$ 表示特征向量 k 的第 i 个分量。做个类比解释：特征值（频率） $\lambda_k$ 下， $f$ 的图傅立叶变换（振幅）等于 $f$ 与 $\lambda_x$ 对应的特征向量 $\mathbf{u_k}$ 的内积。

考虑矩阵乘法：

$\begin{aligned} {\hat f} =\left( {\matrix{ {{\hat f_1}} \cr \vdots \cr {\hat f_N} \cr } } \right) & =\left( {\matrix{ {u_1(1)} & \cdots & u_1(n) \cr \vdots & \ddots & \vdots \cr u_n(1) & \cdots & {u_n(n)} \cr } } \right) \left( {\matrix{ {{ f_1}} \cr \vdots \cr {f_N} \cr } } \right) = \mathbf{U}^T{ f} \end{aligned} \\ \\$

所以我们得到了「图傅立叶变换的矩阵形式」，这里的 $\mathbf{U}$ 为拉普拉斯谱分解的正交矩阵。

我们也可以得到傅立叶逆变换：

$f = \mathbf{U}\mathbf{U}^{-1}f = \mathbf{U}\mathbf{U}^{T}f = \mathbf{U}\hat f \\ \\$

2.6 谱域卷积

现在有了图傅立叶变换，又有了离散卷积操作，那么我们想：既然无法直接在空域进行卷积，可否将图信号映射到频域后再做卷积操作。

所以我们有：

$\begin{aligned} (f*h)_{G} &= \mathcal{F}^{-1}[\mathcal{F}\{ f\} \cdot \mathcal{F}\{ h \} ] \\ &= \mathcal{F}^{-1}[\mathbf{U}^T f \cdot \hat h ] \\ \end{aligned} \\ \\$

其中，向量 $\hat f$ 与向量 $\hat h$ 的元素点积，等价于将 $\hat h$ 组织成对角矩阵的形式进行矩阵乘法，所以我们有：

$\begin{aligned} (f*h)_{G} &= \mathcal{F}^{-1}[\mathbf{U}^T f \cdot \hat h ] \\ &= \mathcal{F}^{-1}[ diag[\hat h_1,...,\hat h_n] \mathbf{U}^T f ] \\ \end{aligned} \\ \\$

最后我们再左乘 $\mathbf{U}$ 进行逆变换：

$\begin{aligned} (f*h)_{G} & = \mathbf{U}{ diag[\hat h_1,...,\hat h_n ]}\mathbf{U}^T{ f}\\ \end{aligned} \\ \\$

这里，我们不写成 $\hat{h}= \mathbf{U}^T h$ 的主要原因在于，我们可以将其与深度学习相结合，在 GCN 中我们的卷积核是可训练并且参数共享的，所以在此我们可以直接将 $diag[\hat h_1,...,\hat h_n ]$ 写成 $diag[\theta_1,...,\theta_n ]$ ，这个便是深度学习中的可学习参数。

3. GCN-1（Spectral GNN）

第一代的卷积神经网络也就是刚刚我们给出的公式：

$y =\sigma(\mathbf{U}g_{\theta}\mathbf{U}^Tx ) =\sigma(\mathbf{U}{ diag[\theta_1,...,\theta_n ]}\mathbf{U}^T{x}) \\ \\$

这和论文中给出的公式是一样的：

$x_{k+1,j} = h\big( V \sum_{i=1}^{f_{k-1}}F_{k,i,j}V^{T}x_{k,i} \big) \\ \\$

我们也称之为 Spectral GNN。

这边补充一点，在这篇论文中，作者还给出了一个基于空域的「深度局部连接网络」（Deep Locally Connected Networks），我们可以简单看一下：

每一层变换定义为：

$x_{k+1,j}= L_k h\big( \sum_{i=1}^{f_{k-1}}F_{k,i,j}x_{k,i} \big) \quad j=1,..,f_k \\ \\$

其中， $x_{k,j}$ 表示第 k 第 i 个节点； $F_{k,i,j}$ 表示第 k 层节点 i 和节点 j 的权值，考虑局部邻居； $h(\cdot)$ 表示卷积运算； $L_k$ 表示第 k 层的池化操作。也就是说每个节点都是由其邻居和自身卷积池化得到。

虽然看起来很简单，但是优点在于它不需要很强的前提假设，其只需要网络具有局部邻域结构，甚至不需要很好的 Embedding 向量。

但这种结构下有一个很大的缺点：「没有办法实现共享参数」。

作者针对这种问题提出了我们所看到第一代图卷积神经网络。

4. GCN-2（ChebNet）

第一代的图卷积神经网络很巧妙的利用图谱理论来实现拓扑图的卷积操作，但其有很多缺点，比如说：计算复杂度太高，我们需要对拉普拉斯矩阵进行谱分解得到特征向量矩阵 $\mathbf U$ ，时间复杂度为 $O(n^3)$ ；就算实现完成谱分解，在做矩阵运算时时间复杂度也高达 $O(n^2)$ ；此外，GCN-1 的卷积操作是全局的操作，并不是仅来源于节点的邻域。

针对这些问题，学者提出了第二代 GCN：ChbeyNet。

首先我们回顾下图傅立叶变换：

$\mathcal{ F}_T(\lambda_k) = \hat g_k = \sum_{i=1}^N g(i) u_{k}(i) \\ \\$

可以看到这是一个和特征值密切相关的函数，我们不妨将 $g_\theta$ 写成拉普拉斯矩阵 L 的特征值函数 $g_{\theta}(\Lambda)$ ：

$y =\sigma(\mathbf{U} g_{\theta} \mathbf{U}^T x ) =\sigma(\mathbf{U}{g_\theta(\Lambda) }\mathbf{U}^T{x}) \\ \\$

然后这个卷积核有两个局限性：

不具备局部连接性；
时间复杂度为 $o(n)$ 。

为了克服这个缺点，我们引入 K 阶多项式：

$g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_k \Lambda^k \\ \\$

其中，参数 $\theta_k \in {R}^K$ 是多项式系数，这样滤波器就具有了 K 阶局部性了，复杂度也降低到 $O(K)$ 。

我们将这个公式带入卷积运算中：

$y =\sigma(\mathbf{U}{g_\theta(\Lambda) }\mathbf{U}^T{x}) =\sigma(\mathbf{U}\sum_{k=0}^{K-1} \theta_k \Lambda^k\mathbf{U} x) = \sigma(\sum_{k=0}^{K-1}\theta_k L^k x) \\ \\$

此时，我们计算图卷积运算就不需要再乘上特征向量矩阵 $\mathbf{U}$ ，而是直接使用拉普拉斯矩阵 L 的 k 次方，这样就避免了进行特征分解。而我们可以事先计算好 $L^k$ ，这样就只需要计算矩阵相乘。同时由于 L 为稀疏矩阵，所以时间复杂度为 $O(K|E|)$ ， $|E|$ 为节点边数。

此外，作者还引入了切比雪夫展开式来近似 $L^k$ 。

设 $T_{k}(x)$ 为切比雪夫多项式的第 k 阶式子，切比雪夫多项式的递归式为： $T_{k}(x) = 2xT_{k-1}(x) - T_{k-2}(x), \; T_{0}(x) =1, \;T_{1}(x)=x$ 。所以我们有：

$g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_k T_k(\widetilde \Lambda) \\ \\$

其中， $\widetilde \Lambda = \frac{2}{\lambda_{max}}\Lambda - I_N$ ； $\lambda_{max}$ 是指拉普拉斯矩阵 L 的最大值。

❝ 这是因为切比雪夫多项式的输入要在 $[-1,1]$ 之间，由于拉普拉斯矩阵的半正定性，所以所有的特征值都是大于等于 0 的，将其除以最大特征值可以将特征压缩到 $[0,1]$ 区间内，现在需要将其压缩到 $[-1, 1]$ ，所以我们有： $\widetilde \Lambda = 2\Lambda/\lambda_{max}-I$
❞