正文 

当前位置： 首页 > IT > java教程

图卷积的演变-从谱图卷积到gcn

LeonYi LeonYi     2023-02-03     184

关键词：

基础

傅里叶级数是对周期为T的确定性信号做展开，而傅里叶变换将周期推广到无穷，能对具有任意长度的信号做展开。

https://www.zhihu.com/question/21665935/answer/2367861632

\\[\\hatf(t)=\\intf(x)\\exp^-iwtdx = \\intf(x) \\left(cos(wx) + isin(wx) \\right)dx \\]

要在图上做图傅里叶变化关键, 是找到图信号的基函数。

拉普拉斯算子(Laplacian operator) 的物理意义是空间二阶导数，其准确定义是：标量梯度场中的散度，可用于描述物理量的流入流出，例如热传播。

图拉普拉斯矩阵L是拉普拉斯算子的在图（离散空间）上的的推广。

广义特征方程：传统傅里叶的基函数可视为拉普拉斯算子（梯度的散度，二阶偏导之和）的特征向量，频率为特征值：

\\[∆e^-iwt=\\frac\\partial^2\\partialt^2e^-iwt=-w^2e^-iwt \\]

那么，很自然的可++把拉普拉斯L的特征向量作为图傅里叶变换的基函数++。

\\[\\mathbfL = \\mathbfD - \\mathbfA = \\mathbfU \\mathbf\\Lambda \\mathbfU^T, 拉普拉斯矩阵特征分解 \\]

\\[\\mathbfU = (\\mathbfu_1, \\mathbfu_2, \\cdots, \\mathbfu_n)， \\mathbfU^-1 =\\mathbfU^T, \\mathbfU \\mathbfU^T = \\mathbfI \\]

\\[ \\phi_l = \\mathbfu_l^T \\mathbff,基向量上的分量 \\]

图上的任意一个信号(n维)都可表示为拉普拉斯矩阵特征向量（基向量）的线性组合。

\\[ 图傅里叶变换， \\mathbf\\Phi = \\left[ \\beginmatrix \\phi_1 \\\\ ... \\\\ \\phi_N \\endmatrix \\right]=\\mathbfU^T \\mathbff \\]

\\[图傅里叶逆变换， \\mathbff =\\sum_l \\phi_l \\mathbfu_l = \\mathbfU \\mathbf\\phi \\]

图傅里叶变换，在这里就是将图信号f投影（内积计算分量）到L的特征向量构成的基向量上。就是将f从原始空间变到新的空间-谱（频）域。

\\[ \\mathbf\\Phi=\\mathbfU^T \\mathbff= \\mathbfU^T (\\mathbfU \\mathbf\\Phi), \\mathbff = \\mathbfU \\mathbf\\Phi = \\mathbfU (\\mathbfU^T \\mathbff) \\]

第一代：Spectral Network

卷积定理：卷积的傅里叶变换等于傅里叶变换的乘积（时域卷积，等于在频域做乘积）

\\[ F\\f*g\\ = F[f] \\odot F[g]] \\]

通过傅里叶逆变换可以得到:

\\[f*g = F^-1[F[f]\\odotF[g]] \\]

在图上做，图信号和滤波器g的卷积：

\\[输入 \\mathbfx \\in \\mathbbR^N，每一个节点有一个标量 \\]

\\[\\mathbfU \\in \\mathbbR^N \\times N, 拉普拉斯矩阵特征向量 \\]

\\[ 有滤波器向量 \\mathbfg \\in \\mathbbR^N \\]

那么，图上的卷积可以定义为：

\\[\\mathbfx \\star \\mathbfg = \\mathbfU (\\mathbfU^T\\mathbfx) \\odot (\\mathbfU^T\\mathbfg) = \\mathbfU (\\mathbfU^T\\mathbfx \\odot \\mathbf\\theta ) \\]

\\[把 \\mathbfU^T\\mathbfg统一视为一个，\\mathbf\\theta \\in \\mathbbR^N (傅里叶变换后的滤波器 \\mathbfg) \\]

传统滤波器需根据经验设定，在这里可将滤波器视为：可参数化的卷积核

