第一代圖卷積網(wǎng)絡(luò)：圖的頻域網(wǎng)絡(luò)與深度局部連接網(wǎng)絡(luò)

論文標(biāo)題：Spectral Networks and Locally Connected Networks on Graphs
論文鏈接：https://arxiv.org/abs/1312.6203
論文來源：NeurIPS 2014

本文需要的前置知識(shí)：傅里葉變換與譜圖理論基礎(chǔ)
鏈接：
①傅里葉級(jí)數(shù)與傅里葉變換
②圖神經(jīng)網(wǎng)絡(luò)中的譜圖理論基礎(chǔ)

一栖茉、概述

CNN在機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)的一些問題上取得了比較成功的效果，這主要得益于它處理的底層數(shù)據(jù)通常有一個(gè)坐標(biāo)網(wǎng)格結(jié)構(gòu)（在1何陆，2，3維度上）胸囱，因此這些數(shù)據(jù)就存在平移不變性（ translational equivariance/invariance）。圖像蚁趁、語音据途、視頻就屬于這一類數(shù)據(jù)。由于網(wǎng)絡(luò)不具備平移不變性（網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)的鄰居數(shù)量是不固定的）朱巨，因此在網(wǎng)絡(luò)上直接應(yīng)用CNN是比較困難的史翘。

對(duì)于常規(guī)的網(wǎng)格數(shù)據(jù)，CNN能夠利用以下幾個(gè)很好地結(jié)合在一起的結(jié)構(gòu)來大大減少系統(tǒng)中的參數(shù)數(shù)量：
①平移結(jié)構(gòu)（translation structure）蔬崩，使用濾波器在數(shù)據(jù)的網(wǎng)格結(jié)構(gòu)上平移處理數(shù)據(jù)恶座，從而實(shí)現(xiàn)參數(shù)共享，并沒有使用線性映射沥阳；
②網(wǎng)格上的度量跨琳，使用緊湊支持濾波器（compactly supported filters），緊湊支持濾波器是指與輸入數(shù)據(jù)大小無關(guān)的濾波器桐罕，它的大小可能遠(yuǎn)小于輸入數(shù)據(jù)的大新鋈谩；
③網(wǎng)格的多尺度二元聚類（multiscale dyadic clustering）功炮，是指CNN應(yīng)用了跨步卷積（stride convolution）和池化（pooling）來進(jìn)行下采樣（subsampling）溅潜。

如果網(wǎng)格數(shù)據(jù)有 $n$ 個(gè)坐標(biāo)，數(shù)據(jù)的維度為 $d$ （舉例來說薪伏，圖片的坐標(biāo)數(shù)就是像素點(diǎn)數(shù)滚澜，維度就是圖片的通道數(shù)，彩色圖為 $3$ 嫁怀，灰度圖為 $1$ ）设捐，如果使用有 $m$ 的輸出節(jié)點(diǎn)的全連接網(wǎng)絡(luò)就需要 $n\times m$ 個(gè)參數(shù)，相當(dāng)于 $O(n^2)$ 的參數(shù)復(fù)雜度塘淑。使用任意的濾波器（也就是①）而非全連接網(wǎng)路能將參數(shù)復(fù)雜度降低到 $O(n)$ 萝招，使用網(wǎng)格上的度量結(jié)構(gòu)（也就是②）來構(gòu)建局部連接網(wǎng)絡(luò)也可以。而如果兩種一起使用能夠?qū)?fù)雜度降低到 $O(k\cdot S)$ 存捺，這里的 $k$ 代表數(shù)據(jù)feature map的數(shù)量槐沼， $S$ 代表卷積核的數(shù)量，此時(shí)復(fù)雜度與 $n$ 無關(guān)捌治。最后使用網(wǎng)格的多尺度二元聚類（也就是③）可以進(jìn)一步降低復(fù)雜度岗钩。

