图卷积网络 GCN Graph Convolutional Network（谱域GCN）的理解和详细推导[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

1. 为什么会出现图卷积神经网络？

普通卷积神经网络研究的对象是具备Euclidean domains的数据，Euclidean domains data数据最显著的特征是他们具有规则的空间结构，如图片是规则的正方形，语音是规则的一维序列等，这些特征都可以用一维或二维的矩阵来表示，卷积神经网络处理起来比较高效。

CNN的【平移不变性】在【非矩阵结构】数据上不适用

• 平移不变性（translation invariance）：比较好理解，在用基础的分类结构比如ResNet、Inception给一只猫分类时，无论猫怎么扭曲、平移，最终识别出来的都是猫，输入怎么变形输出都不变这就是平移不变性，网络的层次越深这个特性会越明显。
• 平移可变性（translation variance）：针对目标检测的，比如一只猫从图片左侧移到了右侧，检测出的猫的坐标会发生变化就称为平移可变性。当卷积网络变深后最后一层卷积输出的feature map变小，物体在输入上的小偏移，经过N多层pooling后在最后的小feature map上会感知不到，这就是为什么R-FCN原文会说网络变深平移可变性变差。

离散卷积本质就是一种加权求和。CNN中的卷积就是一种离散卷积，本质上就是利用一个共享参数的过滤器（kernel），通过计算中心像素点以及相邻像素点的加权和来构成feature map实现空间特征的提取，当然加权系数就是卷积核的权重系数(W)。

那么卷积核的系数如何确定的呢？是随机化初值，然后根据误差函数通过反向传播梯度下降进行迭代优化。这是一个关键点，卷积核的参数通过优化求出才能实现特征提取的作用，GCN的理论很大一部分工作就是为了引入可以优化的卷积参数。

生活中很多数据不具备规则的空间结构，称为Non Euclidean data，如，推荐系统、电子交易、分子结构等抽象出来的图谱。这些图谱中的每个节点连接不尽相同，有的节点有三个连接，有的节点只有一个连接，是不规则的结构。对于这些不规则的数据对象，普通卷积网络的效果不尽人意。CNN卷积操作配合pooling等在结构规则的图像等数据上效果显著，但是如果作者考虑非欧氏空间比如图(即graph，流形也是典型的非欧结构，这里作者只考虑图)，就难以选取固定的卷积核来适应整个图的不规则性，如邻居节点数量的不确定和节点顺序的不确定。

例如，社交网络非常适合用图数据来表达，如社交网络中节点以及节点与节点之间的关系，用户A（有ID信息等）、用户B、帖子都是节点，用户与用户之间的关系是关注，用户与帖子之间的关系可能是发布或者转发。通过这样一个图谱，可以分析用户对什么人、什么事感兴趣，进一步实现推荐机制。

总结一下，图数据中的空间特征具有以下特点：
1） 节点特征：每个节点有自己的特征；（体现在点上）
2） 结构特征：图数据中的每个节点具有结构特征，即节点与节点存在一定的联系。（体现在边上）
总地来说，图数据既要考虑节点信息，也要考虑结构信息，图卷积神经网络就可以自动化地既学习节点特征，又能学习节点与节点之间的关联信息。

综上所述，GCN是要为除CV、NLP之外的任务提供一种处理、研究的模型。
图卷积的核心思想是利用『边的信息』对『节点信息』进行『聚合』从而生成新的『节点表示』。

2. 图卷积网络的两种理解方式

GCN的本质目的就是用来提取拓扑图的空间特征。 而图卷积神经网络主要有两类，一类是基于空间域或顶点域vertex domain(spatial domain)的，另一类则是基于频域或谱域spectral domain的。通俗点解释，空域可以类比到直接在图片的像素点上进行卷积，而频域可以类比到对图片进行傅里叶变换后，再进行卷积。

所谓的两类其实就是从两个不同的角度理解，关于从空间角度的理解可以看本文的从空间角度理解GCN

2.1 vertex domain(spatial domain)：顶点域（空间域）

基于空域卷积的方法直接将卷积操作定义在每个结点的连接关系上，它跟传统的卷积神经网络中的卷积更相似一些。在这个类别中比较有代表性的方法有 Message Passing Neural Networks(MPNN)[1], GraphSage[2], Diffusion Convolution Neural Networks(DCNN)[3], PATCHY-SAN[4]等。

2.2 spectral domain：频域方法（谱方法）

这就是谱域图卷积网络的理论基础了。这种思路就是希望借助图谱的理论来实现拓扑图上的卷积操作。从整个研究的时间进程来看：首先研究GSP（graph signal processing）的学者定义了graph上的Fourier Transformation，进而定义了graph上的convolution，最后与深度学习结合提出了Graph Convolutional Network。

基于频域卷积的方法则从图信号处理起家，包括 Spectral CNN[5], Cheybyshev Spectral CNN(ChebNet)[6], 和 First order of ChebNet(1stChebNet)[7]　等

论文Semi-Supervised Classification with Graph Convolutional Networks就是一阶邻居的ChebNet

认真读到这里，脑海中应该会浮现出一系列问题：
Q1 什么是Spectral graph theory？
Spectral graph theory请参考维基百科的介绍，简单的概括就是借助于图的拉普拉斯矩阵的特征值和特征向量来研究图的性质

Q2 GCN为什么要利用Spectral graph theory？
这是论文（Semi-Supervised Classification with Graph Convolutional Networks）中的重点和难点，要理解这个问题需要大量的数学定义及推导

过程：
（1）定义graph上的Fourier Transformation傅里叶变换（利用Spectral graph theory，借助图的拉普拉斯矩阵的特征值和特征向量研究图的性质）
（2）定义graph上的convolution卷积

下面将介绍关于频谱域的图卷积网络的推导相关的内容。

3. 什么是拉普拉斯矩阵？

拉普拉斯矩阵(Laplacian matrix) 也叫做导纳矩阵、基尔霍夫矩阵或离散拉普拉斯算子，主要应用在图论中，作为一个图的矩阵表示。对于图 G=(V,E)，其Laplacian 矩阵的定义为 L=D-A，其中 L 是Laplacian 矩阵， D=diag(d)是顶点的度矩阵（对角矩阵）,d=rowSum(A)，对角线上元素依次为各个顶点的度， A 是图的邻接矩阵。

Graph Fourier Transformation及Graph Convolution的定义都用到图的拉普拉斯矩阵。

频域卷积的前提条件是图必须是无向图，只考虑无向图，那么L就是对称矩阵。

3.1 常用的几种拉普拉斯矩阵

普通形式的拉普拉斯矩阵

$$L=D-A$$
L中的元素给定为：
$$L_{i,j}=\{\begin{array}{ll}diag(v_i)& i=j\\ -1& i\ne jand{v}_{i}isadjacentto{v}_j\\ 0& otherwise\end{array}$$
其中diag(vi) 表示顶点 i 的度。

对称归一化的拉普拉斯矩阵（Symmetric normalized Laplacian）

$$L^{sys}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}$$
矩阵元素定义为：

$$L_{i,j}^{sys}=\{\begin{array}{ll}1& i=janddiag(v_i)\ne 0\\ -\frac{1}{\sqrt{diag(v_i)diag(v_j)}}& i\ne jand{v}_{i}isadjacentto{v}_j\\ 0& otherwise\end{array}$$

很多GCN的论文中应用的是这种拉普拉斯矩阵

随机游走归一化拉普拉斯矩阵（Random walk normalized Laplacian）

$$L^{rw}=D^{-1}L=I-D^{-1}A$$
矩阵元素定义为：

$$L_{i,j}^{rw}=\{\begin{array}{ll}1& i=janddiag(v_i)\ne 0\\ -\frac{1}{diag(v_i)}& i\ne jand{v}_{i}isadjacentto{v}_j\\ 0& otherwise\end{array}$$

泛化的拉普拉斯 (Generalized Laplacian)

泛化的拉普拉斯(用得少)定义为:

$$\{\begin{array}{ll}{Q}_{i,j}<0& i\ne janddiag(v_i)\ne 0\\ Q_{i,j}=0& i\ne jand{v}_{i}isadjacentto{v}_j\\ anynumber& otherwise\end{array}$$

一个拉普拉斯矩阵的计算例子（依据于上图）：

$$A=\left\{\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right\}，D=\left\{\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right\},L=D-A=\left\{\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right\}$$

$$D^{-1/2}=\left\{\begin{array}{cccccc}\frac{1}{\sqrt{2}}& 0& 0& 0& 0& 0\\ 0& \frac{1}{\sqrt{3}}& 0& 0& 0& 0\\ 0& 0& \frac{1}{\sqrt{2}}& 0& 0& 0\\ 0& 0& 0& \frac{1}{\sqrt{3}}& 0& 0\\ 0& 0& 0& 0& \frac{1}{\sqrt{3}}& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right\},L^{sys}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}A{D}^{-1/2}=\left\{\begin{array}{cccccc}1& -\frac{1}{\sqrt{6}}& 0& -\frac{1}{\sqrt{6}}& 0& 0\\ -\frac{1}{\sqrt{6}}& 1& -\frac{1}{\sqrt{6}}& 0& -\frac{1}{\sqrt{9}}& 0\\ 0& -\frac{1}{\sqrt{6}}& 1& -\frac{1}{\sqrt{6}}& 0& 0\\ -\frac{1}{\sqrt{6}}& 0& -\frac{1}{\sqrt{6}}& 1& -\frac{1}{\sqrt{9}}& -\frac{1}{\sqrt{3}}\\ 0& -\frac{1}{\sqrt{9}}& 0& -\frac{1}{\sqrt{9}}& 1& 0\\ 0& 0& 0& -\frac{1}{\sqrt{3}}& 0& 1\end{array}\right\}$$
可以看出，标准归一化的拉普拉斯矩阵还是对称的，并且符合前面的公式定义。

Graph Convolution与Diffusion相似之处，当然从Random walk normalized Laplacian就能看出了两者确有相似之处（其实两者只差一个相似矩阵的变换，可参考Diffusion-Convolutional Neural Networks)
其实维基本科对Laplacian matrix的定义上写得很清楚，国内的一些介绍中只有第一种定义。这让我在最初看文献的过程中感到一些的困惑，特意写下来，帮助大家避免再遇到类似的问题。

3.2 无向图的拉普拉斯矩阵有什么性质

（1）拉普拉斯矩阵是半正定矩阵。（最小特征值大于等于0）
（2）特征值中0出现的次数就是图连通区域的个数。
（3）最小特征值是0，因为拉普拉斯矩阵（普通形式：$L=D-A$）每一行的和均为0，并且最小特征值对应的特征向量是每个值全为1的向量；
（4）最小非零特征值是图的代数连通度。

拉普拉斯矩阵的半正定性证明,如下：
要证明拉普拉斯矩阵是半正定的，只需要证明其二次型$f^{T}Lf\ge 0$
证明：
$$\begin{array}{rl}{f}^{T}Lf& =f^{T}Df-f^{T}Af\\ & =f^T\ast diag(d)\ast f-f^{T}Af\\ & =\sum _{i=1}^m{d}_i{f}_i^2-\sum _{j=1}^m[\sum _{i=1}^m{f}_j\ast a_{ij}]f_j\\ & =\sum _{i=1}^m{d}_i{f}_i^2-\sum _{i,j=1}^m{f}_i\ast f_j\ast a_{ij}\\ & =\frac{1}{2}[\sum _{i=1}^m{d}_i{f}_i^2-2\sum _{i,j=1}^m{f}_i{f}_j{a}_{ij}+\sum _{j=1}^m{d}_j{f}_j^2]\\ & =\frac{1}{2}\sum _{i,j=1}^m{a}_{ij}(f_i-f_j{)}^2\end{array}$$

所以，对于任意一个属于实向量$f\in {\mathbb{R}}^m$(f为m∗1的实数列向量 )，都有此公式成立：

$$f^{T}Lf=\frac{1}{2}\sum _{i,j=1}^m{a}_{ij}(f_i-f_j{)}^2$$

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

• 拉普拉斯矩阵是对称矩阵，可以进行特征分解（谱分解）
• 由于卷积在傅里叶域的计算相对简单，为了在graph上做傅里叶变换，需要找到graph的连续的正交基对应于傅里叶变换的基，因此要使用拉普拉斯矩阵的特征向量。

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

GCN的核心基于拉普拉斯矩阵的谱分解，文献中对于这部分内容没有讲解太多，初学者可能会遇到不少误区，所以先了解一下特征分解。

特征分解（Eigendecomposition），又称谱分解（Spectral decomposition）是将矩阵分解为由其特征值和特征向量表示的矩阵之积的方法。只有对可对角化矩阵或有n个线性无关的特征向量的矩阵才可以施以特征分解。

不是所有的矩阵都可以特征分解，其充要条件为n阶方阵存在n个线性无关的特征向量。

但是拉普拉斯矩阵是半正定矩阵（半正定矩阵本身就是对称矩阵），有如下三个性质：

• 对称矩阵一定n个线性无关的特征向量
• 半正定矩阵的特征值一定非负
• 对阵矩阵的不同特征值对应的特征向量相互正交，这些正交的特征向量构成的矩阵为正交矩阵。

由上拉普拉斯矩阵对称知一定可以谱分解，且分解后有特殊的形式。

对于拉普拉斯矩阵其谱分解为：

$$L=U\Lambda U^{-1}=U\left[\begin{array}{ccc}{\lambda }_1& & \\ & \ddots & \\ & & {\lambda }_n\end{array}\right]U^{-1}$$
其中$U=(\overrightarrow{u_1},\overrightarrow{u_2},\cdots ,\overrightarrow{u_n})$，是列向量为单位特征向量的矩阵，也就说 $ \vec{u_l} $是列向量，Λ是n个特征值构成的对角阵。

由于 U 是正交矩阵，即$U{U}^T=E$,所以特征分解又可以写成：
$$L=U\Lambda U^{-1}=U\Lambda U^T$$
注意，特征分解最右边的是特征矩阵的逆，只是拉普拉斯矩阵是对称矩阵才可以写成特征矩阵的转置。

3.5 拉普拉斯算子

定义：拉普拉斯算子是n维欧几里德空间中的一个二阶微分算子，定义为梯度（$\nabla f$）的散度（$\nabla \cdot f$，即$\nabla f\cdot f$）。因此如果f是二阶可微的实函数，则f的拉普拉斯算子∆定义为：

$$∆f={\nabla }^{2}f=\nabla \cdot \nabla f$$
f的拉普拉斯算子也是笛卡尔坐标系xi中的所有非混合二阶偏导数：

$$∆f=\sum _{i=1}^n\frac{{\partial }^{2}f}{\partial x_i^2}$$
函数f的拉普拉斯算子也是该函数的海塞矩阵(是一个多元函数的二阶偏导数构成的方阵)的迹：
$$∆f=tr(H(f))$$

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

拉普拉斯矩阵也叫做离散的拉普拉斯算子。

4. 如何通俗易懂地理解卷积？

4.1 连续形式的一维卷积

在泛函分析中，卷积是通过两个函数f(x)和g(x)生成第三个函数的一种算子，它代表的意义是：两个函数中的一个(取g(x)，可以任意取)函数，把g(x)经过翻转平移,然后与f(x)的相乘，得到的一个新的函数，对这个函数积分，也就是对这个新的函数求它所围成的曲边梯形的面积。

设f(t),g(t)是两个可积函数，f(t)与g(t)的卷积记为$f(t)\ast g(t)$，它是其中一个函数翻转并平移后与另一个函数乘积的积分，是一个自变量是平移量的函数。也就是：

$$f(t)\ast g(t)={\int }_{-\infty }^{+\infty }f(\tau )g(t-\tau )d\tau ={\int }_{-\infty }^{+\infty }f(t-\tau )g(\tau )d\tau$$

4.2 离散形式的一维卷积

对于定义在整数$\mathbb{Z}$上的函数f,g,卷积定义为

$$(f\ast g)(t)={\sum }_{\tau =-\infty }^{\infty }f(\tau )g(t-\tau )$$

4.3 实例:掷骰子问题

光看数学定义可能会觉得非常抽象，下面举一个掷骰子的问题，该实例参考了知乎问题”如何通俗易懂地解释卷积”的回答。

想象现在有两个骰子，两个骰子分别是f跟g，f(1)表示骰子f向上一面为数字1的概率。同时抛掷这两个骰子1次，它们正面朝上数字和为4的概率是多少呢？相信读者很快就能想出它包含了三种情况，分别是：

• f向上为1，g向上为3；
• f向上为2，g向上为2；
• f向上为3，g向上为1；

最后这三种情况出现的概率和即问题的答案，如果写成公式，就是${\sum }_{\tau =1}^{3}f(\tau )g(4-\tau )$。可以形象地绘制成下图：

如果稍微扩展一点，比如说认为 f(0) 或者 g(0)等是可以取到的，只是它们的值为0而已。那么该公式可以写成${\sum }_{\tau =-\infty }^{\infty }f(\tau )g(4-\tau )$。仔细观察，这其实就是卷积(f∗g)(4)。如果将它写成内积的形式，卷积其实就是

$$[f(-\infty ),\cdots ,f(1),\cdots ,f(\infty )]\cdot [g(\infty ),\cdots ,g(3),\cdots ,g(-\infty )]$$

这么一看，是不是就对卷积的名字理解更深刻了呢? 所谓卷积，其实就是把一个函数卷(翻)过来，然后与另一个函数求内积。

对应到不同方面，卷积可以有不同的解释：g 既可以看作我们在深度学习里常说的核(Kernel)，也可以对应到信号处理中的滤波器(Filter)。而 f 可以是我们所说的机器学习中的特征(Feature)，也可以是信号处理中的信号(Signal)。f和g的卷积 (f∗g)就可以看作是对f的加权求和。下面两个动图就分别对应信号处理与深度学习中卷积操作的过程。

5. 傅里叶变换

5.1 连续形式的傅立叶变换

关于傅立叶变换相关的详细而有趣的内容，可以看这几篇文章：

• 如何直观地理解傅立叶变换？
• 如何理解傅立叶级数公式？ （强烈推荐看一看）
• 从傅立叶级数到傅立叶变换 （强烈推荐看一看）
• 如何理解拉普拉斯变换?

下面是一个大致流程：
任意函数可以分解为奇偶函数之和:
$$f(x)=\frac{f(x)+f(-x)}{2}+\frac{f(x)-f(-x)}{2}=f_{even}+f_{odd}$$

任意一个周期函数可以由若干个正交函数（由$sin,cos$ 构成）的线性组合构成，写出傅里叶级数的形式如下：
$$f(x)=a_0+\sum _{n=1}^{\infty }\left(a_{n}cos(\frac{2\pi n}{T}x)+b_{n}sin(\frac{2\pi n}{T}x)\right),a_0\in \mathbb{R}$$
利用欧拉公式$e^{ix}=\cos x+i\sin x$（这里的指复数中的i），$\cos x,\sin x$可表示成

$$\cos x=\frac{e^{ix}+e^{-ix}}{2},\sin x=\frac{e^{ix}-e^{-ix}}{2i}$$

在时间t轴上，把$e^{it}$向量的虚部（也就是纵坐标）记录下来，得到的就是$sin(t)$：

在时间t轴上，把$e^{i2t}$向量的虚部记录下来，得到的就是$sin(2t)$：

如果在时间t轴上，把$e^{it}$的实部（横坐标）记录下来，得到的就是$cos(t)$的曲线：

更一般的,具有两种看待$sin,cos$的角度：

$$e^{i\omega t}⟺\{\begin{array}{l}sin(\omega t)\\ cos(\omega t)\end{array}$$

这两种角度，一个可以观察到旋转的频率，所以称为频域；一个可以看到流逝的时间，所以称为时域：

所以，任意周期函数可以以$e^{i\omega t}$为基函数用傅里叶级数的指数形式表示。即，对于一个周期函数$f(x)$以傅里叶级数的指数形式表示为：
$$f(x)=\sum _{n=-\infty }^{\infty }\underset{\text{基的坐标}}{c_n}\cdot \underset{\text{正交基}}{e^{i\frac{2\pi nx}{T}}}$$
但是对于非周期函数，并不能用傅里叶级数的形式表示。但是还是用某个周期函数$f_T(x)$当$T\to \infty$来逼近，即${\lim }_{T\to \infty }{f}_T(x)=f(x)$，用积分的形式可以表示为：

$$f(x)={\int }_{-\infty }^{\infty }[{\int }_{-\infty }^{+\infty }f(x)e^{-i\omega x}dx]e^{i\omega x}d\omega ={\int }_{-\infty }^{\infty }F(\omega )e^{i\omega x}d\omega$$
其中，$F(\omega )$就是$f(x)$的连续形式的傅里叶变换：
$$F(\omega )=\mathcal{F}[f(x)]={\int }_{-\infty }^{+\infty }f(x)e^{-i\omega x}dx$$
可以看出，$f(x)$和$F(\omega )$可以通过指定的积分运算相互表达。

当然，也可以利用欧拉公式通过cos和sin函数表示为$F(u)$：

$$F(u)={\int }_{-\infty }^{+\infty }f(x)\left[cos(2\pi xu)-isin(2\pi xu)\right]dx$$

所以，对函数$f(x)$的傅里叶变换$\mathcal{F}$和傅里叶的逆变换${\mathcal{F}}^{-1}$记作：

$$F(\omega )=\mathcal{F}[f(x)],f(x)={\mathcal{F}}^{-1}[F(\omega )]$$

• $F(\omega )$叫做$f(x)$的象函数或傅里叶变换，即通过傅里叶变换后关于频率的函数，函数图像就是频谱图，$\omega$ 就是f对应在频域中的频率
• $f(x)$叫做$F(\omega )$的原象函数

其实可以发现这个对信号$f(x)$的傅立叶变换$F(\omega )$形式上是$f(x)$与基函数$e^{-i\omega x}$的积分，本质上将函数$f(x)$映射到了以$e^{-i\omega x}$为基向量的空间中。

5.2 频域（frequency domain）和时域（time domain）的理解

时域：真实量到的信号的时间轴，代表真实世界。

频域：为了做信号分析用的一种数学手段。

要理解时域和频域只需要看下面两张动图就可以了：

上图来自于维基百科，图中红色部分就是原函数f(x)在时域里面的曲线图，此函数经过傅里叶变换后可以分解成很多如右图中的曲线。在左图中的的蓝色线就是对应的频域中的频谱图。

频谱图里的竖线分别代表了不同频率的正弦波函数，也就是之前的基，而高度则代表在这个频率上的振幅，也就是这个基上的坐标分量。

很多在时域看似不可能做到的数学操作，在频域相反很容易。这就是需要傅里叶变换的地方。尤其是从某条曲线中去除一些特定的频率成分，这在工程上称为滤波，是信号处理最重要的概念之一，只有在频域才能轻松的做到。

看一个傅里叶变换去噪的例子：
在傅里叶变换前，图像上有一些规律的条纹，直接在原图上去掉条纹有点困难，但我们可以将图片通过傅里叶变换变到频谱图中，频谱图中那些规律的点就是原图中的背景条纹。

只要在频谱图中擦除这些点，就可以将背景条纹去掉，得到下图右侧的结果。

5.3 周期性离散傅里叶变换（Discrete Fourier Transform, DFT）

傅里叶变换有连续时间非周期傅里叶变换，连续时间周期性傅里叶变换，离散时间非周期傅里叶变换和离散时间周期性傅里叶变换，鉴于计算机主要处理离散周期性信号，本文主要介绍周期性离散时间傅里叶变换（DFT）。信号$x_n$的傅里叶变换$X_k$为

$$X_k=\sum _{n=0}^{N-1}{x}_n{e}^{-i\frac{2\pi }{N}kn}$$
信号$x_n$用其傅里叶变换$X_k$表示为：
$$x_n=\sum _{n=0}^{N-1}{X}_k{e}^{i\frac{2\pi }{N}kn}$$
其中

• N表示傅里叶变换的点数
• k表示傅里叶变换的第k个频谱

6. Graph上的傅里叶变换及卷积

把传统的傅里叶变换以及卷积迁移到Graph上来，核心工作其实就是把拉普拉斯算子的特征函数$e^{-i\omega t}$ 变为Graph对应的拉普拉斯矩阵的特征向量。

傅立叶变换与拉普拉斯矩阵的关系：传统傅立叶变换的基，就是拉普拉斯矩阵的一组特征向量。

6.1 图上的傅里叶变换

前面讲到可以用一组正交函数cos和sin(或$e^{-i\omega t}$ )表示任意函数，且傅里叶变换是连续形式的，在处理Graph时，用到的是傅里叶变换的离散形式。由于拉普拉斯矩阵进行谱分解以后，可以得到n个线性无关的特征向量，构成空间中的一组正交基，因此归一化拉普拉斯矩阵算子的特征向量构成了图傅里叶变换的基。图傅里叶变换将输入图的信号投影到了正交空间，相当于把图上定义的任意向量，表示成了拉普拉斯矩阵特征向量的线性组合。

离散积分就是一种内积形式，由此可以定义Graph上的傅里叶变换（实数域）：
$$F({\lambda }_l)=\hat{f}({\lambda }_l)=\sum _{i=1}^{N}f(i)u_l(i)$$

• $f$是Graph上的N维向量，可以表示某个点的特征向量，$f(i)$表示第$i$ 个特征
• $u_l(i)$表示第$l$ 个特征向量的第$i$ 个分量
• $f$的Graph 傅里叶变换就是与 ${\lambda }_l$ 对应的特征向量$u_l$进行内积运算
• $\lambda$就对应于$\omega$(具体解释见第7部分)
• $\hat{f}$表示$f$的傅里叶变换

6.2 图的傅立叶变换——图的傅立叶变换的矩阵形式

利用矩阵乘法将Graph上的傅里叶变换推广到矩阵形式：
$$\left(\begin{array}{c}\hat{f}({\lambda }_1)\\ \hat{f}({\lambda }_2)\\ ⋮\\ \hat{f}({\lambda }_N)\end{array}\right)=\left(\begin{array}{cccc}{u}_1(1)& u_1(2)& \dots & u_1(N)\\ u_2(1)& u_2(2)& \dots & u_2(N)\\ ⋮& ⋮& \ddots & ⋮\\ u_N(1)& u_N(2)& \dots & u_N(N)\end{array}\right)\left(\begin{array}{c}f(1)\\ f(2)\\ ⋮\\ f(N)\end{array}\right)$$
即$f$在Graph上傅里叶变换的矩阵形式为：

$$\hat{f}=U^{T}f(a)$$

6.3 图的傅立叶逆变换——图的傅立叶逆变换的矩阵形式

类似地，传统的傅里叶变换是对频率$\omega$ 求积分：

$${\mathcal{F}}^{-1}[F(\omega )]=\frac{1}{2\Pi }{\int }_{}^{}F(\omega )e^{i\omega t}d\omega$$

迁移到Graph上变为对特征值${\lambda }_l$求和：

$$f(i)=\sum _{l=1}^N\hat{f}({\lambda }_l)u_l(i)$$

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

$$\left(\begin{array}{c}f(1)\\ f(2)\\ ⋮\\ f(N)\end{array}\right)=\left(\begin{array}{cccc}{u}_1(1)& u_2(1)& \dots & u_N(1)\\ u_1(2)& u_1(2)& \dots & u_N(2)\\ ⋮& ⋮& \ddots & ⋮\\ u_1(N)& u_2(N)& \dots & u_N(N)\end{array}\right)\left(\begin{array}{c}\hat{f}({\lambda }_1)\\ \hat{f}({\lambda }_2)\\ ⋮\\ \hat{f}({\lambda }_N)\end{array}\right)$$

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

$$f=U\hat{f}(b)$$

6.4 图上的傅里叶变换推广到图卷积

在上面的基础上，利用卷积定理类比来将卷积运算，推广到Graph上。

卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积，即对于函数f与g两者的卷积是其函数傅立叶变换乘积的逆变换（中间的桥梁就是傅立叶变换与反傅立叶变换，证明见：https://zhuanlan.zhihu.com/p/54505069）：

f ∗ g = F − 1 { F ( f ) ⋅ F ( g ) } = F − 1 { f ^ ⋅ g ^ } f * g=\mathcal{F}^{-1}{\{\mathcal{F}(f) \cdot \mathcal{F}(g) \}}=\mathcal{F}^{-1}\{ \hat{f} \cdot \hat{g}\} f∗g=F−1{
F(f)⋅F(g)}=F−1{
f^​⋅g^​}
所以，对图上f和卷积核g的卷积可以表示为：
$$(f\ast g{)}_G=U((U^{T}g)\cdot (U^{T}f))$$
从上面可以看出，对卷积核$g$和$f$进行傅里叶变换的结果$U^{T}g,U^{T}f$都是一个列向量：

$$\left(\begin{array}{c}\hat{f}({\lambda }_1)\\ \hat{f}({\lambda }_2)\\ ⋮\\ \hat{f}({\lambda }_N)\end{array}\right)，\left(\begin{array}{c}f(1)\\ f(2)\\ ⋮\\ f(N)\end{array}\right)$$

所以，很多论文中的Graph卷积公式也写作：
$$(f\ast g{)}_G=U((U^{T}g)\odot (U^{T}f))$$
$\odot$ 表示hadamard product（哈达马积），对于两个向量，就是进行内积运算；对于维度相同的两个矩阵，就是对应元素的乘积运算。

如果把$U^{T}g$整体看作可学习的卷积核，这里我们把它写作$g_{\theta }$。最终图上的卷积公式即是：

$$(f\ast g{)}_G=U{g}_{\theta }{U}^{T}f$$
有的地方，还把$g_{\theta }=U^{T}g$也成对角矩阵的形式，即定义一个滤波$g_{\theta }=diag(U^{T}g)$，则：

$$f\ast g_{\theta }=U{g}_{\theta }{U}^{T}f=U\left(\begin{array}{ccc}\hat{g}({\lambda }_1)& & \\ & \ddots & \\ & & \hat{g}({\lambda }_n)\end{array}\right)U^{T}f$$

接下来第8节要介绍的图上频域卷积的工作，都是在$g_{\theta }$的基础上做文章。

7. 为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基？特征值表示频率？

在Chebyshev论文(M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,”in Advances in Neural Information Processing Systems, 2016)中就有说明，图上进行傅里叶变换时，拉普拉斯矩阵是对称矩阵，所有有n个线性无关的特征向量，因此可以构成傅里叶变换的一组基，而其对应的特征值就是傅里叶变换的频率。

7.1 为什么拉普拉斯矩阵的特征向量可以作为傅里叶变换的基？

傅里叶变换一个本质理解就是：把任意一个函数表示成了若干个正交函数（由sin,cos 构成）的线性组合。

通过即 f 在Graph上傅里叶逆变换的矩阵形式： $f=U\hat{f}(b)$也能看出，graph傅里叶变换把graph上定义的任意向量f，表示成了拉普拉斯矩阵特征向量的线性组合，即：

$$f=\hat{f}(1)u_1+\hat{f}(2)u_2+\cdots +\hat{f}(n)u_n$$

那么：为什么graph上任意的向量f都可以表示成这样的线性组合？

原因在于$(\overrightarrow{u_1},\overrightarrow{u_2},\cdots ,\overrightarrow{u_n})$是graph上 n维空间中的 n 个线性无关的正交向量（拉普拉斯矩阵是对称矩阵，必定可以进行特征分解，有n个线性无关的特征向量），由线性代数的知识可以知道：n 维空间中n 个线性无关的向量可以构成空间的一组基，而且拉普拉斯矩阵的特征向量还是一组正交基。

7.2 怎么理解拉普拉斯矩阵的特征值表示频率？

在graph空间上无法可视化展示“频率”这个概念，那么从特征方程上来抽象理解。

将拉普拉斯矩阵 L 的 n 个非负实特征值，从小到大排列为${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$，而且最小的特征值${\lambda }_1=0$，因为 n 维的全1向量对应的特征值为0（由 L 的定义就可以得出）：

$$L\left(\begin{array}{c}1\\ 1\\ ⋮\\ 1\end{array}\right)=0$$

从特征方程的数学理解来看：

$$Lu=\lambda u$$

在由Graph确定的 n 维空间中，越小的特征值 ${\lambda }_l$表明：拉普拉斯矩阵 L 其所对应的基$u_l$上的分量、“信息”越少，那么当然就是可以忽略的低频部分了。

其实图像压缩就是这个原理，把像素矩阵特征分解后，把小的特征值（低频部分）全部变成0，PCA降维也是同样的，把协方差矩阵特征分解后，按从大到小取出前K个特征值对应的特征向量作为新的“坐标轴”。

Graph Convolution的理论告一段落了，下面开始Graph Convolution Network

8. 深度学习中GCN的演变

Deep learning 中的Graph Convolution直接看上去会和第6节推导出的图卷积公式有很大的不同，但是万变不离其宗，都是根据下式来推导的：
$$g_{\theta }\ast x=U{g}_{\theta }{U}^{T}x=U\left(\begin{array}{ccc}\hat{g}({\lambda }_1)& & \\ & \ddots & \\ & & \hat{g}({\lambda }_n)\end{array}\right)U^{T}x$$

Deep learning 中的Convolution就是要设计含有trainable共享参数的kernel。

上式计算量很大，因为特征向量矩阵U 的复杂度是$O(N^2)$。此外，对于大型图来说，L特征值分解的计算量也很大。

基于上面最原始的卷积公式，深度学习中的GCN主要是从下面几篇文章演变而来的（引用次数都很高），后面一一进行简单介绍：

• 【1】Bruna, Joan, et al. “Spectral networks and locally connected networks on graphs.” 源于ICLR 2014（被引740次）
• 【2】Defferrard, Michaël, Xavier Bresson, and Pierre Vandergheynst. “Convolutional neural networks on graphs with fast localized spectral filtering.” 源于NIPS 2016（被引997次）
• 【3】Hammond, David K., Pierre Vandergheynst, and Rémi Gribonval. “Wavelets on graphs via spectral graph theory.” Applied and Computational Harmonic Analysis 30.2 (2011)（被引874次）
• 【4】Kipf, Thomas N., and Max Welling. “Semi-supervised classification with graph convolutional networks.” 源于ICML 2017 （被引1537次）

8.1 Spectral CNN

谱CNN源于论文(J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected networks on graphs,” in Proceedings of International Conference on Learning Representations, 2014)，Bruna等人，第一次提出谱卷积神经网络。他们简单地把$g_{\theta }$ 看作是一个可学习参数的集合：$g_{\theta }={\Theta }_{i,j}^k$。并且假设图信号是多维的，图卷积层顶定义为：

$$X_{:,j}^{k+1}=\sigma (\sum _{i=1}^{f_{k-1}}U{\Theta }_{i,j}^k{U}^T{X}_{:,i}^k)(j=1,2,\cdots ,f_k)$$

• $X^k\in {\mathbb{R}}^{N\times f_{k-1}}$是输入图信号,对应图上就是点的输入特征
• $N$是节点数量
• $f_{k-1}$是输入通道的数量
• $f_k$是输出通道的数量
• ${\Theta }_{i,j}^k$是一个可学习参数的对角矩阵,就跟三层神经网络中的weight一样是任意的参数，通过初始化赋值然后利用误差反向传播进行调整
• $\sigma (\cdot )$是激活函数

第一代的参数方法存在着一些弊端，主要在于：
（1）计算复杂：如果一个样本一个图，那么每个样本都需要进行图的拉普拉斯矩阵的特征分解求U矩阵计算复杂；每一次前向传播，都要计算$U,diag({\theta }_l)$及 $U^T$三者的乘积，特别是对于大规模的graph，计算的代价较高，需要$\mathcal{O}(n^2)$的计算复杂度
（2）是非局部性连接的
（3）卷积核需要N个参数，当图中的节点N很大时是不可取的

由于以上的缺点第二代的卷积核设计应运而生。

8.2 Chebyshev谱CNN（ChebNet）

Chebyshev谱CNN源于论文(M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,”in Advances in Neural Information Processing Systems, 2016)。Defferrard等人提出ChebNet，定义特征向量对角矩阵的切比雪夫多项式为滤波器，也就是

$$g_{\theta }=g_{\theta }(\Lambda )\approx \sum _{i=0}^{K-1}{\theta }_i{T}_k(\tilde{\Lambda })$$
其实，就是利用Chebyshev多项式拟合卷积核的方法，来降低计算复杂度。

推导过程如下：
考虑信号$x\in {\mathbb{R}}^N$（x就是graph上对应于每个顶点的feathure vector，即由数据集提取特征构成的向量，而不是和线性代数中常说的特征向量，注意区别）与以参数为 $\theta \in {\mathbb{R}}^N$的滤波器 $g_{\theta }=diag(\theta )$在傅里叶域的谱卷积。

$$g_{\theta }\ast x=U{g}_{\theta }{U}^{T}x(3)$$
其中

• U 是对称归一化的拉普拉斯(normalized graph Laplacian)算子$L=I_N-D^{-1/2}A{D}^{-1/2}=U\Lambda U^T$的特征向量矩阵，Λ是由L的特征值构成的对角矩阵。

$$\begin{array}{rl}L& =D^{-\frac{1}{2}}(D-A)D^{-\frac{1}{2}}\\ & =D^{-\frac{1}{2}}D{D}^{-\frac{1}{2}}-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\\ & =I_N-D^{-\frac{1}{2}}A{D}^{-\frac{1}{2}}\end{array}$$
由于normalized graph Laplacian矩阵L是实对称矩阵, 因此其特征向量矩阵U是正交矩阵,即$U{U}^T=I_N$

• $U^{T}x$是x的傅里叶变换。
• $g_{\theta }$是由参数θ构成的对角矩阵diag(θ)。由于参数θ的确定与L的特征值有关,作者认为$g_{\theta }$是特征值 Λ的一个函数，即令

$$g_{\theta }=g_{\theta }(\Lambda )$$

式3的计算量很大，因为特征向量矩阵U 的复杂度是$O(N^2)$。此外，对于大型图来说，L特征值分解的计算量也很大。
为了解决这个问题，Hammond et al.(2011) ：Wavelets on graphs via spectral graph theory指出$g_{\theta }(\Lambda )$可以很好的通过Chebyshev多项式$T_k(x)$ 的Kth-阶截断展开来拟合，并对Λ进行scale使其元素位于[−1,1]：

$$g_{\theta }(\Lambda )\approx \sum _{k=0}^K{\theta }_k{T}_K(\tilde{\Lambda })(4)$$
其中

• $\tilde{\Lambda }=2\Lambda /{\lambda }_{max}-I_N$(为缩放后的特征向量矩阵,缩放后范围是[−1,1]，单位矩阵的特征值是n重1)，缩放的目的是为了满足Chebyshev多项式$T_k(x)$ 的$K^{th}$ 阶截断展开的条件：自变量范围需要在[−1,1]之间
• ${\lambda }_{max}$是L 的最大特征值，也叫谱半径。
• $\theta \in {\mathbb{R}}^K$ 是切比雪夫系数的向量
• Chebyshev多项式递归定义为$T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$， 其中$T_0(x)=1，T_1(x)=x$ 。

回到对信号x与滤波器$g_{\theta }$的卷积的定义，现在有：

$$g_{\theta }\ast x=\sum _{k=0}^K{\theta }_k{T}_K(\tilde{L})x(5)$$
其中

• $\tilde{L}=2L/{\lambda }_{max}-I_N=U\tilde{\Lambda }{U}^T$
• 易证 $(U\Lambda U^T{)}^k=U{\Lambda }^k{U}^T$

现在，相比于第一种Spectral CNN：

• 此表达式现在是K-localized，具有局部连接性，因为它是拉普拉斯算子中的Kth-阶多项式，即它仅取决于离中央节点(Kth阶邻域)最大K步的节点
• $T_K(\tilde{L})x$的复杂度是O(|E|)，即与边数E呈线性关系，整个运算的复杂度是$O(K|E|)$。当graph是稀疏图的时候，计算加速尤为明显，这个时候复杂度远低于$O(n^2)$

---

公式4到公式5的补充证明如下：
（1）先用数学归纳法证明

$$U{T}_k(\tilde{\Lambda })U^T=T_k(U\tilde{\Lambda }{U}^T)$$
数学归纳法思路：当n=1时显然成立，假设n=k时成立，只需证n=k+1时成立

证明：
根据切比雪夫多项式的定义, 已知
$$\begin{array}{rl}& U{T}_0(\tilde{\Lambda })U^T=U{U}^T=1=T_0(U\tilde{\Lambda }{U}^T)\\ & U{T}_1(\tilde{\Lambda })U^T=U\tilde{\Lambda }{U}^T=T_1(U\tilde{\Lambda }{U}^T)\end{array}$$
假设对于任意k>1, 满足
$$U{T}_{k-2}(\tilde{\Lambda })U^T=T_{k-2}(U\tilde{\Lambda }{U}^T)$$
与

$$U{T}_{k-1}(\tilde{\Lambda })U^T=T_{k-1}(U\tilde{\Lambda }{U}^T)$$
则

$$\begin{array}{rl}U{T}_k(\tilde{\Lambda })U^T& =2U\tilde{\Lambda }{T}_{k-1}(\tilde{\Lambda })U^T-U{T}_{k-2}(\tilde{\Lambda })U^T\\ & =2(U\tilde{\Lambda }{U}^T)\left[U{T}_{k-1}(\tilde{\Lambda })U^T\right]-U{T}_{k-2}(\tilde{\Lambda })U^T\\ & =2(U\tilde{\Lambda }{U}^T)T_{k-1}(U\tilde{\Lambda }{U}^T)-T_{k-2}(U\tilde{\Lambda }{U}^T)\\ & =T_k(U\tilde{\Lambda }{U}^T)\end{array}$$
因此,根据数学归纳法, 证毕。

(2)已知

$$\tilde{L}=U\tilde{\Lambda }{U}^T$$

（3）将（1）、（2）两式带入卷积公式：

$$\begin{array}{rl}{g}_{\theta }\ast x& =U{g}_{\theta }{U}^{T}x\\ & =U{g}_{\theta }(\Lambda )U^{T}x\\ & =U(\sum _{k=0}^K{\theta }_k{T}_K(\tilde{\Lambda }))U^{T}x\\ & =(\sum _{k=0}^K{\theta }_k{T}_K(U\tilde{\Lambda }{U}^T))x\\ & =\sum _{k=0}^K{\theta }_k{T}_K(\tilde{L})x(5)\end{array}$$

---

8.3 CayleyNet

CayleyNet进一步应用了参数有理复合函数的Cayley多项式来捕获窄的频带。CayleyNet的谱图卷积定义为

$$\mathbf{x}\ast g_{\theta }=c_0\mathbf{x}+2\mathrm{Re}\left\{\sum _{j=1}^r{c}_j(h\mathbf{L}-i\mathbf{I}{)}^j(h\mathbf{L}+i\mathbf{I}{)}^{-j}\mathbf{x}\right\}$$
其中

• $Re(\cdot )$为复数的实部
• $c_0$为实数
• $c_j$为复数
• $i$为虚数
• $h4`为控制Cayley滤波器频谱的参数

CayleyNet在保留空间局部性的同时，说明ChebNet可以看作是CayleyNet的一个特例。

8.4 一阶ChebNet（1stChebNet）-GCN

一阶ChebNet源于论文（T. N. Kipf and M.Welling, “Semi-supervised classification with graph convolutional networks,” in Proceedings of the International Conference on Learning Representations, 2017）。这篇论文基于前面的工作，正式成为GCN的开山之作，后面很多变种都是基于这篇文章的。

该篇论文贡献有两点：

• 作者对于直接操作于图结构数据的网络模型根据频谱图卷积(Hammond等人于2011年提出的Wavelets on graphs via spectral graph theory)使用一阶近似简化计算的方法，提出了一种简单有效的层式传播方法。
• 作者验证了图结构神经网络模型可用于快速可扩展式的处理图数据中节点半监督分类问题，作者通过在一些公有数据集上验证了自己的方法的效率和准确率能够媲美现有的顶级半监督方法。

下面介绍ChebNet的一阶近似方法：
Kipf等人引入了一种一阶近似ChebNet。假设$K=1,{\lambda }_{max}=2$,则ChebNet卷积公式简化近似为：

$$x\ast g_{\theta }={\theta }_{0}x-{\theta }_1{D}^{-1/2}A{D}^{-1/2}x$$
为了抑制参数数量防止过拟合，1stChebNet假设$\theta ={\theta }_0=-{\theta }_1$,图卷积的定义就近似为（这是简单的一阶模型）：

$$g_{\theta }\ast x=\theta (I_N+D^{-1/2}A{D}^{-1/2})x$$
其中

• 而$I_N+D^{-1/2}A{D}^{-1/2}$是有范围[0,2]的特征值。因此，如果在深度神经网络模型中使用该算子，则反复应用该算子会导致数值不稳定（发散）和梯度爆炸/消失。

为了解决该问题, 引入了一个renormalization trick：
$$I_N+D^{-1/2}A{D}^{-1/2}\stackrel{\tilde{A}=A+I_N}{⟶}{\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$$
其中

• $\tilde{A}=A+I_N,{\tilde{D}}_{ii}={\sum }_j{\tilde{A}}_{ij}$，即图中加上自环

再加上一个激活函数，最后就可以得到了论文中的快速卷积公式：
$$H^{(l+1)}=f(H^l,A)=\sigma ({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{H}^{(l)}{W}^{(l)})$$

• $W$就是参数$\theta$参数矩阵

推广：特征映射公式
可以将这个定义推广到具有C个输入通道（即每个节点的C维特征向量）的信号$X\in {\mathbb{R}}^{N\times C}$和 F 个滤波器或特征映射如下：

$$Z={\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}X\Theta$$
其中

• $\Theta \in {\mathbb{R}}^{C\times F}$ 是一个滤波器参数矩阵，其实就是参数矩阵W
• $Z\in {\mathbb{R}}^{N\times F}$ 是一次卷积的输出矩阵。

这个滤波操作复杂度是 $O（|E|FC）$（其中E为边数，C为特征向量维度，F为卷积核数量），并且$\tilde{A}X$ `可以有效地实现为密集矩阵和稀疏矩阵的乘积。（在源代码中使用了稀疏矩阵和稠密矩阵乘法）

带一阶滤波器的多层图卷积网络（GCN）的结构图如下图所示。

Input：Feature matrix $X\in {\mathbb{R}}^{N\times D}$,preprocessed adjacency matrix $\tilde{A}$

在看了上面的公式以及论文中的训练方法之后，并没有觉得GCN有多么特别，无非就是一个设计巧妙的公式，也许不用这么复杂的公式，多加一点训练数据或者把模型做深，也可能达到媲美的效果呢。

最后论文的附录里提到“even an untrained GCN model with random weights can serve as a powerful feature extractor for nodes in a graph”，可见即使不训练，完全使用随机初始化的参数W，GCN提取出来的特征就已经十分优秀了！这跟CNN不训练是完全不一样的，CNN不训练是根本得不到什么有效特征的。

然后作者做了一个实验，使用一个俱乐部会员的关系网络，使用随机初始化的GCN进行特征提取，得到各个node的embedding，然后可视化：

可以发现，在原数据中同类别的node，经过GCN的提取出的embedding，已经在空间上自动聚类了。

而这种聚类结果，可以和DeepWalk、node2vec这种经过复杂训练得到的node embedding的效果媲美了。

作者接着给每一类的node，提供仅仅一个标注样本，然后去训练，得到的可视化效果如下：

关于1stChebNet CGN的更多细节，可以参考博客：
Semi-Supervised Classification with Graph Convolutional Networks用图卷积进行半监督分类

GCN的优点

1)、权值共享，参数共享，从$AXW$可以看出每一个节点的参数矩阵都是W，权值共享；
2)、具有局部性Local Connectivity，也就是局部连接的，因为每次聚合的只是一阶邻居；
上述两个特征也是CNN中进行参数减少的核心思想
3)、感受野正比于卷积层层数，第一层的节点只包含与直接相邻节点有关的信息，第二层以后，每个节点还包含相邻节点的相邻节点的信息，这样的话，参与运算的信息就会变多。层数越多，感受野越大，参与运算的信息量越充分。也就是说随着卷积层的增加，从远处邻居的信息也会逐渐聚集过来。
4)、复杂度大大降低，不用再计算拉普拉斯矩阵，特征分解

