图神经网络的“前世今生”

2021-02-04 15:16:35 浏览数 (1)

作者 | 俞壹龄 编辑 | 李仲深

  • GNN的前世今生 Humility
  • 简介
  • GNN的分类
    • 网络Embedding与GNN的异同
  • GCN
    • 从CNN到GCN -- 卷积算子的泛化
    • 谱域卷积算法
    • SCNN-- 谱图卷积理论的直接应用
    • ChebNet-- 利用切比雪夫多项式对谱图卷积理论的近似
    • GCN -- 在ChebNet基础上更进一步的简化
    • 空域卷积方法
    • ConvGNN
    • GraphSAGE
    • 其他
  • GAT
  • GAE
  • GGN
  • GSTN
  • 附
    • 图网络基准数据集
    • 经典图网络实现
  • 参考文献
  • 代码实现

GNN的前世今生

简介

从图像分类, 视频处理到语音识别, 自然语言处理. 深度学习通过端到端的训练彻底改变了很多机器学习任务. 但是这些任务的数据都是欧式空间上的规则数据. 而现实中很多数据之间都有着相当复杂的关系, 一般表现为非欧空间之上的图结构.

为处理图数据之上的任务, 图神经网络就应运而生了.

GNN的分类

  1. GCN -- 图卷积神经网络
    1. 谱域
    2. 空域
    3. 池化模型
  2. GAT -- 图注意力网络
  3. GAE -- 图自编码器
  4. GGN -- 图生成网络
  5. GSTM -- 图时空网络

图一: GNN的分类

网络Embedding与GNN的异同

网络embedding旨在在保留网络拓扑结构和节点信息的基础之上, 在低维向量空间之中对网络节点进行表示.

得到的嵌入向量可以用于后续的各类任务.

网络embedding的方法可以大体分为如下三类 :

  1. 矩阵分解
  2. 随机游走
  3. 深度学习

其中第三点深度学习的方法需要使用GNN的模型. 可以是GAE, 也可以是无监督的GCN.

GCN

图二: 常见的GNN模型分析

从CNN到GCN -- 卷积算子的泛化

CNN的成功在于他的卷积核能够提取整个数据集上共享的局部特征. 而CNN中卷积算子的定义依赖于图像这种规则数据的平移不变性和局部连结性.

想要在图网络中复制CNN的成功, 泛化和定义新的卷积算子便是一种良好的方案.

图三: 从2D卷积到图卷积

谱域卷积算法

图四: 图卷积发展历史

谱域卷积主要的理论依据是卷积定理 : 时域中的卷积同构与谱域中的乘法. 谱域卷积通过离散傅里叶变换把拓扑图映射到谱域, 然后据此来定义自己的图卷积算子.

主要的模型有SCNN、ChebNet和GCN(按发表时间升序排列). 这三个模型都是基于同一种算法, 可以说是一脉相承的了.

图二:谱域卷积公式图五: 图离散卷积算法

SCNN -- 谱图卷积理论的直接应用

  1. 图结构的刻画 :
L = D - A

(拉普拉斯矩阵)与特征矩阵

拉普拉斯矩阵用于刻画图的结构信息.

易知L是一个非负定矩阵, 对其进行相似对角化处理可得

L = ULambda U^T

其中的

U^T

对应了图中的离散傅里叶变换(具体推导可以参考傅里叶变换和拉普拉斯算子之间的关系).

图中除了用拉普拉斯矩阵刻画的结构信息之外, 还有每个节点上的信息. 这种节点信息我们一般会用特征向量来对人工选择的特征进行量化. 每个节点的特征组合起来就得到了我们的特征矩阵

H^{(0)}

, 也就是最底层的语义. 特征矩阵和拉普拉斯矩阵一起完成了对图中信息的量化.

  1. 卷积定理: 时域中的卷积同构于频域中的乘法

由此我们可以定义

f

与

g

两个函数之间的卷积.

mathcal{F}(f*g) = mathcal{F}(g)·mathcal{F}(f) =>f*g = mathcal{F}^{-1}lbracemathcal{F}(g)·mathcal{F}(f)rbrace
  • 离散形式:
