1、無向圖與拉普拉斯矩陣

1.1 圖的基本定義

圖(Graph)通常由頂點的有窮非空集合和頂點之間的邊的集合所構成，通常可表示為 mathcal{G}=(mathbf{V,E,A}). 其中， mathbf{V} 是頂點的集合， mathbf{E} 是邊的集合， mathbf{A} 為圖的鄰接矩陣.在圖中, v_iin mathbf{V} 表示一個結點, e_{ij}=(v_i,v_j)inmathbf{E} 表示一條邊. mathbf{A} 是一個 N imes N 的矩陣(N表示頂點的數目):若 e_{ij}in mathbf{E} 則 mathbf{A}_{ij}=w_{ij}>0 ,若 e_{ij} otin mathbf{E} 則 mathbf{A}_{ij}=0. 圖中頂點的度(degree)指的是與該頂點相連的邊的數量.

我們可以為圖的頂點賦予一個屬性從而得到圖的所有結點的屬性矩陣 mathbf{X}in mathbf{R}^{N imes D} ,矩陣 mathbf{X} 的每一行代表對應頂點的屬性值.

在有向圖中,每條邊都由對應的起點和終點,這意味著 mathbf{A}_{ij} emathbf{A}_{ji} .無向圖中的所有邊都是沒有方向的,這意味著對於一個無向圖 mathbf{A}_{ij}=mathbf{A}_{ji} .

2、拉普拉斯矩陣

給定一個有 n 個頂點的簡單圖(既不含平行邊也不含自環的圖) mathcal{G} ,其拉普拉斯矩陣(Laplacian matrix) mathbf{L}_{nn} 定義為

egin{equation*} mathbf{L=D-A} end{equation*}

其中 mathbf{D} 為結點的度所構成的對角矩陣, mathbf{D_{ii} = sum_j(A_{ij})} , mathbf{A} 為圖的鄰接矩陣.由於 mathcal{G} 是簡單圖,從而 mathbf{A} 中僅僅包含0和1並且對角線元素為0.我們可得到圖的拉普拉斯矩陣中的元素的值如下所示

