3. 谱域来解释GCN

借助图谱的理论来实现拓扑图上的卷积操作. 也是利用图的拉普拉斯Laplacian矩阵的特征值和特征向量来研究图的性质.

Graph Fourier Transformation及Graph Convolution的定义都用到图的拉普拉斯矩阵。频域卷积的前提条件是图必须是无向图，只考虑无向图，那么L就是对称矩阵. 拉普拉斯矩阵的定义: 其中 是度矩阵, 是邻接矩阵(取值{0,1}).

常见的拉普拉斯矩阵:

• 定义的Laplacian 矩阵更专业的名称叫Combinatorial Laplacian
• 定义的叫 Symmetric normalized Laplacian，很多GCN的论文中应用的是这种拉普拉斯矩阵.
• 定义的叫Random walk normalized Laplacian .

虽然GCN的核心基于拉普拉斯矩阵的谱分解, 我们待会再看其理论知识, 现在先从一个简单的类比例子加深拉普拉斯的印象.

3.1 简单的类比例子

我们用特例(图片像素点构造的拓扑图)来思考顶点域角度的GCN.

之前所说每个节点聚合邻居的节点值, 这和平滑空间滤波器的操作特别相似 (用于模糊处理或降低噪声,如均值滤波). 但是, 节点的一些突变信息也很重要(比如说破产/暴发户节点). 回想起锐化空间滤波器的知识, 知道微分算子的响应强度与突变程度成正比关系, 所以可以用微分来提取额外特征信息.

图片中, 二阶微分在增强细节上要比一阶微分好, 最简单的各向同性(旋转后结果不变)微分算子是拉普拉斯算子:

其中

常用的一种拉普拉斯滤波器为(也是 ):

那我们 "理解" 了, 能提取图片的细节特征, 也能提取出节点的细节特征.

拉普拉斯算子(Laplacian operator) 的是空间二阶导, 是梯度的散度. 一般可用于描述物理量的流入流出。比如说在二维空间中的温度传播规律. 散度为正的点是“热源”，热量从其中流出；散度为负的点是“冷源”，热量流入该点.

tips:

采用拉普拉斯矩阵, 现在的论文方案可能不是说利用它来提取二阶微分信息,

而是认为拉普拉斯矩阵更能表达这个拓扑图, 其特征向量作为基函数更有代表性.

现在很多论文也对 L 进行各种魔改, 可能是想找到个更能适应任务代表拓扑图的矩阵.

3.2 拉普拉斯作用

滤波器通过卷积方法,能从图片中提取特征. 拓扑图也是. 卷积一般在傅里叶域中计算(时域卷积=频域相乘), 而为了满足傅里叶变换要求, 需要找到连续的正交基对应于傅里叶变换的基. 若拿到了正交基后, 就可以进行卷积操作(在傅里叶域中计算), 得到卷积结果了.

拉普拉斯矩阵恰好满足这些条件.

• 拉普拉斯是半正定实对称矩阵, 对称矩阵一定n个线性无关的特征向量
• 实对称矩阵具有n个特征值,所对应的n个特征向量相互正交
• 半正定矩阵特征值非负.
• n阶实对称矩阵L必可对角化, 且可用正交矩阵对角化。

那可以直接将拉普拉斯矩阵谱分解:

其中是n个特征值构成的对角矩阵,是单位特征向量(列向量)组成的矩阵. 是正交矩阵，满足

所以通过正交基 可以让卷积操作转到傅里叶域中进行, 从而能得到卷积后结果(即包含节点细节特征的输出).

3.3 Graph上的傅里叶变换

卷积定理：函数卷积的傅里叶变换是函数傅立叶变换的乘积，即对于函数 与 两者的卷积是其函数傅立叶变换乘积的逆变换:

直接说结果:

• 表示对 进行傅里叶变换.
• 表示对 进行傅里叶逆变换.
• 故 和 的卷积结果为(Graph卷积公式, 是hadamard product内积运算)

3.3.1 普通信号的傅里叶与逆变换

对于信号 , 其基函数, 传统傅里叶变换为:

逆变换为:

3.3.2 Graph上的傅里叶与逆变换

Graph上 维向量 , 其中 表示拓扑图上节点的特征向量.

拓扑图的拉普拉斯矩阵L的特征向量矩阵为 , 那么特征值 (频率)所对应的特征向量 可作为傅里叶变换中的一个正交基, 计算得到 的傅里叶变换(不考虑复数情况):