f*g = Ulbrace(U^Tg)(U^Tf)rbrace

为了便于参数的设置和反向传播, 我们取

g_{theta} = diag(U^Tg)

作为卷积核.

这样就给出了文中的卷积公式

  1. 前向传播的公式
H^{(l 1)} = h(UF_kU^TH^{(l)})

其中

F_k

是我们的第k层的卷积层. 他的行数是输入的通道数, 列数为输出的通道数.

ChebNet -- 利用切比雪夫多项式对谱图卷积理论的近似

既然前文中提到的SCNN中特征分解的开销难以接受, 我们可以对其进行近似处理从而简化运算.

ChebNet就是这样一个在SCNN的基础上做了近似处理的网络.

  1. 采用Chebyshev多项式对谱域卷积的卷积核进行插值. 这边是Chebyshev多项式:
T_{n 1}(x) = 2xT_n(x) - T_{n-1}(x)

这里用于多项式插值.

g_theta = diag(U^Tg) stackrel{hat{Lambda} = frac{2}{lambda_{max}} - I_n}{longrightarrow}g_theta(Lambda) = displaystylesum_{k=0}^{K}beta_kT_k(hat{Lambda})

这是利用Chebyshev多项式近似后的卷积核.

  1. 上述插值过程中还有一个小小的trick(你有没有注意到呢?)
hat{Lambda} = frac{2}{lambda_{max}} - I_n

这是一个标准化处理, 将

Lambda

中的特征值全部化到[-1, 1]这个区间内, 旨在避免网络迭代层数过深带来的梯度爆炸问题.

GCN -- 在ChebNet基础上更进一步的简化

GCN在前面ChebNet的基础上再一次进行了简化. 他只取了卷积核Chebyshev插值多项式的前两项, 而且预设了这两项前面的参数相等. 将每个卷积核可学习的参数量降低到了1.

{GCN的卷积核} (x*g_theta)_G = theta(tilde{D}^{-1/2}tilde{W}tilde{D}^{-1/2})x

这就是GCN的卷积核. 其中

theta

就是它可学习的参数.

除了更精简的近似之外, GCN中还有两点trick:

tilde{W}

是在邻接矩阵

A

的基础上加上了自环, 将节点自身的特征也添加到了网络之中.

  1. 对拉普拉斯矩阵
L

的标准化和对称化.

tilde{L} = tilde{D}^{-1/2}Ltilde{D}^{-1/2}

空域卷积方法

谱域卷积基于图谱理论, 具有相当良好的可解释性. 但是谱域上的模型一来只能对整幅图进行处理, 而且无法处理变化的图结构. 这时候空域卷积方法或许是更好的选择.

  • 卷积算子的定义: 采样 聚合. 用于特征提取

ConvGNN

欧式空间上的卷积可以理解为先对固定数量的邻域进行排序, 然后使用卷积核进行内积.

非欧空间之上图结构的卷积也可以参考这种模式.

在这里插入图片描述图六: 图卷积的泛化定义 采样 聚合

  1. 利用随机游走这一马尔科夫过程, 以
k

步之内节点被访问次数的期望进行排序.

  • 以标准化之后的图相似度矩阵
P = D^{-1}S

来作为状态转移矩阵.

  1. 取期望最大的
p

个节点作为

i

的邻域, 按期望由大到小排序.

  1. 使用参数数量为
p

的一维卷积和对邻域进行卷积操作.

图七: 空域卷积网络

GraphSAGE

*SAGE(Sample and AggreGatE)*不同于前面的GNN, GraphSAGE认为卷积是采样加上的信息的聚合.

  • 采样

均匀采样法: 在节点一阶相连的节点上均匀采样, 构建固定大小的邻域.

  • 聚合

GraphSAGE认为节点的邻域中没有顺序可言, 所以要求聚合函数不依赖于邻域节点的输入顺序.

  1. 均值聚合 : 取邻域内节点的均值.
  2. LSTM聚合 : -- 这个真的是顺序无关的吗???
  3. Pooling聚合 : 采用Max Pooling.
h^k_{mathcal{N}(v)}leftarrow AGGREGATE_k({h^{k-1}_u, forall_uinmathcal{N}(v)})