然而某些數(shù)據(jù)并不具備上述幾何結(jié)構(gòu)，比如表面張力或溫度肖油、從一個(gè)氣象臺(tái)網(wǎng)絡(luò)中觀測(cè)到的數(shù)據(jù)兼吓、來自社交網(wǎng)絡(luò)或協(xié)同過濾的數(shù)據(jù)，這些數(shù)據(jù)都不能直接應(yīng)用CNN构韵。雖然CNN可以應(yīng)用于多層周蹭，但是在特征維度上沒有假設(shè)任何幾何屬性趋艘，導(dǎo)致一個(gè)4-D tensor只能沿其空間坐標(biāo)進(jìn)行卷積，即對(duì)于一個(gè)4-D的tensor而言凶朗，其有 $X,Y,Z,feature$ 四個(gè)維度瓷胧，典型的CNN只能對(duì) $X,Y,Z$ 三個(gè)維度（即空間維度）進(jìn)行卷積操作（通過3D convolution 操作），而不能對(duì) $feature$ 維度（特征維度）進(jìn)行操作棚愤。

網(wǎng)絡(luò)提供了低維網(wǎng)格數(shù)據(jù)的一種泛化的框架搓萧，也就是GCN是CNN在domain上的推廣，推廣的方式是通過推廣卷積的概念宛畦。在本文中將會(huì)討論將深度卷積應(yīng)用于網(wǎng)絡(luò)數(shù)據(jù)的方法瘸洛。本文一共提供兩種架構(gòu)。第一種為空域架構(gòu)（spatial construction）次和，這種架構(gòu)能夠?qū)W(wǎng)絡(luò)數(shù)據(jù)應(yīng)用上述②和③反肋，應(yīng)用它們可以構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)的局部連接網(wǎng)絡(luò)，參數(shù)復(fù)雜度為 $O(n)$ 而非 $O(n^2)$ 踏施。另一種架構(gòu)稱為頻域架構(gòu)（spectral construction）石蔗，能夠在傅里葉域內(nèi)應(yīng)用卷積。頻域架構(gòu)對(duì)于每一個(gè)feature map最多需要 $O(n)$ 的參數(shù)復(fù)雜度畅形，也可以構(gòu)建參數(shù)數(shù)量與 $n$ 無關(guān)的架構(gòu)养距。這兩種架構(gòu)都可以應(yīng)用高效的前向傳播并且能夠應(yīng)用在有多個(gè)坐標(biāo)的數(shù)據(jù)的數(shù)據(jù)集上。

二日熬、空域架構(gòu)

網(wǎng)絡(luò)數(shù)據(jù)將由一個(gè)加權(quán)圖 $G=(\Omega ,W)$ 來表示棍厌， $\Omega$ 是一個(gè)離散的節(jié)點(diǎn)集合，大小為 $m$ 竖席， $W$ 是一個(gè)對(duì)稱半正定矩陣耘纱，也就是加權(quán)鄰接矩陣。將CNN泛化到網(wǎng)絡(luò)數(shù)據(jù)的最直接想法是應(yīng)用多尺度的怕敬、層級(jí)的局部感受野揣炕。

通過 $W$ 定義局部性

在網(wǎng)絡(luò)上可以輕松的定義局部性（locality）的概念帘皿。邊的權(quán)重決定了節(jié)點(diǎn)的局部性东跪，舉例來說，可以設(shè)置一個(gè)閾值 $\delta$ 來決定一個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合：

$N_{\delta }(j)=\left \{i\in \Omega :W_{ij}>\delta \right \}$

我們可以將注意力限制在稀疏的濾波器上鹰溜，這些濾波器通過節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合來定義感受野虽填，以此來構(gòu)建局部連接網(wǎng)絡(luò)，這樣可以將參數(shù)量降低為 $O(S\cdot n)$ 曹动，這里的 $S$ 代表平均鄰居節(jié)點(diǎn)數(shù)量斋日。

圖的多尺度聚類

