黄色以及电影毛片,亚洲视频中文,操逼网站在线视频,毛片操逼,www.偷拍,丁香五月成人社区,日本有码第1页,射综合视频

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

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)一步描述每一個(gè)node、edge和entire graph，可以把信息存儲(chǔ)在graph的每個(gè)部分中。其實(shí)就是把信息以embedding的方式存儲(chǔ)。

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

Graphs and where to find them

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

Images as graphs

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

Text as graphs

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

其他還有比如分子、社交網(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，輸出整個(gè)graph的類別。在圖像中，和圖像分類任務(wù)類似；在文本中，和句子情感分析類似。

Node-level task

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

Edge-level task

edge-level任務(wù)用來預(yù)測(cè)node之間的相互關(guān)系。如下圖所示，先將不同部分分割出來，然后判斷不同部分的相互關(guān)系。構(gòu)建成graph就是對(duì)edge進(jìn)行類別預(yù)測(cè)。

The challenges of using graphs in machine learning

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

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

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

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

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

Graph Neural Networks

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

The simplest GNN

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

GNN對(duì)graph的每個(gè)組件分開使用MLP，稱為GNN layer。對(duì)于每個(gè)node vetor，使用MLP后返回一個(gè)learned node-vector，同理edge會(huì)返回一個(gè)learned edge embedding，global會(huì)返回一個(gè)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ù)，那么可以用一個(gè)linear classifier對(duì)graph進(jìn)行分類。

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

Pooling過程有兩個(gè)步驟：

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

2.收集的embedding通過求和操作進(jìn)行聚合。

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

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

同理，可以通過node-level的特征預(yù)測(cè)global。

和CNN類似，通過GNN blocks可以構(gòu)建出一個(gè)end-to-end的GNN。

需要注意的是，在這個(gè)最簡(jiǎn)單的GNN中，沒有在GNN layer使用graph的connectivity。每個(gè)node、每個(gè)edge以及global-context都是獨(dú)立處理的，只在聚合信息進(jìn)行預(yù)測(cè)的時(shí)候使用了connectivity。

Passing messages between parts of the graph

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

Message passing過程有三個(gè)步驟：

1.對(duì)于graph的每個(gè)node，收集所有相鄰node的embedding。

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

3.所有聚合的message都通過一個(gè)update function傳遞(通常使用一個(gè)可學(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，一個(gè)node可以引入整個(gè)graph的信息：在三層GNN layer之后，一個(gè)node可以獲得3步遠(yuǎn)的node信息。

對(duì)最簡(jiǎn)單的GNN范式進(jìn)行更新，增加一個(gè)message passing操作:

Learning edge representations

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

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

在構(gòu)造GNN時(shí)，需要設(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模型還有一個(gè)缺陷：在graph中，距離很遠(yuǎn)的node無法有效的傳遞信息，對(duì)于一個(gè)node，如果有k個(gè)layer，那么信息傳遞的距離最多是k步，這對(duì)于依賴相距很遠(yuǎn)的node信息的預(yù)測(cè)任務(wù)來說，是比較嚴(yán)重的問題。一種解決辦法是讓所有node可以相互傳遞信息，但是對(duì)于大的graph來說，計(jì)算量會(huì)非常昂貴。另一種解決辦法是使用graph(U)的全局表示，稱為master node或者context vector。這個(gè)全局的context vector可以連接到網(wǎng)絡(luò)的所有node和edge，可以作為它們之間信息傳遞的橋梁，構(gòu)建出一個(gè)graph的整體表示。

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

The Challenges of Computation on Graphs

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

Lack of Consistent Structure

graph是極其靈活的數(shù)學(xué)模型，同時(shí)這意味著它們?nèi)狈鐚?shí)例的一致結(jié)構(gòu)。比如不同分子之間有不同的結(jié)構(gòu)。用一種可以計(jì)算的格式來表示graph并不是一件簡(jiǎn)單的事情，graph的最終表示通常由實(shí)際問題決定。

Node-Order Equivariance

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

Scalability

graph可以非常大，像Facebook和Twitter這樣的社交網(wǎng)絡(luò)，它們擁有超過10億的用戶，對(duì)這么大的數(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:?對(duì)單個(gè)節(jié)點(diǎn)進(jìn)行分類。

Graph Classification:?對(duì)整個(gè)圖進(jìn)行分類。

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

Link Prediction:?預(yù)測(cè)缺失的鏈接。

Influence Maximization:?識(shí)別有影響的節(jié)點(diǎn)。

Extending Convolutions to Graphs

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

因此，將卷積推廣到任意的graph是一個(gè)很自然的想法。然而，普通卷積不是節(jié)點(diǎn)順序不變的，因?yàn)樗鼈円蕾囉谙袼氐慕^對(duì)位置。graph可以通過執(zhí)行某種填充和排序，保證每個(gè)節(jié)點(diǎn)的鄰域結(jié)構(gòu)一致性，但是還有更加普遍和強(qiáng)大的方法來處理這個(gè)問題。

下面首先介紹一下在節(jié)點(diǎn)鄰域上構(gòu)造多項(xiàng)式濾波器的方法，這和CNN在相鄰像素上濾波類似。然后介紹更多最新的方法如何用更強(qiáng)大的機(jī)制擴(kuò)展這個(gè)想法。

Polynomial Filters on Graphs

The Graph Laplacian

給定一個(gè)graph G，用A來表示數(shù)值為0或者1的鄰接矩陣，用D表示對(duì)角度矩陣(矩陣對(duì)角線數(shù)值表示與行node相鄰node的數(shù)量)，那么? $D _ { v } = \sum _ { u } A _ { v u }$ ?。graph Laplacian矩陣L可以表示為：L=D - A。右圖的對(duì)角線就是行node的度數(shù)，負(fù)數(shù)是減去的鄰接矩陣(藍(lán)色數(shù)字和graph中的C對(duì)應(yīng))。

Polynomials of the Laplacian

Laplacian的多項(xiàng)式可以表示為：

? $p _ { w } ( L ) = w _ { 0 } I _ { n } + w _ { 1 } L + w _ { 2 } L ^ { 2 } + \ldots + w _ { d } L ^ { d } = \sum _ { i = 0 } ^ { d } w _ { i } L ^ { i }$ ?

這些多項(xiàng)式可以認(rèn)為和CNN中“filters”等價(jià)，而系數(shù)w是“filters”的權(quán)重。

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

通過構(gòu)造的特征向量x，可以定義它和多項(xiàng)式濾波器? $p _ { w }$ ?的卷積公式為：

? $x ^ { \prime } = p _ { w } ( L ) x$ ?

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

ChebNet

ChebNet對(duì)多項(xiàng)式濾波器公式進(jìn)行了改進(jìn):

? $p _ { w } ( L ) = \sum _ { i = 1 } ^ { d } w _ { i } T _ { i } ( \tilde { L } )$ ?

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

Embedding Computation

下面介紹一下如何堆疊帶非線性的ChebNet(或者任何多項(xiàng)式過濾器) layer構(gòu)建成一個(gè)GNN，就像標(biāo)準(zhǔn)的CNN一樣。假設(shè)有K個(gè)不同的多項(xiàng)式過濾器層，? $k ^ { \text {th } }$ ?的可學(xué)習(xí)參數(shù)表示為? $w ^ { ( k ) }$ ?，那么計(jì)算過程可以表示成：

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í)局部過濾器的一個(gè)突破，它激發(fā)了許多人從不同的角度思考圖卷積。

多項(xiàng)式過濾器對(duì)x卷積可以展開為：

? $\begin{aligned} ( L x ) _ { v } & = L _ { v } x \\ & = \sum _ { u \in G } L _ { v u } x _ { u } \\ & = \sum _ { u \in G } \left( D _ { v u } - A _ { v u } \right) x _ { u } \\ & = D _ { v } x _ { v } - \sum _ { u \in \mathcal { N } ( v ) } x _ { u } \end{aligned}$ ?

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

1.聚合直接相鄰的特征? $x_{u}$ ?。

2.結(jié)合node自身的特征? $x_{v}$ ?。

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

這些卷積可以被認(rèn)為是相鄰節(jié)點(diǎn)之間的“message passing”:在每一步之后，每個(gè)節(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

本文只是簡(jiǎn)單介紹了一下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

往期精彩回顧




適合初學(xué)者入門人工智能的路線及資料下載
機(jī)器學(xué)習(xí)及深度學(xué)習(xí)筆記等資料打印
機(jī)器學(xué)習(xí)在線手冊(cè)
深度學(xué)習(xí)筆記專輯
《統(tǒng)計(jì)學(xué)習(xí)方法》的代碼復(fù)現(xiàn)專輯
AI基礎(chǔ)下載
黃海廣老師《機(jī)器學(xué)習(xí)課程》視頻課
黃海廣老師《機(jī)器學(xué)習(xí)課程》711頁(yè)完整版課件
本站qq群554839127，加入微信群請(qǐng)掃碼：

圖神經(jīng)網(wǎng)絡(luò)概述：Graph Neural Networks