日期:2020年11月25日    0

概述

因为最近需要用到图卷积网络,所以需要对图神经网络做一个了解,之前也老听说GNN,GCN啥的,但是一直没有深入了解,借此机会,深入学习和理解了一下。

图神经网络涉及的内容非常多,我也不可能面面俱到,这篇文章也不打算做全面科普和讲解的目的,而是把自己的一些理解总结出来,至于很多在网上可以查到的资料,我只给出引用即可,不深入讲解,除非觉得有必要。

文章,主要是讲讲一下内容:

  • 图、图神经网络的基本概念
  • 图上如何做卷积和池化
  • 卷积的两种:频谱卷积和空间卷积
  • 常见的图卷积网络(注意不是图神经网络,那个范畴更大,我用不到,暂时也不做深入研究)
  • 给出我收集的资料

先给定一个图的基本概念:

$G=(V,E,W)$

  • V 是节点(vertex)集合,其中节点用一个d维向量表示,$n=|V|$
  • X 是节点的向量矩阵,就列就是一个节点的表示,$X \in R^{n \times d}$
  • E 是边(edge)集合
  • W 是邻接矩阵(方阵),矩阵里的值,就是边的权重,$W \in R^{n \times n}$

可以把每个节点当做是一个信号(看,和信号处理勾稽上了)。

图神经网络的用途

好,有了图的基本概念,我们就会想,能拿拿图干嘛?

  • 一个网络,我最终给这个网络一个分类
  • 一个网络,我对网路中的每个节点进行分类(社交网络中的标签分类)
  • 一个网络,我通过局部网络的结构(已知的标注网络)学习出另外部分的网络结构(如预测一个节点和别人的链接情况)(是否用来做OCR布局分析?)
  • 还可以和GAN结合,用于生成一个网络结构(分子制药生成分子式)

你可以看出,其实主要焦点是在整体,还是个体上,整体就是整个大网的表示学习,个体就是每个节点的表示学习,我目前关注GNN,就是想把它应用到OCR的布局分析中,比如把bbox(识别的文字框)当做一个个的节点vertex,然后看他们彼此的关系如何?也就是有无链接?他们自己是什么分类?这样,我就能找出哪些bbox是标题,还是值,他们是否在一行,等等,这样的业务含义,从而满足商业需求。

图卷积

一个图,如何做特征抽取,我们自然而然就想象到过去我们最擅长的卷积神经网络(CNN):

类比CNN

咱们学习CNN,先通过表示学习,学习出图的内在特征,然后用它做分类啥的。是的,没错。你为何会有这么一个思路,因为这个思路就是你过去CNN图像卷积神经网络的思路啊,把图像的特征抽取出来,然后做分类啥的。

好,我们看CNN,我们的两大法器就是卷积和池化,当然核心是卷积,那么这套思路是不是可以套到图神经网络上呢?

答案是,可以的,如下图,图上也可以做卷积完成特征抽取,然后做池化,缩小网络结构,当然,不是说的那么简单,这个后面我会逐一解释,这里先直观有个印象即可。

这里,我自己有个疑问,也算是给自己挖个坑:在做卷积的时候,网络中变化的是什么?是每个节点上的表示么?表示的维度为变么?网络的结构会在变么?我知道池化肯定会变的,这种先不考虑呢?我说的变是整个结构都发生根本变化。这些问题,我提给自己,未来自己来把坑填上。

接下来说说卷积,

CNN只适合欧式空间,比如图像。而基于图(Graph)GNN更通用,适合非欧空间(啥叫欧式空间,就是支持距离公式的空间。) 可是,现在,我还是需要做卷积、池化,我改如何做?

现在问题变成了:图神经网络最核心的就是要解决卷积的问题,卷积最核心的就是卷积核如何确定。

先说说卷积

在讨论图(Graph)如何做卷积之前,我们有必要讨论一下,究竟什么是卷积?

本质上卷积核,是对在过滤不同频率的信号。参考。 你看卷积公式$h(t) = \int_{+\infty}^{-\infty} f(\tau)g(x-\tau) dt$,

