圖卷積網絡GCN的理解與介紹

卷積網絡的卷積, 本質是通過濾波器來對某個空間區域的像素點進行加權求和,得到新的特徵表示的過程. 加權係數就是卷積核的參數，如圖所示

CNN無法處理非歐幾裡得結構的數據, 因為傳統的卷積沒法處理節點關係多變的信息(沒法固定尺寸進行設置卷積核 及其他問題), 為了從這樣的數據結構有效地提取特徵, GCN成為研究熱點.

廣義上來說, 任何數據在在賦范空間內都可以建立拓撲關聯. 簡單地說, 二維圖像也可以構成拓撲圖. 如下簡單例子

先從簡單的頂點域角度說起. 定義幾個符號:

每個節點, 收集來自鄰居傳遞的信息, 然後匯總後更新自己.

比如我們疊加兩層GCN, 每個節點可以把 2-hops 鄰居的特徵加以聚合,得到自身特徵.

不同節點, 其邊的數量和權重幅值都不一樣, 比如有的節點特別多邊, 這導致多邊(或邊權重很大)的節點在聚合後的特徵值遠遠大於少邊(邊權重小)的節點. 所以需要在節點在更新自身前, 對鄰居傳來的信息(包括自環信息)進行歸一化來消除這問題, 即為

3. 譜域來解釋GCN

藉助圖譜的理論來實現拓撲圖上的卷積操作. 也是利用圖的拉普拉斯Laplacian矩陣的特徵值和特徵向量來研究圖的性質.

Graph Fourier Transformation及Graph Convolution的定義都用到圖的拉普拉斯矩陣。頻域卷積的前提條件是圖必須是無向圖，只考慮無向圖，那麼L就是對稱矩陣.拉普拉斯矩陣的定義:

常見的拉普拉斯矩陣:

雖然GCN的核心基於拉普拉斯矩陣的譜分解, 我們待會再看其理論知識, 現在先從一個簡單的類比例子加深拉普拉斯的印象.

3.1 簡單的類比例子

我們用特例(圖片像素點構造的拓撲圖)來思考頂點域角度的GCN.

之前所說每個節點聚合鄰居的節點值, 這和平滑空間濾波器的操作特別相似 (用於模糊處理或降低噪聲,如均值濾波). 但是, 節點的一些突變信息也很重要(比如說破產/暴發戶節點). 回想起銳化空間濾波器的知識, 知道微分算子的響應強度與突變程度成正比關係, 所以可以用微分來提取額外特徵信息.

圖片中, 二階微分在增強細節上要比一階微分好, 最簡單的各向同性(旋轉後結果不變)微分算子是拉普拉斯算子:

其中