3.3.3 Graph的卷积结果

由上面可知, 和卷积核 的傅里叶变换结果 和 (均为列向量), 和   的卷积为 其分别傅里叶变换后的乘积的逆变换, 故Graph卷积公式为如下:

其中 是hadamard product（哈达马积), 即这两个向量进行内积运算(对应元素的乘积).

因为卷积核是自设计(或学习)的,可以将 的傅里叶变换 写成对角形式:

其中 . (这可以理解为每个 提取一种频率上的信息).

所以Graph的卷积结果为(需要设计/学习的参数是 ):

3.4 第一代GCN

论文 Spectral Networks and Locally Connected Networks on Graphs

直接将卷积核 从而让:

但弊端在于:

• 每次前传,都需要计算拉普拉斯矩阵的特征向量矩阵 , 以及 , , 的矩阵乘积, 计算代价高, 是 ;
• 不具有 spatial localization (类似感受野的意思, 这里只能用到 K=1 的邻居.);
• 需要 个参数(卷积核, 来提取各个频率的信息). 拓扑图大时计算量大,参数且多.

3.5 第二代GCN-ChebNet

论文 2016_NIPS_Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

将 用切比雪夫多项式去拟合, 利用Chebyshev多项式去拟合卷积核方法降低复杂度.

图卷积网络 GCN Graph Convolutional Network（谱域GCN）的理解和详细推导

如何理解 Graph Convolutional Network（GCN）？

图卷积网络(GCN)新手村完全指南

定义特征向量对角矩阵的切比雪夫多项式为滤波器：

而 可以通过 Chebyshev 多项式 的 K -th 阶截断展开来进行拟合，　并且 进行scale 使其元素位于 [-1,1]. . (因为原来的 处于 [0,2]). 这样缩放是为了满足 Chebyshev多项式展开的条件:自变量处于[-1,1]之间.

所以最后卷积情况为:

现在整个运算复杂度是, 式子是 K-localized(类比于感受野), 具有局部连接性.

3.6 一阶ChebNet

让GCN火起来的是这篇文章: 2017_ICLR_Semi-supervised classification with graph convolutional networks

当ChebNet一阶近似时, 让 , 那么ChebNet卷积公式简化近似为:

为了限制参数的数量以解决过度拟合, 并最小化每层的计算操作， 1-st ChebNet假设 ,图卷积的定义就近似为（简单一阶模型）：

而 的特征值范围在 [0,2], 所以在深度神经网络中反复使用该算子将导致数值消失或爆炸问题(梯度爆炸或消失问题). 所以引入归一化技巧(renormalization trick):

其中, , 即拓扑图加上自环.

所以论文中的快速卷积公式就是:

其中 是参数 矩阵, 为节点的特征向量. 计算复杂度也大大降低.

那么 ,就具有 维特征(每个节点具有 维特征向量)的 , 以及 个 卷积核参数时,

其中 是卷积核参数矩阵, 且 为新的特征向量. 计算复杂度为

注意, 此时该公式和 [GCN顶点域] 解释中的 [对称归一化] 公式完全一样.

到这里, GCN的原理就算大致介绍完毕了. 下面简略介绍下 一阶ChebNet 以及其他一些GCN论文的应用吧.

4.GCN的应用

4.1 一阶ChebNet的应用

在半监督的节点分类任务中, 可以构建两层的GCN 来完成.

计算邻接矩阵 , 后得到. 每个节点的最后 output 是 维特征向量(对应为   类):

其中 , 是可学习参数, 将标签传给交叉熵就可以让网络进行学习了.

我们看看论文中提供的表格, 加深我们对不同 Propagation (及公式) 的感受.

4.2 学习类别Graph特征与视觉向量对齐 (ZeroShot)

2018_CVPR_Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs

构建知识图谱, 每个节点代表一个类, 利用多层的GCN进行不同类间的信息迁移.

GCN中采用归一化后的 Binary 邻接矩阵. 代码中查得采用对称归一化邻接矩阵, 即传播模式为:

GCN的输入是每类的Word Embedding 向量, 最后一层的输出维度 和视觉向量的维度一致. 通过 均方误差(MSE) 来训练让节点最后的输出和对应的视觉向量相近.

采用的数据集是 Imagenet, 类别间的关系可从Imagenet官网中提取.

4.3 构建加权的密集图_信息传播更广且避免平滑_与视觉向量对齐(ZeroShot)