参考:视频22分钟处。

  • 对应上图:$f(\tau)$就是右侧那个下降函数,$g(x-\tau)$是方波函数,而卷积结果(是个以时间$\t$为变量的函数)是左侧那个上升函数
  • $h(t)$是一个以$t$为变量的函数,是的,他是个时间函数
  • 设想某个$t=t_0$,$h(t_0)$就是那上图中黄色面积
  • 这个面积是一个积分,是$\tau$从$-\infty ~ +\infty$的积分,上图上,就是黄色的面积

那么问题又来了,卷积有啥用?

其实,卷积本质是为了在频域空间的不同频率信号的过滤,原因是,时域卷积=频域相乘,这个是傅里叶变换的结论,细节我会在傅里叶变换的博文中详解,这里只知道结论就可以。你用一个滤波器函数$g(x)$去和你的目标函数$f(x)$做卷积,就相当于是把他们放到了频率里,进行相乘,相乘的结果,就相当于在频率里把某些频段的值给“乘”掉了(理解这个可以参考下面参考问斩各种的方波滤波器的概念),只剩下了你所需要的频段的信号了。

时域卷积=频域相乘,卷积核本质上是一个二维函数,有对应的频谱函数,因而可以看成某种『滤波器』

参考

那么,把这个概念扩展到二维函数上,也就是图像上,图像可以看做是一个二维离散函数。 图像上的分类,其实就是图像上的信号处理。 那么我们来对应一下卷积的概念。 $f(x)和g(x)$的x,对应整个图像的二维位置(x,y),$f(x)$对应图像的值,$g(x)$就是对应的卷积核,时间$t$对应的就是卷积目标feature map上的一个点。你的卷积核,一个一个位置的挪动,就是在计算目标函数$h(t)$。看看,都对应上了吧!

可是,我们又要想,为何要做图像的卷积?

答案是,为了提取图像不同频率的信息。啥?!图像又不是波,怎么会有频率?有的!图像实际上可以看成是一个由不同的点上的值变化,所组成的一个东西。不同的点(二维),对应不同的值,这就是一个函数啊。既然是函数,就可以按照傅里叶变换,变换到频率里。这么说的太数学化,不好懂。你可以换个思路理解,就是像素间变化剧烈,比如从红色突然变成了白色,或者从255的值,突然变成了0,这种变化多剧烈啊!这就是高频啊。反之,就是低频啊。

图上的卷积

注:以下理解均来自这篇很赞的图卷积的知乎解释贴,感兴趣的可以参照阅读。

图片上可以做卷积(CNN),我们理解了,那么问题又来了?一个图(Graph)上,如何做卷积?

前面我们说了,卷积,其实就是一种滤波器,就是把图像变换到频域,然后用某个卷积核来过滤出某个频段的特性。那么,我们同样的思路,把图上的信息,变换到频域里面,然后在里面做相乘,从而过滤出某个频段的信息。这种思路就是频域卷积,论文里都称作谱域卷积(spectral domain)。

当然,我们还可以沿袭CNN的思路,但是和CNN不同,图上不具备欧式空间的平移不变性,那该如何在空域(或者说时域)上做卷积呢?这个正是空(间)域卷积(spatial domain/vertex domain)研究的内容。

谱域卷积

初始概念

最早的图卷积,是杨力昆(Yann LeCun)老师的团队们2014年就琢磨出来的,很诡异的频域卷积:

原始论文: Bruna - Spectral Networks and Locally Connected Networks on Graphs

【1、图上的拉普拉斯分解】

图上的拉普拉斯,

$L=D - W$

  • W上面提到了,就是边上的权重,是一个对称方阵,$W \in R^{n \times n}$
  • D呢?我看很多文章是都说图的节点的度的对角阵,但是实际上D的定义是:$D_{ij}= \sum_j W_{ij}$。

这里不得不说一下,网上的狠多文章都是不考虑边权重的图,或者说,权重是1,但是如果是边带不同权重的,就需要用上述公式来确定矩阵D,即一个边出度上的边的权重之合。

