0%

GNNs - 图神经网络学习笔记

参考AAAI 2020的Tutorial——Graph Neural Networks: Models and Applications以及一些资料来读论文,学习图神经网络领域知识。

GNNs - 图神经网络学习笔记

0 链接

Graph Neural Networks: Models and Applications, AAAI 2020 Tutorial

1 研究背景

相当多的数据是图/图谱(graph)结构的,如:

  • 社交图谱;
  • 传输图谱;
  • 大脑图谱;
  • 网页图谱;
  • 分子图谱;
  • 基因图谱。

一系列的实际问题都需要对图谱进行处理、特征提取和表征,例如:

  • 链路预测;
  • 节点分类;
  • 社区检测;
  • (网页)排序。

传统的深度学习方法所能处理的数据都是简单网格或序列,例如:

  • 通过CNNs处理固定尺寸的图像/网格;
  • 通过RNNs处理文本/序列。

然而图谱是由节点和边组成的,其形式是多变的:

  • 各个节点的邻域节点数量各不相同;
  • 图谱有着复杂的拓扑结构;
  • 图谱也不存在固定的节点序列。

因此,图神经网络(Graph Neural Networks)被提出以解决这些问题。

2 理论基础

2.1 基本图论

Basic Graph Theory

2.1.1 图和图信号

图(Graph)$G$由节点(Vertices)集合$V$和边(Edges)集合$E$组成,形式化为:

图信号

那么,图信号(Graph Signal)可形式化为映射$f$:

即,映射$f$把每一个节点$v$映射为一个$d$维实数向量:

2.1.2 图的矩阵表示

度矩阵

度矩阵(Degree Matrix):

在此例中:

邻接矩阵

邻接矩阵(Adjacency Matrix):

在此例中:

拉普拉斯矩阵

拉普拉斯矩阵(Laplacian Matrix):

在此例中:

2.2 谱图理论

Spectral Graph Theory

拉普拉斯矩阵可作为差分算子(difference operator),即:

可以理解为节点$i$与邻接节点的一阶距离之和。

拉普拉斯二次型(Laplacian quadratic form)可以表达图信号$f$的“平滑程度”(smoothness)或“频率”(frequency):

公式推导可参考:谱聚类方法推导和对拉普拉斯矩阵的理解

可以理解为每对邻接节点之间信号的二阶距离。

  • 低频和高频图谱信号;
  • 低频图信号中,每个图节点的信号接近,意味着图信号变化平缓,即周期长,在频域中低频多,高频少;
  • 高频图信号中,每个图节点的信号相差较大,意味着图信号变化剧烈、频繁,即周期短,在频域中,高频多,低频少。

拉普拉斯矩阵是一个实对称半正定矩阵(a real symmetric positive semidefinite matrix),所以拉普拉斯矩阵满足:

  • 一定有$N$个线性无关的特征向量;
  • 特征值一定非负;
  • 特征向量相互正交(特征向量组成的矩阵为正交矩阵)。

因为特征向量组成的矩阵为正交阵,所以满足:$U^T = U^{-1}$。因此,特征值与特征向量的公式$L u_i = \lambda_i u_i$的矩阵形式 $L U = U \Lambda$可以转换为: $L=U \Lambda U^{-1} = U \Lambda U^T$,即拉普拉斯矩阵的特征分解。

通过拉普拉斯矩阵的特征分解(Eigen-decomposition of Laplacian Matrix),拉普拉斯矩阵具有一个完整的正交特征向量集合$U \in \mathbb{R}^{N \times N}$和特征值对角矩阵 $\Lambda \in \mathbb{R}^{N \times N}$ :

拉普拉斯矩阵的$N$个非负实数特征值,满足非递减性质:

拉普拉斯矩阵特征分解的个正交特征向量集合,即可作为该矩阵空间的正交基。每一个特征向量就代表一个基方向上的信号。把这个特征向量代入上述的计算信号频率的拉普拉斯二次型公式,正好可以推得特征向量的”频率“就是该特征向量对应的特征值:

因此,在该特征分解中,特征向量 对应的特征值$\lambda_i$被称为 $u_i$ 的频率(frequency)。

2.3 图傅里叶分析

Graph Fourier Analysis

2.3.1 图信号的傅里叶分解

信号$f \in \mathbb{R}^N$可以通过图傅里叶级数(Fourier series)进行表示:

其中,$u_i \in \mathbb{R}^N$表示图傅里叶模式(Fourier mode),在图傅里叶变换中是图谱拉普拉斯矩阵的特征向量;$\hat{f_i} \in \mathbb{R}$表示图傅里叶系数(Fourier coefficient),通过图傅里叶变换取得。

图信号的傅里叶分解指的是用$N$个傅里叶模式向量,加权求和,表示图信号。

2.3.2 图傅里叶变换

图傅里叶变换(Graph Fourier Transform, GFT)指的是将图信号从空域(spatial domain)中的空域信号$f$变换到频域(spectral domain)中的频域信号

其中,表示频率,表示图节点。

频域信号实际上是傅里叶模式的权重,例如:是傅里叶模式对应的权重,称为傅里叶系数。在此处的公式中,该傅里叶系数的计算原理实际上就是内积距离(相似度),即:,傅里叶系数 实际上是傅里叶模式与空域信号$f$之间的相似度。

小结:图傅里叶变换将图信号$f$转换为了正交基上的一组权重系数

2.3.3 逆图傅里叶变换

既然图信号$f$能够通过正交基上的一组权重系数进行表示,那么通过这组系数重新对正交基加权求和,显然可以逆变换回去,还原出空域的图信号$f$。

逆图傅里叶变换(Inverse Graph Fourier Transform, IGFT)指的是将图信号从频域$\hat{f}$变换回空域$f$:

小结:逆图傅里叶变换以$\hat{f}$作为正交基$U$上的权重系数对正交基向量进行加权求和,变回了原始空域信号$f$。

3 模型

3.1 概述

图神经网络的目的在于解决图结构数据上的问题,而图结构数据的研究问题可分为两类:

  1. 节点级(Node-level):链路预测、节点分类等;
  2. 图谱级(Graph-level):图谱分类等。

相应地,图神经网络模型中主要包含两类操作:

  1. 滤波(Filtering):取得节点表征(Node Representation),用于解决节点级任务;
  2. 池化(Pooling):降维取得图谱表征(Graph Representation),用于解决图谱级任务。

当然,在神经网络中还需要包含必要的激活(Activation)操作。

图滤波操作不改变图结构和节点数量,而是对图节点的特征向量进行变换,起到优化节点特征的作用。

图池化操作会改变图结构和节点数量,池化操作减少了图中的节点数量,生成了一个更小的图,通常也伴随着特征向量的变换。

3.2 GNN中的滤波

图神经网络模型的研究主要关注于图神经网络中的滤波操作。

