圖神經(jīng)網(wǎng)絡(luò)概述：Graph Neural Networks
https://distill.pub/2021/gnn-intro/
https://distill.pub/2021/understanding-gnns/
講圖神經(jīng)網(wǎng)絡(luò)(GNN)之前，先介紹一下什么是graph，為什么需要graph，以及graph有什么問題，然后介紹一下如何用GNN處理graph問題，最后從GNN推廣到GCN。
Graph
圖由Vertex(V)、Edge(E)和Global(U)三部分構(gòu)成。V可以表示為node identity或者number of neighbors，E可以表示為edge identity或者edge weight，U可以表示為number of nodes或者longest path。
為了進(jìn)一步描述每一個node、edge和entire graph，可以把信息存儲在graph的每個部分中。其實(shí)就是把信息以embedding的方式存儲。
還可以通過edge的方向性(有向的、無向的)來構(gòu)建特殊的圖。
Graphs and where to find them
graph data在生活中無處不在，比如最常見的image和text都可以認(rèn)為是graph data的一種特例，還有其他一些場景也可以用graph data表達(dá)。
Images as graphs
圖片的位置可以表示成(列數(shù)-行數(shù))的形式，將圖片構(gòu)建成adjacency matrix，藍(lán)色塊表示pixel和pixel之間相臨，無方向性，畫成graph就是右邊圖片的形式。
Text as graphs
文本也可以構(gòu)建成adjacency matrix，跟圖片不一樣的是，文本是一個有向圖，每個詞只跟前一個詞相連接，并且有方向性。
其他還有比如分子、社交網(wǎng)絡(luò)、學(xué)術(shù)引用網(wǎng)絡(luò)等等都可以構(gòu)建成graph。
What types of problems have graph structured data?
graph可以處理graph-level、node-level和edge-level三種層面的問題。
Graph-level task
輸入graph，輸出整個graph的類別。在圖像中，和圖像分類任務(wù)類似；在文本中，和句子情感分析類似。
Node-level task
輸入node不帶類別的graph，輸出每個node的類別。在圖像中，和語義分割類似；在文本中，和詞性分類類似。
Edge-level task
edge-level任務(wù)用來預(yù)測node之間的相互關(guān)系。如下圖所示，先將不同部分分割出來，然后判斷不同部分的相互關(guān)系。構(gòu)建成graph就是對edge進(jìn)行類別預(yù)測。
The challenges of using graphs in machine learning
如何用神經(jīng)網(wǎng)絡(luò)處理graph任務(wù)呢？
第一步是考慮如何表示和神經(jīng)網(wǎng)絡(luò)相兼容的圖。graph最多有4種想要預(yù)測的信息：node、edge、global-context和connectivity。前3個相對容易，比如可以用一個?
還有一個問題是，許多鄰接矩陣可以編碼相同的連通性，但是不能保證這些不同的矩陣在神經(jīng)網(wǎng)絡(luò)中會產(chǎn)生相同的結(jié)果(也就是說，它們不是置換不變的)。
一種優(yōu)雅而高效表示稀疏矩陣的方法是用鄰接表。edge ?
以一個graph的鄰接表為例，如下圖所示:
Graph Neural Networks
通過上面的描述，graph可以通過置換不變的鄰接表表示，那么可以設(shè)計(jì)一個graph neural networks(GNN)來解決graph的預(yù)測任務(wù)。
The simplest GNN
從最簡單的GNN開始，更新所有g(shù)raph的屬性(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做二分類任務(wù)，那么可以用一個linear classifier對graph進(jìn)行分類。
然而，有時候信息只儲存在edge中，那么就需要從edge收集信息轉(zhuǎn)移到node用于預(yù)測，這個過程稱之為pooling。
Pooling過程有兩個步驟：
1.對于要pooling的每一項(xiàng)(上圖一行中的一列)，收集它們的embedding并且concat到一個矩陣中（上圖中的一行）。
2.收集的embedding通過求和操作進(jìn)行聚合。
因此，如果只有edge-level的特征，可以通過pooling傳遞信息來預(yù)測node(上圖虛線表示pooling傳遞信息給node，然后進(jìn)行二分類)。
同理，如果只有node-level的特征，可以通過pooling傳遞信息來預(yù)測edge。類似CV中的global average pooling。
同理，可以通過node-level的特征預(yù)測global。
和CNN類似，通過GNN blocks可以構(gòu)建出一個end-to-end的GNN。
需要注意的是，在這個最簡單的GNN中，沒有在GNN layer使用graph的connectivity。每個node、每個edge以及global-context都是獨(dú)立處理的，只在聚合信息進(jìn)行預(yù)測的時候使用了connectivity。
Passing messages between parts of the graph
為了使learned embedding感知到graph的connectivity，可以在GNN layer使用pooling構(gòu)建出更加復(fù)雜的GNN(和convlution類似)?？梢允褂胢essage passing實(shí)現(xiàn)，相鄰node或者edge可以交換信息，并且影響彼此的embedding更新。
Message passing過程有三個步驟：
1.對于graph的每個node，收集所有相鄰node的embedding。
2.通過相加操作聚合所有message。
3.所有聚合的message都通過一個update function傳遞(通常使用一個可學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò))。
這些步驟是利用graph的connectivity的關(guān)鍵。在GNN layer中構(gòu)建更精細(xì)的message passing變體，可以獲得表達(dá)和能力更強(qiáng)的GNN模型。
通過堆疊的message passing GNN layer，一個node可以引入整個graph的信息：在三層GNN layer之后，一個node可以獲得3步遠(yuǎn)的node信息。
對最簡單的GNN范式進(jìn)行更新，增加一個message passing操作:
Learning edge representations
通過meassage passing，可以在GNN layer的node和edge之間共享信息。可以像之前使用相鄰node信息一樣，先將edge信息pooling，然后用update function轉(zhuǎn)化并且存儲，從而聚合來自相鄰edge的信息。
然而，存儲在graph中的node和edge信息不一定具有相同的大小或形狀，因此不能立刻知道如何將它們組合起來。一種方法是學(xué)習(xí)從node空間到edge空間的線性映射，或者，可以在update function之前將它們concat在一起。
在構(gòu)造GNN時，需要設(shè)計(jì)更新哪些graph屬性以及更新順序。比如可以使用weave的方式進(jìn)行更新，node to node(linear)，edge to edge(linear)，node to edge(edge layer)，edge to node(node layer)。
Adding global representations
上面描述的GNN模型還有一個缺陷：在graph中，距離很遠(yuǎn)的node無法有效的傳遞信息，對于一個node，如果有k個layer，那么信息傳遞的距離最多是k步，這對于依賴相距很遠(yuǎn)的node信息的預(yù)測任務(wù)來說，是比較嚴(yán)重的問題。一種解決辦法是讓所有node可以相互傳遞信息，但是對于大的graph來說，計(jì)算量會非常昂貴。另一種解決辦法是使用graph(U)的全局表示，稱為master node或者context vector。這個全局的context vector可以連接到網(wǎng)絡(luò)的所有node和edge，可以作為它們之間信息傳遞的橋梁，構(gòu)建出一個graph的整體表示。
從這個角度看，所有g(shù)raph屬性都可以通過將感興趣的屬性和其他屬性關(guān)聯(lián)，然后在pooling過程中利用起來。比如對于一個node，可以同時考慮相鄰的node、edge和global信息，然后通過concat將它們關(guān)聯(lián)起來，最后通過線性映射將它們映射到相同特征空間中。
The Challenges of Computation on Graphs
graph在計(jì)算中有三個挑戰(zhàn)：lack of consistent structure、node-order equivariance和scalability。
Lack of Consistent Structure
graph是極其靈活的數(shù)學(xué)模型，同時這意味著它們?nèi)狈鐚?shí)例的一致結(jié)構(gòu)。比如不同分子之間有不同的結(jié)構(gòu)。用一種可以計(jì)算的格式來表示graph并不是一件簡單的事情，graph的最終表示通常由實(shí)際問題決定。
Node-Order Equivariance
graph的node之間通常沒有內(nèi)在的順序，相比之下，在圖像中，每個像素都是由其在圖像中的絕對位置唯一決定的。因此，我們希望我們的算法是節(jié)點(diǎn)順序不變的:它們不應(yīng)該依賴于graph中node的順序。如果我們以某種方式對node進(jìn)行排列，則由算法計(jì)算得到的node表示也應(yīng)該以同樣的方式進(jìn)行排列。
Scalability
graph可以非常大，像Facebook和Twitter這樣的社交網(wǎng)絡(luò)，它們擁有超過10億的用戶，對這么大的數(shù)據(jù)進(jìn)行操作并不容易。幸運(yùn)的是，大多數(shù)自然出現(xiàn)的graph都是“稀疏的”:它們的邊數(shù)往往與頂點(diǎn)數(shù)成線性關(guān)系。graph的稀疏性導(dǎo)致可以使用特殊的方法有效計(jì)算graph中node的表示。另外，和graph的數(shù)據(jù)量相比，這些方法的參數(shù)要少得多。
Problem Setting and Notation
許多問題都可以用graph來表示:
Node Classification:?對單個節(jié)點(diǎn)進(jìn)行分類。
Graph Classification:?對整個圖進(jìn)行分類。
Node Clustering:?根據(jù)連接性將相似的節(jié)點(diǎn)分組。
Link Prediction:?預(yù)測缺失的鏈接。
Influence Maximization:?識別有影響的節(jié)點(diǎn)。
Extending Convolutions to Graphs
卷積神經(jīng)網(wǎng)絡(luò)在圖像中提取特征方面是非常強(qiáng)大的。而圖像本身可以看作是一種非常規(guī)則的網(wǎng)格狀結(jié)構(gòu)的圖，其中單個像素為節(jié)點(diǎn)，每個像素處的RGB通道值為節(jié)點(diǎn)特征。
因此，將卷積推廣到任意的graph是一個很自然的想法。然而，普通卷積不是節(jié)點(diǎn)順序不變的，因?yàn)樗鼈円蕾囉谙袼氐慕^對位置。graph可以通過執(zhí)行某種填充和排序，保證每個節(jié)點(diǎn)的鄰域結(jié)構(gòu)一致性，但是還有更加普遍和強(qiáng)大的方法來處理這個問題。
下面首先介紹一下在節(jié)點(diǎn)鄰域上構(gòu)造多項(xiàng)式濾波器的方法，這和CNN在相鄰像素上濾波類似。然后介紹更多最新的方法如何用更強(qiáng)大的機(jī)制擴(kuò)展這個想法。
Polynomial Filters on Graphs
The Graph Laplacian
給定一個graph G，用A來表示數(shù)值為0或者1的鄰接矩陣，用D表示對角度矩陣(矩陣對角線數(shù)值表示與行node相鄰node的數(shù)量)，那么?
Polynomials of the Laplacian
Laplacian的多項(xiàng)式可以表示為：
?
這些多項(xiàng)式可以認(rèn)為和CNN中“filters”等價(jià)，而系數(shù)w是“filters”的權(quán)重。
為了方便討論，下面考慮節(jié)點(diǎn)只有一維特性的情況(每個節(jié)點(diǎn)是一個數(shù)值)。使用前面選擇的節(jié)點(diǎn)順序，我們可以將所有節(jié)點(diǎn)特征堆在一起得到一個x向量。
通過構(gòu)造的特征向量x，可以定義它和多項(xiàng)式濾波器?
?
關(guān)于Laplacian矩陣如何作用在x上的解釋，參照https://distill.pub/2021/understanding-gnns/。
ChebNet
ChebNet對多項(xiàng)式濾波器公式進(jìn)行了改進(jìn):
?
其中?
Embedding Computation
下面介紹一下如何堆疊帶非線性的ChebNet(或者任何多項(xiàng)式過濾器) layer構(gòu)建成一個GNN，就像標(biāo)準(zhǔn)的CNN一樣。假設(shè)有K個不同的多項(xiàng)式過濾器層，?
GNN和CNN計(jì)算方式類似，將輸入作為初始features，然后計(jì)算多項(xiàng)式過濾器，然后和輸入特征進(jìn)行矩陣相乘，最后用非線性函數(shù)進(jìn)行非線性變換，循環(huán)迭代K次。
需要注意的是，GNN在不同的節(jié)點(diǎn)上過濾器權(quán)重參數(shù)共享，和CNN類似，CNN的卷積在不同位置也是參數(shù)共享的。
Modern Graph Neural Networks
ChebNet是graph中學(xué)習(xí)局部過濾器的一個突破，它激發(fā)了許多人從不同的角度思考圖卷積。
多項(xiàng)式過濾器對x卷積可以展開為：
?
這其實(shí)是一個1步局部卷積(也就是只跟直接相連的node卷積)，可以看成由兩個步驟產(chǎn)生：
1.聚合直接相鄰的特征?
2.結(jié)合node自身的特征?
通過確保聚合是node-order equivariant，來保證整個卷積是node-order equivariant。
這些卷積可以被認(rèn)為是相鄰節(jié)點(diǎn)之間的“message passing”:在每一步之后，每個節(jié)點(diǎn)從它的相鄰節(jié)點(diǎn)接收信息。
通過迭代重復(fù)K次1步局部卷積，感受野為K步遠(yuǎn)的所有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)絡(luò)的領(lǐng)域是極其廣闊的。下面提一下一些可能感興趣的點(diǎn)：
GNNs in Practice：如何提高GNN的效率、GNN的正則化技術(shù)
Different Kinds of Graphs：Directed graphs、Temporal graphs、Heterogeneous graphs
Pooling：SortPool、DiffPool、SAGPool
往期精彩回顧 本站qq群554839127，加入微信群請掃碼：