图神经网络基础
最近在学习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,othersLi,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−21LD−21Li,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=⎣⎡100020001⎦⎤,A=⎣⎡010101010⎦⎤L=D−A=⎣⎡1−10−12−10−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−21LD−21=diag(1,2 1,1)⋅⎣⎡1−10−12−10−11⎦⎤⋅diag(1,2 1,1)=⎣⎢⎡1−2 10−2 11−2 10−2 11⎦⎥⎤
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∑ndxi2d2f
上面这个公式，如果按照图像二维的方式计算，实际上就是拉普拉斯算子。
△
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]
⎣⎡0101−41010⎦⎤
拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总增益 （或者说是总变化）
不难理解，就是一个梯度变化
上面举例的是二维，这种扰动可以看作是一个像素点向周围变化时产生的收益。
推广到图理论中，可以得到：
△
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,jfi−j∈N∑wi,jfj=difi−Wifi
△ 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)=(d1f1−W1f,d2f2−W2f,...,dNfN−WNf)=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=λkuk
所以，图上的傅里叶变换为：
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∑Nfiuk(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∑inff[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))⋅UTfand, 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)