圖卷積神經網絡(Graph Convolutional Network, GCN)

文章目錄

• 從譜聚類說起
• • RatioCut 切圖聚類
• GCN
• • 從傅裡葉級數到傅裡葉變換
  • 傅裡葉級數的直覺意義
  • • 傅裡葉變換推導
  • Signal Processing on Graph
  • 圖上的傅裡葉變換
• 參考資料

從譜聚類說起

譜聚類(spectral clustering)是一種針對圖結構的聚類方法，它跟其他聚類算法的差別在于，他将每個點都看作是一個圖結構上的點，是以，判斷兩個點是否屬于同一類的依據就是，兩個點在圖結構上是否有邊相連，可以是直接相連也可以是間接相連。舉個例子，一個緊湊的子圖（如完全圖）一定比一個松散的子圖更容易聚成一類。

那譜聚類為什麼叫譜而不是圖聚類呢？這個spectral是什麼東西？我們知道一個圖是可以用一個鄰接矩陣A來表示的。而矩陣的譜（spectral）就是指矩陣的特征值，那麼這個特征值跟圖的矩陣到底有什麼深刻的聯系呢？

那麼首先，圖的聚類是什麼？我們可以将聚類問題簡化為一個分割問題，如果圖的結點被分割成A,B這兩個集合，那麼我們自然是希望在集合中的結點的互相連接配接更加緊密比如團，而使得子圖之間更加盡可能松散。

為了建立這個聯系，我們構造一個laplace matrix：

L = D − A L=D-A L=D−A

D是一個對角矩陣，每個對角元素 D i i \displaystyle D_{ii} Dii​表示第i個結點的度。A則是這個圖鄰接矩陣。為什麼要這樣去構造一個矩陣呢？因為研究圖的一些性質的時候，我們常常用到一個類似于下式的目标函數：

x T M x = ∑ { u , v } ∈ E ( x u − x v ) 2 \mathbf{x^{T}} M\mathbf{x} =\sum _{\{u,v\} \in E}( x_{u} -x_{v})^{2} xTMx={u,v}∈E∑​(xu​−xv​)2

這個目标函數可以定義圖上的很多問題，比如最小圖分割問題，就是要找到一個方法将圖分成兩塊的使得切割的邊最少（如果邊有權重那就是切割的權重最小）。如下圖，你不能找到一個比切兩條邊更少的分割方法了。

而這個優化問題其實等價于當 x ∈ { 0 , 1 } V \displaystyle x\in \{0,1\}^{V} x∈{0,1}V的時候:

min ⁡ ∑ { u , v } ∈ E ( x u − x v ) 2 = ∑ u ∈ A , v ∉ A ‾ ( 1 − 0 ) 2 + ∑ u ∈ A , v ∉ A ‾ ( 0 − 1 ) 2 = 2 c u t ( A , A ‾ ) \min\sum _{\{u,v\} \in E}( x_{u} -x_{v})^{2} =\sum _{u\in A,v\not{\in }\overline{A}}( 1-0)^{2} +\sum _{u\in A,v\not{\in }\overline{A}}( 0-1)^{2} =2cut\left( A,\overline{A}\right) min{u,v}∈E∑​(xu​−xv​)2=u∈A,v​∈A∑​(1−0)2+u∈A,v​∈A∑​(0−1)2=2cut(A,A)

而這個方程不正是一個二次型嗎。為了讓二次型得到這個結果。我們發現，當 M = d I − A = D − A \displaystyle M=dI-A=D-A M=dI−A=D−A的時候就可以了。驗證一下：

x T ( d I − A ) x = d x T x − x T A x = ∑ v d x v 2 − 2 ∑ { u , v } ∈ E x u x v = ∑ { u , v } ∈ E ( x u − x v ) 2 \mathbf{x}^{T}( dI-A)\mathbf{x} =d\mathbf{x}^{T}\mathbf{x} -\mathbf{x}^{T} A\mathbf{x} =\sum _{v} dx^{2}_{v} -2\sum _{\{u,v\} \in E} x_{u} x_{v} =\sum _{\{u,v\} \in E}( x_{u} -x_{v})^{2} xT(dI−A)x=dxTx−xTAx=v∑​dxv2​−2{u,v}∈E∑​xu​xv​={u,v}∈E∑​(xu​−xv​)2

此外，當A不是鄰接矩陣而是權重矩陣W的時候，于是d就從度推廣到權重的求和，那麼這個公式還可以推廣為：

x T L x = x T ( d I − W ) x = ∑ i , j ω i j ( x u − x v ) 2 x^{T} Lx\mathbf{=x}^{T}( dI-W)\mathbf{x} =\sum _{i,j} \omega _{ij}( x_{u} -x_{v})^{2} xTLx=xT(dI−W)x=i,j∑​ωij​(xu​−xv​)2

RatioCut 切圖聚類

現在，我們可以嘗試将這個目标函數與Ratio切圖聚類的目标函數建立起聯系，建立聯系有什麼好處呢？好處就是如果我們發現切圖的目标函數是這個二次型，那麼我們隻要優化這個二次型，不就可以用連續的方法來解決一個離散的問題嗎？

RatioCut考慮最小化 c u t ( A 1 , A 2 , . . . , A k ) \displaystyle cut( A_{1} ,A_{2} ,...,A_{k}) cut(A1​,A2​,...,Ak​)，同時最大化每個子圖的個數即：

R a t i o C u t ( A 1 , A 2 , . . . A k ) = 1 2 ∑ i = 1 k c u t ( A i , A ‾ i ) ∣ A i ∣ RatioCut(A_{1} ,A_{2} ,...A_{k} )=\frac{1}{2}\sum\limits ^{k}_{i=1}\frac{cut(A_{i} ,\overline{A}_{i} )}{|A_{i} |} RatioCut(A1​,A2​,...Ak​)=21​i=1∑k​∣Ai​∣cut(Ai​,Ai​)​

其中 c u t ( A i , A ‾ i ) \displaystyle cut(A_{i} ,\overline{A}_{i} ) cut(Ai​,Ai​)表示兩個子圖之間的距離(兩個子圖結點之間距離的求和)：

c u t ( A i , A ‾ i ) = ∑ i ∈ A , j ∈ A ‾ i w i j cut(A_{i} ,\overline{A}_{i} )=\sum\limits _{i\in A,j\in \overline{A}_{i}} w_{ij} cut(Ai​,Ai​)=i∈A,j∈Ai​∑​wij​

這裡公式裡的是A與A的補集的切圖權重（切的邊權重的求和），也就是說我們希望子圖A與其餘的圖分離的代價最小，比如我隻要切掉一條微不足道的邊就能将兩個複雜的圖（比如兩個團）分離開，那麼就可以認為這是一個好的切割。

現在我們仿照上面的x，将其推廣到多個簇，于是我們用一個訓示函數（one-hot）來表達每個結點屬于哪個子圖，這樣就将切割問題跟二次型建立起了聯系

我們引入訓示向量 h j ∈ { h 1 , h 2 , . . h k }   j = 1 , 2 , . . . k h_{j} \in \{h_{1} ,h_{2} ,..h_{k} \}\ j=1,2,...k hj​∈{h1​,h2​,..hk​} j=1,2,...k，表示有k個子圖，對于任意一個向量 h j \displaystyle h_{j} hj​, 它是一個|V|-維向量（|V|為結點數，用來标記哪個結點屬于哪個子圖，類似于one-hot），我們定義 h i j \displaystyle h_{ij} hij​為：

