图卷积网络
@
图卷积网络的概述
图神经网络的核心工作是对空间域(Spatial Domain)中节点的Embedding进行卷积操作(即聚合邻居Embedding信息),然而图数据和图像数据的差别在于节点邻居个数、次序都是不定的,因此传统用于图像上的CNN模型中的卷积操作(Convolution Operator)不能直接用在图上,因此需要从频谱域(Spectral Domain)上重新定义这样的卷积操作再通过卷积定理转换回空间域上。
为了在频谱域和空间域中转换,我们借助了傅里叶公式
,并且定义了图上傅里叶变换
(从空间域变换到频谱域)和图上傅里叶逆变换
(从频谱域回到空间域)的变换公式。具体操作是我们将节点的Embedding f(i), i ∈ (1,⋯,N)通过傅里叶正变换从空间域变换到了频谱域\(\hat{f}\),在频谱域上和卷积核h进行卷积操作,再将变换后的节点Embedding通过傅里叶逆变换回到空间域,参与后续的分类等任务。
循环图神经网络
状态更新与输出
最早的图神经网络是基于一个不动点理论。给定一张图\(G\),每个结点都有自己的特征
(节点的特征用\(x_v\)来表示),而且连接两个结点的边也有自己的特征
(边的特征使用\(x_{(v,u)}\)来表示结点\(v\)与结点\(u\)之间的边的特征)。GNN 的学习目标就是获得每个结点的图感知隐藏状态
\(h_v\)。GNN通过迭代式更新所有结点的隐藏状态来实现,结点\(v\)的隐藏状态按照如下方式更新:
公式中的\(f\)就是隐藏状态中的状态更新函数,又叫局部转移函数。其中的\(x_co[v]\)表示与结点\(v\)相邻的边的特征,\(x_ne[v]\)表示结点\(v\)的另据节点的特征,\(h^t_ne[v]\)表示邻居结点在t时刻的隐藏状态。
![o_image-2-state-update-function](https://gitee.com/Jason66661010/imagecloud/raw/master/img/20210406165732.png)
例如上图,假设结点5为中心结点,其隐藏状态的更新函数如图所示。
除了状态更新函数,还需要一个局部输出函数\(g\),如图。
在 T1 时刻,结点 1 的状态接受来自结点 3 的上一时刻的隐藏状态,因为结点 1 与结点 3相邻。直到 Tn 时刻,各个结点隐藏状态收敛,每个结点后面接一个 g 即可得到该结点的输出 o。
对于不同的图来说,收敛的时刻可能不同,因为收敛是通过两个时刻p范数的差值是否小于某个阈值\(\epsilon\)来判定的,如
不动点理论
GNN的理论基础就是巴拿赫不动点定理。我们用\(F\)表示若干个\(f\)堆叠得到的一个函数,也称为全局更新函数,则图上所有结点的状态更新公式可以写成:
不动点理论指的是,无论\(H_0\)是什么,只要\(F\)是一个压缩映射,\(H_0\)经过不断迭代都会收敛到某一个固定的点
,我们称之为不动点
。那压缩映射又是什么呢,一张图可以解释得明明白白:
上图的实线箭头就是指映射\(F\),任意两个点\(x,y\)在经过\(F\)这个映射后,分别变成了\(F(x),F(y)\).压缩映射就是指\(