Spectral GCN三部曲(二):超越經典——基於SGWT(譜方法圖小波變換)的GCN(下篇)
在前面的兩篇文章中,我們講了SGWT的由來:Spectral GCN三部曲(二):超越經典——基於SGWT(譜方法圖小波變換)的GCN(上篇),以及它的性質:Spectral GCN三部曲(二):超越經典——基於SGWT(譜方法圖小波變換)的GCN(中篇)。作為第二部曲的最後一章,我們會一睹基於SGWT的Spectral GCN的全貌。既然是千呼萬喚始出來,那就不抱琵琶不遮面了。
首先,我們來看看我們的雙核之一,在傅里葉頻域中的小波函數 。回顧之前我們提到過的關於 的設計原則:
- 是一個帶通濾波器,滿足當 時, 。當 時,也有 。這意味著: ,且當 足夠大時, 呈衰減變化。
- 在 附近可以用截斷的 項Taylor展開式來進行近似,且具有 重零根。
- 對graph小波運算元 起作用的有效區間為 ,同時這也是 的帶通區間的右界限的變化範圍。在實際應用中,我們通常使用一個近似的有效區間來代替 ,即 。原因是 可以通過Arnoldi演算法快速估算獲得,而無需進行複雜的eigendecomposition。 在數值上將滿足 的關係,以確保我們使用的近似區間包含 在內。而 可通過 計算得到, 為需要設計的超參數。同樣地, 在數值上將滿足 的關係,以確保我們使用的近似區間包含 在內。
- 在整個區間上都是平滑的。因此,對於在原點附近的Taylor單項式擬合帶,以及在遠離原點處的衰減帶,兩者之間還需要有一個過渡區間。這個過渡區間保證了上述兩個頻帶的平滑銜接。
基於以上的設計原則,我們可以將 定義為一個分段函數。其中,靠近原點的第一段函數為Taylor單項式擬合帶,它近似於一個頻通帶,帶通濾波器的帶寬主要通過它來體現;遠離原點的第三段函數為衰減帶,它近似於一個頻阻帶。而銜接第一段與第三段函數的第二段函數,則是一個平滑過渡帶。以下是其中的一種設計方式:
其中, 和 是三段函數的分界線,它們和指數冪 與 ,都是需要設計的超參數。 和 為歸一化係數,它們確保 的值都落在 0 到 1 之間。而作為過渡段的函數 ,是一個cubic spline插值函數。
cubic spline插值函數是一個三次型函數,形如: 。它通過在兩個銜接端點上同時從函數上和導數上與被銜接的函數段保持一致,從而實現平滑。即:
聯立以上四個方程,即可解出 中的各個係數,從而獲得 的表達式。
這樣,我們就得到了 的表達式。
接下來我們把目光轉向雙核中的另一位:在傅里葉頻域中的尺度函數 。
因為需要覆蓋到 覆蓋不到的低頻帶,即 需要類似於一個低通濾波器,所以它應為一個具有遞減特性的函數,且在 0 頻率處具有和 一樣的頻通效果,即 等於 的最大值。又因為 主要是作為 的一個補充,所以 和 要儘可能正交,也即是在一起覆蓋整個低頻帶的前提下,兩者的交集要越小越好,因此 最好具有足夠快的衰減速度,尤其是在靠近 的頻通帶時,這樣可以使兩者的頻通帶儘可能沒有交集。由於 的頻通帶大概是在靠近 處開始,因此,可令 在遠離 的頻通帶的區間里以較慢的速度衰減,而到了靠近 的頻通帶時開始加速衰減。綜上, 可設計為:
其中, 為帶通係數,控制著對通過濾波器的頻率的信號的縮放,其值可通過 的最大值來確定。 為衰減速度因子,控制著 衰減的速度快慢。 為加速衰減區間係數,控制著 加速衰減的區間的開始點位置。這三個參數都是需要設計的超參數。
現在, 的表達式我們也有了。收集齊了 和 後,我們就可以來打響指了...噢不好意思走錯片場了。有了 和 ,我們就可以將其拼裝成一個 SGWT 運算元了,從而把一個graph信號給安排得明明白白。
我們知道graph小波域有兩個維度,一個是graph頂點,另一個就是尺度了。前面我們都是在單一尺度下對graph小波變換進行討論,而現在,在完整的SGWT中,我們將考慮多尺度的graph小波變換。
記 SGWT 運算元為 ,它將graph信號 投影到多尺度(設為 個尺度)的graph小波域上及尺度基上,即:
同時,我們得到 的表達式:
仿照對graph的拉普拉斯矩陣 的eigenvalue 的標記方式,對於小波尺度 ,我們也將其按照數值從小到大記為 。由於各個尺度值 都是需要設計的超參數,因此我們需要一個設計的指導思想。又因為尺度值 只和 有關,因此,我們不妨先從 上看起:
由於 可以確定 的帶寬,即: 越大, 的帶寬越小, 越小, 的帶寬越大。因此,當 的帶寬最小時,取到最大尺度 ,當 的帶寬最大時,取到最小尺度 。又因為在整個區間上, 只在 上對graph小波運算元產生影響,即 的頻通帶在中的佔比,將決定graph小波運算元的尺度範圍。
因此,我們可以分析關於 取值的兩個極端情況:
- 當 的頻通帶在有效區間中的佔比最大時,意味著 的第一段函數(代表著頻通帶)所佔的有效區間最多,即 的取值區間為 。此時 的帶寬達到最大,對應著最小尺度 。在 的第一段函數的區間邊界,我們於是得到: ,即: ;
- 當 的頻通帶在有效區間中的佔比最小時,意味著 的第三段函數(代表著頻阻帶)所佔的有效區間最多,即 的取值區間為 。此時 的帶寬達到最小,對應著最大尺度 。在 的第三段函數的區間邊界,我們於是得到: ,即: 。
在得到了最大尺度 和最小尺度 之後,我們就可以通過在 和 之間,在對數尺度上進行均分,來得到中間的多個尺度了。即: ,其中, 。
關於 SGWT 的理論部分,講到這裡就基本差不多結束了。但是理論的空中樓閣再華美,終究也還是要落地觸及人間煙火的。所以,本篇的最後兩個小節,我們將分別闡述如何高效地計算 SGWT,以及如何將 SGWT 武裝到我們的Spectral GCN上。
所謂天下沒有免費的午餐,SGWT在具備更優秀的性質的同時,也帶來了龐雜的計算量。
我們可以從 SGWT 運算元 的表達式中看到,要使用 來完成變換,就要首先去計算graph尺度運算元 和graph小波運算元 。而根據矩陣函數的性質,如果一個矩陣是可對角化的,那麼作用於該矩陣的函數映射,其實就是作用在該矩陣的頻譜上,我們發現,計算 ,其實就是去計算 。而要得到graph的拉普拉斯矩陣 的eigenvalue ,就必須對其進行eigendecomposition。若是使用常用的QR分解演算法來完成對 的eigendecomposition,則會帶來 的高計算複雜度。其中 為graph上的節點數。
對於由求解 帶來的計算複雜度高的問題,一個有效的解決方案是使用一個計算複雜度低的數學表達式去近似地表達 。
Weierstrass逼近定理告訴我們:所有定義在閉區間上的連續函數 ,都可以使用一個多項式對其進行一致逼近。什麼是一致逼近呢?其實也就是說,這個用於近似表示 的多項式 ,在其所在的閉區間上的各處,逼近 的速度都是一樣的。這也就意味著, 對 的擬合誤差,在整個擬合區間上都是均勻分布的。但是,我們要怎麼找到一個這樣的多項式呢?
在實際中,常用的一種用於求解此類多項式的方法是minimax近似法:首先,給定用於進行近似的多項式 的degree(即其單項的最大指數和)和擬合區間;然後,將多項式 和被擬合函數 在擬合區間上的最大擬合誤差 作為目標函數 ;最後,對 進行最優化,求出多項式 中的各個參數。
這個通過minimax近似法求得的多項式,被稱為minimax多項式。
而截斷的Chebyshev多項式,又是minimax多項式的一個近似。在被擬合函數的平滑區域,截斷的Chebyshev多項式甚至具有比minimax多項式明顯更小的擬合誤差,同時其最大誤差也僅比minimax多項式的最大誤差略大。再加上Chebyshev多項式中的每一項,都能以一種遞推計算的方式根據前兩項來求出,且中間僅僅涉及矩陣與向量的乘法,在計算時非常快捷,因此截斷的Chebyshev多項式是一個優秀的擬合多項式候選者,而我們也將選擇它,來作為我們擬合 的工具。
和之前使用Taylor多項式進行擬合是為了說明graph小波的局部性的目的不同,這裡使用Chebyshev多項式進行擬合是為了降低計算複雜度。而擬合 ,又可以轉化為擬合 和各個 ,進而再轉化為擬合 和各個 。
用多項式來擬合一個函數的原理,其實就類似於用多個信號基來擬合信號。多項式的每一項,分別對應原函數在某個特徵空間中的一個基,而它的係數,就是原函數投影在該特徵基上的分量,因此可以通過計算原函數與特徵基的內積來得到。
原始的Chebyshev多項式具有如下的形式:
第一項 ,第二項 。從第三項起,所有的後續項都可以通過其前兩項的值遞推求出,即: 。
而原始的Chebyshev的第 項係數可通過:
計算得到。其中, 為被擬合的函數。
利用原始的Chebyshev多項式及其係數, 就可以表示成:
注意,原始的Chebyshev多項式的擬合區間為 。
對於我們的擬合對象 包含了 和各個 ,因此其擬合區間為 。該擬合區間cover了graph的傅里葉頻域上對SGWT起作用的頻帶,即屬於 的低頻部分和屬於 的 部分。
既然原始的Chebyshev多項式的擬合區間和我們需要的擬合區間不一致,那麼我們就需要對其動動手腳,使其能夠符合我們的需求。其實就是對其進行一個縮放和平移:
由於 ,所以,我們令 ,則可使得 。利用換元法,我們有:
由 組成的多項式,即是我們想要的shifted Chebyshev多項式。其形式如下:
第一項 ,第二項 。從第三項起,所有的後續項都可以通過其前兩項的值遞推求出,即: 。
而shifted Chebyshev的第 項係數可通過:
計算得到。其中, 為被擬合的函數。
利用shifted Chebyshev多項式及其係數, 就可以表示成:
於是,對於 ,有:
shifted Chebyshev的第 項係數為:
因此: 。其中, 。
記 的 項截斷shifted Chebyshev多項式為 ,則有:
對於 ,有:
shifted Chebyshev的第 項係數為:
因此: 。
記 的 項截斷shifted Chebyshev多項式為 ,則有:
一點補充說明:shifted Chebyshev多項式是原函數的展開形式,而截斷的shifted Chebyshev多項式則是原函數的近似,截斷後的多項式的項數越多,近似效果越好。
根據矩陣函數的性質,如果一個實函數 可以進行Chebyshev多項展開,那麼將該函數映射 作用於矩陣 後, 也將具有相同形式的Chebyshev多項展開(即等同於將 的Chebyshev多項展開中的 給替換成 )。因此,我們將 和 中 的 給替換成 ,得到: 其中, 。 為單位矩陣。
有了 和 ,我們就可以構造出 的近似表達式 了:
且由 可通過 和 來求解得到,易知: 也可以通過 和 來求解得到,於是有:
其中, 為graph信號。
於是, 和 就也可以通過利用遞推計算得到的 來構建。進而,我們可以藉此直接求解出 :
即我們得到了 的近似表達式 。
利用parseval定理: ,我們還可以得到轉置SGWT運算元 的近似 ,並通過它來求出逆SGWT運算元 的近似 :
由於 是從 的映射,即其自身是一個超定方程組,因此我們無法直接對其求逆,只能通過計算其偽逆(pseudo-inverse)來獲得從 的反向映射,也即逆SGWT運算元 : 。依葫蘆畫瓢,其近似表達式於是可以寫成:。
至此,SGWT的全部零件,就都煥然一「輕」了。
通過使用截斷的shifted Chebyshev多項式來作為對 的近似表達,我們避免了直接計算 所帶來的高計算複雜度:
- 如果直接計算 ,光是利用eigendecomposition來獲得 的eigenvalue 這個步驟,其中的QR分解演算法就會帶來 的計算複雜度,而總過程的計算複雜度更是高達 。 為graph上的節點數, 為SGWT的尺度數。
- 而如果通過截斷的shifted Chebyshev多項式來近似得到 ,則計算複雜度為 。 為截斷的shifted Chebyshev多項式的degree。一般情況下, 。因此,該方法能顯著地降低計算複雜度。
- 利用遞推關係式計算 ,進而得到 ,相比利用遞推關係式計算 ,進而得到 ,最後再得到 ,前者具有更低的計算複雜度。原因是前者的遞推關係式是一個"矩陣-向量"運算的式子,後續的計算都是基於向量級別的;而後者的遞推關係式是一個"矩陣-矩陣"運算的式子,後續的計算都是基於矩陣級別的。
- 由於 是一個稀疏矩陣,因此其在進行"矩陣-向量"運算時,相比於普通矩陣,具有更低的計算複雜度:前者為 ,後者為 。其中, 為 中的非零邊的數量。
- 雖然使用截斷的shifted Chebyshev多項式來近似表達 ,可以避免繁雜的eigendecomposition計算,但由於我們仍需要去確定截斷的shifted Chebyshev多項式的擬合區間,即 ,因此,我們還需要去確定 的值。這一步可以通過Arnoldi演算法來完成。Arnoldi演算法是一種迭代估計演算法,隨著迭代次數的增加,估計值將逐漸收斂至準確值。而我們只需要一個對 的粗略估計值,因為只要對該估計值取高一些,就可以保證 的準確值會被包含在擬合區間之內。此外,在Arnoldi演算法的迭代過程中所涉及的運算,都是"矩陣-向量"運算,因此其計算量也較小。
而有了這種快速演算法,我們也終於可以將SGWT應用到graph卷積中了:
記graph信號為 ,graph卷積核為 ,graph卷積運算為 ,根據卷積定理,在graph頂點域中的卷積可以轉化為在小波域中的乘積:
這就是基於SGWT的Spectral GCN的核心公式。通過它,我們可以簡便快捷地完成對graph的卷積,進而搭建我們的graph卷積神經網路:
記上式中的 ,則這個位於小波域中的graph卷積核 ,就是我們要通過神經網路來學習的對象。再結合用於擬合的截斷的shifted Chebyshev多項式,我們就得到了實際應用版的基於SGWT的Spectral GCN的卷積方程: 進而,graph卷積神經網路的各層layer之間,也就可以通過以下的遞推關係進行描述:
其中,非線性激活層可以選擇其他的非線性激活函數, 為第 層的輸入graph信號, 為第 層的輸入graph信號, 為第 層的近似SGWT運算元, 為第 層的近似逆SGWT運算元, 為第 層的graph小波域濾波核。
基於SGWT的Spectral GCN,到此就是一個成品了。和曲線救國的ChevNet不同,它真正地從本質上完成了蛻變,從而擺脫了來自SGFT的先天不足。
而既然提到了ChevNet,我們也不妨來聊聊它的一些本質。
ChevNet是在基於SGFT的GCN中,利用截斷的shifted Chebyshev多項式,對graph的傅里葉頻譜進行擬合。由於在Chebyshev多項式中,越高階的項對應的信息頻率越高,因此,截斷的shifted Chebyshev多項式也可看作是一個低通濾波器。換句話說,用它來擬合graph的傅里葉頻譜,所得到的近似graph傅里葉運算元,具有類似graph小波運算元的性質,而它實際上也就是拿一個graph小波去近似擬合在整個頂點域中蔓延的graph傅里葉頻率波。至於截斷的shifted Chebyshev多項式的階數,則控制著這個低通濾波器的帶寬,本質上就類似於graph小波運算元中的尺度因子,控制著graph小波的影響範圍,是一個超參數。但顯而易見地,ChevNet的這個類graph小波,其尺寸因子只能夠離散調節,並不夠靈活,因為Chebyshev多項式階數是一個正整數。這會帶來一個問題,就是它具有尺度盲區,即無法捕捉到某些尺寸的graph小波所覆蓋到的graph信息。而上述的基於SGWT的GCN則沒有這樣的問題,其尺度因子是連續可調的,只不過在計算的時候,我們只選取其中的一些離散點罷了。此外,ChevNet在擬合graph的傅里葉頻譜時,截斷的shifted Chebyshev多項式的階數難以確定。由於它控制著類graph小波的尺寸,當階數過高(類graph小波尺寸過大)時,會導致失去對局部信息的提取能力;而當階數過低時,作為一個用於擬合的多項式,階數越低,其擬合效果自然會越差。所以,這是一個trade-off。
在結束本部曲的最後一篇之前,我們再簡單總結一下基於SGWT的GCN的優點:
1. 相比於利用傅里葉變換對graph信號進行分解,小波分解更為稀疏,即分解冗餘度更低。
2. 相比於用傅里葉頻率基完成擬合,小波基對特徵變化劇烈的graph信號的擬合度更高。
3. 相比於傅里葉運算元,小波運算元是一個稀疏矩陣,其計算複雜度更低,佔用內存也更少。
4. 具有比基於SGFT的GCN更強大、比ChevNet更靈活的graph局部信息提取能力。
未經作者許可,本文禁止轉載。
推薦閱讀: