图卷积网络作为图神经网络之一，具有非常广泛的应用。因此网上也有非常多的关于GCN的介绍，但是各种博客看的多了搞得我脑壳嗡嗡的，而刚好最近的一个工作涉及到GCN的内核，因此借助这篇博客整理对GCN进行整理。
在介绍GCN先介绍几篇文献：
Semi-Supervised Classification with Graph Convolutional Networks-首次提出GCN的论文（ICLR2017)
Data Analytics on Graphs-图机器学习的教材
https://www.zhihu.com/question/54504471-介绍GCN的博客
GNN & Message Passing
GNN作为一种graph embedding的手段，可以借助节点特征的message passing提取图结构信息 \[\begin{aligned} \mathbf{h}_{u}^{(k+1)} &=\operatorname{UPDATE}^{(k)}\left(\mathbf{h}_{u}^{(k)}, \text { AGGREGATE }^{(k)}\left(\left\{\mathbf{h}_{v}^{(k)}, \forall v \in \mathcal{N}(u)\right\}\right)\right) \\ &=\operatorname{UPDATE}^{(k)}\left(\mathbf{h}_{u}^{(k)}, \mathbf{m}_{\mathcal{N}(u)}^{(k)}\right) \end{aligned}\]
GNN进行k轮迭代，每轮包括一个聚合（aggregate）和更新（update）操作。聚合来获取邻节点的信息，而后更新节点的自身特征。这种多轮message passaging的机制使得图的结构信息以及邻节点特征被提取到节点的特征中。广义上来说，GCN也是GNN中的一种。GCN的message passaging非常的简单。从下式（最基础形式的GCN）可以看出，GCN借助边信息对节点信息进行聚合。 \[
f\left(H^{(l)}, A\right)=\sigma\left(A H^{(l)} W^{(l)}\right)
\]
GNN & CNN
对于图像来说，nxn的卷积核可以作为图像中的特征提取器（为了防止图和图像这两个词的太过接近导致可能出现的问题，下文提到图时将用graph）。但是这种卷积操作无法直接用在Graph上，为什么？
由于图像与graph的数据特性和卷积操作的特性。首先，图像具有局部平移不变性(local translational invariance)，使得卷积核能够对图像矩阵进行扫描卷积；而graph作为非欧空间的数据 (Non Euclidean Structure)，每个节点邻接点的各异导致传统CNN操作无法应用。第二，卷积核是参数共享的，且可以实现层次化特征提取-卷积层可以在前一层的基础上提取更高阶的特征；而graph的层数加深则是使节点获取更广的感受野。
Spectrum
参考https://zhuanlan.zhihu.com/p/120311352
在空间域上的图卷积碰壁并不意味着在图上没法进行操作，我们可以从频域中进行分析。
图的拉普拉斯矩阵
首先定义几个概念：
在图上最基本的拉普拉斯矩阵Laplacian matrix为： \[
\mathbf{L}=\mathbf{D}-\mathbf{A}
\] 其中\(\mathbf{D}\)为度矩阵，\(\mathbf{A}\)为邻接矩阵。拉普拉斯矩阵有一些基本的性质：对称 (\(\mathbf{L}^{T}=\mathbf{L}\))；半正定 (\(\mathbf{x}^{\top} \mathbf{L} \mathbf{x} \geq 0, \forall \mathbf{x} \in \mathbb{R}^{|\mathcal{V}|}\))，这也意味着拉普拉斯矩阵的特征值都是非负的：\(0=\lambda_{|\mathcal{V}|} \leq \lambda_{|\mathcal{V}|-1} \leq \ldots \leq \lambda_{1}\)。 \[
\begin{aligned}
\mathbf{x}^{\top} \mathbf{L} \mathbf{x} &=\frac{1}{2} \sum_{u \in \mathcal{V}} \sum_{v \in \mathcal{V}} \mathbf{A}[u, v](\mathbf{x}[u]-\mathbf{x}[v])^{2} \\
&=\sum_{(u, v) \in \mathcal{E}}(\mathbf{x}[u]-\mathbf{x}[v])^{2}
\end{aligned}
\] 另外，对称规范化拉普拉斯矩阵symmetric normalized Laplacian定义如下，这是GCN相关工作中比较常用的。 \[
\mathbf{L}_{\mathrm{sym}}=\mathbf{D}^{-\frac{1}{2}} \mathbf{L} \mathbf{D}^{-\frac{1}{2}}
\]
拉普拉斯算子
接下来我们来一步步理解为什么要这样定义图的拉普拉斯矩阵。对于空间中的任意函数\(f\)来说， \[
\Delta f=\nabla^{2} f=\nabla \cdot \nabla f =\sum_{i=1}^{n} \frac{\partial^{2} f}{\partial x_{i}^{2}}
\] 拉普拉斯算子 (Laplacian)是欧式空间中的函数梯度的散度 (Divergence)对应的微分算子。在n维空间中计算的是函数各个维度二阶偏导的和。在二维空间中，可以近似为差分的计算 \[
\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))-2 f(x, y)]+[f(x, y+1)+f(x, y-1))-2 f(x, y)] \\
&=f(x+1, y)+f(x-1, y))+f(x, y+1)+f(x, y-1))-4 f(x, y)
\end{aligned}
\] 上式事实上就是在图像上作用拉普拉斯卷积核 \[
\begin{array}{|r|r|r|}
\hline 0 & 1 & 0 \\
\hline 1 & -4 & 1 \\
\hline 0 & 1 & 0 \\
\hline
\end{array}
\] 因此拉普拉斯算子可以理解为——在所有自由度上进行微小变化后所获得的增益。
而将其推广到有N节点的graph上时，\(f\)维度最高为N，\(f=\left(f_{1}, \ldots, f_{N}\right)\)。其中\(f_{i}\) 表示函数\(f\)在网络图中节点i处的函数值, 类比\(f(x, y)\)为函数\(f\)在 \((\mathrm{x}, \mathrm{y})\)的函数值。
因此当拉普拉斯算子作用在加权graph（边权重为\(w_{i j}\)）上时，借助差分近似后有： \[
\begin{aligned}
\Delta \boldsymbol{f}_{i} &=\sum_{j \in N_{i}} \frac{\partial f_{i}}{\partial j^{2}} \\
& \approx \sum_{j} w_{i j}\left(f_{i}-f_{j}\right) \\
&=\sum_{j} w_{i j}\left(f_{i}-f_{j}\right) \\
&=\left(\sum_{j} w_{i j}\right) f_{i}-\sum_{j} w_{i j} f_{j} \\
&=d_{i} f_{i}-w_{i:} f
\end{aligned}
\] 对于任意\(i \in N\)都成立，所以就得到了： \[
\begin{aligned}
\Delta f=\left(\begin{array}{c}
\Delta f_{1} \\
\vdots \\
\Delta f_{N}
\end{array}\right) &=\left(\begin{array}{cc}
d_{1} f_{1}-w_{1:} f \\
\vdots \\
d_{N} f_{N}-w_{N:} f
\end{array}\right) \\
&=\left(\begin{array}{ccc}
d_{1} & \cdots & 0 \\
\vdots & \ddots & \vdots \\
0 & \cdots & d_{N}
\end{array}\right) f-\left(\begin{array}{c}
w_{1:} \\
\vdots \\
w_{N:}
\end{array}\right) f \\
&=\operatorname{diag}\left(d_{i}\right) f-\mathbf{W} f \\
&=(\mathbf{D}-\mathbf{W}) f \\
&=\mathbf{L} f
\end{aligned}
\] 这就意味着，对由图节点特征构成的向量\(f\)做拉普拉斯等价于图拉普拉斯矩阵与向量\(f\)进行点积。
Graph Fourier Transformer
拉普拉斯矩阵的特征分解 \[ \mathbf{L} \mathbf{u}_{\mathbf{k}}=\lambda_{k} \mathbf{u}_{\mathbf{k}} \] 继而进行正交相似对角化后就得到 \[ \mathbf{L}=\mathbf{U} \mathbf{\Lambda} \mathbf{U}^{-1}=\mathbf{U}\left(\begin{array}{ccc} \lambda_{1} & & \\ & \ddots & \\ & & \\ & & \lambda_{n} \end{array}\right) \mathbf{U^{-1}}=\mathbf{U}\boldsymbol{\Lambda} \mathbf{U}^{T} \] 其中\(\boldsymbol{\Lambda}\) 为特征值构成对角矩阵, \(\mathbf{U}\) 为特征向量构成的正交矩阵。
在这里补充一条性质 \[\Delta e^{-i \omega t} =\frac{\partial^{2} e^{-i \omega t}}{\partial t^{2}}= -\omega^{2} e^{-i \omega t}\] 从广义上来看，这符合特征方程\(AV=\lambda V\)的定义，也就是说\(e^{-i \omega t}\)是拉普拉斯算子的特征函数
把传统的傅里叶变换以及卷积迁移到Graph上来, 核心工作其实就是把拉普拉斯算子的特征函数\(e^{-i \omega t}\) 变为Graph对应的拉普拉斯矩阵的特征向量。 傅立叶变化是信号函数\(f(t)\)与基函数\(e^{-i \omega t}\)的内积 \[ \mathcal{F}_{T}(\omega)=\int_{-\infty}^{+\infty} f(t) e^{-i \omega t} d t \] 因此对于Graph我们就可以定义 \[ F\left(\lambda_{l}\right)=\hat{f}\left(\lambda_{l}\right)=\sum_{i=1}^{N} f(i) u_{l}^{*}(i) \] 其中\(f\)是graph上的N维向量，\(f(i)\)对应于graph上的第i个顶点，\(u_{l}(i)\)表示第l个特征向量的第i个分量。特征值\(\lambda_l\)（频率）下的\(f\)的graph傅立叶变换就是与\(\lambda_l\)对应的特征向量\(u_{l}\)进行内积运算。将上式推广到矩阵形式，就有 \[ \left(\begin{array}{c} \hat{f}\left(\lambda_{1}\right) \\ \hat{f}\left(\lambda_{2}\right) \\ \vdots \\ \hat{f}\left(\lambda_{N}\right) \end{array}\right)=\left(\begin{array}{cccc} u_{1}(1) & u_{1}(2) & \ldots & u_{1}(N) \\ u_{2}(1) & u_{2}(2) & \ldots & u_{2}(N) \\ \vdots & \vdots & \ddots & \vdots \\ u_{N}(1) & u_{N}(2) & \ldots & u_{N}(N) \end{array}\right)\left(\begin{array}{c} f(1) \\ f(2) \\ \vdots \\ f(N) \end{array}\right) \] \[ \hat{f} = U^T f \]
图上的傅立叶逆变换类似于传统傅立叶逆变换的对频率求积分： \[ f(i)=\sum_{l=1}^{N} \hat{f}\left(\lambda_{l}\right) u_{l}(i) \] \[f=U \hat{f}\]
GCN
上文从百草园讲到三味书屋，终于要讲到了本文的主角-GCN。在上面graph傅立叶变换的基础上，我们可以将卷积推广到graph上。 \[ f * h=\mathcal{F}^{-1}[\hat{f}(\omega) \hat{h}(\omega)]=\frac{1}{2 \Pi} \int \hat{f}(\omega) \hat{h}(\omega) e^{i \omega t} d \omega \] 类比到graph上，函数\(f\)与卷积核\(h\)在graph上的卷积 \[ (f * h)_{G}=U\left(\begin{array}{lll} \hat{h}\left(\lambda_{1}\right) & & \\ & \ddots & \\ & & \hat{h}\left(\lambda_{n}\right) \end{array}\right) U^{T} f \] 式中\(\hat{h}\left(\lambda_{l}\right)=\sum_{i=1}^{N} h(i) u_{l}^{*}(i)\)是根据需要设计的卷积核\(h\)在graph上的傅立叶变换。 图表示学习中用的定义为 \[ (f * h)_{G}=U\left(\left(U^{T} h\right) \odot\left(U^{T} f\right)\right) \] \(\odot\) 表示Hadamard product，对两个维度相同的向量、矩阵进行对应位置的逐元素乘积。
将神经网络与graph卷积结合，只需令卷积核变为可学习的参数，也就得到 \[
y_{\text {output }}=\sigma\left(U \left(\begin{array}{lll}
\theta_{1} & & \\
& \ddots & \\
& & \theta_{n}
\end{array}\right) U^{T} x\right)
\] 我们将卷积核记为\(g(\Lambda)\) (\(\Lambda\)就是大写的\(\lambda\))。
这种图卷积被称为第一代图卷积，但这类图卷积计算开销非常大，且卷积核有n个参数，这种图卷积很难处理工业级的数据。 第二代图卷积使用了polynomial filter \[
g_{\theta}(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} \Lambda^{k}=\left(\begin{array}{ccc}
\sum_{j=0}^{K} \alpha_{j} \lambda_{1}^{j} & & \\
& \ddots & \\
& & \\
& & & \sum_{j=0}^{K} \alpha_{j} \lambda_{n}^{j}
\end{array}\right)
\] 其中\(\theta \in \mathbb{R}^{K}\)是多项式系数向量。进而可以推出 \[
U \sum_{j=0}^{K} \alpha_{j} \Lambda^{j} U^{T}=\sum_{j=0}^{K} \alpha_{j} U \Lambda^{j} U^{T}=\sum_{j=0}^{K} \alpha_{j} L^{j}
\] \[y_{\text {output }}=\sigma\left(\sum_{j=0}^{K-1} \alpha_{j} L^{j} x\right)\] 此时，我们计算图卷积运算就不需要再乘上特征向量矩阵\(U\)，而是直接使用拉普拉斯矩阵\(L\)的k 次方（K远小于n），这样就避免了进行特征分解。而我们可以事先计算好\(L^K\) ，这样就只需要计算矩阵相乘。 此外，高阶拉普拉斯可以用切比雪夫展开来近似，因此卷积核还可以用切比雪夫多项式来表示 \[
g_{\theta}(\Lambda)=\sum_{k=0}^{K-1} \theta_{k} T_{k}(\tilde{\Lambda})
\] 而将切比雪夫多项式的阶数限制为2的时候就得到在下游任务中常用的图卷积公式： \[
H^{(l+1)}=\sigma\left(\widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)
\] 上式中，\(\widetilde{A}=A+I, \mathrm{~A}\)为邻接矩阵, \(I\)为单位矩阵, 所以\(\widetilde{A}\) 为添加自连接的邻接矩阵;\(W^{(l)}\) 为神经网络第\(l\)层的权重矩阵; \(\sigma(\cdot)\)是激活函数
GCN & Self-attention
上面从频域分析graph convolution，当我们从空间域上分析得到的卷积公式时，可以看出它仍是一种message passing机制。 \[ A H^{(l)} W^{(l)} \] 上式可以分为两个步骤，首先是\(H\)与参数矩阵\(W\)做一个线性映射，而后与邻节点及其边信息进行聚合汇总。这一框架在某种意义上说与self- attention是非常类似的。
self- attention包含query、key、value；其中输入的query与每个key计算相似度，而后得到一个注意力系数\(\alpha\)，再由注意力系数对value进行加权求和输出最终的结果。抛开邻节点后，这两者的计算机制可以说非常类似，都可以被囊括在message passing这一框架下，而self-attention也可以理解为在完成图（所有节点都相连）上的GCN。而Transformer以及GNN在NLP中的广泛应用也从某种意义上说明了两者之间存在某种相似性。
GCN应用
TextGCN
论文Graph Convolutional Networks for Text Classification所构建的TextGCN将GCN用于文本分类中，在电影评价、新闻等数据集上都取得了不错的表现。
如上图所示，模型将语料库中的每一篇文档和语料库中词作为节点，联合构建了一个异构图，再借助GCN进行特征传播，得到每个文档节点的embedding后进行softmax分类。
文章中节点都使用one-hot vector进行初始化，而文档-词边、词-词边分别用TF-IDF、PMI赋以不同的权重，而最终得到的分类准确率比传统的CNN、LSTM等网络效果要高，足以证明GCN在NLP任务中的潜力。此外，后续用BERT进行节点初始化的BERTGCN也是目前的文本分类的SOTA模型。
ST-GCN
ST-GCN可以说是GCN在骨骼行为识别里面的开山之作。
SGC
作者将图卷积层中的激活函数去掉，得到了SGC在许多NLP任务上更优的结果，且模型速度有了极大的提升。
再回首
回顾一下上文的内容，首先GCN是GNN的一种，从公式上看聚合函数采用的是图的拉普拉斯矩阵。当我们从频域上分析图的拉普拉斯矩阵及其特征分解之后可以发现，拉普拉斯矩阵的特征向量可以作为傅里叶变换的基、特征值表示频率，从而就可以定义图上的傅立叶变换，进而扩展到卷积操作。而将图卷积与神经网络结合后，借助多项式优化后就得到了现在常用的卷积公式。而从空间域中看，图卷积本质上也就是一种信息传播机制，借助边的权重信息对邻节点的特征做限制后传播、聚合、更新节点原本的特征。
在频域分析过程中我们可以得到，在由Graph确定的\(n\)维空间中，越小的特征值 \(\lambda_{l}\) 表明：拉普拉斯矩阵 \(L\) 其所对应的基 \(u_{l}\) 上的分量、"信息"越少、高频部分。所以图卷积有时候也被认知为是图上的高斯平滑，一种滤波的过程，这也导出了图卷积中的一大问题：over-smooshing。当图卷积层数加深时，图上节点自身的特征会因为不断的传播后导致自身的特征消失，所有节点的特征会越来越接近，进而使得下游任务准确率下降。
GCN vs CNN
GCN可以退化为CNN...TODO