图卷积操作主要分为两类:

  • 频域GNN(Spectral-based GNN)
  • 空域GNN(Spatial-based GNN

3.2.1 频域滤波

首先,理解矩阵特征值与特征向量。

从Interactive Linear Algebra一书中,给出了清晰的可视化解释,

不难看出,$Av=\lambda v$体现的意义是,$Av$是和$v$的同方向向量,长度是$v$的$\lambda$倍。因此,特征向量$v$是$A$空间中的一个方向分量,而$\lambda$则体现了该方向向量$v$的在变换矩阵$A$中的重要性、权重。

具体地,在GNN频域滤波的语境中,基于谱图理论中拉普拉斯二次型的计算,特征值$\lambda_i$被解释为相应特征向量$v_i$的“频率”(frequency)。

因为拉普拉斯矩阵既可以表示图(graph)的特征(包含节点的度和邻接关系),又是实对称矩阵能够具备良好的特征分解性质,因此把图通过拉普拉斯矩阵进行表示。在拉普拉斯矩阵的特征分解$L=U\Lambda U^T$中,取得了特征向量组成的正交基和特征值组成的对角矩阵

其中,对应特征值小,即“不重要”/“权重低”的特征向量被解释为“低频分量”,该特征向量表示的信号分量与整体信号相关性小,因此相邻节点之间,该信号分量波动不大,比较平滑,记录的是图中笼统的信息(信号整体的高低);而对应特征值大,即“重要”/“权重高”的特征向量被解释为“高频分量”,该特征向量表示的信号分量与信号波动的相关性高,因此相邻节点之间,该信号分量波动大,相对也就不平滑,记录的是图中细节的信息(节点之间的信号波动差异)。

所谓频域滤波,就是根据频率决定是保留还是滤除该分量。例如:高通滤波(high-pass)就是滤除低频分量,通过高频分量;低通滤波(low-pass)就是滤除高频分量,通过低频分量。

具体地,在GNN的频域滤波语境中,滤波器就可以形式化为:

表示输入代表频率的特征值$\lambda_i$,根据该输入,输出滤波后的权重。

例如,高通滤波就可以通过以下示例来表述:

整体来看,对正交基$U$中的特征向量$u_i$,频域滤波的全过程形式化为:

对所有信号$f \in \mathbb{R}^N$,频域滤波的矩阵形式化为:

输出的滤波后的信号为$f^{(filtered)} \in \mathbb{R}^N$。

根据矩阵乘法的计算顺序,从右往左依次为:

  1. 傅里叶变换:对信号 $f$ 进行傅里叶变换,取得相应于傅里叶模式 $u_i$ 的傅里叶系数 (或 );
  2. 滤波:傅里叶变换得到了傅里叶模式 $u_i$ 的傅里叶系数 ,那该傅里叶模式(即特征向量)是不是我们想要保留的呢?通过滤波,就可以根据该傅里叶模式(即特征向量)对应的频率(即特征值)进行滤波 (或);
  3. 逆傅里叶变换:将滤波过的傅里叶系数 乘以对应的傅里叶分量(特征向量),逆傅里叶变换为滤波过的空域信号(或)。

推广:推广到多通道信号的情况,每个节点信号均为维向量(通道)的$N$个节点的图谱,即输入的空域图谱信号,频域滤波类似地可形式化为:

输出的滤波后的信号为。也就是说,频域滤波不仅对信号进行了滤波,还可以调整输出的每个节点的信号维度()。

分析滤波器参数规模:不难发现,从一个通道到另一个通道的频域滤波(即上图的一个箭头)对应一个滤波器。那么,从个通道到个通道的滤波变换,就需要有个滤波器,每个滤波器为对角阵,包含$N$个参数。因此,该频域滤波的滤波器参数规模为

3.2.2 空域滤波

空域滤波的概念比较符合人的直觉,就是以节点在空域中的邻接节点作为其邻域,对该邻域做加权求和(卷积)即可。基于邻域的空域滤波可形式化为:

遍历节点$j$的邻域,对领域中的的每一个节点$i$,都通过空域滤波器$F \in \mathbb{R}^{N \times N}$来对节点$i$的信号进行滤波。通过对邻域内的所有节点信号进行滤波加权平均,取得节点$j$的空域滤波结果。

对滤波结果,往往通过激活函数进行非线性变换,以及通过池化进行进一步处理,形式化为:

3.2.3 具体模型

3.2.3.1 GNN

【空域滤波】

Scarselli F, Tsoi A C, Gori M, et al. Graphical-based learning environments for pattern recognition[C]//Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR). Springer, Berlin, Heidelberg, 2004: 42-56.

图神经网络的概念最早由Franco Scarselli等人于2004年提出。

Scarselli等人在后续的论文中又反复研究了图神经网络的理论及应用。

Scarselli F, Yong S L, Gori M, et al. Graph neural networks for ranking web pages[C]//The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI’05). IEEE, 2005: 666-672.

Scarselli F, Gori M, Tsoi A C, et al. The graph neural network model[J]. IEEE Transactions on Neural Networks, 2008, 20(1): 61-80.

首次提出的GNN将graph映射到一个实数向量,具体分两种:

  1. graph-focused: 关注图结构,而无视涉及到的节点属性;
  2. node-focused: 根据节点属性将图映射到向量。

最早的GNN的核心思想是,用一个实数向量$x_n$来表示节点$n$的状态(state)。

该状态向量$x_n$取决于其领域中的信息,包含:

  1. $n$的标签;
  2. $n$的连接边的标签;
  3. $n$的邻居节点的状态向量和标签。

具体计算公式为:

在该式中,节点$n$的状态取决于:

  1. $l_n$,节点$n$的标签(Label);
  2. $x_u$,邻居节点$u$的状态;
  3. $l_u$,邻居节点$u$的标签。

显然,节点$n$的状态是通过对节点自身以及邻域节点的信息进行滤波取得的,属于空域滤波。

3.2.3.2 Spectral Graph CNN

【频域滤波】

Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

这篇论文主要研究如何把CNN用到图谱的处理上去。可以理解为这是第一代的GCN。

可以说是GCN的早期研究。论文给出了两种滤波方式,分别对应空域滤波和频域滤波。

论文写的在我看来写得比较晦涩,而且公式琢磨着总感觉有小错误,原理可以参考上述3.2.1和3.2.2分别介绍的频域滤波和空域滤波,是一致的。

在这篇论文中,滤波器就是简单地套上了拉普拉斯矩阵的特征值(加了层非线性变换激活函数),作为初代设计,比较简单粗暴,仅仅使用参数$\theta$来近似滤波器函数:

展开表示,就是:

此处的$\theta \in \mathbb{R}^{N}$是模型的可学习参数。

这种滤波器设计相当于是为每一个节点都计算一个频域滤波值。

不难看出,每个滤波器(卷积核)包含$N$个参数,这个$N$取决于数据规模,一旦节点规模很大,滤波器的参数量就会跟着很大。如果要实现输入 的频域滤波,就需要的滤波器参数规模。

缺陷

1.滤波函数近似效果差

2.滤波器完全依赖于训练时的图谱,无法迁移变通,每一个滤波值都是和对应节点绑定的;

3.模型参数规模庞大,因为一个图谱的节点数量往往是很大的。

3.2.3.3 ChebNet

【频域滤波】

Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in neural information processing systems. 2016: 3844-3852.

这篇论文主要研究在把CNN用到图谱的频域滤波的基础之上,如何改进滤波器的设计。可以理解为这是第二代的GCN。

ChebNet中,首先定义使用的拉普拉斯矩阵不再是基本的$L=D-A$,而是规格化(normalized)拉普拉斯矩阵,即:

使用多项式函数近似滤波器函数

所谓多项式(阶),就是:

通过多项式来近似滤波器,作为滤波器,形式化表示为:

由于通过多项式函数来近似滤波器,参数就只有个,即,在模型训练过程中被优化。这意味着卷积核(滤波器)的参数规模不再受数据规模影响。每个滤波器个参数,意味着从个通道到个通道的滤波映射,需要的参数规模。在实践中,相较于是大大减小了。而且,滤波器参数与节点数量$N$脱钩,还使得训练出的滤波器,使用上不再仅限于当前图谱,而是可适应图谱节点数量、图谱结构的变化。

而且巧的是,使用这个滤波器来滤波傅里叶变换的频域信号,特征值矩阵和特征向量矩阵相乘,刚好就还原了拉普拉斯矩阵(),也就是说——不需要再计算拉普拉斯矩阵特征分解了,一下子减少了计算代价。频域滤波过程推导如下:

解释一下,因为$U$是正交阵,满足$U^T = U^{-1}$,所以此处涉及的数学原理是:

可见,对于多项式形式的滤波器,拉普拉斯矩阵的特征分解刚好被还原了,所以只需要计算拉普拉斯矩阵的幂就可以了。

另外,拉普拉斯矩阵$L$体现的是图节点之间的直接的邻接关系,而$L^K$则体现了图节点之间的$K$跳内的连通关系。因此,意味着计入了从1跳到K跳的节点间联通关系。这使得多项式参数滤波器能够准确地将滤波作用定位于半径为$K$跳的邻域范围内。

使用切比雪夫多项式近似滤波器函数

以上解释了多项式滤波器相较于简单的参数滤波器的好处,ChebNet则是把一般多项式替换为了切比雪夫多项式

在输入参数上,ChebNet对切比雪夫多项式的输入参数$x$进行了缩放(scale)处理。因为当时,切比雪夫多项式$T_k(x)$满足三角函数表达式。这个数学性质使得切比雪夫多项式的值域能够稳定在上界为1,下界为-1的区间内,即使得

数学参阅:2011 Wavelets on graphs via spectral graph theory

具体地,在ChebNet中,切比雪夫多项式的输入参数$\tilde{\Lambda}$是一个缩放对角阵:

该$\tilde{\Lambda}$是对拉普拉斯特征值对角阵$\Lambda$进行缩放的结果,将特征值从缩放至$[-1,1]$以满足上述性质。

这样一来,滤波器$\hat{g}(\Lambda)$被修改为

其中,$k$阶切比雪夫多项式定义为:

切比雪夫多项式是递归定义的多项式,它的初始项

同样地,切比雪夫多项式虽然是递归定义的,但代入展开后也是一种多项式,也满足一般多项式所具备的省去矩阵特征分解的计算代价、K跳局部性的特性。

将该滤波器代入频域滤波函数,可推得:

其中,$\tilde{L}$是对拉普拉斯矩阵的缩放结果:

延伸问题:为什么要用切比雪夫多项式呢?

以下示例参阅:

Hammond D K, Vandergheynst P, Gribonval R. Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150.

数学理论由来参阅:

Geddes K O. Near-minimax polynomial approximation in an elliptical region[J]. SIAM Journal on Numerical Analysis, 1978, 15(6): 1225-1233.

涉及到数学层面的分析,大概的感性理解是,一般多项式在系数变化时,扰动大,而切比雪夫多项式更加抗扰动。尤其是目标函数变化比较平缓时,切比雪夫多项式要平缓的多,近似误差小得多。

对$f(x)$目标函数的$n+2$个采样点 进行近似时,极小极大近似算法(minimax approximation algorithm),典型代表如:Remez algorithmRemez exchange algorithm可以使得$n$阶多项式对目标函数实现minimax近似(最小化最大误差,使$n+2$个采样点的最大误差最小化),形式化为,解线性方程系统:

其中是多项式的多项式系数。

如图:

  • 左图(a)中,黑色表示目标函数,为小波核函数$g(\lambda)$,蓝色表示截断切比雪夫展开式(truncated Chebyshev expansion),红色表示minimax多项式近似。
  • 右图(b)中,表示的是两个近似函数,即截断切比雪夫展开式和minimax多项式,与目标函数的近似误差。

左图(a)中,近似函数与目标函数看起来“相交”的地方,就是采样点位置,经过近似计算,这些采样点的位置的近似误差很小。而采样点之外的地方,近似函数和目标函数可能高度拟合,也可能出现大幅震荡(参考数值计算中的“龙格现象(Runge phenomenon)”)。

进一步查看右图(b)不难发现,以2011年这篇论文研究的小波核为例,截断切比雪夫展开式(蓝色)的最大误差只比真正的minimax多项式(红色)略大一点。但是,在目标函数变化比较平滑的部分,截断切比雪夫展开式的近似误差比minimax多项式的近似误差要低得多。因为其近似出的多项式函数更加平滑,不像minimax多项式那样频繁大幅震荡。

3.2.3.4 GCN

【频域滤波】

Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

Graph Convolutional Network (GCN)

本文提出图卷积网络,实际上并不算是第一个图谱上的卷积网络。上述的Spectral Graph CNN和ChebNet等工作都是图卷积网络的研究工作。

本文的GCN主要是对ChebNet进行了一系列简化和改进。

简化改进的目的,是为了建立深层的神经网络,即,简化每一层的计算复杂度,从而让深层的图卷积成为可能。

如上文所述,ChebNet通过切比雪夫多项式来近似滤波器函数$\hat{g}(\Lambda)$,已经推得了:

其中,

本文的GCN所作出的具体的改变为:

简化1:一阶切比雪夫多项式及系数约束

GCN将切比雪夫展开式限制为1阶,即$K=1$,则滤波器函数表示为:

对于一阶切比雪夫多项式,GCN还增加了限制条件,限定,使参数只剩一项。滤波器函数表示为:

简化2:特征值约束

GCN将特征值的最大值限定为2,即

这样的约束使得缩放拉普拉斯矩阵$\tilde{L}$进一步简化为:

简化到这一步,基于以上限制条件,完整的滤波函数可推得:

简化3:重规格化技巧

作者提出了一项重规格化技巧(renormalization trick),使得滤波计算进一步简化。该技巧形式化为:

其中,,度矩阵基于邻接矩阵计算,也改为

经过该技巧的进一步简化,GCN每层的滤波函数就变为:

最终形式

GCN可以用于多通道的信号处理,对于从个通道的输入信号到个通道的输出信号的滤波映射,GCN的一层可形式化为以下矩阵形式:

其中:

  • 表示频域滤波前的输入信号;
  • 表示个滤波的参数;
  • 表示频域滤波后的输出信号。

由此,就可以建立多层的GCN网络,以2层的GCN网络为例:

其中,

GCN可以用于实现半监督学习,即,以有标签的节点来计算损失,进行训练。具体的,论文中基于有标签节点计算交叉熵损失:

其中,是有标签的节点序号集合。

实验评价

本文设计的GCN做出的简化到底有没有意义呢?从实验结果来看,简化整体上提升了实验效果。

相比其他模型,GCN在几个数据集上的分类准确率结果均为领先,而且速度更快。

3.2.3.5 GraphSage
3.2.3.6 GAT
3.2.3.7 MPNN

3.3 GNN中的池化

3.3.1 gPool

3.3.2 DiffPool

3.3.3 Eigenpooling

3.4 GNN的鲁棒性

Robustness of GNN

3.5 GNN的扩展学习

Scalable Learning for GNN

4 应用

4.1 医疗保健

4.2 自然语言处理

4.3 推荐系统

支持我的写作!