常用的一種拉普拉斯濾波器為(也是

那我們 "理解" 了,

拉普拉斯算子(Laplacian operator) 的是空間二階導, 是梯度的散度. 一般可用於描述物理量的流入流出。比如說在二維空間中的溫度傳播規律. 散度為正的點是「熱源」，熱量從其中流出；散度為負的點是「冷源」，熱量流入該點.

tips:

採用拉普拉斯矩陣, 現在的論文方案可能不是說利用它來提取二階微分信息,

而是認為拉普拉斯矩陣更能表達這個拓撲圖, 其特徵向量作為基函數更有代表性.

現在很多論文也對 L 進行各種魔改, 可能是想找到個更能適應任務代表拓撲圖的矩陣.

3.2 拉普拉斯作用

濾波器通過卷積方法,能從圖片中提取特徵. 拓撲圖也是. 卷積一般在傅立葉域中計算(時域卷積=頻域相乘), 而為了滿足傅立葉變換要求, 需要找到連續的正交基對應於傅立葉變換的基. 若拿到了正交基後, 就可以進行卷積操作(在傅立葉域中計算), 得到卷積結果了.

拉普拉斯矩陣恰好滿足這些條件.

拉普拉斯是半正定實對稱矩陣, 對稱矩陣一定n個線性無關的特徵向量實對稱矩陣具有n個特徵值,所對應的n個特徵向量相互正交n階實對稱矩陣L必可對角化, 且可用正交矩陣對角化。

那可以直接將拉普拉斯矩陣譜分解:

其中

所以通過正交基

3.3 Graph上的傅立葉變換

卷積定理：函數卷積的傅立葉變換是函數傅立葉變換的乘積，即對於函數

直接說結果:

故

對於信號

逆變換為:

3.3.2 Graph上的傅立葉與逆變換

Graph上

拓撲圖的拉普拉斯矩陣L的特徵向量矩陣為

3.3.3 Graph的卷積結果

由上面可知,

其中

因為卷積核是自設計(或學習)的,可以將

其中 . (這可以理解為每個

所以Graph的卷積結果為(需要設計/學習的參數是

3.4 第一代GCN

論文 Spectral Networks and Locally Connected Networks on Graphs

直接將卷積核 從而讓:

但弊端在於:

每次前傳,都需要計算拉普拉斯矩陣的特徵向量矩陣

論文 2016_NIPS_Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering

將

圖卷積網絡 GCN Graph Convolutional Network（譜域GCN）的理解和詳細推導

如何理解 Graph Convolutional Network（GCN）？

圖卷積網絡(GCN)新手村完全指南

定義特徵向量對角矩陣的切比雪夫多項式為濾波器：

而

所以最後卷積情況為:

現在整個運算複雜度是

3.6 一階ChebNet

讓GCN火起來的是這篇文章: 2017_ICLR_Semi-supervised classification with graph convolutional networks

當ChebNet一階近似時, 讓

為了限制參數的數量以解決過度擬合, 並最小化每層的計算操作， 1-st ChebNet假設

而

其中, , 即拓撲圖加上自環.

所以論文中的快速卷積公式就是:

其中

那麼 ,就具有

其中

注意, 此時該公式和 [GCN頂點域] 解釋中的 [對稱歸一化] 公式完全一樣.

到這裡, GCN的原理就算大致介紹完畢了. 下面簡略介紹下 一階ChebNet 以及其他一些GCN論文的應用吧.

4.GCN的應用4.1 一階ChebNet的應用

在半監督的節點分類任務中, 可以構建兩層的GCN 來完成.

計算鄰接矩陣

其中

我們看看論文中提供的表格, 加深我們對不同 Propagation (及公式) 的感受.

4.2 學習類別Graph特徵與視覺向量對齊 (ZeroShot)

2018_CVPR_Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs

構建知識圖譜, 每個節點代表一個類, 利用多層的GCN進行不同類間的信息遷移.

GCN中採用歸一化後的 Binary 鄰接矩陣. 代碼中查得採用對稱歸一化鄰接矩陣, 即傳播模式為:

GCN的輸入是每類的Word Embedding 向量, 最後一層的輸出維度

採用的數據集是 Imagenet, 類別間的關係可從Imagenet官網中提取.

4.3 構建加權的密集圖_信息傳播更廣且避免平滑_與視覺向量對齊(ZeroShot)

2019_CVPR_Rethinking Knowledge Graph Propagation for Zero-Shot Learning

簡單地疊加普通GCN層雖然能讓知識的傳播範圍增廣, 但也容易讓節點平滑(稀釋了知識), 而降低了性能. 該文章提出一種密集設計的圖, 讓遠距離(但有關係)的節點之間能直接連接進行傳播.

簡單地說, 以前都是親兄弟節點才有聯繫(連線), 如果想讓那些表表表親戚的信息傳播過來, 需要疊加GCN層, 這樣會導致信息稀釋(或說平滑). 而該論文就直接讓同一個血緣(或說比較親的血緣關係)的大家族都有線相連接(設置不同的權重), 那淺層的GCN網絡就可以讓遠方親戚的信息傳播過來.

本文基於節點之間的距離學習權重. 明確利用知識圖的層次結構，構建密集連接結構. 節點匯集信息時分為"從祖先輩獲得的信息"和"從子孫輩獲得的信息"階段.

由於傳播時文中定義"先從子輩匯聚信息", 再從"父輩匯聚信息", 所以本文的GCN傳播為:

定義表示可學習參數來獲得ancestor 和 descendant的權重, K 表示 K -hops的距離. 那麼就可以讓邊的權重

重新修改GCN傳播方式:

訓練時的步驟為:

第一步, 訓練圖卷積網絡DGP, 讓其來預測CNN最後的FC層權重(即對齊視覺向量), 用均方誤差.第二步, 讓DGP預測值替代FC的視覺權重, 從而微調CNN網絡.4.4 GCN網絡的改進-殘差結構與擴張卷積

2019_CVPR_Oral_Can GCNs Go as Deep as CNNs?

CNN的成功的一個關鍵因素是能夠設計和訓練一個深層的網絡模型。但多層 GCN 會導致提取消失, 導致定點過度平滑, 讓頂點特徵值收斂到一致的值, 導致目前 GCN 架構都非常淺. 而且,淺層GCN 的感受野有限.

故本文藉助CNN的概念, 把 Residual, Dense connections (殘差,密集連接) 和 dilated convolutions(擴張/空洞卷積) 應用到GCN架構中.

幾種結構

殘差結構中, 通過逐點加法, 讓節點(經過GCN得到的)殘差特徵, 加上節點原來的特徵, 作為最後的節點新特徵:

遇到維度不一致問題, 則跟殘差網絡一樣進行轉換(用GCN). 那麼密集連接類似上述公式一樣處理.

擴張卷積中, 每個GCN層後用 Dilated k-NN去尋找擴張鄰居, 並構建擴張圖, 在訓練時採用隨機擴張的方式(按概率進行擴張聚合). 其他細節的從CNN類比過來即可.

GCN的聚合函數

一般GCN中的聚合函數是 sum aggregator, 將鄰域信息直接相加, 而同時也有 mean aggregator(和sum相像,歸一化後的sum), max-pooling, attention, LSTM 等等聚合方式.

本文採用的是 簡單無參數的max-pooling頂點特徵聚集器. GCN結構是帶BN+ReLU 的MLP.

Dynamic Edgs

GCN在訓練中, 圖結構一般是保持不變的. 有研究表明, 與具有固定圖結構的GCN相比，動態圖卷積可以更好地學習圖的表示.

讓節點的邊動態變化, 能 有助於緩解過度平滑問題, 也能產生較大的感受野. 本文中每一層特徵空間中通過 Dilated k-NN 來重新計算頂點之間的邊, 來動態變化拓撲圖.

雖然有改進, 但是計算成本較高.

4.5 GCN的改進-圖注意力網絡GAT

2018_ICLR_Graph Attention Networks

GCN局限有: 難處理動態圖; 難分配不同的權重給不同的neighbor.

其實GAT是GNN的改進, 與GCN類似, 只是它是基於self-attention的圖模型.

本文: 對不同的相鄰節點學習分配相應的權重, multi-head多頭的Attention結構, 計算注意力係數

對於頂點

即先用共享參數

通過對

加權求和 aggregate

一般來說,聚合方式一般將鄰居傳來特徵進行加權求和, 即可更新本節點的特徵:

本文中增強了集合的方式, 採用 K 個注意力機制, 即用了K種鄰居加權方式, 來更新本節點特徵. 即Attention中的multi-head思想:

歡迎指正討論 ~