CNN通過池化和下采樣來降低網(wǎng)格的大小，這一操作也就是網(wǎng)格的多尺度聚類（ multiscale clustering）：為每個(gè)cluster輸入多個(gè)特征墓陈，輸出一個(gè)特征恶守。在圖上被證明更為有效的聚類方法仍然有待研究第献，在本文中選擇了一種比較樸素的聚類方法。如下圖所示兔港，下圖中有兩層聚類庸毫，灰色的點(diǎn)為數(shù)據(jù)中的無向圖節(jié)點(diǎn)，然后進(jìn)行聚類得到下一層帶顏色的節(jié)點(diǎn)衫樊，然后再對(duì)這些帶顏色的節(jié)點(diǎn)進(jìn)行聚類飒赃，第一層為12個(gè)節(jié)點(diǎn)，第二層6個(gè)節(jié)點(diǎn)科侈，第三層3個(gè)節(jié)點(diǎn)：

圖上的聚類

深度局部連接網(wǎng)絡(luò)

本文提出的空域架構(gòu)也叫做深度局部連接網(wǎng)絡(luò)（Deep Locally Connected Networks）载佳。在這個(gè)架構(gòu)中使用了網(wǎng)絡(luò)的多尺度聚類，事實(shí)上這里的尺度可以認(rèn)為是下采樣的層數(shù)臀栈，在這里我們考慮 $K$ 個(gè)尺度蔫慧，實(shí)際上也就是說這個(gè)架構(gòu)由 $K$ 個(gè)卷積層，每個(gè)卷積層后面都有一個(gè)池化層（也就是進(jìn)行一次聚類）权薯，因此這個(gè)架構(gòu)中總共有 $K$ 層藕漱，每層包括一個(gè)個(gè)卷積層和一個(gè)池化層。

我們?cè)O(shè)置 $\Omega _{0}=\Omega$ 崭闲，也就是輸入層的節(jié)點(diǎn)集合肋联，可以認(rèn)為是第0層，每一層的節(jié)點(diǎn)集合記作 $\Omega _{k}$ 刁俭，這里 $k=1,2,\cdots ,K$ 橄仍， $\Omega _{k}$ 可以認(rèn)為是將 $\Omega _{k-1}$ 聚成 $d_k$ 個(gè)簇的一個(gè)劃分，因此 $d_k$ 就表示第 $k$ 層的節(jié)點(diǎn)個(gè)數(shù)牍戚，有 $d_{k}=|\Omega _{k}|$ 侮繁。另外定義 $\Omega _{k-1}$ 的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合的表示：

$N_{k}=\left \{N_{k,i};i=1,2,\cdots d_{k-1}\right \}$

注意這里 $N_{k}$ 的下標(biāo)雖然為 $k$ ，但它代表的是第 $k-1$ 的節(jié)點(diǎn)集合 $\Omega _{k-1}$ 的每個(gè)節(jié)點(diǎn)的鄰域的表示如孝，里面的每個(gè) $N_{k,i}$ 都是一個(gè)集合宪哩。

有了上述定義現(xiàn)在我們可以定義網(wǎng)絡(luò)的第 $k$ 層。假設(shè)輸入信號(hào)是 $\Omega _{0}$ 上的實(shí)值信號(hào)第晰，以 $f_k$ 來代表第 $k$ 層的卷積核的數(shù)量锁孟，也代表了第 $k$ 層feature map的數(shù)量和信號(hào)的維度（類比CNN，卷積核的數(shù)量等于feature map的數(shù)量茁瘦，也就是卷積后的信號(hào)特征的維度）品抽。每一層都會(huì)將 $\Omega _{k-1}$ 上的 $f_{k-1}$ 維的信號(hào)轉(zhuǎn)換成 $\Omega _{k}$ 上的 $f_{k}$ 維的信號(hào)，這一過程會(huì)權(quán)衡空間分辨率和新創(chuàng)建的特征坐標(biāo)甜熔，也就是說圆恤，雖然經(jīng)過每一層的節(jié)點(diǎn)數(shù)量降低了，但是卷積核的數(shù)量會(huì)逐層增加以保證特征的維度會(huì)增加腔稀，也就是說每層有兩個(gè)結(jié)果：
①空間分辨率降低（loses spatial resolution）盆昙，即空間點(diǎn)數(shù)減少羽历；
②濾波器數(shù)目增加（increases the number of filters），即每個(gè)點(diǎn)特征數(shù) $d_k$ 增加淡喜。