GCN的不足

1)、扩展性差：由于训练时需要需要知道关于训练节点、测试节点在内的所有节点的邻接矩阵$A$，因此是transductive的，不能处理大图，然而工程实践中几乎面临的都是大图问题，因此在扩展性问题上局限很大，为了解决transductive的的问题，GraphSAGE：Inductive Representation Learning on Large Graphs 被提出；
2)、局限于浅层：GCN论文中表明，目前GCN只局限于浅层，实验中使用2层GCN效果最好，为了加深，需要使用残差连接等trick，但是即使使用了这些trick，也只能勉强保存性能不下降，并没有提高，Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning一文也针对When GCNs Fail ？这个问题进行了分析。虽然有一篇论文：DeepGCNs-Can GCNs Go as Deep as CNNs?就是解决GCN局限于浅层的这个问题的，但个人觉得并没有解决实质性的问题，这方面还有值得研究的空间。
3)、不能处理有图：理由很简单，推导过程中用到拉普拉斯矩阵的特征分解需要满足拉普拉斯矩阵是对称矩阵的条件；

9. GCN的一些改进

9.1 邻接矩阵的探索

Adaptive Graph Convolution Network (AGCN)

自适应GCN(AGCN)为了探索图拉普拉斯矩阵为指明的隐藏结构，(R. Li, S. Wang, F. Zhu, and J. Huang, “Adaptive graph convolutional neural networks,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2018）提出了自适应图卷积网络(AGCN)。AGCN利用所谓的残差图来扩充图，残差图是通过计算节点对的距离来构造的。尽管AGCN能够捕获互补关系信息，但是以$O(N^2)$的计算量为代价。自适应图卷积网络(AGCN)通过图的邻接矩阵学习未知的隐藏结构关系。它通过一个以两个节点的特征为输入的可学习的距离函数来构造一个所谓的残差图邻接矩阵。

Dual Graph Convolutional Network(DGCN)

对偶图卷积网络(DGCN)引入了一种对偶图卷积结构，该结构具有两个并行的图卷积层。虽然这些对偶层共享参数,他们使用归一化了的邻接矩阵Ā和归一化了的积极点态互信息(PPMI)的共生矩阵提取节点随机游走。DGCN通过对偶图卷积层的集成输出，无需叠加多个图卷积层即可捕获局部和全局结构信息。

9.2 空间域的GCNs（ConvGNNs）

Neural Network for Graphs (NN4G)

NN4G是第一个提出的基于空间的ConvGNNs。NN4G通过直接累加节点的邻域信息来实现图的卷积。它还应用剩余连接和跳跃连接来记忆每一层的信息。因此，NN4G的下一层节点状态为

$${\mathbf{h}}_v^{(k)}=f\left({\mathbf{x}}_v{\mathbf{W}}^{(k-1)}+\sum _{i=1}^{k-1}\sum _{u\in N(v)}{\mathbf{h}}_u^{(k-1)}{\Theta }^{(k-1)}\right)$$

• $f(\cdot )是激活函数$
• ${\mathbf{h}}_v^{(0)}=0$

上式也可以写出矩阵的形式

$${\mathbf{H}}^{(k)}=f\left(\mathbf{X}{\mathbf{W}}^{(k-1)}+\sum _{i=1}^{k-1}\mathbf{A}{\mathbf{H}}^{(k-1)}{\Theta }^{(k-1)}\right)$$
可以看出，形式和GCN类似。主要区别在于NN4G使用了非标准化邻接矩阵，这可能会导致数值不稳定问题。

Contextual Graph Markov Model (CGMM)

CGMM提出了一种基于NN4G的概率模型。在保持空间局部性的同时，CGMM还具有概率可解释性。

Diffusion Convolutional Neural Network (DCNN)扩散卷积神经网络

DCNN将图卷积看作一个扩散过程。它假设信息以一定的转移概率从一个节点转移到相邻的一个节点，使信息分布在几轮后达到均衡。DCNN将扩散图卷积定义为

$${\mathbf{H}}^{(k)}=f\left({\mathbf{w}}^{(k)}\odot {\mathbf{P}}^k\mathbf{X}\right)$$

• $f(\cdot )是激活函数$
• 概率转移矩阵$\mathbf{P}\in {\mathbf{R}}^{n\times n}$通过$\mathbf{P}={\mathbf{D}}^{-1}\mathbf{A}$来计算
• 在DCNN中，隐含表示矩阵${\mathbf{H}}^{(k)}$和输入特征矩阵$\mathbf{X}$具有相同的维度，不是前一层隐含表示矩阵${\mathbf{H}}^{(k-1)}$的函数
• DCNN将${\mathbf{H}}^{(1)},{\mathbf{H}}^{(2)},\cdots ,{\mathbf{H}}^{(K)}$连接起来最为模型最后的输出

Diffusion Graph Convolution(DGC) 扩散图卷积

由于DCNN扩散过程的平稳分布是概率转移矩阵的幂级数的总和，因此扩散图卷积(Diffusion Graph Convolution, DGC)将每个扩散步骤的输出相加，而不是拼接。它定义扩散图卷积为

$$\mathbf{H}=\sum _{k=0}^{K}f\left({\mathbf{P}}^k\mathbf{X}{\mathbf{W}}^{(k)}\right)$$

• $f(\cdot )是激活函数$
• ${\mathbf{W}}^{(k)}\in {\mathbf{R}}^{D\times F}$

利用转移概率矩阵的幂意味着，遥远的邻居对中心节点提供的信息非常少。

PGC-DGCNN

PGC-DGCNN（On filter size in graph convolutional networks ，SSCI 2018）增加了基于最短路径的远距离邻居的贡献。它定义了一个最短路径邻接矩阵${\mathbf{S}}^{(j)}$。如果从节点$v$到节点$u$的最短路径长度为$j$，则${\mathbf{S}}_{v,u}^{(j)}=1$，否则为0。PGC-DGCNN使用超参数$r$控制感受域的大小，引入了一个图卷积操作，如下所示

$${\mathbf{H}}^{(k)}={\Vert }_{j=0}^{r}f\left({\left({\tilde{\mathbf{D}}}^{(j)}\right)}^{-1}{\mathbf{S}}^{(j)}{\mathbf{H}}^{(k-1)}{\mathbf{W}}^{(j,k-1)}\right)$$

• ${\tilde{D}}_{ii}^{(j)}={\sum }_l{S}_{i,l}^{(j)},{\mathbf{H}}^{(0)}=\mathbf{X}$
• $||$表示两向量连接操作

计算最短路径邻接矩阵的代价可能很高，最大可能为$O(n^3)$

Partition Graph Convolution (PGC)

PGC（Spatial temporal graph convolutional networks for skeleton-based action recognition，AAAI 2018）根据不局限于最短路径的特定条件将一个节点的邻居划分为$Q$组。PGC根据每个组定义的邻域构造$Q$邻接矩阵。然后，PGC将不同参数矩阵的GCN应用到每个邻居组，并将结果进行求和:

$${\mathbf{H}}^{(k)}=\sum _{j=1}^Q{\overline{\mathbf{A}}}^{(j)}{\mathbf{H}}^{(k-1)}{\mathbf{W}}^{(j,k-1)}$$

• ${\mathbf{H}}^{(0)}=\mathbf{X},{\overline{\mathbf{A}}}^{(j)}={\left({\tilde{\mathbf{D}}}^{(j)}\right)}^{-\frac{1}{2}}{\tilde{\mathbf{A}}}^{(j)}{\left({\tilde{\mathbf{D}}}^{(j)}\right)}^{-\frac{1}{2}}$
• $\tilde{\mathbf{A}}={\mathbf{A}}^{(j)}+\mathbf{I}$

Message Passing Neural Networks (MPNN) 信息传递神经网络

信息传递神经网络(MPNNs)(Neural message passing for quantum chemistry,ICML 2017)概述了基于空间的卷积神经网络的一般框架。它把图卷积看作一个信息传递过程，信息可以沿着边直接从一个节点传递到另一个节点。MPNN运行K-step消息传递迭代，让信息进一步传播。定义消息传递函数(即空间图卷积)为

$${\mathbf{h}}_v^{(k)}=U_k\left({\mathbf{h}}_v^{(k-1)},\sum _{u\in N(v)}{M}_k\left({\mathbf{h}}_v^{(k-1)},{\mathbf{h}}_u^{(k-1)},{\mathbf{x}}_{vu}^e\right)\right)$$

• ${\mathbf{h}}_v^{(0)}={\mathbf{x}}_v$
• $U_k(\cdot )$和$M_k(\cdot )$是有参数的函数

在得到每个节点的隐含表示后，可以将${\mathbf{h}}_v^{(k)}$传递给输出层来执行节点级的预测任务，或者传递给readout函数来执行图级的预测任务。readout函数基于节点隐含表示生成整个图的表示。它通常被定义为

$${\mathbf{h}}_G=R\left({\mathbf{h}}_v^{(K)}|v\in G\right)$$

• $R(\cdot )$表示有参数的readout函数

通过假设$U_k(\cdot )$、$M_k(\cdot )$、$R(\cdot )$的不同形式，如GCN、（Convolutional networks on graphs for learning molecular fingerprints，NIPS 2015）、（Molecular graph convolutions: moving beyond fingerprints，2016）、（Quantum-chemical insights from deep tensor neural networks，2017 Nature communications）等，MPNN可以覆盖很多现有的GNN。

Graph Isomorphism Network (GIN) 图同构网络

然而，图同构网络(GIN)发现，MPNN框架下的方法不能根据生成的图embedding来区分不同的图结构。为了修正这个缺点，GIN通过一个可学习的参数${ϵ}^{(k)}$调整中心节点的权重。它通过下式来计算图卷积

$${\mathbf{h}}_v^{(k)}=\sigma \left(\left(1+{ϵ}^{(k)}\right){\mathbf{h}}_v^{(k-1)}+\sum _{u\in N(v)}{\mathbf{h}}_u^{(k-1)}{\mathbf{W}}^{(k-1)}\right)$$

GraphSage

由于一个节点的邻居数量可能从1个到1000个甚至更多，因此获取一个节点邻居的完整大小是低效的。GraphSage(Inductive representation learning on large graphs，NIPS 2017)引入聚合函数的概念定义图形卷积。聚合函数本质上是聚合节点的邻域信息，需要满足对节点顺序的排列保持不变，例如均值函数，求和函数，最大值函数都对节点的顺序没有要求。图的卷积运算定义为:

$${\mathbf{h}}_v^{(k)}=\sigma \left({\mathbf{W}}^{(k)}\cdot f_k\left({\mathbf{h}}_v^{(k-1)},\left\{{\mathbf{h}}_u^{(k-1)},\forall u\in S_{\mathcal{N}(v)}\right\}\right)\right)$$

• ${\mathbf{h}}_v^{(0)}={\mathbf{x}}_v$
• $f_k(\cdot )$是一个聚合函数，聚合函数应该不受节点排序(如均值、和或最大值)的影响
• $S_{\mathcal{N}(v)}$表示节点$v$的邻居的一个随机采样

GraphSage没有更新所有节点上的状态，而是提出了一种batch训练算法，提高了大型图的可扩展性。GraphSage的学习过程分为三个步骤。首先，对一个节点的K-跳邻居节点取样，然后，通过聚合其邻居节的信息表示中心节点的最终状态，最后，利用中心节点的最终状态做预测和误差反向传播。如图所示k-hop,从中心节点跳几步到达的顶点。

假设在第t-hop取样的邻居个数是$s_t$，GraphSage一个batch的时间复杂度是$O({\prod }_{t=1}^T{s}_t)$。因此随着$t$的增加计算量呈指数增加，这限制了GraphSage朝深入的框架发展。但是实践中，作者发现$t=2$已经能够获得很高的性能。

Graph Attention Network (GAT)图注意力网络

图注意网络(GAT)(ICLR 2017,Graph attention networks)假设相邻节点对中心节点的贡献既不像GraphSage一样相同，也不像GCN那样预先确定(这种差异如图4所示)。GAT在聚合节点的邻居信息的时候使用注意力机制确定每个邻居节点对中心节点的重要性，也就是权重。定义图卷积操作如下：

$${\mathbf{h}}_v^{(k)}=\sigma \left(\sum _{u\in \mathcal{N}(v)\cup v}{\alpha }_{vu}{\mathbf{W}}^{(k-1)}{\mathbf{h}}_u^{(k-1)}\right)$$

• ${\mathbf{h}}_v^{(0)}={\mathbf{x}}_v$

${\alpha }_{vu}$表示节点$v$和它的邻居节点$u$之间的连接的权重，通过下式计算

$${\alpha }_{vu}=\mathrm{softmax}\left(g\left({\mathbf{a}}^T\left[{\mathbf{W}}^{(k-1)}{\mathbf{h}}_v\Vert {\mathbf{W}}^{(k-1)}{\mathbf{h}}_u\right]\right)\right)$$

• $g(\cdot )$是一个LeakReLU激活函数
• $\mathbf{a}$是一个可学习的参数向量

softmax函数确保节点$v$的所有邻居的注意权值之和为1。GAT进一步使用multi-head注意力方式，并使用||concat方式对不同注意力节点进行整合，提高了模型的表达能力。这表明在节点分类任务上比GraphSage有了显著的改进。

图4展示了GCN和GAN在聚合邻居节点信息时候的不同。

• （a）图卷积网络GCN(2017,Semi-supervised classification with graph convolutional networks)在聚集过程中很清楚地分配了一个非参数的权重$a_{ij}=\frac{1}{\sqrt{deg(v_i)deg(v_j)}}$给$v_i$的邻居$v_j$
• （b）图注意力网络GAT(ICLR 2017,Graph attention networks)通过端到端的神经网络结构隐式地捕获$a_{ij}$的权重，以便更重要的节点获得更大的权重。

Gated Attention Network (GAAN)-门控注意力网络

GAAN(Gaan:Gated attention networks for learning on large and spatiotemporal graphs,2018)也利用multi-head注意力的方式更新节点的隐层状态。与GAT为各种注意力设置相同的权重进行整合的方式不同，GAAN引入self-attention机制对每一个head，也就是每一种注意力，计算不同的权重，规则如下:

$$h_i^t={\varphi }_o(x_i\oplus {\Vert }_{k=1}^K{g}_i^k\sum _{j\in N_i}{\alpha }_k(h_i^{t-1},h_j^{t-1}){\varphi }_v(h_j^{t-1}))$$
其中，${\varphi }_o(\cdot )$和${\varphi }_v(\cdot )$表示前馈神经网络，$g_i^k$表示第$k$个注意力head的权重。

GeniePath除了在空间上应用了图注意力之外，还提出了一种类似于LSTM的门控机制来控制跨图卷积层的信息流。还有其他一些有趣的图注意模型（Graph classification using structural attention，KDD 18）、（Watch your step: Learning node embeddings via graph attention，NeurIPS,2018）。但是，它们不属于ConvGNN框架。

Mixture Model Network (MoNet)

混合模型网络MoNet(Geometric deep learning on graphs and manifolds using mixture model cnns ,CVPR 2017)采用了一种不同的方法来为一个节点的邻居分配不同的权值。它引入节点伪坐标来确定一个节点与其邻居之间的相对位置。一旦知道了两个节点之间的相对位置，权重函数就会将相对位置映射到这两个节点之间的相对权重。通过这种方式，可以在不同的位置共享图数据过滤器的参数。在MoNet框架下，现有的几种流形处理方法，如Geodesic CNN (GCNN)、Anisotropic CNN (各向异性CNN，ACNN)、Spline CNN，以及针对图的处理方法GCN、DCNN等，都可以通过构造非参数权函数将其推广为MoNet的特殊实例。此外，MoNet还提出了一个具有可学习参数的高斯核函数来自适应地学习权值函数。

PATCHY-SAN

另一种不同的工作方式是根据特定的标准对节点的邻居进行排序，并将每个排序与一个可学习的权重关联起来，从而实现跨不同位置的权重共享。PATCHY-SAN(Learning convolutional neural networks for graphs，ICML 2016)根据每个节点的图标签对邻居排序，并选择最上面的q个邻居。图标记实质上是节点得分，可以通过节点度、中心度、Weisfeiler-Lehman颜色等得到。由于每个节点现在有固定数量的有序邻居，因此可以将图形结构的数据转换为网格结构的数据。PATCHY-SAN应用了一个标准的一维卷积滤波器来聚合邻域特征信息，其中该滤波器的权值的顺序对应于一个节点的邻居的顺序。PATCHY-SAN的排序准则只考虑图的结构，这就需要大量的计算来处理数据。GCNs中利用标准CNN能过保持平移不变性，仅依赖于排序函数。因此，节点选择和排序的标准至关重要。PATCHY-SAN中，排序是基于图标记的，但是图标记值考虑了图结构，忽略了节点的特征信息。

Large-scale Graph Convolution Networks (LGCN)

LGCN(Large-scale learnable graph convolutional networks,SIGKDD 2018)提出了一种基于节点特征信息对节点的邻居进行排序的方法。对于每个节点，LGCN集成其邻居节点的特征矩阵，并沿着特征矩阵的每一列进行排序，排序后的特征矩阵的前k行作为目标节点的输入网格数据。最后LGCN对合成输入进行1D-CNN得到目标节点的隐含输入。PATCHY-SAN中得到图标记需要复杂的预处理，但是LGCN不需要，所以更高效。LGCN提出一个子图训练策略以适应于大规模图场景，做法是将采样的小图作为mini-batch。

GraphSAGE

通常GCN这样的训练函数需要将整个图数据和所有节点中间状态保存到内存中。特别是当一个图包含数百万个节点时，针对ConvGNNs的full-batch训练算法受到内存溢出问题的严重影响。为了节省内存，GraphSage提出了一种batch训练算法。它将节点看作一棵树的根节点，然后通过递归地进行K步邻域扩展，扩展时保持采样大小固定不变。对于每一棵采样树，GraphSage通过从下到上的层次聚集隐含节点表示来计算根节点的隐含表示。

FastGCN

FastGCN（fast learning with graph convolutional networks via importance sampling，ICLR 2018）对每个图卷积层采样固定数量的节点，而不是像GraphSage那样对每个节点采样固定数量的邻居。它将图卷积理解为节点embedding函数在概率测度下的积分变换。采用蒙特卡罗近似和方差减少技术来简化训练过程。由于FastGCN对每个层独立地采样节点，层之间的连接可能是稀疏的。

AS-GCN

AS-GCN（Adaptive Sampling Towards Fast Graph Representation Learning，NeurIPS 2018）提出了一种自适应分层采样方法，其中下层的节点根据上层节点为条件进行采样。与FastGCN相比，该方法以采用更复杂的采样方案为代价，获得了更高的精度。

StoGCN（或VR-GCN）

StoGCN（Stochastic training of graph convolutional networks with variance reduction，VR-GCN，ICML 2018）的随机训练使用历史节点表示作为控制变量，将图卷积的感知域大小降低到任意小的范围。即使每个节点有两个邻居，StoGCN的性能也不相上下。但是，StoGCN仍然必须保存所有节点中间状态，这对于大型图数据来说是消耗内存的。

注：VR-GCN是ClusterGCN中的叫法。

Cluster-GCN

Cluster-GCN使用图聚类算法对一个子图进行采样，并对采样的子图中的节点执行图卷积。由于邻域搜索也被限制在采样的子图中，所以Cluster-GCN能够同时处理更大的图和使用更深层次的体系结构，用更少的时间和更少的内存。值得注意的是，Cluster-GCN为现有的ConvGNN训练算法提供了时间复杂度和内存复杂度的直接比较。

复杂度对比

下表是ConvGNN训练算法时间和内存复杂度的对比，GCN是进行full-batch训练的baseline方法。GraphSage以牺牲时间效率为代价来节省内存。同时，随着$K$和$r$的增加，GraphSage的时间复杂度和内存复杂度呈指数增长，其中，Sto-GCN的时间复杂度最高，内存瓶颈仍然没有解决。然而，Sto-GCN可以用非常小的$r$实现令人满意的性能。由于没有引入冗余计算，因此Cluster-GCN的时间复杂度与baseline方法相同。在所有的方法中，Cluster-GCN实现了最低的内存复杂度。

Complexity	GCN	GraphSage	FastGCN	StoGCN	Cluster-GCN
Time	$O\left(Kmd+Kn{d}^2\right)$	$O\left(r^{K}n{d}^2\right)$	$O\left(Krn{d}^2\right)$	$O\left(Kmd+Kn{d}^2+r^{K}n{d}^2\right)$	$O\left(Kmd+Kn{d}^2\right)$
Memory	$O\left(Knd+K{d}^2\right)$	$O\left(s{r}^{K}d+K{d}^2\right)$	$O\left(Ksrd+K{d}^2\right)$	$O\left(Knd+K{d}^2\right)$	$O\left(Ksd+K{d}^2\right)$

• $n$是所有节点的数量
• $m$是所有边的数量
• $K$是网络层数
• $s$是batch size
• $r$是每一个节点采样的邻居的数量
• 为简单起见，节点隐含特征的维数保持不变，用$d$表示

10. GCN的一些应用

11. GCN代码分析和数据集Cora、Pubmed、Citeseer格式

篇幅较长，数据集格式，见另下一篇：GCN使用的数据集Cora、Citeseer、Pubmed、Tox21格式

篇幅较长，代码分析见另一篇：图卷积网络GCN代码分析（Tensorflow版）

12. 从空间角度理解GCN

前面介绍了GCN谱方法的推导以及背后的思路等，这是一种比较严谨和理论的方法。但是，其实可以发现，在傅立叶域上定义出来的GCN操作，其实也可以在空间域上进行理解，其就是所谓的消息传递机制，或者说每次从邻居中聚集信息然后对中心节点进行更新。

如下图所示，红色节点S1的邻居正是蓝色节点B1,B2,B3，这些邻居节点根据一定的规则将信息，也就是特征，汇总到红色节点上。

通常来说，会加入一个线性变换矩阵W，以作为汇聚节点特征的特征维度转换（或者说是映射），于是有

$$\sum _{u\in \mathcal{N}(v)}{H}^{(l)}(u))W^{(l)}$$
加入激活函数后有:

$$\sigma (\sum _{u\in \mathcal{N}(v)}{H}^{(l)}(u))W^{(l)})$$
上式用更为紧致的矩阵形式表达：

$$H^{(l+1)}=(H^{(l)},A)=\sigma (A{H}^{(l)}{W}^{(l)})$$
不难发现，其实HW的结果乘上邻接矩阵A的目的其实在于选在一阶邻居节点，其实本质就是在于邻居节点的信息传递。但是上式还可以进行一些改进，比如信息聚合时没有考虑节点自己的信息，因此可以在图中加入一个自环，邻接矩阵变为

$$\tilde{A}=A+I_N$$
度矩阵变为

$${\tilde{D}}_{ii}=\sum _j{\tilde{A}}_{ij}$$
为了标准化（或归一化）邻接矩阵A使得每行之和为1，可以令：

$$\tilde{A}={\tilde{D}}^{-1}\tilde{A}$$

这样就行归一化以后，对邻居的聚合就不是求和了而是求平均值。

还是考虑此图

$$A=\left\{\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right\}，D=\left\{\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right\}$$

$$\tilde{A}=A+I_N=\left\{\begin{array}{cccccc}1& 1& 0& 0& 1& 0\\ 1& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 0& 1\end{array}\right\}，\tilde{D}=\sum _j{\tilde{A}}_{ij}=D+I_N=\left\{\begin{array}{cccccc}3& 0& 0& 0& 0& 0\\ 0& 4& 0& 0& 0& 0\\ 0& 0& 3& 0& 0& 0\\ 0& 0& 0& 4& 0& 0\\ 0& 0& 0& 0& 4& 0\\ 0& 0& 0& 0& 0& 2\end{array}\right\}$$
则归一化以后为