卷积运算中的乘法为element-wise product，即在频域的乘法。在这里，其直观意义就是：

\\[(\\mathbfU^T\\mathbfx) \\odot \\mathbf\\theta，\\mathbf\\theta \\odot (\\mathbfU^T\\mathbfx)，交换顺序不影响 \\]

用卷积核的参数对频域信号的每个分量进行加权操作，从而实现滤波（不同的频率分量有不同的权重系数）

那么将卷积核向量展开为对角矩阵形式（行变换），有：

\\[\\mathbfg_\\theta = diag(\\mathbf\\theta) = \\left[ \\beginmatrix \\theta_1 & ... & 0 \\\\ ... & ... & ... \\\\ 0 & ... & \\theta_N \\endmatrix \\right] \\]

最后，可得到：

\\[\\mathbfx \\star \\mathbfg = \\mathbfU (\\mathbfU^T\\mathbfx \\odot \\mathbf\\theta ) \\\\ = \\mathbfU (\\mathbf\\theta \\odot \\mathbfU^T\\mathbfx ) \\\\ = \\mathbfU \\mathbfg_\\theta \\mathbfU^T \\mathbfx \\]

假设每个节点有d维的特征，即通道数为d（d个图信号）:

\\[\\mathbfX = \\left[ \\beginmatrix x_11 & x_12 & ... & x_1d \\\\ ... & ... & ... \\\\ x_n1 & x_n2 & ... & x_nd \\endmatrix \\right] = \\left[ \\beginmatrix \\mathbfx_1 & \\mathbfx_2 & ... & \\mathbfx_d \\endmatrix \\right] \\]

注意，\\(\\mathbfX \\in \\mathbbR^N \\times d\\), 每一个通道可使用多个卷积核（类似CNN，拓展通道数）。

对于第l层谱图卷积，通道数为d_l：

\\[假设第 l 和l+1层的节点状态为： \\mathbfX^(l) \\in \\mathbbR^N \\times d_l， \\mathbfX^(l+1) \\in \\mathbbR^N \\times d_l+1 \\]

\\[\\mathbfX^(l)_:i =\\mathbfx^(l)_i \\in \\mathbbR^N \\]

使用d_l * d_(l+1)个卷积核，每次在全部通道分别用d_l个卷积核并将结果求和，重复d_(l+1)次，得到输出特征通道：

\\[\\mathbfx^l+1_j=\\sigma(\\mathbfU \\sum_i=1^d_l \\mathbf\\Theta^l_i,j \\mathbfU^T \\mathbfx^l_i), (j = 1, \\dots, d_(l+1)) \\]

\\[\\mathbf\\Theta^l_i,j直接视为模型参数， \\mathbfU \\mathbf\\Theta^l_i,j \\mathbfU^T对应CNN中的卷积核(复杂度 O(n^2)) \\]

Spectral Graph Convolution操作定义为：

  • 计算图拉普拉斯(graph Laplacian)的特征值分解，得到特征向量
  • 将图信号进行图傅里叶变换， 然后使用卷积核进行滤波，然后再进行图傅里叶逆变换

缺点：

  • 图拉普拉斯特征分解O(n^3)复杂度， 前向传播O(n^2)。
  • 卷积核参数量大： n * d_l * d_(l+1), 易过拟合(n 为节点数量)
  • 在空域上没有明确定义，不能局部化到节点上

第二代：ChebNet

切比雪夫网络实现了：快速局部化和低复杂度

\\[\\mathbfg \\star \\mathbfx = \\mathbfx \\star \\mathbfg = \\mathbfU \\mathbfg_\\theta \\mathbfU^T \\mathbfx， 谱图卷积 \\]

从图信号分析的角度考虑，希望这个过滤函数g能有较好的局部化（只影响节点的局部邻居点）。

\\[故可把\\mathbfg定义成\\mathbfL的函数\\mathbfg_\\theta(\\mathbfL)， 例如\\mathbfL的多项式 \\]

因为作用一次拉普拉斯矩阵, 相当于在图上把信息扩散到1阶邻居。

图信号被这个滤波器过滤后 (++拉普拉斯矩阵乘法仅与特征值相关++)，得到：

