图卷积神经网络打怪升级之路

作者: 笑傲NLP江湖 | 来源:发表于2022-02-11 17:18 被阅读0次

横看成岭侧成峰——从谱的视角出发！
图卷积神经网络打怪升级之路
CNNs 文本分类
CS231n 卷积神经网络: 架构, 卷积/池化层(上)
关于感受野的理解与计算
视觉
卷积神经网络结构
caffe模型学习5
datawhale-task05（卷积神经网络基础；leNet；
卷积神经网络

原创：袁一歌

前言导语

图结构数据 (Graph) 广泛的存在于我们的日常生活之中，从社交网络错综复杂的人际关系，到化学分子键键相连的结构特征。图卷积神经网络(Graph Convolutional Network, GCN) 正是一类对这种图结构数据进行建模的算法。本文《图卷积神经网络打怪升级之路》将从 GCN 的诞生以及三代 GCN 的进阶升级的角度对图卷积领域进行简要介绍，下面让我们开始吧~

从 CNN 到 GCN

CNN 卷积神经网络

卷积神经网络(Convolutional Neural Network,CNN)，是一类包含卷积计算且具有深度结构的神经网络，自1998年 Yann LeCun 等人构建出 LeNet 并成功应用于手写数字识别任务之后，已经成为视觉领域一大杀器，在各种任务上表现出色。下图为 LeNet 模型架构图，可以看出 LeNet 输入是原始图像，经过多层卷积核的卷积操作，不断提取特征图，最终输出原始图像的表示向量。

CNN 模型架构示例}

图数据的非欧性

CNN 成功之后，很多学者开始思考：卷积能否应用于图(Graph)的网络结构之中？解决这个问题的第一步，是思考图(Graph)与图像(Image)的联系与区别。Graph 与 Image 的联系在于 Image 可以看做一种特殊的 Graph，每个像素点看做一个节点，相邻的像素点直接认为存在连边，即密布整齐排列的 grid-graph。

基于此，Graph 与 Image 的区别便昭然若现：Image 中每个像素节点其邻居，即存在连边直接相连的节点数量都是固定的，然而 Graph 节点邻居数量不固定。上述区别提炼到数学领域可以表达为：图是非欧空间而图像是欧式空间^[1] 。

看到现在，很多同学可能会问：欧式空间有什么影响呢，Graph 不是欧式空间会给卷积运算带来什么问题？实际上，非欧空间对于卷积的影响在于卷积核的定义。

回顾一下 CNN 的卷积与卷积核，卷积核定义为 n*n 大小的矩阵并在 Image 上扫描游走。如下图所示的二维卷积运算，其 Image 大小为 5*5，在大小为 3*3 的卷积核的扫描下，得到了大小为 3*3 的特征图。正是因为该Image 数据是像素点整齐排布的欧式空间，每个像素点只与周围的 8 个像素点固定相连，其卷积核才可以被定义并游走扫描。试想一下，如果该 Image 排布不规则，可以与很远的某个像素点存在连边，但与相邻的像素点不存在连边，那么这个 3*3 的卷积核便失去了意义：因为卷积核体现的是感受的范围，感受到的是与中心像素相关联的像素点，而并非无关的像素点。

GCN 核心问题

上文说到：图(Graph)是非欧空间，图的空间不规则，其邻域数量不固定，不便于卷积核的定义；而图像(Image)是典型的欧几里得空间，其空间是规则的，其邻域是确定的，便于卷积核的定义。至此，GCN的研究问题就变成：如何克服非欧性，定义 Graph 上的卷积？

下面将介绍的内容是 GCN 的三代打怪升级之路：SCNN -> Chebynet -> 3rd GCN^[2]。这里需要解释一下，打怪的“怪”指的是每代模型存在的问题与弊端，下一代解决了上一代的弊端，不断完善优化，就是GCN 的打怪升级之路。

SCNN: 开山之作

概述简介

《Spectral Networks and Deep Locally Connected Networks on Graphs》这篇论文是 GCN 的开山之作，提出了谱域 GCN 的第一代模型 SCNN。SCNN 利用谱域变换^[3]定义了Graph 上的卷积核。谱域变换简单来讲可以理解为：在当前空间，Graph 数据为非欧空间，难以定义卷积核；那么将 Graph 数据进行某种空间变换，变换到欧式空间不就可以了？而 SCNN 的这个“某种空间变换”，正是利用了谱图理论中图傅里叶变换与图卷积定理的相关知识，将 Graph 数据投射到了谱域。在谱域下，Graph 是欧式空间，可以定义卷积核，可以进行卷积运算。

模型设计

第一代图卷积神经网络 SCNN 卷积计算公式如下，其利用图傅里叶变换与图的卷积定理，直接将卷积核进行参数化。其中， $U$ 为 Graph 拉普拉斯矩阵特征向量，利用 $U^{T}$ 与图数据相乘代表图傅里叶变换，目的是将非欧的空域 Graph 数据变换到欧式的谱域； $g_{\theta}$ 为卷积核，其中每一个参数 $theta$ 都为可学习的卷积核参数； $f$ 为输入的图上信号(特征)。

$\begin{align*} &(f * _{G} g)=U\left(U^{T} g \odot U^{T} f\right)\\ &\text{Let}\; g_{\theta}=dia(U^{T} g)\\ &\text{then} \; (f * _{G} g)=U\left( g_{\theta}U^{T} f\right)\\ &g_{\theta} =\left[\begin{array}{ccc} \theta_{1} & \ldots & 0 \\ \ldots & \ldots & \ldots \\ 0 & \ldots & \theta_{n} \end{array}\right] \end{align*}$

SCNN 模型架构图如下，原始 Graph 不断经过卷积操作，变换为特征向量。其一层卷积计算公式如下，其中， $x_k$ 是第 k 层特征； $G_{k}$ 是第 k 层卷积核； $U$ 是 Graph 拉普拉斯矩阵特征向量； $h$ 是激活函数。下式为一层卷积计算表达，SCNN 由多层卷积层叠加而成

$\begin{align*} x_{k+1, j}=h\left(U \sum_{i=1}^{f_{k-1}} G_{k, i, j} U^{T} x_{k, i}\right) \quad\left(j=1 \ldots f_{k}\right) \end{align*}$

存在问题

SCNN 作为第一代 GCN，是十分具有开创性的一项工作，但是仍然具有很多问题，主要问题有以下三点：

卷积不具有局部性：SCNN 直接将卷积核进行参数化，卷积核的参数是全图具有影响力的，相当于 CNN 中使用了与原图同样大小的卷积核，失去局部性。
需特征分解，计算复杂：SCNN 需要进行图拉普拉斯矩阵的特征分解，得到特征值与特征向量进行傅里叶变换，而矩阵的特征分解复杂度很高，对于一个 $N \times N$ 的矩阵，其特征分解复杂度为为 $O(N^3)$ 。
参数量与节点数量相同，参数量大：同样因为第一代 GCN 直接将卷积核进行参数化，然后与频域图信号进行矩阵乘法，因此参数数量与矩阵节点数量相当。与节点数量相同的参数数量，对于诸如社交网络等上亿节点数量级的网络来说是不可接受的。

Chebynet：谱域升级

概述简介

《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》这篇论文提出了谱域 GCN 的第二代模型 ChebyNet。ChebyNet 并不像 SCNN 一样直接将卷积核参数化，而是着眼于卷积核与特征值间的映射函数，从而利用多项式近似这个函数。ChebyNet 利用切比雪夫多项式近似卷积核，解决了 SCNN 致命的三大问题，使图卷积网络获得了局部性、降低了计算量与参数量，起到了重要的承上启下作用。

模型设计

第二代图卷积神经网络 ChebyNet 利用切比雪夫多项式对卷积核进行近似。切比雪夫多项式公式如下所示，其中 $T_n(x)$ 是 $x$ 的 $n$ 阶切比雪夫多项式

$\begin{align*} \begin{array}{l} T_{0}(x)=1 \\ T_{1}(x)=x \\ T_{n+1}(x)=2 x T_{n}(x)-T_{n-1}(x) . \end{array} \end{align*}$

在经过切比雪夫多项式近似后， ChebyNet 卷积核变成了如下所示。其中， $\alpha$ 是新的参数，数量为切比雪夫多项式的阶数 k； $\Lambda$ 是拉普拉斯矩阵的特征值矩阵； $L$ 是拉普拉斯矩阵；

$\begin{align*} \begin{aligned} g_{\theta}= \sum_{k=0}^{k-1} \alpha_{k} T_k(\Lambda)=\left[\begin{array}{cc} \sum_{k=0}^{k-1} \alpha_{k} T_k(\lambda_{1}) &\\ \ddots & \\ & \ddots \\ &\sum_{k=0}^{k-1} \alpha_{k} T_k(\lambda_{n}) \end{array}\right] \end{aligned} \end{align*}$

将近似后的卷积核代入卷积计算，可以得到 ChebyNet 一层卷积计算表达。其中， $\Lambda$ 是拉普拉斯矩阵的特征值矩阵； $L$ 是拉普拉斯矩阵

$\begin{align*} \begin{aligned} (g_{\theta} * _{G} x) &=U \cdot \sum_{k=0}^{k-1} \alpha_{k} T_k(\Lambda) U^{\top} x \\ &=\sum_{k=0}^{k-1} \alpha_{k}\left(U T_k(\Lambda) U^{\top}\right) x \\ &=\sum_{k=0}^{k-1} \alpha_{k} T_k(L) x \end{aligned} \end{align*}$

存在问题

ChebyNet 利用切比雪夫多项式近似卷积核，解决了谱域第一代 GCN 致命的三大问题，使图卷积网络获得了局部性、降低了计算量与参数量。但是 k 阶多项式的近似，其高阶的性质不利于卷积层的快速计算与堆叠。

3rd GCN：空域变迁

概述简介

《Semi-Supervised Classification with Graph Convolutional Networks》这篇论文提出了谱域图卷积网络的第三代模型 3rd GCN。3rd GCN 基于 ChebyNet 取其多项式一阶近似，它既可以从谱域进行理解，也可以从空域解释，是一个横跨谱域与空域的模型。3 rd GCN 相比 ChebyNet 计算量进一步降低，是第一个可以真正使用的图卷积模型，具有重要的意义。

模型设计

第三代图卷积神经网络 3rd GCN 将切比雪夫多项式阶数取 1。其一层卷积计算公式如下，其中， $H^{(l)}$ 是第 $l$ 层特征表示； $W^{(l)}$ 是第 $l$ 层可学习参数； $\sigma$ 是激活函数。

$\begin{align*} H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right) \end{align*}$

3rd GCN 不同于 SCNN 与 ChebyNet，SCNN 与 ChebyNet是纯从谱域进行卷积运算的模型，而 3rd GCN 同时具有谱域的卷积核卷积性质，与空域的聚合传播性质。其谱域性质如下：3rd GCN 是一种谱域图卷积模型，它是 ChebyNet 的 1 阶近似，具有卷积核与卷积性质。

$\begin{align*} \begin{aligned} g *_{G} x &=\sum_{k=0}^{1} \beta_{k} T_{k}(\tilde{L}) x \\ &=\beta_{0} T_{0}(\tilde{L}) x+\beta_{1} T_{1}(\tilde{L}) x \\ &=\beta_{0} I_{N} x+\beta_{1} \widetilde{L} x \\ &=\left(\beta_{0} I_{N}+\beta_{1} \tilde{L}\right) x \end{aligned} \end{align*}$

3rd GCN 空域性质如下：GCN 也是一种空域图卷积模型，它具有邻域聚合传播的性质。其中， $h_{ij}^{k}$ 是节点 i 在第 $k$ 层的隐层表示； $d_{ij}$ 是节点 $i$ 的度； $a_{ij}$ 是节点 $i$ 与节点 $j$ 的权重，即邻接矩阵，如果节点 $i$ 与 $j$ 之间存在连边则 $a_{ij}$ 不为 0，否则为 0，这体现了邻域的聚合与传播。

$\begin{align*} \overline{\mathbf{h}}_{i}^{(k)} \leftarrow \frac{1}{d_{i}+1} \mathbf{h}_{i}^{(k-1)}+\sum_{j=1}^{n} \frac{a_{i j}}{\sqrt{\left(d_{i}+1\right)\left(d_{j}+1\right)}} \mathbf{h}_{j}^{(k-1)} \end{align*}$

文末总结

本文介绍了 GCN 的三代打怪升级之路：SCNN -> Chebynet -> 3rd GCN^[2]，后者不断分析前者存在的问题与弊端，并加以优化完善，形成了一条打怪升级的道路。

当下 GCN 的发展日新月异，现在看来不论是 SCNN、Chebynet 还是 3rd GCN 都已经是相对古老的模型，已经被喷涌而出的更新更强的 GCN 完善乃至超越。但是这三代 GCN 十分经典，代表了图卷积领域模型典型的变迁过程，具有很高的学习价值。

关于欧式空方面的知识，这篇文章不做详细介绍，可以见下一篇推送关于谱图理论的内容。 ↩
第三代 GCN 是一个具体的模型的，其名称简写与领域重名就叫做 GCN😂；这里为了加以区分，将第三代 GCN 表示为 3rd GCN。 ↩ ↩
关于谱域变换方面的知识，这篇文章不做详细介绍，可以见下一篇推送关于谱图理论的内容。 ↩

横看成岭侧成峰——从谱的视角出发！
原创：袁一歌前言导语前段时间发布的《图卷积神经网络打怪升级之路》一文介绍了图卷积神经网络的诞生以及三代经典 G...
图卷积神经网络打怪升级之路
原创：袁一歌前言导语图结构数据 (Graph) 广泛的存在于我们的日常生活之中，从社交网络错综复杂的人际关系，...
CNNs 文本分类
1. 介绍卷积神经网络 (Convolutional Neural Networks, CNNs) 及其升级模型...
CS231n 卷积神经网络: 架构, 卷积/池化层(上)
卷积神经网络: 架构, 卷积/池化层(上) 卷积神经网络: 架构, 卷积/池化层(上) 卷积神经网络(CNNs/C...
关于感受野的理解与计算
感受野在卷积神经网络中，感受野（Receptive Field）的定义是卷积神经网络每一层输出的特征图（feat...
视觉
卷积神经网络整理各种卷积神经网络变形
卷积神经网络结构
卷积神经网络是一个多层的神经网络，每层由多个二维平面组成，而每个平面由多个独立神经元组成。图：卷积神经网络的概念...
caffe模型学习5
卷积神经网络是一个多层的神经网络，每层由多个二维平面组成，而每个平面由多个独立神经元组成。图：卷积神经网络的概...
datawhale-task05（卷积神经网络基础；leNet；
卷积神经网络基础 LeNet和其他进阶卷积神经网络
卷积神经网络
第七章卷积神经网络卷积层（Convolution Layer）卷积神经网络（Convolutional Ne...