$${\tilde{D}}^{-1}\tilde{A}=\left\{\begin{array}{cccccc}1/3& 0& 0& 0& 0& 0\\ 0& 1/4& 0& 0& 0& 0\\ 0& 0& 1/3& 0& 0& 0\\ 0& 0& 0& 1/4& 0& 0\\ 0& 0& 0& 0& 1/4& 0\\ 0& 0& 0& 0& 0& 1/2\end{array}\right\}\cdot \left\{\begin{array}{cccccc}1& 1& 0& 0& 1& 0\\ 1& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 0& 1\end{array}\right\}=\left\{\begin{array}{cccccc}1/3& 1/3& 0& 0& 1/3& 0\\ 1/4& 1/4& 1/4& 0& 1/4& 0\\ 0& 1/3& 1/3& 1/3& 0& 0\\ 0& 0& 1/4& 1/4& 1/4& 1/4\\ 1/4& 1/4& 0& 1/4& 1/4& 0\\ 0& 0& 0& 1/2& 0& 1/2\end{array}\right\}$$

上式对邻接矩阵进行了标准化，这个标准化称之为random walk normalization。然而，在实际中，动态特性更为重要，因此经常使用的是renormalization（GCN论文中的叫法）：

$$\tilde{A}={\tilde{D}}^{-1/2}\tilde{A}{D}^{-1/2}$$