第 $k$ 層的輸入用 $x_{k}=(x_{k,i};i=1,2,\cdots ,f_{k-1})$ 來表示窄陡，這里的 $x_{k}$ 是一個(gè) $d_{k-1}\times f_{k-1}$ 的矩陣， $x_{k,i}$ 可以認(rèn)為是一個(gè)列向量拆火， $x_{k,i}$ 也就相當(dāng)于第 $i$ 個(gè)feature map的信號(hào)跳夭。那么第 $k$ 層的輸出 $x_{k+1}$ 就被定義為：

$x_{k+1,j}=L_{k}h\left (\sum_{i=1}^{f_{k-1}}F_{k,i,j}x_{k,i}\right )\; \; \; (j=1,2,\cdots ,f_{k})$

這里的 $F_{k,i,j}$ 代表第 $k$ 層的第 $j$ 個(gè)卷積核對(duì)第 $k-1$ 層的第 $i$ 個(gè)feature map進(jìn)行卷積的部分，注意由于圖的節(jié)點(diǎn)的鄰居分布情況不同们镜，所以卷積核不像CNN那樣是共享的币叹。這里的 $F_{k,i,j}$ 是一個(gè) $d_{k-1}\times d_{k-1}$ 的稀疏矩陣，矩陣的第 $m$ 行的非零值都只會(huì)存在于 $N_{k,m}$ 所指定的第 $m$ 個(gè)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)位置模狭。 $h$ 代表非線性激活函數(shù)颈抚。 $L_k$ 代表對(duì)卷積的結(jié)果進(jìn)行之前所述的池化操作來降低節(jié)點(diǎn)的數(shù)量， $L_k$ 相當(dāng)于聚類的結(jié)果嚼鹉，是一個(gè) $d_{k}\times d_{k-1}$ 的稀疏矩陣贩汉，每一行指示一個(gè)簇的分布，如果采用平均池化锚赤，那么 $L_k$ 的一個(gè)例子（ $d_{k}=3,d_{k-1}=6$ ）可以是：