h i j = { 0 v j ∉ A i 1 ∣ A i ∣ v j ∈ A i h_{ij} =\begin{cases} 0 & v_{j} \notin A_{i}\\ \frac{1}{\sqrt{|A_{i} |}} & v_{j} \in A_{i} \end{cases} hij​={0∣Ai​∣

​1​​vj​∈/​Ai​vj​∈Ai​​

那麼，對于每一個子圖都有：

h i T L h i = 1 2 ∑ m = 1 ∣ V ∣ ∑ n = 1 ∣ V ∣ w m n ( h i m − h i n ) 2 = 1 2 ( ∑ m ∈ A i , n ∉ A i w m n ( 1 ∣ A i ∣ − 0 ) 2 + ∑ m ∉ A i , n ∈ A i w m n ( 0 − 1 ∣ A i ∣ ) 2 = 1 2 ( ∑ m ∈ A i , n ∉ A i w m n 1 ∣ A i ∣ + ∑ m ∉ A i , n ∈ A i w m n 1 ∣ A i ∣ = 1 2 ( c u t ( A i , A ‾ i ) 1 ∣ A i ∣ + c u t ( A ‾ i , A i ) 1 ∣ A i ∣ ) = c u t ( A i , A ‾ i ) ∣ A i ∣ \begin{aligned} h^{T}_{i} Lh_{i} & =\frac{1}{2}\sum\limits ^{|V|}_{m=1}\sum\limits ^{|V|}_{n=1} w_{mn} (h_{im} -h_{in} )^{2}\\ & =\frac{1}{2} (\sum\limits _{m\in A_{i} ,n\notin A_{i}} w_{mn} (\frac{1}{\sqrt{|A_{i} |}} -0)^{2} +\sum\limits _{m\notin A_{i} ,n\in A_{i}} w_{mn} (0-\frac{1}{\sqrt{|A_{i} |}} )^{2}\\ & =\frac{1}{2} (\sum\limits _{m\in A_{i} ,n\notin A_{i}} w_{mn}\frac{1}{|A_{i} |} +\sum\limits _{m\notin A_{i} ,n\in A_{i}} w_{mn}\frac{1}{|A_{i} |}\\ & =\frac{1}{2} (cut(A_{i} ,\overline{A}_{i} )\frac{1}{|A_{i} |} +cut(\overline{A}_{i} ,A_{i} )\frac{1}{|A_{i} |} )\\ & =\frac{cut(A_{i} ,\overline{A}_{i} )}{|A_{i} |} \end{aligned} hiT​Lhi​​=21​m=1∑∣V∣​n=1∑∣V∣​wmn​(him​−hin​)2=21​(m∈Ai​,n∈/​Ai​∑​wmn​(∣Ai​∣

​1​−0)2+m∈/​Ai​,n∈Ai​∑​wmn​(0−∣Ai​∣

​1​)2=21​(m∈Ai​,n∈/​Ai​∑​wmn​∣Ai​∣1​+m∈/​Ai​,n∈Ai​∑​wmn​∣Ai​∣1​=21​(cut(Ai​,Ai​)∣Ai​∣1​+cut(Ai​,Ai​)∣Ai​∣1​)=∣Ai​∣cut(Ai​,Ai​)​​

其原理在于，因為當 m ∈ A i , n ∉ A i \displaystyle m\in A_{i} ,n\notin A_{i} m∈Ai​,n∈/​Ai​時，因為結點 v m \displaystyle v_{m} vm​屬于子圖i，結點 v n \displaystyle v_{n} vn​不屬于子圖i，于是 h i m − h i n = 1 ∣ A i ∣ − 0 \displaystyle h_{im} -h_{in} =\frac{1}{\sqrt{|A_{i} |}} -0 him​−hin​=∣Ai​∣

​1​−0，同理，當 v m \displaystyle v_{m} vm​, v n \displaystyle v_{n} vn​都屬于子圖的時候 h i m − h i n = 1 ∣ A i ∣ − 1 ∣ A i ∣ = 0 \displaystyle h_{im} -h_{in} =\frac{1}{\sqrt{|A_{i} |}} -\frac{1}{\sqrt{|A_{i} |}} =0 him​−hin​=∣Ai​∣

​1​−∣Ai​∣

​1​=0。

上述是第i個子圖的式子，我們将k個子圖的h合并成一個H，于是式子變成：

R a t i o C u t ( A 1 , A 2 , . . . A k ) = ∑ i = 1 k h i T L h i = ∑ i = 1 k ( H T L H ) i i = t r ( H T L H ) s . t .   h i T h i = 1 ,   i = 1 , 2 , . . . , k RatioCut(A_{1} ,A_{2} ,...A_{k} )=\sum\limits ^{k}_{i=1} h^{T}_{i} Lh_{i} =\sum\limits ^{k}_{i=1} (H^{T} LH)_{ii} =tr(H^{T} LH)\\ s.t.\ h^{T}_{i} h_{i} =1,\ i=1,2,...,k RatioCut(A1​,A2​,...Ak​)=i=1∑k​hiT​Lhi​=i=1∑k​(HTLH)ii​=tr(HTLH)s.t. hiT​hi​=1, i=1,2,...,k

也就是說Ratiocut本質上就是在最小化 t r ( H T L H ) \displaystyle tr(H^{T} LH) tr(HTLH)這個東西。那麼怎麼優化呢？注意到每個 h i \displaystyle h_{i} hi​都是互相正交的，因為一個結點不能同時屬于多個類别，是以H是一個正交矩陣，又因為L是一個對稱矩陣，那麼可以證明，H是L的特征向量的時候，恰好是這個優化問題的解，我們需要要找到那麼特征值比較小的特征向量，就可以找到一種代價最小的切割方法。我們可以來證明一下,特征向量恰好是他的極值：

∇ h ( h T L h − λ ( 1 − h T h ) ) = ∇ h t r ( h T L h − λ ( 1 − h T h ) ) = ∇ h t r ( h T L h ) − λ ∇ h t r ( h h T ) = ∇ h t r ( h h T L ) − λ ∇ h t r ( h E h T E ) = ∇ h t r ( h E h T L ) − λ ∇ h t r ( h E h T E ) = L h + L T h − λ ( h + h ) = 2 L h − 2 λ h = 0 ⟹ L u = λ h \begin{aligned} \nabla _{h}\left( h^{T} Lh-\lambda \left( 1-h^{T} h\right)\right) & =\nabla _{h} tr\left( h^{T} Lh-\lambda \left( 1-h^{T} h\right)\right)\\ & =\nabla _{h} tr\left( h^{T} Lh\right) -\lambda \nabla _{h} tr\left( hh^{T}\right)\\ & =\nabla _{h} tr(hh^{T} L)-\lambda \nabla _{h} tr(hEh^{T} E)\\ & =\nabla _{h} tr(hEh^{T} L)-\lambda \nabla _{h} tr(hEh^{T} E)\\ & =Lh+L^{T} h-\lambda ( h+h)\\ & =2Lh-2\lambda h\\ & =0\\ & \Longrightarrow Lu=\lambda h \end{aligned} ∇h​(hTLh−λ(1−hTh))​=∇h​tr(hTLh−λ(1−hTh))=∇h​tr(hTLh)−λ∇h​tr(hhT)=∇h​tr(hhTL)−λ∇h​tr(hEhTE)=∇h​tr(hEhTL)−λ∇h​tr(hEhTE)=Lh+LTh−λ(h+h)=2Lh−2λh=0⟹Lu=λh​

這裡用到了一些最優化求導常用公式技巧，其實這個推導跟PCA是一樣的，隻不過PCA找的是最大特征值（PCA中L是協方差矩陣，目标是找到一個向量最大化方差），這裡是找最小特征值，我們目标是找到一個向量最小化這個二次型矩陣。(PS: 想知道為什麼是找特征值最小，而PCA找的是特征值最大的同學，不妨看看我的另外一篇文章：譜圖理論(spectral graph theory))

最後，通過找到L的最小的k個特征值，可以得到對應的k個特征向量，這k個特征向量組成一個nxk次元的矩陣，即為我們的H。一般需要對H矩陣按行做标準化，即

h i j ∗ = h i j ( ∑ t = 1 k h i t 2 ) 1 / 2 h^{*}_{ij} =\frac{h_{ij}}{(\sum\limits ^{k}_{t=1} h^{2}_{it} )^{1/2}} hij∗​=(t=1∑k​hit2​)1/2hij​​

由于我們在使用次元規約的時候損失了少量資訊，導緻得到的優化後的訓示向量h對應的H不能完全訓示各樣本的歸屬（因為是連續的優化，不可能恰到得到一個one-hot向量），是以一般在得到nxk次元的矩陣H後還需要對每一行進行一次傳統的聚類，比如使用K-Means聚類，進而得到一個真正的one-hot訓示向量。

是以譜聚類的流程可以總結如下：

1. 計算标準化後的lapace矩陣
2. 求解标準化lapace矩陣的特征值與特征向量
3. 取最小的k1個特征向量,及其對應的特征向量f
4. 将f排列成一個n*k1的矩陣，對矩陣的每一行進行标準化，然後使用k means聚類，聚類數為k2
5. 得到k2個簇，就是對應k2個劃分。

GCN

圖卷積神經網絡，顧名思義就是在圖上使用卷積運算，然而圖上的卷積運算是什麼東西？為了解決這個問題題，我們可以利用圖上的傅裡葉變換，再使用卷積定理，這樣就可以通過兩個傅裡葉變換的乘積來表示這個卷積的操作。那麼為了介紹圖上的傅裡葉變換，我接來下從最原始的傅裡葉級數開始講起。

從傅裡葉級數到傅裡葉變換

此部分主要參考了馬同學的兩篇文章：

1. 從傅立葉級數到傅立葉變換
2. 如何了解傅立葉級數公式？

傅裡葉級數的直覺意義

如下圖，傅裡葉級數其實就是用一組sin，cos的函數來逼近一個周期函數，那麼每個sin，cos函數就是一組基，這組基上的系數就是頻域，你會發現随着頻域越來越多（基越來越多），函數的拟合就越準确。

傅裡葉變換推導

要講傅裡葉變換的推導，我們要先從傅裡葉級數講起，考慮一周期等于T，現定義于區間[-T/2,T/2]的周期函數f(x)，傅裡葉級數近似的表達式如下:

f ( x ) = C + ∑ n = 1 ∞ ( a n c o s ( 2 π n T x ) + b n s i n ( 2 π n T x ) ) , C ∈ R {\displaystyle f(x)=C+\sum ^{\infty }_{n=1}\left( a_{n} cos(\frac{2\pi n}{T} x)+b_{n} sin(\frac{2\pi n}{T} x)\right) ,C\in \mathbb{R}} f(x)=C+n=1∑∞​(an​cos(T2πn​x)+bn​sin(T2πn​x)),C∈R

利用偶函數*奇函數=奇函數的性質可以計算出 a k \displaystyle a_{k} ak​與 b k \displaystyle b_{k} bk​

a n = ∫ − T / 2 T / 2 f ( x ) c o s ( 2 π n T x ) d x ∫ − T / 2 T / 2 c o s 2 ( 2 π n T x ) d x = 2 T ∫ − T / 2 T / 2 f ( x ) c o s ( 2 π n T x ) d x b n = ∫ − T / 2 T / 2 f ( x ) s i n ( 2 π n T x ) d x ∫ − T / 2 T / 2 s i n 2 ( 2 π n T x ) d x = 2 T ∫ − T / 2 T / 2 f ( x ) s i n ( 2 π n T x ) d x a_{n} =\frac{\int ^{T/2}_{-T/2} f(x)cos(\frac{2\pi n}{T} x)dx}{\int ^{T/2}_{-T/2} cos^{2} (\frac{2\pi n}{T} x)dx} =\frac{2}{T}\int ^{T/2}_{-T/2} f(x)cos(\frac{2\pi n}{T} x)dx\\ b_{n} =\frac{\int ^{T/2}_{-T/2} f(x)sin(\frac{2\pi n}{T} x)dx}{\int ^{T/2}_{-T/2} sin^{2} (\frac{2\pi n}{T} x)dx} =\frac{2}{T}\int ^{T/2}_{-T/2} f(x)sin(\frac{2\pi n}{T} x)dx an​=∫−T/2T/2​cos2(T2πn​x)dx∫−T/2T/2​f(x)cos(T2πn​x)dx​=T2​∫−T/2T/2​f(x)cos(T2πn​x)dxbn​=∫−T/2T/2​sin2(T2πn​x)dx∫−T/2T/2​f(x)sin(T2πn​x)dx​=T2​∫−T/2T/2​f(x)sin(T2πn​x)dx

利用歐拉公式 e i x = cos ⁡ x + i sin ⁡ e^{ix} =\cos x+i\sin eix=cosx+isinx，我們發現 cos ⁡ x , sin ⁡ x \displaystyle \cos x,\sin x cosx,sinx 可表示成

cos ⁡ x = e i x + e − i x 2 , sin ⁡ x = e i x − e − i x 2 i ， {\displaystyle \cos x=\frac{e^{ix} +e^{-ix}}{2} ,\sin x=\frac{e^{ix} -e^{-ix}}{2i} ，} cosx=2eix+e−ix​,sinx=2ieix−e−ix​，

再将傅立葉級數f(x)中 cos ⁡ ( 2 π n T x ) \cos (\frac{2\pi n}{T} x) cos(T2πn​x)和 sin ⁡ ( 2 π n T x ) \sin (\frac{2\pi n}{T} x) sin(T2πn​x)的線性組合式改寫如下：

a n cos ⁡ ( 2 π n T x ) + b n sin ⁡ ( 2 π n T x ) = a n ( e i 2 π n T x + e − i 2 π n T x 2 ) + b k ( e i 2 π n T x − e − i 2 π n T x 2 i ) = ( a n − i b n 2 ) e i 2 π n T x + ( a n + i b n 2 ) e − i 2 π n T x = c n e i 2 π n T x + c − n e − i 2 π n T x \begin{aligned} a_{n}\cos (\frac{2\pi n}{T} x)+b_{n}\sin (\frac{2\pi n}{T} x) & =a_{n}\left(\frac{e^{i\frac{2\pi n}{T} x} +e^{-i\frac{2\pi n}{T} x}}{2}\right)+b_{k}\left(\frac{e^{i\frac{2\pi n}{T} x} -e^{-i\frac{2\pi n}{T} x}}{2i}\right)\\ & =\left(\frac{a_{n} -ib_{n}}{2}\right) e^{i\frac{2\pi n}{T} x} +\left(\frac{a_{n} +ib_{n}}{2}\right) e^{-i\frac{2\pi n}{T} x}\\ & =c_{n} e^{i\frac{2\pi n}{T} x} +c_{-n} e^{-i\frac{2\pi n}{T} x} \end{aligned} an​cos(T2πn​x)+bn​sin(T2πn​x)​=an​(2eiT2πn​x+e−iT2πn​x​)+bk​(2ieiT2πn​x−e−iT2πn​x​)=(2an​−ibn​​)eiT2πn​x+(2an​+ibn​​)e−iT2πn​x=cn​eiT2πn​x+c−n​e−iT2πn​x​

可以驗證 c − n = a − n − i b − n 2 = a n + i b n 2 \displaystyle c_{-n} =\frac{a_{-n} -ib_{-n}}{2} =\frac{a_{n} +ib_{n}}{2} c−n​=2a−n​−ib−n​​=2an​+ibn​​，這是因為an是一個偶函數，bn是一個奇函數。此外，若n=0，就有 c 0 = a 0 / 2 c_{0} =a_{0} /2 c0​=a0​/2。将以上結果代回f(x)的傅立葉級數即得指數傅立葉級數：

f ( x ) = ∑ n = − ∞ ∞ c n ⏟ 基 的 坐 标 ⋅ e i 2 π n x T ⏟ 正 交 基 {\displaystyle f(x)=\sum ^{\infty }_{n=-\infty }\underbrace{c_{n}}_{基的坐标} \cdot \underbrace{e^{i\tfrac{2\pi nx}{T}}}_{正交基}} f(x)=n=−∞∑∞​基的坐标

cn​​​⋅正交基

eiT2πnx​​​

現在我們知道 c n = a n − i b n 2 \displaystyle c_{n} =\frac{a_{n} -ib_{n}}{2} cn​=2an​−ibn​​，将 a n , b n \displaystyle a_{n} ,b_{n} an​,bn​的結果代進去可以得到：

c n = 1 T ∫ − T / 2 T / 2 f ( x ) ( cos ⁡ ( 2 π n T x ) − i sin ⁡ ( 2 π n T x ) ) d x = 1 T ∫ − T / 2 T / 2 f ( x ) e − i 2 π n T x d x c_{n} =\frac{1}{T}\int ^{T/2}_{-T/2} f(x)(\cos (\frac{2\pi n}{T} x)-i\sin (\frac{2\pi n}{T} x))dx=\frac{1}{T}\int ^{T/2}_{-T/2} f(x)e^{-i \frac{2\pi n}{T}} x dx cn​=T1​∫−T/2T/2​f(x)(cos(T2πn​x)−isin(T2πn​x))dx=T1​∫−T/2T/2​f(x)e−iT2πn​xdx

公式用頻率替換： Δ ω = 2 π T \displaystyle \Delta \omega =\frac{2\pi }{T} Δω=T2π​，再令 ω n = ω n \displaystyle \omega _{n} =\omega n ωn​=ωn現在我們可以寫出全新的傅裡葉級數：

f ( x ) = ∑ n = − ∞ ∞ Δ ω 2 π ∫ − T / 2 T / 2 f ( x ) e − i ω n x d x ⋅ e i ω n x {\displaystyle f(x)=\sum ^{\infty }_{n=-\infty }\frac{\Delta \omega }{2\pi }\int ^{T/2}_{-T/2} f(x)e^{-i\omega _{n} x} dx\cdot } e^{i\omega _{n} x} f(x)=n=−∞∑∞​2πΔω​∫−T/2T/2​f(x)e−iωn​xdx⋅eiωn​x

現在令 T → ∞ ， Δ ω → 0 \displaystyle T\rightarrow \infty ，\Delta \omega \rightarrow 0 T→∞，Δω→0，并設 F ( ω ) = lim ⁡ T → ∞ ∫ − T / 2 T / 2 f ( x ) e − i ω x d x \displaystyle F{\displaystyle ( \omega ) =\lim _{T\rightarrow \infty }\int ^{T/2}_{-T/2} f(x)e^{-i\omega x} dx} F(ω)=T→∞lim​∫−T/2T/2​f(x)e−iωxdx

f ( x ) = ∑ n = − ∞ ∞ Δ ω 2 π F ( ω n ) ⋅ e i ω n x = 1 2 π ∑ n = − ∞ ∞ F ( ω n ) ⋅ e i ω n x Δ ω = 1 2 π ∫ − ∞ + ∞ F ( ω ) ⋅ e i ω x d ω \begin{aligned} {\displaystyle f(x)} & ={\displaystyle \sum ^{\infty }_{n=-\infty }\frac{\Delta \omega }{2\pi } F( \omega _{n}) \cdot } e^{i\omega _{n} x}\\ & ={\displaystyle \frac{1}{2\pi }\sum ^{\infty }_{n=-\infty } F( \omega _{n}) \cdot } e^{i\omega _{n} x} \Delta \omega \\ & ={\displaystyle \frac{1}{2\pi }\int ^{+\infty }_{-\infty } F( \omega ) \cdot } e^{i\omega x} d\omega \end{aligned} f(x)​=n=−∞∑∞​2πΔω​F(ωn​)⋅eiωn​x=2π1​n=−∞∑∞​F(ωn​)⋅eiωn​xΔω=2π1​∫−∞+∞​F(ω)⋅eiωxdω​

于是得到了傅裡葉變換就是

F ( ω ) = ∫ − ∞ + ∞ f ( x ) e − i ω x d x {\displaystyle F( \omega ) =\int ^{+\infty }_{-\infty } f(x)e^{-i\omega x} dx} F(ω)=∫−∞+∞​f(x)e−iωxdx

Signal Processing on Graph

在将圖的傅裡葉變換之前，我們先介紹一下圖信号是什麼。我們在傳統機率圖中，考慮每個圖上的結點都是一個feature，對應資料的每一列，但是圖信号不一樣，這裡每個結點不是随機變量，相反它是一個object。也就是說，他描繪機率圖下每個樣本之間的圖聯系，可以了解為刻畫了不滿足iid假設的一般情形。

圖上的傅裡葉變換

那麼我們要怎麼将傳統的傅裡葉變換推廣到圖結構中去？回憶一下，傳統對f作傅裡葉變換的方法：

f ^ ( ξ ) : = < f , e 2 π i ξ t > = ∫ R f ( t ) e − 2 π i ξ t d t \hat{f} (\xi ):=\left< f,e^{2\pi i\xi t}\right> =\int _{\mathbb{R}} f(t)e^{-2\pi i\xi t} dt f^​(ξ):=⟨f,e2πiξt⟩=∫R​f(t)e−2πiξtdt

我們換了種寫法，其實我們發現這個傅裡葉變換本質上是一個内積。這個 e − 2 π i ξ t \displaystyle e^{-2\pi i\xi t} e−2πiξt其實是lapace算子的一個特征函數，可以了解為一種特殊形式的特征向量：

− Δ ( e 2 π i ξ t ) = − ∂ 2 ∂ t 2 e 2 π i ξ t = ( 2 π ξ ) 2 e 2 π i ξ t -\Delta \left( e^{2\pi i\xi t}\right) =-\frac{\partial ^{2}}{\partial t^{2}} e^{2\pi i\xi t} =(2\pi \xi )^{2} e^{2\pi i\xi t} −Δ(e2πiξt)=−∂t2∂2​e2πiξt=(2πξ)2e2πiξt

注意，這裡導數本質上是一個線性變換，因為它滿足線性算子的兩個性質，T(x+y)=T(x)+T(y), cT(x)=T(cx)。可以看到 e 2 π i ξ t \displaystyle e^{2\pi i\xi t} e2πiξt是laplace算子的特征向量，而 ( 2 π ξ ) 2 \displaystyle (2\pi \xi )^{2} (2πξ)2則是lapace算子的特征值。那麼在圖上我們的laplace矩陣就是離散化的lapace算子，而這個算子在圖上的基顯然就是特征向量了！

關于拉普拉斯算子的直覺了解推薦看這篇文章：https://www.zhihu.com/question/54504471/answer/630639025

是以，隻要意識到傳統的傅裡葉變換本質上求的是與正交基的内積（比如基 e 2 π i ξ t \displaystyle e^{2\pi i\xi t} e2πiξt）上的系數，而推廣到圖上的正交基很顯然就是laplace矩陣的特征向量，于是對于laplace矩陣的傅裡葉變換就可以表達為:

f ^ ( λ l ) : = < f , u l > = ∑ i = 1 N f ( i ) u l ∗ ( i ) \hat{f}( \lambda _{l}) :=< \mathbf{f} ,\mathbf{u}_{l}> =\sum ^{N}_{i=1} f(i)u^{*}_{l} (i) f^​(λl​):=<f,ul​>=i=1∑N​f(i)ul∗​(i)

f是Graph上的N維向量， f ( i ) f(i) f(i)與Graph的頂點一一對應， u l ( i ) u_l(i) ul​(i)表示第 l l l個特征向量的第 i i i個分量。那麼特征值（頻率） λ l \lambda_l λl​下的，f的Graph 傅裡葉變換就是與$lambda_l$對應的特征向量 u l u_l ul​進行内積運算。

這個變換就是在求解特征向量的系數，類似于基的系數“頻域”。為什麼呢？首先f是圖上的某個向量，于是我們可以用正交基将其展開：

f = λ 1 u 1 + ⋯ + λ l u l + ⋯ + λ N u N f=\lambda_1u_1+\dots+\lambda_lu_l+\dots+\lambda_Nu_N f=λ1​u1​+⋯+λl​ul​+⋯+λN​uN​

那麼f跟 u l u_l ul​ 的内積就是：

< f , u l > = λ l < \mathbf{f} ,\mathbf{u}_{l}> =\lambda_l <f,ul​>=λl​

因為 u l u_l ul​跟其他特征向量都正交，是以内積為0，而跟自己的内積則等于1，是以結果就等于 λ l \lambda_l λl​.

是以，可以了解為圖上的經過傅裡葉變換後的函數 f ^ \displaystyle \hat{f} f^​就是一個計算計算特征向量的系數的函數。

更一般的，圖上的傅裡葉變換可以寫成以下内積的形式，其中U是laplace矩陣的特征向量矩陣：

傅裡葉變換：

x ^ = U T x \hat{x} =U^{T} x x^=UTx

傅裡葉逆變換：

x = U x ^ x=U\hat{x} x=Ux^

是以，我們就可以定義圖上的卷積，因為它就是簡單的兩個變換的乘積然後再逆變換而已：

比如，x,y的卷積，就是他們傅裡葉變換頻域對應相乘，再通過傅裡葉逆變換求回去

y ∗ x = U ( ( U T y ) ⊙ ( U T x ) ) y * x=U\left(\left(U^{T} y\right) \odot\left(U^{T} x\right)\right) y∗x=U((UTy)⊙(UTx))

又因為

( x 1 ⋮ x n ) ⊙ ( y 1 ⋮ y n ) = ( x 1 ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ x n ) ( y 1 ⋮ y n ) \left( \begin{array}{c}{x_{1}} \\ {\vdots} \\ {x_{n}}\end{array}\right) \odot \left( \begin{array}{c}{y_{1}} \\ {\vdots} \\ {y_{n}}\end{array}\right)=\left( \begin{array}{ccc}{x_{1}} & {\cdots} & {0} \\ {\vdots} & {\ddots} & {\vdots} \\ {0} & {\cdots} & {x_{n}}\end{array}\right) \left( \begin{array}{c}{y_{1}} \\ {\vdots} \\ {y_{n}}\end{array}\right) ⎝⎜⎛​x1​⋮xn​​⎠⎟⎞​⊙⎝⎜⎛​y1​⋮yn​​⎠⎟⎞​=⎝⎜⎛​x1​⋮0​⋯⋱⋯​0⋮xn​​⎠⎟⎞​⎝⎜⎛​y1​⋮yn​​⎠⎟⎞​

是以我們将 U T y U^Ty UTy 參數并化為一個對角矩陣，設 g θ = diag ⁡ ( θ ) \displaystyle g_{\theta } =\operatorname{diag} (\theta ) gθ​=diag(θ)，進而可以訓練一個卷積核：

g θ ⋆ x = U g θ U ⊤ x g_{\theta } \star x=Ug_{\theta } U^{\top } x gθ​⋆x=Ugθ​U⊤x

然而計算U的代價太高了，是以要想辦法去近似它，有人提出，

g θ ′ ( Λ ) ≈ ∑ k = 0 K θ k ′ T k ( Λ ~ ) g_{\theta ^{\prime }} (\Lambda )\approx \sum ^{K}_{k=0} \theta ^{\prime }_{k} T_{k} (\tilde{\Lambda } ) gθ′​(Λ)≈k=0∑K​θk′​Tk​(Λ~)

其中 Λ ~ = 2 λ max ⁡ Λ − I N \displaystyle \tilde{\Lambda } =\frac{2}{\lambda _{\max}} \Lambda -I_{N} Λ~=λmax​2​Λ−IN​，現在假設 λ max ⁡ ≈ 2 \displaystyle \lambda _{\max} \approx 2 λmax​≈2,并且k=1，于是

g θ ′ ⋆ x ≈ θ 0 ′ x + θ 1 ′ ( L − I N ) x = θ 0 ′ x − θ 1 ′ D − 1 2 A D − 1 2 x g_{\theta ^{\prime }} \star x\approx \theta ^{\prime }_{0} x+\theta ^{\prime }_{1}( L-I_{N}) x=\theta ^{\prime }_{0} x-\theta ^{\prime }_{1} D^{-\frac{1}{2}} AD^{-\frac{1}{2}} x gθ′​⋆x≈θ0′​x+θ1′​(L−IN​)x=θ0′​x−θ1′​D−21​AD−21​x

最後再假設這兩個參數是共享的，可以得到：

g θ ⋆ x ≈ θ ( I N + D − 1 2 A D − 1 2 ) x g_{\theta } \star x\approx \theta \left( I_{N} +D^{-\frac{1}{2}} AD^{-\frac{1}{2}}\right) x gθ​⋆x≈θ(IN​+D−21​AD−21​)x

最後，再将中間的項用一個trick變成： I N + D − 1 2 A D − 1 2 → D ~ − 1 2 A ~ D ~ − 1 2 \displaystyle I_{N} +D^{-\frac{1}{2}} AD^{-\frac{1}{2}}\rightarrow \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}} IN​+D−21​AD−21​→D~−21​A~D~−21​，其中 A ~ = A + I N \displaystyle \tilde{A} =A+I_{N} A~=A+IN​, D ~ i i = ∑ j A ~ i j \displaystyle \tilde{D}_{ii} =\sum _{j}\tilde{A}_{ij} D~ii​=j∑​A~ij​，最後的最後，終于得到了這樣的近似卷積公式：

Z = D ~ − 1 2 A ~ D ~ − 1 2 X Θ Z=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}} X\Theta Z=D~−21​A~D~−21​XΘ

這樣我們就可以直接用神經網絡訓練了：

H ( l + 1 ) = σ ( D ~ − 1 2 A ~ D ~ − 1 2 H ( l ) W ( l ) ) H^{(l+1)} =\sigma \left(\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right) H(l+1)=σ(D~−21​A~D~−21​H(l)W(l))

參考資料

https://towardsdatascience.com/spectral-clustering-82d3cff3d3b7

https://www.cnblogs.com/pinard/p/6221564.html

https://tkipf.github.io/graph-convolutional-networks/

https://ccjou.wordpress.com/2012/04/03/%E5%82%85%E7%AB%8B%E8%91%89%E7%B4%9A%E6%95%B8-%E4%B8%8B/

https://www.matongxue.com/madocs/712/

https://www.youtube.com/watch?v=Q99ZPGnUBAQ