$${\tilde{D}}^{-1/2}=\left\{\begin{array}{cccccc}\frac{1}{\sqrt{3}}& 0& 0& 0& 0& 0\\ 0& \frac{1}{\sqrt{4}}& 0& 0& 0& 0\\ 0& 0& \frac{1}{\sqrt{3}}& 0& 0& 0\\ 0& 0& 0& \frac{1}{\sqrt{4}}& 0& 0\\ 0& 0& 0& 0& \frac{1}{\sqrt{4}}& 0\\ 0& 0& 0& 0& 0& \frac{1}{\sqrt{2}}\end{array}\right\}$$

$$\begin{gathered} \tilde{A}={\tilde{D}}^{-1/2}\tilde{A}{D}^{-1/2}=\left\{\begin{array}{cccccc}\frac{1}{\sqrt{3}}& 0& 0& 0& 0& 0\\ 0& \frac{1}{\sqrt{4}}& 0& 0& 0& 0\\ 0& 0& \frac{1}{\sqrt{3}}& 0& 0& 0\\ 0& 0& 0& \frac{1}{\sqrt{4}}& 0& 0\\ 0& 0& 0& 0& \frac{1}{\sqrt{4}}& 0\\ 0& 0& 0& 0& 0& \frac{1}{\sqrt{2}}\end{array}\right\}\cdot \left\{\begin{array}{cccccc}1& 1& 0& 0& 1& 0\\ 1& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 0& 1\end{array}\right\}\cdot \left\{\begin{array}{cccccc}\frac{1}{\sqrt{3}}& 0& 0& 0& 0& 0\\ 0& \frac{1}{\sqrt{4}}& 0& 0& 0& 0\\ 0& 0& \frac{1}{\sqrt{3}}& 0& 0& 0\\ 0& 0& 0& \frac{1}{\sqrt{4}}& 0& 0\\ 0& 0& 0& 0& \frac{1}{\sqrt{4}}& 0\\ 0& 0& 0& 0& 0& \frac{1}{\sqrt{2}}\end{array}\right\}= \\ \left\{\begin{array}{cccccc}\frac{1}{\sqrt{9}}& \frac{1}{\sqrt{12}}& 0& 0& \frac{1}{\sqrt{12}}& 0\\ \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{12}}& 0& \frac{1}{\sqrt{16}}& 0\\ 0& \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{9}}& \frac{1}{\sqrt{12}}& 0& 0\\ 0& 0& \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{8}}\\ \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{16}}& 0& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{16}}& 0\\ 0& 0& 0& \frac{1}{\sqrt{8}}& 0& \frac{1}{\sqrt{4}}\end{array}\right\} \end{gathered}$$

