第二代圖卷積網(wǎng)絡(luò)：應(yīng)用快速局部譜卷積的圖卷積網(wǎng)絡(luò)

論文標(biāo)題：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
論文鏈接：https://arxiv.org/abs/1606.09375
論文來源：NeurIPS 2016

之前的文章：
①傅里葉級數(shù)與傅里葉變換
②圖神經(jīng)網(wǎng)絡(luò)中的譜圖理論基礎(chǔ)
③第一代圖卷積網(wǎng)絡(luò)：圖的頻域網(wǎng)絡(luò)與深度局部連接網(wǎng)絡(luò)

一散吵、概述

在將CNN泛化到圖數(shù)據(jù)上的一個主要的瓶頸在于局部圖卷積核的定義锅铅。本文在第一代圖卷積神經(jīng)網(wǎng)絡(luò)上進(jìn)行改進(jìn)，定義了第二代圖卷積神經(jīng)網(wǎng)絡(luò)猴凹，主要的貢獻(xiàn)如下：
①譜圖理論表達(dá)式：一種基于圖信號處理（Graph Signal Processing痒筒，GSP）中已建立的工具的圖上卷積神經(jīng)網(wǎng)絡(luò)的譜圖理論公式宰闰。
②嚴(yán)格局部化的卷積核：本文提出的卷積核在中心節(jié)點的以 $K$ 為半徑的最短路徑內(nèi)是嚴(yán)格局部化的。
③低計算復(fù)雜度：本文提出的卷積核的復(fù)雜度是和卷積核的尺寸 $K$ 以及邊的數(shù)量 $|\varepsilon |$ 成線性關(guān)系的簿透，另外由于大多數(shù)圖稀疏的移袍，我們可以估計地認(rèn)為 $|\varepsilon |\ll n^{2}$ 并且 $|\varepsilon |=kn$ ，也就是每個節(jié)點只和 $k$ 個近鄰有邊老充，這樣復(fù)雜度就和節(jié)點數(shù)量 $n$ 成線性關(guān)系葡盗。另外本方法避免了使用傅里葉基底，因此不再需要進(jìn)行昂貴的特征值分解以及存儲傅里葉基底（使用一個 $n^2$ 大小的矩陣）啡浊。除了數(shù)據(jù)觅够，本方法只需要存儲拉普拉斯矩陣這個包含 $|\varepsilon |$ 個非零值的稀疏矩陣。
④高效池化：本文提出了一種圖上的高效池化策略巷嚣。
⑤實驗結(jié)果：通過實驗證明了方法的有效性喘先，并與其他方法進(jìn)行了對比。

二廷粒、方法

將CNN泛化到圖上需要3個基本步驟：
①設(shè)計圖上的局部卷積核苹祟；
②圖的粗化（coarsening）；
③圖的池化（pooling）评雌。

學(xué)習(xí)快速局部譜卷積核

定義圖卷積核的方法分空域（spatial）和頻域（spectral）兩種≈北海空域的方法可以通過定義有限大小的卷積核來確保卷積核的局部性景东。卷積定理將卷積定義為在傅里葉基底（表示為拉普拉斯矩陣的特征向量）中對角化的線性算子，頻域方法應(yīng)用這一定理奔誓，然而頻域卷積核存在兩個限制：
①頻域卷積核并非天然局部化斤吐；
②由于需要與圖傅里葉基底相乘，會產(chǎn)生 $O(n^2)$ 的復(fù)雜度厨喂，轉(zhuǎn)換成本很高和措。在本文中上述兩個限制可以通過特殊的卷積核參數(shù)化選擇來克服，這也是本文的主要內(nèi)容之一蜕煌。

圖信號的譜卷積核

圖信號的卷積操作無法在空域完成派阱，不過通過卷積定理可以定義頻域的卷積操作，假設(shè)有圖記作 $G$ 斜纪，并且兩個圖信號 $x$ 和 $y$ 的卷積操作記作 $*_{G}$ 贫母，即：

$x\, *_{G}\, y=U((U^{T}x)\odot (U^{T}y))$

