本文參照以下兩篇blog，這兩篇應該是目前介紹GNN和GCN最好的blog了。

https://distill.pub/2021/gnn-intro/

https://distill.pub/2021/understanding-gnns/

講圖神經(jīng)網(wǎng)絡(GNN)之前，先介紹一下什么是graph，為什么需要graph，以及graph有什么問題，然后介紹一下如何用GNN處理graph問題，最后從GNN推廣到GCN。

Graph

圖由Vertex(V)、Edge(E)和Global(U)三部分構成。V可以表示為node identity或者number of neighbors，E可以表示為edge identity或者edge weight，U可以表示為number of nodes或者longest path。

為了進一步描述每一個node、edge和entire graph，可以把信息存儲在graph的每個部分中。其實就是把信息以embedding的方式存儲。

還可以通過edge的方向性(有向的、無向的)來構建特殊的圖。

Graphs and where to find them

graph data在生活中無處不在，比如最常見的image和text都可以認為是graph data的一種特例，還有其他一些場景也可以用graph data表達。

Images as graphs

圖片的位置可以表示成(列數(shù)-行數(shù))的形式，將圖片構建成adjacency matrix，藍色塊表示pixel和pixel之間相臨，無方向性，畫成graph就是右邊圖片的形式。

Text as graphs

文本也可以構建成adjacency matrix，跟圖片不一樣的是，文本是一個有向圖，每個詞只跟前一個詞相連接，并且有方向性。

其他還有比如分子、社交網(wǎng)絡、學術引用網(wǎng)絡等等都可以構建成graph。

What types of problems have graph structured data?

graph可以處理graph-level、node-level和edge-level三種層面的問題。

Graph-level task

輸入graph，輸出整個graph的類別。在圖像中，和圖像分類任務類似；在文本中，和句子情感分析類似。

Node-level task

輸入node不帶類別的graph，輸出每個node的類別。在圖像中，和語義分割類似；在文本中，和詞性分類類似。

Edge-level task

edge-level任務用來預測node之間的相互關系。如下圖所示，先將不同部分分割出來，然后判斷不同部分的相互關系。構建成graph就是對edge進行類別預測。

The challenges of using graphs in machine learning

如何用神經(jīng)網(wǎng)絡處理graph任務呢？

第一步是考慮如何表示和神經(jīng)網(wǎng)絡相兼容的圖。graph最多有4種想要預測的信息：node、edge、global-context和connectivity。前3個相對容易，比如可以用一個??表示存儲了第i個node的特征矩陣N。然而connectivity的表示要復雜的多，最直接的方式是構建鄰接矩陣，但是空間效率很低，可能會產(chǎn)生非常稀疏的鄰接矩陣。

還有一個問題是，許多鄰接矩陣可以編碼相同的連通性，但是不能保證這些不同的矩陣在神經(jīng)網(wǎng)絡中會產(chǎn)生相同的結果(也就是說，它們不是置換不變的)。

一種優(yōu)雅而高效表示稀疏矩陣的方法是用鄰接表。edge ??表示節(jié)點??和????之間的連通性，在鄰接表的第k項中表示為一個元組(i,j)。

以一個graph的鄰接表為例，如下圖所示:

Graph Neural Networks

通過上面的描述，graph可以通過置換不變的鄰接表表示，那么可以設計一個graph neural networks(GNN)來解決graph的預測任務。

The simplest GNN

從最簡單的GNN開始，更新所有graph的屬性(nodes(V)，edges(E)，global(U))作為新的embedding，但是不使用graph的connectivity。

GNN對graph的每個組件分開使用MLP，稱為GNN layer。對于每個node vetor，使用MLP后返回一個learned node-vector，同理edge會返回一個learned edge embedding，global會返回一個global embedding。

和CNN類似，GNN layer可以堆疊起來組成GNN。由于GNN layer不更新輸入graph的connectivity，所有輸出graph的鄰接表跟輸入圖相同。但是通過GNN layer，node、edge和global-context的embedding已經(jīng)更新。

GNN Predictions by Pooling Information

如果想用GNN做二分類任務，那么可以用一個linear classifier對graph進行分類。

然而，有時候信息只儲存在edge中，那么就需要從edge收集信息轉(zhuǎn)移到node用于預測，這個過程稱之為pooling。

Pooling過程有兩個步驟：

1.對于要pooling的每一項(上圖一行中的一列)，收集它們的embedding并且concat到一個矩陣中（上圖中的一行）。

2.收集的embedding通過求和操作進行聚合。

因此，如果只有edge-level的特征，可以通過pooling傳遞信息來預測node(上圖虛線表示pooling傳遞信息給node，然后進行二分類)。

同理，如果只有node-level的特征，可以通過pooling傳遞信息來預測edge。類似CV中的global average pooling。