renormalization后有：

$$L^{sym}:=D^{-1/2}L{D}^{-1/2}=D^{-1/2}(D-A)D^{-1/2}=I_n-D^{-1/2}A{D}^{-1/2}$$
这就是在GCN谱方法推导中中提到的拉普拉斯矩阵要这样标准化的原因了。
经过邻接矩阵添加自环（renormalization）之后，可以得到

$$H^{(l+1)}=f(H^l,A)=\sigma ({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{H}^{(l)}{W}^{(l)})$$

这就是GCN用谱方法推导出来的公式，这样就可以从空间结构的角度理解一阶ChebNet（GCN）了。

13. GCN处理不同类型的图

关于带权图问题

GCN论文里的针对的是无权的无向图，并且采用的是平均聚合的方法，邻居之间没有权重。但是，现实生活中更多的是带权图。比如，我们都认识马化腾，但是张志东与马化腾的亲密度要比我们和马化腾的亲密度高得多。因此，可以预测张志东的工资比我们更接近马化腾。

不过GCN还是可以直接处理带权图，原来的邻居矩阵取值只能是0和1，现在可以取更多的权值。

关于有向图问题

前面的都是针对于无向图的问题，所有拉普拉斯矩阵是对称矩阵，但是在有向图中，就不能定义拉普拉斯矩阵了。目前的两种解决思路：
（a）要想保持理论上的完美，就需要重新定义图的邻接关系，保持对称性
比如这篇文章MotifNet: a motif-based Graph Convolutional Network for directed graphs
提出利用Graph Motifs定义图的邻接矩阵。

（b）个人认为基于空间域的GCNs都可以处理有向图，比如GraphSAGE、GAT等，聚合邻居信息时根据有向边判断是否是邻居即可

节点没有特征的图

对于很多网络，可能没有节点的特征，这个时候也是可以使用GCN的，如论文中作者对那个俱乐部网络，采用的方法就是用单位矩阵 I替换特征矩阵X，有的地方也用节点度作为节点特征。

14. 问题讨论

下面将总结一些常见的问题和回答，欢迎大佬们一起讨论

Q1：GCN中邻接矩阵为什么要归一化？

看前面的例子

$$\tilde{A}=A+I_N=\left\{\begin{array}{cccccc}1& 1& 0& 0& 1& 0\\ 1& 1& 1& 0& 1& 0\\ 0& 1& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1\\ 1& 1& 0& 1& 1& 0\\ 0& 0& 0& 1& 0& 1\end{array}\right\}，\tilde{D}=\sum _j{\tilde{A}}_{ij}=D+I_N=\left\{\begin{array}{cccccc}3& 0& 0& 0& 0& 0\\ 0& 4& 0& 0& 0& 0\\ 0& 0& 3& 0& 0& 0\\ 0& 0& 0& 4& 0& 0\\ 0& 0& 0& 0& 4& 0\\ 0& 0& 0& 0& 0& 2\end{array}\right\}$$

$${\tilde{D}}^{-1}\tilde{A}=\left\{\begin{array}{cccccc}1/3& 1/3& 0& 0& 1/3& 0\\ 1/4& 1/4& 1/4& 0& 1/4& 0\\ 0& 1/3& 1/3& 1/3& 0& 0\\ 0& 0& 1/4& 1/4& 1/4& 1/4\\ 1/4& 1/4& 0& 1/4& 1/4& 0\\ 0& 0& 0& 1/2& 0& 1/2\end{array}\right\}$$

显然，${\tilde{D}}^{-1}\tilde{A}X$归一化对邻居取平均值。

$$\begin{array}{l}{X}^{\ast }={\tilde{D}}^{-1}\tilde{A}X\\ X_i^{\ast }={\sum }_{j=1}^N\frac{{\tilde{A}}_{ij}}{{\tilde{D}}_{ii}}{X}_j={\sum }_{j=1}^N\frac{{\tilde{A}}_{ij}}{{\sum }_{k=1}^N{\tilde{A}}_{ik}}{X}_j\end{array}$$

举个例子，如果把『我』看成当前节点，『我的朋友』看做『我』的相邻节点，要估算『我的工资』该怎么做呢？对邻居节点的工资进行加权后是求和，不能估算『我的工资』，求和的方式可能出现一个低端交际花员工的工资比一个朋友较少的大佬的工资更高。因此，进行归一化（$D^{-1}A$）取平均值，就可以更合理的估算『我的工资』。

Q2:GCN中邻接矩阵为什么要renormalization？

还是看前面的例子
$$\tilde{A}={\tilde{D}}^{-1/2}\tilde{A}{D}^{-1/2}=\left\{\begin{array}{cccccc}\frac{1}{\sqrt{9}}& \frac{1}{\sqrt{12}}& 0& 0& \frac{1}{\sqrt{12}}& 0\\ \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{12}}& 0& \frac{1}{\sqrt{16}}& 0\\ 0& \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{9}}& \frac{1}{\sqrt{12}}& 0& 0\\ 0& 0& \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{8}}\\ \frac{1}{\sqrt{12}}& \frac{1}{\sqrt{16}}& 0& \frac{1}{\sqrt{16}}& \frac{1}{\sqrt{16}}& 0\\ 0& 0& 0& \frac{1}{\sqrt{8}}& 0& \frac{1}{\sqrt{4}}\end{array}\right\}$$
网上很多地方把上面这个叫做对称归一化，从例子中可以看出$\tilde{A}={\tilde{D}}^{-1/2}\tilde{A}{D}^{-1/2}$确实是对称的，但是行和列都没有归一化，论文中叫renormalization，本人提议各大网友不要再叫对称归一化，容易误导别人。
对于节点4，邻居节点分别为[3,4,5,6]，邻居节点的度数分别为[3,4,4,2]。现考虑第4行，邻居节点分到的权重分别为[$\frac{1}{\sqrt{12}},\frac{1}{\sqrt{16}},\frac{1}{\sqrt{16}},\frac{1}{\sqrt{8}}$]，可以看到，邻居节点度数越小，分配到的权重越大。因此，空间意义就是：每个节点通过边对外发送相同量的信息, 边越多的节点,每条边发送出去的信息量就越小。