這里的 $U$ 指圖的拉普拉斯矩陣的特征向量矩陣文兑， $U$ 的每一列都是一個特征向量， $\odot$ 代指哈達(dá)瑪積腺劣。同樣的绿贞，一個圖信號 $x$ 被 $g_{\theta }$ 所卷積后得到的結(jié)果 $y$ 可以表示為：

$y=g_{\theta }(L)x=g_{\theta }(U\Lambda U^{T})x=Ug_{\theta }(\Lambda )U^{T}x$

這里的 $\Lambda$ 是特征值的對角矩陣。一個非參數(shù)化（non-parametric）的卷積核橘原，也就是說它的參數(shù)全部都是自由參數(shù)籍铁，被定義為：

$g_{\theta }(\Lambda )=diag(\theta )$

這里 $\theta \in \mathbb{R}^{n}$ ，是一個傅里葉系數(shù)向量趾断，其實可以理解為卷積核與 $U$ 相乘后的結(jié)果拒名，這個結(jié)果的每一維相當(dāng)于這一維對應(yīng)的特征向量的系數(shù)。

局部卷積核的多項式參數(shù)化

前述非參數(shù)化的卷積核有兩個局限性：
①這樣的卷積核在空間上不是局部化的歼冰；
②他們的學(xué)習(xí)復(fù)雜度是 $O(n)$ 靡狞。

這些局限性可以通過采用多項式卷積核來解決：

$g_{\theta }(\Lambda )=\sum_{k=0}^{K-1}\theta _{k}\Lambda ^{k}$

這里的 $\theta \in \mathbb{R}^{K}$ ，是多項式的系數(shù)向量隔嫡，是要學(xué)習(xí)的參數(shù)甸怕。此時，圖信號 $x$ 被 $g_{\theta }$ 所卷積后得到的結(jié)果 $y$ 為：

$y=U\left (\sum_{k=0}^{K-1}\theta _{k}\Lambda ^{k}\right )U^{T}x\\ =\left (\sum_{k=0}^{K-1}\theta _{k}U\Lambda ^{k}U^{T}\right )x\\ =\sum_{k=0}^{K-1}\theta _{k}L^{k}x$

有文獻(xiàn)可以證明腮恩，當(dāng) $d_{G}(i,j)>K$ 時有 $(L^{K})_{i,j}=0$ 梢杭， $d_{G}$ 代表最短路徑距離，也就是圖中連接兩個頂點的最小的邊的數(shù)量秸滴。也就是說這樣的卷積核是嚴(yán)格K-localized的武契。另外，需要學(xué)習(xí)的參數(shù)復(fù)雜度為 $O(K)$ 荡含，與CNN相同咒唆。

總結(jié)來說，這樣設(shè)計的卷積核有以下特點：
①卷積核只有 $K$ 個參數(shù)释液，一般 $K\ll n$ 全释，參數(shù)復(fù)雜度大大降低了；
②不需要進(jìn)行拉普拉斯矩陣的特征分解了误债，直接用拉普拉斯矩陣 $L$ 進(jìn)行變換浸船，然而由于要計算 $L^k$ ，計算復(fù)雜度還是 $O(n^3)$ 寝蹈；
③卷積核具有很好的空間局部性李命，具體來說， $K$ 就是卷積核的感受野箫老，也就是說每次卷積會將中心頂點K-hop neighbor上的feature進(jìn)行加權(quán)求和封字，權(quán)系數(shù)就是 $\theta _{k}$ 。

應(yīng)用遞歸多項式的快速卷積

非參數(shù)化的卷積核的復(fù)雜度較高，并且上述多項式卷積核的計算復(fù)雜度仍然是比較高的周叮，本小節(jié)介紹的卷積核應(yīng)用切比雪夫多項式辩撑，能夠?qū)崿F(xiàn) $O(K|\varepsilon |)$ 的復(fù)雜度。設(shè)計的思想是將 $g_{\theta }(L)$ 參數(shù)化為一個可由 $L$ 遞歸計算的多項式函數(shù)仿耽，這樣的多項式可以采用切比雪夫多項式合冀，如下：

$T_{0}(x)=1\\ T_{1}(x)=x\\ T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)$

這里需要 $x$ 在 $[-1,1]$ 之間，不熟悉切比雪夫多項式的讀者可以自行百度项贺。利用切比雪夫多項式君躺，卷積核可以設(shè)計為：