聚合函数

聚合之后还需要结合自身信息然后进行卷积和激活.

h^k_v leftarrow sigma(W^k·CONCAT(h^{k-1}_v, h^k _{mathcal{N(v)}}))

最后进行标准化以防止梯度爆炸和梯度消失.

其他

空域卷积网络还有着各种各样的变体. 诸如LGCN, MoNet之类的, 在此不多赘述.

GAT

都说Attention is all you need.

GAT模型将attention机制引入图卷积模型, 为更重要的节点分配更大的权重.

正常的图卷积神经网络卷积核的参数都是共享的, 这种就是所谓的分心模型. 他预设了输入节点对不同的输出节点的影响是相同的.

但是从我们人的认知模型出发, 输入节点对不同的输出节点影响肯定是不同的. 所以就提出了所谓的Attention机制. 通过每个输出节点上挂载的权值数组来衡量各个输入节点对该输出的重要程度.

图八: 注意力机制中权重的分配

  1. 计算节点之间的关联度
e_{ij} = alpha(Wvec{h_i}, Wvec{h_j})

其中

e_{ij}

为注意力系数, 可以认为它正比于

i, j

两节点的关联度.

  1. 利用softmax归一化, 求得注意力系数.
alpha_{ij} = softmax_j(e_{ij}) = frac{exp(e_{ij})}{sumlimits_{kinmathcal{N_i}}exp(e_{ik})}
  1. 以上文求得的注意力系数作为权重来对邻域节点的信息进行聚合, 完成图卷积操作.
vec{h_{i}^{'}} = fBigg{(}sumlimits_{jinmathcal{N_i}}alpha_{ij}Wvec{h_j}Bigg{)}

其中的

W

是共享的权值, 而真正的差异化的卷积核为

alpha_{ij}W

.

GAE

图九: 自编码器

图自编码器, 一种自监督的学习框架. 通过编码器学习网络节点的低维表示, 然后通过解码器重构图数据.

GAE最早使用GCN来作为编码器.

Z = GCN(X, A)

其中X为节点特征,

A

为图的邻接矩阵.

解码器:

A = sigma(ZZ^{T})

采用变分法进行训练, 最小化变分下界

L
L = Eq(Z|X, A)[logp(A|Z) - KL[q(Z|X)||P(Z)]

近来又提出了一种对抗正则化自编码器(ARGA), 利用GAN的方案训练正则化图自编码器.

编码器用节点的特征编码其结构信息, 也就是GCN中的隐层表示, 然后解码器从编码器的输出中重构邻接矩阵. GANs在训练生成模型的时候在生成和判别模型之间进行一个最小-最大博弈. 生成器尽可能生成真实的“伪样本”, 而判别器则尽可能从真实样本中识别”伪样本“.

图十: 常见GAE总结

GGN

图生成网络, 从数据中获取图的经验分布, 然后根据经验分布来生成全新图结构的网络.

特定领域有很多图网络模型, 比如用于分子图生成的SMILES.

近来提出了一些统一的生成方法, 其中有一部分将图生成看做节点和边的交替生成的过程, 另一部分采用GAN的方案进行训练.

GSTN

图时空网络, 处理时空图的网络. 利用GCN提取空间特征, 然后将时间离散化使用CNN或者RNN来提取时间特征.

图十一: 图时空网络汇总

附

图网络基准数据集

图十二: 基准数据集汇总

经典图网络实现

图十三: 经典图网络实现汇总

参考文献

[[1901.00596] A Comprehensive Survey on Graph Neural Networks (arxiv.org)](https://arxiv.org/abs/1901.00596#:~:text=In this survey, we provide a comprehensive overview,networks, convolutional graph neural networks, graph autoencoders, )

[1710.10903v3] Graph Attention Networks (arxiv.org)

[1801.07455] Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition (arxiv.org)

[1312.6203] Spectral Networks and Locally Connected Networks on Graphs (arxiv.org)

[1706.02216] Inductive Representation Learning on Large Graphs (arxiv.org)

代码实现

见图十三

机器学习 深度学习 人工智能 卷积神经网络 神经网络

0 人点赞