举个例子，要估计一个大佬的工资，那么他的朋友中除了同等高收入的朋友，也有一些低端交际花，如果按这些低端交际花的朋友数给他分配权重，那么就会拉低大佬的工资，因此，需要剔出这些低端交际花的影响。

Q3:GCN中参数矩阵W的维度如何确定？怎么理解GCN是transductive的？

由下列公式可知
$$Z={\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}XW$$

参数矩阵W的行数为输入节点特征的维度，不可调，而列数F为节点最后输出的特征维度，是可调参数。
虽然W的维度和邻接矩阵A无关，但是参数矩阵W的取值的更新和A相关，因此如果把训练集和测试集分开，分别形成自己的邻接矩阵。那么W的值的更新和训练集的邻接矩阵相关，如果直接用于计算测试集的embedding，效果应该会很差。这也是都说GCN是transductive的原因。

Q4：为什么GCN里使用NELL数据集相比于其他三个的分类准确率这么低？

Q5：目前GCN的分类准确率仅为80%左右，如何提高GCN在Citeseer、Cora、Pubmed、Nell上的分类准确率？

Q6：增加GCN层数，为何准确率还降低了？

在“A Comprehensive Survey on Graph Neural Networks”和“Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning”中的解释是over smoothing，也就是层数多了，反而使远处的节点和近处的节点相似而更难以区分，当层数到达一定时，整个网络呈一个稳定的不动点，达到平衡。