$L_{k}=\begin{vmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\ 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \end{vmatrix}$

整個(gè)過程可以用下圖來表示：

空域架構(gòu)

另外通過以下過程構(gòu)建第 $k$ 層的 $W_k$ 和 $N_k$ ：

$W_{0}=W\\ A_{k}(i,j)=\sum _{s\in \Omega _{k}(i)}\sum _{t\in \Omega _{k}(j)}W_{k-1}(s,t),\; (k\leq K)\\ W_{k}=rownormalize(A_{k}),\; (k\leq K)\\ N_{k}=supp(W_{k}),\; (k\leq K)$

這里 $A_{k}(i,j)$ 的計(jì)算過程是指：由于 $\Omega _{k}$ 中的節(jié)點(diǎn)來自 $\Omega _{k-1}$ 中的節(jié)點(diǎn)的聚類瓢省，所以 $i,j$ 之間的權(quán)重是 $i$ 和 $j$ 對(duì)應(yīng)的聚類之前的 $\Omega _{k-1}$ 中節(jié)點(diǎn)之間所有權(quán)重的累加羔飞。 $\Omega _{k}$ 是對(duì) $\Omega _{k-1}$ 的聚類，圖聚類的方法是多種多樣的，可以自行選取睦尽，這里的方法是采用 $W_{k}$ 的 $\epsilon$ - covering混巧，使用核函數(shù) $K$ 的 $\Omega$ 的 $\epsilon$ - covering是一個(gè)劃分 $P=\left \{P_{1},P_{2},\cdots ,P_{n}\right \}$ 姜挺，滿足：

$sup_{n}sup_{x,x^{'}\in P_{n}}K(x,x^{'})\geq \epsilon$

以 $S_k$ 代表平均節(jié)點(diǎn)數(shù)量盐类，那么第 $k$ 層用來學(xué)習(xí)的參數(shù)量為：

$O(S_{k}\cdot |\Omega _{k}|\cdot f_{k}\cdot f_{k-1})=O(n)$

實(shí)踐中通常有 $S_{k}\cdot |\Omega _{k}|\approx \alpha \cdot |\Omega _{k-1}|$ ， $\alpha$ 是下采樣因子寓落，滿足 $\alpha \in(1,4)$ 括丁。

評(píng)價(jià)

這種架構(gòu)的優(yōu)點(diǎn)在于不需要很強(qiáng)的前提假設(shè)，只需要圖具備鄰域結(jié)構(gòu)即可伶选，甚至不需要很好的embedding向量史飞。但是缺點(diǎn)在于沒辦法進(jìn)行參數(shù)共享，對(duì)于每一層的每一個(gè)節(jié)點(diǎn)都要有單獨(dú)的參數(shù)進(jìn)行卷積而不能像CNN那樣使用同一個(gè)卷積核在數(shù)據(jù)網(wǎng)格上進(jìn)行平移考蕾。

三祸憋、頻域架構(gòu)

圖的拉普拉斯矩陣

在這里会宪，以 $D$ 代表圖的度矩陣肖卧， $W$ 代表圖的加權(quán)鄰接矩陣，常用的圖的拉普拉斯矩陣有三種：
①Combinatorial Laplacian掸鹅，也就是普通形式的拉普拉斯矩陣：

$L=D-W$

其中的元素為：

$L_{i,j}=\left\{\begin{matrix} d_{i},i=j \\ -w_{ij},i\neq j\; and\; v_{i}\; is\; adjacent\; to\; v_{j}\\ 0,otherwise \end{matrix}\right.$

②Symmetric normalized Laplacian塞帐，也就是對(duì)稱歸一化的拉普拉斯矩陣：

$L^{sys}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2}$

其中的元素為：

$L_{i,j}^{sys}=\left\{\begin{matrix} 1,i=j\; and\; d_{i}\neq 0\\ -\frac{w_{ij}}{\sqrt{d_{i}d_{j}}},i\neq j\; and\; v_{i}\; is\; adjacent\; to\; v_{j}\\ 0,otherwise \end{matrix}\right.$

③Random walk normalized Laplacian拦赠，也就是隨機(jī)游走歸一化拉普拉斯矩陣：

$L^{rw}=D^{-1}L=I-D^{-1}W$

其中的元素為：

$L_{i,j}^{rw}=\left\{\begin{matrix} 1,i=j\; and\; d_{i}\neq 0 \\ -\frac{w_{ij}}{d_{i}},i\neq j\; and\; v_{i}\; is\; adjacent\; to\; v_{j}\\ 0,otherwise \end{matrix}\right.$

加權(quán)圖的調(diào)和分析

為簡(jiǎn)便起見，本文應(yīng)用的是第①種葵姥。對(duì)于一個(gè)固定的加權(quán)鄰接矩陣 $W$ 荷鼠，不同的節(jié)點(diǎn)信號(hào)列向量 $x\in \mathbb{R}^{m}$ （也就是說網(wǎng)絡(luò)有 $m$ 個(gè)節(jié)點(diǎn)）有不同的平滑性（smoothness）度量 $||\nabla x||_{W}^{2}$ ，在節(jié)點(diǎn) $i$ 處的平滑性度量為：

$||\nabla x||_{W}^{2}(i)=\sum _{j}w_{ij}[x(i)-x(j)]^{2}$

所有信號(hào)的平滑性度量為：

$||\nabla x||_{W}^{2}=\sum _{i}\sum _{j}w_{ij}[x(i)-x(j)]^{2}$

其實(shí) $||\nabla x||_{W}^{2}$ 也就是 $x^{T}Lx$ 榔幸，關(guān)于拉普拉斯矩陣與信號(hào)平滑性的關(guān)系已經(jīng)在本文開頭給出的文章鏈接里介紹過了允乐，這里不再贅述。

有了上面的公式我們可以得出最平滑的信號(hào) $x$ 其實(shí)是一個(gè)歸一化的全 $1$ 向量：

$v_{0}=\underset{x\in \mathbb{R}^{m}\; ||x||=1}{argmin}||\nabla x||_{W}^{2}=(1/\sqrt{m})1_{m}$

事實(shí)上 $\mathbb{R}^{m}$ 空間中最平滑的 $m$ 個(gè)相互正交的單位向量其實(shí)就是 $L$ 的特征向量：

$v_{i}=\underset{x\in \mathbb{R}^{m}\; ||x||=1\; x\perp \left \{v_{0},\cdots ,v_{i-1}\right \}}{argmin}||\nabla x||_{W}^{2}$

每個(gè)特征向量 $v_{i}$ 的平滑性度量的值其實(shí)也就是特征值 $\lambda _{i}$ 削咆，這一點(diǎn)只需要代入計(jì)算一下就可以得出牍疏，拉普拉斯矩陣的譜分解為 $L=V\Lambda V^{-1}=V\Lambda V^{T}$ ，這里的 $\Lambda$ 為特征值構(gòu)成的對(duì)角矩陣拨齐， $V$ 為特征向量構(gòu)成的正交矩陣鳞陨， $V$ 的每一列都是一個(gè)特征向量，那么 $v_{i}^{T}Lv_{i}$ 計(jì)算一下就可以得到等于特征值 $\lambda _{i}$ 瞻惋，因此最平滑的信號(hào)向量就是特征值最小的特征向量厦滤，拉普拉斯矩陣的特征值就代表了特征向量的平滑度。

上面提到的一組特征向量其實(shí)就是 $\mathbb{R}^{m}$ 空間的一組基歼狼，前面的文章里說過圖傅里葉變換其實(shí)就是將信號(hào)向量投影到拉普拉斯矩陣的各個(gè)特征向量上：

$F(\lambda _{k})=\sum_{i=1}^{m}x(i)v_{k}(i)$

特征值的大小表示平滑程度掏导，它對(duì)應(yīng)傳統(tǒng)傅里葉變換中的頻率，頻率高表示短時(shí)間內(nèi)變動(dòng)多羽峰，和這里的相鄰節(jié)點(diǎn)變動(dòng)大（變動(dòng)越大越不平滑）能對(duì)應(yīng)起來碘菜。因此圖傅里葉變換就是在將一個(gè)圖信號(hào)分解到不同平滑程度的圖信號(hào)上，就像傳統(tǒng)傅里葉變換將函數(shù)分解到不同頻率的函數(shù)上一樣限寞。

一個(gè)任意信號(hào)向量 $x$ 分解到所有的特征向量上對(duì)應(yīng)的每個(gè)系數(shù)用 $a_{i}$ （ $a_{i}=F(\lambda _{i})$ 忍啸，這些系數(shù)也就是圖傅里葉變換后的系數(shù)）表示， $x$ 可以表示為 $\sum_{i=1}^{m}a_{i}v_{i}$ 履植，也就是 $Va$ 计雌，那么 $x$ 的平滑性度量的值可以用這些系數(shù)和特征值表示：

$x^{T}Lx=(Va)^{T}LVa\\ =a^{T}V^{T}LVa\\ =a^{T}V^{T}V\Lambda V^{T}Va\\ =a^{T}I\Lambda Ia\\ =a^{T}\Lambda a\\ =\sum_{i=1}^{m}a_{i}^{2}\lambda _{i}$

圖卷積

兩個(gè)函數(shù) $f$ 和 $g$ 進(jìn)行卷積可以應(yīng)用卷積定理，用公式表達(dá)卷積定理就是：

$F(f*g)=F(f)\cdot F(g)$

應(yīng)用卷積定理可以在頻域上進(jìn)行圖的卷積操作玫霎，具體的方法是將濾波器 $h$ 和圖信號(hào) $x$ 都通過圖傅里葉變換轉(zhuǎn)換到頻域然后計(jì)算轉(zhuǎn)換后的結(jié)果的乘積（哈達(dá)瑪積凿滤，也就是向量對(duì)應(yīng)元素相乘），然后將相乘的結(jié)果再通過圖傅里葉逆變換轉(zhuǎn)換回空域庶近，整個(gè)過程如下：

$h*x=F^{-1}\left \{F\left \{h\right \}\cdot F\left \{x\right \}\right \}\\ =F^{-1}\left \{\hat{h}\cdot \hat{x}\right \}\\ =F^{-1}\left \{\hat{h}\cdot V^{T}x\right \}\\ =F^{-1}\left \{diag[\hat{h}_{1},\cdots ,\hat{h}_{m}]V^{T}x\right \}\\ =Vdiag[\hat{h}_{1},\cdots ,\hat{h}_{m}]V^{T}x$

這里將 $\hat{h}$ 組織成對(duì)角矩陣 $diag[\hat{h}_{1},\cdots ,\hat{h}_{m}]$ 翁脆， $\hat{h}_{1},\cdots ,\hat{h}_{m}$ 也就是神經(jīng)網(wǎng)絡(luò)要學(xué)習(xí)的參數(shù)。

頻域架構(gòu)

在這里我們?nèi)匀皇褂?img class="math-inline" src="https://math.jianshu.com/math?formula=k" alt="k" mathimg="1">來代表網(wǎng)絡(luò)的第 $k$ 層鼻种， $k=1,2,\cdots ,K$ 反番， $f_k$ 仍然代表卷積核的數(shù)量。這種架構(gòu)的卷積的過程主要依照卷積定理，首先來描述卷積的過程罢缸，之后再描述如何進(jìn)行下采樣篙贸，因此現(xiàn)在假設(shè)第 $k$ 層和第 $k+1$ 層的節(jié)點(diǎn)數(shù)都是 $|\Omega |$ ，那么第 $k$ 層的輸入 $x_{k}$ 就是一個(gè) $|\Omega |\times f_{k-1}$ 的矩陣枫疆，輸出 $x_{k+1}$ 就是一個(gè) $|\Omega |\times f_{k}$ 的矩陣爵川。第 $k$ 層的計(jì)算過程可以表示為：

$x_{k+1,j}=h\left (V\sum_{i=1}^{f_{k-1}}F_{k,i,j}V^{T}x_{k,i}\right )\; \; \; (j=1,2,\cdots ,f_{k})$

這里的 $x_{k,i}$ 仍然相當(dāng)于第 $i$ 個(gè)feature map的信號(hào)。 $F_{k,i,j}$ 也就是第 $j$ 個(gè)卷積核中對(duì)第 $i$ 個(gè)feature map進(jìn)行卷積的部分息楔，每一個(gè) $F_{k,i,j}$ 都是一個(gè)對(duì)角矩陣寝贡，其實(shí)就是前面的 $diag[\hat{h}_{1},\cdots ,\hat{h}_{m}]$ ，這里之所以有一個(gè)連加號(hào)是因?yàn)橐獙⒍鄠€(gè)feature map的結(jié)果累加起來值依， $h$ 仍然表示非線性激活兔甘，另外這里的 $V$ 的每一列的特征向量是按照特征值的大小依次排列的（降序）。

通常只有拉普拉斯矩陣的前 $d$ 個(gè)特征向量是有意義的鳞滨，因?yàn)楹竺娴奶卣飨蛄繉?duì)應(yīng)的特征值比較小洞焙，特征向量非常的平滑，因此在實(shí)際中可以取拉普拉斯矩陣的前 $d$ 列構(gòu)成的矩陣 $V_d$ 代替 $V$ 拯啦，這個(gè)過程就相當(dāng)于頻域架構(gòu)的下采樣的過程澡匪，這里的 $d$ 就相當(dāng)于空域架構(gòu)中的 $d_k$ ，每一層可以取不同的值褒链。按照目前這種架構(gòu)所需的參數(shù)復(fù)雜度為 $f_{k-1}\cdot f_{k}\cdot d=O(|\Omega |)$ 唁情。