拉普拉斯矩阵是对称阵,所以是半正定的,所以特征值都是非负的,所有有n个线性无关的特征向量。拉普拉斯的特征值分解,通过相似对角化,就可以得到一组基:

通过相似对角化,得到的一组特征向量彼此都是彼此正交的,你可以认为是一组正交基。用它就可以表达一个新的坐标系出来,

拉普拉斯矩阵正交分解后:

\[L = U \begin{pmatrix} \lambda_1 & & \\ & \ddots & \\ & & \lambda_n \end{pmatrix} U^T\]

【2、图上的频域傅里叶变换】

你可以把这组由特征向量构成的正交基,类比成傅里叶变换中的不同频率,也就是不同的基,通过这组基,就可以把时域,(论文里有时候叫vetex domain)转化到频率空间里面去(spectrum domain),然后在频率里做卷积,也就是滤波,滤完后,在变换回时域(vetex domain)。

类比傅里叶变换:

  • $f$是Graph上的N维向量
  • $f(i)$就是第$i$个节点的向量表达
  • $u_l(i)$就是第$l$个特征向量的第$i$维度的值
  • $\hat f(\lambda_l)$,就是到了频域后,这个频率$\lambda_i$对应的值。

【3、频域上的卷积】

上面只是说,图上如何做频域(spectrum domain)和时域(vertex domain)的转换,但是,其实对我们更重要的是卷积。

我们现在需要在频域内,设计卷积核通过这个卷积核的学习,可以让你学习出最优的对时域(vertex domain)中每个节点的向量表达,用这些向量表达,就可以完成分类,或者关系预测啥的了。

具体怎么做呢?

我们假设我们的卷函数在时域内叫$h$(卷积核叫啥$h$啊!TMD,论文就这么叫的,我们也叫把,一般h都表示隐层啊),是个n维度向量,和节点的向量表达维数已知。

然后我们也要把这个$h$变换到频域里去,用上面的一样的方法:$\hat h(\lambda_l)=\sum_{i=1}^N h(i)u_l(i)$

这样,我们的原始数据特征变换到频域的$\hat f$,和刚刚变换到频域的卷积核$\hat h$,可以做卷积了。

我们上面先说说卷积已经讨论过了,时域上的卷积,就相当于频域的点积,所以,卷积这个操作就变成了:

$\hat f \odot \hat h = U^T f \odot U^T h $

$\odot$ 是Hamada积,表示逐点相乘

如果再变换回去,就需要再乘以$U$,所以整个卷积过程便是:

$(f*h)_G = U( (U^T f) \odot (U^T h))$

【5、迭代起来】

你用图上的节点们的表示$h_i$,做了一个卷积(是在频域里做的),你考虑了图的结构(就是那个$U$,他是通过邻接矩阵、出入度得到的),可是,这个只是做了一次卷积。

过我们过去要用多个卷积核,卷完一层,再卷一层,变成有给深层网络,对吧?那么这里,图卷积,如何和这个形式对照起来呢?

  • 多参数,我觉得好像是没有,这个网络里,就一组参数,就是$g_\theta$
  • 多层网络,这个有,就是学完后,每个节点上的隐含表达更新了,那下一轮再重复这个过程,我理解就算是“下一层”了
  • 如何更新参数?还是梯度下降啊,那也必须得有损失函数loss啊。这个,肯定是要依赖于下游任务了,比如节点分类,节点关系预测啥的。

这里有个小地方,必须得说一声,否则后面ChebNet的时候就该搞不清楚了:

为什么卷积核是一个有N(节点数)个参数的对角阵?

$h$是卷积核,对吧,长啥样?其实不用关心,因为卷积,不像之前的CNN(是在时域上做的),现在变到了频域上去了,所以你现在应该关心的是,频域上的卷积核长啥样?

它的本来面目,还记得不?是$(U^T h)$,对,就是这个样子,其实,就是一个N维度的向量,对吧?

他然后要和$f$(原始数据)做$\odot$:$U( (U^T f) \odot (U^T h))$,对吧?

