图神经网络基础

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了图神经网络基础，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9541字，纯文字阅读大概需要14分钟。

内容图文

图神经网络基础

最近在学习GCN，看到很多公式都不太懂，和以前看CNN完全不一样，在这里整理一下一些看到的公式和推导，希望能够帮助理解。

首先，为什么要用GCN呢，因为在面对非欧式空间的数据处理时，发现CNN并不能保证平移不变性，因此图网络结构一直被提出用来处理非欧式空间数据；另一方面，CNN的局限性很严重，比如

（1）take all pixels into consideration regardless of importance，CNN处理所有的像素点都相同，没有考虑到不同感兴趣的贡献度，相关的研究方向为attention；

（2）long-range dependency，这也是目前Transformer比较火热的原因，可以学习到None-local的信息。

（3）could not take care of relationship between pixels，CNN只能通过叠加特征图和调整感受野来增加信息，Transformer和GNN都可以将点之间的关系考虑进去。

好了，到此废话不多说，开始进入到GNN的基础。

GNN主要分为两类研究方向：spatial（空间域）、spectral（频域）。

一、基本图的公式：

D ： 入 度 / 出 度 矩 阵 A : 邻 接 矩 阵 （ 0 ? 1 矩 阵 ） L : 拉 普 拉 斯 矩 阵 D： 入度/出度矩阵\\ A: 邻接矩阵（0-1矩阵）\\ L: 拉普拉斯矩阵\\ D：入度/出度矩阵A:邻接矩阵（0?1矩阵）L:拉普拉斯矩阵