$g_{\theta }(\Lambda )=\sum_{k=0}^{K-1}\theta _{k}T_{k}(\widetilde{\Lambda })$

這里的 $\theta$ 是切比雪夫系數(shù)向量，也就是需要學(xué)習(xí)的參數(shù)开缎。 $T_{k}(\widetilde{\Lambda })\in \mathbb{R}^{n\times n}$ 是 $k$ 階的切比雪夫多項式棕叫， $\widetilde{\Lambda }=2\Lambda /\lambda _{max}-I_{n}$ ，這樣可以將特征值標(biāo)準(zhǔn)化到 $[-1,1]$ 之間奕删。如此卷積操作就是下面這樣的過程：

$y=g_{\theta }(L)x=\sum_{k=0}^{K-1}\theta _{k}T_{k}(\widetilde{L})x$

上式的推導(dǎo)過程很簡單就不贅述了俺泣，這里的 $\widetilde{L}\in \mathbb{R}^{n\times n}$ 也就是標(biāo)準(zhǔn)化以后的 $L$ ，即 $\widetilde{L}=2L/\lambda _{max}-I_{n}$ 完残。

將 $\overline{x}_{k}$ 記作 $\overline{x}_{k}=T_{k}(\widetilde{L})x\in \mathbb{R}^{k}$ 伏钠，同樣地也可以利用遞歸關(guān)系去計算 $\overline{x}_{k}=2\widetilde{L}\overline{x}_{k-1}-\overline{x}_{k-2}$ ，此時 $\overline{x}_{0}=x,\overline{x}_{1}=\widetilde{L}x$ 谨设，此時卷積的過程又可以表示為：

$y=g_{\theta }(L)x=[\overline{x}_{0},\cdots ,\overline{x}_{K-1}]\theta$

這樣設(shè)計的卷積過程的復(fù)雜度為 $O(K|\varepsilon |)$ 熟掂。對比上一小節(jié)的多項式卷積核，這里利用切比雪夫多項式設(shè)計的卷積核不再需要計算 $L^k$ 扎拣，而只是利用僅包含加減操作的遞歸關(guān)系來計算 $T_{k}(\widetilde{L})$ 赴肚，這樣大大減少了計算的復(fù)雜度。

卷積核的學(xué)習(xí)

在一個卷積層中二蓝，一個樣本 $s$ 的第 $j$ 個feature map的輸出為：

$y_{s,j}=\sum_{i=1}^{F_{in}}g_{\theta _{i,j}}(L)x_{s,i}\in \mathbb{R}^{n}$

$x_{s,i}$ 是輸入的feature map誉券，總計有 $F_{in}\times F_{out}$ 個向量 $\theta _{i,j}$ ，這些是需要學(xué)習(xí)的參數(shù)向量刊愚。

另外在訓(xùn)練時需要計算兩個梯度：

$\frac{\partial E}{\partial \theta _{i,j}}=\sum_{s=1}^{S}[\overline{x}_{s,i,0},\cdots, \overline{x}_{s,i,K-1}]^{T}\frac{\partial E}{\partial y_{s,j}}\\ \frac{\partial E}{\partial x_{s,i}}=\sum_{j=1}^{F_{out}}g_{\theta _{i,j}}(L)\frac{\partial E}{\partial y_{s,j}}$

$E$ 是損失函數(shù)横朋，由于采用多項式卷積核，不同階直接是累加關(guān)系百拓，因此無論是計算 $E$ 對 $\theta$ 還是 $x$ 的梯度，都只需要先計算 $E$ 對 $y$ 的梯度晰甚，再利用累加關(guān)系很方便地就能得到最終結(jié)果衙传，因此應(yīng)用反向傳播算法學(xué)習(xí)參數(shù)是可行的，在并行運算時也是高效的厕九。還有一點就是 $[\overline{x}_{s,i,0},\cdots, \overline{x}_{s,i,K-1}]$ 只需要計算一次蓖捶。

圖的粗化