好,那我直接把他从一个N维向量,变成一个$N \times N$的矩阵,然后$\odot$操作,就可以写成矩阵乘法啦。

所以,现在卷积核,就变成一个对角阵了。

好!我们终于解释了我们自己提出的问题,“为何是个对角阵?”:是因为,我们把$\odot$操作变成了矩阵乘法。别看这个问题小,愚笨的我还是想了半天才想明白的。

然后,这个$(U^T h)$,实际的长相是:

\[\begin{pmatrix} \theta_1 & & \\ & \ddots & \\ & & \theta_n \end{pmatrix}\]

对,就是这个样子,这个就是参数,是神经网络要去学习的东东。

这里再絮叨一句,这个卷积核,后来在ChebNet的时候,被诡异、神奇、创新的替换成了特征根$\lambda_i$的切比雪夫多项式了

【4、可以深度学习了】

上面的式子里,$h$是我们的卷积核,就是我们要学习的参数,终于可以用个深度网络来学习这些参数了。

不过,原始论文里,

他做法更粗暴的,直接把$U^T h$ => $g_\theta$,原有的式子也变成了:

$(f*h)_G = U( g_\theta \odot (U^T h))$

然后,最后再放一个非线性变换,就是最后的神经网络的前项公式了:

$(f*h)_G = \sigma( U( g_\theta \odot (U^T h)))$

【它的问题】

这个方法有很多很多问题,比如:

  • 他得要求这个Graph节点数不能变,因为上述公式中的$U$是特征向量,你的节点一变,拉普拉斯矩阵就变了,你的$U$就得重新求了
  • 你学的参数$g_\theta$,是个N维度,跟你节点数一样的啊,你节点数一遍,参数个数都得变啊
  • 还有,这个卷积核$g_\theta$是跟整个图相关的,原因是它和整个图的特征分解相关啊,这样,他也不是局部化的,你说非局部化有啥不好?我理解是,你没法像传统CNN那样,通过一个小卷积核,通过局部的卷积操作,可以学出整个图的特征。

不好,不好那就改吧,这就引出了ChebNet,切比雪夫图网络:

改进

还记得上面说过吧,现在参数,是这个样子:

\[g_\theta = \begin{pmatrix} \theta_1 & & \\ & \ddots & \\ & & \theta_n \end{pmatrix}\]

ChebNet,来了个神奇的操作,把$g_\theta$变成了关于特征值n次$\lambda_i$的多项式:$g_\theta(\Lambda)$

\[g_\theta(\Lambda) = \begin{pmatrix} \sum_{j=0}^K \theta_j \lambda_1^j & & \\ & \ddots & \\ & & \sum_{j=0}^K \theta_j \lambda_n^j \end{pmatrix}\]

即:$g_\theta(\Lambda)=\sum_{j=0}^K \theta_j \Lambda^j$,你说这个K是啥?其实就是拍脑袋定的一个超参,他在后面推导出来的结论里有体现,即某个节点的K个hop的邻居的,具体是拉普拉斯矩阵$L^K$体现出来的。

注:利用了对角阵N次方等于对角线元素的N次方的性质。

好,接下来,骚操作来了:

卷积:

\[(g_\theta * x)=> \\ U\sum_{j=0}^K \theta_j \Lambda^j U^T x \\ = \sum_{j=0}^K \theta_j (U \Lambda^j U^T) x \\ = \sum_{j=0}^K \theta_j (U \Lambda U^T)^j x \\ = \sum_{j=0}^K \theta_j L^j x \\\]

这么改进后,不用做特征值分解啦,啦啦啦啦啦啦啦,$L$是拉普拉斯矩阵。

牢记原始谱方法的两个问题:

  • 特征分解、特征向量求取麻烦
  • 卷积核是全局相关的

ChebnetNet

【参考】

先自己给自己提了一个问题,“为什么要用切比雪夫多项式?这个多项式替换了啥?”

我先提纲挈领地自问自答一下:

  • 既然上面创新性的用一个特征值n次多项式替换了参数,

    ChebNet,来了个神奇的操作,把$g_\theta$变成了关于特征值n次$\lambda_i$的多项式:$g_\theta(\Lambda)$