L i , j = D ? A = { d v ,  if i = j , ? 1 , i f { v i , v j } ∈  E and i  ≠  j, 0 , o t h e r s L i , j ( s y s ) = { 1 ,  if i = j , ? 1 d u d v , i f { v i , v j } ∈  E and i  ≠  j, 0 , o t h e r s \\ \\ L_{i,j} = D - A = \begin{cases} d_v, \text{ if i = j},\\ -1,if \text{\{$v_i$,$v_j$\}$\in$ E and i $\ne$ j,} \\ 0, others \end{cases} \\ L_{i,j}(sys) = \begin{cases} 1, \text{ if i = j},\\ -\frac{1}{\sqrt{d_u}\sqrt{d_v}},if \text{\{$v_i$,$v_j$\}$\in$ E and i $\ne$ j,} \\ 0, others \end{cases} \\ Li,j?=D?A=??????dv?, if i = j,?1,if{vi?,vj?}∈ E and i ?= j,0,others?Li,j?(sys)=??????1, if i = j,?du? ?dv? ?1?,if{vi?,vj?}∈ E and i ?= j,0,others?

Let T T T denote the denote the diagonal matrix with the ( v , v ) (v,v) (v,v)-th entry having value d v d_v dv?.（实际T就是D）
L i , j ( s y s ) = D ? 1 2 L D ? 1 2 L i , j ( R W ) = D ? 1 L L_{i,j}(sys) = D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\\ L_{i,j}(RW) = D^{-1}L Li,j?(sys)=D?21?LD?21?Li,j?(RW)=D?1L
这里强调几个性质：

（1） L L L是半定对称矩阵，特征值均为非负，实数

（2）特征值为0的次数就是联通区域的个数

（3）最小的特征值为0，因为每一行加和都为0

（4）最小不为0的特征值大小就是图的代数连通度

举例子：

A-B-C
D = [ 1 0 0 0 2 0 0 0 1 ] , A = [ 0 1 0 1 0 1 0 1 0 ] L = D ? A = [ 1 ? 1 0 ? 1 2 ? 1 0 ? 1 1 ] D = \left[ \begin{array}{ccc} 1 & 0& 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{array} \right] , A = \left[ \begin{array}{ccc} 0&1&0\\ 1&0&1\\ 0&1&0 \end{array} \right]\\ L = D - A = \left[ \begin{array}{ccc} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{array} \right]\\ D=???100?020?001????,A=???010?101?010????L=D?A=???1?10??12?1?0?11????

D = d i a g ( 1 , 2 , 1 ) D ? 1 2 = d i a g ( 1 , 1 2 , 1 ) D = diag(1,2,1)\\ D^{-\frac{1}{2}}=diag(1,\frac{1}{\sqrt{2}},1)\\ D=diag(1,2,1)D?21?=diag(1,2 ?1?,1)

L s y s = D ? 1 2 L D ? 1 2 = d i a g ( 1 , 1 2 , 1 ) ? [ 1 ? 1 0 ? 1 2 ? 1 0 ? 1 1 ] ? d i a g ( 1 , 1 2 , 1 ) = [ 1 ? 1 2 0 ? 1 2 1 ? 1 2 0 ? 1 2 1 ] \begin{aligned} L_{sys} &= D^{-\frac{1}{2}}LD^{-\frac{1}{2}} \\ &=diag(1,\frac{1}{\sqrt{2}},1)\cdot \left[ \begin{array}{ccc} 1&-1&0\\ -1&2&-1\\ 0&-1&1 \end{array} \right] \cdot diag(1,\frac{1}{\sqrt{2}},1)\\ &= \left[ \begin{array}{ccc} 1&-\frac{1}{\sqrt{2}}&0\\ -\frac{1}{\sqrt{2}}&1&-\frac{1}{\sqrt{2}}\\ 0&-\frac{1}{\sqrt{2}}&1 \end{array} \right] \end{aligned} Lsys??=D?21?LD?21?=diag(1,2 ?1?,1)????1?10??12?1?0?11?????diag(1,2 ?1?,1)=????1?2 ?1?0??2 ?1?1?2 ?1??0?2 ?1?1??????

L L L可以变成酉相似矩阵
L = U Λ U ? 1 , Λ = d i a g ( λ i , . . . λ n ) L = U \Lambda U^{-1},\Lambda = diag(\lambda_i,...\lambda_n) L=UΛU?1,Λ=diag(λi?,...λn?)

二、图谱理论、随机游走、特征值分析

三、拉普拉斯矩阵和拉普拉斯算子

其实很难理解的是，为什么要这么定义拉普拉斯矩阵？

这里就比较复杂了，我们从拉普拉斯算子讲起。

拉普拉斯算子（Laplacian）是由欧几里得空间中的一个函数的梯度的散度给出的微分算子。常用数学表示形式： △ f = ▽ 2 f \bigtriangleup f = \bigtriangledown^{2} f △f=▽2f。
△ f = ∑ i = 1 n d 2 f d x i 2 \bigtriangleup f = \sum_{i=1}^{n}{\frac{\rm d^2f}{\rm dx_i^2}} △f=i=1∑n?dxi2?d2f?
上面这个公式，如果按照图像二维的方式计算，实际上就是拉普拉斯算子。
△ f = d 2 f d x 2 + d 2 f d y 2 = [ f ( x + 1 , y ) + f ( x ? 1 , y ) ? 2 f ( x , y ) ] + [ f ( x , y + 1 ) + f ( x , y ? 1 ) ? 2 f ( x , y ) ] = f ( x + 1 , y ) + f ( x ? 1 , y ) + f ( x , y + 1 ) + f ( x , y ? 1 ) ? 4 f ( x , y ) \begin{aligned} \bigtriangleup f &= \frac{\rm d^2f}{\rm dx^2} + \frac{\rm d^2f}{\rm dy^2}\\ &=[f(x+1,y)+f(x-1,y)-2f(x,y)]+[f(x,y+1)+f(x,y-1)-2f(x,y)]\\ &=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y) \end{aligned} △f?=dx2d2f?+dy2d2f?=[f(x+1,y)+f(x?1,y)?2f(x,y)]+[f(x,y+1)+f(x,y?1)?2f(x,y)]=f(x+1,y)+f(x?1,y)+f(x,y+1)+f(x,y?1)?4f(x,y)?
即拉普拉斯算子：
[ 0 1 0 1 ? 4 1 0 1 0 ] \left[ \begin{array}{ccc} 0&1&0\\ 1&-4&1\\ 0&1&0 \end{array} \right] ???010?1?41?010????
拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总增益 （或者说是总变化）

不难理解，就是一个梯度变化

上面举例的是二维，这种扰动可以看作是一个像素点向周围变化时产生的收益。

推广到图理论中，可以得到：
△ f i = ∑ j ∈ N i ( f i ? f j ) \bigtriangleup f_i = \sum_{j \in N_i}{(f_i - f_j)} △fi?=j∈Ni?∑?(fi??fj?)
解释一下这个公式的含义，比如对一个节点 i i i 进行扰动，周围的点与该点值的数值差的和，可以类比上面的图像二维的变化，其实图拉普拉斯算子就是一个图微分操作， N i N_i Ni?表示节点 i i i 的近邻点。接下来就好办了：
△ f i = ∑ j ∈ N i w i , j ( f i ? f j ) = ∑ j ∈ N w i , j f i ? ∑ j ∈ N w i , j f j = d i f i ? W i f i \begin{aligned} \bigtriangleup f_i &= \sum_{j \in N_i}{w_{i,j}(f_i - f_j)}\\ &=\sum_{j \in N}{w_{i,j}f_i}-\sum_{j \in N}{w_{i,j}f_j}\\ &=d_if_i-W_if_i\\ \end{aligned} △fi??=j∈Ni?∑?wi,j?(fi??fj?)=j∈N∑?wi,j?fi??j∈N∑?wi,j?fj?=di?fi??Wi?fi??

△ f = ( △ f 1 , △ f 2 , . . . , △ f N ) = ( d 1 f 1 ? W 1 f , d 2 f 2 ? W 2 f , . . . , d N f N ? W N f ) = d i a g ( d 1 , d 2 , . . . , d f ) ? ( f 1 , f 2 , . . . , f N ) ? ( W 1 , W 2 , . . . , W N ) ? ( f 1 , f 2 , . . . , f N ) = d i a g ( d i ) f ? W f = ( D ? W ) f = L f \begin{aligned} \bigtriangleup f &= (\bigtriangleup f_1,\bigtriangleup f_2,...,\bigtriangleup f_N)\\ &= (d_1f_1 - W_1f,d_2f_2 - W_2f,...,d_Nf_N - W_Nf)\\ &= diag(d_1,d_2,...,d_f) \cdot (f_1,f_2,...,f_N) - (W_1,W_2,...,W_N) \cdot (f_1,f_2,...,f_N)\\ &= diag(d_i)f - Wf\\ &= (D-W)f\\ &=Lf \end{aligned} △f?=(△f1?,△f2?,...,△fN?)=(d1?f1??W1?f,d2?f2??W2?f,...,dN?fN??WN?f)=diag(d1?,d2?,...,df?)?(f1?,f2?,...,fN?)?(W1?,W2?,...,WN?)?(f1?,f2?,...,fN?)=diag(di?)f?Wf=(D?W)f=Lf?

从这里我们看到拉普拉斯矩阵就是一个点扰动矩阵，不难看到，这个矩阵将是一些的计算的根源。

四、图卷积推导

从上面我们可以得出结论，节点 i i i 的拉普拉斯矩阵为：
L f ( i ) = ∑ j ∈ N i W i , j ( f i ? f j ) Lf(i)=\sum_{j \in N_i}{W_{i,j}(f_i-f_j)} Lf(i)=j∈Ni?∑?Wi,j?(fi??fj?)
其实对于一个不知道的边 W i , j W_{i,j} Wi,j?，我们可以用一种很简单的方式计算，就可以得到一个有效的结果：
W i , j = { e x p ( ? ( d i s t ( i , j ) 2 ) 2 θ 2 ) 0 W_{i,j}= \begin{cases} exp(-\frac{(dist(i,j)^2)}{2\theta^2 })\\ 0 \end{cases} Wi,j?={exp(?2θ2(dist(i,j)2)?)0?
废话不多说，我们进入到卷积的讲解，不过在此之前，我们先看一下拉普拉斯谱分解

这里有个东西叫亥姆霍兹方程：
▽ 2 f = ? k 2 f , f 为特征函数， ? k 2 为特征值 \bigtriangledown^2f=-k^2f,\text{$f$为特征函数，$-k^2$为特征值} ▽2f=?k2f,f为特征函数，?k2为特征值
即，广义上的特征方程。

考虑到：
▽ 2 e ? i w t = d e ? i w t d t 2 = ? w 2 e ? i w t \bigtriangledown^2e^{-iwt}=\frac{\rm de^{-iwt}}{\rm dt^2}=-w^2e^{-iwt} ▽2e?iwt=dt2de?iwt?=?w2e?iwt
可以看到 e ? i w t e^{-iwt} e?iwt就是拉普拉斯算子的特征函数，所以说离散傅立叶变换是拉普拉斯谱分析的一个特例

反过来看傅里叶变换：
F ( w ) = F [ f ( t ) ] = ∫ f ( t ) e ? i w t d t F(w)=F[f(t)]=\int{f(t)e^{-iwt}dt} F(w)=F[f(t)]=∫f(t)e?iwtdt
这里， e ? i w t e^{-iwt} e?iwt为基函数，这时考虑图的卷积，那对应的基函数就是拉普拉斯矩阵的特征向量
L u k = λ k u k Lu_k=\lambda_ku_k Luk?=λk?uk?
所以，图上的傅里叶变换为：
F ( λ k ) = f k ^ = ∑ i = 1 N f i u k ( i ) f ^ = ( f 1 ^ , . . . f N ^ ) = [ u 1 ( 1 ) . . . u 1 ( n ) . . . . . . . . . u n ( 1 ) . . . u n ( n ) ] ? ( f 1 , . . . f N ) T = U T f F(\lambda_k)=\hat{f_k}=\sum_{i=1}^{N}{f{i}u_k(i)}\\ \hat{f}=(\hat{f_1},...\hat{f_N})= \left[ \begin{array}{ccc} u_1(1)&...&u_1(n)\\ ...&...&...\\ u_n(1)&...&u_n(n) \end{array} \right] \cdot (f_1,...f_N)^T = U^Tf F(λk?)=fk?^?=i=1∑N?fiuk?(i)f^?=(f1?^?,...fN?^?)=???u1?(1)...un?(1)?.........?u1?(n)...un?(n)?????(f1?,...fN?)T=UTf
其中， U U U为拉普拉斯谱分解的正交矩阵。
f = U U ? 1 f = = U U T f = U f ^ f=UU^{-1}f==UU^Tf=U\hat{f} f=UU?1f==UUTf=Uf^?

回到图卷积公式，离散的傅里叶变换公式为：
f ? h [ n ] = ∑ m = ? i n f i n f f [ n ? m ] h [ m ] = F ? 1 [ F ( f [ n ] ) ? F ( h [ n ] ) ] = F ? 1 [ U T f ? h ^ [ n ] ] = F ? 1 [ d i a g [ h ^ 1 , h ^ 2 , . . . , h ^ n ] ? U T f ] = U ? d i a g [ h ^ 1 , h ^ 2 , . . . , h ^ n ] U T f \begin{aligned} f*h[n] &= \sum_{m=-inf}^{inf}f[n-m]h[m]\\ &= F^{-1}[F(f[n])\cdot F(h[n])]\\ &= F^{-1}[U^Tf \cdot \hat{h}[n]]\\ &= F^{-1}[diag[\hat{h}_1,\hat{h}_2,...,\hat{h}_n] \cdot U^Tf]\\ &= U \cdot diag[\hat{h}_1,\hat{h}_2,...,\hat{h}_n] U^T f \end{aligned} f?h[n]?=m=?inf∑inf?f[n?m]h[m]=F?1[F(f[n])?F(h[n])]=F?1[UTf?h^[n]]=F?1[diag[h^1?,h^2?,...,h^n?]?UTf]=U?diag[h^1?,h^2?,...,h^n?]UTf?
这个公式好多人第一眼看着有些快，这里写一下详细步骤：
F [ f ? h ] = [ f ^ ( λ 1 ) f ^ ( λ 2 ) . . . f ^ ( λ n ) ] ? [ h ^ ( λ 1 ) h ^ ( λ 2 ) . . . h ^ ( λ n ) ] = [ f ^ ( λ 1 ) h ^ ( λ 1 ) f ^ ( λ 2 ) h ^ ( λ 2 ) . . . f ^ ( λ n ) h ^ ( λ n ) ] = [ h ^ ( λ 1 ) h ^ ( λ 2 ) . . . h ^ ( λ n ) ] ? [ f ^ ( λ 1 ) f ^ ( λ 2 ) . . . f ^ ( λ n ) ] = d i a g ( h ^ ( λ 1 ) , h ^ ( λ 2 ) , . . . , h ^ ( λ n ) ) ? U T f and,  F [ f ] = U T f \begin{aligned} F[f*h] &= \left[ \begin{array}{c} \hat{f}(\lambda_1)\\ \hat{f}(\lambda_2)\\ ...\\ \hat{f}(\lambda_n) \end{array} \right] \cdot \left[ \begin{array}{c} \hat{h}(\lambda_1)\\ \hat{h}(\lambda_2)\\ ...\\ \hat{h}(\lambda_n) \end{array} \right] = \left[ \begin{array}{c} \hat{f}(\lambda_1) \hat{h}(\lambda_1)\\ \hat{f}(\lambda_2) \hat{h}(\lambda_2)\\ ...\\ \hat{f}(\lambda_n) \hat{h}(\lambda_n)\\ \end{array} \right]\\ &= \left[ \begin{array}{cccc} \hat{h}(\lambda_1)&&&\\ &\hat{h}(\lambda_2)&&\\ &&...&\\ &&&\hat{h}(\lambda_n)\\ \end{array} \right ] \cdot \left[ \begin{array}{c} \hat{f}(\lambda_1)\\ \hat{f}(\lambda_2)\\ ...\\ \hat{f}(\lambda_n) \end{array} \right]\\ &=diag(\hat{h}(\lambda_1),\hat{h}(\lambda_2),...,\hat{h}(\lambda_n)) \cdot U^Tf \end{aligned}\\ \text{and, }F[f]=U^Tf\\ F[f?h]?=?????f^?(λ1?)f^?(λ2?)...f^?(λn?)????????????h^(λ1?)h^(λ2?)...h^(λn?)??????=?????f^?(λ1?)h^(λ1?)f^?(λ2?)h^(λ2?)...f^?(λn?)h^(λn?)??????=?????h^(λ1?)?h^(λ2?)?...?h^(λn?)????????????f^?(λ1?)f^?(λ2?)...f^?(λn?)??????=diag(h^(λ1?),h^(λ2?),...,h^(λn?))?UTf?and, F[f]=UTf

so,  f ? h = U d i a g ( h ( λ i ) ) U T f = U ( U T h ° U T f ) \begin{aligned} \text{so, }f*h &=Udiag(h(\lambda_i))U^Tf\\ &=U(U^Th \circ U^Tf) \end{aligned} so, f?h?=Udiag(h(λi?))UTf=U(UTh°UTf)?

内容总结

以上是互联网集市为您收集整理的图神经网络基础全部内容，希望文章能够帮你解决图神经网络基础所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---