\\[\\mathbfy = \\mathbfg_\\theta (\\mathbfL)\\mathbfx = \\mathbfg_\\theta (\\mathbfU \\mathbf\\Lambda \\mathbfU^T) \\mathbfx = \\mathbfU \\mathbfg_\\theta (\\mathbf\\Lambda) \\mathbfU^T \\mathbfx \\]

\\[\\mathbf\\Lambda，特征值构成的对角矩阵 \\]

也就是说，可把谱域图卷积中的卷积核, 看作拉普拉斯矩阵特征值的函数。通常，可选择使用一个多项式卷积核:

\\[\\mathbfg_\\theta(\\mathbf\\Lambda) = \\sum_k=0^K \\mathbf\\theta_k \\mathbf\\Lambda^k \\]

其中，参数ek是多项式的系数。通过这个定义，我们现在只需要K+1个参数（K《n）这大大降低了参数学习过程的复杂度。就相当于:

\\[\\mathbfg_\\theta(\\mathbfL) = \\sum_k=0^K \\mathbf\\theta_k \\mathbfL^k \\]

因此信息最多在每个节点传播K步，即即卷积的局部化。

ChebNet进一步提出了加速方案：

\\[把 \\mathbfg_\\theta(\\mathbf\\Lambda)近似为切比雪夫多项式的K阶阶段 \\]

\\[\\mathbfg_\\theta(\\mathbf\\Lambda) = \\sum_k=0^K \\theta_k T_k(\\tilde\\mathbf\\Lambda) \\]

其中，Tk是k阶切比雪夫多项式。

\\[\\tilde\\mathbf\\Lambda = 2 \\mathbf\\Lambda_n / \\lambda_max - \\mathbfI_n是一个对角阵 \\\\ 主要将特征值对角阵映射到[-1，1]区间 \\\\ \\lambda_max是\\mathbfL 最大的特征值，\\theta_k \\in \\mathbbR^K为切比雪夫系数向量 \\]

之所以采用切比雪夫多项式，是因为考虑到它具有很好的性质，可以循环递归求解:

\\[T_k(\\mathbfx)=2 \\mathbfx T_k-1(\\mathbfx)-T_k-2(\\mathbfx) \\]

\\[从初始值 T_0(\\mathbfx)=1, T_1(\\mathbfx)=\\mathbfx开始,采用递归公式，可求得k阶T_k的值 \\]

为了避免特征值分解，将式（3.8）写回为L的函数:

\\[\\beginaligned \\mathbfy =\\boldsymbolg * \\mathbfx & = \\mathbfU \\mathbfg_\\theta (\\mathbf\\Lambda) \\mathbfU^T \\mathbfx \\\\ & = \\mathbfU \\left( \\sum_k=0^K \\theta_k T_k(\\tilde\\mathbf\\Lambda) \\right) \\mathbfU^T \\mathbfx \\\\ & = \\sum_k=0^K \\theta_k \\left(\\mathbfU T_k(\\tilde\\mathbf\\Lambda) \\mathbfU^T\\right) x \\\\ &=\\sum_k=0^K \\theta_k T_k(\\tilde\\mathbfL) \\mathbfx \\endaligned \\]

\\[其中, \\tilde\\mathbfL=\\frac2\\lambda_\\max \\mathbfL-\\mathbfI_N。这个式子是拉普拉斯矩阵的K次多项式。 \\]