咱先把目标列出来:

  • 得降维吧!过去图多大,参数$g_\theta$就多少维度,不好!现在咱们得想办法给他降到一个固定的低维。
  • 别全局相关,最好只考虑局部的特征就能学出全图来,这样,我不用全图信息,也能学出全图,比如通过采样啥的

来吧,我们搞搞看:

切比雪夫多项式

有必须要先学习一下切比雪夫展开式!参考:视频文章

我的理解是:他是一个借助$cos,argcos$,得到的一个多项式展开方法,这个多项式有一些神奇的特性,可以被用来解决最值问题啥的。

稍微推导一下切比雪夫多项式的由来:

他尝试展开$cos(\theta),cos(2\theta),cos(3\theta),… $

他观察到,展开式都是:$\sum Acos^n(\theta)$ 的样子,也就是$cos(\theta$的n次方,和前面有个系数$A$:

\[cos(\theta) = cos(\theta) \\ cos(2\theta) = 2cos^2(\theta) -1 \\ cos(3\theta) = 4cos^3(\theta) - 3cos(\theta) \\ cos(4\theta) = 8cos^4(\theta) - 8cos^2(\theta) + 1\]

然后,可以观察猜出(当然人家老人家也证明了):

最高项的系数,也就是$cos(4\theta) = 8cos^4(\theta) …$中的这个$8$,是$2n-1$,这里$n=4$.

接下来,做一个变形,令$x=cos(\theta),x \in [-1,1]$,也就是$\theta=arc cos(x)$,切比雪夫余弦展开,就变成了一个多项式展开了:

\[g(x) = cos(\theta) = cos( arc cos(x)) \\ g(x) = cos(2\theta) = cos( 2arc cos(x)) \\ g(x) = cos(3\theta) = cos( 3arc cos(x)) \\ g(x) = cos(4\theta) = cos( 4arc cos(x))\]

这里$g(x)$就表示,是一个$x,x \in [-1,1]$的多项式,现在x就是$cos(\theta)$啊。

然后,然后我们得到了一个$g(x) = cos(n arc cosx)$,这个$g(x)$形式上就是一个$x$的多项式,这个多项式背后,就是一个$cos(x)$的展开式。

它还有个神奇特性,就是可以高阶多项式,可以通过低阶多项式,递归推出,比如$cos(3\theta)$可以通过$cos(2\theta)$推出,而$cos(2\theta)$又可以由$cos(\theta)$推出,对应到多项式也是一样的,g_n(x),也就是最高项为$x^n$的多项式,可以由$x^{n-1}$的多项式递归推出,具体的公式如下:

Chebyshev多项式的递推公式: $g_{n+1}(x) = 2xg_n(x) - g_{n-1}(x)$

那么,接下来,我的问题是:为何要用这么一个诡异的多项式,去替换GCN中的$g_\theta$参数?说实话,我真心没懂,是因为一组正交基的组合,可以通过多项式去拟合么?我偶然看到说,切比雪夫多项式是“以递归方式定义的一系列正交多项式序列,难道说,这里的特征向量,就是一组正交基,他们的线性表达,恰好可以被这样的多项式可以逼近?不知道,好希望有人能给我讲讲啊。

后来看到这篇,多少给出了一些答案:

$p(x) = \sum_{n = 0}^{3} a_nT_n = a_0 T_0(x)+a_1 T_1(x)+a_2 T_2(x)+a_3 T_3(x)$,

$p(x)$是我们造出来的最高项为3次方的多项式,去拟合题目中给的4个点$(1,1),(2,3),(3,5),(4,4)$,把$x$带入进去,就可以递归的推出$T_i(x)$,结果$y$你也知道,剩下的就是解一个线性方程,求出这些待定系数$a_i$了。

也就是说,你用切比雪夫多项式,去逼近你的那些需要拟合的点。为何要这么样做呢?因为这样的拟合可以防止龙格现象,且,这样的逼近是一个“多项式在连续函数的最佳一致逼近”(其实这个我也不太懂?难道是说,这样的逼近方法最优?算了,先不研究了,继续…)

好吧,我假装,我对这里面的关系和原理已经深刻理解了(未来会的,哈哈哈),那么,我接下来看,如何应用切比雪夫多项式展开,到GCN的优化当中去吧!

前戏有点多哈…….

ChebNet

回忆一下,$g_\theta(\Lambda)=\sum_{j=0}^K \theta_j \Lambda^j$,这个是之前,骚操作,生生憋出来的神经网络参数:$g_\theta(\Lambda)$。

现在

$g_\theta(\Lambda)=\sum_{j=0}^K \theta_j \Lambda^j \rightarrow \sum_{j=0}^K \theta_j T_k(\hat \Lambda)$

这样做完,会有啥影响呢?我们来回忆一下,当初这个$g_\theta$怎么创造出来的:

ChebNet,来了个神奇的操作,把$g_\theta$变成了关于特征值n次$\lambda_i$的多项式:$g_\theta(\Lambda)$

\[g_\theta(\Lambda) = \begin{pmatrix} \sum_{j=0}^K \theta_j \lambda_1^j & & \\ & \ddots & \\ & & \sum_{j=0}^K \theta_j \lambda_n^j \end{pmatrix}\]

看,每一项,其实都是一个关于$\lambda_i$的K次多项式:$g(\lambda_1) = \theta_1 \lambda_1 + \theta_2 \lambda_1^2 + \theta_3 \lambda_1^3 + … + \theta_K \lambda_1^K$,这个是一个多项式函数,对吧?现在,我再来个骚操作,就是我用一个切比雪夫多项式,去逼近这个多项式函数:

\[g(\lambda_1) = \theta_1 \lambda_1 + \theta_2 \lambda_1^2 + ... + \theta_K \lambda_1^K \rightarrow \\ = \theta_1 T_0(\lambda_1) + \theta_2 T_0(\lambda_1^2) + ... + \theta_K T_0(\lambda_1^K) \\ T_i(\lambda_1) 就是切比雪夫递归式项\]

这个只是$lambda_1$,我们对整个$Lambda$做变换:

\[(g_\theta * x) \\ = U \sum_{j=0}^K \theta_j \Lambda^j U^T x \\ \approx U \sum_{j=0}^K \theta_j T_j(\Lambda^j) U^T x \\ 因为Chebyshev多项式作用在对角矩阵上,不会影响矩阵运算\\ 那就改变一下运算顺序,先把矩阵运算放进去 \\ = \sum_{j=0}^K \theta_j T_j (U (\Lambda^j) U^T) x \\ = \sum_{j=0}^K \theta_j T_j (L) x \\\]

OK! 现在再观察这个式子:$(g_\theta * x)=\sum_{j=0}^K \theta_j T_j (L) x$,$L$是已知的,而$T_j(L)$,也可以递归推出,那剩下的就是需要梯度下降求解的参数$\theta_j$了,而且,计算复杂度也降下来了,只要递归推一下$T_j$既可以,是$O(n)$复杂度的了。

这里,其实是有纰漏的,你如果看superbrother的推导,他的结果是:$(g_\theta * x)=\sum_{j=0}^K \theta_j T_j (\hat L) x$,注意到了么?拉普拉斯矩阵从$L$变成了$\hat L$,这个$\hat L$是什么鬼?

原因是出在,切比雪夫展开,要求$x$的定义域必须是$[-1,1]$,为了满足这一点,要让$\lambda$们的值,都要在这个范围内,要对矩阵$\Lambda$做变形:

\[\hat L = \frac{2}{\lambda_{max}} L - I\]

其中最大特征值$\lambda_{max}$可以利用幂迭代法(power iteration)求出,具体我也没去深究了,感兴趣,可以看看superbrother给出的链接

参考切比雪夫递推式:

Chebyshev多项式的递推公式: $g_{n+1}(x) = 2xg_n(x) - g_{n-1}(x)$

可以得到:

\[T_0(\hat L) = I \\ T_1(\hat L) = \hat L \\ T_j(\hat L) = 2T_{j-1}(\hat L) - T_{j-2}(\hat L)\]

崩溃了么?

如果没有,强!我稍微总结一下:

  • 我们要模仿CNN的卷积,为何我们要做卷积呢?我们是为了做不同信号的滤波。
  • 可是图网络不具备空间不变形,所以呢,只好把卷积核设计到了频域里。参照傅里叶变换,我们用拉普拉斯矩阵的特征向量,当我们的正交基,来做变换。
  • 这样下来,需要做特征值分解,且,卷积核不具备局部性,只好改进。
  • 改进的方法是先生生憋出一个基于特征值的多项式,来替换频域的参数$\theta$
  • 然后,在进一步,用切比雪夫多项式,来逼近这个特征值的多项式

至此,完成了图神经网络最核心的频域的骚操作,终于让基于频(谱)域的图卷积得以实现了。

GCN

你以为完了么?骚年,天真的很呐!还要简化,简化到死!这次是对切比雪夫多项式再简化,只取,0阶和1阶的展开。参考:Graph Convolutional Networks:从卷积到GCN论文:《Semi-Supervised Classification with Graph Convolutional Networks》

这个便是GCN的来历,不够我吐槽一下,这个名字有些无耻,因为所有这些方法其实都是图卷积(Graph Convolutional Network),人家都没好意思占用这个“大名字”,你居然就注册成商标了,呵呵。

正如上面说的,还要简化,我们一起来推导:

\[(g_\theta * x) = \\ \sum_{j=0}^K \theta_j T_j (L) x \\ \approx \theta_0 x + \theta_1(\hat L) \\ = \theta_0 x + \theta_1(\hat L) \\ = \theta_0 x + (\frac{2}{\lambda_{max}} L - I) x \\ \lambda_{max} \leqslant 2(这个我也没深究,是可以证明的) \\ \approx \theta_0 x + \theta_1(L - I) x \\ = \theta_0 x + \theta_1(L - I) x \\ = \theta_0 x + \theta_1( D^{- \frac{1}{2}} W D^{-\frac{1}{2}} ) x \\ 这个是拉普拉斯矩阵的对称归一化的拉普拉斯矩阵 \\ 然后,再简化一下,令\theta_0 = -\theta_1,上式继续简化,\\ = \theta(I_n + D^{-\frac{1}{2}} W D^{-\frac{1}{2}} ) \\ 由于谱半径[0,2]太大,归一化一下(为何做这步?没搞明白)\\ = \hat D^{-\frac{1}{2}} \hat W \hat D^{-\frac{1}{2}}\\ 其中,\hat W = W + I_n, \hat D_{ij} = \sum_j \hat W_{ij}\]

最终,

我们得到:\(\underbrace{g_\theta * x}_{\mathbb R^{N \times 1}} = \theta( \underbrace{ \hat D^{-\frac{1}{2}} \hat W \hat D^{-\frac{1}{2}}}_{\mathbb R^{n \times n}} ) \underbrace{x}_{\mathbb R^{n \times 1}}\)

这里有一些需要说明的,$x$居然是$n$维度的,$n$是节点数,出乎意料把,这个原因是,

参考

$x$就是graph上对应每个节点的feature构成的向量,$x=(x_1,x_2,…,x_n)$ ​,这里暂时对每个节点都使用标量,相当于channel为1。

把$x$扩展到多维$C$去,$x \in \mathbb R^{N \times 1} \rightarrow X \in \mathbb R^{N \times C}$,$N$是节点数,$C$是节点上的维度表示,$X$变成整个图的特征矩阵(包含了所有的nodes)。随之参数也从$\theta \in \mathbb R \rightarrow \Theta \in \mathbb R^{C \times F}$,$F$为卷积核个数。

最终,公式表达为:

\[\underbrace{Z}_{\mathbb R^{N \times F}} = ( \underbrace{ \hat D^{-\frac{1}{2}} \hat W \hat D^{-\frac{1}{2}}}_{\mathbb R^{N \times N}} ) \underbrace{X}_{\mathbb R^{N \times C}} \underbrace{\Theta}_{\mathbb R^{C \times F}}\]

GCN已经把谱域家族荣耀到极致了,但是,他仍然是不完美的:

GCN的缺点也是很显然易见的:第一,GCN需要将整个图放到内存和显存,这将非常耗内存和显存,处理不了大图;第二,GCN在训练时需要知道整个图的结构信息(包括待预测的节点)

后面,我们来填这2个坑。

空域卷积

上面终于谈完了谱域(Spectral)卷积啦,现在我们可以说说空域(Spatial)卷积了。

空域卷积,对我们这些正常人来说,可能更好理解。就是得有个卷积核,过去是和图片卷积,现在是要和图卷积了,过去是在图片上,卷积核形状是固定的,现在是不固定的了,如何解决不固定问题,就是要解决的问题啦。当然还有池化,也是需要解决的问题。还可以引入注意力模型,恩,这些都是可以类比的了。

GraphSAGE

参考:

Inductive(归纳) learning和Transductive(直推) learning的概念?就讨厌玩概念,Inductive,就是从局部的图推演出整体的图特性,就是用图上某些有限的节点和关系,学习出整个图上泛化特性。而Transductive就得用整个图的信息才可以,前面的那一堆谱方法,都是用所有的节点,即使是最简化的GCN,也需要所有的节点信息($\underbrace{X}_{\mathbb R^{N \times C}}$ 里的N,就表明是所有的节点)。

正如前面谈及GCN的不足的时候提及到的,很多时候,你是不可能用所有的图的节点这么折腾的,比如社交网络中10亿+的节点数,这得多少大显卡才跑的开啊。而且,你是知道邻接矩阵的的,也就是你知道这个图的所有节点间的关系。但是,现实中,很多情况,连关系可能也是要学习和探索的。

GrachSAGE(Graph Sample and Aggregate)就是为了解决GCN的上面说的两个问题:

GraphSAGE是这样玩的:对每一个节点,随机采样他的K跳近邻,采样出一颗子图(其实是个树吧?),然后使用一个聚合函数(这个函数得设计),分K层依次聚合,就跟消息传递似的,一直从边缘传播到中心,更新这个节点的embeding表示。

【咋采样?】

采用一个叫“定长抽样”的方法,固定当前节点的邻居数为$S$,然后采用有放回的重采样/负采样方法达到,保证每个节点(采样后的)邻居个数一致,这样做是为了训练时候批次一样。

【这里参数是啥?】

你不是定义了K跳/层邻居(K-hop)了么?所以你就有K个参数,每个参数是应该是$\matbb R^D$,而不是个矩阵,不过应该有K个,每层一个。然后,每一个邻居,都要先和这个$W$相乘,然后聚合(聚合有3种方式,后面提),然后逐层向中心聚拢。每一层(第k层)共享一个相同的$W_k$,大家都用这一个$W$。

【咋聚合?参数呢?】

就是如何根据周边的节点,算出当前目标节点的更新后的embeding值。(你看,其实图结构没变),一共有三种方式:Mean、LSTM、Pooling。(这块没细看,需要再看,大致明白就成)。

【损失函数】

如果是有监督的情况下,可以使用每个节点的预测lable和真实lable的交叉熵作为损失函数。如果是在无监督的情况下,可以假设相邻的节点的embedding表示尽可能相近。

【GraphSAGE得到了啥】

它是得到了每个node的embeding的向量,然后你可以单个取出一个向量来,去做分类、预测啥的了,每个node有个语义表示啦!

【GraphSAGE的缺点】

GraphSAGE也有一些缺点,每个节点那么多邻居,GraphSAGE的采样没有考虑到不同邻居节点的重要性不同,而且聚合计算的时候邻居节点的重要性和当前节点也是不同的。这个就需要下面介绍的GAT(Graph Attention Networks)来解决喽。

GAT

开源项目

pytorch的那个项目

开源的那个

参考

文档

视频

【目前看过的】

【待学习的】