图卷积

图卷积 Graph Convolution

Posted by aptx1231 on February 14, 2021
字数统计:3092 | 阅读时长:9min

图卷积

图卷积网络Graph Convolutional Network,简称GCN。

G=(V,E)是图,图中有N个节点,每个节点有F维特征,输入图信号可以表示为XN×F 的矩阵。图的结构可以表示为邻接矩阵AN×N ,图的度矩阵为D是一个对角矩阵,对角线的元素等于邻接矩阵每一行的和。

拉普拉斯算子 Δ/2

拉普拉斯算子(Laplace Operator)是n维欧几里得空间中的一个二阶微分算子,定义为梯度f的散度。即Δf=2f=f=div(gradf),假设f是n维函数,Δf=Σi2f2x2i

1612788628697

拉普拉斯算子推广到图上:

1612788664006

图拉普拉斯矩阵

普通的拉普拉斯矩阵

定义:L=DA

1612787278541

其中deg(vi)表示节点i的度。

1612787252081

对称归一化的拉普拉斯 (Symmetric normalized Laplacian)

1612787336763

随机游走归一化的拉普拉斯 (Random walk normalized Laplacian)

??D-1*L还是D-1*A

1612787370545

泛化的拉普拉斯 (Generalized Laplacian)

1612787394727

拉普拉斯矩阵的半正定性

证明过程针对普通的拉普拉斯矩阵 L=DA

  • 拉普拉斯矩阵首先一定是一个实对称矩阵
  • 拉普拉斯矩阵也是半正定矩阵

1612787505681

【首先证明L可以写出Incident Matrix矩阵的乘积,即L=T,然后取非0向量x,证明xTLx0恒成立即说明L是半正定矩阵(PSD)。xTLx=xTTx=(x)T(x)(x)是一个向量,所以$x^TLx =   \nabla x   ^2​\nabla​110\Sigma(x_i-x_j)^2​$,半正定得证。】

根据半正定性,有如下结论:

  • L有n个非负的实数特征值(包括重根)。
  • L有n个线性无关的实数特征向量。
  • 存在由所有特征向量(需要进行归一化和正交化)构成的正交矩阵U,使得UTLU=Λ(相似对角化),其中Λ是L的特征值构成的对角矩阵。
  • 进一步可以推导出:L=UΛUT
  • U=[u1,u2,,un]Rn×n,任意的​ui都是​L的特征向量,也就是满足​Lui=λiui的值,其中​λiL的特征值。由于L是实对称矩阵,所以U是正交矩阵,满足UTU=UUT=I
  • Λ是特征值构成的对角矩阵:1612789014602

图卷积

傅里叶变换

1612789310251

卷积定理

1612789379566

1612789396390

1612789404193

图的傅里叶变换/逆变换

eiωt称为傅里叶基 fouries basis,它是拉普拉斯算子的特征函数:

1612789482835

推广:

  • 拉普拉斯算子对应于图的拉普拉斯矩阵L
  • 频率ω对应于拉普拉斯矩阵的特征值​λ
  • 傅里叶基eiωt对应于特征向量u。(U=[u1,u2,,un]Rn×n

图的傅里叶变换(傅里叶基是UT

1612789844044

即:

1612790528928

图的傅里叶逆变换(傅里叶基是U

1612789894426

即:

1612790559386

图的卷积定理

原始的卷积定理:

1612790486803

推广:

1612790496240

作为图卷积的filter函数g,我们希望具有很好的局部性,可以把g定义成一个拉普拉斯矩阵的函数g(L)

作用一次拉普拉斯矩阵相当于在图上传播了一次邻居节点。

1612790734068

所以得到图卷积公式:

1612790834718

gθ(Λ)的计算需要先计算拉普拉斯矩阵的特征值,比较复杂,使用Chebyshev多项式进行近似计算:

1612790972867

1612791097373

解释方法2:

1612854883102

K=1λmax=2

1612791256955

【下边这步不是完全相等的转换!】

1612791344275

图卷积

图卷积网络结构的定义:H(l+1)=f(H(l),A)

其中输入层H(0)=XN×F,输出层H(L)=ZN×FL是层数。

不同的GCN模型采用不同的f(,)函数。

(1)层级传导

f(H(l),A)=σ(AH(l)W(l)),直接用AH矩阵相乘,然后通过权重矩阵W(l)做线性变化,经过非线性激活函数σ(),即可以得到当前层的输出,即下一层的输入H(l+1)

通过矩阵乘法,快速将相邻的节点的信息相加得到自己下一层的输入。

AN×NHN×F,矩阵乘法就是A的每一行乘以H的每一列。A的第i行代表节点i的邻接点信息,相邻则为1,不相邻则为0;H的第j列代表这N个节点的第j个维度的特征。相乘求和,则与i不相邻的点的特征为0,相邻的点的特征被加到了一起,成为了输出矩阵中第i个点的第j维度的特征。

(2)矩阵添加自环

定义:˜A=A+I ,因为在(1)的做法中,由于邻接矩阵A的对角线全0,矩阵AH相乘只考虑了周围节点,而为考虑自己本身,所以在A的基础上,补充对角线全1即可。

(3)矩阵归一化

由于矩阵相乘,会导致矩阵的值越来越大。所以可以对邻接矩阵进行归一化,使得其每一行的和为1,这样AH相乘得到的就是加权的结果,但是数值不会变得越来越大。

归一化方法1:每一行除以这一行的和即可。

A=D1A,即Aij=AijDii

归一化方法2:对称归一化。

A=D12AD12,即Aij=Aijdidj

【这对应的就是不同的拉普拉斯矩阵】

(4)最后的结果

同时应用(2)和(3):

f(H(l),A)=σ(ˆD12ˆAˆD12H(l)W(l))

其中ˆA=A+IˆDˆA的度矩阵,ˆD12ˆAˆD12则对ˆA进行了对称归一化。

参考

  • https://zhuanlan.zhihu.com/p/107162772
  • https://zhuanlan.zhihu.com/p/54505069
  • https://zhuanlan.zhihu.com/p/124727955
  • https://www.cnblogs.com/shiyublog/p/9785342.html
  • http://www.huaxiaozhuan.com/%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0/chapters/11_GNN.html
  • https://davidham3.github.io/blog/2018/07/23/structured-sequence-modeling-with-graph-convolutional-recurrent-networks/

转载请标明如下内容:

本文作者:姜佳伟

本文链接:https://aptx1231.github.io/2021/02/14/%E5%9B%BE%E5%8D%B7%E7%A7%AF/

Github:aptx1231