Graph Convolutional Network

先介紹一下需要的數學基礎

拉普拉斯運算元

參考：拉普拉斯

先解釋下散度：在直角坐標系下，你可以看到這樣一個公式：如果向量場A可以表示成以下形式：

mathbf{A}(x,y,z) = P(x,y,z)mathbf{i} + Q(x,y,z)mathbf{j} + R(x,y,z)mathbf{k}

那麼散度表示為：

ablacdotmathbf{A} = frac{partial P}{partial x} + frac{partial Q}{partial y} + frac{partial R}{partial z}

散度運算的對像是向量,運算出來的結果會是標量

拉普拉斯運算元或是拉普拉斯算符是由歐幾裏得空間中的一個函數的梯度的散度給出的微分運算元。也就是定義為：定義為對函數f先做梯度運算( abla f )，再做散度運算( abla cdot abla f )的結果，因此如果f 是二階可微的實函數，則 f 的拉普拉斯運算元定義為：

Delta f= abla^{2} f= abla cdot abla f-(1)

f 的拉普拉斯運算元也是笛卡兒坐標系 x_i 中的所有非混合二階偏導數：

Delta f=sum_{i=1}^{n} frac{partial^{2} f}{partial x_{i}^{2}}

其實就是f對所有的變數求解非混合二階偏導，然後求和

函數的拉普拉斯運算元也是該函數的海森矩陣的跡：

Delta f=operatorname{tr}(H(f))

拉普拉斯運算元作用在向量值函數上，其結果被定義為一個向量，這個向量的各個分量分別為向量值函數各個分量的拉普拉斯，即：

abla^{2} mathbf{A}=left( abla^{2} A_{x}, abla^{2} A_{y}, abla^{2} A_{z} ight)

拉普拉斯矩陣

簡單圖的拉普拉斯矩陣

在數學領域圖論中，拉普拉斯矩陣，有時也被稱為導納矩陣，基爾霍夫矩陣或離散拉普拉斯，是矩陣 A的代表性曲線圖。拉普拉斯矩陣可用於查找圖的許多有用屬性。

給定具有n個頂點的簡單圖 G，其拉普拉斯矩陣 L_{n imes n} 定義為：

L=D-A

其中D是度(出度入度)矩陣，A是圖的鄰接矩陣。G是一個簡單的圖表，A僅包含1或0，其對角線元素均為0。 在有向圖的情況下，可以使用indegree或outdegree，具體取決於應用程序。L定義為：

L_{i, j} :=left{egin{array}{ll}{operatorname{deg}left(v_{i} ight)} & { ext { if } i=j} \ {-1} & { ext { if } i eq j ext { and } v_{i} ext { is adjacent to } v_{j}} \ {0} & { ext { otherwise }}end{array} ight.

其中 operatorname{deg}left(v_{i} ight) 是頂點 i 的度數

標記圖

度矩陣

鄰接矩陣
拉普拉斯矩陣

對稱歸一化拉普拉斯運算元

對稱歸一化拉普拉斯矩陣定義為：

L^{mathrm{sym}} :=D^{-frac{1}{2}} L D^{-frac{1}{2}}=I-D^{-frac{1}{2}} A D^{-frac{1}{2}}

L^{mathrm{sym}} 的元素定義為：

L_{i, j}^{mathrm{sym}} :=left{egin{array}{ll}{1} & { ext { if } i=j ext { and } operatorname{deg}left(v_{i} ight) eq 0} \ {-frac{1}{sqrt{operatorname{deg}left(v_{i} ight) operatorname{deg}left(v_{j} ight)}}} & { ext { if } i eq j ext { and } v_{i} ext { is adjacent to } v_{j}} \ {0} & { ext { otherwise. }}end{array} ight.

隨機遊走歸一化拉普拉斯運算元

隨機遊走歸一化拉普拉斯矩陣定義為：

L^{mathrm{rw}} :=D^{-1} L=I-D^{-1} A

可由公式定義為：

L_{i, j}^{mathrm{rw}} :=left{egin{array}{ll}{1} & { ext { if } i=j ext { and } operatorname{deg}left(v_{i} ight) eq 0} \ {-frac{1}{operatorname{deg}left(v_{i} ight)}} & { ext { if } i eq j ext { and } v_{i} ext { is adjacent to } v_{j}} \ {0} & { ext { otherwise. }}end{array} ight.

對於（無向）圖G及其具有特徵值的拉普拉斯矩陣L： lambda_{0} leq lambda_{1} leq cdots leq lambda_{n-1}

  • L是對稱的。
  • L是半正定的(即 lambda_{i} geq 0 }
  • L是一個M矩陣
  • L的每一行和列總和為零

傅裏葉變換

傅裏葉變換是一種線性積分變換，用於信號在時域（或空域）和頻域之間的變換，經傅裏葉變換生成的函數 hat{f} 稱作原函數 f 的傅裏葉變換、亦稱頻譜。在許多情況下，傅裏葉變換是可逆的，即可通過 hat{f} 得到其原函數 f

定義：

一般情況下，若「傅裏葉變換」一詞不加任何限定語，則指的是「連續傅裏葉變換」（連續函數的傅裏葉變換）。定義傅裏葉變換有許多不同的方式。本文中採用如下的定義：（連續）傅裏葉變換將可積函數 f : mathbb{R} ightarrow mathbb{C} 表示成復指數函數的積分或級數形。

hat{f}(xi)=int_{-infty}^{infty} f(x) e^{-2 pi i x xi} d x ，ξ為任意實數

自變數x表示時間（以秒為單位），變換變數ξ表示頻率（以赫茲為單位）。在適當條件下， hat{f} 可由逆變換由下式確定 f ：

f(x)=int_{-infty}^{infty} hat{f}(xi) e^{2 pi i xi x} d xi ，x為任意實數。

離散傅裏葉變換

為了在科學計算和數字信號處理等領域使用計算機進行傅裏葉變換，必須將函數xn定義在離散點而非連續域內，且須滿足有限性或週期性條件。這種情況下，使用離散傅裏葉變換，將函數xn表示為下面的求和形式：

x_{n}=sum_{k=0}^{N-1} X_{k} e^{-i frac{2 pi}{N} k n} quad n=0, dots, N-1

圖卷積神經網路

真實世界中，許多重要的數據集都是以圖或者網路的形式存在的，比如社交網路，知識圖譜，蛋白質相互作用網，世界貿易網等等。一些論文重新回顧了這個問題，嘗試將神經網路一般化並應用在任意圖結構數據中。

圖（graph）是一種數據格式，它可以用於表示社交網路、通信網路、蛋白分子網路等，圖中的節點表示網路中的個體，連邊表示個體之間的連接關係。許多機器學習任務例如社團發現、鏈路預測等都需要用到圖結構數據，因此圖卷積神經網路的出現為這些問題的解決提供了新的思路。下圖就是一個簡單的圖結構數據：

目前，大多數圖神經網路模型都有一個通用的架構。稱為圖卷積神經網（GCNs），這些模型是可卷積的，因為濾波器參數在圖中所有位置或者一個局部位置上都可以共享。

下面這部分參考：GCN

CNN可以很有效地提取空間特徵。但是有一點需要注意：CNN處理的圖像或者視頻數據中像素點（pixel）是排列成成很整齊的矩陣，與之相對應，科學研究中還有很多Non Euclidean Structure的數據，如圖3所示。社交網路、信息網路中有很多類似的結構。實際上，這樣的網路結構（Non Euclidean Structure）就是圖論中抽象意義上的拓撲圖，所以，Graph Convolutional Network中的Graph是指數學（圖論）中的用頂點和邊建立相應關係的拓撲圖。

研究GCN的原因：

  1. CNN無法處理Non Euclidean Structure的數據，學術上的表達是傳統的離散卷積，在Non Euclidean Structure的數據上無法保持平移不變性。通俗理解就是在拓撲圖中每個頂點的相鄰頂點數目都可能不同，那麼當然無法用一個同樣尺寸的卷積核來進行卷積運算。
  2. 由於CNN無法處理Non Euclidean Structure的數據，又希望在這樣的數據結構（拓撲圖）上有效地提取空間特徵來進行機器學習，所以GCN成為了研究的重點。
  3. 廣義上來講任何數據在賦範空間內都可以建立拓撲關聯，譜聚類就是應用了這樣的思想（譜聚類）。所以說拓撲連接是一種廣義的數據結構，GCN有很大的應用空間。

對於這些模型，它們的目標是要學習圖G=（V，E）上的信號或特徵的一個映射。它們的輸入包括：

  • 每一個節點i的特徵描述 x_i ，可以寫成一個N*D的特徵矩陣（N表示節點數，D表示輸入的特徵數）
  • 矩陣形式的圖結構的特徵描述，通常是以鄰接矩陣的形式（或者其他的形式）

模型會產生一個節點級別的輸出Z（一個N*F的特徵矩陣，其中F表示每一個節點的輸出特徵數）。圖級別的輸出可以通過引入一些池化操作來建模

每一個神經網路層可以寫成這樣一個非線性函數：

H^{(l+1)}=fleft(H^{(l)}, A ight)

H^{(0)}=X

H^{(L)}=Z

Z也可以作為圖級別的輸出），L是層數，這個模型主要在於 f() 怎樣選擇以及參數化。

下面詳細介紹下 f() 是怎麼設計的

圖上的卷積網路從卷積方式上可以分為兩種：1.譜（spectral）卷積，2.空間域卷積，而Semi-Supervised Classification with Graph Convolutional Networks 這篇論文就是譜（spectral）卷積，Learning Convolutional Neural Networks for Graphs 是空間域卷積，

先介紹下Semi-Supervised Classification with Graph Convolutional Networks這篇論文

GCN的符號規定

Symbols

  • mathcal{G}=(mathcal{V},mathcal{E}) 表示一個圖， mathcal{V},mathcal{E} 分別表示相應的節點集與邊集，u,vinmathcal{V} 表示圖中的節點， (u,v)inmathcal{E} 表示圖中的邊。
  • A 表示圖的鄰接矩陣（adjacency matrix）。
  • D 表示圖的度矩陣（degree matrix）。
  • L 表示圖的拉普拉斯矩陣（Laplacian matrix），mathcal{L} 表示圖的歸一化拉普拉斯矩陣。

參考：GCN

本文嘗試用 GCN 進行半監督的分類，通過引入一個 graph Laplacian regularization term 到損失函數中

mathcal{L}=mathcal{L}_{0}+lambda mathcal{L}_{mathrm{reg}}, quad ext { with } quad mathcal{L}_{mathrm{reg}}=sum_{i, j} A_{i j}left|fleft(X_{i} ight)-fleft(X_{j} ight) ight|^{2}=f(X)^{ op} Delta f(X)

其中，L0 代表損失函數，即：graph 的標註部分，f(*) 可以是類似神經網路的可微分函數，X 是節點特徵向量組成的矩陣， Delta=D-A 代表 無向圖 g 的 unnormalized graph Laplacian，及其鄰接矩陣 A，degree matrix D_{ii} = sum_{j} A_{ij} . 公式是依賴於假設：connected nodes in the graph are likely to share the same label. 但是這個假設，可能限制了模型的適應性（the modeling capacity），因為 graph edges 不需要編碼 node 的相似性，但可以包含額外的信息。

直接用神經網路模型 f(X, A) 來編碼 graph 結構，然後在有label 的節點上進行訓練，所以，避免了顯示的 在損失函數中，基於 graph 的正則化項。基於 f(*) 在 graph 上的近鄰矩陣將會允許模型從監督loss L0 來分佈梯度信息，也確保其可以學習 nodes 的表示

譜圖卷積

從本質上說，GCN是譜圖卷積的一階局部近似。那麼，什麼是譜圖卷積呢？

首先來看圖上的譜卷積。圖上的譜卷積可以定義為信號 xinmathbb{R}^{N} 與濾波器 g_{ heta}=diag( heta) （ hetainmathbb{R}^{N} ）在傅裏葉域的乘積：

g_{ heta} star x=U g_{ heta} U^{ op} x

其中，U為歸一化拉普拉斯L=I_{N}-D^{-frac{1}{2}}AD^{-frac{1}{2}}=ULambda U^{T}的特徵向量矩陣（即譜矩陣），對L進行特徵分解就可以得到U，其中，Lambda為相應的特徵值矩陣（對角矩陣），U^{T}x為x的圖傅氏變換(即離散傅裏葉變換)。在這裡，可以將g_{ heta}看作是L特徵向量的函數，也就是g_{ heta}(Lambda)。

Theta=({ heta_1},{ heta_2},cdots,{ heta_n})就跟三層神經網路中的weight一樣是任意的參數

對於圖譜卷積來說，其計算代價無疑是很大的：（1） 使用 U 進行矩陣乘法運算的計算複雜度為 mathcal{O}(N^{2}) ;（2）計算大圖的拉普拉斯矩陣 L 的特徵分解需要很大的計算量。針對這一問題，本文採用了[2]中的方法來近似 g_{ heta}(Lambda) 。該方法使用切比雪夫多項式（Chebyshev polynomial） T_{k}(x) 的 K 階截斷來獲得對 g_{ heta}(Lambda) 的近似：

g_{ heta^{prime}}(Lambda) approx sum_{k=0}^{K} heta_{k}^{prime} T_{k}( ilde{Lambda})

其中， ilde{Lambda}=frac{2}{lambda_{max}}Lambda-I_{N}為經L的最大特徵值（即譜半徑）縮放後的特徵向量矩陣。 hetain mathbb{R}^{K}表示一個切比雪夫向量。切比雪夫多項式使用遞歸的方式進行定義：T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)，其中，T_{0}(x)=1且T_{1}(x)=x。

此時，可以使用近似的g_{ heta}替代原來的g_{ heta}，此時，可以得到：

g_{ heta^{prime}} * x approx U sum_{k=0}^{K} heta^{prime} T_{k}( ilde{Lambda}) U^{T} x=sum_{k=0}^{K} heta_{k}^{prime} U T_{k}( ilde{Lambda}) U^{T} x

而T_{k}( ilde{Lambda})是Lambda的k階多項式，且有U ilde{Lambda}^{k}U^{T}=(U ilde{Lambda}U^{T})^{k}= ilde{L}^{k}，其中， ilde{L}=frac{2}{lambda_{max}}L-I_{N}。這樣，我們就得到了文中的公式：

g_{ heta^{prime}} star x approx sum_{k=0}^{K} heta_{k}^{prime} T_{k}( ilde{L}) x

通過這一近似，可以發現，譜圖卷積不再依賴於整個圖，而只是依賴於距離中心節點K步之內的節點（即K階鄰居）。在[3]中，Defferrard et al. 使用了這一概念定義了圖上的卷積神經網路

Layer-wise線性模型

近似的譜圖卷積雖然可以建立起 K 階鄰居的依賴，然而，卻仍然需要在 ilde{L} 上進行 K 階運算。在實際過程中，這一運算的代價也是非常大的。為了降低運算代價，本文進一步簡化了該運算，即限定 K=1 。此時，譜圖卷積可以近似為 ilde{L} （或 L ）的線性函數。

當然，這樣做的代價是，只能建立起一階鄰居的依賴。對於這一問題，可以通過堆積多層圖卷積網路建立 K 階鄰居的依賴，而且，這樣做的另一個優勢是，在建立 K>1 階鄰居的依賴時，不需要受到切比雪夫多項式的限制。

為了進一步簡化運算，在GCN的線性模型中，本文定義 lambda_{max}approx 2 。此時，我們可以得到圖譜卷積的一階線性近似：

g_{ heta^{prime}} star x approx heta_{0}^{prime} x+ heta_{1}^{prime}left(L-I_{N} ight) x= heta_{0}^{prime} x- heta_{1}^{prime} D^{-frac{1}{2}} A D^{-frac{1}{2}} x

可以看到，該式中僅有兩個參數 heta_{0}與 heta_{1}。若需建立k階鄰居上的依賴，可以通過設置k層這樣的濾波器來實現。

在實際的過程中，可以通過對參數進行約束來避免過擬合，並進一步簡化運算複雜度。例如，可以令 heta= heta_{0}=- heta_{1} ，從而得到

g_{ heta} star x approx hetaleft(I_{N}+D^{-frac{1}{2}} A D^{-frac{1}{2}} ight) x

需要注意的是， I_{N}+D^{-frac{1}{2}}AD^{-frac{1}{2}} 的特徵值範圍為[0,2]，這意味著，當不停地重複該操作時（網路非常深時），可能會引起梯度爆炸或梯度消失。為了減弱這一問題，本文提出了一種 renormalization trick：

I_{N}+D^{-frac{1}{2}} A D^{-frac{1}{2}} ightarrow ilde{D}^{-frac{1}{2}} ilde{A} ilde{D}^{-frac{1}{2}}

其中， ilde{A}=A+I_{N} ， ilde{D}_{ii}=Sigma_{j} ilde{A}_{ij} 。

當圖中每個節點的表示不是單獨的標量而是一個大小為 C 的向量時，可以使用其變體進行處理：

其中， Thetainmathbb{R}^{C imes F} 表示參數矩陣， Zinmathbb{R}^{N imes F} 為相應的卷積結果。此時，每個節點的節點表示被更新成了一個新的 F 維向量，該 F 維向量包含了相應的一階鄰居上的信息。

圖卷積神經網路

經過以上的推導，本文得到了圖卷積神經網路的（單層）最終形式：

H^{(l+1)}=sigmaleft( ilde{D}^{-frac{1}{2}} ilde{A} ilde{D}^{-frac{1}{2}} H^{(l)} W^{(l)} ight)

其中， 第 l 層網路的輸入為 H^{(l)}inmathbb{R}^{N imes D} （初始輸入為 H^{(0)}=X ）， N 為圖中的節點數量，每個節點使用 D 維的特徵向量進行表示。 ilde{A}=A+I_{N} 為添加了自連接的鄰接矩陣， ilde{D}為度矩陣， ilde{D}_{ii}=Sigma_{j} ilde{A}_{ij} 。 W^{(l)}in mathbb{R}^{D imes D} 為待訓練的參數。 sigma 為相應的激活函數，例如 ReLU(·)=max(0,·) 。此即GCN的最終形式。

具體來說，本文使用了一個兩層的GCN進行節點分類。模型結構圖如下圖所示：

其具體流程為：

  • 首先獲取節點的特徵表示 X 並計算鄰接矩陣 hat{A}= ilde{D}^{-frac{1}{2}} ilde{A} ilde{D}^{-frac{1}{2}} 。
  • 將其輸入到一個兩層的GCN網路中，得到每個標籤的預測結果：

Z=f(X, A)=operatorname{softmax}left(hat{A} operatorname{ReLU}left(hat{A} X W^{(0)} ight) W^{(1)} ight)

其中， W^{(0)}inmathbb{R}^{C imes H} 為第一層的權值矩陣，用於將節點的特徵表示映射為相應的隱層狀態。 W^{(1)}inmathbb{R}^{H imes F} 為第二層的權值矩陣，用於將節點的隱層表示映射為相應的輸出（ F 對應節點標籤的數量）。最後將每個節點的表示通過一個softmax函數，即可得到每個標籤的預測結果。

對於半監督分類問題，使用所有有標籤節點上的期望交叉熵作為損失函數：

mathcal{L}=-sum_{l in mathcal{Y}_{L}} sum_{f=1}^{F} Y_{l f} ln Z_{l f}

其中， mathcal{Y}_{L} 表示有標籤的節點集。

後續待更新

pytorch版本的實現：GCN_PyTorch


推薦閱讀：
相關文章