一、為什么學(xué)習(xí)拉普拉斯矩陣
????早期，很多圖神經(jīng)網(wǎng)絡(luò)的概念是基于圖信號分析或圖擴散的，而這些都需要與圖譜論相關(guān)的知識。并且在圖網(wǎng)絡(luò)深度學(xué)習(xí)中（graph deep learning）中，拉普拉斯矩陣是很常用的概念，深入理解其物理含義非常有助于加深對GNN模型的理解。博主最近在學(xué)習(xí)GCN，想要在拉普拉斯矩陣方面有個更加深入的了解，看了不少文獻資料與網(wǎng)上的解讀，受益匪淺。
二、拉普拉斯矩陣的定義與性質(zhì)
????對于一個有n個頂點的圖G，它的拉普拉斯矩陣(Laplacian Matrix)定義為：
L
=
D
?
A
L=D-A
L=D?A????其中，D是圖G的度矩陣，A是圖G的鄰接矩陣。L中的元素可定義為：
L
i
j
=
{
d
(
v
i
)
如
果
i
=
j
?
A
i
j
如
果
i
?
≠
?
j
并
且
v
i
與
v
j
之
間
有
邊
0
其
他
L_{ij}= \begin{cases} d(v_i)& 如果i=j \\ -A_{ij}& 如果i\ {\neq}\ j并且v_i與v_j之間有邊 \\ 0& 其他 \end{cases}
Lij?=??????d(vi?)?Aij?0?如果i=j如果i??=?j并且vi?與vj?之間有邊其他?????通常， 我們需要將拉普拉斯矩陣進行歸一化。常用的有兩種方式。
????(1) 對稱歸一化的拉普拉斯矩陣(Symmetric Normalized Laplacian Matrix)
L
s
y
m
=
D
?
1
2
L
D
?
1
2
=
I
?
D
?
1
2
A
D
?
1
2
L^{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}
Lsym=D?21?LD?21?=I?D?21?AD?21?????(2) 隨機游走歸一化的拉普拉斯矩陣(Random Walk Normalized Laplacian Matrix)
L
r
w
=
D
?
1
L
=
I
?
D
?
1
A
L^{rw}=D^{-{1}}L=I-D^{-{1}}A
Lrw=D?1L=I?D?1A????以下面這個圖為例，假設(shè)每條邊權(quán)重為1，得到這個圖的鄰接矩陣、度矩陣和拉普拉斯矩陣。
????從這個L矩陣中可以觀察到拉普拉斯矩陣的以下幾條性質(zhì)。
????○ L是對稱的
????○ L是半正定矩陣（每個特征值
λ
i
≥
0
\lambda_i{\geq}0
λi?≥0）
????○ L的每一行每一列的和為0
????○ L的最小特征值為0。給定一個特征向量
v
0
=
(
1
,
1
,
?
?
,
1
)
T
v_0=(1,1,\cdots,1)^T
v0?=(1,1,?,1)T，根據(jù)上一條性質(zhì)，L的每一行之和為0，所以
L
v
0
=
0
Lv_0=0
Lv0?=0
三、拉普拉斯矩陣的推導(dǎo)與意義
3.1 梯度、散度與拉普拉斯算子
????圖拉普拉斯矩陣，如果把它看作線性變換的話，它起的作用與分析中的拉普拉斯算子是一樣的。我們將在下面詳細討論，這里需要補充一些基礎(chǔ)知識：
梯度定義
梯度 “ ? \nabla ? ” 是一個矢量，表示某一函數(shù)在該點處的方向?qū)?shù)沿著該方向取得最大值，即函數(shù)在該方向處沿著此梯度方向變化最快，變化率最大（梯度的模）。
????假設(shè)一個三元函數(shù)
u
=
f
(
x
,
y
,
z
)
u=f(x,y,z)
u=f(x,y,z)在空間區(qū)域
G
G
G內(nèi)具有一階連續(xù)偏導(dǎo)數(shù)，點
P
(
x
,
y
,
z
)
∈
G
P(x,y,z){\in}G
P(x,y,z)∈G，則稱以下向量表示為點
P
P
P處的梯度：
{
?
f
?
x
,
?
f
?
y
,
?
f
?
z
}
=
?
f
?
x
i
?
+
?
f
?
y
j
?
+
?
f
?
z
k
?
\{\frac{{\partial}f}{{\partial}x},\frac{{\partial}f}{{\partial}y},\frac{{\partial}f}{{\partial}z}\}=\frac{{\partial}f}{{\partial}x}\vec{i}+\frac{{\partial}f}{{\partial}y}\vec{j}+\frac{{\partial}f}{{\partial}z}\vec{k}
{?x?f?,?y?f?,?z?f?}=?x?f?i+?y?f?j?+?z?f?k????該式可記為
g
r
a
d
f
(
x
,
y
,
z
)
gradf(x,y,z)
gradf(x,y,z)或
?
f
(
x
,
y
,
z
)
{\nabla}f(x,y,z)
?f(x,y,z)，其中：
?
=
?
?
x
i
?
+
?
?
y
j
?
+
?
?
z
k
?
\nabla=\frac{{\partial}}{{\partial}x}\vec{i}+\frac{{\partial}}{{\partial}y}\vec{j}+\frac{{\partial}}{{\partial}z}\vec{k}
?=?x??i+?y??j?+?z??k????稱為向量的微分算子或者Nabla算子
散度定義
散度 “ ? ? {\nabla}{\cdot} ??” （divergence）是一個標(biāo)量，用于表示空間中各點矢量場發(fā)散的強弱程度，物理上，散度的意義是場的有源性。當(dāng) d i v ( F ) > 0 div(F)>0 div(F)>0，表示該點有散發(fā)通量的正源（發(fā)散源）；當(dāng) d i v ( F ) < 0 div(F)<0 div(F)<0，表示該點有吸收能量的負源（洞或匯）；當(dāng) d i v ( F ) = 0 div(F)=0 div(F)=0，表示該點無源
????散度是作用在向量場上的一個算子。用三維空間舉例，向量場就是在空間中每一點處都對應(yīng)一個三維向量的向量函數(shù)：
F
(
x
,
y
,
z
)
=
(
v
1
(
x
,
y
,
z
)
,
v
2
(
x
,
y
,
z
)
,
v
3
(
x
,
y
,
z
)
)
T
d
i
v
(
F
)
=
?
v
1
?
x
+
?
v
2
?
y
+
?
v
3
?
z
F(x,y,z)=(v_1(x,y,z),v_2(x,y,z),v_3(x,y,z))^T\\ div(F)=\frac{{\partial}v_1}{{\partial}x}+\frac{{\partial}v_2}{{\partial}y}+\frac{{\partial}v_3}{{\partial}z}
F(x,y,z)=(v1?(x,y,z),v2?(x,y,z),v3?(x,y,z))Tdiv(F)=?x?v1??+?y?v2??+?z?v3??????它是一個標(biāo)量函數(shù)（場），也就是說，在定義空間中每一點的散度是一個值。矢量
V
V
V的散度在笛卡爾坐標(biāo)（直角坐標(biāo)系）下的表達式如下所示：
?
?
V
=
?
V
x
?
x
+
?
V
y
?
y
+
?
V
z
?
z
\nabla{\cdot}V=\frac{{\partial}V_x}{{\partial}x}+\frac{{\partial}V_y}{{\partial}y}+\frac{{\partial}V_z}{{\partial}z}
??V=?x?Vx??+?y?Vy??+?z?Vz??
拉普拉斯算子定義
拉普拉斯算子“ △ \triangle △”（Laplace Operator）是n維歐幾里得空間中的一個二階微分算子，定義為梯度（ ? f {\nabla}f ?f）的散度（ ? ? {\nabla}\cdot ??）
△ f = ? 2 f = ? ? ? f = d i v ( g r a d f ) {\triangle}f={\nabla}^2f={\nabla}{\cdot}{\nabla}f=div(gradf) △f=?2f=???f=div(gradf)
????在笛卡爾坐標(biāo)表示下：
△
f
=
?
2
f
?
x
2
+
?
2
f
?
y
2
+
?
2
f
?
z
2
{\triangle}f=\frac{{\partial}^2f}{{\partial}x^2}+\frac{{\partial}^2f}{{\partial}y^2}+\frac{{\partial}^2f}{{\partial}z^2}
△f=?x2?2f?+?y2?2f?+?z2?2f?????n維形式如下：
△
=
∑
i
?
2
?
x
i
2
{\triangle}=\sum_i\frac{\partial^2}{{\partial}x_i^2}
△=i∑??xi2??2?????然后推導(dǎo)離散形式的導(dǎo)數(shù)：
?
f
?
x
=
f
(
x
+
1
)
?
f
(
x
)
?
2
f
?
x
2
=
f
′
′
(
x
)
=
f
′
(
x
)
?
f
′
(
x
?
1
)
=
f
(
x
+
1
)
+
f
(
x
?
1
)
?
2
f
(
x
)
\frac{{\partial}f}{{\partial}x}=f(x+1)-f(x)\\ \frac{{\partial}^2f}{{\partial}x^2}=f''(x)=f'(x)-f'(x-1)=f(x+1)+f(x-1)-2f(x)
?x?f?=f(x+1)?f(x)?x2?2f?=f′′(x)=f′(x)?f′(x?1)=f(x+1)+f(x?1)?2f(x)????以二維坐標(biāo)為例，將拉普拉斯算子轉(zhuǎn)化為離散形式：
△
f
=
?
2
f
?
x
2
+
?
2
f
?
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
)
{\triangle}f=\frac{{\partial}^2f}{{\partial}x^2}+\frac{{\partial}^2f}{{\partial}y^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)
△f=?x2?2f?+?y2?2f?=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)????下面用散度
△
f
{\triangle}f
△f的概念進一步分析：
????1.
△
f
>
0
{\triangle}f>0
△f>0時，表示該點為發(fā)散源，是散發(fā)通量的正源，比如下圖中的點
q
1
,
q
2
,
q
4
q_1,q_2,q_4
q1?,q2?,q4?。
????2.
△
f
<
0
{\triangle}f<0
△f<0時，表示該點為洞或穴，是吸收通量的負源，比如下圖中的點
q
3
q_3
q3?。
????3.
△
f
=
0
{\triangle}f=0
△f=0時，表示該點無源。
????我們將上面的式子用矩陣進行表示如下：
[
0
1
0
1
?
4
1
0
1
0
]
\begin{bmatrix} 0&1&0\\ 1&-4&1\\ 0&1&0\\ \end{bmatrix}
???010?1?41?010????????實際上，拉普拉斯算子計算了周圍點與中心點的梯度差。當(dāng)
f
(
x
,
y
)
f(x,y)
f(x,y)受到擾動之后，其可能變?yōu)橄噜彽?span id="n5n3t3z" class="katex--inline">
f
(
x
?
1
,
y
)
,
f
(
x
+
1
,
y
)
,
f
(
x
,
y
?
1
)
,
f
(
x
,
y
+
1
)
f(x-1,y),f(x+1,y),f(x,y-1),f(x,y+1)
f(x?1,y),f(x+1,y),f(x,y?1),f(x,y+1)之一，拉普拉斯算子得到的是對該點進行微小擾動后可能獲得的總增益 （或者說是總變化）。
????形象地說，假設(shè)上圖五個圓點都是人，四條黑線分別牽著兩個人，所有人同時用力拉繩子，每個人的力氣大小分別為：
f
(
x
,
y
)
,
f
(
x
?
1
,
y
)
,
f
(
x
+
1
,
y
)
,
f
(
x
,
y
?
1
)
,
f
(
x
,
y
+
1
)
f(x,y),f(x-1,y),f(x+1,y),f(x,y-1),f(x,y+1)
f(x,y),f(x?1,y),f(x+1,y),f(x,y?1),f(x,y+1)。而
△
f
{\triangle}f
△f的值就表示了中間那位可憐的仁兄會被拉跑還是把其他人拉過來以及拉過來和被拉跑的程度。
△
f
>
0
{\triangle}f>0
△f>0時表示他會被拉跑，
△
f
<
0
{\triangle}f<0
△f<0表示這家伙大力出奇跡把人全拉過來了，
△
f
=
0
{\triangle}f=0
△f=0表示這五個人正在僵持狀態(tài)，誰都拉不動中間那位同志。文章來源：http://www.zghlxwxcb.cn/news/detail-406970.html
3.2 從拉普拉斯算子到拉普拉斯矩陣
????我們現(xiàn)在將3.1節(jié)的結(jié)論推廣到圖：
????假設(shè)具有
N
N
N個節(jié)點的圖
G
G
G，節(jié)點
i
i
i的鄰域為
N
i
N_i
Ni?，圖上定義一個函數(shù)
f
=
(
f
1
,
f
2
,
?
?
,
f
n
)
f=(f_1,f_2,\cdots,f_n)
f=(f1?,f2?,?,fn?)，
f
i
f_i
fi?表示函數(shù)
f
f
f在節(jié)點
i
i
i處的函數(shù)值，則對其中一個節(jié)點
i
i
i進行微擾，它可能變?yōu)閳D中任意一個與它相鄰的節(jié)點
j
∈
N
i
j{\in}N_i
j∈Ni?，
N
i
N_i
Ni?表示節(jié)點
i
i
i的一階鄰域。
????我們已經(jīng)知道通過拉普拉斯算子可以計算一個點在它所有自由度上微小擾動的增益，則通過圖來表示就是任意一個節(jié)點
i
i
i變化到節(jié)點
j
j
j所帶來的增益，設(shè)節(jié)點
i
i
i與節(jié)點
j
j
j之間連邊
e
i
j
e_{ij}
eij?的權(quán)值為
w
i
j
w_{ij}
wij?，考慮圖中邊的權(quán)值則有：
△
f
i
=
∑
j
∈
N
i
w
i
j
(
f
i
?
f
j
)
{\triangle}f_i=\sum_{j{\in}N_i}w_{ij}(f_i-f_j)
△fi?=j∈Ni?∑?wij?(fi??fj?)????如果假設(shè)節(jié)點
i
i
i與節(jié)點
j
j
j不相鄰時
w
i
j
=
0
w_{ij}=0
wij?=0，并將上面的式子進行簡化：
△
f
i
=
∑
j
∈
N
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
d
i
=
∑
j
∈
N
i
w
i
j
表
示
頂
點
的
度
w
i
:
=
(
w
i
1
,
?
?
,
w
i
N
)
表
示
N
維
的
行
向
量
f
=
(
f
1
?
f
N
)
表
示
N
維
的
列
向
量
{\triangle}f_i=\sum_{j{\in}N}w_{ij}(f_i-f_j)\\=\sum_{j{\in}N}w_{ij}f_i-\sum_{j{\in}N}w_{ij}f_j\\=d_if_i-w_{i:}f\\d_i=\sum_{j{\in}N_i}w_{ij}表示頂點的度\\w_{i:}=(w_{i1},\cdots,w_{iN})表示N維的行向量\\f=\begin{pmatrix} f_1\\ {\vdots}\\ f_N\\ \end{pmatrix}表示N維的列向量
△fi?=j∈N∑?wij?(fi??fj?)=j∈N∑?wij?fi??j∈N∑?wij?fj?=di?fi??wi:?fdi?=j∈Ni?∑?wij?表示頂點的度wi:?=(wi1?,?,wiN?)表示N維的行向量f=????f1??fN??????表示N維的列向量????對于所有的N個節(jié)點來說：
△
f
=
(
△
f
1
?
△
f
N
)
=
(
d
1
f
1
?
w
1
:
f
?
d
N
f
N
?
w
N
:
f
)
=
(
d
1
?
0
?
?
?
0
?
d
N
)
f
?
(
w
1
:
?
w
N
:
)
f
=
d
i
a
g
(
d
i
)
f
?
W
f
=
(
D
?
W
)
f
=
L
f
{\triangle}f=\begin{pmatrix} {\triangle}f_1\\ {\vdots}\\ {\triangle}f_N\\ \end{pmatrix}=\begin{pmatrix} d_1f_1-w_{1:}f\\ {\vdots}\\ d_Nf_N-w_{N:}f\\ \end{pmatrix}\\=\begin{pmatrix} d_1&{\cdots}&0\\ {\vdots}&{\ddots}&{\vdots}\\ 0&{\cdots}&d_N\\ \end{pmatrix}f-\begin{pmatrix} w_{1:}\\ {\vdots}\\ w_{N:}\\ \end{pmatrix}f\\=diag(d_i)f-Wf\\=(D-W)f\\=Lf
△f=????△f1??△fN??????=????d1?f1??w1:?f?dN?fN??wN:?f?????=????d1??0?????0?dN??????f?????w1:??wN:??????f=diag(di?)f?Wf=(D?W)f=Lf????這里的
(
D
?
W
)
(D-W)
(D?W)實際上就是拉普拉斯矩陣
L
L
L。
????根據(jù)前面所述，拉普拉斯矩陣中的第
i
i
i行實際上反應(yīng)了第
i
i
i個節(jié)點在對其他所有節(jié)點產(chǎn)生擾動時所產(chǎn)生的增益累積。直觀上來講，圖拉普拉斯反映了當(dāng)我們在節(jié)點
i
i
i上施加一個勢，這個勢以哪個方向能夠多順暢的流向其他節(jié)點。譜聚類中的拉普拉斯矩陣可以理解為是對圖的一種矩陣表示形式。
????形象點說，我們可以把
N
N
N個節(jié)點想象為
N
N
N座山峰，
f
i
f_i
fi?為山峰
i
i
i的海拔高度，兩個節(jié)點之間有連邊則代表兩座山峰之間有路徑，拉普拉斯矩陣實際就是嵌入了某一個山峰對在其他山峰上的人的吸引程度，或者說是一種人口流動傾向。
????參考鏈接：
????1. https://zhuanlan.zhihu.com/p/81502804
????2. https://zhuanlan.zhihu.com/p/238644468
????3. https://zhuanlan.zhihu.com/p/85287578文章來源地址http://www.zghlxwxcb.cn/news/detail-406970.html
到了這里，關(guān)于圖譜論學(xué)習(xí)—拉普拉斯矩陣背后的含義的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