2019_CVPR_Rethinking Knowledge Graph Propagation for Zero-Shot Learning

简单地叠加普通GCN层虽然能让知识的传播范围增广, 但也容易让节点平滑(稀释了知识), 而降低了性能. 该文章提出一种密集设计的图, 让远距离(但有关系)的节点之间能直接连接进行传播.

简单地说, 以前都是亲兄弟节点才有联系(连线), 如果想让那些表表表亲戚的信息传播过来, 需要叠加GCN层, 这样会导致信息稀释(或说平滑). 而该论文就直接让同一个血缘(或说比较亲的血缘关系)的大家族都有线相连接(设置不同的权重), 那浅层的GCN网络就可以让远方亲戚的信息传播过来.

本文基于节点之间的距离学习权重. 明确利用知识图的层次结构，构建密集连接结构. 节点汇集信息时分为"从祖先辈获得的信息"和"从子孙辈获得的信息"阶段.

由于传播时文中定义"先从子辈汇聚信息", 再从"父辈汇聚信息", 所以本文的GCN传播为:

定义表示可学习参数来获得ancestor 和 descendant的权重, K 表示 K -hops的距离. 那么就可以让边的权重

重新修改GCN传播方式:

训练时的步骤为:

• 第一步, 训练图卷积网络DGP, 让其来预测CNN最后的FC层权重(即对齐视觉向量), 用均方误差.
• 第二步, 让DGP预测值替代FC的视觉权重, 从而微调CNN网络.

4.4 GCN网络的改进-残差结构与扩张卷积

2019_CVPR_Oral_Can GCNs Go as Deep as CNNs?

CNN的成功的一个关键因素是能够设计和训练一个深层的网络模型。但多层 GCN 会导致提取消失, 导致定点过度平滑, 让顶点特征值收敛到一致的值, 导致目前 GCN 架构都非常浅. 而且,浅层GCN 的感受野有限.

故本文借助CNN的概念, 把 Residual, Dense connections (残差,密集连接) 和 dilated convolutions(扩张/空洞卷积) 应用到GCN架构中.

几种结构

残差结构中, 通过逐点加法, 让节点(经过GCN得到的)残差特征, 加上节点原来的特征, 作为最后的节点新特征:

遇到维度不一致问题, 则跟残差网络一样进行转换(用GCN). 那么密集连接类似上述公式一样处理.

扩张卷积中, 每个GCN层后用 Dilated k-NN去寻找扩张邻居, 并构建扩张图, 在训练时采用随机扩张的方式(按概率进行扩张聚合). 其他细节的从CNN类比过来即可.

GCN的聚合函数

一般GCN中的聚合函数是 sum aggregator, 将邻域信息直接相加, 而同时也有 mean aggregator(和sum相像,归一化后的sum), max-pooling, attention, LSTM 等等聚合方式.

本文采用的是 简单无参数的max-pooling顶点特征聚集器. GCN结构是带BN+ReLU 的MLP.

Dynamic Edgs

GCN在训练中, 图结构一般是保持不变的. 有研究表明, 与具有固定图结构的GCN相比，动态图卷积可以更好地学习图的表示.

让节点的边动态变化, 能 有助于缓解过度平滑问题, 也能产生较大的感受野. 本文中每一层特征空间中通过 Dilated k-NN 来重新计算顶点之间的边, 来动态变化拓扑图.

虽然有改进, 但是计算成本较高.

4.5 GCN的改进-图注意力网络GAT

2018_ICLR_Graph Attention Networks

GCN局限有: 难处理动态图; 难分配不同的权重给不同的neighbor.

其实GAT是GNN的改进, 与GCN类似, 只是它是基于self-attention的图模型.

本文: 对不同的相邻节点学习分配相应的权重, multi-head多头的Attention结构, 计算注意力系数

对于顶点 , 逐个计算它的邻居和之间的相似系数:

即先用共享参数 对顶点进行增维, 后拼接(concatenate)两个特征, 通过映射函数 将高维特征映射到一个Attention实数上.

通过对 的邻居进行softmax, 就可以得到(学习出)节点间的关系系数:

加权求和 aggregate

一般来说,聚合方式一般将邻居传来特征进行加权求和, 即可更新本节点的特征:

本文中增强了集合的方式, 采用 K 个注意力机制, 即用了K种邻居加权方式, 来更新本节点特征. 即Attention中的multi-head思想:

---

欢迎指正讨论 ~