當前位置:成語大全網 - 書法字典 - 卷積網絡原理分析(GCN)

卷積網絡原理分析(GCN)

圖卷積網絡涉及兩個非常重要的概念:圖和卷積。傳統的卷積方法在歐洲數據空間中顯示出巨大的威力,但在非歐洲數據空間中卻是啞的。其中壹個最重要的原因是傳統的卷積方法無法在非歐數據空間中保持“平移不變性”。為了將卷積擴展到圖等非歐洲數據結構的拓撲圖,GCN誕生了。在深入了解GCN的背景之前,我認為我們有必要先了解以下概念:

基於圖自願網絡的論文鏈接半監督分類

1.拉普拉斯矩陣及其變體

給定具有節點的簡單圖是的度矩陣和的鄰接矩陣,的拉普拉斯矩陣可以表示為。圖表中的元素如下:

1.傳統傅裏葉變換

當變換對象是離散變量時,積分相當於內積,即

這裏是傳說中的拉普拉斯算子的特征函數(拉普拉斯算子是歐洲空間中的二階微分算子,卸妝後看起來很像)。

為什麽這麽說?因為從特征方程的廣義定義看,它是壹個變換,壹個特征向量或特征函數,壹個特征值。我們取基函數的二階導數,它可以看作是變換的特征函數。

在圖中,拉普拉斯矩陣可以通過譜分解(特征分解),其特征向量組成的矩陣是,根據特征方程的定義,我們可以得到它。通過比較,我們可以發現它相當於,相當於。因此,圖上的傅裏葉變換可以寫成。

從傅裏葉變換的基本思想來看,傅裏葉變換的本質是將其轉換為壹組正交基上的坐標表示進行線性變換,坐標就是傅裏葉變換的結果。下圖顯示了第壹個基礎上投影組件的大小。

我們通過矩陣乘法將圖上的傅立葉變換擴展為矩陣形式:

是圖上第個節點的特征向量,可以得到圖上的傅裏葉變換形式:

這是由圖的拉普拉斯矩陣的特征向量組成的特征矩陣的轉置。在拉普拉斯矩陣的優良性質中,我們知道由拉普拉斯矩陣的特征向量組成的矩陣是正交的,即滿足,因此圖的逆傅立葉變換形式如下:

到目前為止,我們已經通過類比將傳統的傅裏葉變換擴展到了圖上的傅裏葉變換。接下來,我們將使用傅裏葉變換的橋梁來使卷積和圖形好好喝壹杯。

前言中我們知道著名的卷積定理:函數卷積的傅裏葉變換是其傅裏葉變換的乘積,即對於,兩者的卷積是其傅裏葉變換的逆:

我們在上壹節獲得的圖表上代入傅裏葉變換公式,得到:

是Hamada乘積,意思是逐點相乘。

通常,我們將輸入圖的節點特征視為帶參數* * *的可訓練卷積核來提取拓撲圖的空間特征。為了進壹步理解卷積核,我們將上述公式改寫為:

也許有人對上面公式的變換有疑問,證明其實很簡單。有興趣的可以看看答案的答案,GCN平等的證明-知乎。

到目前為止,我們已經得出了GCN的原型。

1.第壹代GCN

卷積運算的核心是壹個可由參數* * *訓練和共享的卷積核,因此第壹代GCN直接用參數替換了上述公式中的對角元素。首先初始化賦值,然後通過反向傳播誤差調整參數。

所以第壹代GCN變成了醬:

它是圖中每個節點特征的表示向量和GCN卷積後每個節點的輸出。圖中的每個節點都要通過卷積核進行卷積以提取其對應的拓撲空間,然後通過激活函數傳播到下壹層。

第壹代GCN的缺點也很明顯,主要有以下幾點。

2.第二代GCN

面對第壹代GCN參數過多的缺點,第二代GCN進行了改進。因為圖上的傅裏葉變換是特征值的函數,所以它也可以寫成,卷積核由k階多項式改進:

代入得到:

所以第二代GCN是這樣的:

可以看出,第二代GCN的最終簡化結果不需要矩陣分解,而是直接變換拉普拉斯矩陣。參數是k壹般遠小於圖中的節點數,因此與第壹代GCN相比,第二代GCN的參數數量明顯少於第壹代GCN,從而降低了模型的復雜性。對於參數,首先初始化它們,然後根據誤差反向傳播更新參數。但是還是需要計算的,時間復雜度是。

此外,我們知道對於矩陣的K次方,我們可以得到與中心節點k-hop連接的節點,即圖中的元素是否為0表示圖中的壹個節點是否可以在k-hop後到達另壹個節點,其中K實際上表示卷積核的感受野的大小,中心節點的特征表示通過聚合每個中心節點k-hop中的相鄰節點來更新,參數是k-hop鄰居的權重。

未完待續。

1.在譜圖的卷積中,我們分解圖的拉普拉斯矩陣。傅立葉空間的特征分解有助於我們理解潛在的子圖結構。ChebyNet是使用譜域卷積的典型深度學習架構。

2.空間卷積作用於節點的鄰域,通過節點的k跳鄰居得到節點的特征表示。空間卷積比譜卷積更簡單、更有效。GraphSAGE和GAT是空間卷積的典型代表。

參考

1./

3./yyl 424525/article/details/100058264