因此，它仍然保几K-局部化(节点仅被其周围的K 阶邻居节点所影响）。

第三代：GCN

GCN限制了逐层的卷积操作，并将切比雪夫多项式的项数设为K=1来减缓过拟合的问题，

\\[它还近似了\\lambda_\\max \\approx 2，最后简化的方程如下 \\]

\\[ \\mathbfg_\\theta^\\prime \\star \\mathbfx \\approx \\theta_0^\\prime \\mathbfx+\\theta_1^\\prime\\left(\\mathbfL-\\mathbfI_N\\right) \\mathbfx=\\theta_0^\\prime \\mathbfx-\\theta_1^\\prime \\mathbfD^-\\frac12 \\mathbfA \\mathbfD^-\\frac12 \\mathbfx \\]

使用两个无限制的参数\\(\\theta\'_0\\)和\\(\\theta\'_1\\)。

在通过设置\\(\\theta=\\theta_0^\\prime=-\\theta_1^\\prime\\)来限制参数的数量之后，我们可以得到一下的表达式

\\[ \\mathbfy =\\boldsymbolg * \\mathbfx = \\mathbfg_\\theta \\star \\mathbfx \\approx \\theta\\left(\\mathbfI_N+\\mathbfD^-\\frac12 \\mathbfA \\mathbfD^-\\frac12\\right) \\mathbfx \\]

值得一提的是，叠加使用这个操作会导致数值不稳定性以及梯度爆炸或消失(因为不断地乘以同一个矩阵)，因此，该论文里面使用了重规整化操作(renormalization)：

\\[ \\mathbfI_N+\\mathbfD^-\\frac12 \\mathbfA \\mathbfD^-\\frac12\\rightarrow\\tilde\\mathbfD^-\\frac12 \\tilde\\mathbfA \\tilde\\mathbfD^-\\frac12 \\]

其中，

\\[\\tilde\\mathbfA=\\mathbfA+\\mathbfI_N，\\tilde\\mathbfD_i i=\\sum_j \\tilde\\mathbfA_i j \\]

\\[最后，论文将模型扩展为含有C个输入通道的信号，\\mathbfX \\in \\mathbbR^N \\times C以及F个滤波器来用于提取特征 \\]

\\[ \\mathbfZ=\\tilde\\mathbfD^-\\frac12 \\tilde\\mathbfA \\tilde\\mathbfD^-\\frac12 \\mathbfX \\boldsymbol\\Theta \\]

\\[ 其中，\\Theta \\in \\mathbbR^C \\times F是滤波器参数矩阵，\\mathbfZ \\in\\mathbbR^N \\times F是卷积信号矩阵。 \\]

在所有这些频域方法中，学习得到的滤波器都是基于拉普拉斯特征分解，也就是取决于图的结构，这也就意味着，在一个特定结构上训练得到的模型，并不能直接应用到另外一个结构不同的图上。

深度学习100例|第52天-图卷积神经网络（gcn）：实现论文分类

查看详情

gcn-图卷积神经网络算法简单实现（含python代码）(代码片段)

...程讲解三、代码实现和结果分析1.导入包2.数据准备¶3. 图卷积层定义4.GC 查看详情

图卷积神经网络gcn的一些理解以及dgl代码实例的一些讲解(代码片段)

...f0c;因此，图神经网络的学习也是必不可少的。GCNGCN是图卷积神经网络， 查看详情

gcn图卷积网络入门详解

...再深入了解它背后的数学原理。字幕组双语原文：【GCN】图卷积网络(GCN)入门详解英语原文：GraphConvolutionalNetworks(GCN)翻译：听风1996、大表哥许多问题的本质上都是图。在我们的世界里，我们看到很多数据都是图，比如分子、社... 查看详情

gcn笔记：graphconvolutionneuralnetwork，chebnet

在 GNN笔记：图卷积_UQI-LIUWJ的博客-CSDN博客中，我们知道了谱图卷积相当于是那么问题在于，如何设计含有可训练的、共享参数的kernel呢？ 1GCN-ver1.0（2013）1.0原理SpectralNetworksandDeepLocallyConnectedNetworksonGraphs... 查看详情

如何使用图卷积网络对图进行深度学习(代码片段)

文章目录简介什么是图卷积网络？一个简单的传播规则存在的问题添加自循环规范化特征表示把它放在一起加回权重添加激活函数回到现实扎卡里的空手道俱乐部构建GCN结论简介由于高度复杂但信息丰富的图结构，图上... 查看详情

深度学习100例|第52天-图卷积神经网络（gcn）：实现论文分类(代码片段)

文章目录一、GCN是什么二、数据集-CoraDataset1.数据集介绍2.准备数据三、划分训练集、测试集和验证集四、模型训练1.Loss计算2.训练模型3.结果可视化五、同系列作品🚀我的环境：语言环境：Python3.6.5编译器：jupytern... 查看详情

论文笔记：semi-supervisedclassificationwithgraphconvolutionalnetworks

...，有label的那一部分，计算L0，以此进行训练2图卷积的快速估计考虑一个多层的GCN，其中第l层的propagation可以写成,A是邻接矩阵W是第l层的可学习参数σ是激活函数第零层=X 论文接下来的部分将说明这种propagation... 查看详情

论文笔记：semi-supervisedclassificationwithgraphconvolutionalnetworks

...，有label的那一部分，计算L0，以此进行训练2图卷积的快速估计考虑一个多层的GCN，其中第l层的propagation可以写成,A是邻接矩阵W是第l层的可学习参数σ是激活函数第零层=X 论文接下来的部分将说明这种propagation... 查看详情

考虑关系的图卷积神经网络r-gcn的一些理解以及dgl官方代码的一些讲解(代码片段)

文章目录前言R-GCN传播公式正则化DGL中的R-GCN实体分类的实例nn.Parametertorch.matmul参考前言昨天写的GCN的一篇文章入榜了，可喜可贺。但是感觉距离我的目标还是有点远，因为最后要用R-GAT，我感觉可能得再懂一点R-GCN和G... 查看详情

图卷积网络gcn

GCNCNN中的卷积本质上就是共享参数的过滤器，可以较为有效地提取空间特征而很多其他的研究中还有很多非欧拉结构的数据1.CNN无法处理非欧拉结构的数据，传统的离散卷积在NonEuclideanStructure的数据上无法保持平移不变性... 查看详情

图卷积网络gcn

GCNCNN中的卷积本质上就是共享参数的过滤器，可以较为有效地提取空间特征而很多其他的研究中还有很多非欧拉结构的数据1.CNN无法处理非欧拉结构的数据，传统的离散卷积在NonEuclideanStructure的数据上无法保持平移不变性... 查看详情

图卷积神经网络(gcn)综述与实现（pytorch版)(代码片段)

图卷积神经网络(GCN)综述与实现（PyTorch版)本文的实验环境为PyTorch=1.11.0+cu113，PyG=2.0.4，相关依赖库和数据集的下载请见链接。一、图卷积神经网络介绍1.1传统图像卷积卷积神经网络中的卷积(Convolution)指的是... 查看详情

深入浅出图神经网络|gnn原理解析☄学习笔记图信号处理与图卷积神经网络(代码片段)

...网络|GNN原理解析☄学习笔记（五）图信号处理与图卷积神经网络文章目录深入浅出图神经网络|GNN原理解析☄学习笔记（五）图信号处理与图卷积神经网络矩阵乘法的三种形式图信号与图的拉普拉斯矩阵图傅里叶... 查看详情

用于交通预测的时空交互动态图卷积网络

...动态关联。我们提出了一种基于神经网络的时空交互动态图卷积网络(STIDGCN)来解决上述交通预测 查看详情

从0到1实现gcn——最详细的代码实现(代码片段)

最近论文中需要使用图卷积神经网络（GNN），看了一些关于GCN的代码，还有基于PyTorchGeometricTemporal的代码实现，在这里做一下记录。GCN原始代码关于GCN的原理在这里不进行过多阐述，其他文章里面解释的已... 查看详情

从图(graph)到图卷积(graphconvolution)：漫谈图神经网络模型(代码片段)

...于图神经网络的系列文章，文章目录如下：从图(Graph)到图卷积(GraphConvolution)：漫谈图神经网络模型(一)从图(Graph)到图卷积(GraphConvolution)：漫谈图神经网络模型(二)从图(Graph)到图卷积(GraphConvolution)：漫谈图神经网络模型(三)笔者最... 查看详情

从图(graph)到图卷积(graphconvolution)：漫谈图神经网络模型

...于图神经网络的系列文章，文章目录如下：从图(Graph)到图卷积(GraphConvolution)：漫谈图神经网络模型(一)从图(Graph)到图卷积(GraphConvolution)：漫谈图神经网络模型(二)从图(Graph)到图卷积(GraphConvolution)：漫谈图神经网络模型(三)在上一... 查看详情