同理，可以通過node-level的特征預測global。

和CNN類似，通過GNN blocks可以構建出一個end-to-end的GNN。

需要注意的是，在這個最簡單的GNN中，沒有在GNN layer使用graph的connectivity。每個node、每個edge以及global-context都是獨立處理的，只在聚合信息進行預測的時候使用了connectivity。

Passing messages between parts of the graph

為了使learned embedding感知到graph的connectivity，可以在GNN layer使用pooling構建出更加復雜的GNN(和convlution類似)。可以使用message passing實現(xiàn)，相鄰node或者edge可以交換信息，并且影響彼此的embedding更新。

Message passing過程有三個步驟：

1.對于graph的每個node，收集所有相鄰node的embedding。

2.通過相加操作聚合所有message。

3.所有聚合的message都通過一個update function傳遞(通常使用一個可學習的神經(jīng)網(wǎng)絡)。

這些步驟是利用graph的connectivity的關鍵。在GNN layer中構建更精細的message passing變體，可以獲得表達和能力更強的GNN模型。

通過堆疊的message passing GNN layer，一個node可以引入整個graph的信息：在三層GNN layer之后，一個node可以獲得3步遠的node信息。

對最簡單的GNN范式進行更新，增加一個message passing操作:

Learning edge representations

通過meassage passing，可以在GNN layer的node和edge之間共享信息。可以像之前使用相鄰node信息一樣，先將edge信息pooling，然后用update function轉(zhuǎn)化并且存儲，從而聚合來自相鄰edge的信息。

然而，存儲在graph中的node和edge信息不一定具有相同的大小或形狀，因此不能立刻知道如何將它們組合起來。一種方法是學習從node空間到edge空間的線性映射，或者，可以在update function之前將它們concat在一起。

在構造GNN時，需要設計更新哪些graph屬性以及更新順序。比如可以使用weave的方式進行更新，node to node(linear)，edge to edge(linear)，node to edge(edge layer)，edge to node(node layer)。

Adding global representations

上面描述的GNN模型還有一個缺陷：在graph中，距離很遠的node無法有效的傳遞信息，對于一個node，如果有k個layer，那么信息傳遞的距離最多是k步，這對于依賴相距很遠的node信息的預測任務來說，是比較嚴重的問題。一種解決辦法是讓所有node可以相互傳遞信息，但是對于大的graph來說，計算量會非常昂貴。另一種解決辦法是使用graph(U)的全局表示，稱為master node或者context vector。這個全局的context vector可以連接到網(wǎng)絡的所有node和edge，可以作為它們之間信息傳遞的橋梁，構建出一個graph的整體表示。

從這個角度看，所有graph屬性都可以通過將感興趣的屬性和其他屬性關聯(lián)，然后在pooling過程中利用起來。比如對于一個node，可以同時考慮相鄰的node、edge和global信息，然后通過concat將它們關聯(lián)起來，最后通過線性映射將它們映射到相同特征空間中。

The Challenges of Computation on Graphs

graph在計算中有三個挑戰(zhàn)：lack of consistent structure、node-order equivariance和scalability。

Lack of Consistent Structure

graph是極其靈活的數(shù)學模型，同時這意味著它們?nèi)狈鐚嵗囊恢陆Y構。比如不同分子之間有不同的結構。用一種可以計算的格式來表示graph并不是一件簡單的事情，graph的最終表示通常由實際問題決定。

Node-Order Equivariance

graph的node之間通常沒有內(nèi)在的順序，相比之下，在圖像中，每個像素都是由其在圖像中的絕對位置唯一決定的。因此，我們希望我們的算法是節(jié)點順序不變的:它們不應該依賴于graph中node的順序。如果我們以某種方式對node進行排列，則由算法計算得到的node表示也應該以同樣的方式進行排列。

Scalability

graph可以非常大，像Facebook和Twitter這樣的社交網(wǎng)絡，它們擁有超過10億的用戶，對這么大的數(shù)據(jù)進行操作并不容易。幸運的是，大多數(shù)自然出現(xiàn)的graph都是“稀疏的”:它們的邊數(shù)往往與頂點數(shù)成線性關系。graph的稀疏性導致可以使用特殊的方法有效計算graph中node的表示。另外，和graph的數(shù)據(jù)量相比，這些方法的參數(shù)要少得多。

Problem Setting and Notation

許多問題都可以用graph來表示:

Node Classification:?對單個節(jié)點進行分類。

Graph Classification:?對整個圖進行分類。

Node Clustering:?根據(jù)連接性將相似的節(jié)點分組。

Link Prediction:?預測缺失的鏈接。

Influence Maximization:?識別有影響的節(jié)點。

Extending Convolutions to Graphs

