論文標(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é)點(diǎn)的以 $K$ 為半徑的最短路徑內(nèi)是嚴(yán)格局部化的。
③低計算復(fù)雜度：本文提出的卷積核的復(fù)雜度是和卷積核的尺寸 $K$ 以及邊的數(shù)量 $|\varepsilon |$ 成線性關(guān)系的，另外由于大多數(shù)圖稀疏的，我們可以估計地認(rèn)為 $|\varepsilon |\ll n^{2}$ 并且 $|\varepsilon |=kn$ ，也就是每個節(jié)點(diǎn)只和 $k$ 個近鄰有邊，這樣復(fù)雜度就和節(jié)點(diǎn)數(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}$ 代表最短路徑距離，也就是圖中連接兩個頂點(diǎn)的最小的邊的數(shù)量。也就是說這樣的卷積核是嚴(yán)格K-localized的。另外，需要學(xué)習(xí)的參數(shù)復(fù)雜度為 $O(K)$ ，與CNN相同。

總結(jié)來說，這樣設(shè)計的卷積核有以下特點(diǎn)：
①卷積核只有 $K$ 個參數(shù)，一般 $K\ll n$ ，參數(shù)復(fù)雜度大大降低了；
②不需要進(jìn)行拉普拉斯矩陣的特征分解了，直接用拉普拉斯矩陣 $L$ 進(jìn)行變換，然而由于要計算 $L^k$ ，計算復(fù)雜度還是 $O(n^3)$ ；
③卷積核具有很好的空間局部性，具體來說， $K$ 就是卷積核的感受野，也就是說每次卷積會將中心頂點(diǎn)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ù)是可行的，在并行運(yùn)算時也是高效的。還有一點(diǎn)就是 $[\overline{x}_{s,i,0},\cdots, \overline{x}_{s,i,K-1}]$ 只需要計算一次。

圖的粗化

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

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

圖信號的快速池化

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

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

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

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