egin{equation*} mathbf{L}_{ij}=left{ egin{aligned} & ext{deg}(v_i) & ext{如果}i=j\ &-1 & ext{如果}i eq j ext{並且}i ext{與}j ext{相鄰結}\ &0 & ext{其他} end{aligned} ight. end{equation*}

其中, ext{deg}v_i 表示的是結點i的度.此外我們常用一種標準化的拉普拉斯矩陣來表示一個無向圖,其定義為

egin{equation*} mathbf{L := D^{-frac{1}{2}}LD^{-frac{1}{2}} = I -D^{-frac{1}{2}}LD^{-frac{1}{2}}}, end{equation*}

從而,

egin{equation*} mathbf{L}_{ij}=left{ egin{aligned} &1 & ext{如果}i=j\ &-frac{1}{sqrt{ ext{deg}(v_i) ext{deg}v_j}} & ext{如果}i eq j ext{並且}i ext{與}j ext{相鄰結}\ &0 & ext{其他} end{aligned} ight. end{equation*}

這一標準化的拉普拉斯矩陣是一個實對稱半正定矩陣,從而可以分解為: mathbf{L=U}oldsymbol{Lambda} mathbf{U^T}. 其中 mathbf{U = [u_0,u_1,cdots}mathbf{,u_{n-1}]}in mathbf{R}^{N imes N} 是矩陣的特徵向量所構成的矩陣, oldsymbol{Lambda} 是對應的特徵向量構成的對角矩陣且有 oldsymbol{Lambda}_{ii} = lambda_i .此外,特徵向量可以構成一個n維的正交空間,即 mathbf{U}^Tmathbf{U=I} .

3、圖傅裏葉變換

圖信號(圖中結點的屬性值) mathbf{x} 的圖傅裏葉變換被定義為 mathcal{F}(mathbf{x}) = mathbf{U}^Tmathbf{x} ,對應的傅裏葉逆變換被定義為 mathcal{F}^{-1}(hat{mathbf{x}})=mathbf{Uhat{x}}, 其中 hat{mathbf{x}} 表示對原始的圖信號進行傅裏葉變換的結果.從這一定義上我們實際可以看出圖傅裏葉變換實際上是將原始的圖信號變換到圖的標準化呢拉普拉斯矩陣的特徵向量所構成的正交空間中.這樣原始的圖信號其實可以通過正交空間中的基向量進行線性表示,即

egin{align*} mathbf{U}mathcal{F}(mathbf{x}) = mathbf{UU}^Tmathbf{x}=mathbf{x} end{align*}

從而我們可以得到 mathbf{x} = sum_imathbf{hat{x}_i}mathbf{u}_i .我們定義輸入信號 mathbf{x} 與濾波器 mathbf{gin R}^N 的圖卷積為

egin{align*} mathbf{x*g} &= mathcal{F}^{-1}(mathcal{F}(mathbf{x})odotmathcal{F}(mathbf{g}))\ &=mathbf{U}(mathbf{U}^Tmathbf{x}odotmathbf{U}^Tmathbf{g}) end{align*}

其中 odot 代表對應元素之間的乘積(Hadamard product).如果我們在圖卷積後的頻域空間中定義一個矩陣形式的濾波器為 mathbf{g}_ heta = ext{diag}(mathbf{U}^Tmathbf{g}) ,這時我們可以得到更為簡單的圖卷積的定義

egin{equation*} mathbf{x}*mathbf{g}_ heta = mathbf{Ug}_ hetamathbf{U}^Tmathbf{x} end{equation*}

基於頻譜的圖卷積網路均遵循這一簡單的定義方法.直覺上來說,圖卷積操作可以看成將原始的處於空域的圖信號變換到頻域上之後,對頻域屬性進行濾波,然後再恢復到原來的圖信號所在的空域中,從而完成了對圖信號的降噪與特徵提取的功能.

4、幾種基於頻譜的圖卷積網路

4.1 頻譜卷積神經網路

最開始的譜卷積網路(Spectral CNN)假設卷積濾波器是由一組可學習的參數構成的,並且圖信號是一個多維向量.從而定義為如下的圖卷積層

egin{equation*} mathbf{X}_{:,j}^{k+1} = sigma(sum_{i=1}^{f_{k-1}}mathbf{U}oldsymbol{Theta}_{i,j}^{k}mathbf{U}^Tmathbf{X}_{:,i}^{k})quad(j=1,2,,cdots,f_k) end{equation*}

其中 mathbf{X}^kinmathbf{R}^{N imes f_{k-1}} 是輸入的圖信號所構成的矩陣,N表示圖中結點的數目, f_{k-1} 表示輸入信號的維度(channel), f_k 表示輸出信號的維度, oldsymbol{Theta}_{i,j}^{k} 是一個由待學習的參數所構成的對角矩陣, sigma 表示非線性變換.

4.2 契比雪夫頻譜卷積網路(ChebNet)

契比雪夫頻譜卷積網路是通過圖的拉普拉斯矩陣的特徵值所構成的對角矩陣的契比雪夫多項式所組成的,其卷積濾波器的定義為

egin{equation*} mathbf{g}_ heta = sum_{k=0}^{K-1} heta_kT_k(oldsymbol{hat{Lambda}}) end{equation*}

其中, oldsymbol{hat{Lambda}}=2oldsymbol{Lambda}/lambda_{ ext{max}}-mathbf{I}_N .契比雪夫多項式可遞歸的定義為

egin{equation*} T_k(mathbf{x}) = 2mathbf{x}T_{k-1}(mathbf{x}) - T_{k-1}(mathbf{x}),quad T_0(mathbf{x}) = 1,T_1(mathbf{x}) = mathbf{x}. end{equation*}

從而,在上述卷積濾波器的定義下,圖信號 mathbf{x} 的圖卷積可定義為

egin{align*} mathbf{x}*mathbf{g}_ heta &= mathbf{U}(sum_{k=0}^{K-1} heta_kT_k(oldsymbol{hat{Lambda}}))mathbf{U}^Tmathbf{x} \ & = sum_{k=0}^{K-1} heta_kT_k(oldsymbol{hat{L}})mathbf{x} end{align*}

其中, oldsymbol{hat{L}} = 2mathbf{L}/lambda_{max} - mathbf{I}_N. 從上面的表達式我們可以看出,ChebNet不需要計算拉普拉斯特徵矩陣的傅裏葉基矩陣,這樣可以降低計算的複雜度.並且由於卷積操作只針對單個結點,因而其是一個局部卷積操作.

4.3 ChebNet的一階近似

我們只保留上訴ChebNet的一階項並且令 lambda_{max}=2 ,從而得到下面的卷積公式

egin{equation*} mathbf{x}*mathbf{g}_ heta = heta_0mathbf{x} - heta_1mathbf{D}^{-frac{1}{2}}mathbf{AD}^{-frac{1}{2}}mathbf{x} end{equation*}

為了減少參數的數量和過擬合,可進一步假設 heta = heta_0=- heta_1 ,從而產生了下面形式的圖卷積

egin{equation*} mathbf{x}*mathbf{g}_ heta = heta(mathbf{I}_n +mathbf{D}^{-frac{1}{2}}mathbf{AD}^{-frac{1}{2}})mathbf{x} end{equation*}

將上述公式寫為輸入數據的批量的形式,可以得到如下的公式

egin{equation*} mathbf{X}^{k+1} = mathbf{hat{A}X}^koldsymbol{Theta} end{equation*}\

其中, mathbf{hat{A}} = mathbf{I}_n +mathbf{D}^{-frac{1}{2}}mathbf{AD}^{-frac{1}{2}} .

這裡定義的圖卷積是空間中的局部卷積操作,它融合了基於空域的方法和基於頻域的方法.輸出矩陣的每一行代表將輸入矩陣的當前行所對應的圖信號和其近鄰的信號通過權重矩陣 mathbf{hat{A}} 進行融合後的隱藏屬性.

5、小結

Spectral CNN 依賴於對拉普拉斯矩陣的特徵分解,這使得其會有如下三個限制:(1)對圖結構的小小擾動將會導致不同的特徵基;(2)特徵分解需要較為龐大的計算代價;(3)學習到的濾波器是針對特定問題的,不能夠將其進行推廣到更豐富的圖結構上.ChebNet及其一階近似是局部卷積操作,從而可以在圖的不同位置共享相同的濾波器參數.

基於頻譜方法的一個關鍵缺陷是其需要將整個圖的信息載入內存中,這使得其在大規模的圖結構(如大規模的社交網路分析)上不能有效的進行應用.

參考文獻：

[1] Wu Z, Pan S, Chen F, et al. A comprehensive survey on graph neural networks[J]. arXiv preprint arXiv:1901.00596, 2019.

[2] Bruna J, Zaremba W, Szlam A, et al. Spectral networks and locally connected networks on graphs[J]. arXiv preprint arXiv:1312.6203, 2013.

[3] Defferrard M, Bresson X, Vandergheynst P. Convolutional neural networks on graphs with fast localized spectral filtering[C]//Advances in neural information processing systems. 2016: 3844-3852.

[4] Kipf T N, Welling M. Semi-supervised classification with graph convolutional networks[J]. arXiv preprint arXiv:1609.02907, 2016.

推薦閱讀：

相關文章