有错误的地方还望不吝指出，欢迎进群交流GNNs&GCNs（入群备注信息!!!，格式：姓名 -（学校或其他机构信息）- 研究方向）。

资料下载

多篇图卷积相关ppt下载
ResGCN-Can GCNs Go as Deep as CNNs? 两份PPT（官方PPT和会议PPT）
Cluster-GCN An Efficient Algorithm for Training Deep and Large Graph…ppt
Large-Scale Learnable Graph Convolutional Networks（LGCN）ppt

参考

感谢以下大佬的总结，一些重要的参考如下：

知乎superbrother给出了非常详细的说明, 写得很好, 手动点赞：如何理解 Graph Convolutional Network（GCN）？
从图(Graph)到图卷积(Graph Convolution)：漫谈图神经网络模型 (二)
图卷积神经网络入门基础
图卷积网络知识汇总
GNN 教程：漫谈谱图理论和GCN的起源
部分论文：
[1]. Neural Message Passing for Quantum Chemistry　　
[2]. Inductive Representation Learning on Large Graphs　　
[3]. Diffusion-Convolutional Neural Networks　　
[4]. Learning Convolutional Neural Networks for Graphs　
[5]. Spectral Networks and Locally Connected Networks on Graphs
[6]. Convolutional neural networks on graphs with fast localized spectral filtering
[7]. Semi-Supervised Classification with Graph Convolutional Networks
[8]. A Comprehensive Survey on Graph Neural Network