一文讀懂圖神經網絡


一文讀懂圖神經網絡

2021-01-11 程序媛驛站

分類:深度學習

文章來源:哈工大SCIR

作者:哈工大SCIR博士生 鄭博

本文轉自公衆號哈工大SCIR程序媛驛站獲授權轉載,如需轉載請聯繫原公衆號。

小聲:今天老闆說深度學習必須學習python,於是:

一、介紹
什麼是圖神經網絡

圖神經網絡(Graph Neural Networks, GNNs)是基於圖結構的深度學習方法,近期被廣泛應用到各類圖像、自然語言處理等任務上。圖神經網絡作爲神經網絡擴展,可以處理以圖結構表示的數據格式。在圖中,每個節點都由本身的特性以及其相鄰的節點和關系所定義,網絡通過遞歸地聚合和轉換相鄰節點的表示向量來計算節點的表示向量。

圖神經網絡(GraphNeural Networks, GNNs),主要針對非歐幾里得空間結構(圖結構)的數據進行處理。具有以下特點:

在論文《Relational inductive biases, deep learning, and graph networks》中,作者定義了通用圖網絡框架graph networks (GN) framework,概括和擴展了各種圖神經網絡,並且支持使用簡單的模塊來構建複雜的結構。GN framework的主要計算單元是GN塊,一個圖到圖的模塊,它的輸入是一個圖,在圖結構上進行計算,然後得到同樣是圖結構的輸出。

在GN framework下,一個圖可以被定義爲一個三元組,

每一個GN block包含三個更新函數,以及三個聚合函數:

上式中

其中應用於圖中每條邊的更新,應用於圖中每個節點的更新,則用來更新圖的全局表示;函數將輸入的表示集合整合爲一個表示,該函數設計爲可以接收任意大小的集合輸入,通常可以爲加和、平均值或者最大值等不限輸入個數的操作。

當一個GN block得到一個圖的輸入時,計算通常從邊到節點,再到全局進行。下圖給出了一個GN block的更新過程。

圖1 一個GN block的更新過程

一個GN block的計算可以被描述爲如下幾步:

1. 更新每一條邊,輸入參數爲邊表示,接收和發送節點的表示和以及全局表示,輸出爲更新過的邊表示;

2.  用來有同一個聚合接收節點的邊的信息,對節點i得到所有入邊及鄰近節點信息整合,用於下一步節點的更新;

3.  更新每一個節點,輸入爲上文的,節點,全局表示,輸出爲更新過的節點;

4.  聚合圖中所有邊的信息得到邊信息整合;

5.  通過聚合圖中所有節點信息得到節點的信息整合;

6. 更新全局的表示,輸入爲邊信息整合,節點信息整合,以及節點表示,輸出爲更新過的全局表示。

我們可以通過上述的更新步驟來套用目前的圖神經網絡算法,當然這裡的步驟的順序並不是嚴格固定的,比如可以先更新全局信息,再更新節點信息以及邊的信息。

爲什麼要使用圖神經網絡

圖神經網絡有靈活的結構和更新方式,可以很好的表達一些數據本身的結構特性,除了一些自帶圖結構的數據集(如Cora,Citeseer等)以外,圖神經網絡目前也被應用在更多的任務上,比如文本摘要,文本分類和序列標註任務等,目前圖神經網絡以及其變種在很多任務上都取得了目前最好的結果。

比較常見的圖神經網絡算法主要有Graph Convolutional Network(GCN)和圖註解網絡(蓋特)等網絡及其變種,在本文第三部分會給出基於圖神經網絡框架DGL的GCN以及GAT的代碼及註解。

二、圖神經網絡庫

相比於傳統的基於鄰接矩陣的圖神經網絡實現方法,目前完成度較好的圖神經網絡框架主要是基於PyTorch和MXNet的DGL (Deep Graph Library)和PyG (PyTorch Geometric)。筆者主要使用了DGL作爲開發的框架,原因是各種網絡模型的tutorial比較詳盡,同時TreeLSTM這種經典模型也可以通過給定節點訪問的順序通過框架很輕鬆的實現,相比於不使用圖網絡框架的代碼具有更強的可讀性。

但是,實際上圖神經網絡框架只適用於圖結構中的邊和點是同一量級的情況,因爲圖神經網絡框架的信息是通過圖中的邊來傳遞的,會將節點的表示複製多次。在這種情況下,反而不如使用鄰接矩陣直接做矩陣乘法,因爲使用鄰接矩陣做矩陣乘法不會將節點信息複製多次,會對顯存有極大的節省。

三、常見算法以及代碼示例詳解

GCN

GCN的計算公式如下(基於鄰接矩陣的公式定義):

上式中表示網絡的第l層,代表非線性激活函數,爲該層的權重矩陣,和分別代表度矩陣以及鄰接矩陣,~符號表示對每一個節點加上一個自環,即,爲單位矩陣;由於鄰接矩陣是沒有進行正則化的,所以論文中通過使得結果中每一行的和都爲1。

圖2 在每一層圖網絡中,每個節點通過對鄰近節點的信息聚合得到這層該節點的輸出

相比於前文GCN基於鄰接矩陣的公式定義,GCN的公式可以被更簡潔的定義爲以下兩步:

1)對於節點u,首先將節點鄰居表示聚合到一起,生成中間表示,

2)將得到的中間表示通過一層非線性神經網絡層。

下面爲基於DGL的GCN代碼示例

在代碼實現中,第一步通過DGL自帶的message passing函數實現,第二步通過DGL的apply_nodes方法,將基於PyTorch中nn.Module的用戶自定義函數加入實現:

1進口喜歡
2導入dgl.function為fn
3作為手電筒
4將torch.nn導入為nn
5導入torch.nn。功能為F
6從dgl導入DGLGraph
7
8gcn_msg = fn.copy_src(src =“ https://ppfocus.com/0/h”,out =“ m”)
9gcn_reduce = fn.sum(msg =’m’,out =“ https://ppfocus.com/0/h”)

接下來爲apply_nodes定義更新節點的自定義函數,這裡是一個線性變換加上一個非線性激活函數的網絡層:

1類NodeApplyModule(nn.Module):
2 def __init __(自我,in_feats,out_feats,激活):
3超級(NodeApplyModule,self).__ init __()
4 self.linear = nn.Linear(in_feats,out_feats)
5 self.activation =激活
6
7 def轉發(自己,節點):
8小時= self.linear(node.data[“https://ppfocus.com/0/h”])
9小時= self.activation(h)
10 return {“ https://ppfocus.com/0/h”:h}

下面定義GCN模塊,一層GCN首先通過update_all方法將節點信息通過邊傳遞,然後通過apply_nodes得到新的節點表示:

1類GCN(nn.Module):
2 def __init __(自我,in_feats,out_feats,激活):
3超級(GCN,自我)。__init __()
4 self.apply_mod = NodeApplyModule(in_feats,out_feats,激活)
5
6 def前進(自我,自我,特徵):
7克ndata[“https://ppfocus.com/0/h”] =功能
8 g.update_all(gcn_msg,gcn_reduce)
9 g.apply_nodes(func = self.apply_mod)
10返回g.ndata.pop(“ https://ppfocus.com/0/h”)

整個網絡模塊的定義和Pytorch中的NN模型定義本質上相同,如下我們定義兩個GCN網絡層:

1類網絡(nn.Module):
2 def __init __(self,in_dim,hidden_​​dim,out_dim):
3超級(淨,自我).__ init __()
4 self.gcn1 = GCN(in_dim,hidden_​​dim,F.relu)
5 self.gcn2 = GCN(hidden_​​dim,out_dim,F.relu)
6
7 def forward(自我,g,特徵):
8 x = self.gcn1(g,功能)
9 x = self.gcn2(g,x)
10返回x
11net = Net()
12印刷(淨)

蓋特

GAT和GCN的主要區別就在於鄰近節點信息的聚合方式,GAT通過引入attention機制來替代GCN中的靜態歸一化卷積運算,下面給出使用 l 層網絡輸出來計算第 l+1 層網絡輸出的公式:

在上式中,公式(1)爲上一層節點表示通過可學習的權重矩陣做線性變換;公式(2)計算兩個鄰近節點的爲未進行標準化的attention分數,這裡首先將兩個節點的表示相連,然後和一個可學習的權重向量做點積,最後通過函數。這種形式通常叫做additive attention,相比Transformer中的則是dot-product attention;公式(3)對每個與該節點有入邊的節點的attention分數使用softmax函數作歸一化操作;公式(4)與GCN類似,聚合鄰近節點的表示,使用公式(3)得到的分數作爲權值。具體的計算方式如下圖所示:

圖3 Graph Attention Networks計算attention分數以及更新節點表示

下面的基於DGL的代碼逐一分解了上面的四個公式,公式(1)中的線性變換直接使用Pytorch中的torch.nn.Linear模塊

1個進口火炬
2導入torch.nn為nn
3 import torch.nn。功能為F
4
5類GATLayer(nn.Module):
6 def __init __(self,g,in_dim,out_dim):
7超級(GATLayer,self).__ init __()
8個自我。g = g
9#方程式(1)
10 self.fc = nn.Linear(in_dim,out_dim,bias = False)
11#方程(2)
12 self.attn_fc = nn.Linear(2 * out_dim,1,bias = False)
13
14
15 def edge_attention(自身,邊緣):
公式(2)的16#邊UDF
17 z2 = torch.cat([edges.src[‘z’],edges.dst[‘z’]],dim = 1)
18 a = self.attn_fc(z2)
19 return {‘e’:F.leaky_relu(a)}
20
21
22 def message_func(自身,邊):
23#等式(3)和(4)的消息UDF
24 return {‘z’:edge.src[‘z’],’e’:edges.data[‘e’]}
25
26
27 def reduce_func(自己,節點):
28#減少等式(3)和(4)的UDF
29#方程式(3)
30 alpha = F.softmax(nodes.mailbox[‘e’],dim = 1)
31#方程式(4)
32小時= torch.sum(alpha * nodes.mailbox[‘z’],dim = 1)
33 return {“ https://ppfocus.com/0/h”:h}
34
35
36 def forward(自我,h):
37#方程式(1)
38 z = self.fc(h)
39自我ndata[‘z’] = z
40#方程式(2)
41 self.g.apply_edges(self.edge_attention)
42#公式(3)和(4)
43 self.g.update_all(self.message_func,self.reduce_func)
44 return self.g.ndata.pop(“ https://ppfocus.com/0/h”)

公式(2)中的通過兩個相鄰節點i和j的表示計算,這裡通過DGL的apply_edgesAPI來實現,參數是下面的自定義函數edge_attention:

1def edge_attention(自身,邊緣):
等式(2)的2#邊UDF
3 z2 = torch.cat([edges.src[‘z’],edges.dst[‘z’]],dim = 1)
4 a = self.attn_fc(z2)
5返回{‘e’:F.leaky_relu(a)}

這裡和可學習權重向量的點積通過上面定義的線性變換函數attn_fc得到,這裡apply_edge會將所有的邊的數據放到一個tensor里,所以cat,attn_fc可以並行計算,這也是上文提到的如果邊的數量比點的數量多一個量級,最好還是使用鄰接矩陣的方式實現圖網絡的原因,因爲會將點的信息複製多次。

對於公式(3)和公式(4),使用update_allAPI來實現所有節點的信息傳遞,message function會發送兩部分信息:經過變換的表示和每條邊上尚未經過歸一化的attention分數,然後通過下面的reduce function,首先通過softmax對attention的分數作歸一化操作(公式(3)),然後將節點的鄰近節點的表示按照歸一化之後的attention權重聚合起來得到新的表示(公式(4)):

1def reduce_func(自己,節點):
2#減少等式(3)和(4)的UDF
3#等式(3)
4 alpha = F.softmax(nodes.mailbox[‘e’],dim = 1)
5#等式(4)
6小時= Torch.sum(alpha * nodes.mailbox[‘z’],dim = 1)
7 return {“ https://ppfocus.com/0/h”:h}

GAT同樣使用了類似Transformer的Multi-head Attention,用來加強模型表達能力並且穩定學習過程。每一個attention head有自己獨立的參數,可以通過兩種方式合併它們的輸出:

或者

上式中代表attention heads的數量,原作者建議對於網絡中間層使用concatenation,最後一層使用average得到attention的輸出,與上面的單個head的GATLayer相結合可以得到下面的代碼:

1類MultiHeadGATLayer(nn.Module):
2 def __init __(self,g,in_dim,out_dim,num_heads,merge =“ cat”):
3超級(MultiHeadGATLayer,self).__ init __()
4個self.heads = nn.ModuleList()
我在範圍(num_heads)中為5:
6個self.heads.append(GATLayer(g,in_dim,out_dim))
7 self.merge =合併
8
9
10 def前進(自我,h):
11出局= [attn_head(h) for attn_head in self.heads]
12如果self.merge ==’cat’:
13#結合輸出要素尺寸(dim = 1)
14返回torch.cat(head_outs,dim = 1)
其他15個:
16#使用平均值合併
17返回torch.mean(torch.stack(head_outs))

最後定義一個兩層的GAT模型

1類GAT(nn.Module):
2 def __init __(self,g,in_dim,hidden_​​dim,out_dim,num_heads):
3超級(GAT,自我).__初始__()
4 self.layer1 = MultiHeadGATLayer(g,in_dim,hidden_​​dim,num_heads)
5#請注意,輸入維為hidden_​​dim * num_heads,因為
6#多頭輸出串聯在一起。 而且,只有
7#一個注意力集中在輸出層。
8 self.layer2 = MultiHeadGATLayer(g,hidden_​​dim * num_heads,out_dim,1)
9
10
11 def forward(自我,h):
12小時= self.layer1(h)
13小時= F.elu(小時)
14小時= self.layer2(h)
15返回h

上面GAT和GCN的詳細代碼可以在DGL的Github(https://github.com/dmlc/dgl)上找到。

四、總結

圖神經網絡在近期的研究中被廣泛應用,作者結合參考資料和自身對圖神經網絡的理解,總結了一個快速上手的簡要教程。除了在一些有著天然圖結構的任務,圖神經網絡也可以應用在自然語言處理任務中,可以在模型中更好地表示信息。本文還給出了基於圖神經網絡框架DGL的GCN和GAT的代碼及註解,但是根據實際使用經驗,圖神經網絡框架在處理邊數量比節點數量多一個量級的情況下,會比使用鄰接矩陣的寫法占用更多的內存,還是需要根據具體情況來選擇使用。

五、參考資料

[1] https://docs.dgl.ai/

[2] TN Kipf和M. Welling。 圖卷積網絡的半監督分類.ICLR,2016年

[3] Battaglia,PW,Hamrick,JB,Bapst,V.,SanchezGonzalez,A.,Zambaldi,V.,Malinowski,M.,Tacchetti,A.,Raposo,D.,Santoro,A.,Faulkner,R.,等。 關係歸納偏差,深度學習和圖網絡。 arXiv預印本arXiv:1806.01261,2018。

[4] 圖神經網絡:方法和應用綜述。周錦,崔光,張中,楊,劉,孫。 arXiv預印本arXiv:1812.08434,2018。

作者:哈工大SCIR

編輯:西柚媛


本文來自程序媛驛站,未經授權不得轉載.

如有需要請公衆號後台聯繫

(歡迎轉發到朋友圈~)

請留下你指尖的溫度

讓太陽擁抱你

記得這是一個有溫度的公衆號