池化操作需要將相似的節(jié)點聚類到一起，對于多層網(wǎng)絡(luò)來說做到這一點相當(dāng)于對需要保持局部幾何結(jié)構(gòu)的圖進(jìn)行多尺度聚類（multi-scale clustering）扁远。圖的聚類方法存在多種俊鱼，比如常見的譜聚類方法（參考鏈接：譜聚類|機器學(xué)習(xí)推導(dǎo)系列（二十））刻像。在本文的方法中沒有采用譜聚類這種方法，而是選擇了一種近似能夠?qū)D的規(guī)模除以2的聚類方法并闲，這樣的方法可以精確控制粗化和池化的size细睡。本文采用的圖粗化方法為Graclus多尺度聚類算法。

Graclus方法采用一種貪婪的方法來計算給定圖的連續(xù)的粗化的版本帝火，并且能夠最小化多種譜聚類的目標(biāo)溜徙，在這里選擇的目標(biāo)為normalized cut。具體的方法是在每層進(jìn)行粗化時犀填，選擇一個未標(biāo)記的節(jié)點 $i$ 蠢壹，然后選擇一個能夠最小化 $W_{ij}(1/d_{i}+1/d_{j})$ 的未標(biāo)記的鄰居節(jié)點，然后將這兩個節(jié)點標(biāo)記九巡，這兩個匹配的節(jié)點在池化時被合并图贸，合并節(jié)點的信號是這兩個節(jié)點的信號加和。上述匹配的過程一直進(jìn)行下去知道所有節(jié)點被遍歷冕广。這種方法是非呈枞眨快速的，并且能夠?qū)D的規(guī)模近似除以2佳窑，之所以近似是因為可能有一些未匹配的節(jié)點（文中稱為singleton節(jié)點）制恍。

圖信號的快速池化

池化操作被執(zhí)行多次，所以必須是高效的神凑。輸入的圖和粗化圖的節(jié)點的排列方法是無意義的净神，因此，一個直接的池化操作的方法是需要一張表來保存匹配的節(jié)點溉委，然而這種方法是內(nèi)存低效的鹃唯，并且緩慢，也不能并行處理瓣喊。本文采用的方法可以使得池化操作像1D池化那樣高效坡慌。

本文采用的方法分兩個步驟：
①創(chuàng)建一個平衡二叉樹；
②重排列所有節(jié)點藻三。

在進(jìn)行圖的粗化以后洪橘，粗化圖的每個節(jié)點要么有兩個子節(jié)點（被匹配到的節(jié)點），要么只有一個節(jié)點（singleton節(jié)點）棵帽。從最粗到最細(xì)的圖熄求，將會添加fake節(jié)點（不與圖連接在一起）到每一層來與singleton節(jié)點進(jìn)行匹配。這樣的結(jié)構(gòu)是一個平衡二叉樹逗概，主要包含3種節(jié)點：
①regular節(jié)點（或者singleton節(jié)點）弟晚，擁有兩個regular子節(jié)點（如下圖 level 1節(jié)點0）；
②regular節(jié)點（或者singleton節(jié)點），擁有一個regular節(jié)點和一個singleton節(jié)點座位子節(jié)點的節(jié)點（如下圖 level 2節(jié)點0）卿城；
③fake節(jié)點枚钓，總是擁有兩個fake子節(jié)點（如下圖 level 1節(jié)點1）。

fake節(jié)點的值初始化通常選擇一個中性的值瑟押，比如當(dāng)使用max pooling和ReLU激活函數(shù)時初始化為0搀捷。這些fake節(jié)點不與圖的節(jié)點連接，因此卷積操作不會影響到它們勉耀。雖然這些節(jié)點會增加數(shù)據(jù)的維度指煎，這樣會增加計算的花費，但是在實踐中證明Graclus方法所剩下的singleton節(jié)點是比較少的便斥。在最粗化的圖中任意排列節(jié)點至壤，然后傳播回最細(xì)的圖中，這是由于粗化圖中第 $k$ 的節(jié)點的子節(jié)點是上一層圖中的 $2k$ 和 $2k+1$ 節(jié)點枢纠，這樣就可以在最細(xì)的圖中有一個規(guī)范的排列順序像街，這里規(guī)范是指相鄰節(jié)點在較粗的層次上分層合并。這種pooling方法類似1D pooling晋渺。這種規(guī)范的排列能夠讓pooling操作非常的高效且可以并行化镰绎，并且內(nèi)存訪問是local的。下圖是這種方法的一個例子：