卷積神經(jīng)網(wǎng)絡在圖像中提取特征方面是非常強大的。而圖像本身可以看作是一種非常規(guī)則的網(wǎng)格狀結構的圖，其中單個像素為節(jié)點，每個像素處的RGB通道值為節(jié)點特征。

因此，將卷積推廣到任意的graph是一個很自然的想法。然而，普通卷積不是節(jié)點順序不變的，因為它們依賴于像素的絕對位置。graph可以通過執(zhí)行某種填充和排序，保證每個節(jié)點的鄰域結構一致性，但是還有更加普遍和強大的方法來處理這個問題。

下面首先介紹一下在節(jié)點鄰域上構造多項式濾波器的方法，這和CNN在相鄰像素上濾波類似。然后介紹更多最新的方法如何用更強大的機制擴展這個想法。

Polynomial Filters on Graphs

The Graph Laplacian

給定一個graph G，用A來表示數(shù)值為0或者1的鄰接矩陣，用D表示對角度矩陣(矩陣對角線數(shù)值表示與行node相鄰node的數(shù)量)，那么??。graph Laplacian矩陣L可以表示為：L=D - A。右圖的對角線就是行node的度數(shù)，負數(shù)是減去的鄰接矩陣(藍色數(shù)字和graph中的C對應)。

Polynomials of the Laplacian

Laplacian的多項式可以表示為：

這些多項式可以認為和CNN中“filters”等價，而系數(shù)w是“filters”的權重。

為了方便討論，下面考慮節(jié)點只有一維特性的情況(每個節(jié)點是一個數(shù)值)。使用前面選擇的節(jié)點順序，我們可以將所有節(jié)點特征堆在一起得到一個x向量。

通過構造的特征向量x，可以定義它和多項式濾波器??的卷積公式為：

關于Laplacian矩陣如何作用在x上的解釋，參照https://distill.pub/2021/understanding-gnns/。

ChebNet

ChebNet對多項式濾波器公式進行了改進:

其中??是度數(shù)為i的第一種切比雪夫多項式，??是使用L最大特征值定義的歸一化Laplacian矩陣。關于ChebNet細節(jié)參照https://distill.pub/2021/understanding-gnns/。

Embedding Computation

下面介紹一下如何堆疊帶非線性的ChebNet(或者任何多項式過濾器) layer構建成一個GNN，就像標準的CNN一樣。假設有K個不同的多項式過濾器層，??的可學習參數(shù)表示為??，那么計算過程可以表示成：

GNN和CNN計算方式類似，將輸入作為初始features，然后計算多項式過濾器，然后和輸入特征進行矩陣相乘，最后用非線性函數(shù)進行非線性變換，循環(huán)迭代K次。

需要注意的是，GNN在不同的節(jié)點上過濾器權重參數(shù)共享，和CNN類似，CNN的卷積在不同位置也是參數(shù)共享的。

Modern Graph Neural Networks

ChebNet是graph中學習局部過濾器的一個突破，它激發(fā)了許多人從不同的角度思考圖卷積。

多項式過濾器對x卷積可以展開為：

這其實是一個1步局部卷積(也就是只跟直接相連的node卷積)，可以看成由兩個步驟產(chǎn)生：

1.聚合直接相鄰的特征??。

2.結合node自身的特征??。

通過確保聚合是node-order equivariant，來保證整個卷積是node-order equivariant。

這些卷積可以被認為是相鄰節(jié)點之間的“message passing”:在每一步之后，每個節(jié)點從它的相鄰節(jié)點接收信息。

通過迭代重復K次1步局部卷積，感受野為K步遠的所有node。

Embedding Computation

Message-passing形成了很多GNN模型的backbone。下面介紹一些流行的GNN模型:

• Graph Convolutional Networks (GCN)

• Graph Attention Networks (GAT)

• Graph Sample and Aggregate (GraphSAGE)

• Graph Isomorphism Network (GIN)

GCN

GAT

GraphSAGE

GIN

比較一下GCN、GAT、GraphSAGE和GIN的形式，主要差別就在于如何聚合信息和如何傳遞信息。

Conclusion

本文只是簡單介紹了一下GNN和GCN的一些變體，但圖神經(jīng)網(wǎng)絡的領域是極其廣闊的。下面提一下一些可能感興趣的點：

GNNs in Practice：如何提高GNN的效率、GNN的正則化技術

Different Kinds of Graphs：Directed graphs、Temporal graphs、Heterogeneous graphs

Pooling：SortPool、DiffPool、SAGPool

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯《統(tǒng)計學習方法》的代碼復現(xiàn)專輯 AI基礎下載黃海廣老師《機器學習課程》視頻課黃海廣老師《機器學習課程》711頁完整版課件

本站qq群554839127，加入微信群請掃碼：

總結

以上是生活随笔為你收集整理的图神经网络概述：Graph Neural Networks的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。