辦文明網(wǎng)站 做文明網(wǎng)民活動關(guān)鍵詞查詢網(wǎng)
2 FAST? APROXIMATE? CONVOLUTIONS ON GRAPHS
在這一章節(jié),我們?yōu)檫@種特殊的的圖基礎(chǔ)的神經(jīng)網(wǎng)絡(luò)模型f(X, A)提供理論上的支持。我們考慮一個多層的圖卷積網(wǎng)絡(luò)(GCN),它通過以下方式進(jìn)行層間的傳播:
這里,是無向圖鄰接矩陣加上自己本身。
是對稱矩陣,
,
是層的訓(xùn)練權(quán)重矩陣。
表示激活函數(shù),例如ReLu.
是
層的激活矩陣,
.在接下來中,我們將會展示,這種規(guī)則的傳播方式是局部譜域濾波的一階近似。
2.1 SPECTRAL GRAPH CONVOLUTIONS
我們考慮圖上的譜域卷積 : 多維信號,用參數(shù)
定義的傅里葉過濾器
,i.e.:
這里U是歸一化的圖拉普拉斯矩陣的特征向量矩陣,這里,
對角矩陣是特征值,
是x的圖傅里葉的轉(zhuǎn)換。我們可以理解
是拉普拉斯矩陣L的特征值的函數(shù),即
。計算公式(3)是非常繁重的計算,因為特征向量的矩陣U的乘法是
。并且,在大的圖上計算L的特征值分解,其計算量之大以至于無法做到。為了規(guī)避在大圖上特征值分解的問題,
近似是切比雪夫多項式
級截斷
?:
。
表示L的最大特征值。
是切比雪夫向量的系數(shù)。切比雪夫多項式遞歸地定義為
,這里面
。
回到我們信號x過濾器
這里;可以輕易驗證
。這個表達(dá)式是K階截斷的拉普拉斯多項式近似,它依賴于中心節(jié)點周圍做多K個節(jié)點的作用。公式 5的復(fù)雜度是
,隨著邊的數(shù)量線性增長。Defferrard et al 使用K階卷積定義了圖上的卷積網(wǎng)絡(luò)。
2.2 LAYER-WISE LINEAR MODEL
通過公式5,圖卷積神經(jīng)網(wǎng)絡(luò)可以疊多個卷積層,每一層都是非線性的?,F(xiàn)在,如果我們將層的卷積操作K=1,即圖譜域拉普拉斯矩陣L的限行函數(shù)。
這種一階的線性方式,我們?nèi)匀豢梢粤_列多層的卷積層,這不局限于切比雪夫多項式。我直覺期望這樣的模型能夠?qū)τ邳c的度數(shù)很高的分布(例如,社交網(wǎng)絡(luò)、引用網(wǎng)絡(luò)、知識圖譜和其他一些真實世界的數(shù)據(jù)庫)的圖結(jié)構(gòu)起到減輕過擬合的作用。并且,對于一定的計算資源,這種一階的layer-wise方式能夠建立更深的網(wǎng)絡(luò)。
這樣一種GCN的方式,我們近似,訓(xùn)練過程中,網(wǎng)絡(luò)的參數(shù)適應(yīng)如下方式:
這里2個自由參數(shù)和
。這個過濾器的參數(shù)被整個網(wǎng)絡(luò)共享。多層卷積過濾能夠卷積到一個節(jié)點的第
層鄰居,k就是圖神經(jīng)網(wǎng)絡(luò)卷積層的層數(shù)。
在實際中,限制參數(shù)的數(shù)量以減少計算(例如矩陣乘法)已解決過擬合的問題,這種優(yōu)化可以得到如下公式
一個參數(shù)。注意
的特征值取值范圍在
。在神經(jīng)網(wǎng)絡(luò)里面疊多層這樣的操作將導(dǎo)致數(shù)值不穩(wěn)定,以及神經(jīng)網(wǎng)絡(luò)梯度的消失。為了有效緩解這個問題,我們將使用再歸一化的技巧:
,
和
。
我們可以將上述的定義真正泛化到一個信號,帶有C個輸入通道(例如,每一個節(jié)點有C維的特征向量),F過濾和特征映射如下:
這里是過濾矩陣的參數(shù),
是卷積信號矩陣。這個過濾操作有
的復(fù)雜度,
是稀疏矩陣和稠密矩陣的乘積。