四、實(shí)驗(yàn)

本文中提出的兩種架構(gòu)在兩個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證效果甫匹。具體實(shí)驗(yàn)設(shè)置參看原論文甸鸟，這里不做贅述。

采樣MNIST數(shù)據(jù)集

這個(gè)數(shù)據(jù)集是從MNIST數(shù)據(jù)集的每張圖片（ $28\times 28$ ）上采樣 $400$ 個(gè)樣本點(diǎn)構(gòu)建圖兵迅。實(shí)驗(yàn)樣本如下圖：

樣本

實(shí)驗(yàn)結(jié)果如下圖所示：

結(jié)果

球體上的MNIST數(shù)據(jù)集

這個(gè)數(shù)據(jù)集將MNIST數(shù)據(jù)集中的樣本提升到3維空間中抢韭。實(shí)驗(yàn)樣本如下圖：

樣本

實(shí)驗(yàn)結(jié)果如下圖所示：

結(jié)果1

結(jié)果2

參考資料

ref:圖傅里葉變換
ref:paper reading：[第一代GCN] Spectral Networks and Deep Locally Connected Networks on Graphs

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

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市恍箭，隨后出現(xiàn)的幾起案子刻恭，更是在濱河造成了極大的恐慌，老刑警劉巖扯夭，帶你破解...
沈念sama閱讀 221,576評(píng)論 6贊 515
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件鳍贾，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡交洗，警方通過查閱死者的電腦和手機(jī)骑科，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,515評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來构拳，“玉大人咆爽，你說我怎么就攤上這事梁棠。” “怎么了伍掀？”我有些...
開封第一講書人閱讀 168,017評(píng)論 0贊 360
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵掰茶，是天一觀的道長(zhǎng)暇藏。經(jīng)常有香客問我蜜笤，道長(zhǎng)，這世上最難降的妖魔是什么盐碱？我笑而不...
開封第一講書人閱讀 59,626評(píng)論 1贊 296
?港島之戀（遺憾婚禮）
正文為了忘掉前任把兔，我火速辦了婚禮，結(jié)果婚禮上瓮顽，老公的妹妹穿的比我還像新娘县好。我一直安慰自己，他們只是感情好暖混，可當(dāng)我...
茶點(diǎn)故事閱讀 68,625評(píng)論 6贊 397
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布缕贡。她就那樣靜靜地躺著，像睡著了一般拣播。火紅的嫁衣襯著肌膚如雪晾咪。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,255評(píng)論 1贊 308
城市分裂傳說
那天贮配，我揣著相機(jī)與錄音谍倦，去河邊找鬼。笑死泪勒，一個(gè)胖子當(dāng)著我的面吹牛昼蛀，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播圆存，決...
沈念sama閱讀 40,825評(píng)論 3贊 421
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼叼旋，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了沦辙？” 一聲冷哼從身側(cè)響起送淆，我...
開封第一講書人閱讀 39,729評(píng)論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎怕轿，沒想到半個(gè)月后偷崩，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,271評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡撞羽，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,363評(píng)論 3贊 340
?白月光啟示錄
正文我和宋清朗相戀三年阐斜，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片诀紊。...
茶點(diǎn)故事閱讀 40,498評(píng)論 1贊 352
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡谒出，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情笤喳，我是刑警寧澤为居，帶...
沈念sama閱讀 36,183評(píng)論 5贊 350
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站杀狡，受9級(jí)特大地震影響蒙畴，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜呜象，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,867評(píng)論 3贊 333
男人毒藥：我在死后第九天來索命
文/蒙蒙一膳凝、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧恭陡，春花似錦蹬音、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,338評(píng)論 0贊 24
一樁弒父案著淆，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至拴疤，卻和暖如春永部，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背遥赚。一陣腳步聲響...
開封第一講書人閱讀 33,458評(píng)論 1贊 272
情欲美人皮
我被黑心中介騙來泰國(guó)打工扬舒，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人凫佛。一個(gè)月前我還...
沈念sama閱讀 48,906評(píng)論 3贊 376
代替公主和親
正文我出身青樓讲坎，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親愧薛。傳聞我的和親對(duì)象是個(gè)殘疾皇子晨炕，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,507評(píng)論 2贊 359

第一代圖卷積網(wǎng)絡(luò)：圖的頻域網(wǎng)絡(luò)與深度局部連接網(wǎng)絡(luò)

一栖茉、概述

二日熬、空域架構(gòu)

三祸憋、頻域架構(gòu)

四、實(shí)驗(yàn)

參考資料

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