pooling

三木西、實驗

這里簡單列幾個實驗結(jié)果畴栖，具體實驗設(shè)置可以自行參考原論文。

MNIST數(shù)據(jù)集上對比經(jīng)典CNN

MNIST數(shù)據(jù)集上對比經(jīng)典CNN

20NEWs數(shù)據(jù)集上多種架構(gòu)效果

20NEWs數(shù)據(jù)集上多種架構(gòu)效果

MNIST數(shù)據(jù)集上多種卷積核的對比

下圖中Non-Param和Spline代表第一代GCN論文中提出的兩種卷積核八千，Chebyshev代表本文提出的卷積核：

MNIST數(shù)據(jù)集上多種卷積核的對比

GPU加速效果對比

下圖表明本文提出的GCN結(jié)構(gòu)在使用GPU加速時比經(jīng)典CNN能獲得更多的加速倍數(shù)吗讶，說明該架構(gòu)的并行化處理能力是比較可觀的：

GPU加速效果對比

最后編輯于：2024.06.20 11:49:31

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市恋捆，隨后出現(xiàn)的幾起案子照皆，更是在濱河造成了極大的恐慌，老刑警劉巖沸停，帶你破解...
沈念sama閱讀 221,548評論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件膜毁，死亡現(xiàn)場離奇詭異，居然都是意外死亡愤钾，警方通過查閱死者的電腦和手機瘟滨，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,497評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來能颁，“玉大人杂瘸，你說我怎么就攤上這事【⒆埃” “怎么了？”我有些...
開封第一講書人閱讀 167,990評論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長占业。經(jīng)常有香客問我绒怨，道長，這世上最難降的妖魔是什么谦疾？我笑而不...
開封第一講書人閱讀 59,618評論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任南蹂，我火速辦了婚禮，結(jié)果婚禮上念恍，老公的妹妹穿的比我還像新娘六剥。我一直安慰自己，他們只是感情好峰伙，可當(dāng)我...
茶點故事閱讀 68,618評論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布疗疟。她就那樣靜靜地躺著，像睡著了一般瞳氓。火紅的嫁衣襯著肌膚如雪策彤。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,246評論 1贊 308
城市分裂傳說
那天匣摘，我揣著相機與錄音店诗，去河邊找鬼。笑死音榜，一個胖子當(dāng)著我的面吹牛庞瘸，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播赠叼，決...
沈念sama閱讀 40,819評論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼擦囊，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了梅割？” 一聲冷哼從身側(cè)響起霜第，我...
開封第一講書人閱讀 39,725評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎户辞，沒想到半個月后泌类，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,268評論 1贊 320
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡底燎，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,356評論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年刃榨，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片双仍。...
茶點故事閱讀 40,488評論 1贊 352
活死人
序言：一個原本活蹦亂跳的男人離奇死亡枢希，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出朱沃，到底是詐尸還是另有隱情苞轿，我是刑警寧澤茅诱，帶...
沈念sama閱讀 36,181評論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站搬卒，受9級特大地震影響瑟俭，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜契邀，卻給世界環(huán)境...
茶點故事閱讀 41,862評論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一摆寄、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧坯门，春花似錦微饥、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,331評論 0贊 24
一樁弒父案欠橘，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至允瞧，卻和暖如春简软，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背述暂。一陣腳步聲響...
開封第一講書人閱讀 33,445評論 1贊 272
情欲美人皮
我被黑心中介騙來泰國打工痹升，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人畦韭。一個月前我還...
沈念sama閱讀 48,897評論 3贊 376
代替公主和親
正文我出身青樓疼蛾，卻偏偏與公主長得像，于是被迫代替她去往敵國和親艺配。傳聞我的和親對象是個殘疾皇子察郁，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,500評論 2贊 359

第二代圖卷積網(wǎng)絡(luò)：應(yīng)用快速局部譜卷積的圖卷積網(wǎng)絡(luò)

一散吵、概述

二廷粒、方法

三木西、實驗

推薦閱讀更多精彩內(nèi)容